Method and apparatus for implementing a quality of service policy in a data communications network

• US 6,868,065 B1
• Filed: 03/18/2003
• Issued: 03/15/2005
• Est. Priority Date: 12/18/1998
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Edsall, Thomas J., Fine, Michael, Dutt, Dinesh G., Kloth, Raymond J.
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): Harper, Kevin C.
• Application Number:
  US10/391,683
• Time in Patent Office: 728 Days
• Field of Search: 370/395.41, 370/229, 370235-236, 370/395.3, 370/395.31, 370/395.4, 370/412, 370/235.1, 709/223, 709/226, 709/229, 709238-239, 709/240, 709/242
• US Class Current: 370/236
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method and apparatus for implementing Quality of Service (QoS) policy in a data communications network. An active flow content addressable memory (CAM) contains entries of flow information for each active flow of packets passing through a given node of the data communications network. The CAM has associated with each entry a packet counter, a byte counter, a token bucket, and a contract value. Each flow is assigned one of a plurality of output queues and optionally at least one output threshold value. A token bucket algorithm is employed on each flow to determine whether packets from that flow exceed the contract value. Such packets may be dropped or optimally modified to reflect an alternate output queue and/or alternate threshold before being sent to the selected output queue for transmission from the node.

Claims

1. A method for implementing a quality of service policy in a data communications network, comprising:

receiving a packet of a certain flow;

extracting certain flow information from the packet;

using the certain flow information as an index into an active flow table containing at least one active flow to look up quality of service parameters applicable to the certain flow, the quality of service parameters including a contract value specifying a committed access rate corresponding to the certain flow, an output queue corresponding to the certain flow, and an output queue threshold co corresponding to the output queue;

using the quality of service parameters to determine a codepoint for the packet, the codepoint having encoded in it the output queue and the corresponding output queue threshold value;

implementing a token bucket algorithm with respect to the certain flow using the contract value and a leak rate to determine whether the packet is in-profile or out-of-profile; and

when the packet is out-of-profile;

modifying the codepoint for the packet and determining whether the packet is to be drooped; and

when the packet is in-profile or when the determination has been made that the packet that is out-of-profile is not to be drooped;

directing the packet to the output queue based on the codepoint and setting the output queue threshold of the output queue based on the codepoint.

2. The method as defined in claim 1, wherein the active flow table contains Layer 3 flow information.

3. The method as defined in claim 1, wherein the active flow table contains Layer 2 flow information.

4. The method as defined in claim 1, wherein the active flow table contains Layer 4 flow information.

5. The method as defined in claim 1, further comprising:

modifying the active flow table to include an entry for the certain flow if the active flow table does not already include an entry for the certain low.

6. The method as defined in claim 1, further comprising:

using a Ternary Content Addressable Memory to store the active flow table.

7. The method as defined in claim 1, further comprising:

dropping no packets from the certain flow at the output queue while an average queue depth of the output queue of packets belonging to the certain flow is below the output queue threshold.

8. The method as defined in claim 1, further comprising:

dropping at least some packets from the certain flow at the output queue while an average queue depth of the output queue of packets belonging to the certain flow is in excess of the output queue threshold.

9. The method as defined in claim 8, wherein the dropping is performed using a Weighted Random Early Detection algorithm.

10. The method as defined in claim 1, further comprising:

when the packet is an IP type packet, modifying the packet by changing a Type of Service field of the packet.

11. The method as defined in claim 1, further comprising:

when the packet is an 802.1q or an ISL type packet, modifying the packet by changing a Class of Service field of the packet.

12. An apparatus for implementing a quality of service policy data communications network, the apparatus comprising:

a packet input for receiving a packet of a certain flow;

a flow information extractor for extracting certain flow information from the packet;

an active flow table storing for at least one active flow corresponding quality of service parameters specifying at least a contract value specifying a committed access rate, a n output queue, and an output queue threshold value corresponding to the output queue;

a codepoint generator responsive to the flow information extractor and the quality of service parameters, the codepoint generator encoding an output queue and a corresponding output queue threshold value into a codepoint for the packet;

a token bucket using the contract value and a leak rate to determine whether the packet is in-profile or out-of-profile;

a packet codepoint modifier for, when the packet is out-of-profile, modifying the codepoint for the packet;

