Congestione della rete - Network congestion

La congestione della rete nelle reti di dati e nella teoria delle code è la ridotta qualità del servizio che si verifica quando un nodo o un collegamento di rete trasporta più dati di quanti ne possa gestire. Gli effetti tipici includono il ritardo nell'accodamento , la perdita di pacchetti o il blocco di nuove connessioni. Una conseguenza della congestione è che un aumento incrementale del carico offerto porta solo a un piccolo aumento o addirittura a una diminuzione del throughput della rete .

I protocolli di rete che utilizzano ritrasmissioni aggressive per compensare la perdita di pacchetti dovuta alla congestione possono aumentare la congestione, anche dopo che il carico iniziale è stato ridotto a un livello che normalmente non avrebbe indotto la congestione della rete. Tali reti presentano due stati stabili allo stesso livello di carico. Lo stato stabile con bassa produttività è noto come collasso congestizio .

Le reti utilizzano tecniche di controllo della congestione e di prevenzione della congestione per cercare di evitare il collasso. Questi includono: backoff esponenziale in protocolli come CSMA / CA in 802.11 e simili CSMA / CD in originale Ethernet , finestra riduzione TCP , e Fair Queuing in dispositivi quali router e switch di rete . Altre tecniche che affrontano la congestione includono schemi di priorità che trasmettono alcuni pacchetti con priorità maggiore rispetto ad altri e l'allocazione esplicita delle risorse di rete a flussi specifici attraverso l'uso del controllo di ammissione .

Capacità di rete

Le risorse di rete sono limitate, inclusi il tempo di elaborazione del router e il throughput del collegamento . Il conflitto di risorse può verificarsi sulle reti in una serie di circostanze comuni. Una LAN wireless è facilmente riempita da un singolo personal computer. Anche su reti di computer veloci, la dorsale può essere facilmente congestionata da alcuni server e PC client. Gli attacchi Denial of Service da parte delle botnet sono in grado di riempire anche i più grandi collegamenti di rete backbone Internet , generando congestione della rete su larga scala. Nelle reti telefoniche, un evento di chiamata di massa può sopraffare i circuiti telefonici digitali.

Collasso congestizio

Il collasso congestizio (o collasso della congestione) è la condizione in cui la congestione impedisce o limita la comunicazione utile. Il collasso della congestione si verifica generalmente nei punti di strozzatura della rete, dove il traffico in entrata supera la larghezza di banda in uscita. I punti di connessione tra una rete locale e una rete geografica sono comuni strozzature. Quando una rete si trova in questa condizione, si stabilizza in uno stato stabile in cui la domanda di traffico è elevata ma è disponibile poco throughput utile, durante il quale si verificano ritardi e perdite di pacchetti e la qualità del servizio è estremamente scarsa.

Il collasso congestizio è stato identificato come un possibile problema nel 1984. È stato osservato per la prima volta su Internet nell'ottobre 1986, quando la dorsale di fase I di NSFnet è scesa di tre ordini di grandezza dalla sua capacità di 32 kbit/ sa 40 bit/s, che continuò fino a quando i nodi finali iniziarono a implementare il controllo della congestione di Van Jacobson e Sally Floyd tra il 1987 e il 1988. Quando venivano inviati più pacchetti di quanti potevano essere gestiti dai router intermedi, i router intermedi scartavano molti pacchetti, aspettandosi che i punti finali della rete ritrasmettessero il informazione. Tuttavia, le prime implementazioni TCP avevano un comportamento di ritrasmissione scadente. Quando si verificava questa perdita di pacchetti, gli endpoint inviavano pacchetti extra che ripetevano le informazioni perse, raddoppiando la velocità in entrata.

Controllo della congestione

Il controllo della congestione modula l'ingresso del traffico in una rete di telecomunicazioni al fine di evitare il collasso congestizio derivante da un eccesso di abbonamenti. Ciò si ottiene in genere riducendo la velocità dei pacchetti. Mentre il controllo della congestione impedisce ai mittenti di sopraffare la rete , il controllo del flusso impedisce al mittente di sopraffare il destinatario .

Teoria del controllo della congestione

La teoria sul controllo della congestione è stata introdotta da Frank Kelly , che ha applicato la teoria microeconomica e la teoria dell'ottimizzazione convessa per descrivere come gli individui che controllano le proprie tariffe possono interagire per ottenere un'allocazione ottimale delle tariffe a livello di rete. Esempi di allocazione ottimale del tasso sono l'allocazione equa max-min e il suggerimento di Kelly di un'allocazione proporzionalmente equa , sebbene molti altri siano possibili.

