379 Aldo Roveri, Fondamenti di reti Univ. di Roma La Sapienza - a.a. 2009-2010 III.LE FUNZIONI DEI...

1Aldo Roveri, “Fondamenti di reti” Univ. di Roma “La Sapienza” - a.a. 2009-2010

III. LE FUNZIONI DEI SERVIZI DI RETEI parte

III. LE FUNZIONI DEI SERVIZI DI RETEI parte


INDICEINDICE

• III.1 Le funzioni di base in una rete mobile• III.2 Controllo di accesso al mezzo• III.3 Controlli di errore e di flusso

• III.1 Le funzioni di base in una rete mobile• III.2 Controllo di accesso al mezzo• III.3 Controlli di errore e di flusso

III.1 Le funzioni di base in una rete mobileIII.1 Le funzioni di base in una rete mobile

Aldo Roveri, “Fondamenti di reti” Univ. di Roma “La Sapienza” - a.a. 2009-2010


CONTENUTICONTENUTI

III.1.1 La strategia cellulareIII.1.2 Funzioni di base in una rete mobile cellulareIII.1.1 La strategia cellulareIII.1.2 Funzioni di base in una rete mobile cellulare


III.1 LE FUNZIONI DI BASE IN UNA RETE MOBILE

III.1 LE FUNZIONI DI BASE IN UNA RETE MOBILE

III.1.1 La strategia cellulareIII.1.1 La strategia cellulare


Strategia cellulare (1/2)Strategia cellulare (1/2)

• Lo sviluppo delle comunicazioni mobili è stato per lungo tempo frenato da problemi di costo e di mancanza di banda.

• L’introduzione della strategia cellulare ha modifi-cato la situazione offrendo una efficienza tale da consentire l’adeguata diffusione del servizio e la riduzione dei costi.

• Lo sviluppo delle comunicazioni mobili è stato per lungo tempo frenato da problemi di costo e di mancanza di banda.

• L’introduzione della strategia cellulare ha modifi-cato la situazione offrendo una efficienza tale da consentire l’adeguata diffusione del servizio e la riduzione dei costi.


Strategia cellulare (2/2)Strategia cellulare (2/2)

• Circa la strategia cellulare occorre considerare che:– la potenza emessa dai terminali mobili deve

essere limitata per ridurre il loro peso/ingombro e per aumentarne l’autonomia;

– l’attenuazione delle onde radio in ambiente urbano e a livello stradale aumenta tipicamente con la quarta potenza della distanza.

• Circa la strategia cellulare occorre considerare che:– la potenza emessa dai terminali mobili deve

essere limitata per ridurre il loro peso/ingombro e per aumentarne l’autonomia;

– l’attenuazione delle onde radio in ambiente urbano e a livello stradale aumenta tipicamente con la quarta potenza della distanza.


Che cosa è una cella (1/4)Che cosa è una cella (1/4)

• Non è quindi possibile coprire vaste estensioni territoriali con un unico ricetrasmettitore fisso.

• Si deve invece suddividere l’area di servizio in sub-aree, che si sovrappongono solo parzialmente: in ognuna delle sub-aree la copertura elettromagne-tica è assicurata da un apposito ricetrasmettitore (stazione radiobase).

• Non è quindi possibile coprire vaste estensioni territoriali con un unico ricetrasmettitore fisso.

• Si deve invece suddividere l’area di servizio in sub-aree, che si sovrappongono solo parzialmente: in ognuna delle sub-aree la copertura elettromagne-tica è assicurata da un apposito ricetrasmettitore (stazione radiobase).



• Queste sub-aree, chiamate celle, assumono, nella realtà della propagazione delle onde radio, forme geometriche largamente irregolari;

• la linea di demarcazione tra una cella e un’altra rappresenta la transizione dalla copertura elettro-magnetica di un ricetrasmettitore a quella di un altro ricetrasmettitore.

• Queste sub-aree, chiamate celle, assumono, nella realtà della propagazione delle onde radio, forme geometriche largamente irregolari;

• la linea di demarcazione tra una cella e un’altra rappresenta la transizione dalla copertura elettro-magnetica di un ricetrasmettitore a quella di un altro ricetrasmettitore.



• Nella suddivisione dell’area di servizio in celle, spesso si fa riferimento a forme poligonali regolari, ad esempio a celle di forma esagonale, senza sovrapposizione (come in Fig. III.1): queste costitui-scono però solo una schematizzazione teorica di una realtà decisamente più complessa.

• Nella suddivisione dell’area di servizio in celle, spesso si fa riferimento a forme poligonali regolari, ad esempio a celle di forma esagonale, senza sovrapposizione (come in Fig. III.1): queste costitui-scono però solo una schematizzazione teorica di una realtà decisamente più complessa.



1

6

4

2 1 5 7

7 6 3

3 4 2

6 3 4 2

4

5

7

2

7

6 3

Fig. III.1


Simboli (1/2)Simboli (1/2)

• Con riferimento a un’area di servizio As ,indichiamo con

Q il numero di celle in cui è divisa l’area As;

N il numero totale di utenti contemporaneamente attivi da servire;

M il numero totale massimo di utenti contempo-raneamente attivi da servire;

• Con riferimento a un’area di servizio As ,indichiamo con

Q il numero di celle in cui è divisa l’area As;

N il numero totale di utenti contemporaneamente attivi da servire;

M il numero totale massimo di utenti contempo-raneamente attivi da servire;


Simboli (2/2)Simboli (2/2)

R il ritmo binario (in bit/s) richiesto da una singola comunicazione;

W la larghezza di banda radio che è resa disponibile per il servizio;

W0 la larghezza di banda equivalente richiesta per sostenere il ritmo R;

C la potenza media della portante radio,I la potenza media degli interferenti.

R il ritmo binario (in bit/s) richiesto da una singola comunicazione;

W la larghezza di banda radio che è resa disponibile per il servizio;

W0 la larghezza di banda equivalente richiesta per sostenere il ritmo R;

C la potenza media della portante radio,I la potenza media degli interferenti.


Dimensionamento delle celle (1/2)Dimensionamento delle celle (1/2)

• Nel dimensionamento delle celle, occorre tener conto di due obiettivi fondamentali: – il rispetto di una soglia minima nel rapporto C/I

, tra la potenza media C della portante radio e quella I degli interferenti;

– il conseguimento di una adeguata efficienza spettrale definita da

• Nel dimensionamento delle celle, occorre tener conto di due obiettivi fondamentali: – il rispetto di una soglia minima nel rapporto C/I

, tra la potenza media C della portante radio e quella I degli interferenti;

– il conseguimento di una adeguata efficienza spettrale definita da

W

NR


Dimensionamento delle celle (2/2)Dimensionamento delle celle (2/2)

• Il primo obiettivo deriva dalla qualità di servizio che deve essere assicurata ad ogni comunicazione;

• il secondo obiettivo è invece legato all’esigenza di un contenimento del costo per offrire il servizio (rappresentato dalla banda W), costo che è posto in relazione con il beneficio (rappresentato dal prodotto NR) che il servizio offre.

• Il primo obiettivo deriva dalla qualità di servizio che deve essere assicurata ad ogni comunicazione;

• il secondo obiettivo è invece legato all’esigenza di un contenimento del costo per offrire il servizio (rappresentato dalla banda W), costo che è posto in relazione con il beneficio (rappresentato dal prodotto NR) che il servizio offre.


Efficienza spettrale (1/4)Efficienza spettrale (1/4)

• L’efficienza spettrale può essere anche così espressa

in cuif = R / W0 è l’efficienza nella frequenza;s = N / M è l’efficienza nello spazio.

• L’efficienza spettrale può essere anche così espressa

in cuif = R / W0 è l’efficienza nella frequenza;s = N / M è l’efficienza nello spazio.

0f s

NR R N

W W M



• L’efficienza nella frequenza f [misurata in (bit/s)/ Hz] dipende dalla capacità del metodo di mo-demodulazione di compattare la larghezza di banda del segnale trasmesso a parità di ritmo binario R della comunica-zione.

• L’efficienza nello spazio s dipende invece dalla capacità dello spazio stesso di resistere alle interferenze, fissato che sia il filtraggio spaziale (ad es. mediante un’accorta progettazione delle antenne) che esiste nel territorio.

• L’efficienza nella frequenza f [misurata in (bit/s)/ Hz] dipende dalla capacità del metodo di mo-demodulazione di compattare la larghezza di banda del segnale trasmesso a parità di ritmo binario R della comunica-zione.

• L’efficienza nello spazio s dipende invece dalla capacità dello spazio stesso di resistere alle interferenze, fissato che sia il filtraggio spaziale (ad es. mediante un’accorta progettazione delle antenne) che esiste nel territorio.



• Se gli utenti attivi sono distribuiti uniformemente sull’area di servizio, in ogni cella si ha lo stesso numero NQ di utenti attivi e quindi

N = NQ Q

• Se, a parità di area di servizio, si diminuisce la dimensione delle celle, Q aumenta.

• Allora aumenta anche N se si tiene invariato il numero NQ di utenti (e quindi di canali) attivi per cella.

• Se gli utenti attivi sono distribuiti uniformemente sull’area di servizio, in ogni cella si ha lo stesso numero NQ di utenti attivi e quindi

N = NQ Q

• Se, a parità di area di servizio, si diminuisce la dimensione delle celle, Q aumenta.

• Allora aumenta anche N se si tiene invariato il numero NQ di utenti (e quindi di canali) attivi per cella.



• Si conclude che, con la suddivisione in celle e nei limiti di validità delle ipotesi precedente-mente effettuate, si può avere un numero N senza limitazioni con una larghezza di banda W finita.

• Si conclude che, con la suddivisione in celle e nei limiti di validità delle ipotesi precedente-mente effettuate, si può avere un numero N senza limitazioni con una larghezza di banda W finita.


Raggio minimo di cella (1/3)Raggio minimo di cella (1/3)

• A correggere questa conclusione interviene però la mobilità degli utenti, che determina il cambio di cella durante una comunicazione e che richiede quindi lo svolgimento della procedura di handover.

• A correggere questa conclusione interviene però la mobilità degli utenti, che determina il cambio di cella durante una comunicazione e che richiede quindi lo svolgimento della procedura di handover.



• La procedura di handover diviene sempre più critica (per lo scambio di informazioni di controllo da essa richiesto tra gli organi di rete) via via che le celle si riducono di raggio.

• Per contenere l’entità qualitativa e quantitativa di questo scambio si giunge a un valore minimo di raggio di cella sulla base del quale si consegue l’efficienza massima.

• La procedura di handover diviene sempre più critica (per lo scambio di informazioni di controllo da essa richiesto tra gli organi di rete) via via che le celle si riducono di raggio.

• Per contenere l’entità qualitativa e quantitativa di questo scambio si giunge a un valore minimo di raggio di cella sulla base del quale si consegue l’efficienza massima.



• In ogni sistema di grande capacità, i raggi minimi delle celle sono sempre tali che, anche con ridotte potenze a disposizione, l’effetto disturbante del rumore di fondo ( rumore termico o altro disturbo esterno al sistema) è trascurabile.

• Non avviene così per le interferenze di altri utenti attivi che diventano la causa limitante prima della capacità del sistema.

• Nelle valutazioni di efficienza è dunque ragionevole riferirsi all’efficienza limite che si ottiene trascurando l’effetto del rumore di fondo.

• In ogni sistema di grande capacità, i raggi minimi delle celle sono sempre tali che, anche con ridotte potenze a disposizione, l’effetto disturbante del rumore di fondo ( rumore termico o altro disturbo esterno al sistema) è trascurabile.

• Non avviene così per le interferenze di altri utenti attivi che diventano la causa limitante prima della capacità del sistema.

• Nelle valutazioni di efficienza è dunque ragionevole riferirsi all’efficienza limite che si ottiene trascurando l’effetto del rumore di fondo.


Settorizzazione delle celleSettorizzazione delle celle

• La capacità di un sistema cellulare, a parità del numero di stazioni radio-base (SRB) che coprono il territorio di servizio, può essere aumentata con la settorizzazione delle celle, ad esempio con la divisione di una cella di forma esagonale in tre o in sei settori.

• Ogni settore è servito da un’antenna settoriale; in tal modo il numero delle celle è moltiplicato per tre o per sei, come lo è il numero delle antenne SRB.

• Tuttavia il numero delle localizzazioni delle SRB è rimasto lo stesso, in quanto le antenne settoriali hanno la stessa localizzazione.

• La capacità di un sistema cellulare, a parità del numero di stazioni radio-base (SRB) che coprono il territorio di servizio, può essere aumentata con la settorizzazione delle celle, ad esempio con la divisione di una cella di forma esagonale in tre o in sei settori.

• Ogni settore è servito da un’antenna settoriale; in tal modo il numero delle celle è moltiplicato per tre o per sei, come lo è il numero delle antenne SRB.

• Tuttavia il numero delle localizzazioni delle SRB è rimasto lo stesso, in quanto le antenne settoriali hanno la stessa localizzazione.


III.1 LE FUNZIONI DI BASE INUNA RETE MOBILE

III.1 LE FUNZIONI DI BASE INUNA RETE MOBILE

III.1.2 Funzioni di base in una rete mobile cellulare

III.1.2 Funzioni di base in una rete mobile cellulare


Funzioni di base (1/4)Funzioni di base (1/4)

• Una rete mobile (MN - Mobile Network), qualunque sia la sua tecnica realizzativa, comprende sempre una sezione di accesso in cui

– i legamenti di utente utilizzano il mezzo radio come supporto trasmissivo;

– una opportuna funzione di accesso rende disponibile un canale radio all'utente in movimento quando questi ne ha necessita' per chiamare o per essere chiamato.

• Una rete mobile (MN - Mobile Network), qualunque sia la sua tecnica realizzativa, comprende sempre una sezione di accesso in cui

– i legamenti di utente utilizzano il mezzo radio come supporto trasmissivo;

– una opportuna funzione di accesso rende disponibile un canale radio all'utente in movimento quando questi ne ha necessita' per chiamare o per essere chiamato.



• Oltre alla funzione di accesso, una rete mobile deve essere in grado di svolgere altre tre funzioni fondamentali, e cioè:

– l'identificazione dell'utente e la sua autenticazione, ossia la possibilità di individuare univocamente l'apparecchio terminale a cui fa capo l'utente mobile, quando questi richiede un accesso.

• Oltre alla funzione di accesso, una rete mobile deve essere in grado di svolgere altre tre funzioni fondamentali, e cioè:

– l'identificazione dell'utente e la sua autenticazione, ossia la possibilità di individuare univocamente l'apparecchio terminale a cui fa capo l'utente mobile, quando questi richiede un accesso.



• l'aggiornamento della posizione dell'utente (localiz-zazione), ossia la possibilità di aggiornare, in modo continuo ed automatico, in un'appropriata banca di dati, la posizione dell'apparecchio terminale a cui fa capo l'utente mobile: ciò nonostante gli spostamenti di quest’ultimo in un'area anche molto estesa, purché nei limiti della regione di copertura della rete mobile.

• l'aggiornamento della posizione dell'utente (localiz-zazione), ossia la possibilità di aggiornare, in modo continuo ed automatico, in un'appropriata banca di dati, la posizione dell'apparecchio terminale a cui fa capo l'utente mobile: ciò nonostante gli spostamenti di quest’ultimo in un'area anche molto estesa, purché nei limiti della regione di copertura della rete mobile.



– l’handover dei canali radio, ossia la possibilità per l'utente mobile di mantenere il legamento con la MN pur nella necessita' di cambiare il canale radio che lo connette alla rete; questa necessita' può manife-starsi, ad esempio:

» nel passaggio da un'area ad un'altra adiacente che e' caratterizzata da una differente copertura radio;

» nella degradazione della qualità del canale radio che e' stato precedentemente assegnato.

– l’handover dei canali radio, ossia la possibilità per l'utente mobile di mantenere il legamento con la MN pur nella necessita' di cambiare il canale radio che lo connette alla rete; questa necessita' può manife-starsi, ad esempio:

» nel passaggio da un'area ad un'altra adiacente che e' caratterizzata da una differente copertura radio;

» nella degradazione della qualità del canale radio che e' stato precedentemente assegnato.


Reti mobile e fissaReti mobile e fissa

• Circa il legame tra reti mobili e reti fisse, finora queste due reti si sono sviluppate come strutture separate tra le quali sussistono solo i rapporti di inter-lavoro necessari per consentire le comunicazioni tra due utenti facenti capo alle due reti.

• E’ però prevedibile a breve termine l'integrazione tra rete fissa (rete POTS o Internet) e rete mobile.

• Requisito di tale integrazione e' il reciproco beneficio in termini di efficienza e di flessibilità nella fornitura di nuovi servizi con elevate prestazioni.

• Circa il legame tra reti mobili e reti fisse, finora queste due reti si sono sviluppate come strutture separate tra le quali sussistono solo i rapporti di inter-lavoro necessari per consentire le comunicazioni tra due utenti facenti capo alle due reti.

• E’ però prevedibile a breve termine l'integrazione tra rete fissa (rete POTS o Internet) e rete mobile.

• Requisito di tale integrazione e' il reciproco beneficio in termini di efficienza e di flessibilità nella fornitura di nuovi servizi con elevate prestazioni.

III.2 Controllo di accesso al mezzoIII.2 Controllo di accesso al mezzo



CONTENUTICONTENUTI

• III.2.1: Mezzi multiaccesso • III.2.2: Tecniche di accesso multiplo• III.2.3: Modello di accesso perfetto• III.2.4: Accesso casuale• III.2.5: Accesso casuale in ambiente radio (Wireless)• III.2.6: Accesso controllato

• III.2.1: Mezzi multiaccesso • III.2.2: Tecniche di accesso multiplo• III.2.3: Modello di accesso perfetto• III.2.4: Accesso casuale• III.2.5: Accesso casuale in ambiente radio (Wireless)• III.2.6: Accesso controllato


III.2 CONTROLLO DI ACCESSO AL MEZZO (MAC)


III.2.1 Mezzi multiaccessoIII.2.1 Mezzi multiaccesso


Mezzo trasmissivo (1/3)Mezzo trasmissivo (1/3)

• Consente il trasferimento dell’informazione tra due o più punti topologicamente a distanza.

• Supporta per questo scopo la via fisica (canale trasmissivo) su cui si propagano i segnali informativi.

• Consente il trasferimento dell’informazione tra due o più punti topologicamente a distanza.

• Supporta per questo scopo la via fisica (canale trasmissivo) su cui si propagano i segnali informativi.



• E’ punto - punto quando consente trasferimenti da una sola estremità emittente ad una sola ricevente (mezzo mono-accesso);

• in questo caso il segnale ricevuto dipende unicamente dal segnale trasmesso e dal disturbo su quel canale trasmissivo.

• Esempio: il doppino di rame tra la borchia telefonica dell’utente e l’attacco di utente in centrale

• E’ punto - punto quando consente trasferimenti da una sola estremità emittente ad una sola ricevente (mezzo mono-accesso);

• in questo caso il segnale ricevuto dipende unicamente dal segnale trasmesso e dal disturbo su quel canale trasmissivo.

• Esempio: il doppino di rame tra la borchia telefonica dell’utente e l’attacco di utente in centrale



• E’ multi-accesso quando comprende due o più punti distinti che sono sorgenti e/o collettori di informazione (stazioni);

• in questo caso il segnale ricevuto in una stazione dipende dal segnale trasmesso da due o più tra le altre stazioni ed è la somma delle versioni attenuate di questi segnali, corrotti da disturbi e da ritardi.

• Esempio: il mezzo radio intorno ai 900 MHz per la trasmissione di segnali tra terminali GSM e il loro punto di accesso alla rete fissa (BTS)

• E’ multi-accesso quando comprende due o più punti distinti che sono sorgenti e/o collettori di informazione (stazioni);

• in questo caso il segnale ricevuto in una stazione dipende dal segnale trasmesso da due o più tra le altre stazioni ed è la somma delle versioni attenuate di questi segnali, corrotti da disturbi e da ritardi.

• Esempio: il mezzo radio intorno ai 900 MHz per la trasmissione di segnali tra terminali GSM e il loro punto di accesso alla rete fissa (BTS)




III.2.2 Tecniche di accesso multiploIII.2.2 Tecniche di accesso multiplo


Accesso multiplo (1/2)Accesso multiplo (1/2)

• Se il mezzo trasmissivo è condiviso (LAN, radio) occorrono funzioni per la gestione dell’accesso multiplo.

• Queste sono realizzate mediante una tecnica di multiplazione dell’informazione ed eventualmente un protocollo MAC (Medium Access Control).

• La caratteristica distintiva dell’accesso multiplo è la condivisione della capacità di un mezzo multiaccesso da parte di un insieme di stazioni, mediante una multiplazione distribuita.

• Se il mezzo trasmissivo è condiviso (LAN, radio) occorrono funzioni per la gestione dell’accesso multiplo.

• Queste sono realizzate mediante una tecnica di multiplazione dell’informazione ed eventualmente un protocollo MAC (Medium Access Control).

• La caratteristica distintiva dell’accesso multiplo è la condivisione della capacità di un mezzo multiaccesso da parte di un insieme di stazioni, mediante una multiplazione distribuita.


Accesso multiplo (2/2)Accesso multiplo (2/2)

• Aspetti fondamentali dell’accesso multiplo che permettono una classificazione delle relative procedure sono–una allocazione statica o dinamica–una decisione centralizzata o distribuita.

• Aspetti fondamentali dell’accesso multiplo che permettono una classificazione delle relative procedure sono–una allocazione statica o dinamica–una decisione centralizzata o distribuita.


Allocazione statica o dinamica (1/3)Allocazione statica o dinamica (1/3)

• I due tipi di allocazione riguardano la modalità secondo cui la capacità del mezzo multi-accesso viene resa disponibile alle varie stazioni che al mezzo fanno capo.

• I due tipi di allocazione riguardano la modalità secondo cui la capacità del mezzo multi-accesso viene resa disponibile alle varie stazioni che al mezzo fanno capo.



• Nella modalità statica, in analogia a una multiplazione statica

– la capacità del mezzo è suddivisa in canali, che sono pre-assegnati individualmente alle stazioni che ne fanno richiesta all’inizio della comunicazione e che li rilasciano alla sua conclusione;

