Distriburted QoS policing system and method

[0002] The present application is a continuation of commonly assigned and U.S. patent application Ser. No. 09/845,932. Which application was filed on Apr. 30, 2001 now abandoned and has the same title and inventors as the present application. This prior application is hereby incorporated herein by reference, and priority is claimed therefrom under 35 U.S.C. §120.

[0003] 1. Field of the Invention

[0004] The present invention relates generally to computer communications networks, and more particularly to regulating, monitoring and policing traffic on such computer communications networks.

[0005] 2. Background Information

[0006] Enterprises, including businesses, governments and educational institutions, rely on computer networks to share and exchange information. A computer network typically comprises a plurality of entities interconnected by a communications media. An entity may consist of any device, such as a host or end station, that sources (i.e., transmits) and/or receives network messages over the communications media. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. A network device called a “bridge” is often used to implement “bridging” function between entities connected to a LAN. Typically, the bridge is a computer that includes a plurality of ports, which are connected to different entities. The bridging function includes receiving data at a source port that originated from a sending entity, and transferring that data to at least one destination port for forwarding to a receiving entity.

[0007] In many instances, several LANs may be interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc., to form a wide area network (“WAN”) or subnet that may span an entire city, country or continent. One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. A router, for example, may be used to provide a “routing” function between two or more LANs. A multi-protocol router is often used to interconnect LANs executing different LAN standards. To perform these tasks, a router, which also is a computer having a plurality of ports, typically examines the destination address and source address of messages passing through the router. Routers typically operate at the network layer or layer-3 of the communications protocol stack utilized by the network, one such protocol is the Internet Protocol (IP) layer of the five layer Transmission Control Protocol/Internet Protocol (TCP/IP) Reference Model. Furthermore, if the LAN standards associated with the source entity and the destination entity are dissimilar (e.g., Ethernet and Token Ring), the router may also alter the format of the packet so that it may be received by the destination entity. Routers also execute one or more routing protocols or algorithms, which are used to determine the paths along which network messages are sent.

[0008] Congestion typically refers to the presence of too many packets in a subnet or a portion of a network, thereby degrading the network's performance. Congestion occurs when the network devices are unable to keep up with an increase in traffic. The action of not forwarding a packet is called dropping a packet. Dropping packets often affects multiple upper layer applications simultaneously. Furthermore, many upper layer applications, such as TCP, re-send messages if no acknowledgments are received. The upper layer applications may require global synchronization because of packets being dropped, which may significantly exacerbate the congestion problem.

[0009] QoS is a feature that allows dropping of packets on a selective basis to avoid or reduce congestion in the network. Two components of QoS are “classification” and “policing.”Packets are classified into different traffic classes according to policy set by the network administrator. For each class, a policing algorithm is used to measure the incoming traffic and compare that measure with policing parameters set by the network-administrator. As a result of policing, depending on the current traffic-rate for this class of traffic, a packet may be found “in profile” or “out of profile” by the policing algorithm. An out of profile packet is dropped or marked. Marking increases the probability of the packets being dropped later by another device that applies QoS to the packet. A packet that is dropped or marked by the policing algorithm is referred to as a “policed” packet. An in profile packet is forwarded without marking and is referred to as a packet “permitted” by the policing algorithm.

[0010] Various algorithms exist to perform policing. Each of these algorithms is implemented in a single logic-module called policer that performs the same computation for all packets belonging to a traffic class. Such a policer is referenced as a centralized policer, since the same module needs to perform the computation for all packets belonging to a traffic class. One such policing algorithm limits the total number bytes in all packets permitted in any arbitrary time-interval, T, to the value of (T* contract_rate+burst). Here and as defined below, “contract rate” is a policing policy parameter meaning information per unit time, and “burst” is another policing policy parameter meaning the maximum information permitted in excess of the rate. This can be implemented in a policer called the token-bucket policer, which performs the following computation for every packet in a traffic class:—

[0011] where:—

[0012] current_time is a free-running counter that measures time,

[0013] packet_length is the number of bytes in the current packet and

[0014] last_update_time and bucket are states stored for each traffic class

