Distribution of label switched packets

• US 7,277,386 B1
• Filed: 11/12/2002
• Issued: 10/02/2007
• Est. Priority Date: 11/12/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Sheth, Nischal, Ferguson, Dennis C, Kuwabara, Ken
• Primary Examiner(s): Jagannathan; Melanie
• Application Number:
  US10/293,785
• Time in Patent Office: 1,785 Days
• Field of Search: 370/389, 370/392, 370/395.1, 370/400, 370/409, 370/229
• US Class Current: 370/230
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

Techniques are described for distribution of label switched packets, such as multiprotocol label switched (MPLS) packets, across multiple physical data paths. The techniques may, for example, be used to load balance the label switched packets across an aggregated link having two or more logically associated physical interconnects. A network device, for example, includes an interface card to receive packets associated with a common label switched path (LSP), and a control unit to distribute the packets across multiple paths. The network device may include label data that maps ranges of labels, such as MPLS labels, to types of payloads carried by the label switched packets. In accordance with the label data, the control unit extracts flow information from the label switched packets and distributes the label switched packets across the paths based on the flow information. The control unit may generate hash values from the flow information, the labels, or combinations thereof, to control distribution of the label switched packets.

Claims

1. A method comprising:

receiving packets associated with a common label switched path (LSP);

reading a first label of each packet;

accessing label data that associates ranges of labels with different types of communication protocols, wherein the label data includes at least one predefined range defining that a packet is a multi-label packet having a plurality of labels;

determining whether each of the packets has multiple labels when the first label is within the predefined range; and

distributing the packets across multiple paths based on the determination.

2. The method of claim 1, wherein for those packets having a single label, distributing the packets comprises:

reading the label of each of the packets;

determining payload types for the packets based on the label associated with each packet; and

distributing the packets based on the payload types for the packets.

3. The method of claim 2, further comprising:

extracting flow information from the packets based on the determined payload types for the packets;

generating hash values from the flow information of the packets; and

distributing the packets across the multiple paths based on the hash values.

4. The method of claim 1, wherein for those packets in which the first label of the packet is within the predetermined range, distributing the packets comprises:

reading multiple labels from each of the packets;

generating a hash value for each of the packets based on the multiple labels of the respective packet; and

distributing the packets across the multiple paths based on the hash values.

5. The method of claim 1, wherein for any number of labels in each of the packets, distributing the packets comprises distributing the packets across multiple physical interconnects of an aggregated network link.

6. The method of claim 1, wherein, for an number of labels in each of the packets, distributing the packets comprises distributing the packets across multiple internal data paths of a network device.

7. The method of claim 1, wherein the packets comprise multiprotocol label switched (MPLS) packets.

8. A method comprising:

receiving a packet having a label in accordance with a label switching protocol;

reading the first label of the packet;

accessing label data that associates ranges of labels with different types of communication protocols, wherein the label data includes at least one predefined range defining that a packet is a multi-label packet having a plurality of labels;

determining that the packet has multiple labels when the first label is within the predefined range;

when the packet has a single label, extracting flow information from a payload of the packet based on the label and distributing the packet to one of a plurality of paths based on the extracted flow information; and

when the first label is within the predetermined range, distributing the packet to one of a plurality of paths based on the multiple labels without regard to the payload of the packet.

9. The method of claim 8, wherein when the packet has a single label, further comprising:

determining a payload type of the packet based on the label;

extracting the flow information from the packet based on the determined payload type;

generating a hash value from the flow information; and

distributing the packet to one of a plurality of paths based on the hash value.

10. The method of claim 9, wherein determining a payload type comprises:

accessing label data that associates ranges of labels with different types of payloads; and

identifying one of the ranges for the label of the packet.

11. The method of claim 9, wherein generating a hash value comprises applying a hash function to at least a portion of the flow information and the label.

12. The method of claim 9, wherein distributing the packet comprises distributing the packet across one of a physical interconnect of an aggregated network link, a path within a network, and an internal data path of a network device.

13. The method of claim 8, wherein the packet comprises a multiprotocol label switched (MPLS) packet.

14. The method of claim 8, wherein, for each of the packets, when the first label is within the predetermined range, distributing the packet comprises:

applying a hash function to the multiple labels to generate a hash value; and

distributing the packet based on the hash value.

15. The method of claim 14, wherein distributing the packet comprises:

selecting one of a plurality of physical interconnects of an aggregated network link based on the hash value; and

forwarding the label switched packet along the selected physical interconnect.

16. The method of claim 14, wherein distributing the packet comprises:

selecting one of a plurality of parallel data paths within a network device based on the hash value; and

relaying the label switched packet within the network device along the selected data path.

17. The method of claim 14, wherein distributing the packet comprises:

selecting one of a plurality of packet-forwarding engines within a router based on the hash value; and

forwarding the label switched packet along a route within the network using the selected packet-forwarding engine.

18. The method of claim 8, wherein the packet comprises a multiprotocol label switched (MPLS) packet.

19. A method comprising:

receiving a data unit from a network device;

determining a type of communication protocol for the data unit;