– i singoli canali sono pertanto assegnati e rilasciati indipendentemente da una loro effettiva utilizza-zione;

– sono quindi identificabili una fase di instaurazione, una fase di trasferimento e una di rilascio.

• Nella modalità statica, in analogia a una multiplazione statica

– la capacità del mezzo è suddivisa in canali, che sono pre-assegnati individualmente alle stazioni che ne fanno richiesta all’inizio della comunicazione e che li rilasciano alla sua conclusione;

– i singoli canali sono pertanto assegnati e rilasciati indipendentemente da una loro effettiva utilizza-zione;

– sono quindi identificabili una fase di instaurazione, una fase di trasferimento e una di rilascio.



• Nella modalità dinamica, in analogia a una multiplazione dinamica, l’intera capacità del mezzo è assegnata a domanda, tenendo quindi conto delle effettive necessità di utilizzazione da parte delle singole stazioni accedenti

• Nella modalità dinamica, in analogia a una multiplazione dinamica, l’intera capacità del mezzo è assegnata a domanda, tenendo quindi conto delle effettive necessità di utilizzazione da parte delle singole stazioni accedenti


Decisione centralizzata o distribuitaDecisione centralizzata o distribuita

• In una decisione centralizzata, l’organo decisore è localizzato in una stazione-base che provvede a gestire le richieste di accesso al mezzo e a soddisfare queste richieste con una pre-assegnazione individuale (allocazione statica) o con una assegnazione a domanda (allocazione dinamica).

• In una decisione distribuita, che trova applicazione solo nel caso di allocazione dinamica, alle stazioni accedenti è affidata la delega di coordinarsi mutuamente per consentire l’accesso al mezzo.

• In una decisione centralizzata, l’organo decisore è localizzato in una stazione-base che provvede a gestire le richieste di accesso al mezzo e a soddisfare queste richieste con una pre-assegnazione individuale (allocazione statica) o con una assegnazione a domanda (allocazione dinamica).

• In una decisione distribuita, che trova applicazione solo nel caso di allocazione dinamica, alle stazioni accedenti è affidata la delega di coordinarsi mutuamente per consentire l’accesso al mezzo.


Modalità di condivisione (1/2)Modalità di condivisione (1/2)

• La condivisione del mezzo multi-accesso può essere attuata con tecniche che si distinguono in base ai domini che, in alternativa o in unione, sono oggetto di utilizzazione in ogni comunicazione.

• I domini, che nel tempo sono stati la base per un accesso multiplo, sono quelli –della frequenza;–del tempo;–dei codici.

• La condivisione del mezzo multi-accesso può essere attuata con tecniche che si distinguono in base ai domini che, in alternativa o in unione, sono oggetto di utilizzazione in ogni comunicazione.

• I domini, che nel tempo sono stati la base per un accesso multiplo, sono quelli –della frequenza;–del tempo;–dei codici.


Modalità di condivisione (2/2)Modalità di condivisione (2/2)

• Esaminiamo queste tre alternative nel caso di accesso multiplo con allocazione statica;

• nel caso invece di allocazione dinamica, ci limitere-mo a considerare il caso di accesso a divisione di tempo.

• Esaminiamo queste tre alternative nel caso di accesso multiplo con allocazione statica;

• nel caso invece di allocazione dinamica, ci limitere-mo a considerare il caso di accesso a divisione di tempo.


Tecniche di accesso multiplo

Tecniche di accesso multiplo

Accesso multiplo

Con allocazione statica

Controllata Casuale

Con allocazione dinamica

In modo centralizzato

In modo distribuito


Accesso multiplocon allocazione statica

Accesso multiplocon allocazione statica

• In relazione al dominio utilizzato si distinguono accessi multipli:

– a divisione di frequenza (FDMA - Frequency Division Multiple Access) o a divisione di lunghezza d’onda (WDMA – Wavelength Division Multiple Access);

– a divisione di tempo (TDMA – Time Division Multiple Access);

– a divisione di codice (CDMA – Code Division Multiple Access).

• Sono state inoltre utilizzate tecniche miste, ad esempio del tipo FDMA/TDMA.

• In relazione al dominio utilizzato si distinguono accessi multipli:

– a divisione di frequenza (FDMA - Frequency Division Multiple Access) o a divisione di lunghezza d’onda (WDMA – Wavelength Division Multiple Access);

– a divisione di tempo (TDMA – Time Division Multiple Access);

– a divisione di codice (CDMA – Code Division Multiple Access).

• Sono state inoltre utilizzate tecniche miste, ad esempio del tipo FDMA/TDMA.


FDMA (1/6)FDMA (1/6)

• Nella tecnica FDMA, la banda passante del mezzo condiviso è suddivisa in sotto-bande di frequenza aventi uguale larghezza, come in una multiplazione a divisione di frequenza.

• Ad ogni coppia di stazioni tra le quali deve essere inizializzata una comunicazione, viene pre-assegnata, per tutta la durata di questa comuni-cazione, una di tali sotto-bande (banda di stazione).

• Nella tecnica FDMA, la banda passante del mezzo condiviso è suddivisa in sotto-bande di frequenza aventi uguale larghezza, come in una multiplazione a divisione di frequenza.

• Ad ogni coppia di stazioni tra le quali deve essere inizializzata una comunicazione, viene pre-assegnata, per tutta la durata di questa comuni-cazione, una di tali sotto-bande (banda di stazione).



• In tal modo, nell’ambito della comunicazione a cui è stata pre-assegnata una specifica banda di stazio-ne,– la stazione emittente può trasmettere

» in modo tempo-continuo il segnale che è di supporto all’informazione da trasferire;

» con l’utilizzazione della sola frazione della banda passante del mezzo condiviso individuata dalla banda di stazione assegnata alla comunicazione;

• In tal modo, nell’ambito della comunicazione a cui è stata pre-assegnata una specifica banda di stazio-ne,– la stazione emittente può trasmettere

» in modo tempo-continuo il segnale che è di supporto all’informazione da trasferire;

» con l’utilizzazione della sola frazione della banda passante del mezzo condiviso individuata dalla banda di stazione assegnata alla comunicazione;



– la stazione ricevente può estrarre il segnale ad essa pertinente con una operazione di filtraggio passa-banda centrata sulla banda di stazione assegnata alla comunicazione.

• Tra le stazioni emittente e ricevente viene in tal modo instaurato un canale che è di trasferimento per le informazioni da scambiare.

– la stazione ricevente può estrarre il segnale ad essa pertinente con una operazione di filtraggio passa-banda centrata sulla banda di stazione assegnata alla comunicazione.




• Le bande di stazione, che sono nell’intorno di frequenze portanti equidistanziate sull’asse delle frequenze, ripartiscono la banda passante del mezzo condiviso con un inter-vallo tra due sotto-bande adiacenti; ciascuno di questi intervalli costituisce una banda di guardia e ha lo scopo di facilitare l’operazione di filtraggio in ricezione, consentendo così di contenere le interferenze tra i segnali trasferiti in bande di stazione adiacenti.

• Le bande di stazione, che sono nell’intorno di frequenze portanti equidistanziate sull’asse delle frequenze, ripartiscono la banda passante del mezzo condiviso con un inter-vallo tra due sotto-bande adiacenti; ciascuno di questi intervalli costituisce una banda di guardia e ha lo scopo di facilitare l’operazione di filtraggio in ricezione, consentendo così di contenere le interferenze tra i segnali trasferiti in bande di stazione adiacenti.



• L’FDMA è la tecnica di accesso multiplo utilizzata, ad esempio, sull’interfaccia radio dei sistemi radio-mobile cellulari (analogici) di prima generazione, come il TACS (Total Access Communication System).

• L’FDMA è la tecnica di accesso multiplo utilizzata, ad esempio, sull’interfaccia radio dei sistemi radio-mobile cellulari (analogici) di prima generazione, come il TACS (Total Access Communication System).


FDMA (6/6)FDMA (6/6)F

req

ue

nza

Tempo

bande di stazione

bande di guardia

Ba

nd

a p

ass

an

te


TDMA (1/7)TDMA (1/7)

• Nella tecnica TDMA, l’asse dei tempi, relativo all’intera banda passante del mezzo condiviso o a una sua frazione nell’intorno di una frequenza portante (banda di lavoro), è suddiviso in intervalli temporali (IT) di ugual durata, organizzati in trama, come in una multiplazione statica a divisione di tempo;

• in relazione al mezzo trasmissivo utilizzato, la banda di lavoro può anche essere quella base (cioè nell’intorno della frequenza zero).

• Nella tecnica TDMA, l’asse dei tempi, relativo all’intera banda passante del mezzo condiviso o a una sua frazione nell’intorno di una frequenza portante (banda di lavoro), è suddiviso in intervalli temporali (IT) di ugual durata, organizzati in trama, come in una multiplazione statica a divisione di tempo;

• in relazione al mezzo trasmissivo utilizzato, la banda di lavoro può anche essere quella base (cioè nell’intorno della frequenza zero).



Ba

nd

a d

i la

voro

Tempo

ITIntervalli di guardia

trama

Fre

qu

en

za



• Ad ogni coppia di stazioni tra le quali deve essere inizializzata una comunicazione, viene pre-assegnato, per tutta la durata della comunicazione, un IT a periodicità di trama.

• Ad ogni coppia di stazioni tra le quali deve essere inizializzata una comunicazione, viene pre-assegnato, per tutta la durata della comunicazione, un IT a periodicità di trama.



• In tal modo, nell’ambito di una comunicazione a cui è stato pre-assegnato uno specifico IT a periodicità di trama

– la stazione emittente» trasmette solo in modo tempo-discreto, e cioè

nelle frazioni del suo asse dei tempi che corrisponde periodicamente all’ IT che le è stato assegnato;

» utilizza l’intera banda di lavoro.

• In tal modo, nell’ambito di una comunicazione a cui è stato pre-assegnato uno specifico IT a periodicità di trama

– la stazione emittente» trasmette solo in modo tempo-discreto, e cioè

nelle frazioni del suo asse dei tempi che corrisponde periodicamente all’ IT che le è stato assegnato;

» utilizza l’intera banda di lavoro.



–La stazione ricevente, che deve essere sincroniz-zata in frequenza e fase con quella emittente (condizione di sincronismo di cifra e di trama), può estrarre il segnale ad essa pertinente con una operazione di finestratura temporale centrata periodicamente sull’IT assegnato alla comunica-zione.


–La stazione ricevente, che deve essere sincroniz-zata in frequenza e fase con quella emittente (condizione di sincronismo di cifra e di trama), può estrarre il segnale ad essa pertinente con una operazione di finestratura temporale centrata periodicamente sull’IT assegnato alla comunica-zione.




• In relazione al mezzo condiviso che si utilizza, gli IT in ogni trama possono o meno essere separati temporalmente da intervalli di guardia, aventi lo scopo (quando presenti) di contenere le interfe-renze che possono determinarsi tra i segnali che sono trasferiti in IT adiacenti.

• In relazione al mezzo condiviso che si utilizza, gli IT in ogni trama possono o meno essere separati temporalmente da intervalli di guardia, aventi lo scopo (quando presenti) di contenere le interfe-renze che possono determinarsi tra i segnali che sono trasferiti in IT adiacenti.



• Il TDMA, in unione con l’FDMA per la definizione di varie frequenze portanti e quindi di varie bande di lavoro, è la tecnica utilizzata sull’interfaccia radio dei sistemi radio-mobili cellulari (numerici) di seconda generazione, come il GSM (Global System for Mobile Communication).

• Il TDMA, in unione con l’FDMA per la definizione di varie frequenze portanti e quindi di varie bande di lavoro, è la tecnica utilizzata sull’interfaccia radio dei sistemi radio-mobili cellulari (numerici) di seconda generazione, come il GSM (Global System for Mobile Communication).


CDMA (1/6)CDMA (1/6)

• Nella tecnica CDMA si opera nel dominio dei codici, consentendo alle stazioni di comunicare–utilizzando contemporaneamente l’intera banda

passante del mezzo condiviso;–emettendo in modo tempo-continuo (e cioè

senza alcuna limitazione sugli istanti in cui iniziare e terminare una emissione).

• Nella tecnica CDMA si opera nel dominio dei codici, consentendo alle stazioni di comunicare–utilizzando contemporaneamente l’intera banda

passante del mezzo condiviso;–emettendo in modo tempo-continuo (e cioè

senza alcuna limitazione sugli istanti in cui iniziare e terminare una emissione).



Ba

nd

a p

ass

an

te

Tempo

Fre

qu

en

za



• A ciascuna coppia di stazioni da porre in comunicazione e quando ne viene fatta richiesta, viene pre-assegnato per tutta la durata della comunicazione, un codice e cioè una sequenza binaria (sequenza di codice), che

– è utilizzata in emissione per codificare in modo univoco l’informazione di utente che ha origine nella stazione emittente e per trasformare il segnale di utente in quello trasmesso con il risultato di produrre una espansione dello spettro di densità di potenza (SDP) del segnale di utente;

• A ciascuna coppia di stazioni da porre in comunicazione e quando ne viene fatta richiesta, viene pre-assegnato per tutta la durata della comunicazione, un codice e cioè una sequenza binaria (sequenza di codice), che

– è utilizzata in emissione per codificare in modo univoco l’informazione di utente che ha origine nella stazione emittente e per trasformare il segnale di utente in quello trasmesso con il risultato di produrre una espansione dello spettro di densità di potenza (SDP) del segnale di utente;



–è diversa da quelle assegnate alle altre stazioni che condividono il mezzo e scelta in modo che, rispetto alle altre sequenze, sussista una bassa correlazione;

–è utilizzata dalla stazione ricevente per recuperare il segnale di utente dal segnale ricevuto; questo recupero si effettua con una decodifica, che ha come risultato la compressione dell’SDP del segnale ricevuto in modo da restituire un segnale con SDP uguale a quello del segnale di utente.

–è diversa da quelle assegnate alle altre stazioni che condividono il mezzo e scelta in modo che, rispetto alle altre sequenze, sussista una bassa correlazione;

–è utilizzata dalla stazione ricevente per recuperare il segnale di utente dal segnale ricevuto; questo recupero si effettua con una decodifica, che ha come risultato la compressione dell’SDP del segnale ricevuto in modo da restituire un segnale con SDP uguale a quello del segnale di utente.



• Il recupero del segnale di utente è tanto più adeguato allo scopo quanto più bassa è la correlazione tra la sequenza di codice assegnata e le sequenze di codice associate a comunicazioni contemporanea-mente attive.

• In tal modo tra le stazioni emittente e ricevente in una comunicazione viene reso disponibile un canale che è di trasferimento per le informazioni da scambiare.

• Il recupero del segnale di utente è tanto più adeguato allo scopo quanto più bassa è la correlazione tra la sequenza di codice assegnata e le sequenze di codice associate a comunicazioni contemporanea-mente attive.

• In tal modo tra le stazioni emittente e ricevente in una comunicazione viene reso disponibile un canale che è di trasferimento per le informazioni da scambiare.



• La tecnica CDMA può essere realizzata con due modalità corrispondenti ai modi per effettuare la codifica in emissione e la decodifica in ricezione; le modalità sono – il DSSS (Direct Sequence Spread Spectrum);– il FHSS (Frequency Hopping Spread Spectrum).

• La tecnica CDMA, realizzata nella modalità DSSS, è impiegata sull’interfaccia radio dei sistemi radio-mobili cellulari di terza generazione (ad es. nell’UMTS – Universal Mobile Telecommunication System).

• La tecnica CDMA può essere realizzata con due modalità corrispondenti ai modi per effettuare la codifica in emissione e la decodifica in ricezione; le modalità sono – il DSSS (Direct Sequence Spread Spectrum);– il FHSS (Frequency Hopping Spread Spectrum).

• La tecnica CDMA, realizzata nella modalità DSSS, è impiegata sull’interfaccia radio dei sistemi radio-mobili cellulari di terza generazione (ad es. nell’UMTS – Universal Mobile Telecommunication System).


Accesso multiplo con allocazione dinamica (1/4)


• La capacità del mezzo trasmissivo è indivisa o suddivisa in quanti (usualmente nel dominio del tempo) assegnabili a domanda, esclusivamente a fronte di una effettiva esigenza di utilizzazione.

• L’emissione di ogni stazione avviene, come in una multiplazione dinamica, tramite unità informative che, nella loro intestazione, debbono contenere l’indirizzo della stazione di destinazione (oltre a quello della stazione di origine) e altre informazioni di natura protocollare.

• La capacità del mezzo trasmissivo è indivisa o suddivisa in quanti (usualmente nel dominio del tempo) assegnabili a domanda, esclusivamente a fronte di una effettiva esigenza di utilizzazione.

• L’emissione di ogni stazione avviene, come in una multiplazione dinamica, tramite unità informative che, nella loro intestazione, debbono contenere l’indirizzo della stazione di destinazione (oltre a quello della stazione di origine) e altre informazioni di natura protocollare.




• Un accesso multiplo con allocazione dinamica implica sempre contese di utilizzazione, che si verificano quando due o più stazioni fanno contemporaneamente richiesta di accesso allo stesso mezzo di trasferimento.

• Un accesso multiplo con allocazione dinamica implica sempre contese di utilizzazione, che si verificano quando due o più stazioni fanno contemporaneamente richiesta di accesso allo stesso mezzo di trasferimento.




• In base alle modalità di risoluzione delle contese di utilizzazione, si distinguono–accessi casuali, quando ogni stazione ha libertà

di decidere quando iniziare la propria emissione;–accessi controllati, quando l’accesso di ogni

stazione avviene in maniera ordinata, rispettando una opportuna sequenza.

• In base alle modalità di risoluzione delle contese di utilizzazione, si distinguono–accessi casuali, quando ogni stazione ha libertà

di decidere quando iniziare la propria emissione;–accessi controllati, quando l’accesso di ogni

stazione avviene in maniera ordinata, rispettando una opportuna sequenza.




• Nel caso di accesso casuale, che è sempre a decisione distribuita, due o più stazioni possono emettere in intervalli di tempo che sono a copertura totale o parziale: il risultato può essere la distruzione parziale o totale delle UI in ricezione (evento di collisione).

• Nel caso di accesso controllato, che può essere con decisione centralizzata o distribuita, ogni stazione emette in intervalli di tempo che non sono mai sovrapposti a quelli di emissione di altre stazioni; sono quindi esclusi eventi di collisione.

• Nel caso di accesso casuale, che è sempre a decisione distribuita, due o più stazioni possono emettere in intervalli di tempo che sono a copertura totale o parziale: il risultato può essere la distruzione parziale o totale delle UI in ricezione (evento di collisione).

• Nel caso di accesso controllato, che può essere con decisione centralizzata o distribuita, ogni stazione emette in intervalli di tempo che non sono mai sovrapposti a quelli di emissione di altre stazioni; sono quindi esclusi eventi di collisione.


I protocolli MAC (1/2)I protocolli MAC (1/2)

• In entrambi i casi di accessi casuale e controllato, la decisione di accesso, quando è di tipo distribuito (come è possibile nel caso di accesso controllato) è regolata da un protocollo di accesso al mezzo (protocollo MAC – Medium Access Control).

• In entrambi i casi di accessi casuale e controllato, la decisione di accesso, quando è di tipo distribuito (come è possibile nel caso di accesso controllato) è regolata da un protocollo di accesso al mezzo (protocollo MAC – Medium Access Control).


I protocolli MAC (2/2)I protocolli MAC (2/2)

• I protocolli MAC si distinguono in–protocolli MAC con collisione, quando impiegati

in accessi casuali;–protocolli MAC senza collisione, quando

impiegati in accessi controllati.• Le unità informative che sono scambiate

nell’ambito di un protocollo MAC sono indicate qui nel seguito come MAC-PDU o come trame.

• I protocolli MAC si distinguono in–protocolli MAC con collisione, quando impiegati

in accessi casuali;–protocolli MAC senza collisione, quando

impiegati in accessi controllati.• Le unità informative che sono scambiate

nell’ambito di un protocollo MAC sono indicate qui nel seguito come MAC-PDU o come trame.




III.2.3 Modello di accesso perfettoIII.2.3 Modello di accesso perfetto


Modello di accesso multiplo (1/3)


Indichiamo con:• C la capacità di trasferimento (in bit/s) del

mezzo di comunicazione;max il massimo ritardo di propagazione (in s) fra

due stazioni che accedono al mezzo;• F la lunghezza (in bit) di una MAC-PDU tipica

che transita sul mezzo di comunicazione; la lunghezza del canale trasmissivo (in bit) normalizzata rispetto alla lunghezza F.

Indichiamo con:• C la capacità di trasferimento (in bit/s) del

mezzo di comunicazione;max il massimo ritardo di propagazione (in s) fra

due stazioni che accedono al mezzo;• F la lunghezza (in bit) di una MAC-PDU tipica

che transita sul mezzo di comunicazione; la lunghezza del canale trasmissivo (in bit) normalizzata rispetto alla lunghezza F.




Osserviamo che:

• il prodotto Cmax rappresenta la lunghezza del canale trasmissivo espressa in bit e cioè il numero massimo di bit che possono essere in transito tra due stazioni a distanza massima in un qualunque istante di osservazione;

• in base alle definizioni risulta:

Osserviamo che:

• il prodotto Cmax rappresenta la lunghezza del canale trasmissivo espressa in bit e cioè il numero massimo di bit che possono essere in transito tra due stazioni a distanza massima in un qualunque istante di osservazione;

• in base alle definizioni risulta:

max max ./

C

F F C




• Pertanto il parametro è anche uguale a

• valori tipici di sono nell’intervallo 0,01 - 1 ;• esistono tuttavia casi (accesso multiplo in

collegamenti via satellite) in cui il ritardo di propagazione prevale sul tempo di trasmissione ( > 1).

• Pertanto il parametro è anche uguale a

• valori tipici di sono nell’intervallo 0,01 - 1 ;• esistono tuttavia casi (accesso multiplo in

collegamenti via satellite) in cui il ritardo di propagazione prevale sul tempo di trasmissione ( > 1).

;netrasmissioditemponepropagaziodiritardo


Accesso multiplo perfetto (1/5)


Mostriamo come il parametro determina un limite supe-riore al rendimento di utilizzazione U del si-stema multi-accesso.

Mostriamo come il parametro determina un limite supe-riore al rendimento di utilizzazione U del si-stema multi-accesso.




