Cooperative Clustering Techniques Applied to Contact Graph Routing

Routing in the space internet has to face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this presentation we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. Finally, we propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol.