CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] This patent application claims the benefit of U.S. Provisional Patent Application No. 63/289,918 filed December 15, 2021 by Futurewei Technologies, Inc., and titled “Fast Segment Routing Multicast for IPv6,” which is hereby incorporated by reference.

TECHNICAL FIELD

[0002] The present disclosure is generally related to the field of network communication and, in particular, to multicast segment routing (SR) over the Internet Protocol version six (IPv6) data plane (SRv6).

BACKGROUND

[0003] SRv6 is a next-generation internet protocol (IP) bearer protocol that combines SR and IPv6. Utilizing existing IPv6 forwarding technology, SRv6 implements network programming through flexible IPv6 extension headers.

[0004] SRv6 reduces the number of required protocol types, offers great extensibility and programmability, and meets the diversified requirements of more new services. SRv6 also provides high reliability and offers exciting cloud service application potential.

[0005] In computer networking, multicast is group communication where data transmission is addressed to a group of destination computers simultaneously. Multicast can be one-to-many or many-to-many distribution. The one-to-many configuration is known as point-to-multipoint (P2MP).

[0006] SRv6 and multicast techniques may be used together to generate a SR P2MP path through a network multicast SR domain. In order to route packets, the SR P2MP path is encoded into a packet header. The packet header includes a plurality of multicast segment identifiers (SIDs).

SUMMARY

[0007] The currently proposed solutions for Segment Routing (SR) Multicast, or SR Point to Multipoint (P2MP) path or tunnel have the following requirements for a SR P2MP path when transmitting a packet, changing the packet header, in addition to popping segment identifiers (SIDs). The present disclosure proposes methods and apparatus for a segment routing version 6 (SRv6) multicast that operates without modifying the packet header except for popping SIDs and encapsulating the packet with SIDs.

[0008] A first aspect relates to a method implemented by an ingress node in a segment routing (SR) multicast domain along a point-to-multipoint (P2MP) path, comprising receiving a packet from a multicast source, duplicating the packet for each of sub-trees of the P2MP path from the ingress node to a plurality of egress nodes, encapsulating a duplicated packet with a segment routing header (SRH) for the sub-tree, and sending duplicated packet to a next hop node along the sub-tree.

[0009] Optionally, in the preceding aspect, another implementation further comprises setting a source address (SA) of the packet to an address of the ingress node, a setting a destination address (DA) of the packet to a multicast segment identifier (SID) of the next hop node. node.

[0010] Optionally, in any of the preceding aspects, in another implementation the SRH comprises a multicast segment identifier (SID) for each next hop node (NNH) along the sub-tree and a SID for each node of a sub-tree under a (NNH).

[0011] Optionally, in any of the preceding aspects, in another implementation, each SID comprises a common prefix of multicast node SIDs in a block of B bits, a globally unique node identifier (ID) of N bits, and arguments, wherein the B bits plus the N bits plus the arguments comprises 128 bits.

[0012] Optionally, in any of the preceding aspects, in another implementation, each SID comprises a multicast adjacency SID locator comprising a common prefix of B bits for multicast adjacent SIDs and a specific identifier of a node, a link sequence number of L bits corresponding to the node, and arguments, wherein the specific identifier is a globally unique identifier (ID) of N bits, and wherein the B bits plus the N bits plus the L bits plus the arguments comprises 128 bits.

[0013] Optionally, in any of the preceding aspects, in another implementation, B may be a 32- bit open shortest path first (OSPF) protocol router ID.

[0014] Optionally, in any of the preceding aspects, in another implementation, the arguments comprise a number of branches (No-Branches) and a number of SIDs (No-SIDs), and the NoBranches in a SID for a node on a sub-tree of a SR P2MP path has a value indicating the number of branches from the node along the sub-tree, and the No-SIDs in the SID has a value indicating the number of the SIDs encoding the sub-trees under the node and the SIDs following. [0015] A second aspect relates to a method implemented by a transit node in a segment routing (SR) multicast domain along a point-to-multipoint (P2MP) path, comprising receiving a packet having a segment routing header (SRH) with a segment identifier (SID) list of next hops and subtrees coupled with the transit node, and a destination address (DA), wherein the DA comprises a number of next hop branches (No-Branches) coupled with the transit node, a number of the SIDs (no-SIDs) encoding sub-trees under the transit node the SIDs following, and duplicating the packet once for each next hop node of the transit node along the P2MP path, setting the DA of each duplicate packet to a respective SID of the next hop node, setting segments left (SL) in SRH to NoSIDs in DA, and sending the duplicated packets to the DA.

