Reti di Calcolatori a.a. 2005/06 Lezione 9

43
Reti di Calcolat ori Andrea Frosini 1 Reti di Calcolatori a.a. 2005/06 Lezione 9

description

Reti di Calcolatori a.a. 2005/06 Lezione 9. Nel modello di riferimento:. Protocolli bi-direzionali. Nei protocolli di livello Data Link uni-direzionali i frame dati viaggiano sempre nella stessa direzione ed i frame ack nell’altra - PowerPoint PPT Presentation

Transcript of Reti di Calcolatori a.a. 2005/06 Lezione 9

Page 1: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 1

Reti di Calcolatoria.a. 2005/06

Lezione 9

Page 2: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 2

Nel modello di riferimento:

Application

Transport

Network

Data Link

Fisico

Page 3: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 3

Protocolli bi-direzionali

Nei protocolli di livello Data Link uni-direzionali i frame dati viaggiano sempre nellastessa direzione ed i frame ack nell’altra

Una comunicazione bi-direzionale si può realizzare con due canali di comunicazione (almeno half-duplex) ciascuno utilizzante un protocollo uni-direzionale

In questo caso la banda passante di un canale è sotto-utilizzata se i frame dativiaggiano prevalentemente in una sola direzione

I protocolli bi-direzionali consentono di far viaggiare frame dati e frame ack sullostesso canale di comunicazione full-duplex in entrambe le direzioni

Per distinguere i due tipi di frame si utilizza il campo kind posto nella testata del frame

Page 4: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 4

Il piggybacking (letter. portare sulle spalle) è una tecnica che minimizzal’overhead dovuto alla trasmissione delle informazioni di acknowledgement

Funziona solo con protocolli bi-direzionali

Una entità di livello Data Link A invia un frame dati ad una entità di pari livello B

L’entità B che riceve il frame dati non invia subito un frame ack al mittente A. Alcontrario, l’acknowledgement è trasmesso codificando l’informazione nel campoack del successivo frame dati che B dovrà spedire a A

Si evita così l’overhead della costruzione del frame ack, del calcolo delchecksum, e della sua trasmissione (quindi si realizza un miglior uso della bandadel canale)

Piggybacking I

Page 5: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 5

Non è possibile che B attenda ad oltranza un frame dati a cui affidare l’acknowledgement

Se l’attesa fosse troppo lunga, il frame ack non potrebbe arrivare al mittente A primadella scadenza del timer, e quindi A rispedirebbe inutilmente il frame dati

L’attesa di B per un frame dati a cui affidare il trasporto dell’acknowledgement deveessere regolata da un timer

Scaduto il termine (pochi millisecondi), B deve inviare un normale frame ack

Piggybacking II

Page 6: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 6

Protocolli sliding window (a finestra scorrevole)

I protocolli sliding window sono una classe di protocolli per il livello Data Link

• sono bi-direzionali

• possono utilizzare il piggybacking

• sono più efficienti dei protocolli PAR

L’assunzione di base di questi protocolli è che il canale di comunicazione (livello Fisico) sia wire-like: due frame senza errori saranno ricevuti nello stesso ordine in cui

sono stati trasmessi

Page 7: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 7

In generale, nei protocolli sliding window non è necessario attendere l’acknowledgement di un frame dati prima di inviare il successivo

Di conseguenza, sono necessari più di due numeri di sequenza

In generale, assumiamo che il campo seq del frame sia costituito da n bit, e che dunque il numero di sequenza vari tra 0 e 2n – 1

Ad ogni istante sia chi trasmette che chi riceve mantiene una “finestra” (intervallo) di numeri di sequenza ammessi

Protocolli sliding window – Numeri di sequenza

Page 8: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 8

In ogni protocollo sliding window, al trasmittente è consentito inviare solo frame dati aventi un numero di sequenza compreso nella finestra di trasmissione (od anche finestra di invio)

La dimensione della finestra di trasmissione può variare, così come la sua posizione all’interno dell’insieme di numeri di sequenza. Ad esempio, se n=3 abbiamo 23 = 8 numeri di sequenza

Protocolli sliding window – Finestra di trasmissione

Nota Bene: se la finestra di trasmissione è vuota (ha dimensione zero), è sempre possibile estendere la sua dimensione ed inviare un frame!

