Path splicing

ABSTRACT

We present path splicing, a new routing primitive that allows network paths to be constructed by combining multiple routing trees ("slices") to each destination over a single network topology. Path splicing allows traffic to switch trees at any hop en route to the destination. End systems can change the path on which traffic is forwarded by changing a small number of additional bits in the packet header. We evaluate path splicing for intradomain routing using slices generated from perturbed link weights and find that splicing achieves reliability that approaches the best possible using a small number of slices, for only a small increase in latency and no adverse effects on traffic in the network. In the case of interdomain routing, where splicing derives multiple trees from edges in alternate backup routes, path splicing achieves near-optimal reliability and can provide significant benefits even when only a fraction of ASes deploy it. We also describe several other applications of path splicing, as well as various possible deployment paths.

REFERENCES

• 1: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 2: David G. Andersen , Alex C. Snoeren , Hari Balakrishnan, Best-path vs. multi-path overlay routing, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948218]
• 3: G. Apostolopoulos. Using multiple topologies for ip-only protection against network failures: A routing performance perspective. Technical Report 377, ICS-FORTH, Apr. 2006.
• 4: A. Atlas and A. Zinin. Basic Specification for IP Fast-Reroute: Loop-free Alternates. http://tools.ietf.org/html/draft-ietf-rtgwg-ipfrr-spec-base-10, Nov. 2007.
• 5: A. Broido and kc claffy. Topological Resilience in IP and AS Graphs. http://www.caida.org/analysis/topology/resilience/, 2006.
• 6: M. Cha, S. Moon, C.-D. Park, , and A. Shaikh. Placing Relay Nodes for Intra-Domain Path Diversity. In Proc. IEEE INFOCOM, Barcelona, Spain, Mar. 2006.
• 7: MPLS Traffic Engineering Fast Reroute - Link Protection. http://www.cisco.com/univercd/cc/td/doc/product/software/ios120/120newft/120limit/120st/120st16/frr.htm.
• 8: Cisco Multi-Topology Routing. http://www.cisco.com/en/US/products/ps6922/products_feature_guide09186a00807c64b8.html.
• 9: Cisco Optimized Edge Routing (OER). http://www.cisco.com/en/US/products/ps6628/products_ios_protocol_option_home.html, 2006.
• 10: X. A. Dimitropoulos, D. V. Krioukov, A. Vahdat, and G. F. Riley. Graph Annotations in Modeling Complex Network Topologies. CoRR, abs/0708.3879, 2007.
• 11: Lixin Gao , Jennifer Rexford, Stable internet routing without global coordination, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.681-692, December 2001 [doi>10.1109/90.974523]
• 12: Stein Gjessing, Implementation of two Resilience Mechanisms using Multi Topology Routing and Stub Routers, Proceedings of the Advanced Int'l Conference on Telecommunications and Int'l Conference on Internet and Web Applications and Services, p.29, February 19-25, 2006
• 13: Krishna P. Gummadi , Harsha V. Madhyastha , Steven D. Gribble , Henry M. Levy , David Wetherall, Improving the reliability of internet paths with one-hop source routing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.13-13, December 06-08, 2004, San Francisco, CA
• 14: C. Hopps, Analysis of an Equal-Cost Multi-Path Algorithm, RFC Editor, 2000
• 15: Internap. http://www.internap.com/, 2006.
• 16: N. Kushman, S. Kandula, D. Katabi, and B. M. Maggs. R-BGP: Staying connected in a connected world. In Proc. 4th USENIX NSDI, Cambridge, MA, Apr. 2007.
• 17: A. Kvalbein, A. F. Hansen, T. Cicic, S. Gjessing, and O. Lysne. Fast IP Network Recovery using Multiple Routing Configurations. In Proc. IEEE INFOCOM, pages 23--26, Barcelona, Spain, Mar. 2006.
• 18: Karthik Lakshminarayanan , Matthew Caesar , Murali Rangan , Tom Anderson , Scott Shenker , Ion Stoica, Achieving convergence-free routing using failure-carrying packets, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 19: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 20: Juniper Networks: Intelligent Logical Router Service. http://www.juniper.net/solutions/literature/white_papers/200097.pdf.
• 21: M. Motiwala, N. Feamster, and S. Vempala. Path Splicing: Reliable Connectivity with Rapid Recovery. In Proc. 6th ACM Workshop on Hot Topics in Networks (Hotnets-VI), Atlanta, GA, Nov. 2007.
• 22: R. Perlman. Network Layer Protocols with Byzantine Robustness. PhD thesis, Massachusetts Institute of Technology, Oct. 1988. MIT-LCS-TR-429. http://www.lcs.mit.edu/publications/specpub.php?id=997.
• 23: P. Psenak, S. Mirtorabi, A. Roy, L. Nguyen, and P. Pillay-Esnault. Multi-Topology Routing in OSPF. Internet Engineering Task Force, June 2007. RFC 4915.
• 24: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 25: B. Quoitin and S. Uhlig. Modeling the routing of an autonomous system with C-BGP. Network, IEEE, 19(6):12--19, 2005.
• 26: Routing Area Working Group (rtgwg). http://www.ietf.org/html.charters/rtgwg-charter.html.
• 27: M. Shand and S. Bryant. IP Fast Re-route framework. http://www3.tools.ietf.org/html/draft-ietf-rtgwg-ipfrr-framework-07, June 2007.
• 28: M. Shand and S. Bryant. IP Fast Reroute Using Not-via Addresses. http://www3.tools.ietf.org/html/draft-ietf-rtgwg-ipfrr-notvia-addresses-01, July 2007.
• 29: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 30: R. White and B. Akyol. Considerations in Validating the Path in BGP. IETF Draft, 2007.
• 31: Wen Xu , Jennifer Rexford, MIRO: multi-path interdomain routing, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 32: Xiaowei Yang , David Wetherall, Source selectable path diversity via routing deflections, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Reliability

Keywords:
multi-path routing, path diversity, path splicing