A questo scopo, assumendo un accesso perfetto,

supponiamo che • il meccanismo di accesso consenta un solo

trasferimento alla volta;• il traffico comporti trasferimenti senza soluzione di

continuità;• il ritardo di propagazione non varii modificando le

stazioni tra cui avviene il trasferimento.

A questo scopo, assumendo un accesso perfetto,

supponiamo che • il meccanismo di accesso consenta un solo

trasferimento alla volta;• il traffico comporti trasferimenti senza soluzione di

continuità;• il ritardo di propagazione non varii modificando le

stazioni tra cui avviene il trasferimento.




• Il valor massimo di U è esprimibile come rapporto tra la portata media massima che il sistema di accesso è in grado di smaltire e la capacità di trasferimento del mezzo

• rappresenta quindi il massimo traffico medio che il sistema è in grado di smaltire.

• Il valor massimo di U è esprimibile come rapporto tra la portata media massima che il sistema di accesso è in grado di smaltire e la capacità di trasferimento del mezzo

• rappresenta quindi il massimo traffico medio che il sistema è in grado di smaltire.

;maxC

mediaportatamaxU




• D’altra parte per le ipotesi fatte

• quindi

• D’altra parte per le ipotesi fatte

• quindi

max max /

max portata media

F

ritardo di propag. tempo di transmissione

F C C

F/C 1 C F 1

.1

1Umax




• max U è unitario solo nel caso ideale in cui è uguale a zero;

• per ogni positivo, U satura ad 1/(1+) indipendentemente dal meccanismo di accesso;

• per massimizzare il valore di U è conveniente tenere il valore di il più piccolo possibile.

• max U è unitario solo nel caso ideale in cui è uguale a zero;

• per ogni positivo, U satura ad 1/(1+) indipendentemente dal meccanismo di accesso;

• per massimizzare il valore di U è conveniente tenere il valore di il più piccolo possibile.




Po

rtat

a m

edia

Carico medio0,1 0,2 0,5 0,9

0,1

0,2

0,5

0,9

= 10

= 5

= 1

= 0,1




III.2.4 Accesso casuale III.2.4 Accesso casuale


Protocolli ad accesso multiplo casuale (1/2)Protocolli ad accesso multiplo casuale (1/2)

• Le contese di utilizzazione del mezzo possono generare collisioni in ricezione.

• I protocolli MAC di questo tipo sono numerosi; se ne citano qui quattro tipi:

protocollo ALOHAprotocollo CSMAprotocollo CSMA/CDprotocollo CSMA/CA

• Le contese di utilizzazione del mezzo possono generare collisioni in ricezione.

• I protocolli MAC di questo tipo sono numerosi; se ne citano qui quattro tipi:

protocollo ALOHAprotocollo CSMAprotocollo CSMA/CDprotocollo CSMA/CA


Protocolli ad accesso multiplo casuale (2/2)Protocolli ad accesso multiplo casuale (2/2)

• In protocolli di questo tipo le prestazioni sono condizionate dall’intervallo di vulnerabilità e cioè, l’intervallo massimo di tempo entro cui una stazione può iniziare una emissione e collidere con un’altra emissione.

• Si chiama poi dominio di collisione la porzione di rete nella quale collidono le MAC-PDU emesse da due stazioni che emettono all’interno dell’intervallo di vulnerabilità di una tra queste.

• In protocolli di questo tipo le prestazioni sono condizionate dall’intervallo di vulnerabilità e cioè, l’intervallo massimo di tempo entro cui una stazione può iniziare una emissione e collidere con un’altra emissione.

• Si chiama poi dominio di collisione la porzione di rete nella quale collidono le MAC-PDU emesse da due stazioni che emettono all’interno dell’intervallo di vulnerabilità di una tra queste.


Principio base del protocollo–Una stazione può emettere una MAC-PDU non

appena questa è disponibile; viene quindi applicata la regola “trasmetti subito senza preoccuparti delle iniziative di altre stazioni”;

Principio base del protocollo–Una stazione può emettere una MAC-PDU non

appena questa è disponibile; viene quindi applicata la regola “trasmetti subito senza preoccuparti delle iniziative di altre stazioni”;

Protocollo ALOHA (1/4)Protocollo ALOHA (1/4)


–se la stazione emittente non riceve un riscontro positivo dalla stazione di destina-zione entro un determinato intervallo di tempo (time-out), si assume che si sia verificata una collisione;

–occorre allora riemettere la PDU corrispon-dente; per evitare nuove collisioni si rende casuale la riemissione; cioè questa è ritardata di un intervallo di tempo calcolato in base ad un algoritmo di subentro (backoff).

–se la stazione emittente non riceve un riscontro positivo dalla stazione di destina-zione entro un determinato intervallo di tempo (time-out), si assume che si sia verificata una collisione;

–occorre allora riemettere la PDU corrispon-dente; per evitare nuove collisioni si rende casuale la riemissione; cioè questa è ritardata di un intervallo di tempo calcolato in base ad un algoritmo di subentro (backoff).




MAC-PDU

t0 t0+T t0+2Tt0–T

MAC-PDU che vanno in collisione con la MAC-PDU grigia

Nessun arrivo = nessuna collisione



• Come appare dalla figura precedente, l’intervallo di vulnerabilità del protocollo ALOHA è uguale a 2T, e cioè a due volte il tempo di trasmissione T di una MAC-PDU, nell’ipotesi che questa sia di lunghezza costante.

• La portata media (rendimento di utilizzazione) può assumere un valore massimo che è uguale a circa 0,18.

• Come appare dalla figura precedente, l’intervallo di vulnerabilità del protocollo ALOHA è uguale a 2T, e cioè a due volte il tempo di trasmissione T di una MAC-PDU, nell’ipotesi che questa sia di lunghezza costante.

• La portata media (rendimento di utilizzazione) può assumere un valore massimo che è uguale a circa 0,18.


Protocollo ALOHA con IT (1/2)Protocollo ALOHA con IT (1/2)

• Il protocollo ALOHA con IT è usualmente chiamato “slotted ALOHA”;

• E’ come il protocollo ALOHA, ma con una sincronizzazione tra le stazioni: l’asse dei tempi è suddiviso in intervalli temporali (IT) di durata fissa, uguale al tempo di trasmissione T di una MAC-PDU.

• Il protocollo ALOHA con IT è usualmente chiamato “slotted ALOHA”;

• E’ come il protocollo ALOHA, ma con una sincronizzazione tra le stazioni: l’asse dei tempi è suddiviso in intervalli temporali (IT) di durata fissa, uguale al tempo di trasmissione T di una MAC-PDU.


Protocollo ALOHA con IT (2/2)Protocollo ALOHA con IT (2/2)

• Ogni stazione è vincolata ad iniziare l’emissione delle proprie PDU in corrispondenza dell’inizio di un IT;

• con questo accorgimento l’intervallo di vulnerabilità si dimezza: si riduce cioè alla durata T di un IT; conseguentemente la portata media assume un valore massimo che è uguale a circa 0,36, e cioè al doppio dell’analoga portata media massima del protocollo ALOHA.

• Ogni stazione è vincolata ad iniziare l’emissione delle proprie PDU in corrispondenza dell’inizio di un IT;

• con questo accorgimento l’intervallo di vulnerabilità si dimezza: si riduce cioè alla durata T di un IT; conseguentemente la portata media assume un valore massimo che è uguale a circa 0,36, e cioè al doppio dell’analoga portata media massima del protocollo ALOHA.


Prestazioni di ALOHA e slotted ALOHAPrestazioni di ALOHA e slotted ALOHA

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0 0.5 1 1.5 2 2.5 3 3.5 4

slotted ALOHA

ALOHA puro

Carico medio

Po

rtat

a m

edia


CSMA (Carrier Sense Multiple Access)(1/3)


• Adotta la regola: "Ascolta prima di parlare"• Procedura:

– una stazione che desidera emettere ascolta se il canale è occupato da una emissione precedente:

» se il canale è libero, la stazione emette;» se il canale è occupato, la stazione ritarda l’emissione

ad un istante successivo;– se la stazione emittente non riceve un riscontro

positivo dalla stazione ricevente, viene effettuata una riemissione con gli stessi accorgimenti descritti nella procedura del protocollo ALOHA.

• Adotta la regola: "Ascolta prima di parlare"• Procedura:

– una stazione che desidera emettere ascolta se il canale è occupato da una emissione precedente:

» se il canale è libero, la stazione emette;» se il canale è occupato, la stazione ritarda l’emissione

ad un istante successivo;– se la stazione emittente non riceve un riscontro

positivo dalla stazione ricevente, viene effettuata una riemissione con gli stessi accorgimenti descritti nella procedura del protocollo ALOHA.




• A causa dei ritardi di propagazione il protocollo CSMA è soggetto a collisioni.

• A causa dei ritardi di propagazione il protocollo CSMA è soggetto a collisioni.

1 2

2

1




• Per questo protocollo e per quelli della stessa famiglia l’intervallo di vulnerabilità è uguale a 2Δmax , e cioè al doppio del valore massimo del ritardo di propagazione tra due stazioni della rete.

• Infatti, nella condizione più sfavorevole, una stazione A che inizia ad emettere nell’istante t0 collide con una stazione B quando

– non ha sentito l’emissione della stazione B iniziata al tempo to - Δmax;

– non viene sentita dalla stazione B che inizia ad emettere al tempo to + Δmax.

• Per questo protocollo e per quelli della stessa famiglia l’intervallo di vulnerabilità è uguale a 2Δmax , e cioè al doppio del valore massimo del ritardo di propagazione tra due stazioni della rete.

• Infatti, nella condizione più sfavorevole, una stazione A che inizia ad emettere nell’istante t0 collide con una stazione B quando

– non ha sentito l’emissione della stazione B iniziata al tempo to - Δmax;

– non viene sentita dalla stazione B che inizia ad emettere al tempo to + Δmax.

to - Δmax to + Δmaxto


CSMA:procedure di persistenza (1/5)


• Il protocollo deve gestire due problemi connessi alla reiterazione dei tentativi di accesso

– in presenza di canale occupato;– a seguito di collisioni

• Nel caso di canale occupato, l'istante successivo di emissione è determinato in base ad una procedura di persistenza

» 1-persistente» 0-persistente» p-persistente

• Il protocollo deve gestire due problemi connessi alla reiterazione dei tentativi di accesso

– in presenza di canale occupato;– a seguito di collisioni

• Nel caso di canale occupato, l'istante successivo di emissione è determinato in base ad una procedura di persistenza

» 1-persistente» 0-persistente» p-persistente




1-persistente• la stazione aspetta che il canale torni libero, quindi

trasmette

1-persistente• la stazione aspetta che il canale torni libero, quindi

trasmette

Prova del canale(occupato)

Emissione




0-persistente:• la stazione aspetta che il canale torni libero e ritarda poi

l’emissione di un intervallo di tempo calcolato in base ad un algoritmo di subentro

0-persistente:• la stazione aspetta che il canale torni libero e ritarda poi

l’emissione di un intervallo di tempo calcolato in base ad un algoritmo di subentro


Ritardo di subentro

Emissione


Prova del canale(libero)

Ritardo di subentro




p-persistente:• la stazione attende che il canale torni libero, quindi

effettua l’emissione con probabilità p, altrimenti la trasmissione è ritardata di un intervallo di tempo calcolato in base ad un algoritmo di subentro

p-persistente:• la stazione attende che il canale torni libero, quindi

effettua l’emissione con probabilità p, altrimenti la trasmissione è ritardata di un intervallo di tempo calcolato in base ad un algoritmo di subentro

emissione posticipata(probabilità 1-p)

emissione (probabilità p)






• L'algoritmo di subentro serve a casualizzare l'accesso al canale.

• La procedura 1-persistente tende ad aumentare la portata media di rete, ma ad alto traffico aumenta le collisioni.

• La procedura 0-persistente riduce lo svantaggio delle collisioni ad alto traffico.

• La procedura p-persistente consente di regolare la probabilità p in base al traffico di rete.

• L'algoritmo di subentro serve a casualizzare l'accesso al canale.

• La procedura 1-persistente tende ad aumentare la portata media di rete, ma ad alto traffico aumenta le collisioni.

• La procedura 0-persistente riduce lo svantaggio delle collisioni ad alto traffico.

• La procedura p-persistente consente di regolare la probabilità p in base al traffico di rete.


CSMA con rivelazione di collisione (CSMA/CD) (1/2)


• Rispetto al protocollo CSMA, migliora le prestazioni riducendo la durata delle collisioni

• Adotta la regola: "Ascolta prima di parlare e mentre parli"

• Procedura (secondo lo standard IEEE 802.3):

– una stazione che ha ricevuto informazione dalla sorgente e che ha provveduto a strutturarla in una MAC-PDU, tenta di emetterla ascoltando il canale:

» se il canale è libero, la emette subito;

» se il canale è occupato, segue una delle proce-dure di persistenza;

• Rispetto al protocollo CSMA, migliora le prestazioni riducendo la durata delle collisioni

• Adotta la regola: "Ascolta prima di parlare e mentre parli"

• Procedura (secondo lo standard IEEE 802.3):

– una stazione che ha ricevuto informazione dalla sorgente e che ha provveduto a strutturarla in una MAC-PDU, tenta di emetterla ascoltando il canale:

» se il canale è libero, la emette subito;

» se il canale è occupato, segue una delle proce-dure di persistenza;




– se, durante l’emissione viene rivelata una collisione, la stazione interrompe l’emissione e emette un breve segnale di jamming con lo scopo segnalare l’evento alle altre stazioni (collision enforcement);

– completata l’emissione del segnale di jamming, la stazione attende per un tempo W di durata aleatoria e poi riprova ad emettere la MAC-PDU andata in collisione.

– se, durante l’emissione viene rivelata una collisione, la stazione interrompe l’emissione e emette un breve segnale di jamming con lo scopo segnalare l’evento alle altre stazioni (collision enforcement);

– completata l’emissione del segnale di jamming, la stazione attende per un tempo W di durata aleatoria e poi riprova ad emettere la MAC-PDU andata in collisione.


Algoritmo di Exponential Backoff (1/3)Algoritmo di Exponential Backoff (1/3)

• La durata di attesa per tentare una nuova emissione di una MAC-PDU andata in collisione è estratta dall’applicazione dell’algoritmo di Exponential Backoff:

– l’asse dei tempi è suddiviso in intervalli temporali (IT) di durata TIT uguale all’intervallo di vulnerabilità, e cioè a due volte il ritardo di propagazione massimo Δmax;

• La durata di attesa per tentare una nuova emissione di una MAC-PDU andata in collisione è estratta dall’applicazione dell’algoritmo di Exponential Backoff:

– l’asse dei tempi è suddiviso in intervalli temporali (IT) di durata TIT uguale all’intervallo di vulnerabilità, e cioè a due volte il ritardo di propagazione massimo Δmax;



– la durata di attesa W è un multiplo casuale di TIT,

W = K TIT

in cui l’ordine di molteplicità K è un intero estratto da una distribuzione uniforme su un intervallo 0 – R di larghezza (almeno inizialmente) crescente esponenzialmente con il numero di collisioni subite dalla MAC-PDU;

– la durata di attesa W è un multiplo casuale di TIT,

W = K TIT

in cui l’ordine di molteplicità K è un intero estratto da una distribuzione uniforme su un intervallo 0 – R di larghezza (almeno inizialmente) crescente esponenzialmente con il numero di collisioni subite dalla MAC-PDU;



– se i è il numero d’ordine di una collisione subita dalla MAC-PDU, l’intervallo R è così definito

dopo 16 collisioni si interrompono i tentativi di

emissione e si notifica il fallimento ai livelli superiori.

– se i è il numero d’ordine di una collisione subita dalla MAC-PDU, l’intervallo R è così definito

dopo 16 collisioni si interrompono i tentativi di

emissione e si notifica il fallimento ai livelli superiori.

2 1 1 10

1023 10 16

se;

se

i iR

i


Collisioni nel CSMA/CDCollisioni nel CSMA/CD

Δ : ritardo di propagazione tra le stazioni A e BT1: durata di rivelazione della collisione (pochi bit)T2: durata del segnale di jamming (32 bit)

A inizia l’emissione Fine dell’intervallo di collisione

B inizia l’emissione

T1 T2

t0A+ΔΔ Δ

t0A t0A+2 Δ +T1+T2


Lunghezza minima delle MAC-PDU nel CSMA/CD (1/3)


• Nel caso di stazioni A e B a distanza massima, il tempo totale necessario affinché, nel caso di collisione, la stazione A la riveli e interrompa la propria emissione è:

T = 2 Δmax + T1

• D’altra parte, la rivelazione della collisione avviene, da parte di A, per confronto tra quanto rilevabile in rete e quanto viene emesso.

• Nel caso di stazioni A e B a distanza massima, il tempo totale necessario affinché, nel caso di collisione, la stazione A la riveli e interrompa la propria emissione è:

T = 2 Δmax + T1

• D’altra parte, la rivelazione della collisione avviene, da parte di A, per confronto tra quanto rilevabile in rete e quanto viene emesso.




• Conseguentemente, una MAC-PDU deve avere una lunghezza F che soddisfa la seguente condizione

F (2 Δmax + T1)C 2 ΔmaxC,

ove C è la capacità trasmissiva del mezzo.

• Conseguentemente, una MAC-PDU deve avere una lunghezza F che soddisfa la seguente condizione

F (2 Δmax + T1)C 2 ΔmaxC,

ove C è la capacità trasmissiva del mezzo.




• Quindi, allo scopo di permettere la rivelazione delle collisioni da parte di tutte le stazioni, è necessaria una lunghezza minima Fmin per le MAC-PDU

Fmin 2 Δmax C .

• Quindi, allo scopo di permettere la rivelazione delle collisioni da parte di tutte le stazioni, è necessaria una lunghezza minima Fmin per le MAC-PDU

Fmin 2 Δmax C .




III.2.5: Accesso casuale in ambiente radio (Wireless)

III.2.5: Accesso casuale in ambiente radio (Wireless)


Distributed Coordination Function (DCF) (1/6)


• E’ un protocollo distribuito a contesa, basato sul CSMA/CA (Collision Avoidance).

• Non è prevista la rilevazione di collisione (CD), in quanto essa è di difficile realizzazione in una rete wireless.

• E’ un protocollo distribuito a contesa, basato sul CSMA/CA (Collision Avoidance).

• Non è prevista la rilevazione di collisione (CD), in quanto essa è di difficile realizzazione in una rete wireless.




• Ogni UI viene trasferita, in alternativa, con – lo scambio di due UI, una di dati e l’altra di riscontro

(ACK)– lo scambio di quattro UI, una prima RTS (Request To

Send), una seconda CTS (Clear To Send), una terza di dati e una quarta di riscontro (ACK).

• Le UI RTS e CTS possono o meno contenere una infor-mazione (NAV- Network Allocation Vector) circa la durata di impegno della rete ove l’accesso fosse consentito.

• Ogni UI viene trasferita, in alternativa, con – lo scambio di due UI, una di dati e l’altra di riscontro

(ACK)– lo scambio di quattro UI, una prima RTS (Request To

Send), una seconda CTS (Clear To Send), una terza di dati e una quarta di riscontro (ACK).

• Le UI RTS e CTS possono o meno contenere una infor-mazione (NAV- Network Allocation Vector) circa la durata di impegno della rete ove l’accesso fosse consentito.




• L’intervallo di tempo che intercorre tra due trame successive è chiamato “inter-frame space” (IFS).

• Una stazione determina che un canale è libero tramite l’uso della funzione “ascolto del canale” per l’IFS specificato.

• Sono definiti tre diversi IFS per fornire un numero corrispondente di priorità di accesso al mezzo:

– SIFS: Short IFS; precede una ACK, un RTS o un CTS o un MPDU contenente un frammento di MSDU, ad eccezione del primo.

– PIFS: PCF IFS; non è di interesse per questa trattazione.– DIFS: DCF IFS; è usato solo durante la DCF e precede le trame

MPDU contenenti dati.

• L’intervallo di tempo che intercorre tra due trame successive è chiamato “inter-frame space” (IFS).

• Una stazione determina che un canale è libero tramite l’uso della funzione “ascolto del canale” per l’IFS specificato.

• Sono definiti tre diversi IFS per fornire un numero corrispondente di priorità di accesso al mezzo:

– SIFS: Short IFS; precede una ACK, un RTS o un CTS o un MPDU contenente un frammento di MSDU, ad eccezione del primo.

– PIFS: PCF IFS; non è di interesse per questa trattazione.– DIFS: DCF IFS; è usato solo durante la DCF e precede le trame

MPDU contenenti dati.




• Una stazione con un pacchetto da emettere ascolta il canale tramite la funzione “Carrier-sense”;

– se lo trova libero, per un tempo uguale a un DIFS, emette;– se lo trova occupato, subito o durante il DIFS, attende che il

canale si liberi e che lo rimanga per un DIFS.• In questo secondo caso, trascorso l’intervallo DIFS di

canale libero, seleziona un intervallo di tempo avente durata casuale (intervallo di subentro o backoff) con il quale inizializza un contatore a ritroso.

• Una stazione con un pacchetto da emettere ascolta il canale tramite la funzione “Carrier-sense”;

– se lo trova libero, per un tempo uguale a un DIFS, emette;– se lo trova occupato, subito o durante il DIFS, attende che il

canale si liberi e che lo rimanga per un DIFS.• In questo secondo caso, trascorso l’intervallo DIFS di

canale libero, seleziona un intervallo di tempo avente durata casuale (intervallo di subentro o backoff) con il quale inizializza un contatore a ritroso.




• Questo contatore – è decrementato finchè il canale rimane libero– è congelato quando viene rilevata una emissione sul canale– è riattivato, a partire dal valore in cui si trovava nel momento in

cui è stato fermato, quando il canale viene di nuovo rilevato libero per più di un DIFS.

• La stazione emette quando il suo temporizzatore di subentro arriva a zero.

• Questo contatore – è decrementato finchè il canale rimane libero– è congelato quando viene rilevata una emissione sul canale– è riattivato, a partire dal valore in cui si trovava nel momento in

cui è stato fermato, quando il canale viene di nuovo rilevato libero per più di un DIFS.

• La stazione emette quando il suo temporizzatore di subentro arriva a zero.




Attendi IFS

Mezzo ancora

