Reti di Calcolatori - Appunti Parziale 2

3.2 Rilevazione e correzione degli errori

Sono comuni gli errori nei collegamenti locali. Abbiamo due strategie per gestirli:

1) Codici per la correzione degli errori: Vengono inclusi in ciascun blocco dati

trasmesso una quantità di informazioni ridondanti, tali da permettere di

ricostruire il contenuto del blocco in caso di errore . Viene usata

principalmente per trasmissioni con cavi in rame o fibre ottiche. Un frame

consiste di m bit di dati e r bit di controllo (ridondanti). La somma di questi

dà n, cioè codeword di n bit. Si calcola quali e quanti bit corrispondenti sono

differenti tra due codeword e questo numero di bit diversi è detto Distanza di

d una all’altra, saranno necessari d errori su singoli bit

Hamming. Se due codeword sono a distanza di Hamming

per convertire una sequenza nell’altra. m

Nella maggior parte delle applicazioni di trasmissione dati, tutti i 2 possibili

messaggi sono legali, ma per via del modo con cui sono calcolati i bit di controllo, non tutte le possibili 2" codeword

Dato l’algoritmo per calcolare i bit di controllo, è possibile costruire una lista completa delle

vengono usate.

codeword legali e da questa lista trovare due codeword con la minima distanza di Hamming. Per trovare d errori è

necessario una codifica con distanza d+1, in quanto con tale codifica non esiste un modo in cui d errori su singoli bit

in un’altra ancora valida.

possano cambiare una codeword valida Quando la destinazione vede una codeword non

valida, riesce a determinare che c’è stato un errore. Analogamente, per correggere d errori è necessaria una codifica

con distanza 2d + 1; in tal modo le codeword legali sono così distanziate fra di loro, che anche con d cambiamenti la

codeword originale è sempre più vicina di ogni altra codeword e può quindi essere determinata univocamente.

di codifica a rilevazione d’errore si può realizzare aggiungendo un

Un semplice esempio bit di parità ai dati. Questo

viene calcolato in modo che il numero di 1 nella codeword sia sempre pari (o dispari). Per esempio, per trasferire

1011010 con parità pari bisogna aggiungere un bit per ottenere 10110100, mentre con parità dispari sarà 10110101.

Una codifica con un singolo bit di parità ha distanza d=2, infatti ogni errore su un singolo bit produce una codeword

con la parità sbagliata. Questa codifica può essere usata per rilevare errori su singoli bit, ma anche per raffiche di bit.

Anziché inviare una singola parola per volta con bit da destra a sinistra, vengono inviate intere colonne da sinistra a

ricostruite e verificate all’arrivo. Prendo tutti i caratteri, li metto

destra, in sequenza di k condeword consecutive

come per la sequenza ASCII. La sequenza è disposta riga per riga in modo da formare una matrice. Metto i bit di

controllo in posizioni intermedie di potenza di 2. I restanti bit (3, 5, 6, 7, 9, ecc.) sono riempiti con m bit di dati.

Ogni bit di controllo forza la parità di alcuni gruppi di bit , incluso se stesso, a essere pari (o dispari). Un bit può

essere incluso in diversi calcoli di parità. Per vedere quali bit di controllo sono legati a un certo bit di dati, riscri-

viamo k come somma di potenze di 2. Per esempio 11 = 1 + 2 + 8 e 29 = 1 + 4 + 8 + 1 6 . Un bit di dati è controllato

solo dai bit di controllo presenti nella sua espansione come somma di potenze di 2 (per esempio 11 è controllato solo

dai bit 1, 2 e 8). Quando una codeword viene ricevuta, la destinazione inizializza il contatore a zero. A quel punto

esamina ogni bit di controllo k (dove k = 1, 2, 4, 8, ...) per vedere se la parità è corretta, in caso negativo aggiunge il

valore k al contatore. Se il contatore è ancora a zero quando tutti i bit di controllo sono stati esaminati (cioè se non

sono stati rilevati errori), la codeword viene accettata come valida. In caso contrario il valore non nullo del

contatore indica il numero del bit in errore. Per esempio, se i bit di controllo 1, 2 e 8 sono in errore il bit invertito

infatti questo è l’unico che viene controllato dai bit di controllo 1, 2 e 8. Ricordiamo che i dati si trovano

è 1 1 ;

nelle posizioni 3, 5, 6, 7, 9, 10, 11. Questa tecnica si chiama bursting. Per correggere gli errori burst, invece, i dati

vengono trasmessi colonna per colonna a partire dalla prima a sinistra. Quando tutti i k bit della prima colonna sono

stati inviati si procede con la seconda e così via. Non è molto utilizzata.

d’errore:

2) Codifiche a rilevazione Viene introdotta abbastanza ridondanza tale che nel messaggio inviato e

ricevuto esistono informazioni per capire se esiste un errore e per chiedere la ritrasmissione . Vengono usate per

-6 -8

le trasmissioni wireless poiché rumorose e piene di errori. Si hanno bassi tassi di errore (10 - 10 errori per bit

trasmessi in funzione della tecnologia adottata). Al minimo basta trasmettere un solo bit di controllo per blocco

(trama) di n colonne e k righe. Prendiamo la trama di partenza e su quella effettuiamo un calcolo per verificare quale

è una posizione media con un algoritmo. Un bit di parità viene calcolato separatamente per ogni colonna e aggiunto

una riga alla volta. All’arrivo del blocco, la destinazione

come ultima riga della matrice. La matrice è poi trasmessa

controlla tutti i bit di parità. Se uno qualunque di questi bit è errato, la destinazione richiede la ritrasmissione del

finché l’intero blocco non sarà ricevuto

blocco, senza errori di parità. Per maggior sicurezza prendiamo un codice

polinomiale di riferimento o controllo ciclico di ridondanza (CRC code), che sono basate sul fatto di trattare le

sequenze di bit come dei polinomi a coefficienti che possono assumere solo i valori 0 oppure 1. Funziona come una

trama di k bit e’ vista come un polinomio

espressione con potenza massima k. La di grado k-1 (es. 110001 =

con l’impiego di un OR

5 4 0

x +x +x ). Viene addizionata (o sottratta) in binario e appiccicata alla trama in partenza

esclusivo. Dei polinomi si gestisce in modulo 2 secondo le regole della teoria dei campi algebrici e non ci sono

riporti per le addizioni o prestiti per le sottrazioni. Quando questo arriva, questo polinomio fa i calcoli sul campo dati

e se il risultato è esattamente quello appiccicato nella trama che è arrivato, non è stato corretto. Se i numeri non

combaciano, bisogna rinviare tutto. Quando si utilizza una codifica polinomiale, la sorgente e la destinazione

devono mettersi d’accordo in anticipo su un polinomio generatore. L’idea è quella di aggiungere un checksum alla

fine del frame in modo che il polinomio rappresentato dal frame con checksum sia divisibile per polinomio

generatore. Ci sarà quindi header, campo dati, checksum e trailer. Certi polinomi sono diventati degli standard

32 26 23 22 1 6 12 11 10 8 7 5 4 2

Quello usato per l’IEEE 802 è: x + x + x + x + x + x + x + x + x + x + x + x + x

internazionali.

1

+ x +1. Questo polinomio ha molte proprietà utili, fra cui quella che riesce a rilevare tutti i grappoli di errori di

lunghezza uguale o minore a 32 e tutti quelli che toccano un numero dispari di bit.

3.3 Protocolli data link elementari

Prima di trattare i protocolli, si devono vedere degli assunti fondamentali:

1) Si deve assumere che negli strati fisico, data link e network siano presenti dei processi indipendenti che comunicano

passandosi messaggi uno con l’altro. I processi dei livelli fisici e di data link gireranno su un processore all’interno di

uno speciale chip per I/O, mentre network girerà sulla CPU principale (son possibili anche altre implementazioni).

2) Un altro assunto è che la macchina A voglia mandare un consistente flusso di dati alla macchina B, usando un

servizio affidabile e orientato alla connessione. Poi considereremo il caso in cui B voglia simultaneamente mandare

dei dati ad A. Assumiamo che la sorgente A abbia a disposizione una quantità illimitata di dati pronti da trasmettere e

quindi non debba mai aspettare che i dati vengano prodotti, cioè lo strato network sia sempre pronto a fornire i dati

quando lo strato data link della macchina A li richiede. Nel nostro schema le macchine non sono soggette a crash,

cioè i protocolli che trattiamo si prendono cura degli errori di comunicazione ma non dei problemi causati dai crash

dei computer e dei conseguenti reboot.

3) Per quanto concerne lo strato data link, i bit contenuti nei pacchetti che gli arrivano dallo strato network sono tutti da

considerare come appartenenti ai dati e quindi da trasferire allo strato network della destinazione. Il fatto che lo strato

network possa considerare alcuni di questi bit come appartenenti all’intestazione dei pacchetti o altro, non riguarda

assolutamente lo strato data link.