[0016] Optionally, in any of the preceding aspects, in another implementation, each SID comprises a common prefix of multicast node SIDs in a block of B bits, a globally unique node identifier (ID) of N bits, and arguments, wherein the B bits plus the N bits plus the arguments comprise 128 bits.

[0017] Optionally, in any of the preceding aspects, in another implementation, each SID comprises a multicast adjacency SID locator comprising a common prefix of B bits for multicast adjacent SIDs and a specific identifier of a node, a link sequence number L corresponding to the node, and arguments, wherein the specific identifier is a globally unique identifier (ID) of N bits, and wherein the B bits plus the N bits plus the L bits plus the arguments comprise 128 bits.

[0018] Optionally, in any of the preceding aspects, in another implementation, B may be a 32- bit open shortest path first (OSPF) protocol router ID.

[0019] Optionally, in any of the preceding aspects, in another implementation, the arguments comprise the number of branches (No-Branches) and the number of SIDs (No-SIDs), wherein the No-Branches in a SID for a node on a sub-tree of a SR P2MP path along a path tree of the SR multicast domain to a destination address (DA).

[0020] A third aspect relates to a ingress node in a segment routing (SR) multicast domain along a point-to-multipoint (P2MP) path, comprising a memory storing instructions and a processor coupled to the memory, wherein the processor is configured to execute the instructions to cause the ingress node to receive a packet from a multicast source and duplicate the packet for each of sub-trees of the P2MP path from the ingress node to a plurality of egress nodes, encapsulate the duplicated packet with a segment routing header (SRH) for the sub-tree, and send the duplicated packet to a next hop node along the sub-tree. [0021] Optionally, in the preceding aspect, in another implementation the processor is further configured to cause the ingress node to set a source address (SA) of the packet to an address of the ingress node, and set a destination address (DA) of the packet to a SID of the next hop node.

[0022] Optionally, in any of the preceding aspects, in another implementation, the segment routing header (SRH) comprises a multicast segment identifier (SID) for each next hop node (NNH) of the next hop node along the sub-tree, and a SID for each node of a sub-tree under a next hop node.

[0023] Optionally, in any of the preceding aspects, in another implementation, each SID comprises a common prefix of multicast node SIDs in a block of B bits, a globally unique node identifier (ID) of N bits, and arguments, wherein the B bits plus the N bits plus the arguments comprise 128 bits.

[0024] Optionally, in any of the preceding aspects, in another implementation, each SID comprises a multicast adjacency SID locator comprising a common prefix of B bits for multicast adjacent SIDs and a specific identifier of a node, a link sequence number of L bits corresponding to the node, and arguments, wherein the specific identifier is a globally unique identifier of N bits, and wherein the B bits plus the N bits plus the L bits plus the arguments comprise 128 bits.

[0025] Optionally, in any of the preceding aspects, in another implementation, B is a 32-bit open shortest path first (OSPF) protocol router ID.

[0026] Optionally, in any of the preceding aspects, in another implementation, the arguments comprise the number of branches (no-Branches) and the number of SIDs (No-SIDs), wherein the No-branches in a SID for a node on a sub-tree of a SR P2MP path has a value indicating the number of branches from the node along the sub-tree, and the No-SIDs in the SID has a value indicating the number of the SIDs encoding the sub-trees under the node and the SIDs following.

[0027] A fourth aspect relates to a transit node in a segment routing (SR) multicast domain along a point-to-multipoint (P2MP) path, comprising a memory storing instructions and a processor coupled to the memory. The processor is configured to execute the instructions to cause the transit node to receive a packet having a segment routing header (SRH) with a segment identifier (SID) list of next hops and sub-trees coupled with the transit node, and a destination address (DA), wherein the DA comprises a number of branches (No-Branches) coupled with the transit node, a number of SIDs encoding sub-trees under the transit node, and the SIDs following. In this aspect, the instructions further cause the processor to duplicate the packet once for each next hop node of the transit node along the P2MP path, set the DA of each duplicate packet to a respective SID of the next hop node, set segment left (SL) in SRH to No-SIDs in the DA, and send the duplicated packets to the DA.

[0028] Optionally, in the preceding aspect, in another implementation, each SID comprises a common prefix of multicast node SIDs in a block of B bits, a globally unique node identifier (ID) of N bits, and arguments, wherein the B bits plus the N bits plus the arguments comprise 128 bits.

