Efficient implementation of MPLS tables for multi-level and multi-path scenarios

#The present invention relates generally to computer networks, and specifically to routing and forwarding of data packets in such networks.

#Multiprotocol Label Switching (MPLS) is a mechanism for packet routing that is widely used in high-performance computer networks. In an MPLS network, data packets are assigned labels, and packet-forwarding decisions are made solely on the contents of the labels, without the need to examine the network address of the packet itself. The MPLS architecture and label structure were originally defined by Rosen et al. in Requests for Comments (RFCs) 3031 and 3032 of the Internet Engineering Task Force (IETF) Network Working Group (2001), which are incorporated herein by reference.

#MPLS is a network-layer protocol (Layer 3 in the Open Systems Interconnection [OSI] model), which is implemented by routers in place of or in addition to address-based routing. At the ingress to an MPLS network, a prefix is appended to the packet header, containing one or more MPLS labels. This prefix is called a label stack. According to RFC 3032, each label in the label stack contains four fields: A 20-bit label value (commonly referred to as the label identifier or “label ID”). A 3-bit traffic class field for QoS (quality of service) priority and ECN (explicit congestion notification) signaling (also referred to as the “EXP” or traffic class—“TC”—field). A 1-bit bottom-of-stack flag, which is set to indicate that the current label is the last in the stack. An 8-bit TTL (time to live) field.

#FIG. 1 is a block diagram that schematically illustrates a label-switched router, in accordance with an embodiment of the present invention; and

#FIG. 2 is a block diagram that schematically illustrates a table used in label-switched routing, in accordance with an embodiment of the present invention.

#Multi-path and multi-level scenarios are becoming increasingly common in large-scale MPLS networks. As explained above, RFC 3031 provides that each ILM or FTN record in an LSR may point to multiple entries in the NHLFE table, corresponding to multiple paths that a given packet may take. Furthermore, in many situations, a sequence of multiple labels is pushed onto a packet in an LSR (for example by the ingress router to an MPLS network), providing multiple levels of routing information, and not just a single label. For effective load balancing, it can be desirable that the sequences of labels be shuffled, i.e., each packet receives one label from a first group, and another label from a second group, and so forth, with the choice of label in each group varying from packet to packet. Thus, if each group i contains ni labels, and j labels are to be pushed in sequence onto each packet, then the number of possible different sequences is the product N=Πi=1jni. To support this many label sequence choices in a conventional MPLS router, the NHLFE table would have to contain at least N entries, each entry containing multiple labels. In a large network, tables of this size can become impractical.

#Some embodiments of the present invention that are described herein address this problem by configuring the NHLFE table as a linked list. Specifically, the NHLFE table contains at least first and second groups of entries, wherein each of the entries in the first group contains a respective pointer to at least one of the entries in the second group. When a router containing such an NHLFE table receives a data packet from the network, it selects a first entry from the first group (typically based on mapping provided by the ILM or FTN), and then follows the pointer in the first entry to select the next entry from the second group. The entries in the second set may contain pointers to a third group of entries in the NHLFE, and so forth. The router reads the labels from the linked list of entries that it has selected and pushes them onto the MPLS label stack of the data packet before forwarding the data packet to the network.

#In some cases, one or both of the first and second groups, as defined above, may contain only a single entry. In the more general case, however, each of the groups (and possibly a third and subsequent groups) may contain a large number of entries, and all of the entries in a given group may contain pointers to any or all of the entries in the next group. Even so, the size of the table will scale as the sum of the numbers of labels in all the groups, rather than the product as in the scenario described above. In other words, configuring the NHLFE table as a linked list can significantly reduce the table size and thus enhance scalability of the network. Appropriate decision logic, such as ECMP calculations, may be applied in choosing the next entry at each stage in the linked list in order to provide load balancing and/or satisfy other relevant packet routing criteria.