Method and apparatus for implementing a quality of service policy in a data communications network
First Claim
1. A method for implementing a quality of service policy in a data communications network, comprising:
- receiving an IP packet of a certain flow at a port of a network node;
extracting certain flow information from said packet;
assigning the packet an initial class of service value based upon a class of service value encoded in the packet if such class of service value is encoded in the packet and the port is a trunk port;
assigning the packet an initial class of service value configured for the port if (1) no class of service value is encoded in the packet and if the port is a trunk port, or (2) the port is an access port;
reassigning the packet a class of service value configured for the packet'"'"'s MAC destination address if such a value is configured;
comparing said flow information from the packet with configured Access Control Entries (ACEs) and if the packet'"'"'s flow matches an ACE, reassigning the packet a class of service value corresponding to the class of service value configured for the matched ACE;
using said 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 said certain flow;
using said quality of service parameters to determine a codepoint for said packet; and
directing said packet to an output queue specified by said codepoint.
0 Assignments
0 Petitions
Accused Products
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.
141 Citations
57 Claims
-
1. A method for implementing a quality of service policy in a data communications network, comprising:
-
receiving an IP packet of a certain flow at a port of a network node;
extracting certain flow information from said packet;
assigning the packet an initial class of service value based upon a class of service value encoded in the packet if such class of service value is encoded in the packet and the port is a trunk port;
assigning the packet an initial class of service value configured for the port if (1) no class of service value is encoded in the packet and if the port is a trunk port, or (2) the port is an access port;
reassigning the packet a class of service value configured for the packet'"'"'s MAC destination address if such a value is configured;
comparing said flow information from the packet with configured Access Control Entries (ACEs) and if the packet'"'"'s flow matches an ACE, reassigning the packet a class of service value corresponding to the class of service value configured for the matched ACE;
using said 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 said certain flow;
using said quality of service parameters to determine a codepoint for said packet; and
directing said packet to an output queue specified by said codepoint. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
setting said output queue threshold of said specified output queue in accordance with said output queue threshold value.
-
-
3. A method according to claim 2 wherein said active flow table contains Layer 2 flow information.
-
4. A method according to claim 2 wherein said active flow table contains Layer 4 flow information.
-
5. A method according to claim 2, further comprising:
dropping no packets from said certain flow at said specified output queue while the average queue depth of said specified output queue of packets belonging to said certain flow is below said output queue threshold.
-
6. A method according to claim 5, further comprising:
dropping at least some packets from said certain flow at said specified output queue while the average queue depth of said specified output queue of packets belonging to said certain flow is in excess of said output queue threshold.
-
7. A method according to claim 6, wherein said dropping is performed using a weighted random early detection algorithm.
-
8. A method according to claim 2 wherein said quality of service parameters include a contract value specifying a committed access rate corresponding to said certain flow, said method further comprising:
implementing a token bucket algorithm with respect to said certain flow using said contract value and a predetermined leak rate to determine whether said packet is in-profile or out-of-profile.
-
9. A method according to claim 1 wherein said active flow table contains Layer 3 flow information.
-
10. A method according to claim 2 wherein said active flow table contains Layer 3 flow information.
-
11. A method according to claim 1 wherein said quality of service parameters include a contract value specifying a committed access rate corresponding to said certain flow, said method further comprising:
implementing a token bucket algorithm with respect to said certain flow using said contract value and a predetermined leak rate to determine whether said packet is in-profile or out-of-profile.
-
12. A method according to claim 11, further comprising dropping said packet if said packet is out-of-profile.
-
13. A method according to claim 11, further comprising randomly dropping said packet if said packet is out-of-profile.
-
14. A method according to claim 11, further comprising modifying said packet if said packet is out-of-profile.
-
15. A method according to claim 11, further comprising:
modifying said packet.
-
16. A method according to claim 1, further comprising:
modifying said active flow table to include an entry for said certain flow if said active flow table does not already include an entry for said certain flow.
-
17. A method according to claim 16, further comprising:
using a TCAM to store said active flow table.
-
18. A method according to claim 1 wherein said active flow table contains Layer 2 flow information.
-
19. A method according to claim 1 wherein said active flow table contains Layer 4 flow information.
-
20. A method for implementing a quality of service policy in a data communications network, comprising:
-
receiving an IP packet of a certain flow at a port of a network node;
extracting certain flow information from said packet;
assigning the packet an initial class of service value based upon a class of service value encoded in the packet if such class of service value is encoded in the packet and the port is a trunk port, assigning the packet an initial class of service value configured for the port if (1) no class of service value is encoded in the packet and if the port is a trunk port, or (2) the port is an access port;
reassigning the packet a class of service value configured for the packet'"'"'s MAC destination address if such a value is configured;
comparing said flow information from the packet with configured Access Control Entries (ACES) and if the packet'"'"'s flow matches an ACE, reassigning assigning the packet a class of service value corresponding to the class of service value configured for the matched ACE;
using said certain flow information to determine a match with an entry in a content addressable memory associated with an aggregate flow table, said content addressable memory containing a plurality of entries, each corresponding to an aggregation of individual flows; and
selecting, based upon said match, an output queue. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
setting said output queue threshold of said selected output queue in accordance with said output queue threshold value.
-
-
23. A method according to claim 22 wherein said content addressable memory contains masked Layer 3 flow information.
-
24. A method according to claim 22, further comprising:
dropping no packets from said certain flow at said selected output queue while the average queue depth of said selected output queue of packets belonging to said certain aggregation of flows is below said output queue threshold.
-
25. A method according to claim 24, further comprising:
dropping at least some packets from said certain flow at said specified output queue while the average queue depth of said specified output queue of packets belonging to said certain aggregation of flows is in excess of said output queue threshold.
-
26. A method according to claim 25 wherein said dropping is performed using a weighted random early detection algorithm.
-
27. A method according to claim 22 wherein said quality of service parameters include a contract value specifying a committed access rate corresponding to said certain flow, said method further comprising:
implementing a token bucket algorithm with respect to said certain flow using said contract value and a predetermined leak rate to determine whether said packet is in-profile or out-of-profile.
-
28. A method according to claim 21 wherein said content addressable memory contains masked Layer 3 flow information.
-
29. A method according to claim 21 wherein said quality of service parameters include a contract value specifying a committed access rate corresponding to a certain aggregation of flows to which said certain flow belongs, said method further comprising:
implementing a token bucket algorithm with respect to said certain aggregation of flows using said contract value and a predetermined leak rate to determine whether said packet is in-profile or out-of-profile.
-
30. A method according to claim 29, further comprising dropping said packet if said packet is out-of-profile.
-
31. A method according to claim 29, further comprising randomly dropping said packet if said packet is out-of-profile.
-
32. A method according to claim 29, further comprising modifying said packet if said packet is out-of-profile.
-
33. A method according to claim 29, further comprising:
modifying said packet.
-
34. A method according to claim 20, further comprising:
setting a codepoint associated with said packet to a value encoding said selected output queue.
-
35. An apparatus for implementing a quality of service policy, comprising:
-
an IP a packet input at a port of a network node;
a flow information extractor;
an IP packet modifier (1) assigning the packet an initial class of service value based upon a class of service value encoded in a received IP packet if such class of service value is encoded in the packet and the port is a trunk port;
(2) assigning the packet an initial class of service value configured for the port if (a) no class of service value encoded in the received IP packet and if the port is a trunk port, or (b) the port is an access port;
(3) reassigning the packet a class of service value configured for the packet'"'"'s MAC destination address if such value is configured; and
(4) comparing said flow information from the packet with configured Access Control Entries (ACEs) and if the packet'"'"'s flow matches a configured ACE reassigning the packet a class of service value corresponding to the class of service value configured for the matched ACE;
an active flow table storing active flows and corresponding quality of service parameters specifying at least an output queue for each active flow;
a codepoint generator responsive to said flow information extractor and said quality of service parameters; and
a plurality of output queues, one of said output queues selected for transmission of a packet arriving at said packet input in response to a codepoint for said packet generated by said codepoint generator. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42)
-
-
43. An apparatus for implementing a quality of service policy, comprising:
-
an IP a packet input at a port of a network node;
a flow information extractor;
an IP packet modifier (1) assigning the packet an initial class of service value based upon a class of service value encoded in a received IP packet if such class of service value is encoded in the packet and the port is a trunk port;
(2) assigning the packet an initial class of service value configured for the port if (a) no class of service value encoded in the received IP packet and if the port is a trunk port, or (b) the port is an access port;
(3) reassigning the packet a class of service value configured for the packet'"'"'s MAC destination address if such value is configured; and
(4) comparing said flow information from the packet with configured Access Control Entries (ACEs) and if the packet'"'"'s flow matches a configured ACE, reassigning the packet a class of service value corresponding to the class of service value configured for the matched ACE;
a content addressable memory (CAM); and
an aggregate flow table, said CAM containing a plurality of entries, each said entry corresponding to an aggregation of individual packet flows, said aggregate flow table coupled to said CAM and containing information selected by said 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 said entries in said CAM; and
said aggregate flow table providing a selected output queue for said packet in response to said match. - View Dependent Claims (44, 45)
-
-
46. An apparatus for implementing a quality of service policy, comprising:
-
an IP packet input at a port of a network node;
an IP packet modifier (1) assigning the packet an initial class of service value based upon a class of service value encoded in a received IP packet if such class of service value is encoded in the packet and the port is a trunk port;
(2) assigning the packet an initial class of service value configured for the port if (a) no class of service value encoded in the received IP packet and if the port is a trunk port, or (b) the port is an access port;
(3) reassigning the packet a class of service value configured for the packet'"'"'s MAC destination address if such value is configured; and
(4) comparing said flow information from the packet with configured Access Control Entries (ACEs) and if the packet'"'"'s flow matches a configured ACE, reassigning the packet a class of service value corresponding to the class of service value configured for the matched ACE;
a content addressable memory (CAM) coupled to said packet input, said CAM matching a packet arriving on said packet input with a preconfigured aggregate flow entry in said CAM, such entry including an index to an aggregate flow table, said aggregate flow table containing at least one quality of service parameter for controlling the quality of service provided by the apparatus to said packet. - View Dependent Claims (47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57)
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 said entry in said aggregate flow table and said counter decremented periodically by said leak rate.
-
-
54. An apparatus according to claim 53 wherein packets for which said counter exceeds said contract value are designated as out-of-profile.
-
55. An apparatus according to claim 54 wherein out-of-profile packets are dropped.
-
56. An apparatus according to claim 54 wherein out-of-profile packets are randomly dropped.
-
57. An apparatus according to claim 54 wherein out-of-profile packets are modified.
Specification