[0029] Optionally, in any of the preceding aspects, in another implementation, each SID comprises a multicast adjacency SID locator comprising a common prefix of B bits for multicast adjacent SIDs and a specific location of a node, a link sequence number of L bits corresponding to the node, and arguments, wherein the specific identifier is a globally unique identifier (ID) of N bits, and wherein the B bits plus the N bits plus the L bits plus the arguments comprise 128 bits.

[0030] Optionally, in any of the preceding aspects, in another implementation, B is a 32-bit open shortest path first (OSPF) protocol router ID.

[0031] Optionally, in any of the preceding aspects, in another implementation, the arguments comprise the number of branches (no-Branches) and the number of SIDs (No-SIDs), wherein the No-Branches in a SID for a node on a sub-tree of a SR P2MP path has a value indicating the number of branches from the node along the sub-tree, and the No-SIDs in the SID has a value indicating the number of the SIDs encoding the sub-trees under the node and the SIDs following.

[0032] A fifth aspect relates to a ingress node in a segment routing (SR) multicast domain along a point-to-multipoint (P2MP) path, comprising means for receiving a packet from a multicast source, means for duplicating the packet for each of sub-trees of a SR P2MP path from the ingress node to a plurality of egress nodes, means for encapsulating a duplicated packet with a segment routing header (SRH) for the sub-tree, and means for sending the duplicated packet to a next hop node along the sub-tree.

[0033] A sixth aspect relates to a transit node in a segment routing (SR) multicast domain along a point-to-multipoint (P2MP) path, comprising means for receiving a packet having a segment routing header (SRH) with a segment identifier (SID) list of next hops and sub-trees coupled with the transit node, and a destination address (DA), wherein the DA comprises a number of next hop branches (No-Branches) coupled with the transit node, a number of SIDs (No-SIDs) encoding sub-trees under the transit node and the SIDs following, means for duplicating the packet once for each next hop node of the transit node along the P2MP path, means for setting the DA of each duplicated packet to a respective SID of the next hop node and setting segment left (SL) in SRH to No-SIDs in the DA, and means for sending the duplicate packet to the DA.

[0034] For the purpose of clarity, any one of the foregoing embodiments may be combined with any one or more of the other foregoing embodiments to create a new embodiment within the scope of the present disclosure.

[0035] These and other features will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings and claims.

BRIEF DESCRIPTION OF THE DRAWINGS

[0036] For a more complete understanding of this disclosure, reference is now made to the following brief description, taken in connection with the accompanying drawings and detailed description, wherein like reference numerals represent like parts.

[0037] FIG. 1 is a schematic diagram of a SRv6 topology including a SRv6 multicast domain.

[0038] FIG. 2 is a multicast node segment identifier (SID) with branch and sub-tree information according to an embodiment of the disclosure.

[0039] FIG. 3 is a multicast adjacency SID according to an embodiment of the disclosure.

[0040] FIG. 4A is a multicast node SID with branch and sub-tree information according to an embodiment of the disclosure.

[0041] FIG. 4B is a multicast adjacency SID with branch and sub-tree information according to an embodiment of the disclosure.

[0042] FIG. 5 is a schematic diagram of multicast adjacency SIDs assigned to links according to an embodiment of the disclosure.

[0043] FIG. 6 is a segment list encoding sub-tree corresponding to a path shown in the example of FIG. 1.

[0044] FIG. 7 is a packet sent from ingress PE8 to Pl corresponding to the example of FIG. 1.

[0045] FIG. 8 depicts a packet received by Pl from PE8 corresponding to the example of FIG.

1.

[0046] FIG. 9 is a packet duplicated at Pl for sending to P2 and P3 corresponding to the example of FIG. 1.

[0047] FIG. 10 is a packet received at Pl and duplicated for sending to P2 and P3 corresponding to the example of FIG. 1. [0048] FIG. 11 is a packet received at P2 and duplicated for sending to PEI and PE2 corresponding to the example of FIG. 1.

[0049] FIG. 12 is a packet received at PEI corresponding to the example of FIG. 1.

[0050] FIG. 13 is a packet received at PE2 corresponding to the example of FIG. 1.

[0051] FIG. 14 is an example implementation of an embodiment of the disclosure.

[0052] FIG. 15 is an example of an IPv6 header using generalized SRv6 (G-SRv6) according to an embodiment of the disclosure.

[0053] FIG. 16 is an example of an IPv6 header for sending from an ingress node to a destination address according to an embodiment of the disclosure.

[0054] FIG. 17 is a schematic diagram of a network apparatus according to an embodiment.

DETAILED DESCRIPTION

