Exploring the Trade-Off Between Label Size and Stack Depth in MPLS Routing

Multiprotocol Label Switching or MPLS technology is being increasingly deployed by several of the largest Internet service providers to solve problems such as traffic engineering and to offer IP services like virtual private networks. In MPLS, the analysis of the packet (network layer) header is performed just once, and causes the packet to be assigned a stack of labels, where the labels are usually much smaller than the packet headers themselves. At each subsequent hop, the router examines the label at the the top of the label stack, and makes the decision for the next hop based solely on that label. It can then pop this label off the stack if it so desires, and push on zero or more labels onto the stack, before sending it on its merry way. Despite the fact that MPLS is becoming widespread on the Internet, we know essentially very little at a theoretical level about the performance one can achieve with it, and about the intrinsic trade-offs in its use of resources. In this paper, we undertake a comprehensive theoretical study of the label size versus stack depth trade-off for MPLS routing protocols on lines and trees. Specifically, we develop routing algorithms and prove lower bounds for two basic problems: (1) Fixed Label Routing: Given a fixed number of labels, we want to minimize the stack depth, and (2) Fixed Depth Routing: Given a bound on the stack depth, we want to minimize the number of labels used. Our simulation results validate our approach, demonstrating that our novel protocols enable MPLS routing on large trees with few labels and small stack sizes.