libero?

Emetti trama

Emetti trama

Attendi IFS

Mezzo ancora libero

Attendi a emettere trama

Mezzo libero?

Attendi termineemissione corrente

Subentro exp. con mezzo libero

NO

NO

NO

SI

SI

SI


Subentro esponenziale binarioSubentro esponenziale binario

• L'asse dei tempi è suddiviso in IT, di durata molto più breve di quella di una PDU (ad es., s per il DSSS).

• L’intervallo di subentro è una variabile aleatoria, multiplo intero di un IT, uniformemente distribuita tra 0 e un valore noto come Contention Window (CW).

• La dimensione della CW è posta ad un valore minimo (Cw

min) dopo ogni emissione andata a buon fine; viene

raddoppiata dopo ciascun tentativo fallito, fino a quando non si raggiunge un valore massimo (Cw

max).

• L'asse dei tempi è suddiviso in IT, di durata molto più breve di quella di una PDU (ad es., s per il DSSS).

• L’intervallo di subentro è una variabile aleatoria, multiplo intero di un IT, uniformemente distribuita tra 0 e un valore noto come Contention Window (CW).

• La dimensione della CW è posta ad un valore minimo (Cw

min) dopo ogni emissione andata a buon fine; viene

raddoppiata dopo ciascun tentativo fallito, fino a quando non si raggiunge un valore massimo (Cw

max).


Terminale nascostoTerminale nascosto


DCF: esempi (1/3)DCF: esempi (1/3)




III.2.6: Accesso controllatoIII.2.6: Accesso controllato


Protocolli MAC senza collisioniProtocolli MAC senza collisioni

• Sono basati sulla possibilità di prenotare e/o arbitrare l’accesso alla risorsa trasmissiva condivisa–polling– token passing–accodamento distribuito

• Permettono di offrire limiti garantiti per le prestazioni di portata e ritardo, anche con la definizione di classi di priorità, e garantiscono la stabilità del MAC

• Sono basati sulla possibilità di prenotare e/o arbitrare l’accesso alla risorsa trasmissiva condivisa–polling– token passing–accodamento distribuito

• Permettono di offrire limiti garantiti per le prestazioni di portata e ritardo, anche con la definizione di classi di priorità, e garantiscono la stabilità del MAC


Protocollo a token su anello (1/3)Protocollo a token su anello (1/3)

• È applicabile su una topologia logica ad anello. • L’accesso senza collisioni è ottenuto con il passaggio

di una trama apposita (token) da stazione a stazione e con la regola che può emettere solo la stazione che è in possesso del token.

• Le stazioni possono trovarsi nella modalità– ascolto (anello chiuso)– trasmissione (anello aperto)– bypass (stazione staccata e trasparente).

• È applicabile su una topologia logica ad anello. • L’accesso senza collisioni è ottenuto con il passaggio

di una trama apposita (token) da stazione a stazione e con la regola che può emettere solo la stazione che è in possesso del token.

• Le stazioni possono trovarsi nella modalità– ascolto (anello chiuso)– trasmissione (anello aperto)– bypass (stazione staccata e trasparente).



• Una stazione, che ha MAC-PDU (trame) da tras-mettere, attende il token, lo trattiene ed inizia ad emettere (passaggio dallo stato “ascolto” allo stato “trasmissione”).

• La rimozione delle MAC-PDU trasmesse sull’anello è a cura di chi le emette; completata la rimozione, si riemette un nuovo token.

• Una stazione, che ha MAC-PDU (trame) da tras-mettere, attende il token, lo trattiene ed inizia ad emettere (passaggio dallo stato “ascolto” allo stato “trasmissione”).

• La rimozione delle MAC-PDU trasmesse sull’anello è a cura di chi le emette; completata la rimozione, si riemette un nuovo token.



• Il protocollo a token su anello presenta una serie di problemi di gestione:

– inizializzazione dell’anello– mantenimento di un unico token (perdite,

duplicazioni)• Alcune funzioni gestionali sono tipiche di un anello

– rimozione delle trame “orfane” e corrotte– controllo del minimo ritardo di anello

• Queste funzioni sono assolte da una stazione che agisce da “monitor”; una qualsiasi stazione dell’anello può assumere questo ruolo, se occorre.

• Il protocollo a token su anello presenta una serie di problemi di gestione:

– inizializzazione dell’anello– mantenimento di un unico token (perdite,

duplicazioni)• Alcune funzioni gestionali sono tipiche di un anello

– rimozione delle trame “orfane” e corrotte– controllo del minimo ritardo di anello

• Queste funzioni sono assolte da una stazione che agisce da “monitor”; una qualsiasi stazione dell’anello può assumere questo ruolo, se occorre.

III.3 Controlli di errore e di flussoIII.3 Controlli di errore e di flusso



CONTENUTICONTENUTI

III.3.1 La funzione di controllo d’erroreIII.3.2 Codifica a rivelazione di erroreIII.3.3 Mezzi di recupero III.3.4 Numeri di sequenzaIII.3.5 Finestre scorrevoliIII.3.6 Azioni di recuperoIII.3.7 Procedure di recuperoIII.3.8 Analisi di una procedura ARQ III.3.9 La funzione di controllo di flussoIII.3.10 Funzioni dello strato di collegamentoIII.3.11 Esempio di protocollo di collegamento

III.3.1 La funzione di controllo d’erroreIII.3.2 Codifica a rivelazione di erroreIII.3.3 Mezzi di recupero III.3.4 Numeri di sequenzaIII.3.5 Finestre scorrevoliIII.3.6 Azioni di recuperoIII.3.7 Procedure di recuperoIII.3.8 Analisi di una procedura ARQ III.3.9 La funzione di controllo di flussoIII.3.10 Funzioni dello strato di collegamentoIII.3.11 Esempio di protocollo di collegamento


III.3 CONTROLLO DI ERRORE E DI FLUSSO


III.3.1: La funzione di controllo d’erroreIII.3.1: La funzione di controllo d’errore


Protezione dagli errori binariProtezione dagli errori binari

• Si distinguono–codici per la correzione degli errori (codici

Forward Error Correction, FEC)–codici per la rivelazione degli errori

• I primi permettono il recupero dell’informazione corrotta (entro i limiti operativi del codice)

• I secondi consentono, entro i limiti della prote-zione da loro effettuata di rivelare la presenza di uno o più errori.

• Si distinguono–codici per la correzione degli errori (codici

Forward Error Correction, FEC)–codici per la rivelazione degli errori

• I primi permettono il recupero dell’informazione corrotta (entro i limiti operativi del codice)

• I secondi consentono, entro i limiti della prote-zione da loro effettuata di rivelare la presenza di uno o più errori.


FEC (1/2)FEC (1/2)

• Date due stringhe binarie di ugual lunghezza, X e Y e posto W(A) = numero di bit 1 della stringa A, si definisce distanza di Hamming tra X e Y la quantità

HD(X,Y) = W(X xor Y).

• Un codice con parole di n bit può rappresentare simboli di m bit e la capacità di correzione è funzione della ridondanza r = n – m; il valore mi-nimo della HD tra tutte le coppie di parole di codice è la HD del codice.

• Date due stringhe binarie di ugual lunghezza, X e Y e posto W(A) = numero di bit 1 della stringa A, si definisce distanza di Hamming tra X e Y la quantità

HD(X,Y) = W(X xor Y).

• Un codice con parole di n bit può rappresentare simboli di m bit e la capacità di correzione è funzione della ridondanza r = n – m; il valore mi-nimo della HD tra tutte le coppie di parole di codice è la HD del codice.


FEC (2/2)FEC (2/2)

• Un codice con HD=2d+1 può correggere fino a d errori binari e può rivelarne fino a 2d .

• Un esempio di codice con n=10, m=2, r=8, d=2 è il seguente

0000000000 0000011111 1111100000 1111111111

• Un codice con HD=2d+1 può correggere fino a d errori binari e può rivelarne fino a 2d .

• Un esempio di codice con n=10, m=2, r=8, d=2 è il seguente

0000000000 0000011111 1111100000 1111111111


Il problema del controllo di errore (1/2)


• La funzione di controllo di errore include – la rivelazione degli errori; – lo scarto delle PDU rivelate errate.

a cui può o meno seguire il recupero di queste ultime;

• la funzione, in cui è svolto il controllo di errore, è attuata in uno o più strati ed è effettuata da entità di strato alla pari, una con ruolo emittente e l’altra con ruolo ricevente.

• La funzione di controllo di errore include – la rivelazione degli errori; – lo scarto delle PDU rivelate errate.

a cui può o meno seguire il recupero di queste ultime;

• la funzione, in cui è svolto il controllo di errore, è attuata in uno o più strati ed è effettuata da entità di strato alla pari, una con ruolo emittente e l’altra con ruolo ricevente.




• La funzione di controllo di errore agisce sulle PDU dello strato in cui è svolta tale funzione;

• se una PDU è rivelata errata, il relativo recupero avviene con regole che ne determinano la riemissione.

• La funzione di controllo di errore agisce sulle PDU dello strato in cui è svolta tale funzione;

• se una PDU è rivelata errata, il relativo recupero avviene con regole che ne determinano la riemissione.


Rivelazione di errore (1/4)Rivelazione di errore (1/4)

• Data una stringa di bit, che compone una PDU e che si desidera proteggere nei confronti di errori (stringa da proteggere), la rivelazione di questi errori in ricezione può essere effettuata, seppure senza certezza di successo, aggiungendo alla stringa uno o più bit (extra-bit), che sono il risultato di una codifica a rivelazione di errore;

• l’insieme della stringa da proteggere e dei relativi extra-bit costituisce una parola di codice.

• Data una stringa di bit, che compone una PDU e che si desidera proteggere nei confronti di errori (stringa da proteggere), la rivelazione di questi errori in ricezione può essere effettuata, seppure senza certezza di successo, aggiungendo alla stringa uno o più bit (extra-bit), che sono il risultato di una codifica a rivelazione di errore;

• l’insieme della stringa da proteggere e dei relativi extra-bit costituisce una parola di codice.



• Se

K è la lunghezza della stringa da proteggere;Z è la lunghezza della stringa di extra-bit, le parole di codice sono di lunghezza T uguale a

T = K + Z.

• Se

K è la lunghezza della stringa da proteggere;Z è la lunghezza della stringa di extra-bit, le parole di codice sono di lunghezza T uguale a

T = K + Z.



• Se una PDU è colpita da errore e se questi sono in configurazione tale da non essere rivelati, si verifica l’evento di “errori non rivelati”.

• Se una PDU è colpita da errore e se questi sono in configurazione tale da non essere rivelati, si verifica l’evento di “errori non rivelati”.



• I metodi di codifica per rivelare errori rientrano usualmente nella categoria dei codici con controllo di parità (parity check codes).

• A questa categoria appartengono i controlli– a parità singola;– a parità a blocchi;–a somma di controllo (checksum); – a ridondanza ciclica (CRC, Cyclic Redun-

dancy Check).

• I metodi di codifica per rivelare errori rientrano usualmente nella categoria dei codici con controllo di parità (parity check codes).

• A questa categoria appartengono i controlli– a parità singola;– a parità a blocchi;–a somma di controllo (checksum); – a ridondanza ciclica (CRC, Cyclic Redun-

dancy Check).




III.3.2: Codifica a rivelazione di erroreIII.3.2: Codifica a rivelazione di errore


Controllo a parità singola

Controllo a parità singola

• Si aggiunge un singolo bit (bit di parità) alla stringa da proteggere (ad es. ad un carattere);

• il bit di parità ha un valore “1” se il numero di “1” nella stringa è dispari; altrimenti è posto al valore “0”;

• operativamente, il bit di parità è la somma modulo 2 dei valori di cifra binaria contenuti nella stringa da proteggere.

• Si aggiunge un singolo bit (bit di parità) alla stringa da proteggere (ad es. ad un carattere);

• il bit di parità ha un valore “1” se il numero di “1” nella stringa è dispari; altrimenti è posto al valore “0”;

• operativamente, il bit di parità è la somma modulo 2 dei valori di cifra binaria contenuti nella stringa da proteggere.


Controllo a parità a blocchi (1/2)


• Si organizza la stringa da proteggere in una forma matriciale a due dimensioni e si applica il controllo di parità singola ad ogni riga e ad ogni colonna.

• Il controllo di parità relativo all’angolo destro in basso può essere visto come:–un controllo di parità su riga;–un controllo di parità su colonna;–un controllo di parità sull’intera stringa da

proteggere.

• Si organizza la stringa da proteggere in una forma matriciale a due dimensioni e si applica il controllo di parità singola ad ogni riga e ad ogni colonna.

• Il controllo di parità relativo all’angolo destro in basso può essere visto come:–un controllo di parità su riga;–un controllo di parità su colonna;–un controllo di parità sull’intera stringa da

proteggere.




Bit di parità per colonne

0 1 0 1 0 0 1 1

0 0 0 0 1 1 0 0

0 0 1 1 1 0 1 0

1 1 0 0 0 1 0 1

0 0 0 1 0 1 1 1

0 1 1 0 1 0 1 0

1 0 0 0 1 1 0 0

0 1 0 1 0 0 0 0

Bit di parità per colonne

0 1 0 1 0 0 1 10 1 0 0 1 0 0 0

0 0 1 1 1 0 1 0

1 1 0 0 0 1 0 10 1 0 1 0 0 1 1

0 1 1 0 1 0 1 0

1 0 0 0 1 1 0 0

0 1 0 1 0 0 0 0

Bit

di

par

ità

per

rig

he

Bit

di

par

ità

per

rig

he

blocco di caratteri originario e bit di

parità

blocco di caratteri originario e bit di

parità

errori non rivelatierrori non rivelati


Algoritmo “somma di controllo” (1/3)Algoritmo “somma di controllo” (1/3)

• L’idea su cui si basa l’algoritmo “a somma di con-trollo” è molto semplice:– in emissione si sommano tutte le parole che

compongono la stringa da emettere e si tra-smette il risultato di questa somma (checksum);

– in ricezione si effettua la stessa somma sui dati ricevuti e si confronta il risultato cone la “checksum” ricevuta.

• Se uno o più dei dati trasmessi, inclusa la checksum, è corrotto da errori, allora il risultato della somma in ricezione non corrisponde alla checksum ricevuta; il ricevitore ne deduce che si sono verificati errori.

• L’idea su cui si basa l’algoritmo “a somma di con-trollo” è molto semplice:– in emissione si sommano tutte le parole che

compongono la stringa da emettere e si tra-smette il risultato di questa somma (checksum);

– in ricezione si effettua la stessa somma sui dati ricevuti e si confronta il risultato cone la “checksum” ricevuta.

• Se uno o più dei dati trasmessi, inclusa la checksum, è corrotto da errori, allora il risultato della somma in ricezione non corrisponde alla checksum ricevuta; il ricevitore ne deduce che si sono verificati errori.



• Su questa idea si possono ipotizzare più varianti; la attuazione in Internet adotta una aritmetica in complemento a uno ed è la seguente:– in emissione

» si calcola la somma complemento a uno di tutte le parole di 16 bit che compongono la stringa da proteggere e che sono considerate una sequenza di interi;

» si effettua il complemento a uno di questa somma, la si assume come checksum e la si colloca nel campo omonimo della stringa.

• Su questa idea si possono ipotizzare più varianti; la attuazione in Internet adotta una aritmetica in complemento a uno ed è la seguente:– in emissione

» si calcola la somma complemento a uno di tutte le parole di 16 bit che compongono la stringa da proteggere e che sono considerate una sequenza di interi;

» si effettua il complemento a uno di questa somma, la si assume come checksum e la si colloca nel campo omonimo della stringa.



– in ricezione» si calcola la stessa somma sulla stringa ricevuta,

includendo in questa anche il contenuto del campo checksum.

• Se il risultato dell’operazione nel ricevitore è nullo, si assume che la stringa sia esente da errori; infatti

– in una somma effettuata con aritmetica complemento a uno occorre un riporto dei bit più significativi su quelli meno significativi;

– dato che il complemento a uno è un additivo inverso, l’aggiungere un valore al suo complemento fornisce un risultato uguale a zero

– in ricezione» si calcola la stessa somma sulla stringa ricevuta,

includendo in questa anche il contenuto del campo checksum.

• Se il risultato dell’operazione nel ricevitore è nullo, si assume che la stringa sia esente da errori; infatti

– in una somma effettuata con aritmetica complemento a uno occorre un riporto dei bit più significativi su quelli meno significativi;

– dato che il complemento a uno è un additivo inverso, l’aggiungere un valore al suo complemento fornisce un risultato uguale a zero


Codici CRC:i polinomi (1/4)


• Le singole cifre binarie di una stringa da proteggere sono trattate come coefficienti (di valore “0” o “1”) di un polinomio P(x).

• Le cifre binarie della stringa con lunghezza uguale a K sono quindi considerate come i coefficienti di un polinomio completo di grado K–1.

• In particolare, l’i-esimo bit della stringa è il coefficiente del termine xi–1 di P(x) .

• Le singole cifre binarie di una stringa da proteggere sono trattate come coefficienti (di valore “0” o “1”) di un polinomio P(x).

• Le cifre binarie della stringa con lunghezza uguale a K sono quindi considerate come i coefficienti di un polinomio completo di grado K–1.

• In particolare, l’i-esimo bit della stringa è il coefficiente del termine xi–1 di P(x) .




• Le entità emittente e ricevente utilizzano un polinomio comune G(x), detto polinomio generatore, che qualifica il codice a rivelazione di errore.

• Il polinomio G(x) gode di opportune proprietà nell’ambi-to della teoria dei campi algebrici:

– i coefficienti di G(x) sono binari, come quelli di P(x);– tra i coefficienti di G(x), quelli dei termini di grado

massimo e di grado nullo debbono entrambi essere uguali a 1.

• Supponiamo che questo polinomio sia di grado Z .

• Le entità emittente e ricevente utilizzano un polinomio comune G(x), detto polinomio generatore, che qualifica il codice a rivelazione di errore.

• Il polinomio G(x) gode di opportune proprietà nell’ambi-to della teoria dei campi algebrici:

– i coefficienti di G(x) sono binari, come quelli di P(x);– tra i coefficienti di G(x), quelli dei termini di grado

massimo e di grado nullo debbono entrambi essere uguali a 1.

• Supponiamo che questo polinomio sia di grado Z .




• La entità emittente utilizza G(x) come divisore del polinomio xZ P(x)

dove: Q(x) è il polinomio quoziente; R(x) è il polinomio resto.

• La entità emittente utilizza G(x) come divisore del polinomio xZ P(x)