Un protocollo elementare è composto da frame che a sua volta sono composti da 5

campi: kind, seq, ack, info, trailer più nel caso un CRC se lo stiamo usando. I primi

tre contengono le informazioni di controllo (chiamati intestazione del frame frame

header), info i dati da trasferire. Abbiamo:

1) Il campo kind dice se ci sono dati nel frame, poiché alcuni protocolli distinguono

i frame che contengono solo informazioni di controllo da quelli che contengono

anche i dati. Definisce il tipo di trama. e per l’ack, rispettivamente.

2) I campi seq e ack sono usati per i numeri di sequenza E’ il campo dati

3) Il campo info di un frame dati contiene un singolo pacchetto e non è usato per i frame di controllo.

che proviene dal livello di rete

Nella maggior parte dei protocolli si assume che il canale non sia affidabile e che a volte perda degli interi frame. Per

poter risolvere, il data link della sorgente deve far partire internamente un timer ogni volta che invia un frame. Se non

nessuna risposta entro un tempo determinato, l’allarme scatta e lo strato data link riceve un segnale di

viene ricevuta

interrupt. Abbiamo tre protocolli: E’ una

1) Protocollo simplex senza restrizioni: condizione utopica. I dati vengono trasmessi in una sola direzione ;

gli strati network della sorgente e della destinazione sono sempre pronti; è disponibile un buffer infinito; ha una

procedura composta da mittente e una da destinatario che è diretta; invia velocemente; ha solo campo info nel

campo dati; si aspetta solo frame corrette. Nei livelli fisico, data link e network, ci sono processi HW o SW

indipendenti, che comunicano tra loro, ad esempio, scambiandosi messaggi. Quando il SW di livello data link riceve

un pacchetto dal livello network, lo incapsula nel campo info tra un header ed un trailer contenenti info di

controllo; quindi vengono calcolati la checksum ed i delimitatori (di norma a cura di un HW apposito di livello

data link). In ricezione, l’HW di livello data link identifica i delimitatori, estrae il frame, ricalcola la checksum:

– Se è sbagliato, il SW di livello data link viene informato dell’errore;

– Se è corretto, il SW di livello data link riceve il frame (senza più checksum).

Il SW di livello data link, quando riceve un frame, esamina le informazioni di controllo:

– Se tutto è OK, consegna il contenuto, e solo quello, al livello network.

– Altrimenti intraprende le azioni necessarie per ottenere un frame corretto, e non consegna pacchetti al network.

2) Protocollo simplex stop-and-wait: Il canale fisico è un half-duplex, cioè è sempre occupato da una trasmissione

monodirezionale: in una direzione frame e successivamente in quella opposta ack richiesto. Supponiamo di avere

sempre il protocollo diviso come in simplex. Non invia velocemente; Stop and wait perché è invio e attesa di un

piccolo frame (feedback) di riscontro inviato dal destinatario al mittente , senza dati (dummy), che dà al mittente il

permesso di inviare il frame successivo; rallento però molto perché è di tipo 1 a 1. Si ha con buffer, senza buffer

Il problema di questo approccio è che è troppo conservativo perchè porta a un’utilizzazione

(collegamento-rete).

della banda disponibile ben al di sotto delle possibilità ottimali, fatta eccezione per la situazione dove per il

Solamente l’arrivo del frame di ack è importante per

ricevente il caso migliore e peggiore sono praticamente uguali.

il mittente, quindi la destinazione non dovrà preoccuparsi di mettervi informazioni particolari.

3) Protocollo simplex per canali rumorosi e disturbati: Considerando una situazione normale, posso avere un

Supponiamo che se un frame è danneggiato durante la trasmissione, l’HW

danneggiamento o perdita frame. della

destinazione riesce ad accorgersene calcolando il checksum. Nell’eventualità remota che il frame sia danneggiato in

modo tale che il checksum risulti comunque corretto, questo protocollo (come tutti gli altri) può fallire, cioè

potrebbe trasferire allo strato network un pacchetto erroneo. L’idea è che quando la sorgente invia un frame, la

destinazione risponde con un ack solo quando il frame è stato ricevuto correttamente. Se arriva un frame

danneggiato, allora la destinazione semplicemente lo scarta. Dopo che i timer della sorgente scattano, il frame

viene inviato di nuovo finché non arriva intatto a destinazione. Questo contiene però un errore fatale , infatti il

compito dei processi allo strato data link è quello di fornire ai processi network la possibilità di comunicare in modo

trasparente e senza errori. Lo strato network della macchina A passa una serie di pacchetti al suo strato data link,

che deve preoccuparsi che una serie identica di pacchetti arrivi allo strato network della macchina B, tramite il

rispettivo strato data link. Quello che serve, quindi, è un metodo che la destinazione possa usare per distinguere i

inserire un numero di sequenza nell’intestazione

frame che vede per la prima volta dalle ritrasmissioni, ovvero

del frame quando viene inviato. La destinazione può quindi controllare i numeri di sequenza e quindi riesce a sapere

se si tratta di un frame nuovo o di un duplicato da scartare. Un numero di sequenza con un solo bit è quindi

sufficiente. A ogni istante la destinazione si aspetta di ricevere un particolare numero di sequenza che, se è sbagliato

viene scartato come duplicato, se è corretto, viene accettato e passato al network. Quindi il numero di sequenza

atteso è incrementato in aritmetica modulo 2 (cioè lo 0 diventa 1 e viceversa). Si hanno 2 protocolli:

PAR (Positive Acknowledgement with Retransmission, risposta positiva con ritrasmissione)

E’ basata su un timer per cui se non trovo

ARQ (Automatic Repeat reQuest, richiesta automatica di ripetizione):

niente per un certo tempo, rinvio.

3.4 Protocolli a finestra scorrevole (sliding window)

Nei protocolli precedenti i frame di dati venivano trasmessi solamente in una direzione. Nella maggior parte delle

situazioni reali è necessario trasmettere in entrambe le direzioni (full-duplex) cioè avere due canali fisici di

un canale “di andata”

trasmissione separati e usare ciascuno di essi per una trasmissione simplex (in direzioni diverse):

(per i dati) e uno “di ritorno” (per gli ack). In entrambi i casi la banda del canale di ritorno risulta quasi interamente

l’utente paga per due circuiti, ma usa solo la capacità di uno.

sprecata poichè Nei protocolli precedenti si perdeva tempo

Un’idea migliore consiste nell’usare

sia per canale perfetto che per rumore perché devo attendere il dummit. lo stesso

circuito per entrambe le direzioni di comunicazione (come nei protocolli 2 e 3). In questo modello i frame dati che

passano da A a B sono mescolati a quelli di ack (non più autonomi come nei dummit) da A a B. Guardando al campo

nell’intestazione del

kind frame in arrivo, la destinazione può determinare se si tratta di dati oppure ack. Si può però

migliorare poichè quando arriva un frame di dati, la destinazione non invia subito un frame di controllo separato, ma

L’ack

aspetta che lo strato network gli passi il successivo pacchetto. viene aggiunto al frame di dati in uscita usando il

del

campo ack nell’intestazione frame. La tecnica che consiste nel ritardare gli ack, che avviene per blocchi, in uscita

(“trasportare in groppa”).

in modo da agganciarli al successivo frame di dati è chiamata piggybacking Il suo vantaggio

nell’intestazione del frame

principale rispetto agli ack separati, sta nel miglior uso della banda disponibile. Il campo ack

un’intestazione, un ack

costa solamente alcuni bit, mentre costruire un frame separato richiederebbe e un checksum.

Inoltre un minor numero di frame inviati significa anche un minor numero di interrupt di tipo “frame in arrivo”, e quindi

anche un minor numero di buffer nella destinazione, a seconda di come è strutturato il software della destinazione. Però il

campo piggyback introduce una complicazione non presente nei protocolli con ack separato. Quanto deve aspettare il

dell’ack?

data link per avere un pacchetto su cui effettuare il piggybacking Se il data link aspetta più a lungo del periodo

rendendo vano l’ack.

di timeout della sorgente, il pacchetto verrà ritrasmesso, Se il nuovo pacchetto arriva rapidamente,

dell’ack, a

viene fatto il piggybacking ltrimenti, se alla fine del periodo di attesa non è arrivato, il data link invia un frame

di ack separato. I successivi tre protocolli sono di tipo bidirezionale e appartengono alla classe chiamata sliding

(“finestra scorrevole”). Le differenze fra i tre protocolli riguardano l’efficienza, la complessità

window e i requisiti in

termini di buffer. Ogni frame in uscita contiene un numero di sequenza che va da 0 fino a un valore massimo che di solito

n

è 2 - 1, così che il numero di sequenza entra esattamente in un campo di n bit. I protocolli stop-and-wait e sliding

dei protocolli

window a 1 bit hanno n= 1, restringendo i numeri di sequenza a 0 e 1.L’essenza sliding window è che, a

