{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:21:43Z","timestamp":1790749303077,"version":"4.1.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539702409927","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:00:22Z","timestamp":1109797222000},"page":"453-474","source":"Crossref","is-referenced-by-count":37,"title":["Traveling with a Pez Dispenser (or, Routing Issues in MPLS)"],"prefix":"10.1137","volume":"34","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Rastogi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Arias, L. J. Cowen, K. A. Laing, R. Rajaraman, and O. Taka,\n                      Compact routing with name independence\n                      , in Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, CA, ACM Press, New York, 2003, pp. 184\u2013192.","DOI":"10.1145\/777412.777442"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/35.809383"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Bar\u2010Noy, N. Linial, and D. Peleg,\n                      Compact distributed data structures for adaptive routing\n                      , in Proceedings of the Twenty\u2010First Annual ACM Symposium on Theory of Computing, Seattle, WA, ACM Press, New York, 1989, pp. 479\u2013489.","DOI":"10.1145\/73007.73053"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, S. Kutten, and D. Peleg,\n                      On buffer\u2010economical store\u2010and\u2010forward deadlock prevention\n                      , in Proceedings of the Twelfth IEEE INFOCOM, San Francisco, 1991, pp. 410\u2013414.","DOI":"10.1109\/INFCOM.1991.147532"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000088"},{"key":"R9","unstructured":"CISCO MPLS Web Page\n                      , http:\/\/www.cisco.com\/warp\/public\/732\/Tech\/mpls\/."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"R11","unstructured":"B. Davie and Y. Rekhter,\n                      MPLS: Technology and Applications\n                      , Morgan Kaufmann (Elsevier), New York, 2000."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(02)00308-0"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762113"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0218058"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/568438.568451"},{"key":"R16","unstructured":"Cyril Gavoille, David Peleg, St\u00e9phane P\u00e9rennes, Ran Raz, Distance labeling in graphs (extended abstract), SIAM, Philadelphia, PA, 2001, 210\u20132191958410"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Anupam Gupta, Amit Kumar, Rajeev Rastogi, Traveling with a Pez dispenser (or, routing issues in MPLS), IEEE Computer Soc., Los Alamitos, CA, 2001, 148\u20131571948703","DOI":"10.1109\/SFCS.2001.959889"},{"key":"R18","unstructured":"A. Gupta, A. Kumar, and R. Rastogi,\n                      Exploring the trade\u2010off between label size and stack depth in MPLS routing\n                      , in Proceedings of the Twenty\u2010Second IEEE INFOCOM, San Francisco, 2003, pp. 544\u2013554."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A. Gupta, A. Kumar, and M. Thorup,\n                      Tree based MPLS routing\n                      , in Proceedings of the Fifteenth Annual ACM symposium on Parallel Algorithms and Architectures, San Diego, CA, ACM Press, New York, 2003, pp. 193\u2013199.","DOI":"10.1145\/777412.777443"},{"key":"R20","unstructured":"MPLS Charter\n                      , http:\/\/www.ietf.org\/html.charters\/mpls\u2010charter.html."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"R22","first-page":"51","volume":"24","author":"Margulis G.","year":"1988","journal-title":"Problemy Peredachi Informatsii"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785579"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/bltj.2268"},{"key":"R25","unstructured":"Nortel MPLS Web Page\n                      , http:\/\/www.nortelnetworks.com\/corporate\/technology\/mpls\/ index.html."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"David Peleg, Proximity\u2010preserving labeling schemes and their applications, Lecture Notes in Comput. Sci., Vol. 1665, Springer, Berlin, 1999, 30\u2013411852472","DOI":"10.1007\/3-540-46784-X_5"},{"key":"R27","volume-title":"Distributed computing","author":"Peleg David","year":"2000"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"D. Peleg and E. Upfal,\n                      A trade\u2010off between space and efficiency for routing tables\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Dallas, TX, 1998, ACM Press, New York, pp. 43\u201352.","DOI":"10.1145\/62212.62217"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"E. C. Rosen, D. Tappan, Y. Rekhter, G. Federkow, D. Farinacci, T. Li, and A. Conta,\n                      MPLS Label Stack Encoding (RFC 3032)\n                      , http:\/\/www.ietf.org\/rfc\/rfc3032.txt, 2001.","DOI":"10.17487\/rfc3032"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"E. C. Rosen, A. Viswanathan, and R. Callon,\n                      MultiProtocol Label Switching Architecture (RFC 3031)\n                      , http:\/\/www.ietf.org\/rfc\/rfc3031.txt, 2001.","DOI":"10.17487\/rfc3031"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, IEEE Computer Soc., Los Alamitos, CA, 2001, 242\u20132511948712","DOI":"10.1109\/SFCS.2001.959898"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick,\n                      Approximate distance oracles\n                      , in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Crete, Greece, 2001, ACM Press, New York, pp. 183\u2013192.","DOI":"10.1145\/380752.380798"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579350"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702409927","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:24Z","timestamp":1787336304000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702409927"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539702409927"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702409927","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}