Technique for avoiding IP lookup with multipoint-to-multipoint label switched paths

BACKGROUND OF THE INVENTION

00011. Field of the Invention

0002The present invention relates to computer networks and more particularly to avoiding Internet Protocol (IP) lookup with Multipoint-to-Multipoint (MP2MP) Label Switched Paths (LSPs) in a computer network.

00032. Background Information

0004A computer network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end nodes, such as personal computers and workstations. Many types of networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect the nodes over dedicated private communications links located in the same general physical location, such as a building or campus. WANs, on the other hand, typically connect geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines, optical lightpaths, synchronous optical networks (SONET), or synchronous digital hierarchy (SDH) links. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other.

0005The data packets transferred among the network nodes may include fixed-sized data cells and/or variable-sized data frames. Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate network nodes, such as routers, to route the packet efficiently through the computer network. Often, a packet's network headers include at least a data-link (layer 2) header and an internetwork (layer 3) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.

0006In operation, a network node may send a data packet to a network interface of an intermediate network node. Thereafter, the intermediate network node receives the packet and forwards the packet to its next destination. For example, the intermediate is network node may perform a layer-2 switching function that simply re-directs the packet from one network interface to another based on the contents of the packet's data-link header. Alternatively, the intermediate network node may perform a layer-3 routing function, or forwarding decision, that selects the most appropriate network interface to forward the packet based on the contents of the packet's internetwork header.

0007A source node (sender) may be configured to transfer a unidirectional stream of data packets, or a “data flow,” to a destination node (receiver) in a data network. The data stream is unidirectional in that data travels one-way from the sender to the receiver. The logical procession of intermediate network nodes that transmit and receive data packets from the sender to the receiver defines the data stream's data path. A first node that is nearer the receiver in the data stream's data path than a second node in the stream is said to be “downstream” from the second node. Likewise, a first node that is nearer the sender in the data stream's path than a second node in the stream is said to be “upstream” from the second node.

0008“Unicast” data transfer (i.e., unicast forwarding) involves forwarding a data packet from a single process of an end node (“source”) to a single process of an end node (“receiver”) on the computer network. Often the destination of the data packet issued by a source may be more than one, but less than all of the receivers on the network. This type of “multicast” data transfer (i.e., multicast forwarding) is typically employed to segregate communication between groups of receivers on the network. IP multicasting, in particular, may be used to disseminate data to a large group of receivers on the network.

0009To effect IP multicasting, the source generally specifies a destination IP address that is a multicast group address for the message and, as such, can only represent receivers of packets. The IPv4 (or IPv6) address range is subdivided into different prefixes, one of which is designated for use by IP multicast. Receivers typically notify their communication software of their desire to receive messages destined for the multicast group address; this is called “joining a multicast group.” These receiving members then “listen” on the multicast address and, when a multicast message is received at a receiver, it delivers a copy of the message to each process that belongs to the group.

0010IP multicasting relies on (i) a group management protocol to establish and maintain local multicast group membership, and (ii) multicast routing protocols to route packets efficiently, such as, e.g., Protocol Independent Multicast (PIM). The Internet Group Management Protocol (IGMP) manages packet communication between end nodes, e.g., hosts, and their local intermediate network node, e.g., multicast router, letting them join or leave groups. That is, IGMP is used to send a group membership message from a host to its directly connected router, indicating that the host wants to join a group (address) as a receiver. Note that IGMP is an IPv4 group membership protocol; the conventional Multicast Listener Discovery (MLD) protocol is substantially similar to, and performs the same functions as, IGMP, but for IPv6. When group membership is established, multicast packets (identified by a multicast source (S) and group (G) address in the destination address field of an IP header, or an “(S,G)” address) are forwarded between routers using multicast routing protocols. IGMP is described in RFC 3376, entitled Internet Group Management Protocol, Version 3, by Cain et al., October 2002, the contents of which are hereby incorporated by reference as though fully set forth herein.

0011In certain IP multicast networks, a single node or router acts as a meeting place for sources and receivers of multicast data. In other words, IP multicast packets from an upstream source and join messages from downstream routers “rendezvous” at this core router, or “Rendezvous Point” (RP). An RP may be configured to know the sources (S) for all multicast groups (G) of the IP multicast network. That is, by using an RP, other routers of the IP multicast networks are not required to know the addresses of the sources or every multicast group, but instead only the address of the RP. When a router (an end point) learns that an interested receiver wishes to join a particular group, the router will attempt to join the group at the RP, not to the actual source of the content. Thus, rather than the (S,G) notation above, the RP model utilizes a “(*,G)” notation, in which any source (*) may be used for a given group (G), i.e., multiple sources may source multicast traffic for the same group. The use of RPs and multicasting generally is further described in RFC 2362, entitled Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification, by Estrin et al., June 1998, and in the Internet Draft by Fenner et al., entitled Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification (Revised) <draft-ietf-pim-sm-v2-new-12.txt>, Internet Draft, March 2006, the contents of both which are hereby incorporated by reference as though fully set forth herein.

