Algebraic Analysis of Routing Protocols: Theory and Applications (AARP)

Tutorial Program

The tutorial has an associated Slack channel for discussions. Click on the link below to visit it. If you're asked to sign in, use the workspace name "sigcomm.slack.com" to sign up or sign in.

Go to tutorial Slack channel

Call For Participation

This tutorial features an algebraic theory of routing as a unified framework to reason about routing protocols. The theory establishes nexuses between routing metrics and routing policies, on the one hand, and protocol behaviors, on the other. It informs the design and configuration of routing protocols and explains away undesirable or otherwise counter-intuitive behaviors that these protocols sometimes exhibit, such as non-termination, non-optimality, forwarding loops, traffic black holes, and packet deflections. Presently, the theory underlies methods for the verification of routing configurations and provides abstractions for the specification and design of programmable control and data planes.

The tutorial presents the main principles, results, algorithms, and subtleties of the algebraic theory of routing in a clear and intuitive way. The invitation to the tutorial extends to researchers, practitioners, educators, and students in computer networking, even if they are not experts on routing. Researchers are exposed to an intellectual tool to help design new routing systems; practitioners may complement their know-how with a handful of high-level insights about routing protocols; educators may see an opportunity to teach routing from first principles; and students get an articulated overview of routing protocols.

Important Dates

• August 14, 2020

  Tutorial

Background

Algebraic theory of routing is an expression given to a framework of an algebraic nature to reason about routing algorithms and protocols from first principles. The theory emerges from the key observation that at a certain level of abstraction routing protocols can be described in common terms: they all perform iterations of selection and extension operations on attributes at the nodes of a network. Attributes represent metrics and parameters that are relevant in a given routing context; a selection operation retains one attribute from a pair of attributes and discards the other; and an extension operation transforms the attribute of a path into that of another path containing more links. At this level of abstraction, routing protocols differ on how selection and extension operations on attributes are distributed among the nodes and interleaved at a node. The fundamental insight obtained from the theory is that important global behaviors exhibited by any given class of routing protocols are determined by the algebraic properties of the selection operation, of the extension operation, and of the entwinement between these two operations. Put differently, important global behaviors of any specific routing protocol can be predicted from a few algebraic properties identified among its many configuration options and implementation details.

Outline

The tutorial is organized in six parts as follows:

• Why a theory for routing protocols (15 minutes): The necessity of a solid framework to reason about routing protocols is motivated with the presentation of undesirable and counter-intuitive behaviors exhibited by current routing protocols: BGP and the possibility of non-termination; EIGRP and non-optimal paths; administrative distances and forwarding loops; Babel and traffic black holes. At the same time, the possibility of a unified treatment for routing protocols is argued from the fact that they all perform iterations of common elementary operations.

• Routing algebra and optimality (60 minutes): The concept of routing algebra is presented as a set of attributes, a binary selection operation on attributes and a binary extension operation on attributes, together with a basic set of algebraic properties for these operations. The selection operation is equivalently described by a total order on attributes. Multiple examples of routing algebras are given representing various performance metrics both in wired and wireless networks. We show that non-restarting vectoring protocols, such as BGP and EIGRP, do not solve the problem of optimal path routing, in general. Instead, they solve the problem of optimal path routing constrained to a destination-based forwarding strategy. If the routing algebra satisfies the algebraic property of left-isotonicity, then non-restarting vectoring protocols do solve the problem of (unconstrained) optimal path routing. We further show that, contrarily to a non-restarting vectoring protocol, a restarting vectoring protocol, such as Babel, requires left-isotonicity for correct delivery of data-packets and a link-state protocol, such as OSPF, requires both left- and right-isotonicity for correct delivery of data-packets, in which case both these classes of protocols route on optimal paths.

• Relaxation of algebraic properties (15 minutes): Some of the properties that were assumed in the definition of a routing algebra are not satisfied in relevant routing contexts. We show that the Multi-Exit-Discriminator (MED) parameter of BGP may lead to a violation of the associativity of the selection operation; that the routing loop detection capability of BGP violates the associativity of the extension operation; and that the configuration of administrative distances may break inflation (also called monotonicity), which is an algebraic property entwining the total order and the extension operation on attributes. The last two cases prompt the generalization of a routing algebra presented next.

