ADAPTIVE LOAD BALANCING IN PACKET PROCESSING

• US 20160182380A1
• Filed: 04/07/2015
• Published: 06/23/2016
• Est. Priority Date: 12/22/2014
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: MEHRA, Ashwani Kumar, ANAND, Prashant
• Granted Patent: US 10,148,575 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers

Abstract

A method of forwarding packets in a network device is disclosed. The method comprises assigning a packet to a first packet processing thread; and determining a state of the first packet processing thread. Responsive to determining that the state of the first packet processing thread is a backlogged state, mapping the packet to a second packet processing thread from a pool of packet processing threads based on a load balancing scheme, wherein the pool of packet processing threads includes a subset of threads from the plurality of packet processing threads, and the state of each one of the packet processing threads from the pool is the backlogged state, processing the packet in the second packet processing thread, and forwarding the packet according to a predetermined order that is based on a position of the packet relative to positions of other packets at their receipt in the network device.

Claims

1. A method of forwarding packets in a network device, the method comprising:

receiving a packet at the network device;

assigning the packet to a first packet processing thread from a plurality of packet processing threads;

determining a state of the first packet processing thread, wherein the state was set based on a monitoring of a length of a queue of the first packet processing thread, and wherein the state is determined to be one of a plurality of states including a backlogged state and a normal state;

responsive to determining that the state of the first packet processing thread is a normal state, performing the following;

mapping the packet to the first packet processing thread,

processing the packet in the first packet processing thread, and

forwarding the packet; and

responsive to determining that the state of the first packet processing thread is a backlogged state, performing the following;

mapping the packet to a second packet processing thread from a pool of packet processing threads based on a load balancing scheme, wherein the pool of packet processing threads includes a subset of packet processing threads from the plurality of packet processing threads, and the state of each one of the packet processing threads from the pool is the backlogged state,

processing the packet in the second packet processing thread, and

forwarding the packet according to a predetermined order, wherein the predetermined order is based on a position of the packet relative to positions of other packets at their receipt in the network device.

2. The method of claim 1, wherein the plurality of states additionally includes a transition state.

3. The method of claim 2, the method further comprising:

responsive to determining that the state of the first packet processing thread is the transition state, performing the following;

mapping the packet to the first packet processing thread,

processing the packet in the first packet processing thread, and

forwarding the packet according to the predetermined order.

4. The method of claim 1, wherein the packet is received after receipt of a preceding packet at the network device and wherein forwarding the packet according to the predetermined order further includes:

determining whether the preceding packet is still to be processed by one of the plurality of packet processing threads;

responsive to determining that the preceding packet is still to be processed, storing the packet in a buffer; and

outputting the packet following the processing and outputting of the preceding packet.

5. The method of claim 4, wherein forwarding the packet according to the predetermined order further includes:

determining that the packet has a load balancing flag set prior to storing the packet in the buffer.

6. The method of claim 1, further comprising:

assigning a unique sequence number to the packet, and

wherein forwarding the packet is performed according to the unique sequence number.

7. The method of claim 1, wherein the length of the queue of the first packet processing thread is monitored in part by measuring an exponentially weighted moving average (EWMA) of the length of the queue and comparing the measurement with a threshold.

8. The method of claim 1, wherein the pool of packet processing threads includes the first packet processing thread.

9. A non-transitory machine-readable storage medium that provides instructions, which when executed by a processor of a network device, cause said processor to perform operations comprising:

assigning a received packet to a first packet processing thread from a plurality of packet processing threads;

determining a state of the first packet processing thread, wherein the state was set based on a monitoring of a length of a queue of the first packet processing thread, and wherein the state is determined to be one of a plurality of states including a backlogged state and a normal state;

responsive to determining that the state of the first packet processing thread is a normal state, performing the following;

mapping the packet to the first packet processing thread,

processing the packet in the first packet processing thread, and

causing the packet to be forwarded; and