0012RPs for an IP multicast network may be determined using either manual configuration (e.g., a system administrator manually configures the RP at each router), or dynamic configuration. One example of a dynamically configured RP is an “Auto-RP” protocol (a proprietary protocol of Cisco Systems, Inc.), which automatically distributes information to routers that identifies the RP address for various multicast groups. Specifically, potential RPs announce themselves to a “mapping agent,” which resolves any conflicts from the potential RPs. The mapping agent then sends out the multicast group RP mapping information to the other routers, which are listening for this RP information (e.g., using pre-configured group addresses). Alternatively, a non-proprietary dynamic RP configuration method involves the use of a “bootstrap router” (BSR), which operates in a similar manner to the mapping agent of Auto-RP. In particular, a single BSR may be selected based on one or more configured policies. Potential RP candidates may announce themselves to the BSR, which then elects the RP based on the candidates. The use of a BSR is further described in the Internet Draft by Bhaskar et al., entitled Bootstrap Router (BSR) Mechanism for PIM <draft-ietf-pim-sm-bsr-09.txt>, Internet Draft, June 2006, the contents of which are hereby incorporated by reference as though fully set forth herein.

0013A virtual circuit may be used to define a logical end-to-end data path between two or more network nodes (e.g., participating in virtual private network, “VPN”). The virtual circuit may be established using, for example, conventional layer-2 Frame Relay (FR) or Asynchronous Transfer Mode (ATM) networks. Alternatively, the virtual circuit may “tunnel” data between its logical end points using known layer-2 and/or layer-3 tunneling protocols, such as the Layer-2 Tunneling Protocol (L2TP) and the Generic Routing Encapsulation (GRE) protocol. In this case, one or more tunnel headers are prepended to a data packet to appropriately route the packet along the virtual circuit. The Multi-Protocol Label Switching (MPLS) protocol may be used as a tunneling mechanism for establishing layer-2 virtual circuits or layer-3 network-based VPNs through an IP network. Notably, when the two or more nodes are located in different routing domains, devices in a plurality of interconnected routing domains may cooperate to establish the nodes' virtual circuit.

0014MPLS enables network nodes to forward packets along predetermined “label switched paths” (LSPs). Each LSP defines a logical data path, or virtual circuit, between a pair of source and destination nodes; the set of network nodes situated along the LSP may be determined using reachability information provided by conventional interior gateway protocols, such as OSPF, IS-IS, etc. Unlike traditional IP routing, where node-to-node (“next hop”) forwarding decisions are performed based on destination IP addresses, MPLS-configured nodes instead forward data packets based on “label” values (or “tag” values) added to the IP packets. As such, an MPLS-configured node can perform a label-lookup operation to determine a packet's next-hop destination. MPLS Traffic Engineering (TE) provides additional advantages over IP-based routing, such as enabling MPLS-configured nodes to reserve network resources, such as bandwidth, to ensure a desired quality of service (QoS).

0015Each destination represented via an LSP is associated with a locally allocated label value at each hop of the LSP, such that the locally allocated label value is carried by data packets forwarded over its associated hop. The MPLS label values are typically distributed among the LSP's nodes using, e.g., the Label Distribution Protocol (LDP), Resource Reservation Protocol (RSVP) or Multiprotocol (MP)-BGP protocol. Operationally, when a data packet is received at an MPLS-configured node, the node extracts the packet's transported label value, e.g., stored at a known location in the packet's encapsulating headers. The extracted label value is used to identify the next network node to forward the packet. Typically, an IGP label determines the packet's next hop within a routing domain, and a VPN label determines the packet's next hop across routing domains. More generally, the IGP label may be an MPLS label or any other encapsulation header used to identify the packet's next hop in the routing domain.

0016The packet may contain a “stack” of labels such that the stack's top-most label (i.e., an “outer-label”) determines the packet's next-hop destination. After receiving the packet, the MPLS-configured node “pops” (removes) the packet's top-most label from the label stack and performs a label-lookup operation to determine the packet's next-hop destination. Then, the node “pushes” (inserts) a new label value associated with the packet's next hop onto the top of the stack and forwards the packet to its next destination. This process is repeated for every logical hop along the LSP until the packet reaches its destination node. The above-described MPLS operation is described in more detail in Chapter 7 of the reference book entitled IP Switching and Routing Essentials, by Stephen Thomas, published 2002, which is hereby incorporated by reference as though fully set forth herein.