Sia la velocità del flusso , sia la capacità del collegamento e sia 1 se il flusso utilizza il collegamento e 0 altrimenti. Sia , e i vettori e la matrice corrispondenti. Sia una funzione crescente, strettamente concava , chiamata utilità , che misura il vantaggio che un utente ottiene trasmettendo a velocità . L'allocazione del tasso ottimale soddisfa quindi ${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle c_{l}}$${\displaystyle l}$${\displaystyle r_{li}}$${\displaystyle i}$${\displaystyle l}$${\displaystyle x}$${\displaystyle c}$${\displaystyle R}$${\displaystyle U(x)}$${\displaystyle x}$

${\displaystyle \max \limits _{x}\sum _{i}U(x_{i})}$

tale che ${\displaystyle Rx\leq c}$

Il duale di Lagrange di questo problema si disaccoppia, in modo che ogni flusso fissi la propria velocità, basata solo su un prezzo segnalato dalla rete. Ogni capacità di collegamento impone un vincolo, che dà luogo a un moltiplicatore di Lagrange , . La somma di questi moltiplicatori, è il prezzo a cui risponde il flusso. ${\displaystyle p_{l}}$${\displaystyle y_{i}=\sum _{l}p_{l}r_{li},}$

Il controllo della congestione diventa quindi un algoritmo di ottimizzazione distribuito. Molti attuali algoritmi di controllo della congestione possono essere modellati in questo quadro, con la probabilità di perdita o il ritardo di coda al collegamento . Una delle principali debolezze è che assegna lo stesso prezzo a tutti i flussi, mentre il controllo del flusso della finestra scorrevole causa burst che fanno sì che flussi diversi osservino perdite o ritardi diversi su un determinato collegamento. ${\displaystyle p_{l}}$${\displaystyle l}$

Classificazione degli algoritmi di controllo della congestione

Tra i modi per classificare gli algoritmi di controllo della congestione ci sono:

• Per tipologia e quantità di feedback ricevuti dalla rete: Perdita; ritardo; segnali espliciti a bit singolo o multi-bit
• Per distribuzione incrementale: solo il mittente necessita di modifiche; mittente e destinatario necessitano di modifiche; solo il router necessita di modifiche; mittente, destinatario e router necessitano di modifiche.
• Sotto l'aspetto delle prestazioni: reti di prodotti a elevato ritardo di larghezza di banda; collegamenti con perdita; equità; vantaggio per flussi brevi; link a tasso variabile
• Per criterio di equità: equità max-min; proporzionalmente equo; ritardo controllato

Mitigazione

Sono stati inventati meccanismi per prevenire la congestione della rete o per far fronte a un collasso della rete:

• Schedulatore di rete  : gestione attiva delle code che riordina o elimina selettivamente i pacchetti di rete in presenza di congestione
• Notifica esplicita di congestione  : un'estensione ai protocolli di comunicazione IP e TCP che aggiunge un meccanismo di controllo del flusso
• Controllo della congestione TCP  : varie implementazioni degli sforzi per affrontare la congestione della rete

Il comportamento corretto dell'endpoint è in genere quello di ripetere le informazioni perse, ma rallentare progressivamente la frequenza di ripetizione. A condizione che tutti gli endpoint lo facciano, la congestione si risolve e la rete riprende il comportamento normale. Altre strategie come l' avvio lento assicurano che le nuove connessioni non sovraccaricano il router prima che inizi il rilevamento della congestione.

I comuni meccanismi di prevenzione della congestione del router includono l' accodamento corretto e altri algoritmi di pianificazione e il rilevamento precoce casuale (RED) in cui i pacchetti vengono eliminati casualmente quando viene rilevata la congestione. Ciò attiva in modo proattivo gli endpoint per rallentare la trasmissione prima che si verifichi il collasso della congestione.

Alcuni protocolli end-to-end sono progettati per comportarsi bene in condizioni congestionate; TCP è un esempio ben noto. Le prime implementazioni TCP per gestire la congestione sono state descritte nel 1984, ma l'inclusione di una soluzione open source da parte di Van Jacobson nella Berkeley Standard Distribution UNIX (" BSD ") nel 1988 ha fornito per la prima volta un buon comportamento.