10

45

2

3

7

6

finestra di dimensione 3

Page 9: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 9

In ogni protocollo sliding window, al ricevente è consentito accettare solo frame dati aventi un numero di sequenza compreso in un determinato intervallo chiamato finestra di ricezione. La posizione all’interno dell’insieme di numeri di sequenza della finestra di ricezione può variare; in genere (ma non sempre) la dimensione è fissata

Protocolli sliding window – Finestra di ricezione

La finestra di ricezione di una certa entità non è in alcun modo legata alla finestra di trasmissione della stessa entità. In generale, nel protocollo sliding window, la finestra di trasmissione del trasmittente e quella di ricezione del ricevente non sono identiche (possono essere in posizioni differenti nella sequenza di numeri, possono avere dimensioni differenti, eccetera)

10

45

2

3

7

6

finestra di dimensione 4del ricevente

Page 10: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 10

I numeri di sequenza all’interno della finestra di trasmissione rappresentano frame dati inviati, ma non ancora confermati

Quando il livello Network fornisce un nuovo pacchetto da inviare, l’entità del livello Data Link:

1. controlla che la finestra di trasmissione non abbia già raggiunto la dimensione massima

2. assegna al nuovo frame dati il più vicino numero di sequenza alla destra della finestra di trasmissione

3. trasmette il frame dati

4. allarga la finestra di trasmissione per includere il nuovo numero di sequenza (ovviamente non dovrà essere possibile allargare la finestra fino a comprendere tutti i 2n numeri)

Protocolli sliding window – Trasmissione I

Page 11: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 11

Tutti i frame dati il cui numero di sequenza è all’interno della finestra di trasmissione devono essere conservati in memoria

Infatti, la mancanza di conferma della loro ricezione implica la possibilità che essi debbano essere ritrasmessi

Quando si riceve un acknowledgement per il numero di sequenza più a sinistra della finestra di trasmissione:

1. la finestra viene accorciata escludendo tale numero

2. il buffer contenente il frame dati viene liberato

Protocolli sliding window – Trasmissione II

Page 12: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 12

I numeri di sequenza all’interno della finestra di ricezione rappresentano i frame dati che l’entità Data Link può accettare. La finestra di ricezione generalmente conserva sempre la stessa dimensione

Quando l’entità Data Link riceve un frame dati:

1. Se il suo numero di sequenza è al di fuori della finestra di ricezione, il frame dati viene scartato

2. Se il suo numero di sequenza è uguale al numero più a sinistra nella finestra, il pacchetto viene trasmesso al livello Network e la finestra di ricezione viene spostata verso destra e viene inviato l’ack corrispondente

3. Se il suo numero di sequenza è dentro la finestra di ricezione, ma non è il numero più a sinistra, il frame viene salvato in un buffer e NON viene inviato l’ack corrispondente (si ricordi l’assunzione che il canale è supposto wire-like, quindi il pacchetto più a sinistra è necessariamente andato perduto)

Protocolli sliding window – Ricezione

Page 13: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 13

Protocolli sliding window – Esempio

10

45

2

3

7

6

10

45

2

3

7

6

10

45

2

3

7

6

10

45

2

3

7

6

Trasmissione

Ricezione

10

45

2

3

7

6

10

45

2

3

7

6

10

45

2

3

7

6

10

45

2

3

7

6

Inizialmente Invio seq = 1 Ricez. seq = 1 Ricez. ack = 1

Page 14: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 14

E’ un protocollo stop-and-wait

La dimensione massima della finestra di trasmissione è 1

La dimensione della finestra di ricezione è fissata a 1

Simile al protocollo PAR, ma è bi-direzionale e usa il piggybacking

I numeri di sequenza sono solo 0 e 1

In trasmissione si controlla il campo ack di ciascun frame ricevuto: contiene il numero dell’ultimo frame passato al livello Network dall’altra entità:

• Se coincide con quello nella finestra di trasmissione, la finestra si svuota ed un nuovo pacchetto del livello Network può essere accettato

• Se il numero non coincide, il frame nella finestra di trasmissione viene ritrasmesso

• Se scade il timer fatto partire all’invio di un frame si ha ritrasmissione

Protocollo one bit sliding windows I