0017LSPs may be used to carry traffic from multiple IP streams that are demultiplexed at downstream end nodes of the LSP. A receiving end node (i.e., the destination of the LSP) receives the traffic, and may perform an “IP lookup” operation, e.g., into a forwarding/routing table, to determine where to forward the traffic based on the destination address of the traffic previously encapsulated in the LSP. The end node may then forward the traffic to the appropriate destination (i.e., without the LSP labels). Because an IP lookup may consume time and/or resources, an efficient advance has been made to utilize an “inner-label” that corresponds to a particular IP stream. Specifically, an upstream source of a particular IP stream on the LSP (e.g., an end/root node) may allocate a specific inner-label that corresponds to the particular IP stream. A receiving LSP end node may then use the inner-label to determine to which IP stream the received data belongs. By doing so, the receiving LSP end node may forward the traffic to an appropriate destination (or destinations) accordingly without the need for an IP lookup. Notably, the inner-label may be based on a context provided by the outer-label for the LSP if multiple LSPs end at the receiving end node, as will be understood by those skilled in the art.

0018Conventional LSPs are established between a source end node and a destination end node, i.e., “point-to-point” (P2P) LSPs. Multipoint LSPs, on the other hand, may be employed that connect one or more source end points to one or more destination end points, e.g., along a shared tree. These multipoint LSPs may be used in a manner similar to (and may complement) IP multicast, with packet replication at various LSRs of the shared tree, as will be understood by those skilled in the art. Notably, extensions to LDP are further described in the Internet Draft by Minei et al., entitled Label Distribution Protocol Extensions for Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths <draft-ietf-mpls-ldp-p2mp-01>, dated June 2005 and in the Internet Draft by Wijnands et al., entitled Multicast Extensions for LDP <draft-wijnands-mpls-ldp-mcast-ext-00.txt>, dated March 2005, the contents of both of which are hereby incorporated by reference as though fully set forth herein. “Point-to-Multipoint” (P2MP) LSPs, for example, have one source end node to source traffic onto the P2MP LSP, and multiple destination end nodes to receive the traffic from the P2MP LSP. As mentioned above, the upstream source end (root) node may allocate an inner-label for sourced IP stream traffic, such that each of the destination end nodes may uniquely identify a received IP stream based on the upstream-allocated inner-label and forward the corresponding traffic without performing an IP lookup.

0019“Multipoint-to-Multipoint” (MP2MP) LSPs, on the other hand, may have multiple source end nodes to source traffic onto the MP2MP LSP, and multiple destination end nodes to receive the traffic from the MP2MP LSP. Thus, an MP2MP LSP utilizes a bi-directional tree, in which each end node may either source or receive traffic, e.g., for various IP streams. (For instance, a multicast group utilizing MP2MP LSPs may employ the (*,G) source-independent notation.) One problem associated with using upstream-allocated inner-labels with MP2MP LSPs, however, is that there may be more than one source for a particular group that is sourcing traffic for an IP stream onto the MP2MP LSP. According to the upstream-allocated inner-label technique, each upstream source of the MP2MP LSP may allocate its own inner-label, which may be different from other sources' inner-labels. Accordingly, any end node receiving traffic for the IP stream on the MP2MP LSP will be unable to use the inner-labels effectively since it does not know to which source the inner-label belongs, and, unfortunately, may be required to perform an inefficient IP lookup operation. There remains a need, therefore, to avoid IP lookup with MP2MP LSPs.

SUMMARY OF THE INVENTION

0020The present invention is directed to a technique for avoiding Internet Protocol (IP) lookup with Multipoint-to-Multipoint (MP2MP) Label Switched Paths (LSPs) in a computer network. According to the novel technique, end nodes of an MP2MP LSP determine a root node of the MP2MP LSP for a particular IP stream, e.g., based on a rendezvous point (RP) of the IP stream. The root node of the MP2MP LSP allocates an inner-label for the particular IP stream, and informs each of the end nodes of the inner-label for that stream. When any one of the end nodes thereafter sources traffic for the stream, the sourced traffic contains the allocated inner-label for the IP stream. Upon receiving the traffic for the particular IP stream, an end node may determine the particular IP stream to which the received traffic belongs based on the MP2MP LSP (e.g., indicated by an outer-label) and the inner-label, i.e., without performing an IP lookup operation.

0021Advantageously, the novel technique avoids IP lookup with MP2MP LSPs in a computer network. By ensuring that each possible source node of the IP stream on the MP2MP LSP utilizes the same inner-label, the novel technique allows the receiving end nodes to determine the IP stream to which the received traffic belongs based on the unique inner-label for that LSP (i.e., regardless of the source). In particular, the present invention extends the concept of upstream-allocated inner-labels for point-to-multipoint (P2MP) LSPs for use with MP2MP LSPs by creating a mechanism through which all source nodes share the same unique inner-label for the IP stream on the MP2MP LSP, which is known by all the receiving end nodes. Further, the dynamic nature of the novel technique alleviates the need for cumbersome manual configuration.

BRIEF DESCRIPTION OF THE DRAWINGS

0022The above and further advantages of the invention may be better understood by referring to the following description in conjunction with the accompanying drawings in which like reference numerals indicate identically or functionally similar elements, of which:

0023<figref idref="DRAWINGS">FIG. 1</figref> is a schematic block diagram of an exemplary computer network that may be used in accordance with the present invention;

