Pathlet routing

P. Brighten Godfrey, Igor Ganichev, Scott Shenker, Ion Stoica

Research output: Contribution to journalConference article

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.

Original languageEnglish (US)
Pages (from-to)111-122
Number of pages12
JournalComputer Communication Review
Volume39
Issue number4
DOIs
StatePublished - Nov 30 2009
EventACM SIGCOMM 2009 Conference on Data Communication, SIGCOMM 2009 - Barcelona, Spain
Duration: Aug 17 2009Aug 21 2009

Keywords

  • Design
  • Experimentation
  • Performance
  • Reliability

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Pathlet routing'. Together they form a unique fingerprint.

  • Cite this

    Godfrey, P. B., Ganichev, I., Shenker, S., & Stoica, I. (2009). Pathlet routing. Computer Communication Review, 39(4), 111-122. https://doi.org/10.1145/1594977.1592583