Tree based MPLS routing

ABSTRACT

MPLS (MultiProtocol Label Switching) is a new technology proposed by the IETF [4,10] for network routing, and is being increasingly deployed by the largest Internet service providers. The MPLS technology differs from conventional network protocols in a crucial way: instead of reading the entire packet header at all switching points, the analysis of the packet header is done just once, when the packet header is assigned a stack of labels, and thenceforth, each switching point or router just gets to look at the label at the top of the stack (and the ingress edge), and based only on this information, it has to make a decision about the next-hop node [17,16]. In another departure from conventional routing and in particular from IP source routing, where the entire packet route is explicitly put in the header and popped off along the route, the router can not only pop the top label, it can push other labels on top of the stack.The two parameters of interest in designing MPLS routing protocols are the number of labels used, and the depth of the stack used for routing. Clearly, both cannot be simultaneously minimized, and there is often an interesting trade-off between label size and stack depth: it is obvious that if k labels are used, one must have a stack depth of log_k n.In fact, it was not known whether this bound could be achieved even for trees; the best stack depth previously achieved with a constant number of labels was O(log² n). In this paper, we show that one can indeed get asymptotically optimal upper bounds and route on trees using k labels and a maximum stack depth of O(log_k n), and that this trade-off can be achieved using a simpler and more intuitive protocol than the one given in [9]. These tree-routing ideas are then shown to give better routing protocols for planar graphs as well. In particular, we show how to route along near-shortest paths (of length at most (1 + ε) times the shortest-path) with O(log² n/ε) labels and logarithmic stack depth. We also apply them to graphs with smaller separators, including most large ISP networks.

REFERENCES

• 1: Daniel O. Awduche. MPLS and traffic engineering in IP networks. IEEE Communications Magazine, December 1999.
• 2: William Cook and Paul Seymour. Tour merging via branch-decomposition. http://www.isye.gatech.edu/ wcook/, December 2002.
• 3: Lenore J. Cowen, Compact routing with minimum stretch, Journal of Algorithms, v.38 n.1, p.170-183, Jan. 2001 [doi>10.1006/jagm.2000.1134 ]
• 4: Bruce Davie , Yakov Rekhter, MPLS: technology and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 5: Anwar Elwalid, Cheng Jin, Steven H. Low, and Indra Widjaja. MATE: MPLS adaptive traffic engineering. In Proceedings IEEE INFOCOM 2001, volume 3, pages 1300--1309, 2001.
• 6: Greg N. Frederickson and Ravi Janardan. Designing networks with compact routing tables. Algorithmica, 3:171--190, 1988.
• 7: Greg N. Frederickson , Ravi Janardan, Efficient message routing in planar networks, SIAM Journal on Computing, v.18 n.4, p.843-857, Aug. 1989 [doi>10.1137/0218058]
• 8: Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001 [doi>10.1145/568438.568451]
• 9: A. Gupta , A. Kumar, Traveling with a Pez Dispenser (Or, Routing Issues in MPLS), Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.148, October 14-17, 2001
• 10: MPLS Charter. http://www.ietf.org/html.charters/mpls-charter.html.
• 11: Jirí Matousek. On embedding trees into uniformly convex Banach spaces. Israel Journal of Mathematics, 114:221--237, 1999. (Czech version in : Lipschitz distance of metric spaces, C.Sc. degree thesis, Charles University, 1990).
• 12: Debasis Mitra and K. G. Ramakrishnan. Engineering of multiservice, multipriority networks. Bell Labs Technical Journal, 6(1):139--151, 2001.
• 13: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 14: David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62217]
• 15: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006 ]
• 16: Eric C. Rosen, Dan Tappan, Yakov Rekhter, Guy Federkow, Dino Farinacci, Tony Li, and Alex Conta. MPLS label stack encoding (RFC 3032). http://www.ietf.org/rfc/rfc3032.txt, January 2001.
• 17: Eric C. Rosen, Arun Viswanathan, and Ross Callon. MultiProtocol Label Switching architecture (RFC 3031). http://www.ietf.org/rfc/rfc3031.txt, January 2001.
• 18: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 19: M. Thorup, Compact Oracles for Reachability and Approximate Distances in Planar Digraphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.242, October 14-17, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
MPLS routing, networks, routing algorithms