Sistemi di Telecomunicazione

SN SN3. Trasmettere il pacchetto numero in un frame contenente nel campo numero di sequenza. RNSe da B viene ricevuto un frame privo di errori contenente un numero di richiesta4. SN SN RNmaggiore di , aumentare a e tornare al passo 2. Se tale frame non viene ricevuto entro un ritardo finito, vai al passaggio 3.

L'algoritmo del nodo B per la trasmissione da A a B è il seguente:

1. RN 0,1. Inizializzare la variabile integer a quindi ripetere i passaggi 2 e 3 in un loop infinito.
2. Ogni volta che viene ricevuto un frame privo di errori da A contenente un numero SN RN di sequenza uguale a , consegnare il pacchetto ricevuto al livello superiore e RN incrementare .
3. In momenti arbitrari, ma entro un ritardo limitato dopo aver ricevuto da A un qualsiasi RN frame di dati privo di errori, trasmettere un frame ad A contenente nel campo del numero di richiesta.

Ci sono una serie di modi convenzionali per gestire i ritardi arbitrari tra le trasmissioni successive nell'algoritmo sopra. La procedura

L'approccio abituale per il nodo A (considerando solo la strategia di Stop-and-Wait per il traffico da A a B) è quello di avviare un timer all'inizio di una trasmissione del frame. Se il timer scade prima della ricezione di una richiesta per il pacchetto successivo da B, il timer viene riavviato e il pacchetto viene ritrasmesso in un nuovo frame. Se una richiesta per un nuovo pacchetto viene ricevuta da B prima della scadenza del timer, il timer viene fermato fino a quando A non trasmette il pacchetto successivo. Lo stesso tipo di gestione del timer può essere utilizzato nel nodo B. In alternativa, il nodo B potrebbe inviare un frame contenente una richiesta per il pacchetto atteso ogni volta che riceve un frame da A. Inoltre, se B sta trasmettendo i suoi numeri di richiesta in piggyback a un frame di dati, RN potrebbe semplicemente inviare il valore corrente di in ciascuno di questi frame. Si noti che ciò non è di per sé sufficiente, poiché la comunicazione da A a B

si fermerebbe in assenza di traffico da B ad A; pertanto, il nodo B deve inviare frame senza dati contenenti il valore di quando non c'è traffico dati da B ad A. Il punto importante è che, qualunque sia la strategia di temporizzazione utilizzata, bisogna garantire che l'intervallo che intercorre tra le ritrasmissioni in ogni direzione sia limitato.

Correttezza di Stop-and-Wait

Dimostrazioni di questo tipo di solito si suddividono in due parti, chiamate safety e liveness. Un algoritmo è safe (sicuro) se non produce mai un risultato errato, il che in questo caso significa non consegnare mai un pacchetto in disordine al livello superiore. Un algoritmo soddisfa la proprietà di liveness se può continuare per sempre a produrre risultati (cioè, se non può mai entrare in una condizione di deadlock da cui non è possibile progredire). In questo caso liveness

incapsulato per la prima volta in un frame per la trasmissione dal nodo A, ricevuto per la prima volta e consegnato al livello superiore dal nodo B, e riscontrata per la prima volta la sua ricezione al nodo A. Significa la capacità di continuare per sempre ad accettare nuovi pacchetti dal livello superiore nel nodo A e consegnarli al livello superiore in B. SNÈ possibile che Stop-and-Wait soddisfi il requisito di liveness dato che l'evoluzione di edRN è di tipo ciclico e può potenzialmente continuare all'infinito, come è possibile notare nella figura 3.20. Un problema della strategia di Stop-and-Wait sviluppata sopra è che i numeri di sequenza e i numeri delle richieste diventano arbitrariamente grandi allo scorrere del tempo. Anche se si potesse semplicemente usare un campo molto grande per l'invio di questi numeri, sarebbe più elegante inviare questi numeri in modulo (un qualsiasi numero intero). Avendo supposto che i frame viaggiano in ordine nel canale.si può dimostrare che è sufficiente rappresentare i valori modulo 2. Per capire perché è sufficiente inviare numeri di sequenza modulo, prima guardiamo più attentamente a ciò che accade nella Fig. 3.20 quando vengono utilizzati interi ordinari. Si nota che dopo che il nodo B riceve il pacchetto i al tempo t, i frame successivi ricevuti in B devono avere tutti numeri di sequenza ≥ i + 1 (poiché i frame inviati precedentemente non possono arrivare dopo). Allo stesso modo, mentre B è in attesa del pacchetto i, nessun pacchetto maggiore di i + 1 può essere inviato (dal momento che RN(t) = i + 1). Quindi, l'invio del numero di sequenza modulo è sufficiente per risolvere l'ambiguità. Lo stesso discorso vale per ogni SN(t) compreso tra i e i + 1. Infatti, nell'intervallo da SN(t) = i a SN(t) = i + 1, i numeri di sequenza ricevuti in A devono essere o i o i + 1.ancora, l'invio di modulo è sufficiente per risolvere l'ambiguità. Infine, poiché e devono essere trasmessi solo modulo è sufficiente tenerne traccia ai nodi solo modulo2 SN RN. Usando i valori modulo per e, possiamo modellare i nodi A e B come degli automi aSN RN due stati (ai fini del traffico da A a B), corrispondenti al valore binario di al nodo A e0; 1 al nodo B. Pertanto, A inizia nello stato una transizione allo stato si verifica alla ricezione di1 2 una richiesta senza errori per il pacchetto modulo. Si noti che A deve tenere traccia di più informazioni oltre a questo stato, come il contenuto del pacchetto corrente e il tempo residuo fino al timeout, ma esaminiamo solo lo stato binario. 0 1, 2 Il nodo B ha due possibili stati, e corrispondenti al numero modulo del pacchetto 2, attualmente atteso. Quando viene ricevuto un pacchetto con numero desiderato modulo il DLC in B consegna quel pacchetto al livello superiore e transita nell'altro stato.

