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

Fingerprint

Routing protocols
Routers
Scalability
Internet
Network protocols

Keywords

  • Design
  • Experimentation
  • Performance
  • Reliability

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

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

Pathlet routing. / Godfrey, P. Brighten; Ganichev, Igor; Shenker, Scott; Stoica, Ion.

In: Computer Communication Review, Vol. 39, No. 4, 30.11.2009, p. 111-122.

Research output: Contribution to journalConference article

Godfrey, PB, Ganichev, I, Shenker, S & Stoica, I 2009, 'Pathlet routing', Computer Communication Review, vol. 39, no. 4, pp. 111-122. https://doi.org/10.1145/1594977.1592583
Godfrey PB, Ganichev I, Shenker S, Stoica I. Pathlet routing. Computer Communication Review. 2009 Nov 30;39(4):111-122. https://doi.org/10.1145/1594977.1592583
Godfrey, P. Brighten ; Ganichev, Igor ; Shenker, Scott ; Stoica, Ion. / Pathlet routing. In: Computer Communication Review. 2009 ; Vol. 39, No. 4. pp. 111-122.
@article{c323885692954cd6ad66a03f52401814,
title = "Pathlet routing",
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.",
keywords = "Design, Experimentation, Performance, Reliability",
author = "Godfrey, {P. Brighten} and Igor Ganichev and Scott Shenker and Ion Stoica",
year = "2009",
month = "11",
day = "30",
doi = "10.1145/1594977.1592583",
language = "English (US)",
volume = "39",
pages = "111--122",
journal = "Computer Communication Review",
issn = "0146-4833",
publisher = "Association for Computing Machinery (ACM)",
number = "4",

}

TY - JOUR

T1 - Pathlet routing

AU - Godfrey, P. Brighten

AU - Ganichev, Igor

AU - Shenker, Scott

AU - Stoica, Ion

PY - 2009/11/30

Y1 - 2009/11/30

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

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

KW - Design

KW - Experimentation

KW - Performance

KW - Reliability

UR - http://www.scopus.com/inward/record.url?scp=70450237206&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70450237206&partnerID=8YFLogxK

U2 - 10.1145/1594977.1592583

DO - 10.1145/1594977.1592583

M3 - Conference article

AN - SCOPUS:70450237206

VL - 39

SP - 111

EP - 122

JO - Computer Communication Review

JF - Computer Communication Review

SN - 0146-4833

IS - 4

ER -