Stateless multicasting over traffic engineered unicast tunnels

#Multiprotocol label switching (MPLS) is used to route data between nodes of a network based on labels instead of network addresses, thereby avoiding complex address lookups in a routing table. The labels identify virtual links (or paths) between nodes, which are referred to herein as label switched paths (LSPs). An LSP begins at a label edge router (LER) that is an ingress router for the path and traverses one or more label switched routers (LSRs) before ending at an LER that is an egress router for the LSP. To send a packet along an LSP, the ingress router pushes a label onto the packet. The label is assigned to the LSP by the next hop LSR in the path. The ingress router then sends the labeled packet to the next hop LSR. In response to receiving a packet, an LSR uses the label value in the topmost entry of the label stack to determine the next hop for the packet, e.g., using a lookup table that contains states of LSPs. The LSR then performs operations on the label stack based on the information in the topmost entry. For example, the LSR can swap the topmost label with a new label. For another example, the LSR can push a new label on top of the existing label to encapsulate the packet in another layer of MPLS. For yet another example, if the LSR is the egress router of the LSP associated with a topmost label, the LSR pops the topmost label from the packet.

#The present disclosure may be better understood, and its numerous features and advantages made apparent to those skilled in the art by referencing the accompanying drawings. The use of the same reference symbols in different drawings indicates similar or identical items.

#FIG. 1 is a block diagram of a communication system that implements stateful multiprotocol label switching (MPLS) multicasting according to some embodiments.

#FIG. 2 is a block diagram of a communication system that implements stateful MPLS multicasting along traffic engineered (TE) paths according to some embodiments.

#Multiprotocol label switching (MPLS) is implemented using label switched paths (LSPs) of two types—Best-Effort LSPs (BE-LSP) and Traffic Engineered LSPs (TE-LSP). The paths of BE-LSPs between routers in a network are determined using link state protocols such as open shortest path first (OSPF, OSPFv3), intermediate system-to-intermediate system (IS-IS), and the like. The link state protocol floods the status of locally connected networks and links of the routers across the network. Each router in the network builds an identical copy of the network topology based on the status information and then independently computes the paths to every other router (and any advertised networks), using path algorithms such as Dijkstra's Shortest Path First (SPF) algorithm, which computes the shortest paths between the nodes in a graph that represents the routers in the network. In response to the SPF computation, the routers program routing tables, e.g., to indicate next hop routers for unicast paths to different egress routers. The paths are associated with labels that are associated with the BE-LSP that follows the shortest paths to the egress routers. The egress router is an endpoint of the BE-LSP and there is only one BE-LSP to each egress router since the BE-LSP identifies the egress router. As used herein, the term “best effort” indicates that an LSR does not provide any guarantee that the packets are delivered or that delivery meets any quality-of-service (QoS) requirements. Best effort packets are conveyed at an unspecified variable bit rate and latency and packet loss rates that depend on the current traffic load.

#In contrast to BE-LSPs, TE-LSPs follow a path that satisfies QoS requirements of the packets transported over the TE-LSP. Each link in the network is assigned a set of TE metrics. Examples of TE metrics include a configured bandwidth, an available bandwidth that is equal to the configured bandwidth minus the bandwidth reserved by (or allocated to) existing flows, a delay, a color, a preference, an affinity, and the like. The TE metrics are flooded by the link state protocols. Using the flooded information, each router in the network builds a TE database (TEDB) that includes a copy of the TE metrics of the links in the network. The routers in the network build identical copies of the TEDB. The path of a TE-LSP between ingress and egress router is computed by CSPF (Constraint Shortest Path First) computation on TEDB with QoS as the constraint. The path is associated with labels that identify the TE-LSP. Once the TE-LSP is set up, the TE metrics of links along its path are updated based on QoS resources reserved for the TE-LSP. For example, available bandwidth on the links are decremented by the bandwidth used by the TE-LSP. Unlike the BE-LSPs, there could be multiple TE-LSPs between a pair of ingress and egress routers, each set up with a specific QoS.

#Multicasting allows a source to transmit a single packet to multiple receivers via a multicast distribution tree (MDT) including nodes along the MDT from an ingress router associated with the source to the egress routers associated with the receivers of the multicast packet. The nodes in the MDT selectively replicate the packet when the MDT branches into multiple paths towards different next hop nodes or egress routers. The MDT can be implemented as a point-to-multipoint tree that connects a single source to multiple receivers or a multipoint-to multipoint tree that connects multiple sources to multiple receivers, e.g., in a mesh network. Multicasting with MPLS is implemented in a stateful version and a stateless version. In stateful MPLS multicasting, the routers maintain control plane and data plane states that represent the MDT. The routers forward or replicate multicast packets based on the state that is stored in the router. In stateless MPLS multicasting, the routers do not maintain any control plane or data plane states for an MDT. An ingress router prefixes a packet with a label stack including the labels of the BE-LSPs to all egress routers. The ingress router replicates the packet to the next hops associated with the labels, e.g., based on states of the BE-LSPs. Labels that share the same next hop are included in the label stack of the packet replicated to the next hop. In response to receiving a packet, an LSR looks up each label in the label stack to determine the next hop, e.g., using a lookup table that contains the states of BE-LSPs. For example, an LSR can swap a label with a new label to the corresponding next hop. For another example, if the LSR is the egress router for the BE-LSP associated with the label, the LSR makes a local copy of the packet, pops the entire label stack from the packet copy, and forwards the packet to a multicast overlay such as a virtual private network (VPN) or other application that is using the multicast flow.