ogni istante, la sorgente tiene traccia di un insieme di numeri di sequenza corrispondenti ai frame che è autorizzata

a inviare. Si hanno una serie di trame , non più una, per le quali definisco delle finestre (bufferizzazioni) per le quali

posso avere delle conferme. Si hanno due canali fisici separati e due canali fisici sottoutilizzati. Ci sono due finestre (la

grandezza è in bit, nel nostro caso è in 8 bit cioè 8 posizioni): finestra di trasmissione (sending window) e finestra di

ricezione (receiving windows). Ci sono 8 possibili posizioni di invio. Man mano che invio, sposto in avanti la barra

sino a che non viene confermata, dopodiché attacco l’ack all’invio nel senso contrario. Si dice che questi frame si trovano

nella finestra di invio [una finestra di invio vuota non significa che non è possibile inviare alcun frame]. La destinazione

della finestra di ricezione, che corrisponde all’insieme dei frame che può accettare. Le finestre d’invio e di

tiene traccia

ricezione non devono necessariamente avere gli stessi limiti inferiori o superiori e neppure la stessa dimensione , infatti

in alcuni protocolli hanno delle dimensioni fisse, in altri variabili nel tempo. Supponiamo che il canale fisico di

comunicazione sia simile a un cavo, cioè che debba

trasferire i frame nell’ordine in cui sono stati inviati. Il

numero di sequenza nella finestra d’invio rappresenta i

frame che sono già stati trasmessi correttamente oppure

l’ack

che sono in transito, ma non hanno ancora ricevuto

corrispondente. Quando un nuovo pacchetto arriva

dallo strato network, gli viene assegnato il numero di

sequenza successivo in ordine crescente e il limite

superiore della finestra è incrementato di uno.

s’incrementa

Quando invece arriva un ack, di uno il

limite inferiore della finestra. In questo modo la finestra

continua a mantenere la lista dei frame che ancora

necessitano di ack [Figura]. Visto che i frame che sono

all’interno della finestra d’invio potrebbero andare

persi o danneggiati durante la trasmissione, la sorgente

deve mantenere tutti questi frame nella sua memoria

per l’eventuale ritrasmissione. Quindi, se la massima

dimensione della finestra è n, la sorgente ha bisogno di

avere n buffer per contenere i frame in attesa di ack. Se la finestra cresce fino alla sua massima dimensione, lo strato data

link è costretto a chiudere forzatamente lo strato network finché non si libera almeno un buffer. La finestra di ricezione

tiene traccia dei frame che possono essere accettati dalla destinazione. Fissare una dimensione della finestra pari a 1

significa stabilire che lo strato data link accetta i frame solamente in ordine , con finestre più larghe questo non è più

vero. Lo strato network riceve sempre i dati nell’ordine corretto, indipendentemente dalla dimensione della finestra nel

data link. Protocolli:

1) Protocollo sliding window di 1 solo bit: Un protocollo simile usa il metodo full-duplex di tipo stop-and- wait, cioè

prima la sorgente trasmette un frame e poi aspetta di ricevere il corrispondente ack per poter continuare a trasmettere

il successivo frame, perché la finestra è forzata ad 1. Si deve stare attenti alla sincronizzazione :

 Se è corretta (a), cioè se gli strati data link non partono simultaneamente, tutto funziona correttamente, ovvero:

frame 0 consegnato dal liv. rete di A e inviato da A a B

frame 0 consegnato dal liv. rete di B e inviato da B a A

 Se invece la sincronizzazione è sbagliata (b) e entrambi gli

strati data link partono simultaneamente, allora abbiamo una

situazione particolare. La macchina che parte prende il primo pac-

chetto dal suo strato network, lo usa per costruire un frame e lo

invia. Quando questo (o un altro) frame arriva a destinazione, lo

strato data link della destinazione controlla per vedere se è un

duplicato (come nel protocollo 3). Se il frame è quello che la

destinazione si aspettava, lo passa allo strato network e la finestra

della destinazione viene portata avanti. Il campo di ack contiene il

numero dell’ultimo frame ricevuto senza errori. Se questo numero

concorda con il numero di sequenza che la sorgente vuole

trasmettere, allora la sorgente sa di aver finito il lavoro con il

frame memorizzato nel buffer e può prendere il successivo

pacchetto dal suo strato network. Se non concordano, allora deve provare a inviare di nuovo lo stesso frame. Quando

un frame viene ricevuto, un altro frame è inviato indietro. Prendiamo la situazione in cui il computer A tenta di

inviare il frame 0 al computer B, mentre B vuole mandare il frame 0 ad A. Supponiamo che A mandi il frame a B, ma

l’intervallo di timeout del frame 0 di A è leggermente troppo corto. Di conseguenza, A può generare timeout a raffica

mandando una serie di frame identici, tutti con seq = 0 e ack = 1. Quando il computer B riceve il primo frame valido

lo accetta. Tutti i frame successivi saranno rifiutati perché B ora si aspetta dei frame con numero di seq=1 e non 0.

ad aspettare l’ack

Inoltre, visto che i duplicati hanno ack = 1 e B continua di 0, B non prenderà altri pacchetti dal suo

strato network. Dopo aver rifiutato ogni frame duplicato in arrivo, B manda ad A un frame che contiene seq = 0 e ack

= 0. Infine, uno di questi arriva correttamente ad A e fa sì che A mandi il pacchetto successivo. Nessuna

combinazione di pacchetti persi o di timeout prematuri può causare la trasmissione di pacchetti duplicati allo strato

network, la perdita di pacchetti oppure situazioni di deadlock. Una situazione particolare si ha quando entrambi i

soggetti mandano simultaneamente un pacchetto iniziale. Nella parte (a) viene mostrata la normale operatività del

protocollo, in (b) si vede invece la situazione particolare. Se B aspetta il primo frame da A prima di inviarne uno dei

suoi, la sequenza è come mostrato in (a), e ogni frame viene accettato. Se invece A e B iniziano simultaneamente la

la situazione (b). In (a) l’arrivo di ogni

comunicazione, i primi frame si incrociano e lo strato data link raggiunge

frame porta un nuovo pacchetto per lo strato network. In (b) metà dei frame contengono dei duplicati, anche quando

non ci sono errori di trasmissione. Situazioni simili possono accadere come risultato di timeout pre maturi, anche se

un soggetto inizia a trasmettere nettamente prima dell’altro.

2) Protocollo che usa go back n: Fino ad ora abbiamo supposto che il tempo necessario a trasmettere un frame alla

destinazione sommato al tempo per l’ack sia trascurabile. In alcuni casi in queste situazioni i tempi lunghi di

di efficienza dell’uso della banda.

tragitto dei frame possono avere pesanti implicazioni in termini Questo problema

alla sorgente di aspettare l’ack della destinazione

può essere visto come una conseguenza della regola che richiede un’efficienza

prima di mandare il frame successivo. Se alleggeriamo questo requisito possiamo ottenere migliore. La

soluzione sta nel sostituire il concetto seq-ack con un numero di frame w maggiore di uno, prima del blocco

dell’invio per mancato pervenimento dell’ack. Con una scelta appropriata di w la sorgente è in grado di

trasmettere per un tempo pari al tempo totale di transito senza arrivare a riempire la finestra. Il bisogno di avere una

finestra larga da parte della sorgente si ha quando il prodotto tra banda e ritardo di trasmissione totale è

particolarmente grande. Se la banda è larga, anche in presenza di un piccolo ritardo la sorgente è in grado di saturare

la finestra velocemente, a meno che questa non sia di grandi dimensioni. Se il ritardo è grande (es. su un canale

satellitare geostazionario) la sorgente può saturare la finestra anche con una banda moderata. Il prodotto di questi

due fattori indica qual è la capacità della pipeline (tubo). La sorgente, per poter operare alla massima

efficienza, ha bisogno di poterla utilizzare tutta se nza fermarsi. Questa tecnica è chiamata pipelining. Il

pipelining dei frame su un canale di comunicazione non affidabile comporta alcuni seri problemi. Cosa succede

quando un frame nel mezzo di una lunga sequenza viene danneggiato o perso? Una gran quantità di frame

arriverà alla destinazione prima che la sorgente riesca a sapere che ci sono stati degli errori di trasmissione.

Quando un frame danneggiato arriva a destinazione, deve ovviamente essere scartato. Cosa deve fare, però, la

destinazione con i frame corretti che eventualmente seguono quello danneggiato? Ricordiamo che lo strato data link

della destinazione è obbligato a mandare i pacchetti allo strato network nella corretta sequenza. Go back n (indietro

scarti tutti i frame successivi all’errore senza mandare l’ack

n) vuole che la destinazione semplicemente per

“piggybacking”,

questi frame scartati [il protocollo è bidirezionale, perciò continuano ad essere inviate le conferme

di sequenza dell’ultimo frame passato

con il numero allo strato network]. La strategia corrisponde a una finestra di

