Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-07-31
2002-01-08
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S412000, C370S252000, C709S224000
Reexamination Certificate
active
06337851
ABSTRACT:
CROSS REFERENCES TO RELATED APPLICATION
The present invention is related to patent application Ser. No. 08/579,393 filed Dec. 27, 1995 entitled “Method and Apparatus for Rate-Based Scheduling in a Communications Network Using a Relative Error Approach”, now U.S. Pat. No. 6,130,878.
FIELD OF THE INVENTION
The present invention relates to the method and apparatus for rate-based scheduling and weighted fair sharing of a common resource. The problem of rate-based scheduling and weighted fair sharing arise in many different contexts and relates, for example, to the field of computer networks or to processor design. In general, this invention relates to any problem of scheduling jobs according to some rates in a broad context of environments and applications.
BACKGROUND OF THE INVENTION
The problem of scheduling different jobs sharing a common resource occurs in many different contexts. In the most general terms it can be formulated as follows:
A single resource of some kind is shared by several entities indexed by integers i=1,2, . . . n. Every entity has a rate R(i) associated with it. The rates are assigned in such a way that sum of all R(i) does not exceed the capacity of the resource. For example, in computer networks the entity is an individual flow, and the shared resource may be a bottleneck communications link or a server capacity. The entities can be served in some service increments, one at a time. For example, the service increment for a network flow is one packet (or cell, in the ATM terminology). A device, called the Scheduler, needs to determine the order of service for different entities so that the average service rate received by an entity is its assigned rate R(i). Aside from guaranteeing the long-term average rate, an important goal is to bound the discrepancy between the ideal and the actual service times of each individual service increment, i.e., each packet of each flow.
An example of an environment where such a problem occurs is a processor which must schedule jobs competing for its cycles. If all jobs are of equal importance, then it is desirable to provide all jobs an equal share of the processor capacity. If however, the jobs have different importance, a possible strategy is to assign weights to all jobs corresponding to their importance, and provide each job a share of processor capacity proportional to the weight assigned to the job. In this case the desired service rates are determined by the weights of the jobs. An alternative approach might be to assign rates to jobs according to some other rule, which is specific to a particular policy and environment of the problem. For example, a rule might be to give some fixed allocation to high priority jobs and then share the remaining bandwidth among low priority jobs.
As mentioned earlier, another example when a similar problem might occur is in computer networks. For example, in ATM networks there is usually some rate associated with every flow traversing the network. This rate can be either the result of negotiation with the network at setup time, as for example for Constant Bit Rate (CBR) traffic, or can be the result of a traffic management feedback control scheme as is the case for Available Bit Rate (ABR) traffic. The set of rates can be either relatively static, as for long-term CBR flows, or may change quickly in response to congestion as in the case of ABR flows.
Even if the rates are not assigned explicitly, which is the case, for example, in many packet-switching networks, different flows may be of different importance. For example, one flow may be a compound flow of data from 1000 users, while another flow may represent a single user. It may be reasonable in such a case to assign weights to different flows given their relative importance. If the total demand of flows exceeds the capacity of the bottleneck resource, typically a communication link, then a possible policy is to service all flows proportionally to their weights as described earlier in the example of processor sharing. This effectively assigns rates to the flows.
In recent years, rate-based scheduling disciplines at the switching points in computer networks have received much attention. A comprehensive review of such schemes can be found in Hui Zhang,
Service Disciplines for Guaranteed Performance in Packet
-
Switching Vetworks
, Proceedings IEEE, October 1995. These schemes generally are applicable at network switches and can guarantee rates assigned to the flows.
The problem of scheduling of different flows in computer networks exists not only for the switches in the network, but in host adapters as well. For example, an adapter in an ATM network must schedule different flows, each of which has a rate associated with it. Typically, the CBR flows are serviced at a higher priority according to a pre-computed schedule. One of the disadvantages of pre-computing the CBR schedule is that because it is computed without taking any non-CBR flows into account, the service of non-CBR flows may be unnecessarily adversely affected by the CBR bursts. Pre-computing the schedule also has the disadvantage that it is computationally expensive and is usually done in software on a slow time scale. While this may be acceptable for CBR flows which only need to perform this once a new connection is established, it is not feasible if many flows with frequently changing rates need to be scheduled.
Another scheme that is known for rate-based scheduling is the so-called Leaky Bucket, described for example in The ATM Forum Traffic Management Specification Version 4.0. The scheme requires a large amount of per flow state and therefore is prohibitive for a large number of flows.
Also frequently used is the so called “time-wheel” or “calendar queue” approach. An example of the calendar queue approach may be found in Brown., R,
Calendar Queue: A fast O
(1)
priority queue implementation for the simulation even set problem
, Communications of the ACM, vol.31, pp.1220-1227. Unlike the Leaky Bucket scheme, the calendar queues are simple to implement. Unfortunately, in general the calendar queue approach cannot guarantee that the long-term average rate achieved by a flow is equal to its assigned rate.
Therefore, it is desirable to design a scheme that may be used for rate-based scheduling of flows with dynamically changing rates at networks adapters and that can guarantee the assigned rate of the flows.
It is also desirable that this scheme be of use for CBR-type traffic (also known as “guaranteed service” in packet switching networks) and ABR-type traffic (also known as adaptive traffic) simultaneously, as well as VBR (variable bit rate) traffic in ATM networks (also known as predictive traffic in packet switching networks). Finally it is desirable that this scheme be useful in the more general context of rate—based scheduling as described earlier.
What is needed is a general approach to rate scheduling that will work in many different environments. In particular, the new approach should work well for network adapters as well as for network switches.
The approaches described in the paper by Hui Zhang for switch scheduling are not easily applicable to adapters. One of the reasons for this is that most of the scheduling schemes for switches rely on packet arrival times to the switch to determine the scheduling order of packets from different flows. The notion of arrival time is not always well-specified for the adapter
A new scheme, referred to as the Relative Error (RE) Scheduler, was described in copending patent application Ser. No. 08/579,393. The RE scheme has several appealing properties, the most important of which is that the descrepancy between the ideal transmission time of any cell and its actual transmission time is bounded, thereby providing a stringent rate guarantee for any flow.
However, the RE scheme as described in patent application Ser. No. 08/579,393 required finding the maximum of n numbers (where n is the number of flows to be scheduled), all of which had to be updated at each step of the method. Thus, complexity of the RE scheme is O(n
Charny Anna
Cheung Wing
Roman Peter
Thomas Robert
Chin Wellington
Compaq Computer Corporation
Hamilton, Brook, Smith and Reynolds, P.C.
Nguyen Steven
LandOfFree
Method and apparatus for relative error scheduling in a... 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 relative error scheduling in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for relative error scheduling in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857150