[0055] It should be understood at the outset that although an illustrative implementation of one or more embodiments are provided below, the disclosed systems and methods may be implemented using any number of techniques, whether currently known or in existence. The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims along with their full scope of equivalents.

[0056] The present disclosure proposes systems and methods for a segment routing version 6 (SRv6) multicast implemented without modifying the packet header except for popping SIDs and encapsulating the packet with SIDs. A segment identifier (SID) block is allocated for SR Multicast. SIDs in this block are called multicast SIDs. When a node receives a packet with the destination address (DA) matching a multicast SID of the node, the node duplicates the packet received from an incoming interface and delivers the duplicated packet to each of the multiple outgoing interfaces along the SR P2MP path/tree (branches). In one embodiment, each node in a network is assigned a multicast SID. For example, as depicted in FIG. 1, there are nodes PEI to PE5, PE8, Pl to P4. They are assigned multicast SIDs PEl-m to PE5-m, PE8-m, Pl-m to P4-m, respectively.

[0057] The SR P2MP path/tree from the ingress to egresses (or leaves) is encoded in the segment list of the segment routing header (SRH) of a packet at the ingress. For example, the SR P2MP path in FIG. 1 comprises multicast SIDs PE8-m, Pl-m, PE5-m, P2-m, P3-m, PEl-m, PE2- m, P4-m, PE3-m and PE4-m. In one embodiment, after receiving a packet from a multicast traffic source, these SIDs are pushed into the segment list of SRH of the packet at ingress node PE8, wherein the SRH includes a segments left (SL) field and the packet includes a destination address (DA) and a source address (SA). Ingress node PE8 sets the DA of the packet to multicast SID PE8- m, which is the multicast SID of ingress node PE8; sets the SA of the packet to an IPv6 address of ingress node PE8; sets the SL in the SRH to the value in a number of SIDs (No-SID) field in PE8- m; “sends” the packet to ingress node PE8 (i.e., calls a procedure for a multicast SID for a transit node on ingress node PE8). After “receiving” the packet (i.e., the procedure is called), ingress node PE8 acting as a transit node duplicates the packet for each of the sub-trees branching from ingress node PE8 and sends the duplicated packet to the next hop node along the sub-tree. In another embodiment, after receiving a packet from a multicast traffic source, ingress node PE8 duplicates the packet for each of the sub-trees branching from ingress node PE8; pushes a SRH with a segment list into the duplicated packet for each sub-tree, wherein the segment list is for the sub-tree; sets the DA of the duplicated packet to a multicast SID of a next hop node along the subtree; sets the SA of the packet to an IPv6 address of ingress node PE8; sets the SL in the SRH to the value in No-SID field in the multicast SID and sends the duplicated packet the next hop node along the sub-tree.

[0058] The SR P2MP path/tree uses multicast SIDs. The packet received from a multicast source is imported into the SR P2MP path/tree at ingress and sent to the egresses/leaves of the path/tree along the path/tree. In the example shown in FIG. 1, a packet from CE3 is imported into the SR P2MP path/tree at ingress PE8 and sent to egresses PEI to PE5 along the path/tree.

[0059] For each node in a network SR multicast domain, a multicast node SID is allocated from the multicast SID block to the node, which is globally unique.

[0060] In one embodiment, a network administrator configures the multicast node SID for every node, which distributes the multicast SID in the SR multicast domain. In another embodiment, a central controller allocates a multicast SID for each node and sends the information about the SID to its node, which may then distribute the information in the SR multicast domain.

[0061] FIG. 2 illustrates an embodiment showing an example of a format of a multicast node SID of 128 bits. The multicast node SID comprises a multicast node SID block of B bits (i.e., the common prefix of the multicast node SIDs) and a node identifier (ID) of N bits. The former is the common prefix allocated for the multicast node SIDs. The latter is the ID of a node that is globally unique. In one embodiment for example, the open shortest path first (OSPF) router ID of 32-bits for a node is used as the ID of the node. The multicast node SID also comprises some arguments and functions (not shown).

[0062] For each node in a network SR multicast domain, every multicast link (or interface) connected to the node has an associated multicast segment identifier (SID), which is called Multicast Adjacency Segment Identifier. A multicast adjacency SID is relative to a specific node, and is locally significant.

[0063] Every node in the network SR multicast domain assigns a multicast SID from the multicast SID block to each of its links as the multicast adjacency SID for the link and advertises the information about the SID and its link. In another embodiment, for every node, a central controller assigns a multicast SID from the multicast SID block to each link of the node as the multicast adjacency SID for the link and sends the information about the SID and its link to the node and the neighbors of the node.

