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

A new packet routing model proposed by the Internet Engineering Task Force, MultiProtocol Label Switching (MPLS), is discussed. Instead of each router's parsing the packet network layer header and doing its lookup based on that analysis, MPLS ensures that the analysis of the header is performed just once. This model has several advantages over conventional routing protocols, which includes reduced amount of header analysis at intermediate routers, which allows for faster switching times, and better traffic engineering capabilities and hence easier handeling of quality of service issues. MPLS protocols, and routing algorithms and lower bounds are given for a variety of situations and routing problems on the line are also studied.