1. In altre parole lo strato data link, rilevato l’errore, si rifiuta di accettare

ricezione di dimensione qualunque frame

eccetto il successivo che deve inviare allo strato network. Se la finestra della sorgente si riempie prima che il timer

Dopo un po’ di tempo la sorgente va in timeout e ritrasmette in ordine

scatti, la pipeline comincia a svuotarsi. l’ack,

tutti i frame che non hanno ricevuto cominciando da quello danneggiato o perso. Questo approccio può

far perdere molta banda se la frequenza degli errori è alta. Nella Figura vediamo go back n nel caso di una finestra di

Con w=10, prima dell’invio del 10 frame dovrà essere pervenuto ack=0. E’ strettamente legata

0

destinazione larga.

alla velocità di propagazione della linea utilizzata (aumento dell’efficienza). Viene dato un intervallo che il livello

data link si attende di avere come intervallo di scarto

potenziale. La fila di sopra trasmette mentre quella

di sotto riceve. A trasmette 0, viene confermato e

viene inviato ack di 0. Stessa cosa di 1. Quando

invia 2 viene generato un errore che non viene

riscontrato subito perché per garantire una certa

velocità di trasferimento, mi sono assicurato un certo

intervallo di tempo in cui l’invio continua fino a che

viene rilevato dopo un certo tempo (tempo di scarto

potenziale), che 2 non è mai arrivato e allora si vede

qual è l’ultima trama confermata (1) e si continua da

questa. Il buffer mantiene memoria delle trame pari

almeno all’intervallo stabilito tra le due stazioni, per

essere pronto ad inviare subito. Consente di bloccare

tutti gli ack da 1 in poi. E’ anche questa

3) Protocollo a ripetizione selettiva:

ed è più pesante dell’altra.

una tecnica di pipeling

C’è un intervallo più ampio ma siccome si richiede

la riconferma “fine”, riduco i tempi di invio perché

l’ack arriva prima. Quando arriva l’ack corretto, le

trame rinviate sono quelle che devo rinviare, cioè l’unica che ho perso è quella non confermata. Quindi l’altra

strategia generale per trattare gli errori in presenza di pipelining è chiamata ripetizione selettiva. Con tale metodo,

un frame in errore viene scartato, mentre i frame buoni ricevuti successivamente vengono messi in un buffer.

Quando la sorgente va in timeout, solo il frame più vecchio senza ack viene ritrasmesso. Se quel frame arriva

correttamente, la destinazione può passare in sequenza allo strato network tutti i frame che ha nel buffer. La

ripetizione selettiva è spesso associata al fatto che la destinazione invia un ack negativo (NAK) quando trova un

errore, per esempio quando riceve un errore di checksum o un frame fuori sequenza. I NAK stimolano la

ritrasmissione prima che il timer corrispondente scatti, e quindi aumentano le performance. Nella Figura (b) i frame 0

e 1 sono di nuovo ricevuti correttamente con ack, mentre il frame 2 è perso. Quando il frame 3 arriva a

destinazione, lo strato data link nota che si è perso un frame, quindi invia un NAK per il frame 2 e mette il 3 nel

buffer. Quando anche i frame 4 e 5 arrivano, anche questi vengono messi in buffer dallo strato data link, ma non

allo strato network. Dopo un po’ il NAK 2 raggiunge

sono ancora passati la sorgente, che manda immediatamente

una nuova copia del frame 2. Quando la copia arriva a destinazione lo strato data link ha tutti i frame da 2 a 5, e li

nell’ordine corretto può anche mandare l’ack

può quindi passare allo strato network. A questo punto di tutti i frame

fino a 5 incluso, come mostrato in figura. Se si dovesse perdere il NAK, la sorgente andrà comunque in timeout per il

frame 2 e autonomamente prenderà la decisione di ritrasmettere il frame 2 (e solamente quello), ma ciò avviene con

un certo ritardo. In effetti, il NAK serve per accelerare la ritrasmissione di uno specifico frame. La ripetizione

selettiva corrisponde ad avere una finestra di ricezione maggiore di 1. Ogni frame nella finestra può essere

accettato e messo in buffer fino a che tutti quelli che lo precedono sono stati passati allo strato network.

3.6 Esempi di protocolli data link

Ci sono vari protocolli: Il primo è HDLC, un classico protocollo orientato ai bit. Il secondo, PPP, è il protocollo usato per

connettersi a Internet con il modem del computer di casa.

1) HDLC (High-level Data Link Control- controllo del data link ad alto livello): Lo standard ISO è diventato HDLC,

mentre prima era SDLC (Synchronus Data Link Control). CCITT ha adottato e

modificato HDLC per creare il suo LAP (Link Access Procedure, procedura di

accesso al collegamento), che è parte dello standard X.25 per le interfacce di rete,

il quale è stato a sua volta modificato in LAPB per renderlo più compatibile con

E’ un protocollo orientato

una successiva versione di HDLC. al riempimento dei

bit, usando il bit stuffing (inserimento di zeri aggiuntivi) per la trasparenza dei

e per evitare che le sequenze di terminazione compaiano all’interno dei

dati

frame. Tutti i protocolli orientati ai bit possono essere trasmessi attraverso

collegamenti sincroni o asincroni e usano una struttura di frame (figura):

a. Il campo Address è di assoluta importanza per le linee con più terminali

(comunicazione multi punto), in quanto è usato proprio per indicare il

terminale. Nelle linee punto-punto, a volte è usato per distinguere i comandi dalle risposte, cioè trasmettere

pacchetti o no successivi.

b. Il campo Control viene usato per numeri di sequenza (non solo 0 e 1 ma più bit), per gli ack e altri scopi.

può contenere qualunque tipo d’informazione. Può avere lunghezza arbitraria,

c. Il campo Data anche se

l’efficienza del checksum diminuisce al crescere della lunghezza del frame, per via della maggior probabilità

d’incontrare E’ variabile nel senso che posso caricare quanti bit voglio,

errori burst multipli. poiché ho una

dimensione molto flessibile.

d. Il campo Checksum è un codice a ridondanza ciclica (CRC-CCITT)

sia all’inizio

e. Il frame è delimitato da una sequenza flag (01111110) che alla fine. Nelle linee punto-punto,

quando non ci sono dati da trasmettere, viene continuamente trasmessa la sequenza flag. Il frame di

lunghezza minima contiene tre campi (totale di 32 bit), escludendo i flag ad entrambe le estremità del frame

Avendo un sliding window, i frame possono essere di tre tipi:

Informazione: I contenuti del campo Control sono nella Figura. Il protocollo

usa una finestra con un numero di sequenza di 3 bit. In ogni istante possiamo

avere fino a 7 frame in attesa di ack.

a. Il campo Seq è il numero di sequenza del frame.

è usato per il piggyback dell’ack.

b. Il campo next Tutti i protocolli di

questa famiglia aderiscono alla convenzione di usare per il

piggyback dell’ack, non il numero dell’ultimo frame ricevuto, ma

invece quello del successivo frame non ancora ricevuto (cioè quello

che la destinazione si aspetta). Questa scelta è puramente arbitraria:

non importa quale convenzione si usa, l’importante è essere consistenti nel suo uso.

c. Il bit P/F (Poll/Final) è usato quando un computer vuole interrogare un gruppo di terminali. Se usato

come P, il computer invita il terminale a mandare i dati. Tutti i frame inviati dal terminale, eccetto

l’ultimo, hanno il bit mentre l’ultimo è impostato a

P/F impostato a P, F. In alcuni protocolli il bit P/F è

usato per forzare l’altra macchina a inviare immediatamente un frame di tipo supervisione, senza quindi

aspettare di avere del traffico all’indie tro per eseguire il piggybacking. Questo bit è usato, in alcuni rari

casi, anche in connessione con i frame senza numero. 1=Final

Supervisione: si distinguono a seconda del valore del campo Type (tipo), dicendoci cosa accade:

a. Il tipo 0 è un frame di ack (RECEIVE READY, cioè ricevi e stai pronto) usato per indicare il prossimo

di sequenza atteso. E’ usato quando non c’è traffico all’indietro da usare per il

numero piggybacking.

b. Il tipo 1 è un frame di tipo ack negativo (chiamato REJECT, cioè rifiuta). Viene usato per indicare che è

stato rilevato un errore di trasmissione. A quel punto il campo Next indica il primo frame della sequenza

che non è stato ricevuto correttamente (cioè il frame che deve essere ritrasmesso). La sorgente deve

ritrasmettere tutti i frame a partire da Next. Questo tipo di strategia è simile a quella del protocollo 5.

READY (ricevi e fermati). Serve per generare 1’ack

c. Il tipo 2 è detto anche RECEIVE NOT di tutti i

frame fino a, ma senza includere, Next. E simile a RECEIVE READY, però in questo caso viene

comunicato alla sorgente di smettere di trasmettere. Viene usato per segnalare dei problemi temporanei