[0064] FIG. 3 shows an example of an embodiment of a possible format of a multicast adjacency SID of 128 bits. The multicast adjacency SID comprises a multicast adjacency SID locator of B bits and a link number of L bits. The multicast adjacency SID locator B bits for a node indicate the location of the node, which includes the common prefix allocated for the multicast adjacency SIDs and the specific identifier to the node. The link number L bits for a node is the link sequence number assigned to every link of the node. In one embodiment, for all n links of a node, link sequence number (or link number for short) 1, 2, . . ., n are assigned to the n links, respectively. The multicast adjacency SID also comprises some arguments and fiinction(s) (not shown).

[0065] A Multicast SID contains the following information. The number of branches (or subtrees) or next hops along the multicast tree from the node receiving a packet with the SID as destination address (DA) that belongs to the node. When the node receives the packet with its multicast SID (either multicast node SID or multicast adjacency SID) as DA transported by a SR P2MP path or tree, the SID includes the number of branches or next hops along the P2MP path or tree from the node. In one embodiment, the number of branches or next hops is included in the SRv6 SID as an argument of a 128-bit SID. This is shown in the examples of FIG. 4 A and FIG. 4B.

[0066] The number of the SIDs encoding the sub-trees from the node and the SIDs following them. In one embodiment, the number of the SIDs is included in the SRv6 SID as an argument of a 128-bit SID. This is also shown in FIG. 4A and FIG. 4B. [0067] An example of the encoding of P2MP Path/Tree is described with further reference to FIG. 1. For a sub-tree (ST) of a SR P2MP path/tree from the ingress node of the P2MP path/tree, suppose that the multicast SID of a next hop node NH (e.g., node Pl in FIG. 1) of the ingress is NH-m, there are B branches (i.e., outgoing interfaces) to the next hop node BNHj (e.g., P2 in FIG. 1) (j = 1, . . ., B (e.g., P3 in FIG. 1)) from node NH along the sub-tree, the multicast SID of BNHj is BNHj-m, and SidSeq-j (j = 1, . . ., B) is the SID sequence in the segment list encoding the sub-trees from node BNHj.

[0068] Sub-tree ST is encoded as segment list <NH-m, BNHl-m, . . ., BNHB-m, SidSeq-1, . . ., SidSeq-B>, where NH-m contains the number of branches in its No-Branches field, which is B, and the number of SIDs in its No-SIDs field, which is the number of the SIDs encoding the subtrees from NH, i.e., the number of the SIDs following NH-m (i.e., B plus the number of the SIDs in SidSeq-1, ..., SidSeq-B).

[0069] BNHj-m (j = 1, . . ., B) contains the number of branches in its No-Branches field, which is the number of branches from node BNHj, and the number of the SIDs in its No-SIDs field, which is the number of the SIDs in SidSeq-j (encoding the sub-trees from node BNHj) plus the number of the SIDs following SidSeq-j (i.e., the number of the SIDs in SidSeq-j to SidSeq-B).

[0070] For the multicast SID of a leaf in a SR P2MP path/tree, both its No-Branches field and No-SIDs field are 0.

[0071] For nodes Pl, P2, P3, P4, PEI, PE2, PE3, PE4, and PE5 in FIG. 1, each node is assigned a multicast node SID. For node X, the multicast node SID assigned to the node is named as X-m. For example, node Pl is assigned a multicast node SID Pl-m. P2-m, P3-m, P4-m, PEl-m, PE2-m, PE3-m, PE4-m, and PE5-m are the multicast node SIDs assigned to nodes P2, P3, P4, PEI, PE2, PE3, PE4, and PE5, respectively.

[0072] As shown in FIG. 5, the links/interfaces for nodes Pl, P2, P3, P4, PEI, PE2, PE3, PE4, and PE5 are connected to each of the nodes assigned multicast SIDs. For node X, the multicast adjacency SID assigned to each of its n links is named as X-im (i = 1, ,. . ., n). For example, node Pl has three links connected to it. Multicast adjacency SIDs Pl-lm, Pl-2m and Pl-3m are assigned to these three links respectively. Node PE2 has one link connected to it, Multicast adjacency SID PE2-lm is assigned to the link.

[0073] For the P2MP path in FIG. 1 from ingress node PE8 to egress nodes PEI, PE2, PE3, PE4, and PE5, there are two sub-trees from ingress PE8. The first sub-tree is from ingress PE8 via Pl to egresses PEI to PE4, the second one is from ingress PE8 to PE5. The second sub-tree is in fact a P2P path and can be encoded in the same way as a SR P2P path.