0024<figref idref="DRAWINGS">FIG. 2</figref> is schematic block diagram of an exemplary router that may be advantageously used with the present invention;

0025<figref idref="DRAWINGS">FIG. 3</figref> is a schematic block diagram of an exemplary encapsulated packet that may be advantageously used with the present invention;

0026<figref idref="DRAWINGS">FIG. 4</figref> is a schematic block diagram of an exemplary label-space/table that may be advantageously used with the present invention; and

0027<figref idref="DRAWINGS">FIG. 5</figref> is a flowchart illustrating a procedure for avoiding IP lookup with MP2MP LSPs in a computer network in accordance with the present invention.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT

0028<figref idref="DRAWINGS">FIG. 1</figref> is a schematic block diagram of an exemplary computer network <b>100</b> that may be advantageously used with the present invention. The network <b>100</b> comprises a service provider (SP) network <b>110</b> (e.g., an Internet SP, “ISP”) having a plurality of provider edge (PE) devices PE<b>1</b>-PE<b>3</b> interconnected by zero or more provider (P) devices (e.g., core devices) P<b>1</b>-P<b>3</b> as shown. Illustratively, the devices of the SP network may be interconnected by one or more links, such as, e.g., over wide area network (WAN) links, local area network (LAN) links, etc., to form the service provider network <b>110</b>. Also, in accordance with the present invention, one or more of the devices of the SP network are configured for multicast services, as will be understood by those skilled in the art, such that the service provider network is a multicast network. Computer network <b>100</b> also comprises one or more customer devices C1-C3, such as, e.g., content providers or receivers. Those skilled in the art will understand that any number of nodes, links, devices, etc., may be used in the computer network <b>100</b> and connected in a variety of ways, and that the view shown herein is for simplicity.

0029Data packets may be exchanged among the devices of the computer network <b>100</b> using predefined network communication protocols such as the Transmission Control Protocol/Internet Protocol (TCP/IP), User Datagram Protocol (UDP), Asynchronous Transfer Mode (ATM) protocol, Frame Relay protocol, Internet Packet Exchange (IPX) protocol, etc.

0030<figref idref="DRAWINGS">FIG. 2</figref> is a schematic block diagram of an exemplary node <b>200</b>, which is illustratively a router that may be advantageously used with the present invention, e.g., as a PE device. The router comprises a plurality of network interfaces <b>210</b>, a processor <b>220</b>, and a memory <b>240</b> interconnected by a system bus <b>250</b>. The network interfaces <b>210</b> contain the mechanical, electrical and signaling circuitry for communicating data over physical links coupled to the network <b>100</b>. The network interfaces may be configured to transmit and/or receive data with interconnected network nodes using a variety of different communication protocols, including, inter alia, TCP/IP, UDP, ATM, DSL, synchronous optical networks (SONET), wireless protocols, Frame Relay, Ethernet, Fiber Distributed Data Interface (FDDI), etc. Notably, a physical network interface <b>210</b> may also be used to implement one or more virtual network interfaces, such as for virtual private network (VPN) access, known to those skilled in the art.

0031The memory <b>240</b> comprises a plurality of storage locations that are addressable by the processor <b>220</b> and the network interfaces <b>210</b> for storing software programs and data structures associated with the present invention. The processor <b>220</b> may comprise necessary elements or logic adapted to execute the software programs and manipulate the data structures, such as label-space/table <b>400</b>. A router operating system <b>242</b> (e.g., the Internetworking Operating System, or IOS™, of Cisco Systems, Inc.), portions of which are typically resident in memory <b>240</b> and executed by the processor, functionally organizes the router by, inter alia, invoking network operations in support of software processes and/or services executing on the router. These software processes and/or services may comprise routing services <b>247</b>, Multipoint-to-Multipoint Label Switched Path (MP2MP LSP) services/process <b>248</b>, multicast forwarding process <b>244</b>, Internet Group Management Protocol (IGMP) process <b>245</b>, etc. It will be apparent to those skilled in the art that other processor and memory means, including various computer-readable media, may be used to store and execute program instructions pertaining to the inventive technique described herein.

0032Routing services <b>247</b> contain computer executable instructions executed by processor <b>220</b> to perform functions provided by one or more routing protocols, such as IGP (e.g., OSPF and IS-IS), BGP, etc. These functions may be configured to manage a forwarding information database (not shown) containing, e.g., data used to make forwarding decisions. Routing services <b>247</b> may also perform functions related to virtual routing protocols, such as maintaining VRF instances (not shown) as will be understood by those skilled in the art.