UDP non controlla la congestione. I protocolli costruiti su UDP devono gestire la congestione in modo indipendente. I protocolli che trasmettono a una velocità fissa, indipendentemente dalla congestione, possono essere problematici. I protocolli di streaming in tempo reale, inclusi molti protocolli Voice over IP , hanno questa proprietà. Pertanto, devono essere prese misure speciali, come la qualità del servizio, per evitare che i pacchetti cadano in presenza di congestione.

Pratico prevenzione della congestione della rete

I protocolli orientati alla connessione , come il protocollo TCP ampiamente utilizzato , controllano la perdita di pacchetti o il ritardo nell'accodamento per regolare la velocità di trasmissione. Vari processi di prevenzione della congestione della rete supportano diversi compromessi.

Prevenzione della congestione TCP/IP

L' algoritmo di prevenzione della congestione TCP è la base principale per il controllo della congestione su Internet.

I problemi si verificano quando i flussi TCP simultanei subiscono cadute di coda , specialmente quando è presente bufferbloat . Questa perdita di pacchetti ritardata interferisce con l'elusione automatica della congestione da parte del TCP. Tutti i flussi che subiscono questa perdita di pacchetti iniziano un riaddestramento TCP nello stesso momento, questa operazione è chiamata sincronizzazione globale TCP .

Gestione attiva delle code

La gestione attiva delle code (AQM) è il riordino o l'eliminazione dei pacchetti di rete all'interno di un buffer di trasmissione associato a un controller di interfaccia di rete (NIC). Questa attività viene eseguita dallo scheduler di rete .

Diagnosi precoce casuale

Una soluzione consiste nell'utilizzare il rilevamento precoce casuale (RED) sulla coda di uscita dell'apparecchiatura di rete. Sulle porte hardware di rete con più di una coda di uscita, è possibile utilizzare il rilevamento precoce casuale ponderato (WRED).

RED segnala indirettamente il mittente e il destinatario TCP eliminando alcuni pacchetti, ad es. quando la lunghezza media della coda è superiore a una soglia (ad es. 50%) e cancella linearmente o cubicamente più pacchetti, fino ad es. 100%, man mano che la coda si riempie ulteriormente.

Robusta diagnosi precoce casuale

Il robusto algoritmo di rilevamento precoce casuale (RRED) è stato proposto per migliorare il throughput TCP contro gli attacchi denial-of-service (DoS), in particolare gli attacchi denial-of-service (LDoS) a bassa velocità. Gli esperimenti hanno confermato che gli algoritmi simili a RED erano vulnerabili agli attacchi LDoS a causa delle dimensioni oscillanti della coda TCP causate dagli attacchi.

WRED . basato sul flusso

Alcune apparecchiature di rete sono dotate di porte che possono seguire e misurare ogni flusso e sono quindi in grado di segnalare un flusso di larghezza di banda troppo grande in base a una politica di qualità del servizio. Una politica potrebbe quindi dividere la larghezza di banda tra tutti i flussi in base a determinati criteri.

Notifica esplicita di congestione

Un altro approccio consiste nell'utilizzare la notifica di congestione esplicita (ECN). ECN viene utilizzato solo quando due host segnalano di volerlo utilizzare. Con questo metodo, viene utilizzato un bit di protocollo per segnalare una congestione esplicita. Questo è migliore della notifica di congestione indiretta segnalata dalla perdita di pacchetti dagli algoritmi RED/WRED, ma richiede il supporto di entrambi gli host.

Quando un router riceve un pacchetto contrassegnato come compatibile con ECN e il router prevede la congestione, imposta il flag ECN, notificando al mittente la congestione. Il mittente dovrebbe rispondere diminuendo la sua larghezza di banda di trasmissione, ad esempio, diminuendo la sua velocità di invio riducendo la dimensione della finestra TCP o con altri mezzi.

Configurazione della finestra TCP

È possibile evitare la congestione in modo efficiente riducendo il traffico. Quando un'applicazione richiede un file di grandi dimensioni, un elemento grafico o una pagina Web, di solito pubblicizza una finestra compresa tra 32K e 64K. Ciò fa sì che il server invii una finestra completa di dati (presupponendo che il file sia più grande della finestra). Quando molte applicazioni richiedono download simultanei, questi dati possono creare un punto di congestione presso un provider upstream. Riducendo l'annuncio della finestra, i server remoti inviano meno dati, riducendo così la congestione.

ECN indietro

