P. Brighten Godfrey
Scott Shenker
Ion Stoica
ABSTRACT
We present a new routing protocol, pathlet routing, in which networks advertise fragments of paths, called pathlets, that sources concatenate into end-to-end source routes. Intuitively, the pathlet is a highly flexible building block, capturing policy constraints as well as enabling an exponentially large number of path choices. In particular, we show that pathlet routing can emulate the policies of BGP, source routing, and several recent multipath proposals. This flexibility lets us address two major challenges for Internet routing: scalability and source-controlled routing. When a router's routing policy has only "local" constraints, it can be represented using a small number of pathlets, leading to very small forwarding tables and many choices of routes for senders. Crucially, pathlet routing does not impose a global requirement on what style of policy is used, but rather allows multiple styles to coexist. The protocol thus supports complex routing policies while enabling and incentivizing the adoption of policies that yield small forwarding plane state and a high degree of path choice.
- D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris. Resilient overlay networks. In Proc. 18th ACM SOSP, October 2001. Google Scholar
Digital Library
- Routing table report. http://thyme.apnic.net/ap-data/2009/01/05/0400/mail-global.Google Scholar
- Avaya. Converged network analyzer. http://www.avaya.com/master-usa/en-us/resource/assets/whitepapers/ef-lb2687.pdf.Google Scholar
- B. Awerbuch, D. Holmer, H. Rubens, and R. Kleinberg. Provably competitive adaptive routing. In INFOCOM, 2005.Google ScholarCross Ref
- CAIDA AS ranking. http://as-rank.caida.org/.Google Scholar
- D. Clark, J. Wroclawski, K. Sollins, and R. Braden. Tussle in cyberspace: defining tomorrow's Internet. In SIGCOMM, 2002. Google ScholarDigital Library
- X. Dimitropoulos, D. Krioukov, A. Vahdat, and G. Riley. Graph annotations in modeling complex network topologies. ACM Transactions on Modeling and Computer Simulation (to appear), 2009. Google ScholarDigital Library
- J. P. (ed.). DARPA internet program protocol specification. In RFC791, September 1981.Google Scholar
- D. Farinacci, V. Fuller, D. Meyer, and D. Lewis. Locator/ID separation protocol (LISP). In Internet-Draft, March 2009.Google Scholar
- B. Ford and J. Iyengar. Breaking up the transport logjam. In HOTNETS, 2008.Google Scholar
- L. Gao and J. Rexford. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking, 9(6):681--692, December 2001. Google ScholarDigital Library
- P. B. Godfrey, M. Caesar, I. Haken, S. Shenker, and I. Stoica. Stable Internet route selection. In NANOG 40, June 2007.Google Scholar
- T. Griffin and J. Sobrinho. Metarouting. In ACM SIGCOMM, 2005. 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 Proc. OSDI, 2004. Google ScholarDigital Library
- G. Huston. BGP routing table analysis reports, 2009. http://bgp.potaroo.net/.Google Scholar
- E. Karpilovsky and J. Rexford. Using forgetful routing to control BGP table size. In CoNEXT, 2006. Google ScholarDigital Library
- N. Kushman, S. Kandula, and D. Katabi. Can you hear me now?! it must be BGP. In Computer Communication Review, 2007. Google ScholarDigital Library
- N. Kushman, S. Kandula, D. Katabi, and B. Maggs. R-BGP: Staying connected in a connected world. In NSDI, 2007. Google ScholarDigital Library
- C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed Internet routing convergence. In ACM SIGCOMM, 2000. Google ScholarDigital Library
- K. Lakshminarayanan, I. Stoica, S. Shenker, and J. Rexford. Routing as a service. Technical Report UCB/EECS-2006-19, UC Berkeley, February 2006.Google Scholar
- Z. M. Mao, R. Bush, T. Griffin, and M. Roughan. BGP beacons. In IMC, 2003. Google ScholarDigital Library
- D. Meyer, L. Zhang, and K. Fall. Report from the iab workshop on routing and addressing. In RFC2439, September 2007.Google Scholar
- M. Motiwala, M. Elmore, N. Feamster, and S. Vempala. Path splicing. In ACM SIGCOMM, 2008. Google ScholarDigital Library
- B. Raghavan and A. C. Snoeren. A system for authenticated policy-compliant routing. In ACM SIGCOMM, 2004. Google ScholarDigital Library
- Y. Rekhter, T. Li, and S. Hares. A border gateway protocol 4 (BGP-4). In RFC4271, January 2006.Google Scholar
- E. Rosen, A. Viswanathan, and R. Callon. Multiprotocol label switching architecture. In RFC3031, January 2001. Google ScholarDigital Library
- S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, G. Voelker, and J. Zahorjan. Detour: Informed Internet routing and transport. In IEEE Micro, January 1999. Google ScholarDigital Library
- W. Xu and J. Rexford. MIRO: Multi-path Interdomain ROuting. In SIGCOMM, 2006. Google ScholarDigital Library
- X. Yang. NIRA: a new Internet routing architecture. Technical Report Ph.D. Thesis, MIT-LCS-TR-967, Massachusetts Institute of Technology, September 2004. Google ScholarDigital Library
- X. Yang, D. Clark, and A. Berger. NIRA: a new inter-domain routing architecture. IEEE/ACM Transactions on Networking, 15(4):775--788, 2007. Google ScholarDigital Library
- X. Yang and D. Wetherall. Source selectable path diversity via routing de ections. In ACM SIGCOMM, 2006. Google ScholarDigital Library
- D. Zhu, M. Gritter, and D. Cheriton. Feedback based routing. Computer Communication Review (CCR), 33(1):71--76, 2003. Google ScholarDigital Library
Index Terms
- Pathlet routing
Recommendations
Pathlet routing
SIGCOMM '09We present a new routing protocol, pathlet routing, in which networks advertise fragments of paths, called pathlets, that sources concatenate into end-to-end source routes. Intuitively, the pathlet is a highly flexible building block, capturing policy ...
BGP-XM: BGP eXtended Multipath for transit Autonomous Systems
Multipath interdomain routing has been proposed to enable flexible traffic engineering for transit Autonomos Systems (ASes). Yet, there is a lack of solutions providing maximal path diversity and backwards compatibility at the same time. The BGP-XM (...
Caching-Based Multipath Routing Protocol
CSE '09: Proceedings of the 2009 International Conference on Computational Science and Engineering - Volume 02Mobility of nodes and unreliability of wireless channel complicate the task of routing data in mobile ad hoc networks. Using multiple paths for routing instead of just one is an interesting approach to this problem, with the advantage of greater path ...
Comments