0033In one embodiment, the routers described herein (e.g., PEs) may be IP routers that implement Multi-Protocol Label Switching (MPLS) and operate as label switched routers (LSRs). In one simple MPLS scenario, at an ingress to a network, a label is assigned to each incoming packet based on its forwarding equivalence class before forwarding the packet to a next-hop router. At each router, a forwarding selection and a new substitute label are determined by using the label found in the incoming packet as a reference to a label forwarding table that includes this information. At the network egress (or one hop prior), a forwarding decision is made based on the incoming label but optionally no label is included when the packet is sent on to the next hop. The paths taken by packets that traverse the network in this manner are referred to as label switched paths (LSPs). A protocol that may be used to distribute the labels throughout the network, e.g., a label distribution protocol (LDP), particularly as used herein, is described in the above-incorporated Internet Draft by Minei et al., entitled Label Distribution Protocol Extensions for Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths, and above-incorporated Internet Draft by Wijnands et al., entitled Multicast Extensions for LDP. Notably, where MPLS Traffic Engineering (TE) is used, TE-LSPs may be created that have guaranteed bandwidth under certain conditions, as will be understood by those skilled in the art.

0034Illustratively, the PE devices PE<b>1</b>-PE<b>3</b> are configured as end nodes of an MP2MP LSP. As those skilled in the art will understand, the MP2MP LSP may traverse links of an underlying IP multicast tree between the end nodes PE<b>1</b>-PE<b>3</b>, e.g., calculated using conventional techniques (e.g., shortest path first, “SPF,” etc.). Further, two illustrative multicast groups, G<b>1</b> and G<b>2</b>, may be configured to utilize the MP2MP LSP. As used herein, for example, PE<b>1</b> may be an ingress for a source (S<b>1</b>) for multicast groups G<b>1</b> and G<b>2</b>, i.e., (S<b>1</b>,G<b>1</b>) and (S<b>1</b>,G<b>2</b>), PE<b>2</b> may be an ingress for a source (S<b>2</b>) for the multicast groups, i.e., (S<b>2</b>,G<b>1</b>) and (S<b>2</b>,G<b>2</b>), and PE<b>3</b> may be an ingress for a source (S<b>3</b>) for the multicast groups, i.e., (S<b>3</b>,G<b>1</b>) and (S<b>3</b>,G<b>2</b>). Notably, each PE device PE<b>1</b>-PE<b>3</b> may also be configured as a receiving end node for the groups G<b>1</b> and G<b>2</b>. Further, customer devices C<b>1</b>-C<b>3</b>, as mentioned above, may be a source or destination of IP multicast traffic streams (IP streams) that utilize the MP2MP LSP.

0035Briefly, <figref idref="DRAWINGS">FIG. 3</figref> is a schematic block diagram of an exemplary encapsulated packet <b>300</b> that may be advantageously used with the present invention. Illustratively, packet <b>300</b> is shown as a high-level generic packet, and those skilled in the art will understand that packet <b>300</b> may comprise other fields accordingly. The packet <b>300</b> includes an outer-label <b>305</b> corresponding to the MP2MP LSP, an inner-label <b>310</b> defined and used in accordance with the present invention described below, as well as conventional headers <b>315</b> (e.g., TCP/IP, etc.) of the un-encapsulated portion of the packet <b>300</b> (e.g., for IP routing of the IP stream), and a payload field <b>320</b> that may be used to contain packet-specific information (e.g., the content of the IP stream), as will be understood by those skilled in the art.

0036MP2MP LSP services/process <b>248</b> contains computer executable instructions executed by processor <b>220</b> to perform functions provided by one or more multicast and/or LSP (tunneling/encapsulation) protocols. For instance, multicast forwarding process <b>244</b> may contain computer executable instructions executed by processor <b>220</b> to perform functions provided by one or more multicast protocols, such as Protocol Independent Multicast (PIM), PIM-Sparse Mode (PIM-SM), etc. These functions may be configured to cooperate with one or more routing protocols of routing services <b>247</b> that may be used to make routing and forwarding decisions. Also, IGMP process <b>245</b> may contain computer executable instructions executed by processor <b>220</b> to perform conventional IGMP functions described briefly above, as will be understood by those skilled in the art. Other processes that will further be understood by those skilled in the art to perform multicast and/or LSP protocols (e.g., RSVP, TE, etc., not shown) may also be contained within MP2MP LSP services/process <b>248</b>, and may be used in accordance with the present invention.

0037Although the illustrative embodiment described herein is directed to MPLS, it should also be noted that the present invention may advantageously apply to Generalized MPLS (GMPLS), which pertains not only to packet and cell-based networks, but also to Time Division Multiplexed (TDM) and optical networks. GMPLS is well known and described in RFC 3945, entitled Generalized Multi-Protocol Label Switching (GMPLS) Architecture, dated October 2004, and RFC 3946, entitled Generalized Multi-Protocol Label Switching (GMPLS) Extensions for Synchronous Optical Network (SONET) and Synchronous Digital Hierarchy (SDH) Control, dated October 2004, the contents of both of which are hereby incorporated by reference in their entirety.

