Home Notizie recenti I ricercatori scoprono un ostacolo importante nell’alleviare la congestione della rete

I ricercatori scoprono un ostacolo importante nell’alleviare la congestione della rete

29
0

Credito: CC0 Pubblico Dominio

Quando gli utenti desiderano inviare dati su Internet più velocemente di quanto la rete sia in grado di gestire, può verificarsi congestione, allo stesso modo in cui la congestione del traffico infastidisce i pendolari mattutini in una grande città.

Computer e dispositivi che trasmettono dati su Internet scompongono i dati in pacchetti più piccoli e utilizzano uno speciale algoritmo per decidere la velocità con cui inviare quei pacchetti. Questi algoritmi di controllo della congestione cercano di scoprire e utilizzare completamente la capacità di rete disponibile condividendola in modo equo con altri utenti che potrebbero condividere la stessa rete. Questi algoritmi cercano di ridurre al minimo il ritardo causato dai dati in attesa nelle code nella rete.

Negli ultimi dieci anni, i ricercatori dell’industria e del mondo accademico hanno sviluppato diversi algoritmi che tentano di raggiungere tassi elevati controllando i ritardi. Alcuni di questi, come l’algoritmo BBR sviluppato da Google, sono ora ampiamente utilizzati da molti siti Web e applicazioni.

Ma un team di ricercatori del MIT ha scoperto che questi algoritmi possono essere profondamente ingiusti. In un nuovo studio, mostrano che ci sarà sempre uno scenario di rete in cui almeno un mittente non riceve quasi nessuna larghezza di banda rispetto ad altri mittenti, un problema noto come fame non può essere evitato.

“Ciò che è davvero sorprendente di questo documento e dei risultati è che quando si tiene conto della complessità del mondo reale dei percorsi di rete e di tutte le cose che possono fare ai pacchetti di dati, è praticamente impossibile per gli algoritmi di controllo della congestione che controllano il ritardo evitare morire di fame con i metodi attuali”, afferma Mohammad Alizadeh, professore associato di ingegneria elettrica e informatica (EECS).

Sebbene Alizadeh e i suoi coautori non siano stati in grado di trovare un algoritmo di controllo della congestione tradizionale che potesse evitare la fame, potrebbero esserci algoritmi in una classe diversa che potrebbero prevenire questo problema. La loro analisi suggerisce anche che la modifica del modo in cui funzionano questi algoritmi, in modo che consentano maggiori variazioni di ritardo, potrebbe aiutare a prevenire la fame in alcune situazioni di rete.

Alizadeh ha scritto l’articolo con il primo autore e studente laureato EECS Venkat Arun e l’autore senior Hari Balakrishnan, il professore di informatica e intelligenza artificiale del Fujitsu. La ricerca sarà presentata alla conferenza dell’ACM Special Interest Group on Data Communications (SIGCOMM).

Controllo della congestione

Il controllo della congestione è un problema fondamentale nelle reti che i ricercatori hanno cercato di affrontare dagli anni ’80.

Il computer di un utente non sa quanto velocemente inviare pacchetti di dati sulla rete perché mancano di informazioni, come la qualità della connessione di rete o quanti altri mittenti stanno utilizzando la rete. L’invio di pacchetti troppo lento fa un uso scarso della larghezza di banda disponibile. Ma inviarli troppo rapidamente può sopraffare la rete e, così facendo, i pacchetti inizieranno a essere eliminati. Questi pacchetti devono essere reinviati, il che porta a ritardi più lunghi. I ritardi possono anche essere causati da pacchetti in attesa in coda per molto tempo.

Gli algoritmi di controllo della congestione utilizzano perdite e ritardi di pacchetti come segnali per dedurre la congestione e decidere la velocità di invio dei dati. Ma Internet è complicato e i pacchetti possono essere ritardati e persi per motivi estranei alla congestione della rete. Ad esempio, i dati potrebbero essere trattenuti in una coda lungo il percorso e quindi rilasciati con un’esplosione di altri pacchetti, oppure il riconoscimento del destinatario potrebbe essere ritardato. Gli autori chiamano “jitter” i ritardi che non sono causati dalla congestione.

