Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-05-18
2004-10-05
Qureshi, Afsar (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235100, C370S395210
Reexamination Certificate
active
06801500
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a system for efficiently providing reserved rates to multiple flows at a network interface. Broadly speaking, the invention involves the determination of what packets to deliver immediately and what packets to queue or drop. More specifically, the present invention is concerned with quality of service guarantees or contracts for network bandwidth to various subscribers or customers. This level of service is treated as a contract, which should not be broken at the service provider level. The relevant component in the present invention is an interface such as a router interface, which makes differing levels of service available for various traffic flows.
Having enough bandwidth has increasingly become a problem particularly on wide area networks such as the Internet. Multiple users often must transmit information over the same limited capacity physical lines. Service providers often specify levels of service in terms of “reserved rates” and “peak rates.”
These rates guarantee that for the multiple users accessing a specific network device, all of the users will be assured at least their reserved rate. Furthermore, data flows must be allowed to have actual transmission rates between the specified reserved and peak rates. The sum of the reserved rates often is equivalent to an interface's entire bandwidth.
Because some data flows are allowed to burst up to a peak rate, it is possible that in the very short term, not all data flows will be able to transmit data at their reserved rates at a specified moment in time. Dropping or queueing the packets according to a “traffic-shaping algorithm” is often the only alternative, but any system for dropping or queueing must still guarantee that the perceived rate as seen by the user never falls below the reserved rate.
Current methods to solve the problem include schemes such as Weighted Fair Queuing and its variant Self Clocked Fair Queueing. These systems provide a way to handle delay-sensitive traffic in an expeditious way while fairly sharing the remaining bandwidth between other data flows. These systems sort packets in a queue based on the start time offset by the product of the length of packet and a weight that represents the packet data flow's share of the bandwidth. These schemes are well known in the art.
Unfortunately, such schemes require sorting the packets for placement in a queue. These sorting schemes do not scale well as the number of data flows increases for a particular interface. Specifically, these schemes typically have processing overhead that grows linearly, and at best, logarithmically as a fraction of the number of flows.
What is needed is an improved scheme for transmitting, queuing, or dropping packets at a network interface that minimizes overhead while guaranteeing reserved rates and fairly allocating the remaining bandwidth to the various flows on the network interface.
SUMMARY OF THE INVENTION
The present invention provides a flow control system that effectively provides reserved rates for multiple connections at the interface of a network device.
Quality of service is critical to maintaining efficient delivery of data under a variety of requirements and constraints. Voice data must be transmitted at a constant bit rate, video at a psuedo-constant bit rate, and data at an efficient best efforts rate. Multiple transmissions often must proceed simultaneously on a single medium. The present invention provides management of multiple flows at a network device interface such as a router interface to assure maximum usage of the bandwidth available on the physical line while guaranteeing minimum reserved rates for individual flows. This invention is particularly applicable to cable and fiber optic infrastructure, but is pertinent to any lines capable of handling multiple flows simultaneously over that same line.
One aspect of the invention relates to a system for controlling data transmission rates for various flows connected to a network device interface. The system can be characterized as follows: (1) one or more processors; (2) memory coupled to at least one of said one or more processors; (3) a reserved rate meter for each flow, where each meter is configured to track the use of reserved bandwidth associated with the flow; (4) a peak rate meter for each flow, where each meter is configured to track the use of maximum bandwidth associated with the flow; and (5) an interface meter configured to track the use of bandwidth of said network device interface, wherein at least one processor is configured or designed to adjust the meters based on the amount of data transmitted and refresh the meters based on the network device bandwidth.
The present invention has a number of convenient embodiments. A meter can be incremented or decremented based on bandwidth usage. The network device interface can have an interface meter associated with it to track the amount of physical bandwidth available. When the interface meter hits zero, the system can recognize that no network device bandwidth is available for transmission of additional packets. The interface meter can be refreshed at distinct intervals, and the interface meter can be incremented to reflect this update. Although a meter level of zero can conveniently indicate the unavailability of bandwidth, other meter levels can be used as well.
These meters indicate bandwidth availability in relation to the flow's reserved and peak rates as well as in relation to the network device interface. These meters track the usage of bandwidth across the network device interface as well as across the individual flows. The peak and reserved meters are refreshed based on the associated peak and reserved rates and the interface meter is refreshed based on the network device bandwidth. If a particular flow has depleted its reserved bandwidth and either its peak bandwidth or interface bandwidth based on data transmissions, the system can determine how long a particular piece of data should be buffered (a “traffic-shaping delay”) until it can be put on the network. In one embodiment of the invention, the system can, via a traffic-shaping algorithm, select a queue based upon the length of time so that the chosen queue has a dequeuing time that matches the traffic-shaping delay.
Meters provide a convenient way of practicing one embodiment of the invention, but many other embodiments exist. Token buckets may conveniently serve as one form of meter. Empty buckets indicate that the interface bandwidth, reserved bandwidth, or the peak bandwidth have been consumed. Buckets containing tokens indicate the amount of bandwidth available for use by a particular flow.
One aspect of the invention relates to a method of controlling data queuing at an interface such as a router interface. The method may be characterized by the following sequence: (1) providing a token bucket representation of the bandwidth available at the network device interface; (2) providing token buckets for each flow representing the reserved rate and peak rate associated with each particular flow; (3) refreshing the number of tokens in each bucket based on the data transmitted and bandwidth usage of each flow; and (4) subtracting the number of tokens equivalent to the size of a packet from the interface, peak, and reserved token buckets associated with a packet enqueued to output when the associated reserved token bucket is not empty or both the interface and associated peak token buckets are not empty. During this subtraction process, the peak and reserved token bucket values can sometimes turn negative.
These token buckets track the usage of bandwidth across the network device interface and across the various flows connected to the interface. Tokens are added at rates equivalent to the reserved and peak rates for the individual flows and at a rate equivalent to the network device bandwidth for the interface token bucket.
Another aspect of the invention provides an apparatus for controlling data flow through a network. The apparatus may be characterized by the follow
Beyer Weaver & Thomas LLP
Cisco Technology Inc.
Qureshi Afsar
LandOfFree
Method and apparatus for providing reserved rates to... 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 providing reserved rates to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing reserved rates to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294506