Il nuovo approccio alla connettività Vertex potrebbe massimizzare la larghezza di banda delle reti

Gli informatici sono costantemente alla ricerca di modi per spremere sempre più larghezza di banda dalle reti di comunicazione.

Ora un nuovo approccio alla comprensione di un concetto di base nella teoria dei grafi, noto come connettività dei vertici, potrebbe in definitiva portare a protocolli di comunicazione - le regole che governano il modo in cui vengono scambiati i messaggi digitali - che convincano quanta più larghezza di banda possibile dalle reti.

La teoria dei grafi svolge un ruolo centrale in matematica e informatica e viene utilizzata per descrivere la relazione tra diversi oggetti. Ciascun grafo è costituito da un numero di nodi, o vertici, che rappresentano gli oggetti e da linee di collegamento tra di essi, note come bordi, che indicano le relazioni tra di essi. Una rete di comunicazioni, ad esempio, può essere rappresentata come un grafico con ciascun nodo nella rete che rappresenta un vertice e una connessione tra due nodi rappresentata come un bordo.

Uno dei concetti fondamentali all'interno della teoria dei grafi è la connettività, che ha due varianti: connettività dei bordi e connettività dei vertici. Questi sono numeri che determinano quante linee o nodi dovrebbero essere rimossi da un dato grafico per disconnetterlo. Più basso è il numero di connettività di bordo o di connettività di vertice di un grafo, quindi, più facile è disconnettersi o separarsi.

In questo modo entrambi i concetti mostrano quanto sia robusta una rete contro i guasti e quanto flusso può attraversarla, che si tratti del flusso di informazioni in una rete di comunicazioni, del flusso di traffico in un sistema di trasporto o del flusso di fluidi nell'idraulica.

Ridurre il margine della connettività edge

Tuttavia, mentre è stata condotta una grande quantità di ricerca in matematica per risolvere i problemi associati alla connettività dei bordi, c'è stato relativamente poco successo nel rispondere alle domande sulla connettività dei vertici.

Ma all'ACM-SIAM Symposium on Discrete Algorithms a Portland, Oregon, a gennaio, Mohsen Ghaffari, uno studente laureato nel Laboratorio di informatica e intelligenza artificiale al MIT, presenterà una nuova tecnica per affrontare i problemi di connettività dei vertici.

Questo potrebbe in definitiva aiutarci a capire come costruire reti più robuste e più veloci, afferma Ghaffari, che ha sviluppato il nuovo approccio insieme a Keren Censor-Hillel al Technion e Fabian Kuhn all'Università di Friburgo.

Negli anni '60, i matematici William Tutte e Crispin Nash-Williams svilupparono separatamente teorie sulle strutture chiamate alberi di copertura edge-disjoint, che ora servono come uno degli strumenti tecnici chiave in molti problemi relativi alla connettività degli edge.

Uno spanning tree è un sottografo, o un grafo all'interno di un grafo, in cui tutti i nodi sono collegati dal minor numero di archi. Un insieme di alberi di copertura all'interno di un grafo sono chiamati archi disgiunti se non condividono nessuna di queste linee di collegamento.

Se una rete contiene tre spanning tree disgiunti, ad esempio, le informazioni possono fluire in parallelo lungo ciascuno di questi alberi contemporaneamente, il che significa una larghezza di banda tre volte maggiore di quella che sarebbe possibile in un grafo contenente un solo albero. Maggiore è il numero di spanning tree disgiunti dai bordi, maggiore è il flusso di informazioni, afferma Ghaffari. I risultati di Tutte e Nash-Williams mostrano che ogni grafo contiene quasi tanti spanning tree quanto la sua connettività di bordo, dice.

Ora il team ha creato una teoria analoga sulla connettività dei vertici. Lo hanno fatto suddividendo il grafico in gruppi separati di nodi, noti come insiemi dominanti connessi. Nella teoria dei grafi, un gruppo di nodi è chiamato insieme dominante connesso se tutti i vertici al suo interno sono collegati tra loro e qualsiasi altro nodo all'interno del grafo è adiacente ad almeno uno di quelli all'interno del gruppo.

In questo modo l'informazione può essere disseminata tra i nodi dell'insieme, e poi passata a qualsiasi altro nodo della rete.

Quindi, in modo simile ai risultati di Tutte e Nash-Williams per la connettività dei bordi, ogni grafo contiene quasi tanti insiemi dominanti connessi con vertici disgiunti quanto la sua connettività di vertice, dice Ghaffari.

Quindi, se pensi a un'applicazione come la trasmissione di informazioni attraverso una rete, ora possiamo scomporre la rete in molti gruppi, ognuno dei quali è un insieme dominante connesso, dice. Ciascuno di questi gruppi sarà quindi responsabile della trasmissione di una serie di messaggi e tutti i gruppi lavoreranno in parallelo per trasmettere tutti i messaggi velocemente, quasi il più velocemente possibile.

Il team ha ora sviluppato un algoritmo in grado di scomporre con attenzione una rete in molti insiemi dominanti connessi. In questo modo può strutturare le cosiddette reti wireless ad hoc, in cui i singoli nodi instradano i dati passandoli da uno all'altro per garantire la massima velocità di flusso delle informazioni. Vogliamo essere in grado di diffondere quante più informazioni possibili per unità di tempo, per creare reti sempre più veloci, dice Ghaffari. E quando un grafico ha una connettività di vertice migliore, consente un flusso [di informazioni] più ampio, aggiunge.

Applicazioni nella valutazione della robustezza

I ricercatori possono anche utilizzare il loro nuovo approccio per analizzare la robustezza di una rete contro guasti casuali. Queste nuove tecniche ci permettono anche di analizzare se è probabile che una rete rimanga connessa quando i suoi nodi falliscono casualmente con una data probabilità, dice Ghaffari. L'affidabilità contro i guasti casuali dei bordi è ben nota, ma ne sapevamo molto meno contro i guasti dei nodi, aggiunge.

Noga Alon, professore di matematica e informatica all'Università di Tel Aviv, afferma che Ghaffari ei suoi colleghi autori hanno identificato la nozione che determina il più grande flusso realizzabile quando si trasmettono messaggi utilizzando l'instradamento nelle reti di comunicazione.

L'indagine su questa nozione, insiemi dominanti connessi disgiunti ai vertici, è trattata in questo articolo da un'elegante combinazione di tecniche combinatorie, probabilistiche e algoritmiche, dice.

nascondere