Xiaowei Yang
David Wetherall
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.
- D. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris. Resilient overlay networks. In SOSP, Oct. 2001. Google Scholar
Digital Library
- P. Baran. On distributed communications, vol. i. RAND Technical Report RM-3420-PR, Aug. 1964.Google Scholar
- I. Castineyra, N. Chiappa, and M. Steenstrup. The Nimrod Routing Architecture. IETF RFC 1992, Aug. 1996. Google ScholarDigital Library
- D. Clark. Policy Routing in Internetworks. Internetworking: Research and Experience, 1, 1990.Google Scholar
- D. Clark, J. Wroclawski, K. Sollins, and R. Braden. Tussle in cyberspace: Defining tomorrow's Internet. In SIGCOMM, Aug. 2002. Google ScholarDigital Library
- D. Estrin, Y. Rekhter, and S. Hotz. Scalable Inter-Domain Routing Architecture. In ACM SIGCOMM, 1992. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot. An approach to alleviate link overload as observed on an IP backbone. In INFOCOM, 2003.Google Scholar
- J. Jannotti. Network layer support for overlay networks. In IEEE OPENARCH, June 2002. Google ScholarDigital Library
- H. T. Kaur, S. Kalyanaraman, A. Weiss, S. Kanwar, and A. Gandhi. Bananas: An evolutionary framework for explicit and multipath routing in the Internet. In ACM SIGCOMM FDNA workshop, Aug. 2003. Google ScholarDigital Library
- N. Maxemchuk. Routing in the manhattan street network. IEEE Trans. on Communication, COM-35(5), May 1987.Google Scholar
- A. Medina, I. Matta, and J. Byers. BRITE: A flexible generator of Internet toplogies. Technical Report BU-CS-TR-2000-005, Boston University, 2000. Google Scholar
- R. Perlman. Network layer protocols with byzantine robustness. Technical report, MIT, Oct. 1988. MIT-LCS-TR-429.Google Scholar
- R. Perlman. Routing with byzantine robustness. Technical report, Sun Labs, Aug. 2005. TR-2005-146. Google ScholarDigital Library
- B. Raghavan and A. C. Snoeren. A System for Authenticated Policy-Compliant Routing. In ACM SIGCOMM, 2004. Google ScholarDigital Library
- E. C. Rosen, A. Viswanathan, and R. Callon. Multiprotocol label switching architecture. IETF RFC3031, Jan. 2001. Google ScholarDigital Library
- S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson. The end-to-end effects of Internet path selection. In SIGCOMM, Aug. 1999. Google ScholarDigital Library
- S. Savage, D. Wetherall, A. Karlin, and T. Anderson. Practical network support for IP traceback. In SIGCOMM, Aug. 2000. Google ScholarDigital Library
- M. Shand and S. Bryant. IP Fast Reroute Framework. IETF Routing Working Group, work in progress, Mar. 2006.Google Scholar
- N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP topologies with Rocketfuel. In SIGCOMM, Aug. 2002. Google ScholarDigital Library
- I. Stoica, S. Shenker, and H. Zhang. Core-stateless fair queueing: A scalable architecture to approximate fair bandwidth allocations in high speed networks. In SIGCOMM, 1998. Google ScholarDigital Library
- D. Thaler and C. Hopps. Multipath issues in unicast and multicast next-hop selection. IETF RFC 2991, Nov. 2000. Google ScholarDigital Library
- S. Vutukury and J. Garcia-Luna-Aceves. MDVA: A distance-vector multipath routing protocol. In IEEE Infocom, 2001.Google Scholar
Index Terms
- Source selectable path diversity via routing deflections
Recommendations
Source selectable path diversity via routing deflections
Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communicationsWe 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 ...
Path splicing
SIGCOMM '08: Proceedings of the ACM SIGCOMM 2008 conference on Data communicationWe 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 ...
An efficient algorithm to enable path diversity in link state routing networks
Multipath routing allows for load balancing and fast re-routing in order to improve the reliability and the efficiency of the network. Current IP routers only support Equal Cost MultiPath (ECMP) which guarantees that the forwarding paths do not contain ...
Comments