Scalability and Resiliency of Static Routing

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2016-12-20
Degree programme
74 + app. 54
Aalto University publication series DOCTORAL DISSERTATIONS, 264/2016
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.
Supervising professor
Ylä-Jääski, Antti, Prof., Aalto University, Department of Computer Science, Finland
Thesis advisor
Gurtov, Andrei, Associate Prof., Linkoping University, Sweden
Lukyanenko, Andrey, Dr.
computer networks, routing algorithms, resiliency, scalability, static routing
Other note
  • [Publication 1]: Ilya Nikolaevskiy, Andrey Lukyanenko, Tatiana Polishchuk, Valentin Polishchuk, Andrei Gurtov. iSBF: Scalable In-packet Bloom Filter Based Multicast. Elsevier Computer Communications (COMCOM), vol. 70, pp. 79-85, October 2015.
    DOI: 10.1016/j.comcom.2015.05.002 View at publisher
  • [Publication 2]: Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrović, Andrei Gurtov, Aleksander Mądry, Aurojit Panda, Michael Schapira, Scott Shenker. The Quest for Resilient (Static) Forwarding Tables. In IEEE INFOCOM: International Conference on Computer Communications, San Francisco, California, USA, April 2016.
    DOI: 10.1109/INFOCOM.2016.7524552 View at publisher
  • [Publication 3]: Marco Chiesa, Andrei Gurtov, Aleksander Mądry, Slobodan Mitrović, Ilya Nikolaevskiy, Michael Schapira, and Scott Shenker. On the Resiliency of Randomized Routing Against Multiple Edge Failures. In ICALP: International Colloquium on Automata, Languages and Programming, Rome, Italy, July 2016.
    DOI: 10.4230/LIPIcs.ICALP.2016.134 View at publisher
  • [Publication 4]: Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrović, Andrei Gurtov, Aleksander Mądry, Michael Schapira, Scott Shenker. On the Resiliency of Static Forwarding Tables. Accepted for publication in IEEE/ACM Transactions on Networking (ToN), October 2016.
    DOI: 10.1109/TNET.2016.2619398 View at publisher