con la destinazione, per esempio il riempimento del buffer, e non come alternativa al controllo di flus so

con sliding window. Quando la condizione di errore è stata superata, la destinazione manda RECEIVE

READY, REJECT o particolari frame di controllo.

d. Il tipo 3 è SELECTIVE REJECT (rifiuta selettivamente) e richiede la ritrasmissione solo del frame

specificato. In questo senso è simile al nostro protocollo 6 e quindi è utile nel caso in cui la finestra della

sorgente è minore o uguale alla dimensione allocata per i numeri di sequenza. Quindi se la destinazione

desidera mettere in buffer i frame fuori sequenza, per esempio per un loro potenziale uso futuro, può farlo

forzando la ritrasmissione degli specifici frame che gli interessano usando SELECTIVE REJECT. I

protocolli HDLC e ADCCP implementano questo tipo di frame, per SDLC e LAPB non è definito.

Senza numero: Viene usata a volte per informazioni di controllo, ma può anche trasportare dati, per conto di

servizi senza connessione e non affidabili (riempimento del traffico). I vari protocolli orientati ai bit differiscono

considerevolmente nell’implementazione di questa classe, al contrario delle altre due che sono identiche per tutti.

Sono disponibili 5 bit per indicare il tipo di frame, però non tutte le 32 combinazioni sono usate.

Tutti i protocolli hanno i comandi:

1) DISC (DISConnect, disconnetti), che permette a una macchina di annunciare che sta andando fuori linea

(per esempio per manutenzione).

2) SNRM (Set Normal Response Mode,connesso in attesa, master-slave, imposta il modo di risposta nomale)

serve per permettere a una macchina che è appena tornata in linea di annunciare la sua presenza e forzare la

(cioè asimmetrico) in cui un’estremità della linea è master

sequenza di numeri a zero. È un modo sbilanciato

e l’altra è slave (servo).

(capo)

3) Per rendere il protocollo più appropriato al caso di comuni cazioni fra pari, HDLC e LAPB introducono un

comando aggiuntivo: SABM (Set Asynchronous Balanced Mode, conneso in attesa, imposta il modo

asincrono bilanciato). Esegue un reset della linea e dichiara che entrambi i soggetti della comunicazione sono

di pari grado. Vengono introdotti anche i comandi SABME e SNRME, analoghi di SABM e SNRM, con la

differenza che i primi abilitano un formato esteso per i frame che usa 7 bit per i numeri di sequenza, al posto

dei 3 bit usati dagli altri.

rifiuta i frame), usato per indicare l’arrivo di un frame con il checksum corretto ma

4) FRMR (FraMe Reject,

con una semantica impossibile. Esempi di semantiche impossibili sono: un frame di tipo (supervisione) in

LAPB, oppure un frame più corto di 32 bit, un frame di controllo illegale, un ack di un frame che era al di

dati da 24 bit con l’indicazione degli errori nel

fuori della finestra, ecc. I frame FRMR contengono un campo

frame con la semantica impossibile. Quindi questo campo contiene: il campo di controllo del frame errato, i

parametri di finestra e una collezione di bit che indica l’errore specifico. I frame di controllo, così come

anch’essi un ack.

quelli dati, si possono perdere o danneggiare e quindi devono avere Per questo scopo viene

usato uno speciale frame di controllo, chiamato UA (Unnumbered acknowledgement, ack senza numero).

Visto che in ogni istante ci può essere un solo frame di controllo in uscita, non sono possibili ambiguità su

sta ricevendo l’ack.

quale frame di controllo

I rimanenti frame di controllo hanno a che vedere con le operazioni di inizializzazione, inter rogazione (polling), e di

sullo stato. C’è anche un tipo di frame di controllo che può contenere informazioni, UI (Unnumbered

rapporto

Information, informazione non numerata). Questi dati non sono passati allo strato network, sono solamente per lo

dall’essere perfetto.

strato data link. Anche se è molto usato, il protocollo HDLC è ben lontano

– RFC 1144): Non da l’indirizzo IP della macchina. E’ un grande problema perché vuol dire che

2) SLIP (RFC 1055

l’indirizzo deve essere acquisito forzosamente dall’utente. Non

l’IP

gestisce gli errori, supporta solo IP, number assegnato (non

gestisce l’assegnazione dinamica), non ha autenticazione

3) Lo strato data link in Internet: Internet consiste in una serie di

e router) e nell’infrastruttura di

macchine individuali (host

comunicazione che le connette fra di loro. All’interno di un

singolo edificio si usano spesso delle LAN per

l’interconnessione delle macchine, mentre la maggior parte

dell’infrastruttura WAN è formata da linee punto-punto

dedicate. La comunicazione punto-punto è usata principalmente

in due situazioni. Nella prima abbiamo una o più LAN, ognuna

costituita da diversi host (personal computer, workstation,

server, ecc) e router (oppure bridge, che hanno funzioni simili).

Spesso i router sono connessi da una LAN detta backbone

“spina dorsale”). Tipicamente tutte le connessioni

(letteralmente

verso il mondo esterno passano attraverso uno o due router che hanno delle linee dedicate verso router remoti. Sono

questi router e le linee che li collegano a creare le sottoreti sulle quali è costruito Internet. Nella seconda abbiamo la

connessione di milioni di individui, che si collegano a Internet da casa attraverso la linea telefonica tramite modem.

casa dell’utente si collega al

Tipicamente, succede che il PC di router di un Internet service provider (ISP), e quindi

diventa a tutti gli effetti un host connesso a Internet. Questo modo di operare è praticamente identico ad avere una

che la connessione termina quando l’utente

linea dedicata fra il PC e il router, a parte il fatto chiude la chiamata. Il

caso di un PC di casa che chiama un Internet service provider è illustrato nella Figura. Nella figura il modem è

disegnato esternamente al computer per enfatizzarne il suo ruolo, comunque nella maggior parte dei computer moderni

troviamo un modem interno. Per le linee dedicate router-router come per quelle che usano la linea telefonica per il col-

legamento host-router, è necessario avere un protocollo data link di tipo punto-punto che gestisca il framing, il

controllo degli errori e le altre funzioni. nell’RFC 1661 e

4) PPP (Point-to-Point Protocol): Il protocollo usato da Internet si chiama PPP, che è definito

ulteriormente elaborato in altri RFC (come per esempio RFC 1662 e 1663). PPP era stato progettato per lavorare

assieme ad altri protocolli di livello superiore, come l'IP, IPX, e AppleTalk. L'uso originario era quello connettere due

computer usando una linea telefonica. Oggi usato per ADSL nelle varianti: PPPoA, PPPoE. Molto ut ilizzato anche

nelle connessioni GPRS. Fra le varie funzionalità troviamo: la rilevazione degli errori, il supporto per più protocolli, la

l’autenticazione. Tre

possibilità di negoziare gli IP al momento della connessione e la possibilità di effettuare

parametri principali sono.

Un metodo di framing che permette di delimitare in modo non ambiguo la fine di un frame e l’inizio del

a. successivo. Il formato del frame permette anche di gestire la rilevazione degli errori.

b. Un protocollo di collegamento per gestire la connessione, il test della linea, negoziare le opzioni di collegamento e

LCP

gestire la disconnessione in modo pulito quando la linea non serve più. Questo protocollo è chiamato (Link

Control Protocol, protocollo di controllo del collegamento). LCP supporta sia circuiti asincroni sia sincroni e

gestisce le codifìche orientate ai bit come pure quelle orientate ai byte.

Una modalità per negoziare le opzioni relative allo strato network, in modo indipendente dall’implementazione di

c. tale strato che verrà usata per la comunicazione. Il

NCP

metodo scelto avrà un diverso (Network

Control Protocol, protocollo di controllo del

network) per ogni strato network supportato.

E’ Orientato al carattere e non al bit come HDLC.

d. - gestisce gli errori

- supporta oltre IP anche altri protolli

- IP number assegnato dinamicamente

permette l’autenticazione

-

HDLC e PPP hanno le stesse caratteristiche di campo dati, cioè entrambi possono caricare un numero variabile di dati.

Dopo aver stabilito i parametri PPP, vengono inviati una serie di pacchetti NCP per configurare lo strato network.

Tipicamente il PC vuole usare il TCP/IP e quindi ha bisogno di ottenere un indirizzo IP. Siccome gli indirizzi IP sono una

risorsa limitata, normalmente un ISP ne ha a disposizione un blocco che poi assegna dinamicamente ai PC man mano che

si connettono e solo per la durata della sessione. Se un provider ha a disposizione n indirizzi, allo ra potrà avere al

massimo n macchine connesse simultaneamente, però la sua base di clienti può essere molto maggiore di n. NCP è usato

per assegnare gli indirizzi IP. A questo punto il PC è diventato a tutti gli effetti un host connesso a Internet e quindi può

l’utente ha finito di lavorare, NCP si

inviare e ricevere pacchetti come se fosse connesso stabilmente alla rete. Quando