[0074] The first sub-tree is encoded as segment list <Pl-m, P2-m, P3-m, PEl-m, PE2-m, P4- m, PE3-m, PE4-m>, where PEl-m, PE2-m is the SID sequence (SidSeq-1) in the segment list encoding the sub-trees from P2.

[0075] P4-m, PE3-m, PE4-m is the SID sequence (SidSeq-2) in the segment list encoding the sub-tree from P3.

[0076] Pl-m’s No-Branches field is set to 2 since there are 2 branches from Pl, Pl-m’s NoSIDs field is set to 7 since there 7 SIDs following Pl-m. These 7 SIDs encode the sub-trees from Pl. There is no SID following these 7 SIDs.

[0077] P2-m’s No-Branches field is set to 2 since there are 2 branches from P2, P2-m’s NoSIDs field is set to 5, which the number of SIDs in SidSeq-1 encoding the sub-trees from P2 plus the number of the SIDs following SidSeq-1.

[0078] P3-m’s No-Branches field is set to 1 since there is 1 branch from P3, P3-m’s No-SIDs field is set to 3, which is the number of SIDs in SidSeq-2 encoding the sub-tree from P3. No SID follows SidSeq-2.

[0079] P4-m’s No-Branches field is set to 2 since there are 2 branches from P4 and No-SIDs field is set to 2.

[0080] PEl-m, PE2-m, PE3-m, PE4-m are the multicast SIDs of leaf nodes in the P2MP path. Their No-Branches fields and No-SIDs fields are zeros. FIG. 6 shows the segment list in detail.

[0081] Note that for the multicast node SID assigned to a node, its No-Branches field and No- SIDs field are zeros. When the multicast node SID is used in the segment list of a packet to encode a SR P2MP path or a part of the SR P2MP path, its No-Branches field and No-SIDs field are set according to the part of the SR P2MP path encoded.

[0082] In FIG. 6, SID Pl-m indicates that there are 2 branches and 7 SIDs. SID P2-m indicates that there are 2 branches and 5 SIDs. SID P3-m indicates that there are 1 branch and 3 SIDs. In an embodiment, Pl-m corresponds to Pl, P2-m corresponds to P2, and P3-m corresponds to P3 in FIG. 1.

[0083] SIDs PEl-m and PE2-m indicate that no branch is under them.

[0084] SID P4-m indicates that there are 2 branches and 2 SIDs. PE3-m and PE4-m indicate that no branch is under them. [0085] In this example, the procedure/behavior on an ingress node is as follows. For a packet to be transported by a SR P2MP Path, the ingress of the P2MP path duplicates the packet for each sub-tree of the SR P2MP path branching from the ingress, sets the destination address (DA) of the packet to the multicast SID of the next hop node along the sub-tree, pushes the segment list encoding the sub-tree into the packet and sends the packet to the next hop node.

[0086] For example, there are two sub-trees branching from the ingress for the SR P2MP path/tree in FIG. 1. The first sub-tree is from ingress PE8 via next hop node Pl towards PEI to PE4. The second sub-tree is from ingress PE8 to egress PE5.

[0087] For the first sub-tree, ingress PE8 duplicates the packet, sets the destination address (DA) to Pl-m (i.e., multicast SID of node Pl) and source address (SA) to PE8, pushes the segment list without Pl-m (i.e., <P2-m, P3-m, PEl-m, PE2-m, P4-m, PE3-m, PE4-m>) with Segments Left (SL) = No-SIDs in Pl-m in SRH of the packet and sends the packet to DA (i.e., node Pl). In one embodiment, the contents of the multicast SIDs Pl-m, P2-m, P3-m, PEl-m, PE2-m, P4-m, PE3-m, PE4-m are shown in FIG. 6.

[0088] The packet ingress PE8 sends Pl the packet shown in FIG. 7.

[0089] When a transit node of a SR P2MP path receives a packet transported by the P2MP path, the DA of the packet is a multicast SID of the node and the packet contains a segment list for the sub-trees from the node. The DA and the segment list comprise the information for encoding the sub-trees under the transit node.

[0090] For example, when node Pl receives a packet transported by the SR P2MP path, the packet’s DA is Pl-m (which is a multicast SID of node Pl) and the segment list is <P2-m, P3-m, PEl-m, PE2-m, P4-m, PE3-m, PE4-m> with SL=7. In one embodiment, the contents of the multicast SIDs Pl-m, P2-m, P3-m, PEl-m, PE2-m, P4-m, PE3-m, PE4-m are shown in FIG. 6.

