More Web Proxy on the site http://driver.im/

research-article

Free access

Pathlet routing

Authors:

P. Brighten Godfrey,

Ion StoicaAuthors Info & Claims

SIGCOMM '09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication

Pages 111 - 122

https://doi.org/10.1145/1592568.1592583

Published: 16 August 2009 Publication History

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.

References

[1]

D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris. Resilient overlay networks. In Proc. 18th ACM SOSP, October 2001.

Digital Library

[2]

Routing table report. http://thyme.apnic.net/ap-data/2009/01/05/0400/mail-global.

[3]

Avaya. Converged network analyzer. http://www.avaya.com/master-usa/en-us/resource/assets/whitepapers/ef-lb2687.pdf.

[4]

B. Awerbuch, D. Holmer, H. Rubens, and R. Kleinberg. Provably competitive adaptive routing. In INFOCOM, 2005.

[5]

CAIDA AS ranking. http://as-rank.caida.org/.

[6]

D. Clark, J. Wroclawski, K. Sollins, and R. Braden. Tussle in cyberspace: defining tomorrow's Internet. In SIGCOMM, 2002.

Digital Library

[7]

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.

Digital Library

[8]

J. P. (ed.). DARPA internet program protocol specification. In RFC791, September 1981.

[9]

D. Farinacci, V. Fuller, D. Meyer, and D. Lewis. Locator/ID separation protocol (LISP). In Internet-Draft, March 2009.

[10]

B. Ford and J. Iyengar. Breaking up the transport logjam. In HOTNETS, 2008.

[11]

L. Gao and J. Rexford. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking, 9(6):681--692, December 2001.

Digital Library

[12]

P. B. Godfrey, M. Caesar, I. Haken, S. Shenker, and I. Stoica. Stable Internet route selection. In NANOG 40, June 2007.

[13]

T. Griffin and J. Sobrinho. Metarouting. In ACM SIGCOMM, 2005.

Digital Library

[14]

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.

Digital Library

[15]

G. Huston. BGP routing table analysis reports, 2009. http://bgp.potaroo.net/.

[16]

E. Karpilovsky and J. Rexford. Using forgetful routing to control BGP table size. In CoNEXT, 2006.

Digital Library

[17]

N. Kushman, S. Kandula, and D. Katabi. Can you hear me now?! it must be BGP. In Computer Communication Review, 2007.

Digital Library

[18]

N. Kushman, S. Kandula, D. Katabi, and B. Maggs. R-BGP: Staying connected in a connected world. In NSDI, 2007.

Digital Library

[19]

C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed Internet routing convergence. In ACM SIGCOMM, 2000.

Digital Library

[20]

K. Lakshminarayanan, I. Stoica, S. Shenker, and J. Rexford. Routing as a service. Technical Report UCB/EECS-2006-19, UC Berkeley, February 2006.

[21]

Z. M. Mao, R. Bush, T. Griffin, and M. Roughan. BGP beacons. In IMC, 2003.

Digital Library

[22]

D. Meyer, L. Zhang, and K. Fall. Report from the iab workshop on routing and addressing. In RFC2439, September 2007.

[23]

M. Motiwala, M. Elmore, N. Feamster, and S. Vempala. Path splicing. In ACM SIGCOMM, 2008.

Digital Library

[24]

B. Raghavan and A. C. Snoeren. A system for authenticated policy-compliant routing. In ACM SIGCOMM, 2004.

Digital Library

[25]

Y. Rekhter, T. Li, and S. Hares. A border gateway protocol 4 (BGP-4). In RFC4271, January 2006.

[26]

E. Rosen, A. Viswanathan, and R. Callon. Multiprotocol label switching architecture. In RFC3031, January 2001.

Digital Library

[27]

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.

Digital Library

[28]

W. Xu and J. Rexford. MIRO: Multi-path Interdomain ROuting. In SIGCOMM, 2006.

Digital Library

[29]

X. Yang. NIRA: a new Internet routing architecture. Technical Report Ph.D. Thesis, MIT-LCS-TR-967, Massachusetts Institute of Technology, September 2004.

Digital Library

[30]

X. Yang, D. Clark, and A. Berger. NIRA: a new inter-domain routing architecture. IEEE/ACM Transactions on Networking, 15(4):775--788, 2007.

Digital Library

[31]

X. Yang and D. Wetherall. Source selectable path diversity via routing de ections. In ACM SIGCOMM, 2006.

Digital Library

[32]

D. Zhu, M. Gritter, and D. Cheriton. Feedback based routing. Computer Communication Review (CCR), 33(1):71--76, 2003.

Digital Library

Cited By