prende carico di terminare la connessione allo strato network e liberare l’indirizzo IP. A questo punto LCP chiude la

connessione data link. Infine il computer comunica al modem di chiudere la linea telefonica e quindi rilasciare la con-

nessione allo strato fisico. Il formato del frame PPP è stato scelto in modo da assomigliare a quello di HDLC. La

principale differenza fra PPP e HDLC è che PPP è orientato ai caratteri, mentre HDLC è orientato ai bit. In particolare

PPP usa il byte stuffing sulle linee telefoniche, così che tutti i frame sono costituiti da un numero intero di byte. Non è

possibile mandare un frame di 30,25 byte con PPP, mentre si può con HDLC. I frame PPP possono essere trasferiti, oltre

che su linee telefoniche, anche su linee SONET oppure linee orientate ai bit con protocollo HDLC (per esempio per

All’interno della struttura:

connessioni router-router). Il formato del frame PPP è mostrato nella Figura.

 Inizio e fine byte con il flag byte standard HDLC (01111110), su cui viene applicato il byte stuffing se compare

all’interno dei dati.

 Campo Address: viene sempre impostato a 11111111 per indicare che tutte le stazioni devono accettare il frame. In

questo modo si evita il problema di dover assegnare indirizzi data link

 Campo Control, che ha come valore di default 00000011. Questo valore indica un frame senza numero. In ambienti

rumorosi, come le reti wireless, si può usare una trasmissione affidabile con numerazione dei frame. I dettagli sono

definiti in RFC 1633, anche se in pratica è usata molto di rado. Visto che Address e Control sono sempre costanti nella

configurazione di default, LCP contiene un meccanismo per far sì che la sorgente e la destinazione possano negoziare

l’opzione di omettere completamente questi campi e salvare quindi due byte per frame.

 Il quarto campo è Protocol e serve per comunicare quale tipo di pacchetto è contenuto nel campo Payload. I protocolli

(non solo IP ma anche altri) che cominciano con un bit a 0 sono protocolli di strato network come IP, IPX, OSI,

CLNP, XNS. Quelli che cominciano con un bit a 1 sono usati per negoziare altri protocolli. La dimensione di default

del campo Protocol è 2 byte, ma può essere negoziata fino a 1 byte con LCP. Ci sono protocolli specifici

1) protocollo di instaurazione, mantenimento e rilascio della linea, LCP (Line Control Protocol)

2) protocollo di negoziazione verso il livello rete diverso per singolo host, NCP (Network Control Protocol)

 Il campo Payload: ha lunghezza variabile fino a un valore massimo che può essere negoziato usando LCP durante

l’inizializzazione della connessione. Il valore di default è 1.500 byte. Se necessario ci può essere rie mpimento del

campo dopo i dati.

 Il campo Checksum: normalmente di 2 byte, ma può essere anche negoziato un checksum di 4 byte.

Vediamo adesso come le linee vengono attivate e disconnesse. Il diagramma (semplificato) della Figura mostra le fasi

che una linea deve attraversare per essere attivata e poi disconnessa. La sequenza si applica sia alle connessioni via

modem sia a quelle router-router. Il protocollo comincia con la linea nello stato DEAD, che significa che allo strato fisico

non abbiamo nessuna portante e quindi non esiste ancora nessuna connessione. Dopo aver stabilito una connessione fisica

la linea si muove allo stato ESTABLISH. A quel punto comincia la negoziazione LCP che, se ha successo, porta allo stato

AUTHENTICATE. Ora sorgente e destinazione possono controllare la loro reciproca identità, se lo desiderano. Quando si

entra nella fase NETWORK, viene invocato l’appropriato protocollo NCP per configurare lo strato network. Se la

configurazione ha successo si raggiunge OPEN e può quindi cominciare il trasporto dei dati. Quando il tra sporto è finito,

la linea si sposta in TERMINATE e da lì toma a DEAD quando viene rila sciata la portante. Le opzioni del protocollo data

link sono negoziate con LCP durante la fase ESTABLISH. Il protocollo LCP non si occupa delle opzioni negoziate, ma

solo del meccanismo per compiere questa operazione. Fornisce al processo che inizia la comunicazione un modo per

poter fare una proposta e alla controparte

un modo per poterla accettare o rifiutare,

in tutto o in parte. LCP fornisce ai due

processi anche un modo per testare la

qualità della linea e quindi giudicare se

può essere considerata adeguata per

stabilire una connessione. Infine, il

protocollo LCP consente di disconnettere

le linee quando non servono più. RFC

1661 definisce 11 tipi di frame LCP.

CAPITOLO 4 (Il sottostrato MAC - Medium Access Control)

È vicino all’hardware e si occupa di

Il MAC è un sottostrato del Data Link Layer. gestire le modalità con cui un insieme

di elaboratori accede ad un unico mezzo condiviso. Esistono due tipi di reti:

1) Punto a punto: Macchine 1 ad 1

Broadcast: L’impiego di canali broadcast (o multiaccesso o ad accesso casuale) viene

2) regolato da protocolli MAC

che sono tipici delle reti LAN e Satellitari.

4.1 II problema dell’assegnazione del canale

Il tema centrale è il sistema utilizzato per assegnare un singolo canale broadcast a utenti in competizione tra loro.

Abbiamo due tipi di assegnazione del canale:

1) Assegnazione statica del canale in LAN e MAN: Per assegnare un singolo canale, tra più utenti in competizione si usa

il multiplexing a divisione di frequenza FDM (Frequency Division Multiplexing). Abbiamo N utenti, banda divisa in

N parti uguali:

 Se N utenti è piccolo e costante: ognuno ha un volume di traffico pesante (come nel caso delle centrali di

commutazione interurbane) e FDM è un meccanismo di assegnazione semplice ed efficiente.

 Se N utenti è elevato e variabile, oppure il traffico è irregolare: FDM presenta alcuni problemi.

 non c’è alcuna

Se N regioni = N utenti: ogni utente usa una propria banda di frequenza e interferenza tra utenti.

 Se N regioni > N utenti: si spreca parte dello spettro. Infatti quando alcuni utenti non sono attivi, la loro banda è

persa, poichè non la utilizzano e a nessun altro è consentito di farlo.

 Se N regioni < N utenti: alcuni utenti non potranno comunicare perché non è disponibile la banda necessaria, anche

se alcuni che in precedenza hanno ricevuto una banda di frequenza non stanno ricevendo o trasmettendo niente.

Nella maggior parte dei sistemi di computer il traffico dati è altamente variabile (rapporti di 1.000 a 1 tra picchi di

traffico e traffico medio sono abbastanza comuni), perciò la maggior parte dei canali rimarrebbe quasi sempre

inutilizzata. Le scarse prestazioni del sistema FDM statico si possono evidenziare conside rando un semplice calcolo

di teoria delle code. Prendiamo la formula, dove:

 T, ritardo medio per un canale (s)

 C, capacità del canale (bps);

 1/μ, lunghezza media del frame (bit/frame)

 λ, frequenza degli arrivi frame (frame/s).

Usando FDM, con N canali, il ritardo medio sarà (Figura). La seconda formula è

maggiore della prima, quindi il ritardo medio quando si utilizza FDM è N volte

peggiore del ritardo che si otterrebbe se tutti i frame fossero ordinatamente inseriti in una grande coda centrale e

ordinata. Lo stesso ragionamento che si applica a FDM vale anche per la tecnica di multiplexing a divisione di tempo

(TDM). A ogni utente viene assegnato un N-esimo intervallo tempora le; se un utente non utilizza il proprio intervallo,

questo viene sprecato. Lo stesso accadrebbe se le reti venissero divise fisicamente. Poiché nessuno dei metodi

tradizionali di assegnazione statica del canale funziona bene con il traffico irregolare, inizieremo a esaminare soluzioni

dinamiche.

2) Assegnazione dinamica del canale in LAN e MAN: Ci sono concetti importanti da affrontare:

 Modello della stazione . Il modello è composto da N stazioni (a volte chiamate terminali) indipendenti (es.

computer, telefoni), ognuno con un programma o utente che genera frame in trasmissione. Una volta generato,

la stazione rimane bloccata e non fa nulla fino a che il frame non è stato trasmesso con successo. Il lavoro è

frequenza costante λ.

generato a una Modelli più sofisticati ammettono stazioni multiprogrammate che possono

( l’analisi

generare lavoro mentre la stazione è bloccata è molto più complessa).

 Presupposto del canale singolo. Tutte le stazioni possono trasmettere e ricevere attraverso un solo canale assicura

ogni comunicazione. Dal punto di vista hardware tutte le stazioni sono equivalenti, ma il software di protocollo

può assegnare loro priorità diverse.

 Presupposto della collisione . Due frame trasmessi contemporaneamente si sovrappongono temporalmente e il

(è l’unico errore generato)

segnale finale risulta distorto. Questo evento è chiamato collisione e tutte le stazioni