dove: Q(x) è il polinomio quoziente; R(x) è il polinomio resto.

)x(G)x(R

)x(Q)x(G

)x(PxZ+=




• La divisione è l’ordinaria divisione di un polinomio per un altro; la particolarità risiede in:

– i coefficienti di dividendo e di divisore sono binari;

– l’aritmetica viene svolta modulo 2.

• La divisione è l’ordinaria divisione di un polinomio per un altro; la particolarità risiede in:

– i coefficienti di dividendo e di divisore sono binari;

– l’aritmetica viene svolta modulo 2.


Osservazione Osservazione

• Dato il grado del polinomio generatore, il grado del polinomio resto R(x) è al più uguale a Z -1;

• conseguentemente R(x) può essere sempre rappresentato con Z coefficienti (binari), ponen-do uguali a “0” i coefficienti dei termini mancan-ti.

• Dato il grado del polinomio generatore, il grado del polinomio resto R(x) è al più uguale a Z -1;

• conseguentemente R(x) può essere sempre rappresentato con Z coefficienti (binari), ponen-do uguali a “0” i coefficienti dei termini mancan-ti.


Codici CRC:l’emettitore (1/4)


• Ottenuto il resto R(x), l’entità emittente inse-risce i coefficienti di questo polinomio in un apposito campo della PDU (campo CRC), che deve quindi avere lunghezza Z .

• Ottenuto il resto R(x), l’entità emittente inse-risce i coefficienti di questo polinomio in un apposito campo della PDU (campo CRC), che deve quindi avere lunghezza Z .




• Nella PDU emessa trovano quindi posto le cifre binarie da proteggere (in numero uguale a K) e le cifre CRC (in numero uguale a Z): in totale

T = K + Z cifre binarie, che sono rappresentative di un polinomio T(x) di grado T – 1 = K + Z –1

T(x) = xZ P(x) + R(x)

e che costituiscono una parola di codice.

• Nella PDU emessa trovano quindi posto le cifre binarie da proteggere (in numero uguale a K) e le cifre CRC (in numero uguale a Z): in totale

T = K + Z cifre binarie, che sono rappresentative di un polinomio T(x) di grado T – 1 = K + Z –1

T(x) = xZ P(x) + R(x)

e che costituiscono una parola di codice.




• Tenendo conto che, per definizione,

xZ P(x) = Q(x)G(x) + R(x)

e poiché addizione e sottrazione modulo 2 si equivalgono, si ottiene

T(x) = Q(x)G(x) ;

cioè la stringa emessa, che è rappresentativa del polinomio T(x), è divisibile per il polinomio generatore G(x).

• Tenendo conto che, per definizione,

xZ P(x) = Q(x)G(x) + R(x)

e poiché addizione e sottrazione modulo 2 si equivalgono, si ottiene

T(x) = Q(x)G(x) ;

cioè la stringa emessa, che è rappresentativa del polinomio T(x), è divisibile per il polinomio generatore G(x).




• Si conclude che –tutte le parole di codice sono divisibili per il

polinomio generatore ;–tutti i polinomi divisibili per G(x) sono parole

di codice.

• Si conclude che –tutte le parole di codice sono divisibili per il

polinomio generatore ;–tutti i polinomi divisibili per G(x) sono parole

di codice.


Codici CRC:il ricevitore (1/5)


• La entità ricevente esegue, con il polinomio generatore, l’operazione di divisione effettuata in emissione;

• in questo caso opera però sul polinomio rappresentato dalle K + Z cifre binarie ricevute.

• La entità ricevente esegue, con il polinomio generatore, l’operazione di divisione effettuata in emissione;

• in questo caso opera però sul polinomio rappresentato dalle K + Z cifre binarie ricevute.




• Supponiamo che nel trasferimento si siano verificati errori, con una sequenza rappresentata dal polinomio E(x): ogni errore nella PDU corrisponde ad un coefficiente non nullo in E(x);

• allora le cifre binarie ricevute rappresentano il polinomio

T(x)+E(x) ,

ove l’addizione è svolta modulo 2.

• Supponiamo che nel trasferimento si siano verificati errori, con una sequenza rappresentata dal polinomio E(x): ogni errore nella PDU corrisponde ad un coefficiente non nullo in E(x);

• allora le cifre binarie ricevute rappresentano il polinomio

T(x)+E(x) ,

ove l’addizione è svolta modulo 2.




• Ogni bit “1” in E(x) corrisponde ad un bit che è stato invertito e quindi a un errore isolato;

• se ci sono n bit “1” in E(x), sono avvenuti n errori di un singolo bit;

• un singolo errore a raffica di lunghezza n è caratterizzato in E (x) da un “1” iniziale, una mescolanza di “0” e “1”, e un “1” finale per un complesso di n coefficienti binari

E (x) = xi (x n-1 + ….+1),

ove i determina quanto la raffica è lontana dall’estremità destra della PDU.

• Ogni bit “1” in E(x) corrisponde ad un bit che è stato invertito e quindi a un errore isolato;

• se ci sono n bit “1” in E(x), sono avvenuti n errori di un singolo bit;

• un singolo errore a raffica di lunghezza n è caratterizzato in E (x) da un “1” iniziale, una mescolanza di “0” e “1”, e un “1” finale per un complesso di n coefficienti binari

E (x) = xi (x n-1 + ….+1),

ove i determina quanto la raffica è lontana dall’estremità destra della PDU.




• Il ricevitore calcola il resto della divisione di T(x)+ E(x) per G(x); le modalità sono le stesse utilizzate nell’emettitore;

• poiché T(x) è divisibile per G(x), ne segue che

• Il ricevitore calcola il resto della divisione di T(x)+ E(x) per G(x); le modalità sono le stesse utilizzate nell’emettitore;

• poiché T(x) è divisibile per G(x), ne segue che

.)x(G)x(E

stoRe)x(G

)x(E)x(TstoRe




• Conseguentemente la regola applicata dal ricevitore è la seguente:–se il resto della divisione [T(x)+E(x)] / G(x) è

nullo, la PDU ricevuta è assunta “senza errori” ;

– in caso contrario, si sono verificati uno o più errori nel corso del trasferimento.

• Si nota che sono non rivelabili le configurazioni di errore per le quali il relativo polinomio E(x) contiene G(x) come fattore.

• Conseguentemente la regola applicata dal ricevitore è la seguente:–se il resto della divisione [T(x)+E(x)] / G(x) è

nullo, la PDU ricevuta è assunta “senza errori” ;

– in caso contrario, si sono verificati uno o più errori nel corso del trasferimento.

• Si nota che sono non rivelabili le configurazioni di errore per le quali il relativo polinomio E(x) contiene G(x) come fattore.


Codici CRC:protezione contro gli errori (1/2)


• Si può dimostrare che, adottando un opportuno polinomio generatore G(x), si possono sempre rivelare i seguenti eventi di errore:– errore su un singolo bit se in G(x) i termini xZ e

x0 hanno coefficienti non nulli;– errori su due bit se G(x) include un fattore con

almeno tre termini;– un qualsiasi numero dispari di errori se G(x)

include il fattore x + 1;– tutti gli errori a raffica di lunghezza Z .

• Si può dimostrare che, adottando un opportuno polinomio generatore G(x), si possono sempre rivelare i seguenti eventi di errore:– errore su un singolo bit se in G(x) i termini xZ e

x0 hanno coefficienti non nulli;– errori su due bit se G(x) include un fattore con

almeno tre termini;– un qualsiasi numero dispari di errori se G(x)

include il fattore x + 1;– tutti gli errori a raffica di lunghezza Z .




• Se la lunghezza della raffica è Z + 1 e se tutte le combinazioni della raffica sono considerate equiprobabili, la probabilità che l’errore a raffica non sia rivelato è uguale a 2 - (Z-1) .

• Infine, se la raffica singola ha lunghezza maggiore di Z+1 o se si verificassero varie raffiche più corte, nell’ipotesi di equiprobabilità delle configurazioni di errore, la probabilità di errore non rivelato è uguale a 2- Z .

• Se la lunghezza della raffica è Z + 1 e se tutte le combinazioni della raffica sono considerate equiprobabili, la probabilità che l’errore a raffica non sia rivelato è uguale a 2 - (Z-1) .

• Infine, se la raffica singola ha lunghezza maggiore di Z+1 o se si verificassero varie raffiche più corte, nell’ipotesi di equiprobabilità delle configurazioni di errore, la probabilità di errore non rivelato è uguale a 2- Z .


Codici CRC:polinomi generatori

Codici CRC:polinomi generatori

• Sono standard i seguenti polinomi generatori:

G(x)= x16 + x12 + x5 + 1

G(x)= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 +

+ x8 + x7 + x5 + x4 + x2 + x + 1

• Entrambi sono divisibili per x+1 e quindi danno luogo a codici CRC con le proprietà suddette.

• Sono standard i seguenti polinomi generatori:

G(x)= x16 + x12 + x5 + 1

G(x)= x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 +

+ x8 + x7 + x5 + x4 + x2 + x + 1

• Entrambi sono divisibili per x+1 e quindi danno luogo a codici CRC con le proprietà suddette.




III.3.3: Mezzi di recupero III.3.3: Mezzi di recupero


Procedure di recupero d’errore (1/3)


• Hanno lo scopo di assicurare che il flusso di PDU (in particolare di quelle contenenti dati di utente), trasferite tra le entità di strato preposte al controllo di errore, pervenga a destinazione–senza errori, almeno nei limiti consentiti dalla

capacità di protezione del codice utilizzato;–senza perdite, senza duplicazioni e senza

fuori-sequenza, almeno per ciò che riguarda la consegna delle relative SDU allo strato superiore.

• Hanno lo scopo di assicurare che il flusso di PDU (in particolare di quelle contenenti dati di utente), trasferite tra le entità di strato preposte al controllo di errore, pervenga a destinazione–senza errori, almeno nei limiti consentiti dalla

capacità di protezione del codice utilizzato;–senza perdite, senza duplicazioni e senza

fuori-sequenza, almeno per ciò che riguarda la consegna delle relative SDU allo strato superiore.




• Il ricevitore deve quindi essere in grado di – informare l’emettitore sui segmenti di

informazione risultanti persi o danneggiati;– coordinare la riemissione di questi segmenti

da parte dell’emettitore.• Le procedure di recupero sono usualmente

indicate con la sigla ARQ (Automatic Repeat reQuest) e sono basate sulla riemissione automatica dei dati, quando questi vengono rivelati errati.

• Il ricevitore deve quindi essere in grado di – informare l’emettitore sui segmenti di

informazione risultanti persi o danneggiati;– coordinare la riemissione di questi segmenti

da parte dell’emettitore.• Le procedure di recupero sono usualmente

indicate con la sigla ARQ (Automatic Repeat reQuest) e sono basate sulla riemissione automatica dei dati, quando questi vengono rivelati errati.




• Possibili procedure di recupero sono le seguenti:–ARQ a riscontro positivo con riemissione (Stop-

and-Wait);

–ARQ a finestra scorrevole con riemissione non selettiva (Go-back-N);

–ARQ a finestra scorrevole con riemissione selettiva (Selective Repeat),

e richiedono tutte un riscontro (acknowled-gement) del ricevitore per i dati trasferitigli dall’emettitore.

• Possibili procedure di recupero sono le seguenti:–ARQ a riscontro positivo con riemissione (Stop-

and-Wait);

–ARQ a finestra scorrevole con riemissione non selettiva (Go-back-N);

–ARQ a finestra scorrevole con riemissione selettiva (Selective Repeat),

e richiedono tutte un riscontro (acknowled-gement) del ricevitore per i dati trasferitigli dall’emettitore.


Mezzi di recupero (1/5)Mezzi di recupero (1/5)

• Nelle procedure di recupero si utilizzano, in alternativa o in unione, uno o più dei mezzi seguenti:

–riscontri positivi (ACK) o negativi (NAK);–temporizzatori (timer);–numeri di sequenza nelle PDU e relative

finestre scorrevoli.

• Nelle procedure di recupero si utilizzano, in alternativa o in unione, uno o più dei mezzi seguenti:

–riscontri positivi (ACK) o negativi (NAK);–temporizzatori (timer);–numeri di sequenza nelle PDU e relative

finestre scorrevoli.


Uso dei riscontri positivi e negativi

Uso dei riscontri positivi e negativi


PDU CPDU CACK

ACK

PDU APDU AACK

ACK

PDU BPDU BACK

ACK

PDU CPDU C (errata)

NAKNAK

Entità A Entità B



Uso dei temporizzatori: recupero di errore su una PDUUso dei temporizzatori: recupero di errore su una PDU

Inizio timer

Inizio timer

Fine timer

Timer scaduto

PDU APDU AACK

ACK

ACK

PDU B(riemessa)

PDU B

ACK

PDU B

Entità A Entità B


Uso dei temporizzatori: duplicazione di una PDU in seguito a perdita di un riscontroUso dei temporizzatori: duplicazione di una PDU in seguito a perdita di un riscontro


PDU APDU AACK

ACK

ACK

PDU B(riemessa) PDU B

(duplicata)

ACK

PDU BPDU BACK

Entità A Entità B

Inizio timer

Inizio timer

Fine timer

Timer scaduto



Uso dei temporizzatori e della numerazione delle PDU.Uso dei temporizzatori e della numerazione delle PDU.

PDU (1)PDU(1)

ACK (1)ACK (1)

ACK (2)

PDU(2)(riemessa) PDU(2)

(duplicata e scartata)

ACK (2)

PDU(2)PDU(2)ACK (2)

Entità A Entità B

Inizio timer

Inizio timer

Fine timer

Timer scaduto


Riscontri positivi (1/2)Riscontri positivi (1/2)

• I riscontri positivi – sono emessi da chi riceve per informare chi emette

sulla ricezione accettata di una o più PDU e sulla consegna delle relative SDU allo strato superiore;

– sono trasferibili, in alternativa o in unione, » con PDU apposite (PDU-ACK), contenenti solo

informazione di controllo, ma anch’esse protette con un CRC;

» con PDU contenenti dati di utente (PDU-dati) e trasferite nel verso contrario a quello dell’informazione da riscontrare: il riscontro è contenuto nell’intesta-zione della PDU come parte dell’informazione di con-trollo.

• I riscontri positivi – sono emessi da chi riceve per informare chi emette

sulla ricezione accettata di una o più PDU e sulla consegna delle relative SDU allo strato superiore;

– sono trasferibili, in alternativa o in unione, » con PDU apposite (PDU-ACK), contenenti solo

informazione di controllo, ma anch’esse protette con un CRC;

» con PDU contenenti dati di utente (PDU-dati) e trasferite nel verso contrario a quello dell’informazione da riscontrare: il riscontro è contenuto nell’intesta-zione della PDU come parte dell’informazione di con-trollo.


Riscontri positivi (2/2)Riscontri positivi (2/2)

• Questa seconda modalità di riscontro è nota come tecnica dell’addossamento” (piggy-backing) e consiste nell’inserire le informazioni di riscontro nelle PDU-dati che sono trasferite da chi ha ricevuto verso chi ha emesso.

• Questa seconda modalità di riscontro è nota come tecnica dell’addossamento” (piggy-backing) e consiste nell’inserire le informazioni di riscontro nelle PDU-dati che sono trasferite da chi ha ricevuto verso chi ha emesso.




III.3.4: Numeri di sequenzaIII.3.4: Numeri di sequenza


Numeri di sequenza (1/2)Numeri di sequenza (1/2)

• Ogni PDU-dati contiene due numeri di sequenza » il numero di sequenza in emissione NS, che è

il numero d’ordine sequenziale caratterizzante la PDU uscente dall’entità agente come emittente;

» il numero di sequenza in ricezione NR, che è l’ NS della PDU che l’entità agente come ricevente (e quindi come riscontrante) si aspetta di ricevere.

• Ogni PDU-dati contiene due numeri di sequenza » il numero di sequenza in emissione NS, che è

il numero d’ordine sequenziale caratterizzante la PDU uscente dall’entità agente come emittente;

» il numero di sequenza in ricezione NR, che è l’ NS della PDU che l’entità agente come ricevente (e quindi come riscontrante) si aspetta di ricevere.


Numeri di sequenza (2/2)Numeri di sequenza (2/2)

• Il numero NR è riscontro positivo implicito per la PDU con NS = NR − 1 (riscontro individuale) ovvero per tutte le PDU non ancora riscontrate e con NS minore o uguale a NR − 1 (riscontro cumulativo).

• Le PDU di riscontro (positivo o negativo) contengono il solo numero di sequenza in ricezione.

• Il numero NR è riscontro positivo implicito per la PDU con NS = NR − 1 (riscontro individuale) ovvero per tutte le PDU non ancora riscontrate e con NS minore o uguale a NR − 1 (riscontro cumulativo).

• Le PDU di riscontro (positivo o negativo) contengono il solo numero di sequenza in ricezione.


Definizione (1/2)Definizione (1/2)

• Per k intero e M intero positivo, k mod M (k modulo M)

e’ l’intero m non negativo e minore di M

0 m < Mtale che k - m è divisibile per M

k - m = j M

• Ad es. 15 mod 8 = 7, in quanto 7 < 8 e 15 - 7 = 8 è divisibile per 8.

• Per k intero e M intero positivo, k mod M (k modulo M)

e’ l’intero m non negativo e minore di M

0 m < Mtale che k - m è divisibile per M

k - m = j M

• Ad es. 15 mod 8 = 7, in quanto 7 < 8 e 15 - 7 = 8 è divisibile per 8.


Definizione (2/2)Definizione (2/2)

0 3 71 2 4 5 6 8- 3 -1-2- 4

1

2

3

k mod 4

k


Rappresentazione di NS e NR (1/2)


• Entrambi i numeri di sequenza sono rappresen-tabili con stringhe binarie di lunghezza limitata b (b = 1,2,…);

• ne deriva che per la loro rappresentazione occorre ricorrere a una numerazione modulo M (numerazione ciclica), con

M = 2b.

• Entrambi i numeri di sequenza sono rappresen-tabili con stringhe binarie di lunghezza limitata b (b = 1,2,…);

• ne deriva che per la loro rappresentazione occorre ricorrere a una numerazione modulo M (numerazione ciclica), con

M = 2b.




• Questa numerazione è quindi rappresentabile su una circonferenza, suddivisa in M segmenti di uguale lunghezza

• Questa numerazione è quindi rappresentabile su una circonferenza, suddivisa in M segmenti di uguale lunghezza

0

1

2

3

4

5

6

7Numerazione

modulo 8


III.3. CONTROLLO DI ERRORE E DI FLUSSO

III.3. CONTROLLO DI ERRORE E DI FLUSSO

III.3.5: Finestre scorrevoliIII.3.5: Finestre scorrevoli


Finestra scorrevole (1/3)Finestra scorrevole (1/3)

• In una numerazione modulo M, si chiama finestra (window) la sequenza di numeri consecutivi che sono compresi tra un limite inferiore Linf e un limite superiore Lsup, entrambi inclusi ;

• i numeri consecutivi compresi tra Linf e Lsup sono così “messi in finestra”;

• la cardinalità W di detta sequenza è chiamata larghezza della finestra

W= (Lsup - Linf +1) mod M e viene fissata a un valore costante nell’ambito di un protocollo di strato di collegamento.

• In una numerazione modulo M, si chiama finestra (window) la sequenza di numeri consecutivi che sono compresi tra un limite inferiore Linf e un limite superiore Lsup, entrambi inclusi ;

• i numeri consecutivi compresi tra Linf e Lsup sono così “messi in finestra”;

• la cardinalità W di detta sequenza è chiamata larghezza della finestra

W= (Lsup - Linf +1) mod M e viene fissata a un valore costante nell’ambito di un protocollo di strato di collegamento.



0

1

2

3

4

5

6

7

W= (Lsup- Linf + 1) mod M

Lsup= (Linf + W - 1) mod M

verso di scorrimento

W

Linf

L sup



• La finestra è scorrevole (sliding window) se si aggiorna aumentando Linf e mantenendo costan-te la sua larghezza W;

• ad ogni aumento di Linf la finestra scorre in senso orario e modifica corrispondentemente la sequenza di numeri “messi in finestra”.

• La finestra è scorrevole (sliding window) se si aggiorna aumentando Linf e mantenendo costan-te la sua larghezza W;

• ad ogni aumento di Linf la finestra scorre in senso orario e modifica corrispondentemente la sequenza di numeri “messi in finestra”.


Finestra in emissione (1/3)


• E’ il numero massimo di PDU che una entità emittente può emettere sequenzialmente senza ricevere riscontro per alcuna di esse;

• questo numero massimo è la larghezza WS della finestra in emissione;

• il limite inferiore Linf viene aggiornato dalla entità ricevente in relazione alla propria disponibilità ad ammettere nuove PDU;

• Linf viene quindi posto uguale all’ultimo numero di sequenza in ricezione NR emesso dall’entità ricevente, che è stato ricevuto dall’entità emittente.

• E’ il numero massimo di PDU che una entità emittente può emettere sequenzialmente senza ricevere riscontro per alcuna di esse;

• questo numero massimo è la larghezza WS della finestra in emissione;

• il limite inferiore Linf viene aggiornato dalla entità ricevente in relazione alla propria disponibilità ad ammettere nuove PDU;

• Linf viene quindi posto uguale all’ultimo numero di sequenza in ricezione NR emesso dall’entità ricevente, che è stato ricevuto dall’entità emittente.




• La finestra in emissione può essere collocata in una qualsiasi entità agente come emittente; quindi, con riferimento alla relazione tra le entità A e B, supponiamo che questa finestra sia collocata in A;

• allora i numeri di sequenza in emissione NSA che possono essere emessi da A sono quelli compresi nel seguente intervallo

ove NRB è l’ultimo numero di sequenza in ricezione emesso da B, che è stato ricevuto da A.

• La finestra in emissione può essere collocata in una qualsiasi entità agente come emittente; quindi, con riferimento alla relazione tra le entità A e B, supponiamo che questa finestra sia collocata in A;

• allora i numeri di sequenza in emissione NSA che possono essere emessi da A sono quelli compresi nel seguente intervallo

ove NRB è l’ultimo numero di sequenza in ricezione emesso da B, che è stato ricevuto da A.

,mod)1( MWNRNSNR SBAB




• Ad ogni variazione di NRB (aggiornamento dei riscontri positivi emessi da B) la finestra “scorre” consentendo l’uscita” (cioè l’emissione) di nuove PDU da A;

• l’entità B può quindi controllare l’emissione da parte di A agendo sui propri riscontri (ad es. rallentandone o accelerandone l’emissione).

• Ad ogni variazione di NRB (aggiornamento dei riscontri positivi emessi da B) la finestra “scorre” consentendo l’uscita” (cioè l’emissione) di nuove PDU da A;

• l’entità B può quindi controllare l’emissione da parte di A agendo sui propri riscontri (ad es. rallentandone o accelerandone l’emissione).


Finestra in ricezione (1/4)


• E’ il numero massimo di PDU che una entità ricevente può ammettere senza emettere riscontro per alcuna di esse;

• questo numero massimo è la larghezza WR della finestra in ricezione;

• il limite inferiore Linf viene aggiornato dalla entità ricevente al suo interno in relazione alla propria disponibilità ad ammettere nuove PDU;

• Linf viene quindi posto uguale all’ultimo numero di sequenza in ricezione NR emesso dalla stessa unità ricevente.

• E’ il numero massimo di PDU che una entità ricevente può ammettere senza emettere riscontro per alcuna di esse;

• questo numero massimo è la larghezza WR della finestra in ricezione;

• il limite inferiore Linf viene aggiornato dalla entità ricevente al suo interno in relazione alla propria disponibilità ad ammettere nuove PDU;

• Linf viene quindi posto uguale all’ultimo numero di sequenza in ricezione NR emesso dalla stessa unità ricevente.




• La finestra in ricezione può essere collocata in una qualsiasi entità agente come ricevente; quindi, con riferimento alla relazione tra le entità A e B, supponiamo che questa finestra sia collocata in B;

• allora i numeri di sequenza in emissione NSA che possono essere ammessi in B sono quelli compresi nel seguente intervallo

ove NRB è l’ultimo numero di sequenza in ricezione emesso da B stesso.

• La finestra in ricezione può essere collocata in una qualsiasi entità agente come ricevente; quindi, con riferimento alla relazione tra le entità A e B, supponiamo che questa finestra sia collocata in B;

• allora i numeri di sequenza in emissione NSA che possono essere ammessi in B sono quelli compresi nel seguente intervallo

ove NRB è l’ultimo numero di sequenza in ricezione emesso da B stesso.

1B A B RNR NS NR W M( )mod ,




• Ad ogni variazione di NRB (aggiornamento dei riscontri positivi emessi da B), la finestra “scorre” consentendo l’ammissione di nuove PDU in B;

• l’entità B può quindi controllare la propria ricettività agendo sui propri riscontri (ad es. rallentandone o accelerandone l’emissione).

• Ad ogni variazione di NRB (aggiornamento dei riscontri positivi emessi da B), la finestra “scorre” consentendo l’ammissione di nuove PDU in B;

• l’entità B può quindi controllare la propria ricettività agendo sui propri riscontri (ad es. rallentandone o accelerandone l’emissione).




• Le PDU che pervengono in B e che sono verificate senza errore sono ammesse da B solo se i loro NSA sono compresi entro la finestra di ricezione, anche se fuori sequenza.

• Invece le PDU che pervengono in B al di fuori della finestra di ricezione vengono scartate, anche se verificate senza errore.

• Le PDU che pervengono in B e che sono verificate senza errore sono ammesse da B solo se i loro NSA sono compresi entro la finestra di ricezione, anche se fuori sequenza.

• Invece le PDU che pervengono in B al di fuori della finestra di ricezione vengono scartate, anche se verificate senza errore.


Larghezze delle finestre (1/5)Larghezze delle finestre (1/5)

• Le larghezze WS e WR delle finestre in trasmissione e in ricezione sono limitate superiormente e congiuntamente dal modulo di numerazione M e dalla esigenza di evitare ambiguità nei riscontri.

• Le larghezze WS e WR delle finestre in trasmissione e in ricezione sono limitate superiormente e congiuntamente dal modulo di numerazione M e dalla esigenza di evitare ambiguità nei riscontri.



• Secondo tale esigenza– l’entità emittente deve avere la possibilità di

identificare senza ambiguità ogni PDU emessa e quindi di associarle in modo univoco in riscontro ricevuto;

– l’entità ricevente deve avere la possibilità di identificare senza ambiguità ogni PDU pervenutale e quindi di poterla riscontrare in modo univoco.

• Secondo tale esigenza– l’entità emittente deve avere la possibilità di

identificare senza ambiguità ogni PDU emessa e quindi di associarle in modo univoco in riscontro ricevuto;

– l’entità ricevente deve avere la possibilità di identificare senza ambiguità ogni PDU pervenutale e quindi di poterla riscontrare in modo univoco.



• Per questo scopo deve essere

WS + WR ≤ M (III.3.1)

• Con il rispetto di questo vincolo si riesce infatti ad evitare che, ad ogni scorrimento della finestra in ricezione, il nuovo insieme di numeri di sequenza ammessi (nuovi numeri ) si sovrapponga a quello valido prima dello scorrimento (vecchi numeri )

• Per questo scopo deve essere

WS + WR ≤ M (III.3.1)

• Con il rispetto di questo vincolo si riesce infatti ad evitare che, ad ogni scorrimento della finestra in ricezione, il nuovo insieme di numeri di sequenza ammessi (nuovi numeri ) si sovrapponga a quello valido prima dello scorrimento (vecchi numeri )



• Una eventuale sovrapposizione tra nuovi e vecchi numeri creerebbe nel ricevitore l’impossibilità di distinguere tra due casi che si possono presentare quando, dopo l’aggiornamento della finestra, perviene al ricevitore un gruppo di PDU;

• queste possono essere il risultato di:–riemissioni, se tutti i riscontri di PDU

precedentemente ricevute sono andati persi;–nuove emissioni, se tutti i riscontri sono stati

ricevuti.

• Una eventuale sovrapposizione tra nuovi e vecchi numeri creerebbe nel ricevitore l’impossibilità di distinguere tra due casi che si possono presentare quando, dopo l’aggiornamento della finestra, perviene al ricevitore un gruppo di PDU;

• queste possono essere il risultato di:–riemissioni, se tutti i riscontri di PDU

precedentemente ricevute sono andati persi;–nuove emissioni, se tutti i riscontri sono stati

ricevuti.



E’ interessante considerare le implicazioni della (III.3.1) nei due casi in cui•la larghezza WR è fissata di valore unitario;•le due largezze WR e WS sono scelte di valore uguale.

E’ interessante considerare le implicazioni della (III.3.1) nei due casi in cui•la larghezza WR è fissata di valore unitario;•le due largezze WR e WS sono scelte di valore uguale.


Larghezze delle finestre: Io caso (1/3)Larghezze delle finestre: Io caso (1/3)

• Se WR= 1, allora, in base alla (III.3.1), deve essere

WS ≤ M – 1 , (III.3.2)

cioè il numero massimo di PDU che si possono emettere senza avere un riscontro per alcuna di esse non può superare il valore di M diminuito di una unità

• Se WR= 1, allora, in base alla (III.3.1), deve essere

WS ≤ M – 1 , (III.3.2)

cioè il numero massimo di PDU che si possono emettere senza avere un riscontro per alcuna di esse non può superare il valore di M diminuito di una unità



• Per convincersene, consideriamo il caso M=8 e mostriamo che il numero di PDU emesse senza riscontro (e cioè la larghezza WS ) non può superare il valore 7 in quanto, se questo limite non fosse rispettato, si avrebbe ambiguità nei riscontri.

• Supponiamo (senza perdita di generalità) che la prima PDU non riscontrata abbia NS = 0;

• allora, chi emette sta ricevendo un riscontro NR= 0, cioè viene riscontrata positivamente la PDU con NS= 7.

• Per convincersene, consideriamo il caso M=8 e mostriamo che il numero di PDU emesse senza riscontro (e cioè la larghezza WS ) non può superare il valore 7 in quanto, se questo limite non fosse rispettato, si avrebbe ambiguità nei riscontri.

• Supponiamo (senza perdita di generalità) che la prima PDU non riscontrata abbia NS = 0;

• allora, chi emette sta ricevendo un riscontro NR= 0, cioè viene riscontrata positivamente la PDU con NS= 7.


• Se si emettessero 8 PDU (compresa quella con NS= 0) e cioè se la sequenza di emissione fosse composta da PDU con i seguenti NS

0 1 2 3 4 5 6 7 ,

il riscontro NR= 0, che per ipotesi continua ad essere ricevuto da chi emette, potrebbe essere interpretato come riscontro positivo per la nuova PDU con NS= 7 e non per quella di ugual NS appartenente al ciclo precedente.

• Se si emettessero 8 PDU (compresa quella con NS= 0) e cioè se la sequenza di emissione fosse composta da PDU con i seguenti NS

0 1 2 3 4 5 6 7 ,

il riscontro NR= 0, che per ipotesi continua ad essere ricevuto da chi emette, potrebbe essere interpretato come riscontro positivo per la nuova PDU con NS= 7 e non per quella di ugual NS appartenente al ciclo precedente.



Larghezze delle finestre: IIo caso (1/2)Larghezze delle finestre: IIo caso (1/2)

• Se WS = WR, allora, in accordo alla (III.3.1), la larghezza comune W deve rispettare il vincolo

W ≤ M / 2 , (III.3.3)

cioè deve essere non superiore alla metà del modulo di numerazione

• Se WS = WR, allora, in accordo alla (III.3.1), la larghezza comune W deve rispettare il vincolo

W ≤ M / 2 , (III.3.3)

cioè deve essere non superiore alla metà del modulo di numerazione


Larghezze delle finestre: IIo caso (2/2)Larghezze delle finestre: IIo caso (2/2)

• Per mostrare la necessità e la sufficienza della (III.3.3), consideriamo il caso M = 4.

• Mostriamo che può verificarsi ambiguità tra vecchi e nuovi numeri se si assumesse W = 3

e che tale ambiguità non si verifica se invece W = 2

• Per mostrare la necessità e la sufficienza della (III.3.3), consideriamo il caso M = 4.

• Mostriamo che può verificarsi ambiguità tra vecchi e nuovi numeri se si assumesse W = 3

e che tale ambiguità non si verifica se invece W = 2

0 1 2 3 0 1

Nuovi numeriVecchi numeri

0 1 2 3

Nuovi numeriVecchi numeri




III.3.6: Azioni di recuperoIII.3.6: Azioni di recupero


Azioni di recuperoAzioni di recupero

• Qualunque sia la procedura impiegata, è sempre richiesta la cooperazione dell’entità agente come ricevente (ricevitore) con quella agente come emittente (emettitore);

• si distinguono i compiti svolti –dall’entità emittente (azioni dell’emettitore);–dall’entità ricevente (azioni del ricevitore).

• Qualunque sia la procedura impiegata, è sempre richiesta la cooperazione dell’entità agente come ricevente (ricevitore) con quella agente come emittente (emettitore);

• si distinguono i compiti svolti –dall’entità emittente (azioni dell’emettitore);–dall’entità ricevente (azioni del ricevitore).


Azioni dell’emettitore (1/2)Azioni dell’emettitore (1/2)

• L’entità emittente, per ogni SDU proveniente dallo strato superiore,–accoglie questa SDU e contestualmente– inserisce la SDU nel campo-dati di una PDU; –codifica la stringa da proteggere nei confronti

degli errori; –attribuisce alla PDU un opportuno numero di

sequenza NS quando sia stato verificato che questo numero è all’interno della finestra in emissione.

• L’entità emittente, per ogni SDU proveniente dallo strato superiore,–accoglie questa SDU e contestualmente– inserisce la SDU nel campo-dati di una PDU; –codifica la stringa da proteggere nei confronti

degli errori; –attribuisce alla PDU un opportuno numero di

sequenza NS quando sia stato verificato che questo numero è all’interno della finestra in emissione.


Azioni dell’emettitore (2/2)Azioni dell’emettitore (2/2)

–Emette la PDU con il rispetto di due vincoli»viene rispettata, nell’ordine di emissione, la

sequenzialità delle SDU provenienti dallo strato superiore;

»viene attivato un temporizzatore, quando questo è presente;

–riemette la stessa PDU il numero di volte necessario a ottenere un riscontro positivo entro l’intervallo di tempo limite con cui è stato tarato il temporizzatore (quando questo è presente).

–Emette la PDU con il rispetto di due vincoli»viene rispettata, nell’ordine di emissione, la

sequenzialità delle SDU provenienti dallo strato superiore;

»viene attivato un temporizzatore, quando questo è presente;

–riemette la stessa PDU il numero di volte necessario a ottenere un riscontro positivo entro l’intervallo di tempo limite con cui è stato tarato il temporizzatore (quando questo è presente).


Azioni del ricevitore (1/5)Azioni del ricevitore (1/5)

• L’entità ricevente, per ogni PDU proveniente dall’entità emittente effettua in generale due tipi di controllo– controlla nella PDU la presenza o meno di

errori, utilizzando il metodo di rivelazione che è adottato nella procedura; si hanno due casi

(1) PDU verificata senza errori;(2) PDU verificata con errori.

• L’entità ricevente, per ogni PDU proveniente dall’entità emittente effettua in generale due tipi di controllo– controlla nella PDU la presenza o meno di

errori, utilizzando il metodo di rivelazione che è adottato nella procedura; si hanno due casi

(1) PDU verificata senza errori;(2) PDU verificata con errori.



• Limitatamente al caso (1), – controlla la PDU per rivelare la presenza o meno di

altre situazioni anomale (ad es. perdite, duplicazioni, ecc.); il controllo è effettuato accertando in primo luogo se il relativo NS è all’interno o all’esterno della finestra in ricezione; si hanno due casi:

(a) PDU controllata senza altre anomalie (all’interno della finestra);

(b) PDU controllata con altre anomalie, (all’esterno della finestra).

• Limitatamente al caso (1), – controlla la PDU per rivelare la presenza o meno di

altre situazioni anomale (ad es. perdite, duplicazioni, ecc.); il controllo è effettuato accertando in primo luogo se il relativo NS è all’interno o all’esterno della finestra in ricezione; si hanno due casi:

(a) PDU controllata senza altre anomalie (all’interno della finestra);

(b) PDU controllata con altre anomalie, (all’esterno della finestra).



• In relazione ai casi (1), (2), (a) e (b), –accetta la PDU ricevuta solo quando si

verifica l’unione dei due casi (1) e (a) e la PDU in questione è collocabile in un corretto ordine sequenziale;

–scarta la PDU ricevuta quando si presenta anche uno solo dei casi (2) o (b).

• In relazione ai casi (1), (2), (a) e (b), –accetta la PDU ricevuta solo quando si

verifica l’unione dei due casi (1) e (a) e la PDU in questione è collocabile in un corretto ordine sequenziale;

–scarta la PDU ricevuta quando si presenta anche uno solo dei casi (2) o (b).



• Limitatamente al caso di PDU accettata–trasferisce allo strato superiore la relativa

SDU o tutte le SDU in attesa;– invia all’entità emittente, con un possibile

ritardo, un riscontro positivo singolo o cumulativo.

• Limitatamente al caso di PDU accettata–trasferisce allo strato superiore la relativa

SDU o tutte le SDU in attesa;– invia all’entità emittente, con un possibile

ritardo, un riscontro positivo singolo o cumulativo.



• Limitatamente al caso (1) in unione con quello (b) (cioè per una PDU verificata senza errori e controllata con altre anomalie);

• ovvero nel caso in cui non sia possibile ricostruire la corretta sequenzialità delle SDU pervenute, – invia all’entità emittente un riscontro

negativo in cui viene richiesta una riemissione che dipende dalla procedura di recupero.

• Limitatamente al caso (1) in unione con quello (b) (cioè per una PDU verificata senza errori e controllata con altre anomalie);

• ovvero nel caso in cui non sia possibile ricostruire la corretta sequenzialità delle SDU pervenute, – invia all’entità emittente un riscontro

negativo in cui viene richiesta una riemissione che dipende dalla procedura di recupero.




III.3.7: Procedure di recuperoIII.3.7: Procedure di recupero


Stop and Wait ARQ :principi (1/2)


Il suo principio è il seguente: ogni entità • nel ruolo di emittente

– emette una sola PDU-dati alla volta;– prima di emettere la successiva, attende un riscontro

positivo;– se non riceve questo riscontro entro l’intervallo di tempo-

limite per cui è stato tarato il tmporizzatore, riemette la PDU e ripeterà questa operazione finché riceve un riscontro positivo;

• nel ruolo di ricevente – accetta una PDU-dati solo se verificata senza errori e con

numero di sequenza in emissione uguale a quello che si aspetta di ricevere.

Il suo principio è il seguente: ogni entità • nel ruolo di emittente

– emette una sola PDU-dati alla volta;– prima di emettere la successiva, attende un riscontro

positivo;– se non riceve questo riscontro entro l’intervallo di tempo-

limite per cui è stato tarato il tmporizzatore, riemette la PDU e ripeterà questa operazione finché riceve un riscontro positivo;

• nel ruolo di ricevente – accetta una PDU-dati solo se verificata senza errori e con

numero di sequenza in emissione uguale a quello che si aspetta di ricevere.


• Con riferimento al modello di recupero precedentemente introdotto, si sottolineano le seguenti particolarità

– il modulo di numerazione per NS e NR è uguale a 2;

– le finestre scorrevoli in emissione e in ricezione hanno entrambe larghezza unitaria (in accordo con la III.3.3).

• Con riferimento al modello di recupero precedentemente introdotto, si sottolineano le seguenti particolarità

– il modulo di numerazione per NS e NR è uguale a 2;

– le finestre scorrevoli in emissione e in ricezione hanno entrambe larghezza unitaria (in accordo con la III.3.3).




Inizio timer

Fine timer

PDU(0)PDU(0)ACK (1)

ACK (1)

PDU(1)(riemessa) PDU(1)

Entità A Entità B

Inizio timer

Fine timerInizio timer

Timer scaduto

PDU (1)

ACK (0)Inizio timer

Timer scaduto PDU(1) PDU(1)duplicata e scartata

ACK (0)ACK (0)

PDU(0) PDU(0)ACK (1)

ACK (1)

Stop and Wait ARQ :evoluzione

Stop and Wait ARQ :evoluzione


“Go back N” ARQ : principi (1/5)


• Il suo principio è il seguente: ogni entità quando agisce da emittente –emette al massimo WS PDU-dati consecutive

senza attendere il riscontro per alcuna di queste;

–prima di emettere un’altra PDU-dati, attende un riscontro positivo, che può essere individuale o cumulativo.

• N.B. La N del titolo del protocollo è la larghezza della finestra in emissione.

• Il suo principio è il seguente: ogni entità quando agisce da emittente –emette al massimo WS PDU-dati consecutive

senza attendere il riscontro per alcuna di queste;

–prima di emettere un’altra PDU-dati, attende un riscontro positivo, che può essere individuale o cumulativo.

• N.B. La N del titolo del protocollo è la larghezza della finestra in emissione.


–Se per alcuna delle PDU-dati emesse non riceve il riscontro positivo entro l’intervallo di tempo-limite per cui è stato tarato il temporizzatore, provvede a riemettere questa PDU e tutte le seguenti emesse e in attesa di riscontro;

–se, in alternativa, riceve dall’entità ricevente un riscontro negativo per una specifica PDU-dati, riemette questa PDU e tutte le seguenti già emesse e in attesa di riscontro.

–Se per alcuna delle PDU-dati emesse non riceve il riscontro positivo entro l’intervallo di tempo-limite per cui è stato tarato il temporizzatore, provvede a riemettere questa PDU e tutte le seguenti emesse e in attesa di riscontro;

–se, in alternativa, riceve dall’entità ricevente un riscontro negativo per una specifica PDU-dati, riemette questa PDU e tutte le seguenti già emesse e in attesa di riscontro.




• Ogni entità quando agisce da ricevente –opera nello stesso modo dell’entità ricevente

nel protocollo “Stop-and-Wait”, cioè accetta solo una PDU-dati che sia verificata senza errore e con numero di sequenza in emis-sione uguale a quello che si aspetta di ricevere.

• Ogni entità quando agisce da ricevente –opera nello stesso modo dell’entità ricevente

nel protocollo “Stop-and-Wait”, cioè accetta solo una PDU-dati che sia verificata senza errore e con numero di sequenza in emis-sione uguale a quello che si aspetta di ricevere.




• Con riferimento al modello per le procedure di recupero, si sottolineano le seguenti particolarità:– il modulo di numerazione per NS e NR ha un

valore M, che costituisce uno dei parametri del protocollo aventi incidenza importante sulle sue prestazioni.

• Con riferimento al modello per le procedure di recupero, si sottolineano le seguenti particolarità:– il modulo di numerazione per NS e NR ha un

valore M, che costituisce uno dei parametri del protocollo aventi incidenza importante sulle sue prestazioni.




– la finestra scorrevole in ricezione ha larghezza di valore unitario;

– la finestra scorrevole in emissione ha larghezza WS , il cui valore può essere fissato nella inizializzazione della procedura con l’unico vincolo che sia rispettata la (III.3.2), e cioè che sia

WS M - 1.

– la finestra scorrevole in ricezione ha larghezza di valore unitario;

– la finestra scorrevole in emissione ha larghezza WS , il cui valore può essere fissato nella inizializzazione della procedura con l’unico vincolo che sia rispettata la (III.3.2), e cioè che sia

WS M - 1.




“Go back N” ARQ : evoluzione

“Go back N” ARQ : evoluzione

ACK (3)ACK(3)

Entità A Entità B

REJ (3)

REJ (3)

PDU(0) PDU(0)PDU(1) PDU(1)PDU(2) PDU(2)

PDU(3)PDU(4) PDU(4) scartata

PDU(5) PDU(5) scartata

PDU(3) PDU(3)PDU(4) PDU(4)PDU(5) PDU(5)ACK(6)

ACK (6)


“Selective Repeat” ARQ:principi (1/3)


• Il suo principio è il seguente: ogni entità emittente si comporta come nel caso del protocollo “Go-back-N”, con la differenza che, nel caso di assenza di riscontro per una specifica PDU-dati entro l’intervallo di tempo-limite per cui è stato tarato il temporizzatore, provvede a riemettere solo questa PDU.

• Il suo principio è il seguente: ogni entità emittente si comporta come nel caso del protocollo “Go-back-N”, con la differenza che, nel caso di assenza di riscontro per una specifica PDU-dati entro l’intervallo di tempo-limite per cui è stato tarato il temporizzatore, provvede a riemettere solo questa PDU.




• Una entità ricevente, a differenza di quella con lo stesso ruolo nei protocolli “Stop-and-Wait” e “Go-back-N”,

–ammette una PDU-dati verificata senza errore e contenuta nella finestra in ricezione, anche se fuori-sequenza.

• Una entità ricevente, a differenza di quella con lo stesso ruolo nei protocolli “Stop-and-Wait” e “Go-back-N”,

–ammette una PDU-dati verificata senza errore e contenuta nella finestra in ricezione, anche se fuori-sequenza.




• Con riferimento al modello per le procedure di recupero, si hanno le seguenti particolarità:– le larghezze delle due finestre sono assunte

ugualiWS = WR = W > 1;

– il loro valore comune deve essere scelto in accordo con la (III.3.3), e cioè con il vincolo W M/2, in modo da assicurare che l’entità ricevente sia in grado di identificare senza ambiguità le PDU pervenutegli.

• Con riferimento al modello per le procedure di recupero, si hanno le seguenti particolarità:– le larghezze delle due finestre sono assunte

ugualiWS = WR = W > 1;

– il loro valore comune deve essere scelto in accordo con la (III.3.3), e cioè con il vincolo W M/2, in modo da assicurare che l’entità ricevente sia in grado di identificare senza ambiguità le PDU pervenutegli.


“Selective Repeat” ARQ:evoluzione

“Selective Repeat” ARQ:evoluzione

ACK (3)ACK (3)

Entità A Entità B

SEL REJ (3)

SEL REJ (3)

PDU (0)PDU(0)PDU(1)PDU(1)PDU(2)PDU(2)

PDU(3)PDU(4) PDU(4) ammessa

PDU(5)

PDU(5) ammessaPDU(3) PDU(3)

ACK (6)ACK (6) PDU(3), (4) e (5)

accettate




III.3.8: Analisi di una procedura ARQIII.3.8: Analisi di una procedura ARQ


Definizioni (1/4)Definizioni (1/4)

• Ci riferiamo a una procedura ARQ tra due nodi A e B. La Fig.III.2 mostra i ritardi connessi ai trasferimenti di una PDU-dati (cioè di una PDU contenente i dati di utente) da A a B e del relativo riscontro positivo PDU- ACK da B ad A, tenendo contodel tempo di trasmissione Tt della PDU-dati;del tempo di trasmissione Tr della relativa PDU-

ACK;dei ritardi di propagazione da A a B e da B ad A;dei ritardi di elaborazione Te della PDU-dati in B e

della PDU-ACK in A.

• Ci riferiamo a una procedura ARQ tra due nodi A e B. La Fig.III.2 mostra i ritardi connessi ai trasferimenti di una PDU-dati (cioè di una PDU contenente i dati di utente) da A a B e del relativo riscontro positivo PDU- ACK da B ad A, tenendo contodel tempo di trasmissione Tt della PDU-dati;del tempo di trasmissione Tr della relativa PDU-

ACK;dei ritardi di propagazione da A a B e da B ad A;dei ritardi di elaborazione Te della PDU-dati in B e

della PDU-ACK in A.



• Il tempo di ciclo TC della procedura è l’intervallo temporale di durata minima che intercorre, in assenza di errori, tra l’inizio della emissione di una PDU-dati da parte del nodo A e la fine dell’elaborazione della relativa PDU-ACK da parte dello stesso nodo;cioè

TC = Tt + 2Δ + 2Te + Tr .

• Il tempo di ciclo TC della procedura è l’intervallo temporale di durata minima che intercorre, in assenza di errori, tra l’inizio della emissione di una PDU-dati da parte del nodo A e la fine dell’elaborazione della relativa PDU-ACK da parte dello stesso nodo;cioè

TC = Tt + 2Δ + 2Te + Tr .



• Inoltre il tempo TO che intercorre tra la fine dell’emissione della PDU-dati da parte del nodo A e la ricezione (con elaborazione)del relativo riscontro PDU-ACK sempre da parte di A ha valore minimo dato da

min TO = 2Δ + 2Te + Tr ;

questo è anche il valore minimo dell’intervallo che deve trascorrere dopo la emissione della PDU-dati per ricevere il relativo riscontro in assenza di errori.

• Tale intervallo è quello minimo attribuibile al time-out Tout della procedura.

• Inoltre il tempo TO che intercorre tra la fine dell’emissione della PDU-dati da parte del nodo A e la ricezione (con elaborazione)del relativo riscontro PDU-ACK sempre da parte di A ha valore minimo dato da

min TO = 2Δ + 2Te + Tr ;

questo è anche il valore minimo dell’intervallo che deve trascorrere dopo la emissione della PDU-dati per ricevere il relativo riscontro in assenza di errori.

• Tale intervallo è quello minimo attribuibile al time-out Tout della procedura.



• .

• . PDU-dati

T

t

Δ Δ

TC

A

B

Tempo

Fig.III.2

Te

ACK

Te Tr


Modello della procedura: ipotesiModello della procedura: ipotesi

• Per un’analisi della procedura adottiamo un modello semplice per il quale

a) le PDU - dati hanno lunghezza costante;b) le PDU - ACK hanno lunghezza trascurabile rispetto alle PDU –

