Hierarchical Inter-Regional Routing Algorithm for Interplanetary Networks

Le comunicazioni interplanetarie sono caratterizzate da lunghi ritardi, perdite elevate e connettività intermittente con frequenti interruzioni. Lo stack TCP/IP è inadatto nell'affrontare questo tipo di problemi. Mentre inizialmente l'unico scenario di riferimento erano le comunicazioni interplanetarie, negli anni successivi è nato il termine "Challenged Networks" per identificare le reti in cui i protocolli tradizionali falliscono. L'idea si evolve così in Delay/Disruption Tolerant Networking(DTN), con l'obiettivo di fornire una soluzione adatta alle challenged network. Tra i vari aspetti in cui le reti DTN differiscono dai protocolli TCP/IP abbiamo il modo in cui viene effettuato routing. L'attuale algoritmo di routing utilizzato proposto per le reti DTN è chiamato Contact Graph Routing(CGR). L'aspetto che contraddistingue il CGR dagli algoritmi di routing tradizionali è che esso costruisce una rotta di "contatti" (ovvero delle possibilità di comunicazione programmate), anzichè costruire un percorso di nodi. Questa caratteristica è efficace nell'ambito delle reti DTN, dove i contatti sono noti a priori. Nonostante il CGR sia molto efficiente, esso presenta dei problemi di scalabilità. Infatti, con l'aumentare del numero dei contatti, il suo tempo di esecuzione tende a crescere fino a degradare le prestazioni dell'intera rete. In questa tesi viene proposto un algoritmo di routing chiamato Hierarchical Inter-regional Routing (HIRR) che ha l'obiettivo di mitigare il problema di scalabilità del CGR dividendo i nodi della rete in diverse regioni amministrative, in cui l'utilizzo del CGR non risulta essere critico. Lo scopo principale di HIRR è quindi quello di cercare di trarre il massimo beneficio dal CGR, accettando un ragionevole compromesso fra ottimalità delle rotte e tempo di calcolo. Questa tesi è stata svolta al NASA Jet Propulsion Laboratory(JPL) situato a Pasadena in California, aderendo al Visiting Student Research Program (VSRP).