0038The present invention is directed to a technique for avoiding IP lookup with MP2MP LSPs in a computer network. According to the novel technique, end nodes of an MP2MP LSP determine a root node of the MP2MP LSP for a particular IP stream, e.g., based on a rendezvous point (RP) of the IP stream. The root node of the MP2MP LSP allocates an inner-label for the particular IP stream, and informs each of the end nodes of the inner-label for that stream. When any one of the end nodes thereafter sources traffic for the particular IP stream, the sourced traffic contains the allocated inner-label for the stream. Upon receiving the traffic for the particular IP stream, an end node may determine the IP stream to which the received traffic belongs based on the MP2MP LSP (e.g., indicated by an outer-label) and the inner-label, i.e., without performing an IP lookup operation.

0039Notably, each of the end nodes of the MP2MP LSP (PE<b>1</b>-PE<b>3</b>) determines the root of the MP2MP LSP, e.g., in a conventional manner. For example, the root (e.g., illustratively PE<b>1</b>) may be selected as the node corresponding to the RP of the underlying IP multicast tree, which, e.g., has been determined manually or dynamically (Auto-RP, BSR, etc.), as described above. In other words, the root may be the RP, or, illustratively, may be the node via which the RP is reachable. Those skilled in the art will understand various means for determining the root of the MP2MP LSP, and such means may be advantageously used with the present invention accordingly.

0040In accordance with the present invention, the root node of the MP2MP LSP (e.g., PE<b>1</b>) allocates an inner-label for each IP stream, i.e., a (*,G) group, that will utilize the MP2MP LSP. In one aspect of the present invention, the root node may advertise the inner-labels using a conventional PE-PE signaling protocol, such as Multiprotocol BGP (MP-BGP), PIM, etc., as will be understood by those skilled in the art. Notably, the advertisements may be sent at any time (e.g., periodic notifications/advertisements to a set of MP2MP LSP end nodes) or specifically in response to join requests from other end nodes (e.g., PE<b>2</b> and PE<b>3</b>).

0041For instance, when configured to send advertisements in response to join requests, each potential source end point learns of the appropriate inner-label for a particular IP stream/group once a receiver attached to the source end point submits a request to join the particular IP stream/group. That is, upon receiving a join request, the root node may return an indication of which MP2MP LSP the requesting end node should join for the group and the inner-label corresponding to the group on that MP2MP LSP. The source end point may then re-use the inner-label learned from the root node when sourcing traffic for the particular IP stream/group itself.

0042For example, assume that a receiver C<b>2</b> becomes active, and sends a join request to PE<b>2</b> (its locally attached PE device) to join an IP stream of group G<b>1</b>, i.e., (*,G<b>1</b>). PE<b>2</b> is thus triggered to communicate PE-PE signaling messages to the root node PE<b>1</b> to transmit the join request accordingly (e.g., to the RP). PE<b>1</b> may return an indication of which MP2MP LSP PE<b>2</b> should join for the group G<b>1</b> (e.g., MP2MP LSP “1” shown). In addition, in accordance with the present invention, PE<b>1</b> may also identify the inner-label (e.g., “L100”) corresponding to G<b>1</b> on that MP2MP LSP. Now, when PE<b>2</b> receives packets <b>300</b> having the corresponding outer- and inner-labels (described in detail below), PE<b>2</b> may determine the appropriate group G<b>1</b>, regardless of the traffic's source.

0043In accordance with the present invention, should C<b>2</b> begin sourcing traffic for G<b>1</b>, PE<b>2</b> may encapsulate the traffic into sourced packets <b>300</b> onto the MP2MP LSP using the appropriate outer-label <b>305</b> (e.g., corresponding to MP2MP LSP “1”) and the learned inner-label <b>310</b> (“L100”) for group G<b>1</b>, i.e., the inner-label to be used by any source of group G<b>1</b> traffic. The same procedure would apply for learning the inner-label for group G<b>2</b> (e.g., “L200”), and for each other end node to learn the inner-labels. Those skilled in the art will understand that the outer-labels for MP2MP LSP “1” may differ at each end node PE<b>1</b>-PE<b>3</b> since outer-labels are hop-by-hop assignments. Accordingly, where the present invention describes an “outer-label” for the MP2MP LSP, an indication of the appropriate MP2MP LSP (e.g., “1”) is implied.

0044The learned outer-labels and inner-labels may be stored at each end node (e.g., PE devices PE<b>1</b>-PE<b>3</b>) in one or more label-spaces/tables accordingly. <figref idref="DRAWINGS">FIG. 4</figref> is a schematic block diagram of an exemplary label-space/table <b>400</b> that may be advantageously used with the present invention. Label-spaces/tables <b>400</b> may be illustratively stored in memory <b>240</b>, where each label-space/table <b>400</b> corresponds to a particular MP2MP LSP context <b>405</b> (e.g., corresponding to an outer-label, e.g., “1”). Label-space/table <b>400</b> includes one or more entries <b>420</b>, each comprising a plurality of fields for storing an inner-label <b>410</b> and a corresponding IP stream (e.g., group, G) <b>415</b>. In accordance with the present invention, the combination of the outer-label context <b>405</b> and inner-label <b>410</b> uniquely identifies a particular IP stream (group) <b>415</b> on all end nodes, regardless of source, i.e., (*,G) groups, thus allowing end nodes of an MP2MP LSP to distinguish received traffic without requiring an IP lookup, e.g., as described below.