[0091] The No-Branches field (which has value of B, where B > 0) of the DA indicates that there are B branches (or next hops) from the transit node. The No-SIDs field of the DA indicates the number of the SIDs encoding the sub-trees under the transit node and the SIDs following. The multicast SIDs of the next hop nodes are the first B multicast SIDs of the segment list in the packet.

[0092] For example, the No-Branches field (which has value of 2) of DA = Pl-m indicates that there are 2 branches (or next hops) from node Pl. The No-SIDs field (which has value of 7) of the DA = Pl-m indicates that there are 7 SIDs for the 2 sub-trees from/under node Pl. The first multicast SID (P2-m) of the segment list is the SID of the next hop node (P2). The second multicast SID (P3-m) of the segment list is the SID of the next hop node (P3).

[0093] Pl receives the packet shown in FIG. 8.

[0094] After the multicast SIDs of the next hop nodes, there are B sequences of SIDs for those B sub-trees. The No-SIDs field (which has value of SI) of the first multicast SID of the next hop nodes indicates that there are SI SIDs from the first SIDs sequence to the last one. The No-SIDs field (which has value of S2) of the second multicast SID of the next hop nodes indicates that there are S2 SIDs from the second SIDs sequence to the last one, and so on.

[0095] For example, there are 2 sequences of SIDs for the 2 sub-trees from/under node Pl after the multicast SIDs P2-m and P3-m of the next hop nodes P2 and P3. The No-SIDs field of P2-m (the first multicast SID of the next hop nodes) has value of 5, indicating that there are 5 SIDs from the first SIDs sequence to the last one, which are PEl-m, PE2-m, P4-m, PE3-m and PE4-m. The No-SIDs field of P3-m (the second multicast SID of the next hop nodes) has value of 3, indicating that there are 3 SIDs from the second SIDs sequence to the last one, which are P4-m, PE3-m and PE4-m.

[0096] The transit node duplicates the packet for each sub-tree or next hop node from/under the transit node, sets the DA of the packet to the multicast SID of the next hop node along the subtree, sets SL in SRH to the No-SIDs in DA, and sends the packet to the DA.

[0097] For example, node Pl duplicates the packet for next hop P2 or the first sub-tree towards PEI and PE2, sets DA to P2-m (multicast SID of next hop P2), sets SL in SRH to 5, and sends the packet to the DA (i.e., P2).

[0098] Node Pl duplicates the packet for next hop P3 or the second sub-tree towards PE3 and PE4, sets DA to P3-m (multicast SID of next hop P3), sets SL in SRH to 3, and sends the packet to the DA (i.e., P3).

[0100] After receiving the packet, Pl duplicates the packet shown in FIG. 9 for sending to P2 and P3. Pl sets DA of the duplicated packet for P2 to P2-m, sets SL in SRH to 5 (the No-SIDs in DA), and sends P2 the packet shown in FIG. 10. The multicast SIDs from the top of the segment list in the SRH, which is indicated by SL = 5, are shown in the FIG. Note that the segment list in the SRH is not changed and still contains P2-m and P3-m (not shown in the FIG). Pl sets DA of the duplicated packet for P3 to P3-m, sets SL in SRH to 3 (the No-SIDs in DA), and sends P3 the packet shown in FIG. 10. The multicast SIDs from the top of the segment list in the SRH, which is indicated by SL = 3, are shown in the FIG. Note that the segment list in the SRH is not changed and still contains P2-m, P3-m, PEl-m and PE2-m (not shown in the FIG). P2 receives the packet shown in FIG. 11. P2 duplicates packet for PEI, sets DA to PEl-m, sets SL in SRH to 0 (the No-SIDs in DA), and sends the packet shown in FIG. 12 to PEI. P2 duplicates packet for PE2, sets DA to PE2-m, sets SL in SRH to 0 (the No-SIDs in DA), and sends the packet shown in FIG. 13 to PE2.

[0101] The implementation of Multicast SID behavior is executed by transit node N when the DA of the packet received by N is N’s Multicast SID. It is a variant of the Endpoint behavior in Section 4.1 of Internet Engineering Task Force (IETF) document Request for Comments (RFC) 8986 entitled “Segment Routing over IPv6 (SRv6) Network Programming” by C. Filsfils, et al., February 2021, with the change from S13 - S15 to S13a - SI 5b. This change duplicates the packet for each of B next hop nodes, branches, or sub-trees from/under N, sends the duplicated packet to the next hop node along the branch through setting the DA of the duplicated packet to the multicast SID of the next hop node, sets SL in SRH to the No-SIDs in DA to pop SIDs and have the SIDs sequence encoding the sub-trees from/under the next hop at the top of the segment list in SRH, and submits the duplicated packet to the egress IPv6 FIB lookup for transmission to the new destination DA (i.e., the next hop). See FIG. 14.

