Nel corso dell'ultimo decennio, i ricercatori del settore industriale e accademico hanno sviluppato diversi algoritmi che mirano a ottenere un'elevata velocità di elaborazione e a ridurre al minimo la latenza. Alcuni di questi, come l'algoritmo BBR sviluppato da Google, sono ora ampiamente utilizzati da numerosi siti web e applicazioni.
Un team di ricercatori del MIT ha però scoperto che questi algoritmi possono essere profondamente iniqui. In un nuovo studio, dimostrano che esisterà sempre uno scenario di rete in cui almeno un mittente riceverà una larghezza di banda quasi nulla rispetto agli altri; in altre parole, un problema noto come carenza di larghezza di banda è inevitabile.
"Ciò che è davvero sorprendente di questo lavoro e dei risultati è che, considerando la complessità dei percorsi di rete reali e tutto ciò che possono fare ai pacchetti di dati, è praticamente impossibile per gli algoritmi di controllo della congestione basati sul ritardo evitare la starvation con i metodi attuali", afferma Mohammad Alizadeh, professore associato di ingegneria elettrica e informatica (EECS).
Sebbene Alizadeh e i suoi coautori non siano riusciti a trovare un algoritmo tradizionale di controllo della congestione in grado di prevenire il blocco da parte di risorse insufficienti, è possibile che algoritmi di una classe diversa possano ovviare a questo problema. La loro analisi suggerisce inoltre che modificare il funzionamento di questi algoritmi per consentire maggiori variazioni di ritardo potrebbe contribuire a prevenire il blocco da parte di risorse insufficienti in alcune situazioni di rete.
Alizadeh ha scritto l'articolo insieme al primo autore, Venkat Arun, studente laureato in Ingegneria Elettrica e Informatica, e all'autore senior Hari Balakrishnan, professore di Informatica e Intelligenza Artificiale presso Fujitsu. La ricerca sarà presentata alla conferenza ACM Special Interest Group on Data Communications (SIGCOMM).
controllo della congestione
Il controllo della congestione è un problema fondamentale nelle reti di comunicazione che i ricercatori cercano di risolvere fin dagli anni '80.
Il computer di un utente non sa a quale velocità inviare i pacchetti di dati attraverso la rete perché non dispone di informazioni come la qualità della connessione di rete o il numero di altri mittenti che utilizzano la rete. Inviare i pacchetti troppo lentamente utilizza la larghezza di banda disponibile in modo inefficiente. Ma inviarli troppo velocemente può sovraccaricare la rete, causando la perdita di pacchetti. Questi pacchetti devono essere ritrasmessi, con conseguenti ulteriori ritardi. I ritardi possono verificarsi anche perché i pacchetti rimangono in coda per periodi prolungati.
Gli algoritmi di controllo della congestione utilizzano la perdita di pacchetti e i ritardi come segnali per dedurre la congestione e decidere la velocità di invio dei dati. Tuttavia, Internet è complesso e i pacchetti possono subire ritardi e perdite per motivi non correlati alla congestione della rete. Ad esempio, i dati potrebbero rimanere bloccati in una coda lungo il percorso e poi essere rilasciati con un flusso di altri pacchetti, oppure la conferma di ricezione da parte del destinatario potrebbe essere ritardata. Gli autori definiscono questi ritardi non correlati alla congestione "jitter".
Anche se un algoritmo di controllo della congestione misurasse perfettamente il ritardo, non sarebbe in grado di distinguere tra il ritardo causato dalla congestione e quello 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, inviando pacchetti a velocità non uniformi. A lungo andare, questo porta a una situazione in cui si verifica un blocco totale e qualcuno viene completamente escluso, spiega Arun.
"Abbiamo avviato il progetto perché ci mancava una comprensione teorica di come si comporta il controllo della congestione in presenza di jitter. Per dargli una base teorica più solida, abbiamo costruito un modello matematico abbastanza semplice da comprendere, ma in grado di cogliere alcune delle complessità di Internet. È stato molto gratificante scoprire che la matematica ci ha rivelato cose che non sapevamo e che hanno una rilevanza pratica", afferma.
Studiare la fame
I ricercatori hanno inserito il loro modello matematico in un computer, gli hanno fornito una serie di algoritmi di controllo della congestione comunemente utilizzati e gli hanno chiesto di trovare un algoritmo in grado di evitare la "soffocamento" (mancanza di risorse), utilizzando il loro modello.
"Non ci siamo riusciti. Abbiamo provato tutti gli algoritmi che conosciamo e anche alcuni nuovi che abbiamo inventato. Niente ha funzionato. Il computer trovava sempre una situazione in cui alcune persone ricevevano tutta la larghezza di banda e almeno una persona non riceveva praticamente nulla", afferma Arun.
I ricercatori sono rimasti sorpresi da questo risultato, soprattutto perché questi algoritmi sono generalmente considerati ragionevolmente equi. Hanno iniziato a sospettare che la starvation, una forma estrema di ingiustizia, potesse non essere possibile. Ciò li ha spinti a definire una classe di algoritmi che hanno chiamato "algoritmi a convergenza di ritardo", dimostrando che questi algoritmi subiranno sempre la starvation nel loro modello di rete. Tutti gli algoritmi di controllo della congestione che gestiscono il ritardo (di cui i ricercatori sono a conoscenza) sono a convergenza di ritardo.
Il fatto che modalità di fallimento così semplici di questi algoritmi ampiamente utilizzati siano rimaste sconosciute per così tanto tempo dimostra quanto sia difficile comprendere gli algoritmi basandosi esclusivamente su test empirici, aggiunge Arun. Ciò sottolinea l'importanza di una solida base teorica.
Ma non tutto è perduto. Sebbene tutti gli algoritmi testati abbiano fallito, potrebbero esistere altri algoritmi non convergenti rispetto al ritardo che possano evitare il blocco. Ciò suggerisce che una possibile soluzione al problema potrebbe essere quella di progettare algoritmi di controllo della congestione che varino l'intervallo di ritardo in modo più ampio, in modo che tale intervallo sia maggiore di qualsiasi ritardo che potrebbe verificarsi a causa delle fluttuazioni della rete.
"Per controllare i ritardi, gli algoritmi hanno anche cercato di limitare le variazioni dei ritardi attorno a un equilibrio desiderato, ma non c'è niente di male nel creare potenzialmente maggiori variazioni di ritardo per ottenere misurazioni più precise dei ritardi dovuti alla congestione. Si tratta semplicemente di una nuova filosofia di progettazione che dovrebbe essere adottata", aggiunge Balakrishnan.
Ora, i ricercatori vogliono continuare a impegnarsi per vedere se riescono a trovare o a costruire un algoritmo che elimini il problema della fame. Vogliono anche applicare questo approccio di modellazione matematica e test computazionali ad altri problemi spinosi e irrisolti nei sistemi in rete.
"Dipendiamo sempre di più dai sistemi informatici per attività di fondamentale importanza, e la loro affidabilità deve avere una base concettuale più solida. Abbiamo dimostrato le sorprendenti scoperte che si possono fare quando si dedica tempo allo sviluppo di specifiche formali che definiscano con precisione la natura del problema", afferma Alizadeh.
###
Articolo di Adam Zewe, Ufficio Stampa del MIT
