Reti di Calcolatori - Appunti parziale 3

E’

(Amministrazione attiva di Coda), algoritmi di controllo della congestione, operanti a livello di collegamento.

pesante sul dato trasferito ed è un metodo prereattivo, cioè comunica la presenza e il livello di congestione, in

modo da causare il decremento dei dati spediti dalla sorgente prima che questi causino overflow nel buffer e la

perdita di pacchetti. Questo viene implementato tramite l'utilizzo di Dynamic Buffer Limiting (DBL) che traccia la

lunghezza della coda per ogni flusso di traffico entrante su singolo ingresso del router e, quando questa eccede il suo

limite, comincia o a cancellare pacchetti o a impostare i bit Explicit Congestion Notification (ECN)

nell'intestazione dei pacchetti IP a 1. I diversi algoritmi AQM differiscono nel tipo di parametri usati come

indicatori di congestione, nella politica usata per riconoscere la congestione e per adattare la probabilità di

è l’algoritmo

cancellazione in relazione alle condizioni di congestione. Uno degli schemi più utilizzati in reti TCP/IP

Random Early Detection (indagine random anticipata). Una coda RED si comporta meglio di una Drop-Tail,

anche se le prestazioni di una rete possono essere migliorate attraverso il settaggio dei parametri.

 Random Early Detection : Venne proposto da Floyd e Jacobson nel 1993, per la prevenzione della congestione nelle

reti a commutazione di pacchetto. Il funzionamento principale è rilevare la congestione tramite il controllo della

lunghezza media della coda (Average Queue Length). Dopo averla rilevata, si può decidere di optare o per la

cancellazione, che porta alla ritrasmissione dei dati, e ha quindi il difetto di aumentare il carico di traffico, o per il

nell’intestazione

contrassegno dei pacchetti tramite un bit particolare ECN (Notifica Esplicita di Congestione) dei

pacchetti che viene settato ad uno. Questo bit viene usato dal router per informare i suoi vicini della presenza della

congestione anche se questo dipende dal protocollo di trasporto utilizzato, e ritarda la risposta della finestra TCP che

potrebbe ricevere abbastanza tardi la notifica o non riceverla (in caso di perdita del pacchetto). Generalmente i router

mantengono una lunghezza di coda relativamente bassa, per poter gestire dei periodi con traffico più consistente,

che però non possono durare per un tempo troppo lungo. Quando la lunghezza media è minore di una certa soglia

minima t (min threshold, min ), nessun pacchetto viene marcato o cancellato. Quando eccede la soglia, il

min th

router marca i pacchetti in maniera casuale con una probabilità data (packet-murking probability), che dipende:

 dal valore dell’Average Queue Length;

 dal tempo trascorso dall’ultima cancellazione;

 da un parametro: la probabilità massima di cancellazione (indicata

con p o con max ), che non deve mai essere superata.

n

Se la lunghezza media della coda è maggiore di una data soglia

massima t (max ) tutti i pacchetti in arrivo vengono cancellati o

max th

contrassegnati. RED viene proposto in due versioni: la prima è quella

classica (Figura 1). Nella gentle-version (gentile perché meno brusca),

invece, quando la lunghezza media della coda supera la soglia massima, la

probabilità di marcatura non diventa unitaria, ma continua a crescere,

anche se più velocemente rispetto a prima. Diventa unitaria solo dopo che

L’obiettivo

supera 2*max (Figura 2). è marcare pacchetti in maniera

th

abbastanza distanziata nel tempo per evitare picchi di traffico, e in maniera frequente da evitare la crescita

eccessiva della lunghezza media della coda, che cresce proporzionalmente al numero di connessioni attive nel

sistema, fino a quando non viene raggiunta la soglia massima, dopo la quale tutti i pacchetti vengono cancellati o

contrassegnati. Con RED, solitamente, si misura la lunghezza della coda in byte, invece che in pacchetti, in modo

che rifletta il ritardo medio al router. RED, inoltre, può essere modificato per assicurare che la probabilità di

marcatura sia proporzionale alla sua grandezza (un grosso pacchetto FTP ha più probabilità rispetto ad un piccolo

pacchetto TELNET), quindi tiene conto della relazione tra dimensione del pacchetto e congestione potenziale

indotta. Non reagisce alle congestioni temporanee, date da un momentaneo aumento di lunghezza della coda, ma

si riflette nell’aumento

alla congestione di lunga durata che della lunghezza media della coda, e porta alla richiesta

di decremento della finestra per alcune delle connessioni. Nonostante i difetti, la gestione dinamica e preventiva

della congestione aumenta le prestazioni della rete e risolve i problemi di Drop-Tail, e garantisce:

 L‘evitare la congestione. La rete viene costantemente monitorata e la marcatura preventiva porta ad una

minore perdita di dati, e quindi a un minor numero di pacchetti rispediti. In caso di cancellazione si ha un

immediato alleviamento della congestione, ma una ritrasmissione dei dati. In caso di contrassegno, si deve fare

sulla “onestà” dei mittenti

affidamento che decrementino la grandezza della loro finestra.

 Tempi appropriati. Dopo aver reso nota una congestione con la marcatura, occorre almeno un Round Trip Time

per vedere una diminuzione della quantità di dati in arrivo (Arrival Rate).

 L’intervallo di marcatura dipende dal livello di congestione:

