Port-based fairness protocol for a network element

Patent metadata

Field	Value
Publication number	US-9705812-B2
Application number	US-201514857100-A
Country	US
Kind code	B2
Filing date	Sep 17, 2015
Priority date	Jan 24, 2013
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

Methods, apparatuses, and computer-readable medium for providing a fairness protocol in a network element are disclosed herein. An example method includes receiving one or more packets at each of a plurality of ingress ports of the network element, and scheduling the packets into a plurality of queues, wherein each of the queues is associated with packets that are sourced from one of the ingress ports. The method also includes monitoring a bandwidth of traffic sourced from each of the ingress ports, identifying a port among the ingress ports that sources a smallest bandwidth of traffic, and arbitrating among the queues when transmitting packets from an egress port of the network element by giving precedence to the identified port that sources the smallest bandwidth of traffic. Additionally, arbitrating among the queues distributes a bandwidth of the egress port equally among the ingress ports.

First claim

What is claimed:

1. A method for providing a fairness protocol in a network element, comprising:
receiving one or more packets at each of a plurality of ingress ports of the network element;
scheduling the one or more packets into a plurality of queues, wherein each of the plurality of queues is associated with packets that are sourced from one of the plurality of ingress ports;
monitoring a bandwidth of traffic sourced from each of the plurality of ingress ports;
identifying a port among the plurality of ingress ports that sources a smallest bandwidth of traffic; and
arbitrating among the plurality of queues when transmitting packets from an egress port of the network element by giving precedence to the identified port that sources the smallest bandwidth of traffic, wherein giving precedence to the identified port comprises transmitting additional packets from a queue associated with packets that are sourced from the identified port, and wherein arbitrating among the plurality of queues distributes a bandwidth of the egress port equally among the plurality of ingress ports.

2. The method of claim 1 , wherein monitoring a bandwidth of traffic sourced from each of the plurality of ingress ports further comprises maintaining a bandwidth table comprising a counter for traffic sourced from each of the plurality of ingress ports.

3. The method of claim 2 , further comprising incrementing the counter for traffic sourced from each of the plurality of ingress ports based on a number of bytes or a number of packets transmitted by each of the plurality of ingress ports.

4. The method of claim 3 , further comprising decrementing the counter for traffic sourced from each of the plurality of ingress ports by at least a fraction of the bandwidth of traffic sourced from each of the plurality of ingress ports every fixed period of time.

5. The method of claim 4 , wherein an amount by which the counter for traffic sourced from each of the plurality of ingress ports is incremented or decremented is weighted according to each of the plurality of ingress ports.

6. The method of claim 1 , wherein monitoring a bandwidth of traffic sourced from each of the plurality of ingress ports further comprises sampling and statistically analyzing traffic sourced from each of the plurality of ingress ports.

7. The method of claim 6 , wherein sampling and statistically analyzing traffic sourced from each of the plurality of ingress ports comprises using an elephant trap.

8. A network element, comprising:
a plurality of ingress ports;
a processing unit;
a memory communicatively connected to the processing unit; and
a program module that executes in the processing unit from the memory and that, when executed by the processing unit, causes the network element to provide a fairness protocol by:
receiving one or more packets at each of the plurality of ingress ports;
scheduling the one or more packets into a plurality of queues, wherein each of the plurality of queues is associated with packets that are sourced from one of the plurality of ingress ports;
monitoring a bandwidth of traffic sourced from each of the plurality of ingress ports;
identifying a port among the plurality of ingress ports that sources a smallest bandwidth of traffic; and
arbitrating among the plurality of queues when transmitting packets from an egress port of the network element by giving precedence to the identified port that sources the smallest bandwidth of traffic, wherein giving precedence to the identified port comprises transmitting additional packets from a queue associated with packets that are sourced from the identified port, and wherein arbitrating among the plurality of queues distributes a bandwidth of the egress port equally among the plurality of ingress ports.

9. The network element of claim 8 , wherein monitoring a bandwidth of traffic sourced from each of the plurality of ingress ports further comprises maintaining a bandwidth table comprising a counter for traffic sourced from each of the plurality of ingress ports.

10. The network element of claim 9 , wherein the program module further causes the network element to provide the fairness protocol by incrementing the counter for traffic sourced from each of the plurality of ingress ports based on a number of bytes or a number of packets transmitted by each of the plurality of ingress ports.

11. The network element of claim 10 , wherein the program module further causes the network element to provide the fairness protocol by decrementing the counter for traffic sourced from each of the plurality of ingress ports by at least a fraction of the bandwidth of traffic sourced from each of the plurality of ingress ports every fixed period of time.

12. The network element of claim 11 , wherein an amount by which the counter for traffic sourced from each of the plurality of ingress ports is incremented or decremented is weighted according to each of the plurality of ingress ports.

13. The network element of claim 8 , wherein monitoring a bandwidth of traffic sourced from each of the plurality of ingress ports further comprises sampling and statistically analyzing traffic sourced from each of the plurality of ingress ports.

14. The network element of claim 13 , wherein sampling and statistically analyzing traffic sourced from each of the plurality of ingress ports comprises using an elephant trap.

15. A non-transitory computer-readable recording medium having computer-executable instructions stored thereon for providing a fairness protocol that, when executed by a processing unit of a network element, cause the processing unit to:
receive one or more packets at each of a plurality of ingress ports of the network element;
schedule the one or more packets into a plurality of queues, wherein each of the plurality of queues is associated with packets that are sourced from one of the plurality of ingress ports;
monitor a bandwidth of traffic sourced from each of the plurality of ingress ports;
identify a port among the plurality of ingress ports that sources a smallest bandwidth of traffic; and
arbitrate among the plurality of queues when transmitting packets from an egress port of the network element by giving precedence to the identified port that sources the smallest bandwidth of traffic, wherein giving precedence to the identified port comprises transmitting additional packets from a queue associated with packets that are sourced from the identified port, and wherein arbitrating among the plurality of queues distributes a bandwidth of the egress port equally among the plurality of ingress ports.

16. The non-transitory computer-readable recording medium of claim 15 , wherein monitoring a bandwidth of traffic sourced from each of the plurality of ingress ports further comprises maintaining a bandwidth table comprising a counter for traffic sourced from each of the plurality of ingress ports.

17. The non-transitory computer-readable recording medium of claim 16 , having further computer-executable instructions stored thereon that, when executed by the processing unit of the network element, cause the processing unit to increment the counter for traffic sourced from each of the plurality of ingress ports based on a number of bytes or a number of packets transmitted by each of the plurality of ingress ports.

18. The non-transitory computer-readable recording medium of claim 17 , having further computer-executable instructions stored thereon that, when executed by the processing unit of the network element, cause the processing unit to decrement the counter for

Assignees

• Cisco Tech Inc

Inventors

• Sabato Simon Luigi
• Suzuki Hiroshi

Classifications

• H04L47/12

  Avoiding congestion; Recovering from congestion · CPC title

• H04L43/0882

  Utilisation of link capacity · CPC title

• H04L47/629

  Ensuring fair share of resources, e.g. weighted fair queuing [WFQ] · CPC title

• H04L47/6265 Primary

  past bandwidth allocation · CPC title

• H04L47/621

  Individual queue per connection or flow, e.g. per VC · CPC title