Anche se un algoritmo di controllo della congestione misura perfettamente il ritardo, non è in grado di distinguere tra il ritardo causato dalla congestione e il ritardo causato dal jitter. Il ritardo causato dal jitter è imprevedibile e confonde il mittente. A causa di questa ambiguità, gli utenti iniziano a stimare il ritardo in modo diverso, il che fa sì che inviino pacchetti a velocità diseguali. Alla fine, questo porta a una situazione in cui si verifica la fame e qualcuno viene completamente escluso, spiega Arun.

“Abbiamo iniziato il progetto perché non avevamo una comprensione teorica del comportamento di controllo della congestione in presenza di jitter. Per collocarlo su una base teorica più solida, abbiamo costruito un modello matematico abbastanza semplice da pensare, ma in grado di catturare alcuni dei complessità di Internet. È stato molto gratificante vedere la matematica dirci cose che non sapevamo e che hanno rilevanza pratica”, afferma.

Studiare la fame

I ricercatori hanno fornito il loro modello matematico a un computer, gli hanno fornito una serie di algoritmi di controllo della congestione comunemente usati e hanno chiesto al computer di trovare un algoritmo che potesse evitare la fame, utilizzando il loro modello.

“Non potevamo farlo. Abbiamo provato tutti gli algoritmi di cui siamo a conoscenza e ne abbiamo inventati di nuovi. Niente ha funzionato. Il computer ha sempre riscontrato una situazione in cui alcune persone ottengono tutta la larghezza di banda e almeno una persona non ottiene praticamente nulla “, dice Arun.

I ricercatori sono rimasti sorpresi da questo risultato, soprattutto perché si ritiene che questi algoritmi siano ragionevolmente equi. Hanno iniziato a sospettare che potrebbe non essere possibile evitare la fame, una forma estrema di ingiustizia. Questo li ha spinti a definire una classe di algoritmi che chiamano “algoritmi convergenti di ritardo” che hanno dimostrato soffriranno sempre di fame sotto il loro modello di rete. Tutti gli algoritmi di controllo della congestione esistenti che controllano il ritardo (di cui i ricercatori sono a conoscenza) sono convergenti in ritardo.

Il fatto che tali semplici modalità di errore di questi algoritmi ampiamente utilizzati siano rimaste sconosciute per così tanto tempo illustra quanto sia difficile comprendere gli algoritmi attraverso i soli test empirici, aggiunge Arun. Sottolinea l’importanza di una solida base teorica.

Ma non tutta la speranza è persa. Sebbene tutti gli algoritmi che hanno testato abbiano fallito, potrebbero esserci altri algoritmi che non sono convergenti in termini di ritardo che potrebbero essere in grado di evitare la fame. Ciò suggerisce che un modo per risolvere il problema potrebbe essere quello di progettare algoritmi di controllo della congestione che varino l’intervallo di ritardo in modo più ampio, quindi l’intervallo è maggiore di qualsiasi ritardo che potrebbe verificarsi a causa del jitter nella rete.

“Per controllare i ritardi, gli algoritmi hanno cercato di vincolare anche le variazioni di ritardo rispetto a un equilibrio desiderato, ma non c’è nulla di sbagliato nel creare potenzialmente una maggiore variazione di ritardo per ottenere misurazioni migliori dei ritardi congestivi. È solo una nuova filosofia di progettazione che dovresti adottare”, aggiunge Balakrishnan.

Ora, i ricercatori vogliono continuare a spingere per vedere se riescono a trovare o costruire un algoritmo che eliminerà la fame. Vogliono anche applicare questo approccio di modellazione matematica e prove computazionali ad altri problemi spinosi e irrisolti nei sistemi in rete.

“Ci affidiamo sempre più ai sistemi informatici per le cose critiche e dobbiamo porre la loro affidabilità su una base concettuale più solida. Abbiamo mostrato le cose sorprendenti che puoi scoprire quando dedichi il tempo a trovare queste specifiche formali di ciò che il problema in realtà è”, afferma Alizadeh.


Questa storia è stata ripubblicata per gentile concessione di MIT News (web.mit.edu/newsoffice/), un popolare sito che copre notizie sulla ricerca, l’innovazione e l’insegnamento del MIT.

Articolo precedenteGli elettrodi microingegnerizzati potrebbero ridurre i costi di produzione delle batterie
Articolo successivoTutte le strade portano a grandi città: il modello computazionale spiega le reti di insediamenti umani