[0015] A centralized policer requires all packets to be processed for policing in a single logic-module. So, packets that are processed in different logic modules cannot belong to the same traffic-class. An object of the present invention is to allow packets arriving at multiple logic-modules to be policed as a single traffic-class. Similarly, an associated object of the present invention is to allow packets arriving at multiple network devices to be policed as a single traffic class. The invention requires each such logic-module to send information about packets that the logic module processed to other such logic-modules. There is a cost associated with the communication capacity used for exchanging such information. If such “overhead” information is sent less often, it uses less of the capacity of the communication system, but it also decreases the accuracy of policing.

[0016] Token based policers are known in the art. One such method is disclosed in U.S. Pat. No. 5,831,971, filed Aug. 22, 1996 and issued Nov. 3, 1998, assigned to Lucent Technologies, Inc. This patent incorporates a token based “leaky bucket” algorithm with queuing algorithms arranged to comply with a given policing policy and to shape traffic incoming to a node into a compliant outgoing stream via some link. However, this patent does not disclose a policing of a class of traffic across an entire network.

[0017] It is an object of the present invention to provide different mechanisms to trigger export of information from a logic-module in order to provide flexibility of optimizing cost-accuracy tradeoff in policing traffic class or classes across a part or an entire network.

[0018] The present invention overcomes the limitations of the prior art by providing a system and method of employing multiple modules in one or more network devices to police a single traffic-class or multiple classes. And wherein such policing can be extended to operate across an entire network.

[0019] The inventive system and method implements the policing policy across the entire network, or part thereof, by providing many modules referenced as individual policers. Each individual policer can observe and police only a part of the traffic. In this system each individual policer uses “global state variables” that stores the measure traffic for the entire traffic-class and “local state variables” that store the measure of the part of traffic that is permitted by this individual policer. Each individual policer exports the measure of traffic it permitted to all individual policers, in the form of the local state variables, or functions thereof. After exporting such information, the individual policer clears the local state variables. Upon receiving such exported information, all the individual policers update their global state variables. At any time, the global state variables of an individual policer account for the total of all the measure of traffic exported from all individual policers till that time. At any time, the local state variables of an individual policer account for the traffic that was permitted at the same individual policer since it last exported the measure of traffic it permitted.

[0020] The present invention provides individual policers that monitor and police part of the traffic. In order to accomplish this policing by individual policers the contract rate and the burst for an entire traffic class is provided to the individual policers. The individual policers measure their parts of the traffic and export that information to all the other individual policers. There is a mechanism for receiving, totalizing and storing the individual policer information exchanged from all the individual policers. That total is then compared to the contract rate and burst for the entire traffic class and a policing decision is made by each individual policer for its part of the traffic class. In an embodiment, there is a master policer that receives all the information from all the individual policers and applies the contract rate and the burst and makes policing decisions for the individual policers that is then sent back to the individual policers.

[0021] In other embodiment, the information can be accumulated and stored at the individual policers and where the individual policers store the own information and that of the other individual policers.

[0022] In other embodiment, there is a threshold established wherein the individual policer broadcasts its information to the other individual policers only when a threshold, previously set in accordance with the overall policing policy is determined for each individual policer, is exceeded. In another related embodiment, the individual policer exports its information containing only the new data received since the last such export in accordance with a time limit that is exceeded. A threshold also may be established wherein the individual policer exports its measure of its part of the traffic when the amount of data locally permitted exceeds a set local-rate threshold.

[0023] In yet other preferred embodiment, the individual policers export information applicable to multiple classes of traffic, and wherein the information is contained in one message. This information may be exported via the same medium used in the network, or alternatively the information may be sent via a medium separate from that used in the network.

[0024] In yet other embodiment, the present invention may be used together with token leaky bucket algorithms incorporating the above discussed elements to advantage.

[0025] In a preferred embodiment, the policing decision for each packet is made using a modified version of the token bucket algorithm, and including thresholds wherein the information messages between individual policers occurs only when these thresholds are exceeded. Such thresholds may be on the data received and/or time from last up date or combinations of both. Moreover, it is possible to interchange the information between the individual policers via channels or a medium outside that of the network itself. For example, dial up telephone/fax lines, and the like. However, the same principle may be employed to other centralized policing algorithms.

[0026] Various techniques are invented to trigger the export of information from the individual policers. This allows various means to reduce information exchanged between policers and increase the accuracy of policing. One technique may be superior to others in a given implementation in a given traffic condition.

