Traveling with a Pez Dispenser (or, routing issues in MPLS)

A. Gupta, A. Kumar, R. Rastogi

Research output: Contribution to journalConference articlepeer-review


MultiProtocol Label Switching (MPLS) [6, 11] is routing model proposed by the IETF for the Internet, and is becoming widely popular. In this paper, we initiate a theoretical study of the routing model, and give routing algorithms and lower bounds in a variety of situations. We first study the routing problems on the line. We then build up our results from paths through trees to more general graphs. The basic technique to go to general graphs is that of finding a tree cover, which is a small set of subtrees of the graph such that for each pair of vertices, one of the trees contains an shortest (or near-shortest) path between them. The concept of tree covers appears to have many interesting applications.

Original languageEnglish (US)
Pages (from-to)148-157
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2001
Event42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States
Duration: Oct 14 2001Oct 17 2001

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Traveling with a Pez Dispenser (or, routing issues in MPLS)'. Together they form a unique fingerprint.

Cite this