Source routed multicast LSP

• US 7,801,136 B2
• Filed: 02/12/2007
• Issued: 09/21/2010
• Est. Priority Date: 02/15/2006
• Status: Active Grant

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Inventors: Tian, Albert Jining
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): NGUYEN, MINH TRANG T
• Application Number:
  US11/706,125
• Publication Number:
  US 20070189291A1
• Time in Patent Office: 1,317 Days
• Field of Search: None
• US Class Current: 370/390
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

Source routed multicast LSP is described herein. In one embodiment, when a first node receives a first packet having a label stack including a plurality of labels compatible with MPLS (multi-protocol label switching), in response to a first label on a top of the label stack, the first packet is duplicated into a second packet. In addition, at least two labels are popped from the top of the label stack of the second packet forming a third packet. Thereafter, the first and third packets are processed based on a label on the top of the label stack of the first and third packets respectively. Other methods and apparatuses are also described.

Claims

1. A computer implemented method performed in a first node for multi-casting a packet, the method comprising:

receiving a first packet having a label stack including a plurality of labels compatible with MPLS (multi-protocol label switching), wherein the label stack is formed in a hierarchical structure based on levels of the label stack, including arranging substantially all nodes involved in a plurality of label switch paths (LSPs) into an array according to the hierarchical structure, from root to bottom and from left to right, and

encoding the hierarchical structure into an offset based level order sequential representation (LOSR), wherein a pointer from a parent node to a child node is encoded as an offset representing a number of elements between the parent node and the child node;

duplicating by a processor the first packet into a second packet as a function of contents of a topmost label of the label stack;

forming by the processor a third packet by removing at least two labels from the top of the label stack of the second packet; and

transmitting by the processor the first and third packets to different destination nodes as a function of respective contents of the topmost labels of the first and third packets.

2. The method of claim 1, further comprising maintaining within the first node a label information base (LIB) to store information related to at least a portion of the plurality of labels with respect to one or more label switch paths (LSPs) associated with the first node.

3. The method of claim 1, wherein transmitting the first packet comprises:

swapping a first label on the top of the label stack of the first packet with a second label to form a fourth packet; and

processing the fourth packet based on the second label of the label stack.

4. The method of claim 3, wherein processing the fourth packet comprises transmitting the fourth packet to a second node associated with the second label, wherein the fourth packet is processed by the second node according to information related to the second label and stored in a LIB of the second node.

5. The method of claim 4, wherein the third packet is transmitted to a third node associated with a label on a top of the label stack of the third packet, wherein the third packet is processed by the third node according to information related to the third label and stored in a LIB of the third node.

6. The method of claim 5, wherein the second and third nodes are different nodes associated with different LSPs (label switch paths).

7. The method of claim 6, wherein the first packet is a multicast packet intended to be transmitted from an origin node to the second and third nodes via the different LSPs, and wherein the origin node transmits a single copy of the first packet to the first node.

8. The method of claim 1, further comprising forming the label stack for a plurality of label switch paths (LSPs) via a plurality of label switch routers (LSRs) according to a hierarchical structure based on levels of the label stack.

9. The method of claim 1, further comprising converting the LOSR into a stack of labels suitable for MPLS routing, wherein an element that is not the last element in the array is encoded with a branch label having a copy and pop operation, and wherein an element that is the last element is encoded as a pop operation for popping multiple labels.

10. A non-transitory computer-readable storage medium for storing instructions, when executed by a machine, cause the machine to perform a method in a first node for multi-casting a packet, the method comprising:

receiving a first packet having a label stack including a plurality of labels compatible with MPLS (multi-protocol label switching), wherein the label stack is formed in a hierarchical structure based on levels of the label stack, including arranging substantially all nodes involved in a plurality of label switch paths (LSPs) into an array according to the hierarchical structure, from root to bottom and from left to right, and

encoding the hierarchical structure into an offset based level order sequential representation (LOSR), wherein a pointer from a parent node to a child node is encoded as an offset representing a number of elements between the parent node and the child node;

duplicating the first packet into a second packet as a function of contents of a topmost label of the label stack;

forming a third packet by removing at least two labels from the top of the label stack of the second packet; and

transmitting the first and third packets to different destination nodes as a function of respective contents of the topmost labels of the first and third packets.

11. The computer readable storage medium of claim 10, wherein the method further comprises maintaining within the first node a label information base (LIB) to store information related to at least a portion of the plurality of labels with respect to one or more label switch paths (LSPs) associated with the first node.

12. The computer readable storage medium of claim 10, wherein transmitting the first packet comprises:

swapping a first label on the top of the label stack of the first packet with a second label to form a fourth packet; and

processing the fourth packet based on the second label of the label stack.

13. The computer readable storage medium of claim 12, wherein processing the fourth packet comprises transmitting the fourth packet to a second node associated with the second label, wherein the fourth packet is processed by the second node according to information related to the second label and stored in a LIB of the second node.

14. The computer readable storage medium of claim 13, wherein the third packet is transmitted to a third node associated with a label on a top of the label stack of the third packet, wherein the third packet is processed by the third node according to information related to the third label and stored in a LIB of the third node.

15. The computer readable storage medium of claim 14, wherein the second and third nodes are different nodes associated with different LSPs (label switch paths).

16. The computer readable storage medium of claim 15, wherein the first packet is a multicast packet intended to be transmitted from an origin node to the second and third nodes via the different LSPs, and wherein the origin node transmits a single copy of the first packet to the first node.

17. The computer readable storage medium of claim 10, wherein the method further comprises forming the label stack for a plurality of label switch paths (LSPs) via a plurality of label switch routers (LSRs) according to a hierarchical structure based on levels of the label stack.

18. The computer readable storage medium of claim 17, wherein the method further comprises converting the LOSR into a stack of labels suitable for MPLS routing, wherein an element that is not the last element in the array is encoded with a branch label having a copy and pop operation, and wherein an element that is the last element is encoded as a pop operation for popping multiple labels.