Source routed multicast LSP

• US 20070189291A1
• Filed: 02/12/2007
• Published: 08/16/2007
• Est. Priority Date: 02/15/2006
• Status: Active Grant

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Redback Networks Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Tian, Albert Jining
• Granted Patent: US 7,801,136 B2
• Time in Patent Office: Days
• 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, comprising:

receiving at a first node 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, duplicating the first packet into a second packet;

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

processing the first and third packets based on a label on the top of the label stack of the first and third packets respectively.

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 processing the first label of the first packet comprises:

swapping the 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 processing the third packet comprises transmitting the third packet 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 8, wherein forming the label stack comprises:

arranging substantially all nodes involved in the plurality of 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.

10. The method of claim 9, 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.

11. A machine-readable medium for storing instructions, when executed by a machine, cause the machine to perform a method, the method comprising:

receiving at a first node 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, duplicating the first packet into a second packet;

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

processing the first and third packets based on a label on the top of the label stack of the first and third packets respectively.

12. The machine-readable medium of claim 11, 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.

13. The machine-readable medium of claim 11, wherein processing the first label of the first packet comprises:

swapping the 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.

14. The machine-readable medium of claim 13, 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.

15. The machine-readable medium of claim 14, wherein processing the third packet comprises transmitting the third packet 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.

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

17. The machine-readable medium of claim 16, 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.

18. The machine-readable medium of claim 11, 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.

19. The machine-readable medium of claim 18, wherein forming the label stack comprises:

arranging substantially all nodes involved in the plurality of 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.

20. The machine-readable medium of claim 19, 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.

21. A computer implemented method, comprising:

receiving at a first node 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, popping at least two labels from the top of the label stack of the first packet forming a second packet;

processing the second packet based on a next label on the top of the label stack of the second packet; and

transmitting the second packet to a second node indicated by the next label on the top of the label stack in accordance with an MPLS protocol, wherein the second packet is processed by the second node based on information associated with the next label on the top of the label stack of the second packet.

22. A computer implemented method, comprising:

arranging a plurality of nodes involved in a plurality of 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 intermediate nodes between the parent node and the child node.

23. The method of claim 22, further comprising converting the LOSR into a stack of labels suitable for MPLS routing, including

encoding a node that is not the last node in the array with a branch label having a copy and pop operation, causing a duplicated packet to be generated and one or more labels to be popped from the label stack;

and

encoding a node that is the last element with a pop label having a pop operation for popping at least two labels.