3.3.4) Protocolli a finestra scorrevole

Nei casi precedenti i frame dati viaggiano in una sola direzione e i frame di ack nella direzione contraria, quindi esistono dei frame che viaggiano in entrambe le direzioni.

Dunque, volendo stabilire una comunicazione dati bidirezionale è necessario disporre di due circuiti, il che ovviamente è uno spreco di risorse. Un'idea migliore è usare un solo circuito, nel quale far convivere tutte le esigenze.

Supponendo che la comunicazione sia fra A e B, si avrà che:

• nella direzione da A a B viaggiano i frame dati inviati da A a B e i frame di ack inviati da A a B (in risposta ai frame dati inviati da B ad A);
• nella direzione da B a A viaggiano i frame dati inviati da B a A e i frame di ack inviati da B a A (in risposta ai frame dati inviati da A ad B);
• il campo kind serve a distinguere fra i due tipi di frame, dati e di ack, che viaggiano nella stessa direzione.

Però c'è un'idea ancora migliore: se, quando si deve inviare un ack da B ad A, si aspetta un pò fin che è pronto un frame dati che B deve inviare ad A, si può "fare autostop" e mettere dentro tale frame dati anche le informazioni relative all'ack in questione. Questa tecnica si chiama piggybacking (letteralmente, portare a spalle).

Il campo ack serve proprio a questo scopo, infatti è il campo in cui viene trasportato, se c'è, un ack.

Questa tecnica consente un notevole risparmio di:

• banda utilizzata;
• uso di cpu.

Infatti, con questa tecnica le informazioni di ack non richiedono la costruzione di un apposito frame (e quindi il tempo necessario alla creazione ed al riempimento della struttura, al calcolo del checksum, ecc.) né la sua trasmissione (e quindi l'uso di banda).

Però c'è un aspetto da non trascurare: per quanto si può aspettare un frame su cui trasportare un ack che è pronto e deve essere inviato? Non troppo, perché se l'ack non arriva in tempo il mittente ritrasmetterà il frame anche se ciò non è necessario. Dunque si stabilisce un limite al tempo di attesa di un frame sul quale trasportare l'ack; trascorso tale tempo si crea un frame apposito nel quale si mette l'ack.

I protocolli che vedremo ora appartengono alla classe dei protocolli sliding window (finestra scorrevole), sono full-duplex (per i dati), sfruttano il piggybacking e sono più robusti di quelli precedenti.

Differiscono fra loro per efficienza, complessità e capacità dei buffer. Alcuni aspetti però sono comuni a tutti gli algoritmi:

• ogni frame inviato ha un numero di sequenza, da 0 a 2ⁿ-1 (il campo seq è costituito da n bit);
• ad ogni istante il mittente mantiene una finestra scorrevole sugli indici dei frame, e solo quelli entro la finestra possono essere trasmessi. I numeri di sequenza entro la finestra rappresentano frame da spedire o spediti, ma non ancora confermati:
  • quando arriva dal livello network un pacchetto, un nuovo indice entra nella finestra;
  • quando arriva un ack, il corrispondente indice esce dalla finestra;
  • i frame dentro la finestra devono essere mantenuti in memoria per la possibile ritrasmissione; se il buffer è pieno, il livello data link deve costringere il livello network a sospendere la consegna di pacchetti;
• analogamente, il destinatario mantiene una finestra corrispondente agli indici dei frame che possono essere accettati:
  • se arriva un frame il cui indice è fuori dalla finestra:
    • il frame viene scartato (e non si invia il relativo ack);
  • se arriva un frame il cui indice è entro la finestra:
    • il frame viene accettato;
    • viene spedito il relativo ack;
    • la finestra viene spostata in avanti;
  • si noti che la finestra del destinatario rimane sempre della stessa dimensione, e se essa è pari a 1 il livello accetta i frame solo nell'ordine giusto (ma per dimensioni maggiori di 1 questo non è più detto).
• le finestre di mittente e destinatario non devono necessariamente avere uguali dimensioni, né uguali limiti inferiori o superiori.

In questi protocolli il livello data link ha più libertà nell'ordine di trasmissione, fermo restando che:

• i pacchetti devono essere riconsegnati al livello network nello stesso ordine di partenza;
• il canale fisico è wire-like, cioé consegna i frame nell'ordine di partenza.

Protocollo a finestra scorrevole di un bit

In questo protocollo sia mittente che destinatario usano una finestra scorrevole di dimensione uno. Di fatto questo è un protocollo stop-and-wait.

Non c'è differenza di comportamento fra mittente e destinatario, tutt'e due usano lo stesso codice (questo vale anche per i protocolli successivi).

Il funzionamento, molto semplice, è il seguente:

• il mittente, quando invia un frame, fa partire un timer:
  • se prima che scada il timer arriva un ack con lo stesso numero di sequenza del frame che si sta cercando di trasmettere, si avanza la finestra e si passa a trasmettere il frame successivo;
  • se arriva un ack diverso o scade il timer, si ritrasmette il frame;
• il destinatario invece:
  • quando arriva un frame corretto, senza errori, invia un ack col corrispondente numero di sequenza;
  • se il frame non è un duplicato lo passa al livello network e avanza la finestra.

Qui sta la principale novità rispetto al protocollo 3: l'ack è etichettato col numero di sequenza del frame a cui si riferisce. I valori dell'etichetta possono solo essere 0 e 1, come nel protocollo 3.

Il peggio che può succedere è la ritrasmissione inutile di qualche frame, ma questo protocollo è sicuro.

Protocolli go-back-n e selective repeat

Se il tempo di andata e ritorno del segnale (round-trip time) è alto, come ad esempio nel caso dei canali satellitari nei quali è tipicamente pari a 500 + 500 msec, c'è un enorme inefficienza coi protocolli stop-and-wait, perché si sta quasi sempre fermi aspettando l'ack.

Per migliorare le cose, si può consentire l'invio di un certo numero di frame anche senza aver ricevuto l'ack del primo. Questa tecnica va sotto il nome di pipelining.

Ciò però pone un serio problema, perché se un frame nel mezzo della sequenza si rovina molti altri frame vengono spediti prima che il mittente sappia che qualcosa è andato storto.

Il primo approccio al problema è quello del protocollo go-back-n:

• se arriva un frame danneggiato o con un numero di sequenza non progressivo, il destinatario ignora tale frame e tutti i successivi, non inviando i relativi ack. Ciò corrisponde ad una finestra di dimensione uno nel ricevitore, che quindi accetta i frame solo nell'ordine giusto;
• il mittente ad un certo punto va in time-out sul frame sbagliato, e poi su tutti quelli successivi (scartati dal destinatario), e quindi provvede a ritrasmettere la sequenza di frame che inizia con quello per il quale si è verificato il time-out.

Si noti che il mittente deve mantenere in un apposito buffer tutti i frame non confermati per poterli eventualmente ritrasmettere. Se il buffer si riempie, il mittente deve bloccare il livello network fino a che non si ricrea dello spazio. Inoltre, vi è spreco di banda se il tasso d'errore è alto e/o il time-out è lungo.

Il secondo approccio è più efficiente, ed è chiamato selective repeat:

• il destinatario mantiene nel suo buffer tutti i frame ricevuti successivamente ad un eventuale frame rovinato; non appena questo arriva nuovamente (senza errori), esso e tutti i successivi frame contigui che il destinatario ha mantenuto nel buffer vengono consegnati al livello network;
• per ogni frame arrivato bene, il destinatario invia un ack col numero più alto della sequenza completa arrivata fino a quel momento;
• quando si verifica un timeout, il mittente rispedisce il frame corrispondente.

Alcune considerazioni a proposito del protocollo selective repeat:

• mittente e destinatario devono entrambi gestire un buffer per mantenervi i frame:
  • non confermati (mittente);
  • successivi ad un errore (destinatario);
• vi è un basso spreco di banda, che si si può ulteriormente diminuire mandando un NACK (Negative ACKnowledgement) quando:
  • arriva un frame danneggiato;
  • arriva un frame diverso da quello atteso (ciò può indicare l'avvenuta perdita del frame precedente).

Infine, si noti che 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.

3.4) Esempi di protocolli data link

I protocolli data link più diffusi oggi sono discendenti del protocollo SDLC (Synchronous Data Link Control), nato nell'ambito dell'architettura SNA. Nel seguito verranno illustrate brevemente le caratteristiche di tre diffusi protocolli: HDLC (standard ISO), SLIP (architettura TCP/IP) e PPP (suo successore).

3.4.1) HDLC (High Level Data Link Control)