0045The label-space/table <b>400</b> is illustratively maintained and managed by MP2MP LSP services/process <b>248</b>. Accordingly, MP2MP LSP services/process <b>248</b> populates the label-space/table <b>400</b> with inner-labels and IP streams in accordance with the present invention. While individual label-spaces/tables <b>400</b> are shown for a plurality of MP2MP LSPs, the end node may alternatively maintain a single label-space/table <b>400</b> to be used for all MP2MP LSPs of the end node (e.g., PE<b>1</b>-PE<b>3</b>). For example, a separate field (e.g., a third column, not shown) may be used to identify the outer-label for each inner-label <b>410</b> and IP stream <b>415</b>.

0046Notably, while the above technique describes dynamically learning the corresponding inner-labels, the present invention may equally be applied to inner-labels that are manually pre-configured, e.g., by a system administrator, such as for relatively simpler network configurations (e.g., having a small number of MP2MP LSPs and IP streams). Moreover, in accordance with the present invention, the root node (PE<b>1</b>) is not required to learn the inner-label through signaling, as it is the root node which has assigned the inner-labels accordingly.

0047In accordance with the present invention, packets <b>300</b> may be received at an end node (e.g., PE device, PE<b>3</b>) of the MP2MP LSP having the outer-label <b>305</b> and inner-label <b>310</b> (e.g., as sent from PE<b>2</b> above). The receiving end node may then perform IP replication of the packet <b>300</b> (i.e., forwarding the packet to associated IP destination addresses, as will be understood by those skilled in the art) based on the outer- and inner-labels accordingly. In particular, the receiving end node examines the contents of the outer-label field <b>305</b> to determine a context (e.g., a label-space/table <b>400</b>) of the inner-label <b>310</b>. In other words, the end node may correlate the combined outer- and inner-labels with associated IP streams or groups, i.e., (*,G) groups, using an appropriate label-space/table <b>400</b>. For example, a packet <b>300</b> may be received at an end node, e.g., PE<b>2</b>, having an outer-label <b>305</b> of “1” and an inner-label <b>310</b> of “L100.” According to the present invention, the packet <b>300</b> is associated with IP stream G<b>1</b>, i.e., (*,G<b>1</b>), based on the entry <b>420</b> corresponding to “L100” within the label-space/table <b>400</b> for MP2MP LSP “1.” Alternatively, if the inner-label <b>310</b> identified “L200,” the packet <b>300</b> would be associated with IP stream G<b>2</b>, i.e., (*,G<b>2</b>), accordingly.

0048Because each end node PE<b>1</b>-PE<b>3</b> of the MP2MP LSP will have configured a label-space/table <b>400</b> with the same outer- and inner-label correlation in accordance with the present invention, each end node may determine the appropriate IP stream regardless of the source of the stream, and without having to perform an IP lookup. That is, an outer-label corresponding to an MP2MP LSP and a particular inner-label will correspond to the same particular IP stream, i.e., (*,G) group, at each receiving end node of the network.

0049Notably, in the event the inner-labels are not learned prior to receiving join requests as described above (e.g., advertised periodically, or once the inner-label is determined at the root node), there may be circumstances that cause an end node of the MP2MP LSP to source traffic for a particular IP stream without an inner-label (e.g., where the source has not received a join request to learn the inner-label from the root node). In such a case, the source end node simply does not include the inner-label, and any receiving end node may perform an IP lookup in a conventional manner. For instance, the receiving end node may be required to use a destination IP address contained within the header <b>315</b> of packet <b>300</b> to determine (through IP lookup) to which IP stream the packet belongs.

0050Those skilled in the art will understand from the present invention that once each source end node of an IP stream has learned the inner-label for the stream, no other (so configured) receiving end node need perform an IP lookup for that IP stream. In particular, once all sources and receivers are active (i.e., have sourced and/or requested to receive IP stream traffic), all traffic (packets <b>300</b>) which is sent over the MP2MP LSP by a source (PE device) is encapsulated with appropriate inner-labels and an MP2MP LSP outer-label (which, notably, may change hop-by-hop within the network). Moreover, those skilled in the art will also understand that the present invention does not impact operation of the P devices (core devices) of the provider network <b>110</b>, i.e., intermediate devices along the MP2MP LSP, since the intermediate devices are only concerned with the conventional outer-labels <b>305</b> of the transmitted packets <b>300</b>.