Krentsel ASaran NKoley BMandal SNarayanan ARatnasamy SAl-Shabibi AShaikh AShakir RSingla AWeatherspoon HSekar VYu MSeneviratne AVeitch D(2024)A Decentralized SDN Architecture for the WANProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672257(938-953)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672257
Lakshmi SDurga TSrilatha PKumari CLaxmi Lydia EAkhmetshin E(2024)Assessment of a Semi-supervised Machine Learning Method for Thwarting Network DDoS AssaultsEvolution in Signal Processing and Telecommunication Networks10.1007/978-981-97-0644-0_28(307-318)Online publication date: 23-Apr-2024
https://doi.org/10.1007/978-981-97-0644-0_28
Klenze TSprenger CBasin D(2023)IsaNet: A framework for verifying secure data plane protocolsJournal of Computer Security10.3233/JCS-22002131:3(217-259)Online publication date: 29-May-2023
https://doi.org/10.3233/JCS-220021
Show More Cited By

Index Terms

Pathlet routing
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols
  2. Network types
    1. Packet-switching networks

Recommendations

Pathlet routing
SIGCOMM '09

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 ...
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 02

Mobility 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '09: Proceedings of the ACM SIGCOMM 2009 conference on Data communication

August 2009

340 pages

ISBN:9781605585949

DOI:10.1145/1592568

General Chairs:
Pablo Rodriguez
Telefonica Research, Spain
,
Ernst Biersack
Eurecom, France
,
Program Chairs:
Konstantina Papagiannaki
Intel Labs Pittsburgh, USA
,
Luigi Rizzo
Università di Pisa, Italy

ACM SIGCOMM Computer Communication Review Volume 39, Issue 4
SIGCOMM '09
October 2009
325 pages
ISSN:0146-4833
DOI:10.1145/1594977
Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM '09

Sponsor:

SIGCOMM '09: ACM SIGCOMM 2009 Conference

August 16 - 21, 2009

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

209
Total Citations
View Citations
1,903
Total Downloads

Downloads (Last 12 months)94
Downloads (Last 6 weeks)16

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Krentsel ASaran NKoley BMandal SNarayanan ARatnasamy SAl-Shabibi AShaikh AShakir RSingla AWeatherspoon HSekar VYu MSeneviratne AVeitch D(2024)A Decentralized SDN Architecture for the WANProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672257(938-953)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672257
Lakshmi SDurga TSrilatha PKumari CLaxmi Lydia EAkhmetshin E(2024)Assessment of a Semi-supervised Machine Learning Method for Thwarting Network DDoS AssaultsEvolution in Signal Processing and Telecommunication Networks10.1007/978-981-97-0644-0_28(307-318)Online publication date: 23-Apr-2024
https://doi.org/10.1007/978-981-97-0644-0_28
Klenze TSprenger CBasin D(2023)IsaNet: A framework for verifying secure data plane protocolsJournal of Computer Security10.3233/JCS-22002131:3(217-259)Online publication date: 29-May-2023
https://doi.org/10.3233/JCS-220021
Umeda NKimura TYanai N(2023)The Juice Is Worth the Squeeze: Analysis of Autonomous System Provider Authorization in Partial DeploymentIEEE Open Journal of the Communications Society10.1109/OJCOMS.2022.32338334(269-306)Online publication date: 2023
https://doi.org/10.1109/OJCOMS.2022.3233833
Davidson AFrei MGartner MHaddadi HPerrig ANieto JWinter PWirz F(2022)Tango or square dance?Proceedings of the 21st ACM Workshop on Hot Topics in Networks10.1145/3563766.3564111(205-212)Online publication date: 14-Nov-2022
https://dl.acm.org/doi/10.1145/3563766.3564111
Luo HLiu ZZhang S(2022)Preventing DDoS Flooding Attacks With Cryptographic Path Identifiers in Future InternetIEEE Transactions on Network and Service Management10.1109/TNSM.2022.314751119:2(1690-1704)Online publication date: Jun-2022
https://doi.org/10.1109/TNSM.2022.3147511
Frei MKwon JTabaeiaghdaei SWyss MLenzen CPerrig A(2022)G-SINC: Global Synchronization Infrastructure for Network Clocks2022 41st International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS55811.2022.00021(133-145)Online publication date: Sep-2022
https://doi.org/10.1109/SRDS55811.2022.00021
Schulz LMoghadam EGarcia-Pardo JHausheer DCalvert K(2022)Supporting Dynamic Secure Interdomain Routing2022 IEEE 30th International Conference on Network Protocols (ICNP)10.1109/ICNP55882.2022.9940382(1-6)Online publication date: 30-Oct-2022
https://doi.org/10.1109/ICNP55882.2022.9940382
Blarer MKwon JGraf VPerrig A(2022)Consent Routing: Towards Bilaterally Trusted Communication Paths2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS54860.2022.00122(1247-1257)Online publication date: Jul-2022
https://doi.org/10.1109/ICDCS54860.2022.00122
Krähenbühl CTabaeiaghdaei SGloor CKwon JPerrig AHausheer DRoos DCarle GOtt J(2021)Deployment and scalability of an inter-domain multi-path routing infrastructureProceedings of the 17th International Conference on emerging Networking EXperiments and Technologies10.1145/3485983.3494862(126-140)Online publication date: 2-Dec-2021
https://dl.acm.org/doi/10.1145/3485983.3494862
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents