Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2001-10-02
2004-11-30
Phan, Man (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S414000, C370S468000, C709S223000, C709S235000
Reexamination Certificate
active
06826150
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer communications networks, and more particularly to regulating, monitoring and policing traffic on such computer communications networks.
2. Background Information
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.
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.
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.
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.
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:—
last_update_time = current_time;
bucket −= (contract_rate * (current_time − last_update_time));
if (bucket < 0)
bucket = 0;
if ((bucket + packet_length) > burst)
police_packet( ); // packet out-of-profile => police
else {
permit_packet( ); // packet in-profile => permit
bucket += packet_length;
}
where:—
current_time is a free-running counter that measures time,
packet_length is the number of bytes in the current packet and
last_update_time and bucket are states stored for each traffic class
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.
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.
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.
SUMMARY OF THE INVENTION
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.
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 varia
Bhattacharya Dipankar
Huang Yiren
Kloth Raymond
Padwekar Ketan A.
LandOfFree
Distriburted QoS policing system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distriburted QoS policing system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distriburted QoS policing system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3287518