Source selectable path diversity via routing deflections

ABSTRACT

We present the design of a routing system in which end-systems set tags to select non-shortest path routes as an alternative to explicit source routes. Routers collectively generate these routes by using tags as hints to independently deflect packets to neighbors that lie off the shortest-path. We show how this can be done simply, by local extensions of the shortest path machinery, and safely, so that loops are provably not formed. The result is to provide end-systems with a high-level of path diversity that allows them to bypass unde-sirable locations within the network. Unlike explicit source routing, our scheme is inherently scalable and compatible with ISP policies because it derives from the deployed Internet routing. We also sug-gest an encoding that is compatible with common IP usage, making our scheme incrementally deployable at the granularity of individual routers.

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: P. Baran. On distributed communications, vol. i. RAND Technical Report RM-3420-PR, Aug. 1964.
• 3: I. Castineyra , N. Chiappa , M. Steenstrup, The Nimrod Routing Architecture, RFC Editor, 1996
• 4: D. Clark. Policy Routing in Internetworks. Internetworking: Research and Experience, 1, 1990.
• 5: David D. Clark , John Wroclawski , Karen R. Sollins , Robert Braden, Tussle in cyberspace: defining tomorrow's internet, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: Deborah Estrin , Yakov Rekhter , Steven Hotz, Scalable inter-domain routing architecture, Conference proceedings on Communications architectures & protocols, p.40-52, August 17-20, 1992, Baltimore, Maryland, United States
• 7: K. P. Gummadi, H. V. Madhyastha, S. D. Gribble, H. M. Levy, and D. Wetherall. Improving the reliability of internet paths with one-hop source routing. In OSDI, Dec. 2004.
• 8: S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot. An approach to alleviate link overload as observed on an IP backbone. In INFOCOM, 2003.
• 9: John Jannotti , M. Frans Kaashoek, Network layer support for overlay networks, 2002
• 10: H. Tahilramani Kaur , S. Kalyanaraman , A. Weiss , S. Kanwar , A. Gandhi, BANANAS: an evolutionary framework for explicit and multipath routing in the internet, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany
• 11: N. Maxemchuk. Routing in the manhattan street network. IEEE Trans. on Communication, COM-35(5), May 1987.
• 12: Alberto Medina , Ibrahim Matta , John Byers, BRITE: A Flexible Generator of Internet Topologies, Boston University, Boston, MA, 2000
• 13: R. Perlman. Network layer protocols with byzantine robustness. Technical report, MIT, Oct. 1988. MIT-LCS-TR-429.
• 14: R. Perlman. Routing with byzantine robustness. Technical report, Sun Labs, Aug. 2005. TR-2005-146.
• 15: Barath Raghavan , Alex C. Snoeren, A system for authenticated policy-compliant routing, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 16: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 17: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 18: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Practical network support for IP traceback, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.295-306, August 28-September 01, 2000, Stockholm, Sweden
• 19: M. Shand and S. Bryant. IP Fast Reroute Framework. IETF Routing Working Group, work in progress, Mar. 2006.
• 20: 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
• 21: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 22: D. Thaler , C. Hopps, Multipath Issues in Unicast and Multicast Next-Hop Selection, RFC Editor, 2000
• 23: S. Vutukury and J. Garcia-Luna-Aceves. MDVA: A distance-vector multipath routing protocol. In IEEE Infocom, 2001.

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

Keywords:
path diversity, routing deflections, source routin