dati;c) le elaborazioni di una PDU – dati in ricezione e di una PDU –

ACK in emissione richiedono tempi trascurabili;d) la emissione delle PDU – ACK avviene senza ritardi;e) i riscontri sono solo individuali (sono esclusi cioè riscontri

cumulativi);f) il collegamento tra i nodi A e B opera in condizioni di pieno

carico (e cioè con una continua esigenza di trasferimento);g) le PDU-ACK non sono mai in errore (coerentemente con

l’ipotesi b).

• Per un’analisi della procedura adottiamo un modello semplice per il quale

a) le PDU - dati hanno lunghezza costante;b) le PDU - ACK hanno lunghezza trascurabile rispetto alle PDU –

dati;c) le elaborazioni di una PDU – dati in ricezione e di una PDU –

ACK in emissione richiedono tempi trascurabili;d) la emissione delle PDU – ACK avviene senza ritardi;e) i riscontri sono solo individuali (sono esclusi cioè riscontri

cumulativi);f) il collegamento tra i nodi A e B opera in condizioni di pieno

carico (e cioè con una continua esigenza di trasferimento);g) le PDU-ACK non sono mai in errore (coerentemente con

l’ipotesi b).


NotazioniNotazioni

• Denotiamo poi con L la lunghezza del testo in una PDU – dati; H la lunghezza dell’intestazione nella PDU – dati; la quota di extra-informazione (cioè il rapporto H/L); F la lunghezza complessiva di una PDU – dati

