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

A. Gupta; A. Kumar; R. Rastogi

doi:10.1109/sfcs.2001.959889

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

A. Gupta, A. Kumar, R. Rastogi

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	148-157
Number of pages	10
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
DOIs	https://doi.org/10.1109/sfcs.2001.959889
State	Published - 2001
Event	42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States Duration: Oct 14 2001 → Oct 17 2001

ASJC Scopus subject areas

Hardware and Architecture

Access to Document

10.1109/sfcs.2001.959889

Cite this

@article{bb82f10fd17543458f9d7ed975224a0c,

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

abstract = "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.",

author = "A. Gupta and A. Kumar and R. Rastogi",

year = "2001",

doi = "10.1109/sfcs.2001.959889",

language = "English (US)",

pages = "148--157",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "42nd Annual Symposium on Foundations of Computer Science ; Conference date: 14-10-2001 Through 17-10-2001",

}

TY - JOUR

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

AU - Gupta, A.

AU - Kumar, A.

AU - Rastogi, R.

PY - 2001

Y1 - 2001

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

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

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

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

U2 - 10.1109/sfcs.2001.959889

DO - 10.1109/sfcs.2001.959889

M3 - Conference article

AN - SCOPUS:0035167505

SN - 0272-5428

SP - 148

EP - 157

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - 42nd Annual Symposium on Foundations of Computer Science

Y2 - 14 October 2001 through 17 October 2001

ER -

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

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this