Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-12-18
2003-11-04
Rao, Seema S. (Department: 2666)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S412000
Reexamination Certificate
active
06643260
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of data communications networks. More particularly, this invention relates to a method and apparatus for implementing a quality of service (QoS) policy in a data communications network so as to thereby prioritize network traffic into a plurality of service levels and provide preferential treatment of different classes of data traffic on the data communications network. A number of priority levels may be implemented in accordance with the invention.
2. Background
This invention relates to switched packet data communications networks. There are a number of different packet types which are used in modern switched packet data communications networks.
FIG. 1A
depicts a generic packet
8
using Layer
2
encapsulation. A number of different Layer
2
encapsulation protocols are recognized. Each may include a MAC (media access control) destination address
10
and a MAC source address
12
. The data
14
may include Layer
3
encapsulated packet information. A CRC (cyclic redundancy check)
16
may also be provided at the end of the Layer
2
encapsulation. The unlabeled block
18
may include an Ethernet type for Ethernet V 2.0 (ARPA) packets. The Ethernet type may include IPv
4
(IP), IPX, AppleTalk, DEC Net, Vines IP/Vines Echo, XNS, ARP or RARP. Other known encapsulations include SAP, SAP
1
, SNAP and the like. The meaning of the bits in and the size of block
18
differs among the different encapsulation protocols. This information is sometimes referred to as the Layer
2
Flow Information.
One special case of Layer
2
encapsulation is the IEEE 802.1q frame shown schematically in FIG.
1
B. The IEEE 802.1q frame (or packet)
20
has a MAC Destination Address (“DA”)
10
, MAC Source Address (“SA”)
12
, Data Portion
14
and CRC
16
. In addition, within block
18
is the IEEE 802.1q “tag”
22
which includes, among other items, a block of three priority bits
24
. These three bits are also known as a “Class of Service” or “CoS” field.
FIG. 1C
depicts the Layer
3
and Layer
4
structure of a typical IP packet The IP packet format will be detailed here by way of example because it is presently one of the most common Layer
3
packet types. The fields of importance to this disclosure are the “ToS value” or type of service
26
which is a preferably 8-bit field also known as the Differentiated Service (“DS”) field, “prot-typ” or IP protocol type
28
(typically either TCP (transmission control protocol) or UDP (user datagram protocol)), the Source IP address
30
(usually the IP address of the originating station), the Destination IP address
32
(usually the IP address of the ultimate destination station), the Layer
4
source port number
34
(available for TCP and UDP packets only) and the Layer
4
destination port number
36
(available for TCP and UDP packets only). The Layer
3
flow information includes the information before the source port number
34
. The Layer
4
flow information includes the Source and Destination ports
34
,
36
. The Layer
4
flow information may be used to identify a particular packet flow as being the product of (source port) or directed to (destination port) a particular application. The ToS and CoS fields are used by routers of the data communications network to provide priority/delay/dropping services.
As the use of data communications networks increases worldwide, congestion of those networks has become a problem. A given data communications network, a given node on a data communications network, or a given link connecting two nodes has a certain capacity to pass data packets and that capacity cannot be exceeded. When data traffic on the data communications network becomes heavy enough that one can anticipate congestion problems, it is desirable to implement a “Quality of Service” or QoS policy so as to give priority to certain types of traffic and restrict the flow of other types of traffic, thus assuring that critical communications are able to pass through the data communications network, albeit at the expense of less critical communications.
One of the problems that network devices face in implementing quality of service solutions is in identifying and grouping transmissions to be given preferential treatment or to be restricted, that is, to prioritize the traffic in accordance with the Quality of Service policy established for the network. This becomes especially critical as bandwidth increases substantially over certain links while other links remain relatively slow resulting in traffic speed mismatches which, in turn, cause bottlenecks to data traffic over the relatively slow links. Such groupings must be consistently applied to traffic and must be applied at the rate that the traffic is passing without introducing additional delays or bottlenecks. Such groupings may be, for example, by protocol type, by destination IP address, by source IP address, by destination/source IP address pair, by source port and/or destination port (Layer
4
), and the like.
Routers have, in the past, kept packet counts and rate limited packets in software, but router software has not scaled to the level of being able to process millions of packets per second through a node, providing the basic routing functions that they are required to provide and being able to also provide the rate limitation function.
One approach to identifying and grouping transmissions is for the host to categorize packets by use of the L2 CoS field, L3 ToS field or both. The primary disadvantage of this approach is that it removes control from the system administrator and requires one to trust the end stations to the communication to properly implement the QoS policy. In some cases this trust cannot be justified. In addition, an end station only sees its own packets and therefore is unaware of the overall resource requirements within the data communications network and cannot make allowances for these requirements.
Accordingly, a Quality of Service policy controlled by a network system administrator is needed together with a mechanism for applying it at the full data rate of the data communications network.
SUMMARY OF THE INVENTION
In a first aspect of the invention 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 number of bytes seen counter, a token bucket and a contract value or committed access rate. Each flow is assigned one of a plurality of output queues and optionally at least one output queue threshold value. A token bucket algorithm is employed on each flow to determine whether packets from that flow exceed a committed access rate. Such packets may be dropped or optionally modified to reflect an alternate output queue and/or alternate output queue threshold value before being sent to the selected output queue for transmission from the node.
In a second aspect of the invention an access control list CAM (ACLCAM) contains masked flow information such as, for example, all or portions of IP source and/or destination addresses, protocol types and the like. The ACLCAM provides single clock cycle accesses when performing lookups for each packet. The ACLCAM provides an N-bit index value in response to QoS lookups based upon the best match for the current packet.
The best match is order dependent for the entry in the ACLCAM and may represent any fields in the packet upon which the administrator of the data communications network wishes to base traffic rate limiting and prioritizing decisions. A plurality of ACLCAM entries can yield the same N-bit index value. The N-bit ACLCAM index selects one of 2
N
internal counters and associated preconfigured contract values, which become affected by the packet statistics. A token bucket algorithm is employed on these counters as discussed above.
The ACL CAM may also be used to determine the QoS parameters for new entries in the L3 Table as
Dutt Dinesh G.
Edsall Thomas J.
Fine Michael
Kloth Raymond J.
Cisco Technology Inc.
Harper Kevin C.
Rao Seema S.
Ritchie David B.
Thelen Reid & Priest LLP
LandOfFree
Method and apparatus for implementing a quality of service... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing a quality of service..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing a quality of service... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3180178