C il ritmo di trasferimento binario del collegamento; WS la larghezza della finestra in emissione.

• Denotiamo poi con L la lunghezza del testo in una PDU – dati; H la lunghezza dell’intestazione nella PDU – dati; la quota di extra-informazione (cioè il rapporto H/L); F la lunghezza complessiva di una PDU – dati

C il ritmo di trasferimento binario del collegamento; WS la larghezza della finestra in emissione.

1 1F L H L ; (III.3.4)


Tempo di ciclo di una procedura (1/2)Tempo di ciclo di una procedura (1/2)

• In base alle ipotesi b), c), d), e), che semplificano la Fig.III.2 nella

Fig.III.3, si può calcolare il tempo di ciclo TC della procedura. • In base alle ipotesi b), c), d), e), che semplificano la Fig.III.2 nella

Fig.III.3, si può calcolare il tempo di ciclo TC della procedura.

Tt Δ Δ

TC

A

B

Tempo

Fig.III.3


Tempo di ciclo di una procedura (2/2) Tempo di ciclo di una procedura (2/2)

• Tale tempo TC è dato da

ove– Tt = F/C è il tempo di trasmissione di una PDU-dati– α = Δ/Tt è un rapporto che può essere interpretato come il

numero di PDU che il mezzo impiegato nel collegamento può contenere.

• Il doppio 2 Δ/Tt = 2CΔ/F del parametro α è chiamato prodotto larghezza di banda – ritardo, normalizzato rispetto alla lunghezza F della PDU – dati, ed è come si vedrà, una misura dell’efficienza di una procedura ARQ.

• Tale tempo TC è dato da

ove– Tt = F/C è il tempo di trasmissione di una PDU-dati– α = Δ/Tt è un rapporto che può essere interpretato come il

numero di PDU che il mezzo impiegato nel collegamento può contenere.

• Il doppio 2 Δ/Tt = 2CΔ/F del parametro α è chiamato prodotto larghezza di banda – ritardo, normalizzato rispetto alla lunghezza F della PDU – dati, ed è come si vedrà, una misura dell’efficienza di una procedura ARQ.

22 1 1 2 2

F F CΔT Δ T α

C C F

C t , (III.3.5)


Utilizzazione del collegamento (1/2)Utilizzazione del collegamento (1/2)

• Indichiamo con T la durata di impegno dell’emettitore operante ad una estremità del collegamento, e cioè il tempo in cui l’unità emittente è impegnata per trasferire una PDU-dati.

• Con questa definizione, se E[T] è il valore atteso della durata T e se si tiene conto delle ipotesi a) e f), la portata media binaria lorda

Ls del collegamento è uguale F/ E[T].

• Indichiamo con T la durata di impegno dell’emettitore operante ad una estremità del collegamento, e cioè il tempo in cui l’unità emittente è impegnata per trasferire una PDU-dati.

• Con questa definizione, se E[T] è il valore atteso della durata T e se si tiene conto delle ipotesi a) e f), la portata media binaria lorda

Ls del collegamento è uguale F/ E[T].


Utilizzazione del collegamento (2/2)Utilizzazione del collegamento (2/2)

• Conseguentemente il rendimento di utilizzazione lorda UL del collegamento è dato da

mentre il rendimento netto UN è uguale a UL/(1+β), e cioè a

• Conseguentemente il rendimento di utilizzazione lorda UL del collegamento è dato da

mentre il rendimento netto UN è uguale a UL/(1+β), e cioè a

, 3Λ T

U = =C E T S t

L

41

TU

β T

t

N .E

(III.3.6)

(III.3.7)

LS


Impegno dell’emettitoreImpegno dell’emettitore

• La durata di impegno T, che per definizione è non inferiore al tempo di trasmissione Tt , è determinata daA. i parametri riguardanti le PDU-dati e il collegamento;B. i vincoli posti dalla operatività della finestra in emissione;C. gli eventi di errore che possono rendere necessaria, quando si

presentano, la riemissione di una PDU-dati quando su questa vengono rilevati errori.

• In base alle ipotesi di modello, la durata T in assenza di errori è una quantità deterministica; diventa invece una variabile aleatoria quando si tiene conto degli eventi di errore.

• La durata di impegno T, che per definizione è non inferiore al tempo di trasmissione Tt , è determinata daA. i parametri riguardanti le PDU-dati e il collegamento;B. i vincoli posti dalla operatività della finestra in emissione;C. gli eventi di errore che possono rendere necessaria, quando si

presentano, la riemissione di una PDU-dati quando su questa vengono rilevati errori.

• In base alle ipotesi di modello, la durata T in assenza di errori è una quantità deterministica; diventa invece una variabile aleatoria quando si tiene conto degli eventi di errore.


Condizione senza errori (1/6)Condizione senza errori (1/6)

• Nell’ipotesi che il trasferimento avvenga senza errori, valutiamo il valore che assume T per effetto dei parametri in A) e dei vincoli in B); indichiamo con T0 questa determinazione di T.

• Al variare di WS e per fissati valori di TC e di Tt, occorre distinguere due casi:

che mettono a confronto il tempo WSTt necessario per trasmettere WS PDU-dati consecutive con il tempo di ciclo TC e che sono esemplificati nelle Figg.III.4 e III.5.

• Nell’ipotesi che il trasferimento avvenga senza errori, valutiamo il valore che assume T per effetto dei parametri in A) e dei vincoli in B); indichiamo con T0 questa determinazione di T.

• Al variare di WS e per fissati valori di TC e di Tt, occorre distinguere due casi:

che mettono a confronto il tempo WSTt necessario per trasmettere WS PDU-dati consecutive con il tempo di ciclo TC e che sono esemplificati nelle Figg.III.4 e III.5.

S t C

S t C

W T < T

W T T ,


Condizione senza errori (2/6) Condizione senza errori (2/6)

1 2 WS

Tempo

WSTt

TC

caso WSTt < TC

A

B

Fig.III.4



1 2 i

Tempo

WSTt

TC

caso WSTt ≥ TC

A

B

WS

Fig.III.5



• Ne caso in cui il prodotto WSTt sia minore di TC (Fig.III.4), quando si è esaurita l’emissione delle WS PDU-dati senza che sia arrivato il riscontro per la prima di queste, l’emettitore passa in uno stato di inattività che cesserà solo quando perviene un riscontro e quindi quando si è concluso un tempo di ciclo.

• In queste condizioni, tenuto conto che in un intervallo temporale di durata TC vengono trasferite WS PDU-dati, la durata di impegno T0 necessaria per trasferire una singola PDU-dati è data da TC / WS;

• si ha quindi

• Ne caso in cui il prodotto WSTt sia minore di TC (Fig.III.4), quando si è esaurita l’emissione delle WS PDU-dati senza che sia arrivato il riscontro per la prima di queste, l’emettitore passa in uno stato di inattività che cesserà solo quando perviene un riscontro e quindi quando si è concluso un tempo di ciclo.

• In queste condizioni, tenuto conto che in un intervallo temporale di durata TC vengono trasferite WS PDU-dati, la durata di impegno T0 necessaria per trasferire una singola PDU-dati è data da TC / WS;

• si ha quindi

0 5T

T W T TW

CS t C

Sse . (III.3.8)



• Se invece il prodotto WSTt è non inferiore a TC (Fig.III.5), il riscontro per la prima PDU-dati emessa perviene all’emettitore prima che sia conclusa l’emissione delle WS PDU-dati.

• Conseguentemente l’emettitore può continuare la sua emissione senza soluzione di continuità e la durata di impegno T0 è uguale al tempo di trasmissione di una PDU-dati;

• pertanto

• Se invece il prodotto WSTt è non inferiore a TC (Fig.III.5), il riscontro per la prima PDU-dati emessa perviene all’emettitore prima che sia conclusa l’emissione delle WS PDU-dati.

• Conseguentemente l’emettitore può continuare la sua emissione senza soluzione di continuità e la durata di impegno T0 è uguale al tempo di trasmissione di una PDU-dati;

• pertanto

0 6T T W T T t S t Cse . (III.3.9)



• Le (III.3.8) e (III.3.9) possono essere così sintetizzate tenendo conto della (III.3.5)

• Le (III.3.8) e (III.3.9) possono essere così sintetizzate tenendo conto della (III.3.5)

0

1 21 2

7

1 2

T WWT

T W

t SS

t S

se

se .

(III.3.10)


Finestra critica (1/2)Finestra critica (1/2)

• I due casi considerati nelle (III.3.8) e (III.3.9) consentono di definire un valore di WS che, a parità di TC e Tt, costituisce separazione tra due intervalli della larghezza WS.

• Tale separazione è chiamata finestra critica e il suo valore WSc può essere ottenuto dal rispetto delle seguenti due disuguaglianze

che possono essere sintetizzate in

• I due casi considerati nelle (III.3.8) e (III.3.9) consentono di definire un valore di WS che, a parità di TC e Tt, costituisce separazione tra due intervalli della larghezza WS.

• Tale separazione è chiamata finestra critica e il suo valore WSc può essere ottenuto dal rispetto delle seguenti due disuguaglianze

che possono essere sintetizzate in

,1 CtSc

CtSc

TTW

TTW

.1t

CSc

t

C T

TW

T

T


Finestra critica (2/2)Finestra critica (2/2)

• Conseguentemente, la larghezza WSc della finestra critica è il più piccolo intero non inferiore al rapporto TC / Tt, ossia

in cui la seconda uguaglianza segue dalla (III.3.5).

• Conseguentemente, la larghezza WSc della finestra critica è il più piccolo intero non inferiore al rapporto TC / Tt, ossia

in cui la seconda uguaglianza segue dalla (III.3.5).

CSc

t

1 2 8T

W ,T

(III.3.11)


Utilizzazione senza errori Utilizzazione senza errori

• Dalle (III.3.10) e (III.3.6) può essere ottenuta l’espressione del rendimento di utilizzazione lorda di una qualunque procedura ARQ in assenza di errori.

• In tale espressione la larghezza Ws è un parametro che assume valore unitario nel caso di procedura “Stop & Wait” e valore maggiore dell’unità nelle procedure “Go-back- N” e “Selective-Repeat”.

• Dalle (III.3.10) e (III.3.6) può essere ottenuta l’espressione del rendimento di utilizzazione lorda di una qualunque procedura ARQ in assenza di errori.

• In tale espressione la larghezza Ws è un parametro che assume valore unitario nel caso di procedura “Stop & Wait” e valore maggiore dell’unità nelle procedure “Go-back- N” e “Selective-Repeat”.

9

W

UW W

.

S

L

S S

-1 1

2=-1

> 1 + 2 2

α

α α

≤

(III.3.12)


Condizione con errori (1/2)Condizione con errori (1/2)

• La (III.3.10) fornisce la durata di impegno per il trasferimento di una singola PDU-dati in assenza di errori; se si rimuove questa condizione e si tiene conto del numero Q di emissioni/ri-emissioni per ottenere il trasferimento di una PDU-dati senza errori, la durata T diventa una variabile aleatoria, per la quale può essere valutato il valore atteso E[T].

• Per definizione risulta T = Q T0, con T0 espresso dalla (III.3.10); pertanto il valore atteso di T è dato da

in cui E[Q] è il valore atteso della variabile aleatoria Q.

• La (III.3.10) fornisce la durata di impegno per il trasferimento di una singola PDU-dati in assenza di errori; se si rimuove questa condizione e si tiene conto del numero Q di emissioni/ri-emissioni per ottenere il trasferimento di una PDU-dati senza errori, la durata T diventa una variabile aleatoria, per la quale può essere valutato il valore atteso E[T].

• Per definizione risulta T = Q T0, con T0 espresso dalla (III.3.10); pertanto il valore atteso di T è dato da

in cui E[Q] è il valore atteso della variabile aleatoria Q.

0E T T E Q ,


Condizione con errori (2/2)Condizione con errori (2/2)

• In base alla (III.3.10), si conclude che il valore di E[T] normalizzato rispetto a Tt è espresso da

in cui E[Q] ha un valore dipendente dal tipo di procedura di recupero che si adotta.

• In base alla (III.3.10), si conclude che il valore di E[T] normalizzato rispetto a Tt è espresso da

in cui E[Q] ha un valore dipendente dal tipo di procedura di recupero che si adotta.

1 21 2

10

1 2

Q WTW

TQ W

SS

tS

E seE

E se ,

(III.3.13)


Trasferimenti con errori (1/3)Trasferimenti con errori (1/3)

• Indichiamo con p la probabilità di errore sul singolo bit delle PDU-dati;ε la probabilità di errore nel trasferimento di una PDU-dati.

• Nell’ipotesi che gli eventi di errore sul singolo bit siano mutuamente indipendenti, la probabilità ε riguarda l’evento in cui almeno un bit della PDU-dati viene ricevuto errato; si ha allora

in cui F è il numero di bit che compongono una PDU-dati.

• Indichiamo con p la probabilità di errore sul singolo bit delle PDU-dati;ε la probabilità di errore nel trasferimento di una PDU-dati.

• Nell’ipotesi che gli eventi di errore sul singolo bit siano mutuamente indipendenti, la probabilità ε riguarda l’evento in cui almeno un bit della PDU-dati viene ricevuto errato; si ha allora

in cui F è il numero di bit che compongono una PDU-dati.

1 1 11F

p , (III.3.14)



• Il pregio di questa relazione è la sua semplicità, che però ne costituisce anche il limite di impiego.

• In realtà, infatti, gli errori sul singolo bit sono altamente correlati: cioè se un bit è in errore, allora la probabilità che il bit seguente sia anch’esso in errore è molto più elevata di quella se il bit precedente non fosse in errore.

• Questa correlazione tra errori sui bit successivi fa sì che la (III.3.14) sia una sovrastima di ε per ogni fissato valore di p; quindi adottare la (III.3.14) equivale a una posizione conservativa.

• Il pregio di questa relazione è la sua semplicità, che però ne costituisce anche il limite di impiego.

• In realtà, infatti, gli errori sul singolo bit sono altamente correlati: cioè se un bit è in errore, allora la probabilità che il bit seguente sia anch’esso in errore è molto più elevata di quella se il bit precedente non fosse in errore.

• Questa correlazione tra errori sui bit successivi fa sì che la (III.3.14) sia una sovrastima di ε per ogni fissato valore di p; quindi adottare la (III.3.14) equivale a una posizione conservativa.



• Con la conoscenza della probabilità ε è possibile calcolare il valore atteso E[Q] per ciascuna delle procedure di recupero, che, per brevità, saranno qui indicate con

SW : procedura “Stop & Wait”;GBN : procedura “Go–back–N”;SR : procedura “Selective Repeat”.

• Con la conoscenza della probabilità ε è possibile calcolare il valore atteso E[Q] per ciascuna delle procedure di recupero, che, per brevità, saranno qui indicate con

SW : procedura “Stop & Wait”;GBN : procedura “Go–back–N”;SR : procedura “Selective Repeat”.


Procedure SW e SR (1/2)Procedure SW e SR (1/2)

• Nelle procedure SW e SR, si tiene conto che– per l’indipendenza dei tentativi di emissione, la probabilità di i

tentativi di emissione/ri-emissione è ugua-le al prodottodella probabilità εi – 1 di i – 1 tentativi senza successo,della probabilità 1 – ε di un i-esimo tentativo con suc-

cesso; cioè:

– per l’operatività delle procedure SW e SR, ogni tentativo di trasferimento comporta l’emissione di una sola PDU-dati;

– in base al modello introdotto precedentemente, le PDU-ACK non sono mai in errore.

• Nelle procedure SW e SR, si tiene conto che– per l’indipendenza dei tentativi di emissione, la probabilità di i

tentativi di emissione/ri-emissione è ugua-le al prodottodella probabilità εi – 1 di i – 1 tentativi senza successo,della probabilità 1 – ε di un i-esimo tentativo con suc-

cesso; cioè:

– per l’operatività delle procedure SW e SR, ogni tentativo di trasferimento comporta l’emissione di una sola PDU-dati;

– in base al modello introdotto precedentemente, le PDU-ACK non sono mai in errore.

;,...2,111 iiQ i


Procedure SW e SR (2/2)Procedure SW e SR (2/2)

• Conseguentemente

come si deduce osservando che» ε è un numero positivo minore di 1;

»

• Conseguentemente

come si deduce osservando che» ε è un numero positivo minore di 1;

»

i

Q iε εε

i-1

=1

1E = 1- = , 12

1-

.1

1

d

d

1 02

i1i

i i

i

(III.3.15)


Procedura GBN (1/5)Procedura GBN (1/5)

• Nella procedura GBN, se K ≤ WS è il numero di PDU-dati che, per l’operatività della

procedura, devono essere ri-emesse in occasione di ogni errore;

h(i) è il numero di PDU-dati emesse se la PDU originale deve essere emessa i volte,

risulta

come si ottiene notando che– nella prima emissione, si emette una sola PDU-dati;– nelle successive i – 1 emissioni, le PDU-dati emesse sono in

un numero totale che è uguale a (i – 1)K.

• Nella procedura GBN, se K ≤ WS è il numero di PDU-dati che, per l’operatività della

procedura, devono essere ri-emesse in occasione di ogni errore;

h(i) è il numero di PDU-dati emesse se la PDU originale deve essere emessa i volte,

risulta

come si ottiene notando che– nella prima emissione, si emette una sola PDU-dati;– nelle successive i – 1 emissioni, le PDU-dati emesse sono in

un numero totale che è uguale a (i – 1)K.

h i i K K iK i = 1 + -1 = 1- + = 1,2, ... , 13(III.3.16)



• Quindi, se si trascurano gli errori, oltre che nelle PDU-ACK, anche nelle PDU-dati ri-emesse dopo la PDU-dati inizialmente errata, si può scrivere

in cui si è tenuto conto della (III.3.16).

• Quindi, se si trascurano gli errori, oltre che nelle PDU-ACK, anche nelle PDU-dati ri-emesse dopo la PDU-dati inizialmente errata, si può scrivere

in cui si è tenuto conto della (III.3.16).

KQ h i ,

i

1i 1E 1 1411

(III.3.17)



• Nella (III.3.16) rimane da specificare il valore di K; osserviamo che– per WS < 1+2α, nelle condizioni di pieno carico (ipotizzate nel

modello di analisi), la finestra in emissione è pressochè sempre piena; si può quindi approssimare K con WS; cioè

• Nella (III.3.16) rimane da specificare il valore di K; osserviamo che– per WS < 1+2α, nelle condizioni di pieno carico (ipotizzate nel

modello di analisi), la finestra in emissione è pressochè sempre piena; si può quindi approssimare K con WS; cioè

1 2 15K W W S Sse . (III.3.18)



– per WS ≥ 1+2α , la finestra in emissione si riempie con un numero K ≤ WS di PDU-dati che deve soddisfare le seguenti due disuguaglianze

che si sintetizzano in

conseguentemente si può approssimare K con il valore 2(1+α); quindi

– per WS ≥ 1+2α , la finestra in emissione si riempie con un numero K ≤ WS di PDU-dati che deve soddisfare le seguenti due disuguaglianze

che si sintetizzano in

conseguentemente si può approssimare K con il valore 2(1+α); quindi

1

t C t

t C t ,

KT T T

K T T T

2 1 3 2K ;

2 1 1 2 16K W Sse . (III.3.19)



• In conclusione, per la procedura GBN, dalle (III.3.17), (III.3.18) e (III.3.19) si ottiene