Backward ECN (BECN) è un altro meccanismo di notifica della congestione proposto. Utilizza i messaggi di spegnimento della sorgente ICMP come meccanismo di segnalazione IP per implementare un meccanismo ECN di base per le reti IP, mantenendo le notifiche di congestione a livello IP e non richiedendo alcuna negoziazione tra gli endpoint di rete. Le notifiche di congestione efficaci possono essere propagate ai protocolli del livello di trasporto, come TCP e UDP, per gli adeguamenti appropriati.

Effetti collaterali dell'evitamento del collasso congestizio

Collegamenti radio

I protocolli che evitano il collasso congestizio generalmente presuppongono che la perdita di dati sia causata dalla congestione. Sulle reti cablate, gli errori durante la trasmissione sono rari. WiFi , 3G e altre reti con un livello radio sono suscettibili di perdita di dati a causa di interferenze e in alcuni casi potrebbero verificarsi una scarsa velocità di trasmissione. Le connessioni TCP in esecuzione su un livello fisico basato su radio vedono la perdita di dati e tendono a credere erroneamente che si stia verificando una congestione.

Connessioni di breve durata

Il protocollo di avvio lento funziona male per le connessioni brevi. I browser Web meno recenti creavano molte connessioni di breve durata e aprivano e chiudevano la connessione per ogni file. Ciò ha mantenuto la maggior parte delle connessioni in modalità di avvio lento. Le prestazioni iniziali possono essere scarse e molte connessioni non escono mai dal regime di avvio lento, aumentando significativamente la latenza. Per evitare questo problema, i browser moderni aprono più connessioni contemporaneamente o riutilizzano una connessione per tutti i file richiesti da un determinato server.

Controllo di ammissione

Il controllo di ammissione è qualsiasi sistema che richiede ai dispositivi di ricevere l'autorizzazione prima di stabilire nuove connessioni di rete. Se la nuova connessione rischia di creare congestione, l'autorizzazione può essere negata. Gli esempi includono Opportunità di trasmissione senza conflitto (CFTXOP) nello standard ITU-T G.hn per reti domestiche su cablaggio legacy, Protocollo di prenotazione delle risorse per reti IP e Protocollo di prenotazione di flusso per Ethernet .

Guarda anche

• Gestione della larghezza di banda  – Processo di misurazione e controllo delle comunicazioni su un collegamento di rete, per evitare di riempire il collegamento fino alla capacità o di sovraccaricare il collegamento
• Fallimento a cascata  – Rischio sistemico di fallimento
•  Centralina choke – Centralina telefonica progettata per gestire più tentativi di chiamata simultanei
• Erlang (unità)  – Misura del carico nelle telecomunicazioni
• Sindrome dell'apprendista stregone  – Difetto del protocollo di rete nelle versioni originali di TFTP
• Ingegneria del teletraffico  - Applicazione della teoria dell'ingegneria del traffico alle telecomunicazioni
• Thrashing  – Il computer scambia costantemente dati tra memoria e storage lasciando poca capacità per l'elaborazione produttiva
• Modellazione del traffico  – Tecnica di gestione della larghezza di banda
• Affidabilità (rete di computer)

Riferimenti

link esterno

• Floyd, S. e K. Fall, Promuovere l'uso del controllo della congestione end-to-end in Internet (Transazioni IEEE/ACM sulla rete, agosto 1999)
• Sally Floyd, On the Evolution of End-to-end Congestion Control in the Internet: An Idiosyncratic View (IMA Workshop on Scaling Phenomena in Communication Networks, October 1999) ( formato pdf )
• Termine concatenato: Accodamento
• Pierre-Francois Quet, Sriram Chellappan, Arjan Durresi, Mukundan Sridharan, Hitay Ozbay, Raj Jain, "Linee guida per l'ottimizzazione dell'ECN multilivello, utilizzando il modello TCP basato sul flusso di fluido"
• Sally Floyd, Ratul Mahajan, David Wetherall: RED-PD: RED con calo preferenziale
• Un semplice simulatore RED generico per scopi didattici di Mehmet Suzen
• Approcci al controllo della congestione nelle reti a pacchetto
• Documenti sul controllo della congestione
• Pagina iniziale di rilevamento casuale casuale
• Home page di notifica esplicita di congestione
• TFRC Homepage
• Homepage AIMD-FC
• collegamento inattivo permanente ] Simulazione del controllo della congestione TCP: ripristino rapido
• Pubblicazioni recenti su attacchi denial-of-service (DoS) a bassa frequenza