accessing label data that associates ranges of labels with different types of communication protocols, wherein the label data includes at least one predefined range to indicate that a data unit has a plurality of labels;

selecting a label based on the type of communication protocol and whether the data unit has multiple labels;

pre-pending the selected label to the data unit to form a label switched packet in accordance with a label switching protocol; and

forwarding the packet along a label switched path in accordance with the label.

20. The method of claim 19, wherein selecting a label comprises:

identifying one of the ranges based on the communication protocol of the data unit and whether the data unit has multiple labels; and

selecting a label within the identified range.

21. The method of claim 19, wherein receiving the data unit comprises receiving a packet conforming to the Internet Protocol.

22. The method of claim 19, wherein receiving the data unit comprises receiving a cell conforming to the Asynchronous Transfer Mode protocol.

23. The method of claim 19, wherein receiving the data unit comprises receiving a tunneled Ethernet frame.

24. The method of claim 19, further comprising:

extracting flow information from the data unit based on the determined communication protocol;

generating a hash value from the flow information; and

distributing the label switched packet to one of a plurality of paths based on the hash value.

25. The method of claim 24, wherein distributing the label switched packet comprises distributing the label switched packet across one of a physical interconnect of an aggregated network link and an internal data path of a network device.

26. The method of claim 19, wherein the label switched packet comprises a multiprotocol label switched (MPLS) packet.

27. A network device comprising:

a computer-readable medium storing label data that associates ranges of labels with different types of communication protocols, wherein the label data includes at least one predefined range defining that a packet is a multi-label packet having a plurality of labels;

an interface card to receive packets associated with a common label switched path (LSP); and

a control unit to distribute the packets across multiple paths, wherein the control unit reads a first label of each of the packets and determines whether each of the packets has multiple labels when the first label is within the predefined range.

28. The network device of claim 27, further comprising label data that maps ranges of labels to payload types, wherein for those packets having a single label, the control unit distributes the packets based on the payload types of the packets in accordance with the label data.

29. The network device of claim 28, wherein for those packets having a single label, the control unit extracts flow information from the packets based on the determined payload types for the packets, and distributes the packets across the multiple paths based on the flow information.

30. The network device of claim 29, wherein for those packets having a singe label, the control unit generates hash values from the flow information of the packets, and distributes the packets across the multiple paths based on the hash values.

31. The network device of claim 27, wherein for those packets having multiple labels, the control unit reads the multiple labels from each of the packets, generates a hash value for each of the packets based on the multiple labels of the respective packet, and distributes the packets across the multiple paths based on the hash values.

32. The network device of claim 27, further comprising an interface card to receive multiple physical interconnects of an aggregated network link, wherein the control unit distributes the packets across the multiple physical interconnects.

33. The network device of claim 27, wherein the control unit distributes the packets across multiple internal data paths of the network device.

34. The network device of claim 27, wherein the packets comprise multiprotocol label switched (MPLS) packets.

35. A computer-readable storage medium comprising instructions that cause a processor to:

receive packets associated with a common label switched path (LSP);

access label data that associates ranges of labels with different types of communication protocols, wherein the label data includes at least one predefined range defining that a packet is a multi-label packet having a plurality of labels;

read a first label of each packet;

determine that a packet has multiple labels when the first label is within the predefined range; and

distribute the packets across multiple paths.

36. The computer-readable medium of claim 35, further comprising, for those packets having a single label instructions to cause a processor to:

read the label of each of the packets;

determine payload types for the packets based on the label associated with each packet; and

distribute the packets based on the payload types for the packets.

37. The computer-readable medium of claim 36, further comprising, for those packets having a single label, instructions to cause a processor to:

extract flow information from the packets based on the determined payload types for the packets;

generate hash values from the flow information of the packets; and

distribute the packets across the multiple paths based on the hash values.

38. The computer-readable medium of claim 35, further comprising, for those packets having multiple labels, instructions to cause a processor to:

read multiple labels from each of the packets;

generate a hash value for each of the packets based on the multiple labels of the respective packet; and

distribute the packets across the multiple paths based on the hash values.

39. The computer-readable medium of claim 35, further comprising instructions to cause a processor to distribute the packets across one of a physical interconnect of an aggregated network link, a path within a network, and an internal data path of a network device.

40. The computer-readable medium of claim 35, wherein the packets comprise multiprotocol label switched (MPLS) packets.

41. A computer-readable storage medium comprising label data that associate ranges of labels with types of payloads of label switched packets, wherein the data defines a first label range to indicates that a label switched packet include a plurality of labels, and wherein the first label range directs a router to control distribution of the label switched packets across multiple physical data paths by application of a hash function to the multiple labels without regard of the payloads of the label switched packets.

42. The computer-readable medium of claim 41, wherein the label data associates respective ranges of the labels with payloads conforming to the Internet Protocol version 4 (IPv4), the Internet Protocol version 6 (IPv6), the Asynchronous Transfer Mode (ATM), and tunneled Ethernet.

43. The computer-readable medium of claim 41, wherein the label data defines a respective range of labels for packets carrying more than one label.

44. The computer-readable medium of claim 41, wherein the packets comprise multiprotocol label switched (MPLS) packets.