• In conclusione, per la procedura GBN, dalle (III.3.17), (III.3.18) e (III.3.19) si ottiene

1 11 2

1 171 1 2

1 21

WW

Q

W

SS

S

seE

se .

(III.3.20)


Utilizzazione in SWUtilizzazione in SW

• In base alle (III.3.13) e (III.3.15), poiché nella procedura SW si ha WS = 1, risulta

• conseguentemente dalla (III.3.7) si ottiene il seguente rendimento di utilizzazione lorda del collegamento per la procedura SW

• In base alle (III.3.13) e (III.3.15), poiché nella procedura SW si ha WS = 1, risulta

• conseguentemente dalla (III.3.7) si ottiene il seguente rendimento di utilizzazione lorda del collegamento per la procedura SW

t

E 118

1

T;

T

L

119

1 2U .

(III.3.22)

(III.3.21)


Utilizzazione in GBNUtilizzazione in GBN

• Dalle (III.3.12) e (III.3.20) si ha

• conseguentemente il rendimento di utilizzazione lorda nella procedura GBN è dato da

• Dalle (III.3.12) e (III.3.20) si ha

• conseguentemente il rendimento di utilizzazione lorda nella procedura GBN è dato da

1 11 21 2

120

1 1 21 2

1

WW

T W

TW

SS

S

tS

seE

;

se

11 2

1 2 1 121

11 2

1 1 2

WW

WU

W

SS

SL

S

se

.

se

(III.3.23)

(III.3.24)


Utilizzazione in SRUtilizzazione in SR

• Dalle (III.3.12) e (III.3.15) si ricava

• ne segue che il rendimento di utilizzazione lorda per la procedura SR è dato da

• Dalle (III.3.12) e (III.3.15) si ricava

• ne segue che il rendimento di utilizzazione lorda per la procedura SR è dato da

1 2 11 2

122

11 2

1

WT W

TW

SS

tS

seE

;

se

1 1 2231 2

1 1 2

WW

UW

SS

L

S

se.

se

(III.3.25)

(III.3.26)


Commenti conclusivi (1/7)Commenti conclusivi (1/7)

• Confrontiamo i rendimenti lordi UL delle tre procedure al crescere del parametro α e a parità del ritmo di errore sulla PDU-dati; scrivendo i campi di variazione di α in ordine crescente, dalle (III.3.22), (III.3.24) e (III.3.26) si ottiene

• Confrontiamo i rendimenti lordi UL delle tre procedure al crescere del parametro α e a parità del ritmo di errore sulla PDU-dati; scrivendo i campi di variazione di α in ordine crescente, dalle (III.3.22), (III.3.24) e (III.3.26) si ottiene



124

1 2U

L per SW ;

11 2

1 1 225

11 2

1 2 1 1

W

UW

WW

S

LS

SS

/

per GBN ;

/

1 1 226

1 1 21 2

WU W

W

S

L SS

/per SR .

/

(III.3.28)

(III.3.29)

(III.3.27)



• Nella figura III.6 è mostrato l’andamento del rendimento UL per le tre procedure e in funzione di α . Si è assunto ε = 10-3 e, nel caso delle procedure GBR ed SN, si sono considerati due casi: uno con finestra di larghezza WS = 7 e l’altro con WS = 127.

• Nella figura III.6 è mostrato l’andamento del rendimento UL per le tre procedure e in funzione di α . Si è assunto ε = 10-3 e, nel caso delle procedure GBR ed SN, si sono considerati due casi: uno con finestra di larghezza WS = 7 e l’altro con WS = 127.



UL

α

SWGBN/SR

WS=7

SR, WS=127

GBN, WS=127

ε = 10-3

Fig.III.6



• La (III.3.27) mostra che, nella procedura SW, UL decresce mo-notonamente al crescere di α secondo il fattore 1/(1+2α).

• Invece per le procedure GBN e SR, come appare dalle (III.3.28) e (III.3.29), occorre distinguere due regioni di variazione di α, definite a parità della larghezza WS della finestra in emissione:

– se 0 < α ≤ (WS – 1)/2, la procedura SR presenta un rendimento lordo che è indipendente da α; invece, nel caso della procedura GBN, UL decresce al crescere di α con un fattore di riduzione che è uguale a 1/[1+ε(1+2α)]; la diminuzione massima può essere di valore contenuto, ad esempio inferiore a circa l’1% se il prodotto (WS – 1)ε è minore di 0,01, ma può essere anche di valore sensibile, ad esempio superiore al 30% se detto prodotto è maggiore di circa 0.40;

• La (III.3.27) mostra che, nella procedura SW, UL decresce mo-notonamente al crescere di α secondo il fattore 1/(1+2α).

• Invece per le procedure GBN e SR, come appare dalle (III.3.28) e (III.3.29), occorre distinguere due regioni di variazione di α, definite a parità della larghezza WS della finestra in emissione:

– se 0 < α ≤ (WS – 1)/2, la procedura SR presenta un rendimento lordo che è indipendente da α; invece, nel caso della procedura GBN, UL decresce al crescere di α con un fattore di riduzione che è uguale a 1/[1+ε(1+2α)]; la diminuzione massima può essere di valore contenuto, ad esempio inferiore a circa l’1% se il prodotto (WS – 1)ε è minore di 0,01, ma può essere anche di valore sensibile, ad esempio superiore al 30% se detto prodotto è maggiore di circa 0.40;



– se invece α > (WS – 1)/2, entrambe le procedure GBN e SR hanno un rendimento lordo che, al crescere di α, decresce con legge monotona secondo un fattore di riduzione uguale a WS /(1+2α) rispetto al valore assunto per α = (WS – 1)/2.

• Esaminando ancora le (III.3.27), (III.3.28) e (III.3.29), si vede inoltre, come era naturale attendersi, che il rendimento lordo è limitato dal ritmo di errore ε; quindi, a parità di tutti gli altri parametri, WS e α, l’unica via per migliorare l’efficienza di una procedura di recupero risiede in una diminuzione del ritmo d’errore.

– se invece α > (WS – 1)/2, entrambe le procedure GBN e SR hanno un rendimento lordo che, al crescere di α, decresce con legge monotona secondo un fattore di riduzione uguale a WS /(1+2α) rispetto al valore assunto per α = (WS – 1)/2.

• Esaminando ancora le (III.3.27), (III.3.28) e (III.3.29), si vede inoltre, come era naturale attendersi, che il rendimento lordo è limitato dal ritmo di errore ε; quindi, a parità di tutti gli altri parametri, WS e α, l’unica via per migliorare l’efficienza di una procedura di recupero risiede in una diminuzione del ritmo d’errore.



• Se si confrontano le tre procedure a parità di ε, si deduce che– la procedura più efficiente è la SR;– la procedura GBN è meno efficiente della SR per il fattore di

riduzione 1/[1+ε(1+2α)];– nel caso della procedura SW il fattore di riduzione rispetto alla

SR è 1/(1+2α) e quindi decisamente maggiore di quello della GBN a parità di α.

• Come appare dalle (III.3.22), (III.3.24) e (III.3.26), il rendimento di utilizzazione netta UN = UL /(1+ β) delle tre procedure è limitato, in egual misura, dalla quota β di extra-informazione; tuttavia per PDU-dati sufficientemente lunghe (ad es. per L > 1000 byte e H < 100 byte), la quota β può essere assunta minore di 0,1; il fattore di riduzione 1/(1+ β) ha allora valori maggiori di 0,91.

• Se si confrontano le tre procedure a parità di ε, si deduce che– la procedura più efficiente è la SR;– la procedura GBN è meno efficiente della SR per il fattore di

riduzione 1/[1+ε(1+2α)];– nel caso della procedura SW il fattore di riduzione rispetto alla

SR è 1/(1+2α) e quindi decisamente maggiore di quello della GBN a parità di α.

• Come appare dalle (III.3.22), (III.3.24) e (III.3.26), il rendimento di utilizzazione netta UN = UL /(1+ β) delle tre procedure è limitato, in egual misura, dalla quota β di extra-informazione; tuttavia per PDU-dati sufficientemente lunghe (ad es. per L > 1000 byte e H < 100 byte), la quota β può essere assunta minore di 0,1; il fattore di riduzione 1/(1+ β) ha allora valori maggiori di 0,91.




III.3.9: La funzione di controllo di flussoIII.3.9: La funzione di controllo di flusso


Procedure di controllo di flusso (1/2)Procedure di controllo di flusso (1/2)

• Hanno lo scopo di restringere il volume di informazione che l’emettitore può inoltrare verso il ricevitore prima di ricevere un riscontro per tale informazione.

• Ogni ricevitore presenta infatti– una limitata velocità con la quale può elaborare

le informazioni entranti;– una limitata capacità di memoria nella quale

immagazzinare tali informazioni.

• Hanno lo scopo di restringere il volume di informazione che l’emettitore può inoltrare verso il ricevitore prima di ricevere un riscontro per tale informazione.

• Ogni ricevitore presenta infatti– una limitata velocità con la quale può elaborare

le informazioni entranti;– una limitata capacità di memoria nella quale

immagazzinare tali informazioni.


Procedure di controllo di flusso (2/2)Procedure di controllo di flusso (2/2)

• Il ricevitore deve quindi essere in grado di informare l’emettitore prima che questi limiti siano raggiunti e di richiedere che l’emettitore riduca la sua portata (invii cioè un minore volume di informazione nell’unità di tempo) o la arresti temporaneamente.

• Le procedure di controllo di flusso nello strato di collegamento utilizzano procedure analoghe a quelle di recupero d’errore per l’interazione tra emettitore e ricevitore.

• Il ricevitore deve quindi essere in grado di informare l’emettitore prima che questi limiti siano raggiunti e di richiedere che l’emettitore riduca la sua portata (invii cioè un minore volume di informazione nell’unità di tempo) o la arresti temporaneamente.

• Le procedure di controllo di flusso nello strato di collegamento utilizzano procedure analoghe a quelle di recupero d’errore per l’interazione tra emettitore e ricevitore.


Controllo di flusso (1/3)


• Nel caso in cui il ritmo di arrivo delle PDU sia superiore alla capacità di elaborazione della entità ricevente, ha il compito di assicurare che non si verifi-chino perdite di informazione a causa della saturazione delle sue risorse di memorizzazione.

• Nel caso in cui il ritmo di arrivo delle PDU sia superiore alla capacità di elaborazione della entità ricevente, ha il compito di assicurare che non si verifi-chino perdite di informazione a causa della saturazione delle sue risorse di memorizzazione.




• Viene effettuato attraverso il rilascio, a cura della parte ricevente e nei confronti di quella emittente, di opportune autorizzazioni relative al numero massimo di PDU che possono essere emesse e/o ammesse.

• Ciò consente di ridurre o di eliminare gli effetti delle singole cause di congestione all’atto in cui si presentano condizioni di carico elevato in certe parti della rete.

• Viene effettuato attraverso il rilascio, a cura della parte ricevente e nei confronti di quella emittente, di opportune autorizzazioni relative al numero massimo di PDU che possono essere emesse e/o ammesse.

• Ciò consente di ridurre o di eliminare gli effetti delle singole cause di congestione all’atto in cui si presentano condizioni di carico elevato in certe parti della rete.




• Sono possibili vari schemi di controllo di flusso.

• La maggior parte di questi utilizza le regole protocollari che sono definite per consentire il recupero di condizioni di trasferimento anomale.

• Sono possibili vari schemi di controllo di flusso.

• La maggior parte di questi utilizza le regole protocollari che sono definite per consentire il recupero di condizioni di trasferimento anomale.


Controllo di flusso a finestra (1/2)


• Con il meccanismo delle finestre, la disponibilità al trasferimento dall’entità A a quella B viene aggiornata esclusivamente da B (cioè da chi agisce come ricevente);

• ciò avviene agendo direttamente sulla finestra in ricezione (se presente) e inviando ad A opportune informazioni per il controllo della finestra in emissione (se presente).

• Con il meccanismo delle finestre, la disponibilità al trasferimento dall’entità A a quella B viene aggiornata esclusivamente da B (cioè da chi agisce come ricevente);

• ciò avviene agendo direttamente sulla finestra in ricezione (se presente) e inviando ad A opportune informazioni per il controllo della finestra in emissione (se presente).




• Il meccanismo a finestra è un tipico esempio di controllo del traffico di tipo reattivo (meccanismo a retro-pressione) che può essere utilizzato come controllo di flusso.

• Il meccanismo a finestra è un tipico esempio di controllo del traffico di tipo reattivo (meccanismo a retro-pressione) che può essere utilizzato come controllo di flusso.




III.3.10: Funzioni dello strato di collegamentoIII.3.10: Funzioni dello strato di collegamento


Protocolli di strato di collegamentoProtocolli di strato di collegamento

• Le funzioni elementari di un protocollo di strato di collegamento sono:– la delimitazione delle PDU (trame)– l’indirizzamento delle trame– la rivelazione degli errori trasmissivi– il recupero, quando richiesto, del corretto

trasferimento delle trame in caso di errori– il controllo di flusso– la gestione (instaurazione, abbattimento e re-

inizializzazione) della connessione di strato di collegamento

• Le funzioni elementari di un protocollo di strato di collegamento sono:– la delimitazione delle PDU (trame)– l’indirizzamento delle trame– la rivelazione degli errori trasmissivi– il recupero, quando richiesto, del corretto

trasferimento delle trame in caso di errori– il controllo di flusso– la gestione (instaurazione, abbattimento e re-

inizializzazione) della connessione di strato di collegamento


Delimitazione delle trame (1/3)Delimitazione delle trame (1/3)

• Un possibile campo di delimitazione (Flag) è 01111110.• Per evitare che una sequenza di dati nel corpo della

trama coincida con un Flag, rendendo così impossibile la delimitazione della trama, si opera con la tecnica del “bit stuffing” in emissione e del “bit destuffing” in ricezione

• Un possibile campo di delimitazione (Flag) è 01111110.• Per evitare che una sequenza di dati nel corpo della

trama coincida con un Flag, rendendo così impossibile la delimitazione della trama, si opera con la tecnica del “bit stuffing” in emissione e del “bit destuffing” in ricezione



– In emissione, si aggiunge uno 0 dopo ogni sequenza di cinque 1 consecutivi entro il corpo della trama (bit stuffing) indipendentemente da quale sia la cifra seguente

– In ricezione si contano le cifre 1 consecutive: se se ne incontrano cinque, si esamina la cifra successiva; se questa è un 1, la sequenza di cifre binarie è un Flag ; in caso contrario, lo 0 che si incontra è necessariamente di riempimento e deve quindi essere eliminato.

– In emissione, si aggiunge uno 0 dopo ogni sequenza di cinque 1 consecutivi entro il corpo della trama (bit stuffing) indipendentemente da quale sia la cifra seguente

– In ricezione si contano le cifre 1 consecutive: se se ne incontrano cinque, si esamina la cifra successiva; se questa è un 1, la sequenza di cifre binarie è un Flag ; in caso contrario, lo 0 che si incontra è necessariamente di riempimento e deve quindi essere eliminato.



sequenza originaria di cifre binariesequenza originaria di cifre binarie

1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0

sequenza dopo l'operazione di riempimento

1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0




III.3.11: Esempio di protocollo di collegamentoIII.3.11: Esempio di protocollo di collegamento


Il Protocollo Punto-Punto (PPP)Il Protocollo Punto-Punto (PPP)

• E’ il protocollo di collegamento attualmente più usato per accedere a un ISP tramite, ad esempio, una linea telefonica commutata.

• I requisiti fissati per il suo progetto erano:– delimitazione delle trame;– trasparenza;– possibilità di supportare protocolli multipli dello

stato di rete;– rivelazione degli errori;– rivelazione di guasti nel DL- strato;– negozazione degli indirizzi del N-strato;– semplicità.

• E’ il protocollo di collegamento attualmente più usato per accedere a un ISP tramite, ad esempio, una linea telefonica commutata.

• I requisiti fissati per il suo progetto erano:– delimitazione delle trame;– trasparenza;– possibilità di supportare protocolli multipli dello

stato di rete;– rivelazione degli errori;– rivelazione di guasti nel DL- strato;– negozazione degli indirizzi del N-strato;– semplicità.


Trama PPPTrama PPP

1 1 1 2 variabile 2 o 4 1

01111110 11111111 00000011 01111110

Campo Flag: delimita la trama Campo Address: è di valore invariabile Campo Control: è di valore invariabile Campo Protocol: specifica a quale protocollo dello strato superiore

appartengono i dati incapsulati nel campo Information Campo Information: contiene i dati incapsulati dal protocollo di strato

superiore (ad es. IP); la lunghezza massima di base è 1500 byte Campo CRC: è sede degli extra- bit per la rivelazione di errore

1 1 1 2 variabile 2 o 4 1

01111110 11111111 00000011 01111110

Campo Flag: delimita la trama Campo Address: è di valore invariabile Campo Control: è di valore invariabile Campo Protocol: specifica a quale protocollo dello strato superiore

appartengono i dati incapsulati nel campo Information Campo Information: contiene i dati incapsulati dal protocollo di strato

superiore (ad es. IP); la lunghezza massima di base è 1500 byte Campo CRC: è sede degli extra- bit per la rivelazione di errore

Flag Address Control Protocol Information CRC Flag


Riempimento di byte (1/2)Riempimento di byte (1/2)

• Viene definito uno speciale byte “ignora” che ha configurazione 01111101.

• In emissione, all’atto della formazione della trama,–se in questa compare la sequenza Flag tra i due

Flag di delimitazione, nel flusso dei dati trasmessi;

–se il byte “ignora” compare come dato reale, • viene inserito il byte “ignora” (operazione di “byte

stuffing”).

• Viene definito uno speciale byte “ignora” che ha configurazione 01111101.

• In emissione, all’atto della formazione della trama,–se in questa compare la sequenza Flag tra i due

Flag di delimitazione, nel flusso dei dati trasmessi;

–se il byte “ignora” compare come dato reale, • viene inserito il byte “ignora” (operazione di “byte

stuffing”).


Riempimento di byte (2/2)Riempimento di byte (2/2)

• I byte “ignora” inseriti in emissione possono essere univocamente individuati in ricezione e quindi eliminati.

• Infatti, in ricezione, quando si incontra–un byte Flag preceduto da un byte “ignora”, –una coppia di byte “ignora”

il singolo byte “ignora” o uno dei due della coppia può essere rimosso per ricostruire i dati originali (operazione di “byte destuffing”).

• I byte “ignora” inseriti in emissione possono essere univocamente individuati in ricezione e quindi eliminati.

• Infatti, in ricezione, quando si incontra–un byte Flag preceduto da un byte “ignora”, –una coppia di byte “ignora”

il singolo byte “ignora” o uno dei due della coppia può essere rimosso per ricostruire i dati originali (operazione di “byte destuffing”).


Protocollo di Controllo del Collegamento (LCP) (1/2)


• Al fine di istaurare una connessione tra due DL entità, sulla quale consentire l’operatività di PPP, è necessario inizialmente uno scambio di messaggi al fine di negoziare la configurazione del collegamento;

• Analoga necessità sorge per supervisionare e per abbattere la connessione.

• Al fine di istaurare una connessione tra due DL entità, sulla quale consentire l’operatività di PPP, è necessario inizialmente uno scambio di messaggi al fine di negoziare la configurazione del collegamento;

• Analoga necessità sorge per supervisionare e per abbattere la connessione.




• Tali messaggi (pacchetti) sono definiti nel protocollo LCP e sono di tre tipi:

– Link Configuration Packets, utilizzati per instaurare e configurare una connessione di collegamento (Configure Request, Configure ACK, Configure NAK and Configure Reject);

– Link Termination Packets, utilizzati per abbattere la connessione di collegamento (Terminate Request, Terminate ACK);

– Link Maintenance Packets, utilizzati per gestire e monitorare il collegamento (Code Reject, Protocol Reject, Echo-Reject, Echo Replay, Discard Request).

• Tali messaggi (pacchetti) sono definiti nel protocollo LCP e sono di tre tipi:

– Link Configuration Packets, utilizzati per instaurare e configurare una connessione di collegamento (Configure Request, Configure ACK, Configure NAK and Configure Reject);

– Link Termination Packets, utilizzati per abbattere la connessione di collegamento (Terminate Request, Terminate ACK);

– Link Maintenance Packets, utilizzati per gestire e monitorare il collegamento (Code Reject, Protocol Reject, Echo-Reject, Echo Replay, Discard Request).


I protocolli NCP (1/2)I protocolli NCP (1/2)

• Quando la connessione di collegamento è stata istaurata e le opzioni sono state concordate, le due DL entità possono scambiarsi i pacchetti di controllo specifici dello strato di rete.

• Tali pacchetti sono definiti nei Protocolli di Controllo di Rete: esiste un NCP per ciascun Protocollo di Rete che sia trasportato da PPP.

• Quando la connessione di collegamento è stata istaurata e le opzioni sono state concordate, le due DL entità possono scambiarsi i pacchetti di controllo specifici dello strato di rete.

• Tali pacchetti sono definiti nei Protocolli di Controllo di Rete: esiste un NCP per ciascun Protocollo di Rete che sia trasportato da PPP.


I protocolli NCP (2/2)I protocolli NCP (2/2)

• Se sul collegamento sta operando IP, il Protocollo di Controllo IP (IPCP) provvede a configurare le IP- entità; i pacchetti IPCP sono inseriti in trame PPP permettendo alle IP-entità di scambiarsi i loro indirizzi IP e di accordarsi su come avverrà l’invio delle proprie PDU.

• NCP simili sono definiti per altri protocolli dello strato di rete.

• Se sul collegamento sta operando IP, il Protocollo di Controllo IP (IPCP) provvede a configurare le IP- entità; i pacchetti IPCP sono inseriti in trame PPP permettendo alle IP-entità di scambiarsi i loro indirizzi IP e di accordarsi su come avverrà l’invio delle proprie PDU.

• NCP simili sono definiti per altri protocolli dello strato di rete.

379 Aldo Roveri, Fondamenti di reti Univ. di Roma La Sapienza - a.a. 2009-2010 III.LE FUNZIONI DEI...

Documents

Transcript of 379 Aldo Roveri, Fondamenti di reti Univ. di Roma La Sapienza - a.a. 2009-2010 III.LE FUNZIONI DEI...