Scalability and Resiliency of Static Routing

Abstract

Computer networks rely both on physical connectivity and a routing protocol responsible for computing routing paths between all network devices. Routing answers the question of what direction each network device should send every incoming packet out. For any non-trivial network, it is not a simple question to answer. Therefore, there are many routing algorithms designed for different circumstances: from the simplest scenario of a small scale single-authority local network to the gigantic Internet scenario, where each part of the network is managed by a different entity.

In this thesis, we investigate the properties of a certain class of routing algorithms, namely static routing. Static routing algorithms are a class of algorithms that do not require a network device to store any changing state in its memory during packet processing. Despite it being one of the simplest and most constrained class of routing methods, researchers do not understand the limits of its applicability fully yet. We focus on two of the most important properties – scalability and resiliency.

For scalability, we design a static routing algorithm, which is a viable solution for the long standing problem of a scalable multicast. We theoretically and using large-scale simulations show the proposed algorithm can scale to a networks up to the size of the Internet. Thus, we prove that static routing is highly scalable.

For resiliency, we embark on a systematic algorithmic study and investigate possible resiliency levels of static routing algorithms in a variety of models: deterministic model, probabilistic model, packet-duplication model, packet-header-mutable model. We achieve a solid theoretical boundaries of resiliency that static algorithms can provide, and propose several highly resilient static routing algorithms.