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

• US 6,870,812 B1
• Filed: 03/18/2003
• Issued: 03/22/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/392,157
• Time in Patent Office: 735 Days
• Field of Search: 370/229, 370/235, 370/235.1, 370/399.1, 370/399.2, 370/399.21, 3703954-39543, 370/412, 370428-429
• US Class Current: 370/235
• 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. A content addressable memory (CAM) contains flow information for each active flow of packets passing through a given node of a 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. An access control list CAM (ACLCAM) contains masked flow information. The ACLCAM provides an index to internal token bucket counters and preconfigured contract values of an aggregate flow table which becomes affected by the packet statistics. In this way, flows are aggregated for assignment of output queues and thresholds, possible dropping, and possible modification of packets.

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 to determine a match with an entry in a content addressable memory associated with an aggregate flow table, the content addressable memory containing a plurality of entries, each of the entries corresponding to an aggregation of individual flows;

selecting, based upon said match, an output queue, the output queue selected based upon a plurality of quality of service parameters contained in the aggregate flow table and indexed from the matching entry in the content addressable memory, and the quality of service parameters further including an output queue threshold value and a contract value specifying a committed access rate corresponding to the certain flow;

encoding a codepoint associated with the packet with an identification of the selected output queue and a value corresponding to the 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;

when the packet is out-of-profile;

modifying the codepoint associated with 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;

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 of claim 1, wherein the content addressable memory contains masked Layer 3 flow information.

3. The method of claim 1, further comprising:

dropping the packet if the packet is out-of-profile.

4. The method of claim 1, further comprising:

randomly dropping the packet if the packet is out-of-profile.

5. The method of claim 1, further comprising:

modifying the packet if the packet is out-of-profile.

6. The method of claim 1, further comprising:

modifying said packet.

7. The method of claim 1, further comprising:

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

8. The method of claim 7, further comprising:

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

9. The method of claim 8, wherein the dropping is performed using a weighted random early detection algorithm.

10. An apparatus for implementing a quality of service policy in a 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;

a content addressable memory (CAM) containing a plurality of entries, each of the entries corresponding to an aggregation of individual packet flows;

an aggregate flow table coupled to said CAM and containing information selected by the entries in said CAM;

said CAM comparing extracted flow information from a packet processed by said flow information extractor and determining a match with one of the entries in said CAM;

said aggregate flow table providing a selected output queue and output queue threshold value for the packet in response to the match;

a codepoint generator responsive to said selected output queue, said codepoint generator encoding an output queue and a corresponding output queue threshold value into a codepoint for the packet;

a token bucket using a contract value stored in the flow table 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 dropper 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.

11. The apparatus of claim 10, wherein said CAM is coupled to said aggregate flow table by a plurality of index pointers stored in said CAM, one pointer per aggregate flow entry in said CAM, and said pointers point to selected locations in said aggregate flow table at which quality of service parameters are stored.

12. The apparatus of claim 10, wherein said CAM is a ternary CAM.

13. The apparatus of claim 10, wherein the aggregate flow entries in said CAM contain only a portion of the flow information for any given packet.

14. The apparatus of claim 13, wherein the portion of the flow information is specified by a mask which is individually programmable for each entry in the CAM.

15. The apparatus of claim 14, wherein the portion of the flow information may include Layer 2, Layer 3 and Layer 4 flow information.

16. The apparatus of claim 10, wherein the quality of service parameters specify at least a contract value and a leak rate, and said apparatus further comprises:

a counter associated with an entry in said aggregate flow table, said counter incremented for in-profile bytes of packets passing through the apparatus which are matched to the entry in said aggregate flow table and said counter decremented periodically by said leak rate.

17. The apparatus of claim 16, wherein packets processed by the apparatus at times at which said counter exceeds said contract value are designated as out-of-profile.

18. The apparatus of claim 17, wherein out-of-profile packets are dropped.

19. The apparatus of claim 17, wherein out-of-profile packets are randomly dropped.

20. The apparatus of claim 17, wherein out-of-profile packets are modified.

21. An apparatus for implementing a quality of service policy in a data communications network, the apparatus 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 to determine a match with an entry in a content addressable memory associated with an aggregate flow table, the content addressable memory containing a plurality of entries, each of the entries corresponding to an aggregation of individual flows;

means for selecting, based upon said match, an output queue, the output queue selected based upon a plurality of quality of service parameters contained in the aggregate flow table and indexed from the matching entry in the content addressable memory, and the quality of service parameters further including an output queue threshold value and a contract value specifying a committed access rate corresponding to the certain flow;

means for encoding a codepoint associated with the packet with an identification of the selected output queue and a value corresponding to the 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 associated with 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.

22. The apparatus of claim 21, wherein the content addressable memory contains masked Layer 3 flow information.

23. The apparatus of claim 21, further comprising:

dropping the packet if the packet is out-of-profile.

24. The apparatus of claim 21, further comprising:

randomly dropping the packet if the packet is out-of-profile.

25. The apparatus of claim 21, further comprising:

modifying the packet if the packet is out-of-profile.

26. The apparatus of claim 21, further comprising:

modifying said packet.

27. The apparatus of claim 21, further comprising:

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

28. The apparatus of claim 27, further comprising:

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

29. The apparatus of claim 28, wherein the dropping is performed using a weighted random early detection algorithm.