Nessuna sincronizzazione globale. se è basso, il

router ha una bassa probabilità di marcare ogni pacchetto che arriva, e quando aumenta, la probabilità

aumenta. I router RED evitano la sincronizzazione globale, che può sfociare a causa di questo tentativo radicale

di eliminare la congestione, marcando meno pacchetti possibile ed elimina questo pericolo tramite la casualità

della scelta del pacchetto da cancellare o contrassegnare.

 L’algoritmo di RED può essere

Semplicità. implementato con un carico minimo nelle reti.

 Massimizzazione del potere globale (rapporto tra la velocità dei dati spediti ed il ritardo). Tramite simulazioni

si notano prestazioni migliori di RED rispetto a quelle di Drop-Tail.

 Gestione equa. Una gestione equa fa in modo di evitare la congestione, da non discriminare nessuna connessione

La quantità di pacchetti marcati per ogni connessione è proporzionale all’utilizzo che

o classe di connessione.

essa fa della larghezza di banda, controllata da meccanismi che permettono di identificare le connessioni. Non

“dell’onestà” degli utenti.

si può assicurare che ogni utente riceva stesso servizio, RED non si preoccupa

 Appropriatezza per una gran quantità di ambienti. Il meccanismo casuale di marcatura è appropriato per reti

con range di RTT diversi, larghezze di banda differenti e gran numero di connessioni attive allo stesso tempo.

C D L M D

ALCOLO ELLA UNGHEZZA EDIA ELLA CODA

I router RED utilizzano un filtro passa-basso per il calcolo della lunghezza media della coda. Anche se si verifica un

inizio di congestione o un aumento improvviso del traffico, la lunghezza media della coda non varia

considerevolmente. Questo filtro è una media dinamica pesata esponenziale: avg = (1-w ) avg+ w q. Se w è troppo

q q q

grande, il calcolo della media non può filtrare la congestione iniziale, quindi deve essere ragionevole poiché non è

desiderabile che la lunghezza media della coda avg non reagisca rapidamente. I valori min e max , dipendono dalla

th th

lunghezza media della coda che si vuole mantenere. Se si vuole un traffico molto intenso per abbastanza tempo, il

limite minimo deve essere abbastanza alto, come quando si vuole che il ritardo di un pacchetto non influenzi troppo

l’affidabilità del collegamento. Il limite massimo dipende invece dal massimo ritardo che il router è disposto ad

accettare. I router RED lavorano meglio quanto la differenza max - min è maggiore del tipico aumento della lunghezza

th th

media della coda in un RTT. Una regola quasi sempre adottata è quella di scegliere un max uguale al doppio del min .

th th

Se invece di cancellare il pacchetto, vengono impostati i bit dell’intestazione, si renderà possibile una cooperazione nella

Un’appropriata bilancia temporale permette che, dopo

prevenzione della congestione da parte degli altri router. il

marcamento, in un tempo pari al Round Trip Time (RTT), il router noti una diminuzione di velocità di arrivo dei

pacchetti. La bilancia temporale, quindi, misura il tempo di reazione alla congestione delle connessioni. La

sincronizzazione globale è da evitare, quindi si devono marcare il minor numero di pacchetti possibile. La

massimizzazione del rapporto tra larghezza di banda e ritardo globale si ottiene con il controllo della lunghezza

è più alto con l’utilizzo dei gateway RED piuttosto che di quelli con normale Drop

media della coda. Questo rapporto

Tail. I router RED non devono discriminare certe connessioni rispetto alle altre, infatti il numero di pacchetti

marcati di una connessione sarà proporzionale alla sua larghezza di banda. Cambiamenti nel traffico vengono notati

dal cambiamento della lunghezza media della coda e la velocità di marcatura è proporzionale alla quantità di congestione.

3.2.7 PI (Proportional Integral)

E’ un’evoluzione di RED e si propone di risolvere i suoi problemi. RED, infatti, mostra un legame eccessivo e dannoso

tra la lunghezza media della coda e la probabilità di marcatura dei pacchetti, e produce un errore detto steady

Con l’introduzione PI, si riesce a portare l’errore di steady state a zero.

state. del controller Infatti la lunghezza della

coda risulta essere molto più stabile. Le caratteristiche principali di PI sono:

 cercare di mantenere una data lunghezza tipo della coda considerata campione entro un certo range

 campionare la lunghezza istantanea ad intervalli precisi e calcolare la probabilità di cancellazione al k-esimo campione

Sebbene l’errore dello

Prima del PI controller, nasceva il Proportional controller. steady state venga eliminato, la velocità

di risposta diminuisce notevolmente, i ritardi di incodamento sono lunghi, grosse quantità di pacchetti vengono persi, ha

cattiva risposta alle oscillazioni di traffico nella rete, sia nei momenti in cui il numero degli utenti decresce

improvvisamente, sia in quelli in cui il numero dei flussi cresce molto rapidamente (la probabilità di marcatura aumenta

2

lentamente). Perciò è stato proposto un ulteriore algoritmo P I , combinazione di PI e Proportional controller, che risolve

il problema della risposta lenta di PI.

5 Qualità del servizio

Un insieme di pacchetti diretti da una sorgente ad una destinazione viene chiamato flusso di sessione. In una rete

connection oriented tutti i pacchetti di un flusso seguono lo stesso percorso. In una connectio