Un frame entrato in collisione con un altro frame deve essere trasmesso un’altra volta.

possono rilevarlo. Il suo

rilevamento viene utilizzato raramente nelle reti wireless.

 Tempo: Sono possibili due ipotesi:

(a) Tempo continuo. La trasmissione di frame può iniziare in qualunque istante. Non esiste un orologio di

riferimento principale che divide il tempo in intervalli discreti.

(b) Tempo diviso in intervalli. Il tempo è diviso in intervalli discreti (slot). Un time slot è composto da n frame.

con l’inizio

La trasmissione di un frame coincide sempre di un intervallo che può contenere 0, 1 o più frame. Ci

sono vari valori, e tra essi: il primo valore rappresenta un intervallo vuoto (slot ozioso), il secondo indica uno slot

con trasmissione corretta che ha avuto successo e il terzo uno slot con collisione.

 Occupazione del canale : Abbiamo due ipotesi:

(a) Verificabile. Prima di tentare la trasmissione, le stazioni sono in grado di capire se il canale è occupato.

Fintanto che il canale rimane occupato, nessuna stazione tenterà di utilizzarlo.

(b) Non verificabile. Le stazioni non sono in grado di capire se il canale è occupato, si limitano a trasmettere il

frame. Solo successivamente possono determinare se la trasmissione ha avuto successo.

4.2 Protocolli ad accesso multiplo

Esistono molti algoritmi per assegnare un canale ad accesso multiplo:

1) ALOHA: utilizza la trasmissione radio broadcast basata su stazioni terrestri (può essere applicata a qualunque

sistema dove utenti non coordinati competono tra loro per utilizzare un singolo canale condiviso). Due versioni:

 L’idea è di

ALOHA puro: consentire a tutti gli utenti di

trasmettere ogni volta che hanno dati da inviare , cioè in

qualunque momento. Ci potranno essere collisioni che dannegge-

ranno i frame, ma grazie alla proprietà di feedback della

trasmissione broadcast(nelle LAN è immediato al contrario delle

reti satellitari), un trasmettitore potrà sempre scoprire, ascoltando

il canale, se il suo frame è andato distrutto. Si potrebbero usare

gli ack anche se c’è il rischio di intasare maggiormente il canale.

Potranno verificare l’arrivo corretto solo dopo. Il riinvio di un

frame che ha subito una collisione avviene dopo un tempo

casuale. I sistemi dove più utenti condividono un canale

comune in un modo che può causare conflitto si dicono sistemi a

contesa. Tutti i frame hanno la stessa lunghezza perché la capacità di

trasporto dei sistemi ALOHA è massima quando si utilizza un frame con

dimensione uniforme . Ogni volta che due frame tentano di occupare

contemporaneamente il canale si verifica una collisione che danneggia

entrambi gli elementi. Basta che il primo bit di un nuovo frame si

sovrapponga all’ultimo bit di un frame quasi completato, per considerarli

entrambi totalmente distrutti e quindi da ritrasmettere. Il checksum non sa

distinguere tra perdita totale e successo parziale della trasmissione. Si

consideri un gruppo infinito di utenti interattivi seduti davanti ai loro

computer (stazioni). Un utente si trova sempre in uno di due stati:

sta scrivendo oppure è in attesa. Inizialmente tutti gli utenti si tro-

vano nel primo stato, ossia stanno scrivendo. Quando termina una

riga, l’utente smette di scrivere e attende una risposta. A questo punto

la stazione trasmette un frame che contiene la riga e controlla il

canale per scoprire se la trasmissione ha avuto successo. In caso

positivo, l’utente vede apparire la risposta e ricomincia a scrivere; in

l’utente

caso negativo, continua ad aspettare e il frame è ritrasmesso

fino a quando la trasmissione non ha successo. Assumiamo inoltre

che anche in caso di blocco degli utenti il numero medio di N

frame trasmessi per tempo non diminuisca.

a. Se N > 1 vuol dire che gli utenti stanno generando una

quantità di frame superiore a quella che il canale può gestire

 collisioni continue

b. Se 0 < N < 1 riusciamo a gestire una trasmissione discreta.

Dopo un primo tentativo le varie sorgenti dovranno trasmettere sia i frame nuovi che quelli che sono andati

distrutti per colpa delle collisioni. Vecchi + Nuovi = G frame per tempo di frame (G >= N). Se t è il tempo

necessario per inviare il frame, quest’ultimo subirà una nell’intervallo di

collisione se verrà inviato un frame

tempo da t a t +t. Quando un frame viene inviato: o arriva o non arriva. Analogamente i frame inviati nel periodo

0 0

compreso tra t +t e t +2t incapperanno nella fine del frame. Si può calcolare la capacità di trasporto del canale

0 0

l’ALOHA puro. Definiamo S=G*P

(S) usando dove P è la probabilità che un frame non collida con un altro. Dal

0 0 k -G

momento che la probabilità che k frame siano generati durante un dato tempo di frame è data da Pr[k] = (G e )/k!

Dal momento che l’intervallo di tempo vulnerabile nelle collisioni è

-G

. Pr[0] = e considerando che G =1 e 0!=1.

0 -2G -2G

pari a 2t possiamo considerare un carico doppio ovvero 2G. Di conseguenza P = e e quindi S= G*e . La

0

capacità di trasporto massima è pari a S=1/(2*e) e si ha quando G=0.5. (S = 0.184 ovvero il 18%)

 Slotted ALOHA: Algoritmo a contesa sviluppato nel 1972. Il tempo è diviso in intervalli discreti (slot) e i vari

utenti si sincronizzano per concordare i limiti di ogni intervallo temporale. Prima di trasmettere ogni utente

l’inizio di un nuovo intervallo temporale

deve attendere , perciò si richiede una sincronizzazione temporale

(non c’è nell’ALOHA puro).

globale Questo accorgimento permette di dimezzare il periodo di tempo

-G

vulnerabile. Quindi S=G*e . Volendo si può calcolare il numero medio di trasmissioni necessarie prima di

inviare correttamente il frame. Dal momento che tale valore dipende in maniera esponenziale da G (sensibile al

variare di G), ogni piccola differenza nel carico risulta significativa nelle prestazioni.

2) Protocolli ad accesso multiplo con rilevamento della portante

Con slotted ALOHA si può ottenere un utilizzo massimo del canale di l/e. Fortunatamente nelle reti locali le stazioni

sono in grado di rilevare le azioni intraprese dalle altre, e adattare di conseguenza il proprio comportamento. Queste reti

possono raggiungere un livello di utilizzo maggiore di 1/e. Alcuni protocolli consentono di migliorare le prestazioni. I

protocolli in cui le stazioni rimangono in ascolto di una portante (ossia di una trasmissione) e si comportano di

conseguenza sono chiamati protocolli con rilevamento della portante (carrier sense protocol).

 CSMA persistente e non persistente

a. CSMA 1-persistente: Tra i protocolli a contesa, esiste

una particolare categoria in grado di rilevare/ascoltare

la portante, ovvero rilevare in anticipo se il canale è

occupato o meno. Funziona così: quando la stazione

deve trasmettere dati ascolta il canale:

 Se è occupato aspetta fino a che non si libera

 Se è libero trasmette

 In caso di collisione aspetta un intervallo di tempo

casuale e poi riprova a trasmettere.

È detto 1‐persistente perché la trasmissione viene

effettuata con una probabilità di 1 ogni volta che il

canale è libero. Ci possono essere le collisioni che

avvengono quando 2 utenti trasmettono in contemporanea o se il ritardo di trasmissione è molto grande.

, più diventa importante l’effetto e

Più è lungo il ritardo di propagazione peggiori le prestazioni del

protocollo. Le collisioni continuano a verificarsi anche se il ritardo di propagazione è uguale a zero. Questo

protocollo ha prestazioni migliori di quelle del sistema ALOHA puro (perché entrambe le stazioni desistono

dall’interferire con il frame della 3a stazione).

b. CSMA non persistente: Funziona come il precedente. Prima di trasmettere, ogni stazione controlla il canale: se

nessun altro sta trasmettendo inizia a inviare i dati, ma se è occupato la stazione non esegue un controllo

continuo per trasmettere subito il proprio frame, ma attende per un intervallo di tempo casuale prima di

l’algoritmo. Questo

ripetere meccanismo permette di utilizzare meglio il canale, ma allunga i ritardi.

c. CSMA p-persistente: Si applica ai canali divisi in intervalli temporali. Quando è pronta a trasmettere, ogni

stazione controlla il canale: se è libero trasmette subito con una probabilità p che varia in maniera da

e rimanda fino all’intervallo successivo – anche quell’intervallo

ottimizzare, con probabilità q = 1 p; se

la stazione trasmette oppure rimanda un’altra volta (anche in questo caso le probabilità sono p e

risulta libero, o un’altra stazione non inizia

q). Il processo si ripete fino a quando il frame non è stato trasmesso a