Page 15: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 15

In ricezione si accettano solo i frame il cui campo seq ha il valore incluso nella finestra di ricezione:

• Si pone nel campo ack del prossimo frame uscente il numero di sequenza del frame accettato

• Si fa avanzare la finestra di ricezione (si inverte il valore del numero di sequenza)

Anche quando il frame non è accettato, si continua ad impostare il campo ack dei successivi frame uscenti con il numero dell’ultimo frame accettato

Protocollo one bit sliding windows II

Page 16: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 16

Protocollo One Bit Sliding Window – Esempio I

host1 host2

(0,1,A2)

(0,0,B0)

(1,0,A1)

(1,1,B1)

(0,1,A0)

(0,1,A0)

(0,0,B0)

(1,0,A1)

(1,1,B1)

(0,1,A2)

Networkhost1

Networkhost2

Leggi:(seq, ack, packet number)

Page 17: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 17

Protocollo One Bit Sliding Window – Anomalia

Una strana anomalia accade quando host1 e host2 trasmettono i propri pacchetti simultaneamente, come mostrato nel lucido seguente:

• sia host1 che host2 ricevono due volte tutti i pacchetti inviati

• nella rete non ci sono perdite o errori nei pacchetti

• tale situazione può verificarsi anche nel caso in cui ci sia un primo trasmettitore, ma uno dei due timeout sia troppo breve

Page 18: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 18

Protocollo One Bit Sliding Window – Esempio II

host1 host2

(0,1,B0)

(0,1,A0)

(1,0,A1)

(0,1,A0)

(0,1,B0)

(0,0,A0)(0,0,B0)

(1,0,A1)

Networkhost1

Networkhost2

(0,0,A0)

(0,0,B0)

(1,0,B1)

(1,0,B1)

(1,1,B1)

(1,1,A1)

Leggi:(seq, ack, packet number)

Page 19: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 19

Protocolli sliding window con pipelining I

Il protocollo One Bit Sliding Window, ed in generale tutti i protocolli stop-and-wait, sono altamente inefficienti se il canale di comunicazioni ha un elevato round trip time (tempo di andata e ritorno del segnale)

Esempio: in un canale satellitare il ritardo tra la trasmissione di un frame e la ricezione di un ack può essere dell’ordine di 500 millisecondi

I protocolli sliding window con una finestra di trasmissione maggiore di uno sono molto più efficienti: è possibile inviare diversi frame prima di bloccare per attendere la conferma

La tecnica è in effetti un particolare tipo di pipelining

Page 20: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 20

Se il canale ha una capacità di b bit/sec, la dimensione del frame è l bit e il round trip time è R secondi, il massimo utilizzo della linea (in una direzione) è pari a

Utilizzo del canale con un protocollo stop and wait

Se il prodotto b R è grande, l’efficienza sarà bassa, a meno di non utilizzare frame molto lunghi

Ad esempio, l’efficienza di un protocollo stop and wait su un canale satellitare con

b = 100 kbps, l = 1000 bit e R = 500 millisecondi è

l / b

l / b + R=

l

l + b R

1000

1000 + 100000 · 0.5=

1

51 2 %

tempo invio frametempo totale operazione

Page 21: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 21

Utilizzo del canale con pipelining

Supponiamo di spedire W frame prima di bloccare in attesa della prima conferma.

L’utilizzo del canale sarà allora pari a:

Ad esempio, l’efficienza di un protocollo pipelining su un canale satellitare con

b = 100 kbps, l = 1000 bit, R = 500 millisecondi e W = 26 è

W · l / b

W · l / b + (R - (W - 1) · l / b )=

W l

l + b R

26 · 1000

1000 + 100000 · 0.5=

26

51 50 %

Page 22: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 22

Se un frame inviato insieme a tanti altri è danneggiato, esso deve essere scartato

Cosa fare con tutti gli altri frame ricevuti dopo quello scartato?

Vi sono essenzialmente due distinte strategie:

• Protocollo Go back n

• Protocollo Selective repeat

Protocolli sliding window con pipelining II

Page 23: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 23

Nel protocollo Go back n, tutti i frame ricevuti dopo un frame danneggiato (o perso) sono scartati: la finestra di ricezione è lunga 1