attesa del7374 Gerardo Cicalese Antonio Giordano

Figura 3.21: Diagramma delle transizioni di stato per il protocollo ARQ Stop-and-Wait.

Lomod 2 RN mod 2stato è (SN al nodo A, al nodo B). (0, 0);pacchetto successivo (vedi Fig. 3.21).

Lo stato combinato di A e B è quindi inizialmente1,quando il primo pacchetto viene ricevuto senza errori, lo stato di B diventa producendo uno(0, 1). RN 1), 1stato combinato Quando A riceve il nuovo valore (cioè lo stato di A diventa e lo(1, 1).stato combinato diventa Si noti che esiste una successione fissa per questi stati combinati,(0, 0), (0, 1), (1, 1), (1, 0), (0, 0), e cosı̀ via, e che A e B si alternano nel cambiare gli stati.(0, 0) (0, 1),È interessante notare che nel momento della transizione da a B conosce lo stato(1, 1) (1, 0),combinato, ma successivamente, fino alla transizione successiva da a non conoscelo stato combinato (cioè, B non sa mai se A ha ricevuto le informazioni contenute nell’ACKfino a quando non viene ricevuto

Il pacchetto successivo). Allo stesso modo, A conosce lo stato(0, 1) (1, 1) (1, 0) (0, 0).combinato nell’istante della transizione da a e della transizione da aLo stato combinato è sempre sconosciuto almeno da A oppure a B, ed è spesso sconosciuto daentrambi. La situazione è molto simile a quella del problema delle tre armate discusso nellasottosezione 3.4.1. Qui, tuttavia, le informazioni vengono trasmesse anche se le informazionicombinate sullo stato non sono mai conosciute congiuntamente, mentre nel problema delletre armate è impossibile coordinare un attacco a causa dell’impossibilità di ottenere questeconoscenze combinate.

La strategia stop-and-wait non è molto utile per le moderne reti di dati a causa del suo utilizzoaltamente inefficiente dei collegamenti di comunicazione. In particolare, sarebbe preferibilepoter fare qualcos’altro in attesa di un ACK. Esistono due strategie comuni per estendere l’ideadi base dell’ARQ Stop-and-Wait in

Per ottenere una maggiore efficienza, è possibile utilizzare due protocolli ARQ: Go Back N e Selective Repeat.

Il problema delle due armate

Per acquisire familiarità con gli algoritmi distribuiti, come nel caso dei protocolli ARQ, introduciamo questo semplice problema, che riguarda le comunicazioni inaffidabili.

Ci sono tre armate, due color magenta e una color lavanda. L'armata lavanda divide in due le armate magenta, e se le armate magenta attaccano simultaneamente, vincono, ma se attaccano separatamente, vince l'armata lavanda. L'unica forma di comunicazione tra le armate magenta avviene tramite l'invio di un messaggero attraverso le linee dell'armata lavanda, ma c'è la possibilità che questo messaggero venga catturato, impedendo al messaggio di arrivare a destinazione (vedi Fig. 3.22). Le armate magenta vorrebbero sincronizzare i loro attacchi in un momento stabilito, ma nessuna delle due vuole attaccare se prima non è sicura che l'altra armata attaccherà.

Allora, la prima armata potrebbe inviare un messaggio del tipo "Attaccheremo sabato a mezzogiorno; per favore riscontrate la ricezione di questo messaggio se accettate." 7475 Gerardo Cicalese Antonio Giordano

La seconda armata, ricevendo questo messaggio, potrebbe inviare un messaggio di ritorno del tipo "Accettiamo; per favore riscontrate la ricezione di questo messaggio." Non è difficile notare che questa strategia porta a una sequenza infinita di messaggi, dato che l'ultima armata ad aver inviato il messaggio non attaccherà se prima non avrà ricevuto il riscontro di quel messaggio dalla controparte. Ciò

Che è sbalorditivo è che non esiste alcuna strategia che consenta alle due armate di sincronizzarsi. Per accorgersene, si assuma che ogni armata sia inizialmente nello stato e ci resta1, finché non riceve dei messaggi. Se un'armata inizia l'attacco, va nello stato ma non ci andrà1, finché non sarà certa che l'altra armata si trova nello stato. Si assuma, inoltre, che un'armata possa cambiare stato solo appena riceve il messaggio. Ora si consideri una qualsiasi sequenza di messaggi ricevuti da entrambe le armate. La prima armata che riceve il messaggio non può1, andare nello stato dato che non ha la certezza che l'altra armata abbia ricevuto il messaggio. La seconda armata riceve il messaggio, ma nemmeno può andare nello stato dato che non ha la certezza che la prima armata abbia ricevuto il messaggio.