responsive to determining that the state of the first packet processing thread is a backlogged state, performing the following;

mapping the packet to a second packet processing thread from a pool of packet processing threads based on a load balancing scheme, wherein the pool of packet processing threads includes a subset of packet processing threads from the plurality of packet processing threads, and the state of each one of the packet processing threads from the pool is the backlogged state,

processing the packet in the second packet processing thread, and

causing the packet to be forwarded according to a predetermined order, wherein the predetermined order is based on a position of the packet relative to positions of other packets at their receipt in the network device.

10. The non-transitory machine-readable storage medium of claim 9, wherein the plurality of states additionally includes a transition state.

11. The non-transitory machine-readable storage medium of claim 10, wherein the operations further comprise:

responsive to determining that the state of the first packet processing thread is the transition state, performing the following;

mapping the packet to the first packet processing thread,

processing the packet in the first packet processing thread, and

causing the packet to be forwarded according to the predetermined order.

12. The non-transitory machine-readable storage medium of claim 9, wherein the packet is received after receipt of a preceding packet at the network device and wherein causing the packet to be forwarded according to the predetermined order further includes:

determining whether the preceding packet is still to be processed by one of the plurality of packet processing threads;

responsive to determining that the preceding packet is still to be processed, causing the packet to be stored in a buffer; and

causing the packet to be output following the processing and outputting of the preceding packet.

13. The non-transitory machine-readable storage medium of claim 12, wherein causing the packet to be forwarded according to the predetermined order further includes:

determining that the packet has a load balancing flag set prior to causing the packet to be stored in the buffer.

14. The non-transitory machine-readable storage medium of claim 9, wherein the operations further comprise:

assigning a unique sequence number to the packet, and

wherein causing the packet to be forwarded is performed according to the unique sequence number.

15. The non-transitory machine-readable storage medium of claim 9, wherein the length of the queue of the first packet processing thread is monitored in part by measuring an exponentially weighted moving average (EWMA) of the length of the queue and comparing the measurement with a threshold.

16. A network device comprising:

a processor; and

a non-transitory machine readable storage media with code stored therein which when executed by the processor performs the following operations;

assigning a received packet to a first packet processing thread from a plurality of packet processing threads,

determining a state of the first packet processing thread, wherein the state was set based on a monitoring of a length of a queue of the first packet processing thread, and wherein the state is determined to be one of a plurality of states including a backlogged state and a normal state,

responsive to determining that the state of the first packet processing thread is a normal state, performing the following;

mapping the packet to the first packet processing thread,

processing the packet in the first packet processing thread, and

causing the packet to be forwarded, and

responsive to determining that the state of the first packet processing thread is a backlogged state, performing the following;

mapping the packet to a second packet processing thread from a pool of packet processing threads based on a load balancing scheme,

wherein the pool of packet processing threads includes a subset of packet processing threads from the plurality of packet processing threads, and the state of each one of the packet processing threads from the pool is the backlogged state,

processing the packet in the second packet processing thread, and

causing the packet to be forwarded according to a predetermined order, wherein the predetermined order is based on a position of the packet relative to positions of other packets at their receipt in the network device.

17. The network device of claim 16, wherein the packet is received after receipt of a preceding packet at the network device and wherein causing the packet to be forwarded according to the predetermined order further includes:

determining whether the preceding packet is still to be processed by one of the plurality of packet processing threads;

responsive to determining that the preceding packet is still to be processed, causing the packet to be stored in a buffer; and

causing the packet to be output following the processing and outputting of the preceding packet.

18. The network device of claim 16, wherein the operations further comprise:

assigning a unique sequence number to the packet, and

wherein causing the packet to be forwarded is performed according to the unique sequence number.

19. The network device of claim 16, wherein the network device is a forwarding element of a software-defined networking (SDN) system.

20. The network device of claim 16, wherein the network device is a general purpose network device of a system implementing network function virtualization (NFV).