trasmettere; in questo caso, la stazione sfortunata attende per un intervallo di tempo casuale e poi ricomincia

(come se ci fosse stata una collisione). Se invece rileva che il canale è occupato, la stazione attende fino

all’intervallo successivo e poi applica l’algoritmo appena descritto.

 CSMA con rilevamento delle collisioni (CSMA/CD - CSMA con Collìsion Detection): Un ulteriore

miglioramento rispetto agli algoritmi precedenti consiste nel fornire la possibilità di individuare rapidamente le

interrompere tempestivamente l’invio del frame e

collisioni quando avvengono. In questo modo: Si può

risparmiare banda e tempo, aspettando un tempo casuale si può provare a ritrasmettere. Ma quanto si impiega

a rilevare una collisione? Solitamente è pari al tempo che il segnale impiega a propagarsi da una stazione

all’altra. Questo non vuol dire che dopo il tempo massimo di propagazione la stazione è sicura di non aver avuto

collisioni. Il segnale deve avere anche il tempo di tornare indietro quindi solitamente il tempo è pari 2t. Questo

protocollo è ampiamente utilizzato nel sottostrato MAC delle LAN (in particolare è la base delle LAN Ethernet).

Nel punto contrassegnato dall’etichetta

CSMA/CD utilizza il modello concettuale rappresentato nella Figura. t

Q

una stazione ha appena finito di trasmettere il suo frame ; ora qualunque altra stazione che ha un frame da

inviare può tentare di trasmettere i dati. Se due o più stazioni decidono contemporaneamente di trasmettere si

verifica una collisione. Le collisioni possono essere rilevate confrontando con il segnale trasmesso la

potenza o la larghezza d’impulso del segnale ricevuto. Se rileva una collisione, la stazione interrompe la sua

(ammesso che nessun’altra stazione abbia nel

trasmissione, attende un periodo di tempo casuale e poi ritenta

frattempo avviato la trasmissione). Perciò il modello di CSMA/CD è composto da periodi di contesa alternati a

periodi di trasmissione, con periodi inattivi che si presentano quando tutte le stazioni sono silenziose (per

della collisione è un processo analogico. L’hardware della stazione deve

mancanza di lavoro). Il rilevamento

controllare il cavo durante la propria trasmissione; se ciò che rileva non è quello che ha trasmesso, la stazione sa

L’implicazione

che è avvenuta una collisione. è che la codifica del segnale deve permettere il rilevamento

delle collisioni (es. una collisione di due segnali da 0 Volt può essere impossibile da rilevare); per questo motivo

di solito si utilizza una codifica speciale . Una stazione trasmittente deve continuamente controllare il canale ,

ascoltando i picchi di rumore che potrebbero indicare le collisioni; per questo motivo CSMA/CD su singolo

canale è intrinsecamente un sistema half

duplex. È impossibile per una stazione

trasmettere e ricevere frame nello stesso

momento, perché durante ogni trasmissione

è attiva la logica che cerca di individuare le

collisioni. Nessun protocollo del

sottostrato MAC garantisce una consegna

affidabile: anche in assenza di collisioni,

il ricevitore potrebbe copiare il frame

non correttamente per diverse ragioni

(es. per mancanza di spazio di

memorizzazione o per un interrupt perduto).

 Protocolli senza collisione: In CSMA/CD una volta acquistato il canale non si possono verificare collisioni,

tranne nella fase di contesa. Esistono per questo protocolli chiamati senza collisione in cui: le stazioni che

partecipano alla trasmissione “prenotano” in anticipo il canale in modo da non creare confusione. Un esempio è

il passaggio di token in 802.4 (token bus) e 802.5 (token ring). I protocolli:

a. Un protocollo a mappa di bit: Il protocollo inizia con un

periodo di contesa composto da N intervalli (dove N è

anche il numero di stazione). Ogni stazione ha un

intervallo di tempo in cui decide se vuole trasmettere o

no, cioè prenota il canale per dopo ponendo ad 1 il bit

relativo all’intervallo da usare. Al termine della contesa

ogni stazione sa chi vuole comunicare e chi no, e poiché

sono tutti d’accordo, non avvengono collisioni.

L’efficienza dell’algoritmo dipende dal numero di

stazioni che desiderano trasmettere: se ce ne sono molte il

periodo di contesa è distribuito proporzionalmente su N frame, se ci sono poche stazioni quelle che vorranno

Dopo che l’ultima stazione

comunicare dovranno aspettare in media N intervalli prima di comunicare.

pronta ha trasmesso il proprio frame (evento che può essere monitorato da tutte le stazioni) ha inizio un

altro periodo di contesa di N bit. Se diventa pronta quando il proprio intervallo è ormai scaduto, la stazione

deve rimanere in silenzio fino a quando tutte le altre non hanno avuto una possibilità e la mappa di bit non

ricomincia daccapo. I protocolli di questo tipo, in cui il desiderio di trasmettere è comunicato a tutti prima

di iniziare la trasmissione, si chia mano protocolli a prenotazione .

b. Conteggio binario: Il protocollo precedente non si adatta bene

a modelli con troppe stazioni. Un risultato migliore si può

ottenere con il conteggio binario che prevede che ogni stazione

abbia un indirizzo binario univoco che ne identifichi la

priorità. Indirizzi più alti indicano priorità maggiori. Se

l’indirizzo della stazione mittente viene posto ad inizio frame

l’efficienza del protocollo è massima. Quando una stazione

assegnato l’indirizzo più basso

trasmette le viene e le altre

scalano. Questa caratteristica può essere utile o svantaggiosa in rela zione al contesto applicativo. Una

stazione che desidera utilizzare il canale deve comunicare a tutti il proprio indirizzo sotto forma di stringa

binaria, partendo dal bit di ordine più elevato. Tutti gli indirizzi hanno la stessa lunghezza. I bit che occupano

l’operatore

la stessa posizione negli indirizzi di stazioni diverse sono elaborati mediante logico booleano

OR. Si presuppone implicitamente che i ritardi di trasmissione siano trascurabili, in modo che tutte le stazioni

possano vedere nello stesso momento i bit dichiarati. Per evitare conflitti si deve applicare una regola di

arbitraggio: la stazione rinuncia non appena si accorge che è stata sovrascritta da un 1 una posizione di bit di

ordine elevato che nel proprio indirizzo vale 0. Per esempio, se le stazioni 0010, 0100, 1001 e 1010 voglio no

il canale, durante il primo tempo di bit trasmettono rispettivamente 0, 0, 1 e 1; il risultato ottenuto unendo

questi valori binari mediante l’operatore logico OR è 1. Le stazioni 0010 e 0100 notano 1’1 e capiscono che

una stazione con un numero più grande sta concorrendo per il canale, perciò si ritirano dal turno corrente. Le

stazioni 1001 e 1010 inve ce vanno avanti. Il bit successivo è 0 ed entrambe continuano. Il terzo bit è 1, perciò

che ha l’indirizzo più alto,

la stazione 1001 si arrende. Il vincitore alla fine sarà 1010, perché è la stazione

quindi può trasmettere un frame, e al termine della trasmissione ricomincia un nuovo turno.

 del

Protocolli a contesa limitata: Si valutano sulla base di due fattori: il ritardo nella trasmissione e l’efficienza

canale a carico elevato. Quando il carico è leggero, ci sono poche stazioni che vogliono trasmettere:

a. I protocolli a contesa sono ottimali perché hanno un basso ritardo

b. I protocolli senza collisione invece a basso carico hanno ritardo elevato

è pesante succede esattamente l’opposto. L’idea è quella di

Quando invece il carico creare una nuova categoria

di algoritmi che sfrutti le caratteristiche positive delle due tipologie viste sopra. Protocolli che combinano le

proprietà dei due tipi di protocolli si chiamano pro tocolli a contesa limitata. In questi protocolli le stazioni

vengono divise in gruppi. Ad ogni gruppo è assegnato un intervallo temporale in cui le stazioni appartenenti

competono. Abbiamo due casi limite: 

a. Gruppi formati da una sola stazione assenza di collisioni



b. Un gruppo che contiene tutte le stazioni ALOHA

La probabilità che alcune stazioni acquisiscano il controllo del

canale può essere aumentata solo diminuendo il livello di

competizione. I protocolli a contesa limitata fanno precisamente

questo: dividono le stazioni in gruppi (non necessariamente

disgiunti); solo ai membri del gruppo 0 è permesso compe -

tere per l’intervallo 0. Se uno di loro vince , il membro

acquisisce il controllo del canale e trasmette il frame . Se

l’intervallo rimane inutilizzato o se c’è una collisione, si contendono l’intervallo 1

i membri del gruppo 1 e

così via. Dividendo le stazioni in gruppi in modo appropriato è possibile ridurre il livello di contesa per

ogni intervallo in modo da operare sempre nella parte più a sinistra del grafico mostrato nella Figura .