[0027] The invention description below refers to the accompanying drawings, of which:

[0028] FIG. 1 is a diagram of a computer network;

[0029] FIG. 2 is another diagram of a computer network depicting network devices,

[0030] FIG. 3 is a block diagram of a network device:

[0031] FIG. 4 is a block diagram of a forwarding engine,

[0032] FIG. 5 is a diagram of a policer memory record, and

[0033] FIG. 6 is a diagram of two leaky buckets of an embodiment.

[0034] EMBODIMENT FIG. 1 is a highly schematic illustration of a computer network 100. The network 100 includes a plurality of servers 102 that are preferably configured as web-hosting servers. A number of users 110 are shown connecting to one of the host 102, but typically there will a number of users that are connected to each host. The network 100 further includes a plurality of intermediate network devices 112, such as backbone routers, high-speed switches, etc. Each host 102 is preferably coupled to two or more of the devices 112 by respective trunks or links 124(a . . . j). Significantly, the network 100 is formed from a multitude of smaller networks, herein shown as NET 1-4. These smaller networks are interconnected together by routers 106. These smaller included networks, considered all together are the Internet 128. In a preferred embodiment, the devices 112 and the routers 106 may include similar designs. Links 126(a . . . i) interconnect devices 112, and links 130, 132 connect devices 112 to Internet 128.

[0035] It should be understood that the configuration of network 100 is meant for illustrative purposes only, and that the present invention will operate with other, possibly far more complex, network designs or topologies.

[0036] Quality of service policing of individual switches and routers is well known in the field, and the present invention can be used advantageously with virtually any known policing system. Since such policers are so well known only a brief overview is provided herein. More fully developed details may be found in the U.S. patent application, assigned to the same entity as is this application, entitled METHOD AND APPARATUS FOR PERFORMING HIGH SPEED TRAFFIC SHAPING, Ser. No. 09/560,499 filed on Apr. 27, 2000, and incorporated herein by reference.

[0037] FIG. 2 is another depiction of a network 200 that includes multiple instances of network devices 202 connected by network links 204. A set of directly connected network devices 202 in this network form a cluster over which a traffic class can be policed. As shown in FIG. 3, each network device 202 in this cluster includes one or more instances of modules called forwarding engines 210. Each forwarding engine performs bridging and/or routing function and implements an individual policer for distributed policing.

[0038] FIG. 3 is the example of a network device that includes multiple instances of a module called forwarding engine 210. Each forwarding engine 210 is directly connected to a set of ports 212, 220, 216, and 218. Each port is connected to a network link 222 that connects to another device, some of which may be other network devices. In this example, all the forwarding engines in the same network device are connected together by a high-speed bus 214. Note that the forwarding engines are connected by a bus for illustrative purposes only. They can be connected by other means like a switch-fabric, etc. When a packet arrives from a network link to a port, say 216, it is processed in a module called the forwarding engine attached to that port. As a result of that processing the packet is either dropped or forwarded to another port, say 218 attached to the same forwarding engine, or forwarded across the high-speed bus 214 to another port attached to a different forwarding engine. In the last case, the packet goes from the high-speed bus through the forwarding engine attached to the destination port, without any processing in that forwarding engine.

[0039] FIG. 4 shows details of a forwarding engine 210. In this preferred embodiment, each forwarding engine includes a submodule, called the individual policer 222, which, in this example, implements a distributed version of the token-bucket algorithm. The output of the individual policer is sent to another module, called the result module 223, that forwards, drops or marks the packet.

[0040] The individual policer includes logic 226 and memory 228. The individual policer logic transmits packets, called the Policer Update Packet or PUP, to other individual policers. The memory in the individual-policer, referenced as policer-memory, stores a record for each traffic class. The following variables are stored in each such record:

[0041] The individual policer includes a free-running counter 229. A packet that is monitored and regulated by an individual policer is referenced as a local packet. Another part of the individual policer logic referenced as classifier 224 examines each local packet and selects a record in the policer-memory that corresponds to the traffic-class of that packet. The classifier also extracts a number, referenced as packet_length, that represents the size of the packet. As shown in FIG. 5, the policer-memory record 230 selected by the classifier includes two global state variables, bucket 232 and last_update_time 234, that store the measure of traffic for the entire traffic-class. The record also includes one local state variable, byte_count_local 236, that stores the measure of the part of traffic that is permitted by this individual policer.

