TRAVELING WITH A PEZ DISPENSER (OR, ROUTING ISSUES IN MPLS).
Saved in:
| Title: | TRAVELING WITH A PEZ DISPENSER (OR, ROUTING ISSUES IN MPLS). |
|---|---|
| Authors: | Gupta, Anupam1 anupamg@cs.cmu.edu, Kumar, Amit2 amitk@cse.iitd.ernet.in, Rastogi, Rajeev3 rastogi@research.bell-labs |
| Source: | SIAM Journal on Computing. 2005, Vol. 34 Issue 2, p453-474. 22p. |
| Subjects: | Algorithms, Quality control, Traffic engineering, Kaufmann, Morgan |
| Geographic Terms: | New York (N.Y.), New York (State) |
| Abstract: | A new packet routing model proposed by the Internet Engineering Task Force is MultiProtocol Label Switching, or MPLS [B. Davie and Y. Rekhter, MPLS: Technology and Applications, Morgan Kaufmann (Elsevier), New York, 2000]. Instead of each router's parsing the packet network layer header and doing its lookups based on that analysis (as in much of conventional packet routing), MPLS ensures that the analysis of the header is performed just once. The packet is then assigned a stack of labels, where the labels are usually much smaller than the packet headers themselves. When a router receives a packet, it examines the label at the top of the label stack and makes the decision of where the packet is forwarded based solely on that label. It can pop the top label off the stack if it so desires, and can also push some new labels onto the stack, before forwarding the packet. This scheme has several advantages over conventional routing protocols, the two primary ones being (a) reduced amount of header analysis at intermediate routers, which allows for faster switching times, and (b) better traffic engineering capabilities and hence easier handling of quality of service issues. However, essentially nothing is known at a theoretical level about the performance one can achieve with this protocol, or about the intrinsic trade-offs in its use of resources. This paper initiates a theoretical study of MPLS protocols, and routing algorithms and lower bounds are given for a variety of situations. We first study the routing problem on the line, a case which is already nontrivial, and give routing protocols whose trade-offs are close to optimality. We then extend our results for paths to trees, and thence onto more general graphs. These routing algorithms on general graphs are obtained by finding a tree cover of a graph, i.e., a small family of subtrees of the graph such that, for each pair of vertices, one of the trees in the family contains an (almost-)shortest path between them. Our results show tree covers of logarithmic size for planar graphs and graphs with bounded separators, which may be of independent interest. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 16195547 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: TRAVELING WITH A PEZ DISPENSER (OR, ROUTING ISSUES IN MPLS). – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Gupta%2C+Anupam%22">Gupta, Anupam</searchLink><relatesTo>1</relatesTo><i> anupamg@cs.cmu.edu</i><br /><searchLink fieldCode="AR" term="%22Kumar%2C+Amit%22">Kumar, Amit</searchLink><relatesTo>2</relatesTo><i> amitk@cse.iitd.ernet.in</i><br /><searchLink fieldCode="AR" term="%22Rastogi%2C+Rajeev%22">Rastogi, Rajeev</searchLink><relatesTo>3</relatesTo><i> rastogi@research.bell-labs</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2005, Vol. 34 Issue 2, p453-474. 22p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Quality+control%22">Quality control</searchLink><br /><searchLink fieldCode="DE" term="%22Traffic+engineering%22">Traffic engineering</searchLink><br /><searchLink fieldCode="DE" term="%22Kaufmann%2C+Morgan%22">Kaufmann, Morgan</searchLink> – Name: SubjectGeographic Label: Geographic Terms Group: Su Data: <searchLink fieldCode="DE" term="%22New+York+%28N%2EY%2E%29%22">New York (N.Y.)</searchLink><br /><searchLink fieldCode="DE" term="%22New+York+%28State%29%22">New York (State)</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: A new packet routing model proposed by the Internet Engineering Task Force is MultiProtocol Label Switching, or MPLS [B. Davie and Y. Rekhter, MPLS: Technology and Applications, Morgan Kaufmann (Elsevier), New York, 2000]. Instead of each router's parsing the packet network layer header and doing its lookups based on that analysis (as in much of conventional packet routing), MPLS ensures that the analysis of the header is performed just once. The packet is then assigned a stack of labels, where the labels are usually much smaller than the packet headers themselves. When a router receives a packet, it examines the label at the top of the label stack and makes the decision of where the packet is forwarded based solely on that label. It can pop the top label off the stack if it so desires, and can also push some new labels onto the stack, before forwarding the packet. This scheme has several advantages over conventional routing protocols, the two primary ones being (a) reduced amount of header analysis at intermediate routers, which allows for faster switching times, and (b) better traffic engineering capabilities and hence easier handling of quality of service issues. However, essentially nothing is known at a theoretical level about the performance one can achieve with this protocol, or about the intrinsic trade-offs in its use of resources. This paper initiates a theoretical study of MPLS protocols, and routing algorithms and lower bounds are given for a variety of situations. We first study the routing problem on the line, a case which is already nontrivial, and give routing protocols whose trade-offs are close to optimality. We then extend our results for paths to trees, and thence onto more general graphs. These routing algorithms on general graphs are obtained by finding a tree cover of a graph, i.e., a small family of subtrees of the graph such that, for each pair of vertices, one of the trees in the family contains an (almost-)shortest path between them. Our results show tree covers of logarithmic size for planar graphs and graphs with bounded separators, which may be of independent interest. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=16195547 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/S0097539702409927 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 22 StartPage: 453 Subjects: – SubjectFull: Algorithms Type: general – SubjectFull: Quality control Type: general – SubjectFull: Traffic engineering Type: general – SubjectFull: Kaufmann, Morgan Type: general – SubjectFull: New York (N.Y.) Type: general – SubjectFull: New York (State) Type: general Titles: – TitleFull: TRAVELING WITH A PEZ DISPENSER (OR, ROUTING ISSUES IN MPLS). Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Gupta, Anupam – PersonEntity: Name: NameFull: Kumar, Amit – PersonEntity: Name: NameFull: Rastogi, Rajeev IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 02 Text: 2005 Type: published Y: 2005 Identifiers: – Type: issn-print Value: 00975397 Numbering: – Type: volume Value: 34 – Type: issue Value: 2 Titles: – TitleFull: SIAM Journal on Computing Type: main |
| ResultId | 1 |