• Routing algebra with maps and protocol termination (60 minutes): For vectoring protocols, the concept of routing algebra is generalized by modeling extension operations with maps on attributes rather than with a binary extension operation on them. Furthermore, contrarily to a routing algebra, the maps on attributes are not assumed to be inflationary. The concept of routing algebra with maps leads, in particular, to an algebraic model for BGP. The problem of non-termination of vectoring protocols is illustrated with realistic inter-domain routing policies. Strict virtuousness is presented as the algebraic property on network cycles that is both sufficient and necessary for termination of vectoring protocols. A connection is made between the algebraic analysis of routing protocols and game theory: we show that BGP aims to solve the problem of finding the Nash equilibria of a suitably defined game.

• Routing algebra with sets and multiple optimality criteria (20 minutes): The problem mentioned earlier of vectoring protocols routing non-optimally in the absence of the algebraic property of isotonicity can be solved by subsuming the total order on attributes under a partial order on them that satisfies isotonicity. The broader problem of routing simultaneously on a multiplicity of optimality criteria is also solvable with a partial order on attributes that, besides satisfying isotonicity, is contained in the total orders associated with the various criteria. The concept of routing algebra is generalized to partial orders, with a selection operation on sets of attributes rather than on (single) attributes. Vectoring protocols, both non-restarting and restarting, are presented that compute according to a selection operation on sets of attributes, electing and advertising multiple attributes per destination.

• Conclusions and bibliography (10 minutes): Main conclusions are presented and a guided tour of the bibliography is provided.

Audience Expectations and Prerequisites

The only prerequisites for attending the tutorial are knowledge of routing protocols at the level of an undergraduate course in computer networks and a predisposition to deductive reasoning. The algebraic constructs themselves are simple, if unusual outside a routing frame of reference.

Organizer

• João Luís Sobrinho

  ULisboa, Inst. de Telecomunicações, Portugal

  • Bio: João Luís Sobrinho is a Professor with the Department of Electrical and Computer Engineering of Instituto Superior Técnico at the University of Lisbon, Portugal, and a senior researcher at Instituto de Telecomunicações, a private not-for-profit organization researching in the field of Telecommunications. Prior to joining the University of Lisbon in 1997, he was a member of the Technical Staff at Bell Labs for two years. Building trustworthy networks based on solid principles has long been João Sobrinho’s general interest. As part of that interest, his research is currently focused on routing for packet-switching networks, data-centers, and the Internet. He was one of the first researchers to cast the operation of routing protocols on an algebraic framework. He authored scientific papers in selective journals and conferences of his field of inquiry and is an inventor in six patents. His research work was recognized with an International IEEE Communications Society `William R. Bennett Prize in the Field of Communications Networking' (2006) and an IRTF `Applied Networking Research Prize' (2015).

References

1. Anubhavnidhi Abhashkumar, Aaron Gember-Jacobson, and Aditya Akella. 2020. Tiramisu: Fast Multilayer Network Verification. In Proc. USENIX NSDI.

2. Ryan Beckett, Aarti Gupta, Ratul Mahajan, and David Walker. 2020. Abstract Interpretation of Distributed Network Control Planes. In Proc. ACM POPL.

3. Ashley Flavel and Matthew Roughan. 2009. Stable and Flexible iBGP. In Proc. ACM SIGCOMM.

4. Michel Gondran and Michel Minoux. 2008. Graphes, Dioides, and Semirings. Springer. ISBN 978-0-387-75449-9.

5. Kuo-Feng Hsu, Ryan Beckett, Ang Chen, Jennifer Rexford, Praveen Tammana, and David Walker. 2020. Contra: A Programmable System for Performance-Aware Routing. In Proc. USENIX NSDI.

6. Franck Le and Geoffrey G. Xie. 2007. On Guidelines for Safe Route Redistributions. In Proc. ACM SIGCOMM Workshop on Internet Network Management.

7. Yong Liao, Lixin Gao, Roch Guérin, and Zhi-Li Zhang. 2010. Safe Interdomain Routing Under Diverse Commercial Agreements. IEEE/ACM Transactions on Networking 18, 6 (2010).

8. Nuno Lopes and Andrey Rybalchenko. 2019. Fast BGP Simulation of Large Data Centers. In Proc. VMCAI.

9. João L. Sobrinho. 2005. An Algebraic Theory of Dynamic Network Routing. IEEE/ACM Transactions on Networking 13, 5 (2005).

10. João L. Sobrinho and Timothy Griffin. 2010. Routing in Equilibrium. In Proc. International Symposium on the Mathematical Theory of Networks and Systems.

11. João L. Sobrinho. 2017. Correctness of Routing Vector Protocols as a Property of Network Cycles. IEEE/ACM Transactions on Networking 25, 1 (2017).