Randomized per-packet port channel load balancing

Patent metadata

Field	Value
Publication number	US-9590914-B2
Application number	US-201414448934-A
Country	US
Kind code	B2
Filing date	Jul 31, 2014
Priority date	Nov 5, 2013
Publication date	Mar 7, 2017
Grant date	Mar 7, 2017

Abstract

Systems, methods, and non-transitory computer-readable storage media for per-packet load balancing in a port channel. The system first maps an incoming traffic flow to queues containing packets to be transmitted through a port channel at the system, the port channel including ports grouped into a single virtual port. Next, the system assigns a port from the port channel to a queue for a predetermined period of time, wherein the port is assigned to the queue based on at least one of a port state and a service history associated with the queue. The system then de-queues at least a portion of the packets in the queue through the port for the predetermined period of time. This load balancing can ensure that traffic is efficiently and fairly load balanced across the links of the port channel, and packets of each queue are not reordered.

First claim

We claim:

1. A method comprising:
mapping, by a network device, an incoming traffic flow to queues containing packets to be transmitted through a port channel at the network device, the port channel comprising a plurality of ports grouped into a single virtual port;
assigning, by the network device, a port from the port channel to a queue of the queues for a predetermined period of time, wherein the port is assigned to the queue based on at least one of a port state and a service history associated with the queue;
assigning a timeout period for the queue;
determining that the queue is active;
determining that the timeout period has not been exceed;
advertising the queue to the port; and
de-queuing, by the network device, at least a portion of the packets in the queue through the port for the predetermined period of time.

2. The method of claim 1 , wherein the port state comprises one of idle or non-idle, and wherein the service history comprises an amount of traffic serviced for that queue by the port channel as defined by a service counter.

3. The method of claim 1 , wherein assigning the port from the port channel to the queue comprises:
selecting the port from the plurality of ports in the port channel for advertising the queue to the port;
advertising the queue to the port to request assignment of the port to the queue for de-queuing the queue through the port; and
accepting an assignment of the port to the queue based on the service history associated with the queue.

4. The method of claim 3 , wherein the port is selected randomly.

5. The method of claim 4 , further comprising grouping the queues into priority groups based on a respective service count of each of the queues, wherein accepting the assignment is based on a priority group associated with the queue.

6. The method of claim 5 , wherein the priority groups are defined by respective ranges of serviced data, wherein a priority group having a lower range of serviced data is assigned a higher priority than priority groups having a higher range of serviced data.

7. The method of claim 5 , wherein the port selects the priority group associated with the queue based on a respective priority of the priority group with respect to other priority groups, and wherein the port selects queues in the priority group for servicing based on a round-robin scheduling.

8. The method of claim 1 , wherein the predetermined period of time is larger than the timeout period assigned for the queues when waiting for service from an assigned port, and wherein the port channel is between two or more chips at the network device, each of the two or more chips being connected to a subset of external physical ports.

9. The method of claim 1 , wherein assigning the port from the port channel to the queue comprises:
sending a first request for assignment of the queue to a different port from the plurality of ports in the port channel;
based on the first request, assigning the queue to the different port;
detecting that the queue has not received service from the different port within the timeout period;
after the timeout period, sending a second request for assignment of the queue to the port; and
receiving an acceptance of the request, the acceptance assigning the queue to the port.

10. The method of claim 1 , further comprising: determining that the queue has waited for servicing from a mapped port for over the timeout period; advertising the queue to a new port based on the timeout period being exceeded, wherein the new port is the port from the port channel; receiving an acceptance to the advertising from the new port; and assigning the new port to the queue based on the acceptance.

11. A system comprising:
a processor; and
a computer-readable storage medium having stored therein instructions which, when executed by the processor, cause the processor to perform operations comprising:
mapping an incoming traffic flow at the system to a queue configured to transmit the incoming traffic flow in the queue through a port channel on the system, the port channel comprising a plurality of ports grouped into a single virtual port;
selecting a port from the plurality of ports to receive a request for an assignment of the queue to the port;
mapping the queue to the port for a predetermined period of time, wherein the queue is mapped to the port based on at least one of a port state and a service history associated with the queue;
assigning a timeout period for the queue;
determining that the queue is active;
determining that the timeout period has not been exceed;
advertising the queue to the port; and
de-queuing at least a portion of packets in the queue through the port for the predetermined period of time.

12. The system of claim 11 , the computer-readable storage medium storing additional instructions which, when executed by the processor, result in an operation further comprising: based on the selecting of the port, sending a query to the port requesting a mapping of the queue to the port.

13. The system of claim 12 , the computer-readable storage medium storing additional instructions which, when executed by the processor, result in operations further comprising: receiving an acceptance to the query; and mapping the queue to the port based on the acceptance.

14. The system of claim 12 , the computer-readable storage medium storing additional instructions which, when executed by the processor, result in an operation further comprising:
receiving a rejection to the query;
based on the rejection, sending a second query to a second port requesting the mapping of the queue to the second port, wherein the second port is selected randomly from the plurality of ports;
receiving an acceptance of the second query from the second port; and
mapping the queue to the second port based on the acceptance.

15. The system of claim 11 , wherein the port state comprises one of idle or non-idle, and wherein the service history comprises an amount of traffic serviced for that queue by the port channel as defined by a service counter.

16. The system of claim 11 , wherein the port is selected randomly from the plurality of ports, and wherein the selecting is configured to prioritize non-idle ports over idle ports.

17. A non-transitory computer-readable storage medium having stored therein instructions which, when executed by a processor, cause the processor to perform operations comprising:
mapping, by a network device, an incoming traffic flow to queues containing packets to be transmitted through a port channel at the network device, the port channel comprising a plurality of ports grouped into a single virtual port;
assigning, by the network device, a port from the port channel to a queue of the queues for a predetermined period of time, wherein the port is assigned to the queue based on at least one of a port state and a service history associated with the queue;
assigning a timeout period for the queue;
determining that the queue is active;
determining that the timeout period has not been exceed;
advertising the queue to the port; and
de-queuing, by the network device, at least a portion of the packets in the queue through the port for the predetermined period of time.

18. The non-transitory computer-readable storage medium of claim 17 , storing additional instructions which, when executed by the processor, result in operations further comprising:
selecting the port from the plurality of ports in the port channel for advertising the queue to the port;
advertising the queue to the port to request m

Assignees

• Cisco Tech Inc

Inventors

• Alizadeh Attar Mohammadreza
• Ma Sha
• Edsall Thomas J

Classifications

• H04L61/103

  across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP] · CPC title

• H04L67/22

  Electricity · mapped topic

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L61/2084

  Electricity · mapped topic

• H04L49/254

  Centralised controller, i.e. arbitration or scheduling · CPC title