Se un frame ricevuto è scartato perché fuori sequenza, esso non viene mai confermato e neppure si confermano i successivi frame che arrivano (però il protocollo è bidirezionale, quindi continuano ad essere inviate le conferme relative all’ultimo frame passato al livello Network)

Quando il trasmittente va in time-out sul primo frame errato, ritrasmette l’intera sottosequenza di frame

Se il trasmittente riceve conferma per un certo frame, tale conferma vale anche per tutti i frame inviati precedentemente a lui e non ancora confermati

Questa strategia minimizza il numero di buffer dell’entità ricevente: vengono accettati solo i frame che possono essere immediatamente inviati al livello Network sovrastante

Protocollo Go back n

Page 24: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 24

Protocollo Go back n – Esempio

Page 25: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 25

Data una finestra di trasmissione di dimensione N + 1, i numeri di sequenza dei frame che potranno essere inviati saranno compresi tra 0 e N +1

Attenzione! Se venissero utilizzati soltanto numeri di sequenza da 0 a N, il protocollo non funzionerebbe, come mostra l’esempio:

1. Il trasmittente invia N +1 frame con numeri da 0 a N

2. Alla fine si riceve una conferma per il frame N

3. Il trasmittente invia altri N +1 frame con numeri da 0 a N

4. Alla fine si riceve un’altra conferma (via piggybacking) per il frame N

Problema: Se tutti i frame trasmessi al passo 3 fossero persi (o semplicemente venisse perso il frame 0, e tutti gli altri fossero scartati dal ricevente), il ricevente continuerebbe a trasmettere l’acknowledgement dell’ultimo frame del passo 1 accettato (frame N) e si creerebbe una situazione anomala

Protocollo Go back n – Numeri di sequenza

Page 26: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 26

Il protocollo Go back n non è efficiente su canali di comunicazione con elevato tasso d’errore. In questi casi il protocollo Selective repeat è migliore perché ha una finestra di ricezione di lunghezza maggiore di 1

Il destinatario memorizza in un buffer tutti i frame ricevuti dopo l’arrivo di un frame rovinato, con il rispettivo numero di sequenza all’interno della finestra di ricezione. Nessun ack viene inviato

Non appena il frame danneggiato viene ricevuto nuovamente, il destinatario passa tutti i frame presenti nel buffer al livello Network e invia un acknowledgment con il più alto numero di frame trasmesso al livello Network, ossia l’ultimo frame della sequenza completa ricevuta

Il trasmittente ritrasmette un frame solo in conseguenza di un timeout (oppure in caso di NAK—Negative Acknowledgement)

Protocollo Selective repeat

Page 27: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 27

Protocollo Selective repeat – Esempio

Page 28: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 28

Osserviamo:

• mittente e destinatario devono entrambi gestire un buffer per mantenervi i frame non confermati (mittente) successivi ad un errore (destinatario)

Protocollo Selective repeat – Gestione frame

host1 host2

• per entrambi i precedenti protocolli:

- è necessaria la gestione di timer multipli (uno per ogni frame inviato e non confermato)

- il ricevente, per inviare gli ack, usa il piggybacking se possibile, altrimenti invia un apposito frame

Xhack

Page 29: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 29

Protocollo Selective repeat – Numeri di sequenza I

Date finestre di trasmissione e ricezione di dimensione N, i numeri di sequenza dei frame saranno compresi tra 0 e 2N - 1

Attenzione! Se venissero utilizzati una quantità inferiore di numeri di sequenza il protocollo non funzionerebbe. Siano i numeri tra 0 e M, con M < 2N - 1

1. Il trasmittente invia frame con numeri da 0 a N - 1

2. Il ricevente li accetta e aggiorna la finestra di ricezione; se M < 2N - 1, 0 è

incluso nella nuova finestra

3. Tutte le conferme sono perse, ed il trasmittente invia nuovamente il frame 0

Page 30: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 30

Protocollo Selective repeat – Numeri di sequenza II

4. il frame 0 viene memorizzato come nuovo, e si invia l’ack per N - 1 (ultimo trasmesso a livello Network)

5. Il trasmittente assume che tutti i frame inviati nel passo 1 sono stati accettati, quindi invia N, N +1, N +2, . . . , M. . .

