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

Anupam Gupta, Amit Kumar, Rajeev Rastogi

Research output: Contribution to journalArticlepeer-review


A new packet routing model proposed by the Internet Engineering Task Force, MultiProtocol Label Switching (MPLS), is discussed. Instead of each router's parsing the packet network layer header and doing its lookup based on that analysis, MPLS ensures that the analysis of the header is performed just once. This model has several advantages over conventional routing protocols, which includes reduced amount of header analysis at intermediate routers, which allows for faster switching times, and better traffic engineering capabilities and hence easier handeling of quality of service issues. MPLS protocols, and routing algorithms and lower bounds are given for a variety of situations and routing problems on the line are also studied.

Original languageEnglish (US)
Pages (from-to)453-474
Number of pages22
JournalSIAM Journal on Computing
Issue number2
StatePublished - 2005


  • Analysis of algorithms
  • Distance labeling
  • Graph separators
  • MPLS routing
  • Network routing
  • Tree covers

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this