a packet drooper for, when the packet is out-of-profile, determining whether the packet is to be dropped;

a plurality of output queues, wherein, when the packet is in-profile or when the determination has been made that the packet that is out-of-profile is not to be dropped, one of the plurality of output queues is selected based on the codepoint as the output queue for transmission of the packet; and

an output queue threshold setter, wherein, when the packet is in-profile or when the determination has been made that the packet that is out-of-profile is not to be dropped, the output queue threshold for the output queue is set based on the codepoint.

13. The apparatus as defined in claim 12, wherein the active flow table contains Layer 3 flow information.

14. The apparatus as defined in claim 12, wherein the active flow table contains Layer 2 flow information.

15. The apparatus as defined in claim 12, wherein the active flow table contains Layer 4 flow information.

16. The apparatus as defined in claim 12, wherein the active flow table is stored in a Ternary Content Addressable Memory.

17. The apparatus as defined in claim 12, wherein the active flow table is modified to include flows corresponding to packets received which do not have corresponding flow entries in the active flow table.

18. The apparatus as defined in claim 12, wherein no packets of the certain flow are dropped at the selected output queue while the average depth of the selected output queue for the certain flow is below the output queue threshold value corresponding to the selected output queue and the certain flow.

19. The apparatus as defined in claim 12, wherein at least some packets of the certain flow are dropped at the selected output queue while the average depth of the selected output queue for the certain flow is in excess of the output queue threshold value corresponding to the selected output queue and the certain flow.

20. The apparatus as defined in claim 19, wherein a Weighted Random Early Detection algorithm is employed to drop the at least some packets.

21. The apparatus as defined in claim 12, further comprising:

packet modifier for, when the packet is an IP type packet, modifying the packet by changing a Type of Service field of the packet.

22. The apparatus as defined in claim 12, further comprising:

a packet modifier for, when the packet is an 802.1 q or an ISL type packet, modify the packet by changing a Class of Service field of the packet.

23. An apparatus for implementing a quality of service policy in a data communications network, comprising:

means for receiving a packet of a certain flow;

means for extracting certain flow information from the packet;

means for using the certain flow information as an index into an active flow table containing at least one active flow to look up quality of service parameters applicable to the certain flow, the quality of service parameters including a contract value specifying a committed access rate corresponding to the certain flow, an output queue corresponding to the certain flow, and an output queue threshold corresponding to the output queue;

means for using the quality of service parameters to determine a codepoint for the packet, the codepoint having encoded in it the output queue and the corresponding output queue threshold value;

means for implementing a token bucket algorithm with respect to the certain flow using the contract value and a leak rate to determine whether the packet is in-profile or out-of-profile;

when the packet is out-of-profile;

means for modifying the codepoint for the packet and determining whether the packet is to be dropped; and

when the packet is in-profile or when the determination has been made that the packet that is out-of-profile is not to be dropped;

means for directing the packet to the output queue based on the codepoint and setting the output queue threshold of the output queue based on the codepoint.

24. The apparatus as defined in claim 23, wherein the active flow table contains Layer 3 flow information.

25. The apparatus as defined in claim 23, wherein the active flow table contains Layer 2 flow information.

26. The apparatus as defined in claim 23, wherein the active flow table contains Layer 4 flow information.

27. The apparatus as defined in claim 23, ether comprising:

means for modifying the active flow table to include an entry for the certain flow if the active flow table does not already include an entry for the certain flow.

28. The apparatus as defined in claim 23, further comprising:

using a Ternary Content Addressable Memory to store the active flow table.

29. The apparatus as defined in claim 23, further comprising:

means for dropping no packets from the certain flow at the output queue while an average queue depth of the output queue of packets belonging to the certain flow is below the output queue threshold.

30. The apparatus as defined in claim 23, further comprising:

means for dropping at least some packets from the certain flow at the output queue while an average queue depth of the output queue of packets belonging to the certain flow is in excess of the output queue threshold.

31. The apparatus as defined in claim 30, wherein the dropping is performed using a Weighted Random Early Detection algorithm.

32. The apparatus as defined in claim 23, further comprising:

when the packet is an IP type packet means for modifying the packet by changing a Type of Service field of the packet.

33. The apparatus as defined in claim 23, further comprising:

when the packet is an 802.1q or an ISL type packet, means for modifying the packet by changing a Class of Service field of the packet.