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

• US 6,643,260 B1
• Filed: 12/18/1998
• Issued: 11/04/2003
• Est. Priority Date: 12/18/1998
• Status: Expired due to Term

• 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:
  US09/213,105
• Time in Patent Office: 1,782 Days
• Field of Search: 370/229, 370/235, 370/236, 370/395.3, 370/395.31, 370/395.4, 370/412, 370/235.1, 709/223, 709/226, 709/229, 709/238, 709/239, 709/240, 709/242
• 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 content addressable memory (CAM or L3 Table) 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 (corresponding to each active flow) 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. In another aspect 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. In another aspect the CAM contains active flow information, the ACLCAM and the aggregate flow table are combined in one system and used to produce in parallel a pair of traffic rate limiting and prioritizing decisions for each packet. The two results are then resolved to yield a single result.

Claims

1. An apparatus for implementing a quality of service policy, comprising:

a packet input;

a first flow information extractor having a single mask, said mask extracting specified flow information from packets appearing at said packet input;

a first content addressable memory (CAM) containing entries corresponding to active packet flows passing through the apparatus, said first CAM responsive to said specified flow information to provide first quality of service parameters;

a second flow information extractor having multiple masks, said multiple masks extracting aggregate flow information from packets appearing at said packet input; and

a second CAM containing entries corresponding to user-configurable aggregations of packet flows passing through the apparatus, said second CAM responsive to aggregate flow information to provide, in conjunction with an aggregate flow table, second quality of service parameters.

2. The apparatus of claim 1, further comprising:

a first rate limiter associated with said first CAM, said first rate limiter generating at least a first codepoint for each packet appearing at said packet input; and

a second rate limiter associated with said second CAM and said aggregate flow table, said second rate limiter generating at least a second codepoint for each packet. appearing at said packet input.

3. The apparatus of claim 2, further comprising:

a codepoint resolver for applying pre-configured policy inputs to said first codepoint and said second codepoint to generate a final codepoint for each packet appearing at said packet input.

4. The apparatus of claim 3, further comprising:

a packet modifier responsive to said final codepoint for modifying CoS fields of 802.1q and ISL packets prior to transmission from the apparatus.

5. The apparatus of claim 3, further comprising:

a packet modifier responsive to said final codepoint for modifying ToS/Differentiated Service fields of IP packets prior to transmission from the apparatus.

6. The apparatus of claim 3, further comprising:

an output port having a plurality of output queues, one of said output queues being selected based upon said final codepoint.

7. The apparatus of claim 6, wherein an output queue threshold value for said selected output queue being selected based upon said final codepoint.

8. The apparatus of claim 7, further comprising:

means for dropping at least some packets of said selected output queue when said output queue threshold value is exceeded by an average queue depth at said selected output queue.

9. A method for implementing a quality of service policy, the method comprising:

receiving packets at a packet input;

extracting specified flow information from packets appearing at the packet input;

using the specified flow information, determining a match with an entry in a first content addressable memory (CAM), the first CAM containing entries corresponding to active packet flows, the first CAM responsive to the specified flow information to provide first quality of service parameters;

extracting aggregate flow information from packets appearing at the packet input; and

using the aggregate flow information, determining a match with an entry in a second CAM associated with an aggregate flow table, the second CAM containing a plurality of entries, each of the entries corresponding to user-configurable aggregations of packet flows and containing second quality of service parameters.

10. The method of claim 9, further comprising:

generating at least a first codepoint for each packet appearing at the packet input, the at least a first codepoint being associated with the first CAM; and

generating at least a second codepoint for each packet appearing at the packet input, the at least a second codepoint being associated with the second CAM.

11. The method of claim 10, further comprising:

applying pre-configured policy inputs to the at least a first codepoint and the at least a second codepoint to generate a final codepoint for each packet appearing at the packet input.

12. The method of claim 11, further comprising:

modifying CoS fields of 802.1q and ISL packets prior to transmission.

13. The method of claim 11, further comprising:

modifying ToS/Differentiated Service fields of IP packets prior to transmission.

14. The method of claim 11, further comprising:

selecting an output queue based upon the final codepoint.

15. The method of claim 14, further comprising:

based upon the final codepoint, selecting an output queue threshold value for the selected output queue.

16. The method of claim 15, further comprising:

dropping at least some packets of the selected output queue when the output queue threshold value is exceeded by an average queue depth at the selected output queue.

17. An apparatus for implementing a quality of service policy, the apparatus comprising:

a packet input for receiving packets;

means for extracting specified flow information from packets appearing at the packet input;

means, using the specified flow information, for determining a match with an entry in a first content addressable memory (CAM), the first CAM containing entries corresponding to active packet flows, the first CAM responsive to the specified flow information to provide first quality of service parameters;

means for extracting aggregate flow information from packets appearing at the packet input; and

means, using the aggregate flow information, for determining a match with an entry in a second CAM associated with an aggregate flow table, the second CAM containing a plurality of entries, each of the entries corresponding to user-configurable aggregations of packet flows and containing second quality of service parameters.

18. The apparatus of claim 17, further comprising:

means for generating at least a first codepoint for each packet appearing at the packet input, the at least a first codepoint being associated with the first CAM; and

means for generating at least a second codepoint for each packet appearing at the packet input, the at least a second codepoint being associated with the second CAM.

19. The apparatus of claim 18, further comprising:

means for applying pre-configured policy inputs to the at least a first codepoint and the at least a second codepoint to generate a final codepoint for each packet appearing at the packet input.

20. The apparatus of claim 19, further comprising:

means for modifying CoS fields of 802.1q and ISL packets prior to transmission.

21. The apparatus of claim 19, further comprising:

means for modifying ToS/Differentiated Service fields of IP packets prior to transmission.

22. The apparatus of claim 19, further comprising:

means for selecting an output queue based upon the final codepoint.

23. The apparatus of claim 22, further comprising:

means, based upon the final codepoint, for selecting an output queue threshold value for the selected output queue.

24. The apparatus of claim 23, further comprising:

means for dropping at least some packets of the selected output queue when the output queue threshold value is exceeded by an average queue depth at the selected output queue.