0051<figref idref="DRAWINGS">FIG. 5</figref> is a flowchart illustrating a procedure for avoiding IP lookup with MP2MP LSPs in a computer network in accordance with the present invention. The procedure <b>500</b> starts at step <b>505</b>, and continues to step <b>510</b>, where the end nodes of an MP2MP LSP (e.g., PE<b>1</b>, PE<b>2</b>, and PE<b>3</b>) determine a root node (e.g., PE<b>1</b>) of the MP2MP LSP, as described above. If the end node is itself the root node at step <b>515</b>, the root node allocates unique inner-labels for each IP stream for which the node is the root. For instance, the root node (PE<b>1</b>) may allocate an inner-label of “L100” for G<b>1</b> and “L200” for G<b>2</b>, as described above. Upon receiving a join request in step <b>525</b> for groups (IP streams) from other end nodes (e.g., PE<b>2</b> and/or PE<b>3</b>), the root node returns an indication of which MP2MP LSP to use for the IP streams in step <b>530</b>, as well as the unique inner-label allocated for the particular IP streams (e.g., L100 for G<b>1</b> requests, L200 for G<b>2</b> requests).

0052If, on the other hand, the end node is not the root node at step <b>515</b> (e.g., PE<b>2</b> and PE<b>3</b>), the end node may receive join requests for groups (IP streams) from one or more attached receivers (e.g., R<b>2</b>, R<b>3</b>, etc.) at step <b>535</b>. At step <b>540</b>, the end node communicates the join request to the root node (PE<b>1</b>), as described above. Based on that communication, the end node learns which MP2MP LSP to join along with a unique inner-label for the requested IP stream (e.g., L100, L200, etc.) in step <b>545</b>. Notably, where pre-configuration is applied to the end nodes to learn the inner-labels in step <b>545</b>, steps <b>535</b> and <b>540</b> may not be required to initiate the learning of inner-labels, as described above.

0053Each of the end nodes of the MP2MP LSP (PE<b>1</b>-PE<b>3</b>) may then either source traffic for the IP stream or receive traffic from the IP stream in step <b>550</b>. When sourcing traffic onto the MP2MP LSP, the end node encapsulates the traffic (in packets <b>300</b>) with the appropriate outer-label (<b>305</b>) for the MP2MP LSP and the unique inner-label (<b>310</b>) for the IP stream in step <b>555</b>. When receiving traffic in step <b>560</b>, the end node extracts the outer-label (<b>305</b>) of the traffic (e.g., of the packet <b>300</b>) to determine the context of the inner-label (<b>310</b>), such as to which table (label-space) <b>400</b> the inner-label applies. Also in step <b>560</b>, the end node may accordingly perform IP replication of the IP stream based on the unique inner-label without IP lookup operations. Notably, as described above, if a source end node has not yet learned the inner-label for a particular IP stream, the inner-label may not be included within the traffic, and the receiving end node may perform IP lookup operations until the inner-label is included. The procedure <b>500</b> ends in step <b>595</b>.

0054Advantageously, the novel technique avoids IP lookup with MP2MP LSPs in a computer network. By ensuring that each possible source node of the IP stream on the MP2MP LSP utilizes the same inner-label, the novel technique allows the receiving end nodes to determine the IP stream to which the received traffic belongs based on the unique inner-label for that LSP (i.e., regardless of the source). In particular, the present invention extends the concept of upstream-allocated inner-labels for point-to-multipoint (P2MP) LSPs for use with MP2MP LSPs by creating a mechanism through which all source nodes share the same unique inner-label for the IP stream on the MP2MP LSP, which is known by all the receiving end nodes. Further, the dynamic nature of the novel technique alleviates the need for cumbersome manual configuration.

0055While there has been shown and described an illustrative embodiment that avoids IP lookup with MP2MP LSPs in a computer network, it is to be understood that various other adaptations and modifications may be made within the spirit and scope of the present invention. For example, the invention has been shown and described herein for use with MP2MP LSPs. However, the invention in its broader sense is not so limited, and may, in fact, be used with root and end nodes of P2MP LSPs and multipoint-to-point (MP2P) LSPs, as will be understood by those skilled in the art. In other words, root and end nodes of LSPs need not distinguish between MP2MP, P2MP, or MP2P LSPs, but may utilize the techniques described herein for the present invention regardless of the type of LSP. Further, while the LSPs as described herein refer particularly to MPLS LSPs, those skilled in the art will understand that any type of LSP or other packet encapsulation method may be utilized in accordance with the present invention, such as, e.g., Generic Routing Encapsulation (GRE) tunnels, IP Security (IPSec) tunnels, Layer-2 Tunneling Protocol (L2TP) tunnels, etc.

0056The foregoing description has been directed to specific embodiments of this invention. It will be apparent, however, that other variations and modifications may be made to the described embodiments, with the attainment of some or all of their advantages. For instance, it is expressly contemplated that the teachings of this invention can be implemented as software, including a computer-readable medium having program instructions executing on a computer, hardware, firmware, or a combination thereof. Also, electromagnetic signals may be generated to carry computer executable instructions that implement aspects of the present invention over, e.g., a wireless data link or a data network, such as the Internet. Accordingly this description is to be taken only by way of example and not to otherwise limit the scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.