6. Il ricevente vede il frame M, che è all’interno della finestra di ricezione e lo passa al livello Network.

7. Il ricevente controlla il buffer per il frame 0: è pieno, dunque lo passa al livello Network

Problema: il frame 0 passato al livello Network la seconda volta appartiene alla prima sequenza!

Page 31: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 31

Negative Acknowledgement

Fino ad ora un frame con errori era considerato come un frame non arrivato e quindi semplicemente scartato

La tecnica chiamata NAK (Negative Acknowledgement) permette di migliorare l’efficienza dei protocolli

Un frame NAK è inviato al mittente quando il destinatario

• riceve un frame con errori, oppure

• riceve un frame con un numero di sequenza diverso da quello atteso

Il frame NAK contiene il numero di sequenza del frame che deve essere rispedito.

Migliora le prestazioni perché il trasmittente non deve aspettare la scadenza del timeout relativo

Page 32: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 32

Protocollo Selective repeat con NAK– Esempio

Page 33: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 33

Approfondimenti

Consideriamo il paragrafo

3.5 PROTOCOL VERIFICATION

del libro di testo “Computer Networks” di A.S. Tanenbaum

1. Cosa è un automa a stati finiti (finite state machine)?

2. Cosa è una rete di Petri (Petri net)?

3. Come possono essere utilizzati entrambi questi strumenti per specificare formalmente un protocollo?

Page 34: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 34

Protocollo HDLC

Il protocollo HDLC = High-level Data Link Control

• è un protocollo Data Link standard emanato dall’ISO ed è derivato dal protocollo SDLC (Synchronous Data Link Control) della architettura IBM SNA. Si è evoluto nei protocolli CCITT LAP (Link Access Procedure) e LAPB dello standard X.25

• è orientato al bit (non ai caratteri): usa la tecnica del bit stuffing per il framing

• il codice per la rilevazione di errori è una variante del CRC-CCITT (la variantefacilita la rilevazione dei flag byte persi)

• la gestione della trasmissione e flusso è essenzialmente un protocollo slidingwindow “Go back N” con numeri di sequenza a tre bit, dimensione massima della finestra di trasmissione pari a 7, NAK e piggybacking

Page 35: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 35

• Address: nelle linee multi-punto identifica i diversi terminali

• Control: informazioni di controllo quali numeri di sequenza e ack. Identificaanche il tipo di frame:

1. Information, per la trasmissione dei dati2. Supervisory, per le conferme e per controllare diverse modalità di trasmissione3. Unnumbered, per traffico di controllo o comunque non affidabile

Protocollo HDLC – Struttura del frame

01111110 01111110Address Control Data Checksum

8 bit 8 bit 8 bit 0 bit 16 bit 8 bit

Page 36: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 36

Il protocollo SLIP = Serial Line IP

• è il più vecchio protocollo Data Link utilizzato nell’architettura Internet Protocol Suite (1984), nato per collegare workstation Sun alla rete Internet tramite modem

• spedisce pacchetti IP terminati dal carattere 0xC0 (usa character stuffing sostituendo 0xDB 0xDC al posto di 0xC0 entro il pacchetto IP)

Protocollo SLIP

Non ha controllo di errori

Ha solo IP con indirizzi statici, e non ha alcuna forma di autenticazione

Non è standard ufficiale di Internet (regolato da RFC 1055 e 1144, ma esistono molte implementazioni incompatibili)

Page 37: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 37

Livello Data Link in Internet

In Internet c’è la necessità di un protocollo point-to-point (PPP protocol) per la gestione delle funzioni Data Link di framing, controllo errori, controllo del flusso etc.

home PC routermodem

modem

processo client che usa TCP/IP

linea telefonicaconvenzionale

connessione TCP/IPbasata su PPP

Page 38: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 38

Il protocollo PPP (= Point-to-Point Protocol)

• è uno standard Internet ufficiale (RFC 1661, 1662, 1663, 2153, e molti altri)

• meccanismo di framing basato su character stuffing, ove i byte delimitatori sono il flag byte 01111110, e il carattere di stuffing è il byte 01111101

• rilevazione d’errori con codice polinomiale, con 16 o 32 bit di controllo per frame

