Load Balancing Manipulation of Packet Flows Within a Transport Conduit

• US 20090201811A1
• Filed: 02/10/2008
• Published: 08/13/2009
• Est. Priority Date: 02/10/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Filsfils, Clarence, Bryant, Stewart Frederick, Townsley, William Mark, Ward, David Delano
• Granted Patent: US 8,868,775 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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/24 Multipath
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Disclosed are, inter alia, methods, apparatus, computer-readable media, mechanisms, and means for load balancing manipulation of packet flows within a transport conduit (e.g., a tunnel, pseudo wire, etc.), typically using a load balancing value which is independent of standard routing-based parameters (e.g., source address, destination address, source port, destination port, protocol type, etc.). A load balancing value is included in encapsulated packets transported across a network using a transport conduit. This load balancing value can be used to load balance the individual flows/microflows within the transport conduit.

Claims

1. An apparatus, comprising:

one or more interfaces configured for sending and receiving packets; and

one or more processing elements configured;

to determine a transport conduit over which to forward a packet in a network;

to determine a load balancing value for load balancing operations performed by packet switching devices in the network providing the transport conduit; and

to forward from an interface of said interfaces the packet encapsulated for transportation through the transport conduit, with said encapsulated packet including said determined load balancing value.

2. The apparatus of claim 1, wherein the transport conduit comprises a tunnel;

and wherein the load balancing value is selected for load balancing packet flows within the tunnel.

3. The apparatus of claim 2, wherein said load balancing value is inserted in a portion of a session identification field of said encapsulation of the packet.

4. The apparatus of claim 3, wherein a portion of the session identification field not including the load balancing value identifies the session within the tunnel for the packet.

5. The apparatus of claim 2, wherein said tunnel is a generic routing encapsulation (GRE) tunnel, and the load balancing value is included in the Key field.

6. The apparatus of claim 1, wherein the transport conduit comprises a pseudo wire;

and wherein the load balancing value is selected for load balancing microflows within the pseudo wire.

7. The apparatus of claim 1, wherein the load balancing value is added to a load balancing field of said encapsulation of the packet.

8. The apparatus of claim 1, wherein the load balancing value is a pseudo-random number.

9. The apparatus of claim 1, wherein the packet switching device is configured to insert the load balancing value in a field independent of other functionality in said encapsulation of the packet.

10. The apparatus of claim 1, wherein the packet switching device is configured to add the load balancing value in a Multiprotocol Label Switching (MPLS) label in said encapsulation of the packet.

11. The apparatus of claim 10, wherein the packet switching device is configured to add the MPLS label to the bottom of a label stack including a plurality of MPLS labels in said encapsulation of the packet.

12. The apparatus of claim 1, wherein the packet switching device is configured to insert the load balancing value in a field for use by one or more of said packet switching devices in the network providing the transport conduit for only load balancing purposes.

13. A method performed by a particular packet switching device, the method comprising:

determining a transport conduit over which to forward a packet to a second packet switching device in a network;

determining a load balancing value for load balancing operations performed by packet switching devices in the network providing the transport conduit; and

forwarding the packet including said determined load balancing value over said determined transport conduit.

14. The method of claim 13, wherein the transport conduit is a tunnel;

and wherein said operation of determining the load balancing value includes selecting the load balancing value for load balancing packet flows within the tunnel.

15. The method of claim 13, wherein the transport conduit is a pseudo wire;

and wherein said operation of determining the load balancing value includes selecting the load balancing value for load balancing microflows within the pseudo wire.

16. The method of claim 13, wherein endpoints of the transport conduit are the particular packet switching device and the second packet switching device.

17. An apparatus, comprising:

means for determining a transport conduit over which to forward a packet to a second packet switching device in a network;

means for determining a load balancing value for load balancing operations performed by packet switching devices in the network providing the transport conduit; and

means for forwarding the packet including said determined load balancing value over said determined transport conduit.

18. A method for operating a first network edge packet switching device of a network, the first network edge packet switching device performing packet encapsulation for transporting packets through a transport conduit across a network to a second network edge packet switching device, the method comprising:

for each particular packet flow of a plurality of packet flows being communicated from the first network edge packet switching device to the second network edge packet switching device over the transport conduit;

for each particular packet of the particular packet flow;

encapsulating said particular packet according to the protocol of said transport conduit and forwarding said particular packet from the first network edge packet switching device, wherein said encapsulation of said particular packet includes a load balancing value for load balancing performed by one or more packet switching devices along at least one of a plurality of active paths in the transport conduit;

wherein the load balancing value is the same for all said packets of a same packet flow of the plurality of packet flows, and is different for at least two different packet flows of the plurality of packet flows.

19. The method of claim 18, wherein the load balancing value is a pseudo-random number.

20. The method of claim 18, the first network edge packet switching device inserts the load balancing value in a field independent of other functionality in said transport conduit encapsulation.

21. The method of claim 18, wherein the first network edge packet switching device pushes a Multiprotocol Label Switching (MPLS) label including the load balancing value onto the bottom of a label stack including a plurality of MPLS labels in said transport conduit encapsulation.

22. The method of claim 18, wherein said load balancing value is inserted in a portion of a session identification field of said transport conduit encapsulation;

and wherein the first network edge packet switching device and the second network edge packet switching device use the portion of the session identification field not including the load balancing value included in each said packet as the identifier of the session within the transport conduit for each said packet.

23. A method performed in a network, the network including a first network edge packet switching device, a second network edge packet switching device, a midpoint packet switching device, wherein the midpoint packet switching device is communicatively coupled to both the first network edge packet switching device and the second network edge packet switching device including a plurality of paths between the midpoint packet switching device and the second network edge packet switching device, the method comprising:

the first network edge packet switching device determining a load balancing value designed to add entropy in the load balancing of packet traffic in the network, and adding the load balancing value to each packet of a stream of packets in a packet flow being routed through the midpoint packet switching device and the second network edge packet switching device;

the midpoint packet switching device receiving each packet of the stream of packets in the packet flow and determining which particular path of the plurality of paths between the midpoint packet switching device and the second network edge packet switching device based on the load balancing value, and sending each packet of the stream of packets; and

the second network edge packet switching device striping the load balancing value from the packet, and forwarding the packet without the load balancing value to another device.

24. The method of claim 23, wherein each packet of the stream of packets in the packet flow is being sent through a transport conduit from the first network edge packet switching device to the second network edge packet switching device, with the first network edge packet switching device adding transport conduit encapsulation to each said packet and the second network edge packet switching device removing said transport conduit encapsulation from each said packet.

25. The method of claim 23, wherein the load balancing value is in a well-defined field designated for load balancing purposes.