Research
Theory and Practice of Interconnecting
Multiple Routing Instances
Today, a large body of research exists on the correctness of existing routing protocols. However, analytical frameworks for studying routing dynamics have mainly focused on the correctness of routing within a single routing protocol instance (e.g., RIP, OSPF or BGP). In reality, the Internet routing architecture consists of a myriad of routing protocol instances, interconnected by a set of primitives. Therefore, routing in the real world generally crosses over multiple routing protocol instances. Existing work has mostly ignored the interactions between routing protocols and the role of the interconnecting primitives.
We analyzed the routing designs of more than 1600 production networks and show that networks are oftentimes extraordinarily complex, deploying tens to hundreds of routing protocol instances at the same time (e.g., OSPF 100, OSPF 200, RIP) (Figure 1). In this compound setting, we unearthed the wide prevalence and fundamental role of the interconnecting primitives: 99% of the analyzed networks rely on them, and operators depend on the interconnecting primitives not simply to interconnect routing instances, but also as powerful tools to implement complex design objectives [1]. However, because of the lack of theoretical foundations behind their design, we prove that their usage is extremely vulnerable to routing anomalies (e.g., forwarding loops, route oscillations) [2], and that existing guidelines can still result in routing instabilities and present severe limitations in terms of desirable design objectives [3]. In addition, we provided analytical and empirical results to link the interconnecting primitives with anomalies discovered in operational networks [4]. As such, the primitives could very well be at the origins of anomalies that have been reported but that could not be explained so far. Finally, we developed a general theory for reasoning about the safety of routing across multiple routing protocol instances, and from the theory, we designed a new set of interconnecting primitives that are not only inherently safe -- ensuring safety even in the event of errors and failures -- but also more expressive than the existing version, enabling design goals that operators have expressed the desire to support but cannot today [5].
To summarize, up until now, most research effort has focused on the correctness of a single routing protocol at a time. However, we showed that ensuring the correctness of individual routing protocols is not sufficient to ensure correct routing in the Internet. Networks generally deploy multiple routing protocol instances and their interactions can also cause a wide range of anomalies.
- Franck Le, Geoffrey G. Xie, Dan Pei, Jia Wang and Hui Zhang, "Shedding Light on the Glue Logic of the Internet Routing Architecture," ACM SIGCOMM, August 2008. (.pdf) (slides)
- Franck Le, Geoffrey G. Xie, and Hui Zhang, "Understanding Route Redistribution," IEEE ICNP (International Conference on Network Protocols), October 2007. (.pdf) (slides)
- Franck Le and Geoffrey Xie, "On Guidelines for Safe Route Redistributions," ACM SIGCOMM INM (Internet Network Management) Workshop, August 2007. (.pdf)
- Franck Le, Geoffrey Xie, and Hui Zhang, "Instability Free Routing: Beyond One Protocol Instance," ACM CoNEXT, December 2008. (.pdf)
- Franck Le, Geoffrey G. Xie, and Hui Zhang, "Theory and New Primitives for Safely Connecting Routing Protocol Instances," to appear in ACM SIGCOMM, September 2010.