[0042] When a forwarding engine processes a packet from a directly attached port, a logic module in the individual policer, referenced as policer-logic, uses the packet length, the policer-memory record and the value of the free-running counter, referenced as current_time, to perform the computation represented in the following pseudo-code:—

[0043] The new values of bucket, last_update_time and byte count_local, as computed by the above pseudo-code, are written back to the same policer memory record. The “police_packet( )” and “permit_packet( )” referenced in the preceding pseudocode refers to the action of permitting or policing packets. The “transmit pup(traffic_class, byte_count_local)”, referenced in the preceding pseudo-code, refers to the action of sending the ordered pair of policer-memory address and byte_count_local to other individual policers in the payload of a packet called the Policer Update Packet or PUP. The PUP is sent to other network devices over the links that connect those devices. The PUP is sent to other forwarding engines inside the same network device over the high-speed bus that connects the forwarding engines. An update is sent, i.e. PUP is transmitted, when a variable referenced as “pup_transmit_condition” is computed to be true. In one implementation, the PUP is transmitted when the byte_count_local exceeds a certain value. In another implementation, the PUP is transmitted when the elapsed time since last PUP transmission exceeds a certain value. In these two alternate implementations, the “pup_transmit_condition”, is computed as follows:—

[0044] When a forwarding engine receives a PUP, the classifier in the individual policer of that forwarding engine selects the record in the policer-memory selected by the traffic_class field in the payload of the PUP. The classifier also sends the byte_count in the payload of the PUP, referenced as PUP->byte_count, to the policer-logic and indicates to the policer-logic that a PUP has been received. The policer-logic uses the policer-memory record, current_time and PUP->byte_count to compute new values of bucket and last_update_time, which are written back to the same policer-memory record. The computation in the policer logic, in this case, is represented in the following pseudo-code:—

[0045] Following is a summary of the terms defined in the previous paragraphs:—

[0046] Another implementation uses additional variables to trigger PUP transmission. This is referred to as “local_bucket based PUP transmission”. In this case, the following extra variables are used:—

[0047] For the local_bucket based PUP transmission, pseudocode describing the operation of an individual policer upon reception of a PUP is the same as in that presented earlier. However, the operation upon reception of a local packet that belongs to a traffic-class is different, as described in the following pseudo-code:—

[0048] FIG. 6 shows diagrammatically the logic of a individual policer which implements local_bucket based PUP transmission. In a preferred embodiment, the traffic policer algorithm may be implemented in hardware through a plurality of registers and combinational logic configured to produce sequential logic circuits and cooperating state machines. Those skilled in the art will recognize that other combinations of firmware, software and hardware components in addition to those specifically described herein may be advantageously utilized to achieve the objectives of the present invention. FIG. 6 shows two leaky buckets —a local alarm bucket and a policing bucket. The policer bucket 630 is used to make the policing decision for local packets. When a local packet is received, the leak 608 is computed as the product of the contract_rate and the elapsed time since the last update of the policing bucket. If the sum of the packet length of the local packet, the value 602 of the policing bucket and the byte_count_local, which is the recently accumulated local byte count, less the leak 608, exceeds the threshold 612 of the policing bucket, the local packet is policed. The threshold 612 of the policing bucket is also called burst. The local alarm bucket 620 is used as a method for determining when traffic information is to be distributed to the other policers in the system i.e. a PUP is to be transmitted. When a local packet is received, the value 606 of the local alarm bucket is incremented by the packet-length of the local packet and decremented by the leak 610, which is the product of local_rate and the time elapsed since the last local packet reception. When the value 606 of the local alarm bucket reaches or exceeds the threshold 604, a PUP is transmitted, whereby the recently accumulated local byte count is transmitted to all the individual policers, including the one sending the update. Upon receiving a PUP, all the individual policers update their policing bucket by adding the received byte count and subtracting the leak 608, which is the product of the contract_rate and the time elapsed since the last update of the policing bucket. The local alarm bucket has a leak rate 610 that is, in this embodiment, an apportioned part of the aggregate network leak rate, and the local alarm threshold is set to a value determined by the accuracy required of the overall policing policy.