[0102] When an egress node of a SR P2MP path receives a packet transported by the P2MP path, the DA of the packet is the Multicast SID of the egress node and SL = 0. The egress node proceeds to process the next header in the packet (refer to S03 in Section 4.1 of RFC 8986).

[0103] FIG. 15 illustrates an example of an IPv6 Header using G-SRv6. For simplicity, 64 bits for Common Prefix, 16 bits for Node ID, 8 bits for the number of branches (No-Branches) and 8 bits for the number of SIDs (No-SIDs) are used when G-SRv6 compression method is applied for <Pl-m, P2-m, P3-m, PEl-m, PE2-m, P4-m, PE3-m, PE4-m> at ingress node PE8 in FIG. 1. The Destination Address (DA) as illustrated contains the Common Prefix of 64 bits, node Pl’s ID of 16 bits, the value 2 for the number of branches (No-Branches) of 8 bits, and the value 7 for the number of SIDs (No-SIDs) of 8 bits. The IPv6 header is shown in FIG. 16. In this example, ingress node PE8 sends a packet with the IPv6 header to the DA.

[0104] FIG. 17 is a schematic diagram of a routing device 1700 according to an embodiment of the disclosure. The routing device 1700 is suitable for implementing the disclosed embodiments as described herein. In an embodiment, the routing device 1700 may be a router, a switch, a node, or another communication device configured to process Internet traffic.

[0105] The routing device 1700 comprises ingress ports 1710 (or input ports 1710) and receiver units (Rx) 1720 for receiving data; a processor, logic unit, or central processing unit (CPU) 1730 to process the data; transmitter units (Tx) 1740 and egress ports 1750 (or output ports 1750) for transmitting the data; and a memory 1760 for storing the data. The routing device 1700 may also comprise optical-to-electrical (OE) components and electrical-to-optical (EO) components coupled to the ingress ports 1710, the receiver units 1720, the transmitter units 1740, and the egress ports 1750 for egress or ingress of optical or electrical signals.

[0106] The processor 1730 is implemented by hardware and software. The processor 1730 may be implemented as one or more CPU chips, cores (e.g., as a multi-core processor), filed programmable gate arrays (FPGAs), application-specific integrated circuits (ASICs), and digital signal processors (DSPs). The processor 1730 is in communication with the ingress ports 1710, receiver units 1720, transmitter units 1740, egress ports 1750, and memory 1760. The processor 1730 comprises a routing module 1770. The routing module 1770 implements the disclosed embodiments described above. For instance, the routing module 1770 implements, processes, prepares, or provides the various coding operations. The inclusion of the routing module 1770 therefore provides a substantial improvement to the functionality of the routing device 1700 and effects a transformation of the routing device 1700 to a different state. Alternatively, the routing module 1770 is implemented as instructions stored in the memory 1760 and executed by the processor 1730.

[0107] The memory 1760 may comprise one or more disks, tape drives, and solid-state drives and may be used as an over-flow data storage device, to store programs when such programs are selected for execution, and to store instructions and data that are read during program execution. The memory 1760 may be, for example, volatile and/or non-volatile and may be a read-only memory (ROM), random access memory (RAM), ternary content-addressable memory (TCAM), and/or static random-access memory (SRAM).

[0108] While several embodiments have been provided in the present disclosure, it should be understood that the disclosed systems and methods might be embodied in many other specific forms without departing from the spirit or scope of the present disclosure. The present examples are to be considered as illustrative and not restrictive, and the intention is not to be limited to the details given herein. For example, the various elements or components may be combined or integrated in another system or certain features may be omitted, or not implemented.

[0109] In addition, techniques, systems, subsystems, and methods described and illustrated in the various embodiments as discrete or separate may be combined or integrated with other systems, modules, techniques, or methods without departing from the scope of the present disclosure. Other items shown or discussed as coupled or directly coupled or communicating with each other may be indirectly coupled or communicating through some interface, device, or intermediate component whether electrically, mechanically, or otherwise. Other examples of changes, substitutions, and alterations are ascertainable by one skilled in the art and could be made without departing from the spirit and scope disclosed herein.