• supporta diversi protocolli di livello Network: IP, IPX, AppleTalk, . . . anche contemporaneamente

• generalmente non usa numeri di sequenza e ack , quindi non offre realmente un servizio affidabile (ma possono essere attivati, cfr RFC 1663)

Protocollo PPP

Page 39: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 39

Il protocollo PPP definisce due sotto-protocolli, i cui pacchetti vengono trasportati all’interno dei frame PPP

• LCP (Line Control Protocol): attiva e disattiva la linea seriale di comunicazione, e negozia i parametri a basso livello quali formato del frame, velocità di trasmissione…

• NCP (Network Control Protocol): negozia opzioni di livello network:

1. Per ogni livello network supportato c'è un differente NCP

2. Nel IP, NCP viene usato per negoziare un indirizzo IP dinamico

3. Il traffico derivante dall'uso dei protocolli LCP e NCP viene trasportato nei frame PPP

Sotto-protocolli LCP e NCP

Page 40: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 40

Formato del frame PPP

• Protocol: indica il protocollo di livello Network utilizzato (RFC 1700)

• Address: indica trasmissione broadcast, può essere assente

• Control: niente numero di sequenza e ack, può essere assente

01111110 01111110Address

11111111Control

00000011Data Checksum

8 bit 8 bit 8 bit variabile 2 o 4 byte 8 bit

Protocol

8 bit

Page 41: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 41

Esercizi

1. Sia data la seguente codifica:A: 01000111 B: 11100011 FLAG: 01111110 ESC: 11100000 Mostrare la sequenza binaria per il messaggio A B ESC FLAG con i framing- conteggio dei caratteri - flag bytes con byte stuffing- flag di inizio e fine e bit stuffing

2. La stringa di bit 0111101111101111110 deve essere trasmessa dal livello Data Link. Come si presenta tale stringa dopo il bit stuffing?

3. Messaggi di sedici bits sono trasmessi utilizzando il codice di Hamming per la correzione del singolo errore. Quanti check bits sono necessari? Assumendo la parità “pari”, qual è il messaggio trasmesso per la stringa di bit

1101001100110101 ?

4. Qual è il messaggio inviato se vogliamo utilizzare la codifica CRC per il messaggio 10100001 con polinomio generatore G(x)=1001?

Page 42: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 42

Esercizi

5. La stringa di bit 10011101 viene trasmessa utilizzando la codifica CRC con G(x)=1001. Durante la trasmissione il terzo bit del messaggio viene invertito. Mostrare che tale errore viene riconosciuto.

6. Un canale ha un bit rate di 4 kbps e un tempo di propagazione di 20 msec. Per quali valori della lunghezza del messaggio un protocollo stop-and-wait raggiunge l’efficienza del 50%?

7. Si consideri un canale satellitare privo di errore con velocità 64 kbps che invia messaggi di 512 byte ciascuno, con lunghezza dell’Ack trascurabile. Qual è il massimo bit rate se si utilizzano finestre di dimensione 1, 7, 15 e 127? Si assuma che il tempo di propagazione di un canale satellitare è posto a 270 msec.

8. Si consideri un cavo T1 (24 canali di ampiezza 8 bit ciascuno, con frequenza di invio di ciascun frame 8000 Hz) lungo 100 Km. La velocità di propagazione al suo interno è circa 2/3 c. Quanti bits “entrano” all’interno del cavo ad un determinato istante?

Page 43: Reti di Calcolatori a.a. 2005/06 Lezione 9

Reti di Calcolatori Andrea Frosini 43

Esercizi

9. Calcolare la lunghezza minima di un frame per ottenere un’efficienza del 40% su di un canale con bit rate di 600 kbps, tempo di propagazione di 200 msec e protocollo a finestra scorrevole con ampiezze W uguale a 1, 30, 100. Nel caso di W=30 qual è l’informazione massima (in bit) codificata in ciascun frame se si utilizza lo standard HDLC con correzione d’errore di Hamming per singolo bit?

10. Simulare la comunicazione tra due stazioni su di un canale con tasso d’errore del 20% e protocolli

i) Go back nii) Selective repeat

usando piggybacking, finestra trasmittente di ampiezza 6, finestra ricevente massima (caso ii)) di ampiezza 3 e 3 bit nel campo Seq.