E' un protocollo bit oriented, e quindi usa la tecnica del bit stuffing. Il formato del frame HDLC è illustrato nella figura seguente.

I campi del frame hanno le seguenti funzioni:

Le caratteristiche salienti sono le seguenti:

• usa una finestra scorrevole con numeri di sequenza a 3 bit, contenuti dentro un campo Seq situato all'interno del campo Control;
• utilizza il campo Next, anch'esso contenuto in Control, per il piggybacking degli ack;
• ha tre tipi di frame (identificati dai primi due bit di Control):
  • Information, per la trasmissione dati;
  • Supervisory, per comandare diverse modalità di ritrasmissione;
  • Unnumbered (non ha il numero di sequenza), per finalità di controllo o per trasportare il traffico di connessioni non affidabili.

3.4.2) SLIP (Serial Line IP)

E' nato nel 1984 ed è il più vecchio protocollo di livello data link dell'Internet Protocol Suite.

Molto semplice, nacque per collegare via modem macchine Sun ad Internet. Spedisce sulla linea pacchetti IP terminati col byte 0xC0. Usa character stuffing.

Ha diverse limitazioni:

• non c'è controllo degli errori;
• supporta solo IP, e per di più solo indirizzi statici;
• non è uno standard ufficiale di Internet.

3.4.3) PPP (Point to Point Protocol)

Per migliorare le cose, IETF ha prodotto uno standard ufficiale, il Point to Point Protocol (RFC 1661, 1662 e 1663). Esso è adatto sia a connessioni telefoniche che a linee router-router.

Esso fornisce le seguenti funzionalità:

• framing;
• rilevamento degli errori;
• un protocollo di controllo per attivare, testare e diasattivare la linea (LCP, Link Control Protocol, RFC 1570);
• supporto di molteplici protocolli di livello network;
• una famiglia di protocolli per negoziare opzioni di livello network (NCP, Network Control Protocol):
  • per ogni livello network supportato c'è un differente NCP;
  • ad esempio, nel caso di IP, NCP viene usato per negoziare un indirizzo IP dinamico;

Il traffico derivante (nelle fasi iniziali e finali della connessione) dall'uso dei protocolli LCP e NCP viene trasportato dentro i frame PPP.

Il protocollo è modellato su HDLC, ma con alcune differenze:

• è character-oriented anziché bit-oriented, e utilizza il character stuffing (quindi i frame sono costituiti da un numero intero di byte);
• c'è un campo apposito per il supporto multiprotocollo offerto al livello network.

Il formato del frame PPP è il seguente.

I campi del frame hanno le seguenti funzioni: