Traffic flow regulation to guarantee end-to-end delay in packet switched networks

The present invention relates to the issue of providing end-to-end delay guarantees in a multi-node communication system. More specifically, the present invention addresses the problem of specifying operational parameters of rate-controlled service disciplines in a communication network in order to efficiently provide end-to-end delay guarantees. The key contribution is a method for specifying leaky bucket parameters as well as scheduling delays at each node, which are used as inputs to the rate-controlled service discipline.

CROSS-REFERENCE TO RELATED APPLICATIONS 
The present application claims priority to co-pending U.S. provisional 
application 60/007,196, filed Nov. 1, 1995. 
DESCRIPTION 
1. Technical field 
This invention describes a method and apparatus for regulating the flow of 
packets through a communication network to efficiently satisfy end-to-end 
delay guarantees. More specifically, this invention provides a mechanism 
for specifying the traffic shaper parameters and scheduler delay 
guarantees at each switch so that the connection's end-to-end delay 
requirements are satisfied. 
2. Description of Prior Art 
The problem addressed in this disclosure is that of designing per 
connection traffic shaping mechanisms at every switch of a packet-switched 
network in order to efficiently provide per packet end-to-end delay 
guarantees. Providing end-to-end delay guarantees is an important 
performance measure of many real-time applications such as video, voice, 
and remote sensing and process control. Various methods for providing 
end-to-end delay guarantees exist in the literature. 
A frame structure is provided in 2!. Every packet arriving at a switch 
within one frame, is guaranteed to leave the switch at the next frame and 
thus the packet delay at that switch is guaranteed to remain below a 
certain bound that depends on the frame size. By having the frames at all 
switches synchronized, it is possible to provide overall delay guarantees 
as the sum of the delay guarantees at each switch. The number of 
connections that can be accommodated within one frame depends on the peak 
rate of these connections. Thus, in general, this method leads to 
inefficient use of the network since it requires that a connection be 
allocated bandwidth equal to its peak rate. 
In 4!, the employed service discipline at each switch is a non-preemptive 
policy that "tracks" the operation of the preemptive Generalized Processor 
Sharing policy (GPS) with general weights, by scheduling for transmission 
at the output link, the enqueued packet that would have completed 
transmission earliest under GPS. This packetized version of GPS is denoted 
by PGPS. Under the assumption that the input traffic to the network 
conforms to the output of a "leaky bucket" traffic shaper 5, 6!, it is 
possible to analyze PGPS for fixed weights, and to provide end-to-end 
delay bounds that are in general much better than the bounds obtained by 
the simple addition of the worst case bounds at each switch. However, the 
method of obtaining these bounds is complicated since it requires to take 
into account the combined effect of all the connections at every switch 
through which a connection passes. Moreover, the connection admission 
protocol requires the solution of a inverse problem, namely that of 
determining the appropriate weights so that specified end-to-end delays 
guarantees are provided. This implies an even greater complexity for the 
connection admission protocol under the PGPS service discipline. However, 
for the specific PGPS policy where the assigned weights are proportional 
to the connection's maximum sustainable rate (or leaky bucket token 
generation rate), called Rate Proportional Processor Sharing (RPPS), 
simpler bounds can be obtained. Relative to the general PGPS policy, RPPS 
provides a greatly simplified method of obtaining end-to-end delay 
guarantees, but at the same time its flexibility in providing a wide range 
of these guarantees is significantly reduced. This is due to the fact that 
the simpler bounds obtained under RPPS are in general looser than the 
tight bounds of a POPS policy; moreover, since one has to pick a very 
specific weight assignment, the choice of possible delay guarantees that 
can be provided is limited. 
A rate-controlled service discipline (RCSD) was first proposed in 7! and 
in general, it consists of two components. A leaky bucket traffic shaper, 
which regulates the the rate at which packets are made eligible for 
transmission on the output link, and a scheduler that arbitrates between 
the possibly many packets that are eligible for transmission, thus 
deciding the order of transmission of the eligible packets. A leaky bucket 
can be implemented by maintaining a counter which is periodically 
incremented until a certain threshold, that is larger than the maximum 
packet size. Whenever a packet arrives it is allowed to pass through the 
leaky bucket if the value of the counter is at least the size of the 
packet. Otherwise the packet is queued until the counter reaches the 
packet size. When a packet clears the leaky bucket, the counter is 
decremented by the size of the packet (See 3! for an example 
implementation). An example scheduler is the Non Preemptive Earliest 
Deadline First (NPEDF) scheduler. Here, each connection is associated with 
a certain delay guarantee. When the packets of a particular connection 
arrive at the scheduler, they are stamped with a deadline, which is the 
sum of their arrival time and the associated delay guarantee. Whenever the 
link is idle, the NPEDF scheduler picks the packet with the smallest 
deadline for transmission on the output link. 
In the RCSD described in 7!, the connection traffic at each switch passes 
first through a traffic shaper and is then delivered to the scheduler at 
the appropriate output link. The input traffic is assumed to conform to 
the output of a particular traffic shaper, hereafter referred to as "input 
traffic shaper". At each switch, the connection is first reshaped by a 
shaper identical to the input traffic shaper. It is shown that the 
end-to-end delay under this discipline can be obtained as the sum of the 
worst case delays at the scheduler at each switch, plus the propagation 
delay. That is, the shapers do not contribute additional delays to the 
end-to-end delay bounds. The major advantages of this class of service 
disciplines are simplicity of implementation, simplified analysis since 
each switch can be analyzed separately, and modularity since, depending on 
the processing power of the switch, scheduling policies of varying 
complexity and efficiency can be chosen. However, the end-to-end delay 
guarantees can be very loose since they are obtained as a sum of worst 
case delays at each switch. 
A rate-controlled service discipline where the traffic shapers at each 
switch can reshape the connection's traffic to a shape that has, in 
general, different parameters than the input traffic shaper, is studied in 
1!. It is shown that this modification has the potential to greatly 
improve the end-to-end delay guarantees and that it can also provide the 
tight delay guarantees of a PGPS policy. However, no general method for 
specifying the parameters of the traffic shapers and the scheduler delay 
guarantees is provided in 1!. 
References 1-9! are hereby incorporated herein by reference. 
In this invention we consider a service discipline of the type described in 
1! and provide a mechanism by which the traffic shaper parameters and the 
scheduler delay guarantees at each switch are specified for a connection 
during the connection admission phase. In the special case where every 
connection requires the RPPS delay guarantees, the proposed mechanism can 
guarantee these delays as well. In addition, the proposed mechanism can 
provide a much wider range of delay guarantees. 
SUMMARY OF THE INVENTION 
Consider a packet-switched network which provides strict end-to-end delay 
guarantees by using a rate-controlled service discipline 7, 1!. The 
maximum packet length is L. It is assumed that the input traffic shaper of 
connection n (See 16 of FIG. 2) is of the type specified in the existing 
ATM 8! and proposed TCP/IP 9! standards. This is equivalent to assuming 
the following constraints on the connection traffic. Let I.sub.n 
t,t+.tau.! be the amount of connection n traffic that enters the network 
in the interval t,t+T!. Then, for all t, .tau..gtoreq.0, 
EQU I.sub.n t,t+.tau.!.ltoreq.I.sub.n (.tau.)=L+min {c.sub.n .tau., 
.sigma..sub.n +.rho..sub.n .tau.}, 
where c.sub.n, .sigma..sub.n, .rho..sub.n, are referred to as the 
connection peak rate, burstiness and sustainable rate respectively. These 
parameters are negotiated with the network during the connection 
establishment process and are referred to as pre-determined traffic 
characteristics. These characteristics basically specify the input shaper 
envelope I.sub.n (.tau.). Also, during the negotiation process, an upper 
bound on the end-to-end packet delay for connection n traffic, D.sub.n, is 
requested from the network. That is, D.sub.n is the requested end-to-end 
delay guarantee. 
The operation of a rate-controlled service discipline that will guarantee 
an upper bound D.sub.n on the end-to-end packet delay for connection n 
traffic, requires the following specifications at each switch m (switching 
node m) along the path of the connection (See FIG. 1): 
The parameter values for a traffic shaper 10 (leaky bucket) L.sub.n.sup.m 
which reshapes the traffic of connection n at switch m, to conform to an 
envelope L+min{c.sub.n.sup.m .tau., .sigma..sub.n.sup.m +.rho..sub.n.sup.m 
.tau.}. 
Upper bounds on the scheduler delays at each of the output links of the 
switch. Given the leaky bucket parameters of all connections that are 
destined for output link l of switch m, the scheduling policy that 
arbitrates packet transmission on the link, guarantees an upper bound 
D.sub.n.sup.m for the scheduling delays (queueing in the scheduler 15 plus 
transmission time of a packet) of connection n packets. 
It is known 1! that for any connection, it is optimal to have identical 
leaky bucket parameters at each switch along the path, but not necessarily 
identical to the parameters of the input traffic shaper. More 
specifically, we have that for each switch, m, along the path of the 
connection n, 
##EQU1## 
It is also known 1! that the optimal value of c.sub.n is in the range 
.rho..sub.n, min.sub.m {r.sub.m.sup.n, c.sub.n }!, where r.sub.n.sup.m 
denotes the link capacity of the output link at node m to which the 
connection n traffic is routed. The previous specification still leaves 
the parameters c.sub.n (peak leaky bucket rate) and D.sub.n.sup.m 
(scheduler delay) undefined. As shown in 1!, these parameters are crucial 
for the efficient operation of the service discipline. The objective of 
this invention is to provide a method for determining c.sub.n and 
D.sub.n.sup.m. First, however, we need to provide an expression for the 
end-to-end delay bound of a rate-controlled service discipline. Referring 
to FIG. 2, let connection n traverse switches 1, . . . , M, and let 
T.sub.n.sup.m be the propagation delay between switches m and m+1. By 
convention, switch M+1 (not shown in FIG. 2) is the destination of 
connection n. Let L.sub.n.sup.m be a bound on the delay the connection n 
traffic experiences in the traffic shaper of switch m (See FIG. 2). It can 
then be shown (See 1!), that the end-to-end delay, i.e., the delay a 
packet experiences from the time it exits the input traffic shaper (See 16 
of FIG. 2) to the time it arrives at its destination, is bounded by 
##EQU2## 
where 
##EQU3## 
Note that the bound on the delay includes only the shaper delays at the 
first switch (L.sub.n.sup.1). This shaper delay at the first switch is 
referred to as the "access delay bound". That is, the shaper delays, 
L.sub.n.sup.2, L.sub.n.sup.3, . . , L.sub.n.sup.M are not included. The 
intuitive explanation for not including the shaper delays at the rest of 
the switches, is that only packets that were transmitted early by the 
scheduler at a switch, can be delayed by the shaper at the next switch. It 
is important to note that the upper bound on the scheduler delay at switch 
m, D.sub.n.sup.m, depends on the leaky bucket parameters and on the delay 
bounds of all the connections whose traffic is routed to the same output 
link at node m as the connection n traffic. 
The method proposed in this invention determines c.sub.n, based on the 
following principle. 
Make the peak rate c.sub.n as small as possible as long as it can be 
guaranteed that D.sub.n .gtoreq.D.sub.n. 
The rationale for picking c.sub.n as small as possible, is that this choice 
smoothes the traffic inside the network as much as possible and therefore 
will result in smaller buffer requirements at the switches. 
Once the parameter c.sub.n is determined, the upper bound on the delay at 
the scheduler, D.sub.n.sup.m, that switch m can provide to connection n 
has also been determined (See description of 32 of FIG. 3 below). The 
end-to-end delay D.sub.n, can then be computed according to formula (1). 
It may, however, happen that we still have D.sub.n &gt;D.sub.n. In which 
case, it remains to determine how the delay slack, D.sub.n -D.sub.n, is to 
be reallocated to the switches along the path of the connection. This 
reallocation is of importance as it allows us to relax the delay bounds of 
the connection at the switches, so that more future connection requests 
can be accepted. In this disclosure, we also describe a method to perform 
this reallocation. The method reflects the following objective 
Allocate the delay slack to the M switches that connection n traverses, so 
that the minimum delay bound over all the nodes is maximized. 
The rationale for this objective is that it tends to equalize the allocated 
delay guarantees at all nodes, which in turn implies that the scheduler 
buffering requirements of the connection are spread more evenly among the 
switches.

DESCRIPTION OF PREFERRED EMBODIMENT 
In this section we describe an implementation of the computations outlined 
in the previous section, to determine the appropriate peak leaky bucket 
rate, c.sub.n, of a new connection n with given end-to-end delay 
requirements, D.sub.n, as well as the upper bound on the scheduler delay, 
D.sub.m.sup.n, to be assigned at each node m on the connection's path. The 
inputs to the computations are the predetermined traffic characteristics 
of the connection L.sub.n =(c.sub.n, .sigma..sub.n, .rho..sub.n), its 
desired end-to-end delay bound D.sub.n, and the path (set of nodes and 
links) over which the connection is to be routed. The implementation 
relies on the use of standard programming methods using high level 
programming languages such as C or C.sup.++ and a general purpose 
processor. 
A flow-chart illustrating the different phases of the computations is shown 
in FIG. 3, which displays the iterative process used to determine the 
optimal value for c.sub.n. For the sake of clarity we describe the 
algorithms in this invention, in the framework of a centralized controller 
that controls each switch in the network. Such a controller can be 
implemented using any general purpose processor. Alternatively, the 
implementation may be distributed among the switches along the path of the 
connection with each switch only aware of the connections that are routed 
through it. Iterations of the process would then take place across the 
switches instead of at the centralized controller. 
We first describe a simple component/subroutine that, as shown in FIG. 3, 
is used repeatedly in the determination of c.sub.n. Consider a link l at 
node m along the path through which connection n is routed. Assume that a 
value c.sub.n has been tentatively selected for the peak rate of 
connection n, so that its characteristics at the output of the shaper at 
switch m (and at all other switches on the path) are now given by the 
triplet L.sub.n =(c.sub.n, .rho..sub.n, .sigma..sub.n). Node m already has 
a set C.sub.l,m of connections established on link l, each with already 
determined characteristics L.sub.k.sup.m =(c.sub.k.sup.m, 
.rho..sub.k.sup.m, .sigma..sub.k.sup.m) and associated delay bounds 
D.sub.m.sup.k, for all k .di-elect cons. C.sub.l,m. The quantities 
L.sub.m.sup.k, D.sub.k.sup.m, k .di-elect cons. C.sub.l,m are stored in an 
array form at the centralized controller, or at node m in the case of a 
distributed implementation. Similarly, the propagation delay on the link 
from switch m to m+1, denoted by T.sub.n.sup.m is stored as part of the 
link attributes of the switch m, and is independent of the connection 
characteristics. All quantities are preferably represented using a 
floating point representation for greater precision, but a fixed-point 
representation can also be used if required. 
Given tentative characteristics (c.sub.n, .rho..sub.n, .sigma..sub.n) for 
connection n and the knowledge of the quantities L.sub.k.sup.m, 
D.sub.k.sup.m, for all connections k .di-elect cons. C.sub.l,m already 
established on link l at node m, a key component in determining the final 
values for the network leaky bucket parameters, is to compute the minimum 
delay that can be guaranteed to connection n on link l of node m. This 
computation has to be carried out at each node m on the path, and is 
performed by the subroutine 
EQU Determine.sub.-- Sched.sub.-- Delay (c.sub.n, .sigma..sub.n, .rho..sub.n, 
{L.sub.k.sup.m, D.sub.k.sup.m, k .di-elect cons. C.sub.l,m }) 
(See 32.) 
The implementation of this subroutine depends on the scheduling policy 
employed at the switch, and can be performed using standard operations 
available in any high level programming languages. An example of such a 
computation can be found in 1! for the case where the scheduler is an 
Earliest-Deadline-First (EDF) scheduler. 
We are now ready to proceed with the description of the implementation, 
outlined in FIG. 3, of the algorithm used to determine the appropriate 
value of c.sub.n as well as the upper bound on the scheduler delay, 
D.sub.n.sup.m at each node m on the path of connection n. The first step 
31 of the algorithm is to select initial values for the network leaky 
buckets which in this case are determined by a single value c.sub.n by 
setting 
##EQU4## 
and determining if this results in a feasible end-to-end delay guarantee. 
The choice for such a starting point is that, as mentioned in the previous 
section, we are trying to minimize c.sub.n, and if the smallest possible 
value is feasible, the algorithm stops right after this first step. 
In order to determine if c.sub.n =.rho..sub.n is feasible, we need to 
compute an upper bound on the scheduler delay, D.sub.n.sup.m, that can be 
guaranteed under this setting at each node m on the connection's path. The 
value D.sub.n.sup.m at each node m on the path of the connection n, is 
computed by applying the subroutine 
EQU Determine.sub.-- Sched.sub.-- Delay (.rho..sub.n, 0, .rho..sub.n, 
{L.sub.k.sup.m, D.sub.k.sup.m, k .di-elect cons. C.sub.l,m }), 
where we have set c.sub.n :=.rho..sub.n and .sigma..sub.n :=0. Once the 
scheduler delay bounds D.sub.n.sup.m have been computed for each node on 
the path, the next step is to determine the associated end-to-end delay 
bound D.sub.n from equation (1). Recall, that in addition to the sum of 
the scheduler delay bounds, the end-to-end delay bound, D.sub.n, includes 
the access delay bound (L.sub.n.sup.1), incurred at the shaper in the 
first switch, as well as the sum of the propagation delays (T.sub.n.sup.m) 
that are incurred at each of the links along the path. Two cases must then 
be distinguished depending on the value of D.sub.n. 
1. D.sub.n .gtoreq.D.sub.n : (See 33.) In this case, the algorithm to 
determine c.sub.n completes after this first step, and the required 
end-to-end delay bound can be achieved by setting c.sub.n :=.rho..sub.n, 
i.e., after reshaping the traffic with a leaky bucket of type 
(.rho..sub.n, 0, .rho..sub.n). 
Since the desired peak rate of the connection is now known, the allocation 
of any residual "delay slack" d.sub.n =D.sub.n -D.sub.n among the M nodes 
can now be performed. This amounts to increasing the scheduling delay 
D.sub.n.sup.M at node m by a quantity e.sub.n.sup.m, such that 
.SIGMA..sub.i=1.sup.m e.sub.n.sup.m =d.sub.n. This delay slack allocation 
is performed by the subroutine 
EQU Allocate.sub.-- Delay.sub.-- Slack (d.sub.n, {D.sub.n.sup.m, e.sub.n.sup.m, 
m=1, . . . , M}), 
(See 37.) 
which can be seen in FIG. 3 and will be detailed later. Note that this 
subroutine again relies on standard computational procedures which can be 
implemented using any high level programming language. 
The last step is to set D.sub.n.sup.m :=D.sub.n.sup.m +e.sub.n.sup.m (See 
38.) and the connection is accepted 39. 
2. D.sub.n &lt;D.sub.n : In this case the end-to-end delay bound cannot be met 
with c.sub.n =.rho..sub.n, and it is necessary to consider larger peak 
rate values. The algorithm then searches for the smallest possible value 
larger than .rho..sub.n such that the resulting end-to-end delay bound 
verifies D.sub.n .gtoreq.D.sub.n. 
This is achieved by means of a standard iterative process (the loop on the 
left-hand-side of FIG. 3), for which a pseudocode description is provided 
below. In each iteration the value of c.sub.n is incremented by a fixed 
quantity .delta., i.e., we set c.sub.n :=c.sub.n +.delta., where 
.delta.=(min.sub.m {r.sub.n.sup.m, c.sub.n }-.rho..sub.n)/.DELTA., and the 
parameter .DELTA. determines the accuracy of the solution (See 34.). For 
each new value of c.sub.n, a check is made to test if the delay bound is 
met, i.e., if D.sub.n .gtoreq.D.sub.n. The algorithm stops at the first 
peak rate value c.sub.n for which this condition is true. As mentioned 
earlier, this is consistent with the principle of selecting the lowest 
possible peak rate. Once a feasible value has been identified for c.sub.n, 
the remaining delay slack is allocated to the different nodes so that the 
final local delay bounds D.sub.n.sup.m are determined. This computation 
(right-hand-side of FIG. 3) is again carried out based on the subroutine 
Allocate.sub.-- Delay.sub.-- Slack (), whose pseudocode implementation is 
also provided below. Finally, if the algorithm reaches c.sub.n =min.sub.m 
{r.sub.n.sup.m, c.sub.n } and we still have D.sub.n &gt;D.sub.n (See 35.), 
the connection is rejected as it cannot be admitted in the network (See 
36.), at least not with the requested delay guarantees. 
Next we provide a pseudocode description of the above algorithm. 
##EQU5## 
The above pseudocode implements a standard sequential search in the range 
of values that c.sub.n can take. It may be possible to devise methods 
other than a sequential search that are more efficient. This would, 
however, require knowledge of the relation between D.sub.n.sup.m and 
c.sub.n, which in turn depends on the specific scheduling policy used. As 
was mentioned before, this is also the case for the subroutine 
Determine.sub.-- Sched.sub.-- Delay () as the minimum possible delay 
obviously depends on the selected scheduling policy. The algorithm whose 
pseudocode is provided here applies irrespective of the policy chosen. 
Step 2. (d) in the above pseudocode allows us to determine the local delay 
bounds at all the switches on the path of the connection, once the 
smallest possible value for c.sub.n has been identified. The local delay 
bounds are obtained from the minimum delays D.sub.n.sup.m obtained for 
that value of c.sub.n, to which a fraction of the residual delay slack 
d.sub.n is added. This requires that we specify the sub-routine 
EQU Allocate.sub.-- Delay.sub.-- Slack (d.sub.n, {D.sub.n.sup.m, e.sub.n.sup.m, 
m=1, . . . , M}). 
As mentioned in the Summary of the Invention Section, the goal of this 
subroutine is to allocate the delay slack d.sub.n to the M switches 
traversed by connection n, so that the minimum delay over all the nodes is 
maximized. In other words, the most stringent delay requirement is 
maximized. 
The formulation of the corresponding optimization problem is as follows: 
##EQU6## 
A solution to this problem is obtained as follows. First, an attempt is 
made to allocate the delay slack among the switches so as to yield equal 
delay bounds at all switches. This may, however, not be possible since it 
may actually require the lowering of some delay bounds, say at switch m, 
below the computed minimal value D.sub.n.sup.m. This actually means that 
these switches should not consume any of the available delay slack since 
their local bound is already higher than that at other switches. Switches 
that fall in this category are identified by the fact that they receive a 
negative delay slack allocation when trying to equalize all switch delays. 
When any such switch is present, the one with the largest D.sub.n.sup.m is 
removed from the computation, and another attempt is made at equalizing 
the delay bounds at the remaining switches. The process is repeated until 
a feasible allocation (no negative value) is achieved. 
The subroutine Allocate.sub.-- Delay.sub.-- Slack () implements the above 
procedure and its pseudocode representation is as follows. 
##EQU7## 
The above subroutine can be easily modified to solve a slightly different 
optimization problem, where the equalization is performed not on the delay 
bounds, but instead only on their component due to queueing delays. In 
general, the delay bound of connection n at node m is of the form 
D.sub.n.sup.m =L/r.sub.n.sup.m +q.sub.n.sup.m, q.sub.n.sup.m .gtoreq.0, 
where L/r.sub.n.sup.m represents the transmission delay of a maximum 
length (L) packet, while q.sub.n.sup.m corresponds to the scheduler 
queueing delay. It may be desirable to equalize as much as possible the 
buffering requirements due to queueing rather than total delays at the M 
switches that connection n traverses. This can be achieved through a 
simple modification of the above subroutine where we simply replace 
D.sub.n.sup.m with q.sub.n.sup.m, i.e., we have 
EQU Allocate.sub.-- Delay.sub.-- Slack (d.sub.n, {q.sub.n.sup.m,e.sub.n.sup.m 
m=1, . . . , M}). 
Example of Application of the Algorithm to Achieve RPPS Delay Bounds 
Last, we illustrate how the general algorithm described in this disclosure 
can be used to provide, as a special case, delay allocations and bounds 
equal to those of the RPPS policy. Assume now that the input traffic for 
connection n satisfies 
EQU I.sub.n t,t+.tau.!.gtoreq.I(r)=L+.sigma..sub.n +.rho..sub.n .tau., 
and that the RPPS delay guarantees are required by all the connections in 
the network, i.e., for connection n it is required that 
##EQU8## 
If the scheduling policy employed by each node is Non-preemptive Earliest 
Deadline First, (NPEDF), and we invoke the subroutine 
EQU Allocate.sub.-- Delay.sub.-- Slack (d.sub.n, {q.sub.n.sup.m, e.sub.n.sup.m, 
m=1, . . . , M}), 
then using the techniques in 1! it can be shown that the resulting traffic 
reshaping parameters result in a rate-controlled service policy that 
guarantees the RPPS bounds. 
REFERENCES 
1! L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivarajan. Efficient 
Network QoS Provisioning Based on Per Node Traffic Shaping. Research 
Report RC 20064, IBM, T. J. Watson Research Center, May 1995. 
2! S. Jamal Golestani. A Framing Strategy for Congestion Management. IEEE 
Journal of Selected Areas in Communication, 9(7):1064-1077, September 
1991. 
3! R. Guerin, A. K. Parekh, P. Chang and J. T. Rayfield. A Method and 
System for Implementing Multiple Leaky Bucket Checkers Using a Hybrid 
Synchronous/Asynchronous Update Mechanism. U.S. patent Ser. No. 08/382,464 
filed Feb. 1, 1995, assigned to the same assignee of the current 
application. IBM Docket YO994-224. 
4! A. K. Parekh and R. G. Gallager. A Generalized Processor Sharing 
Approach to Flow Control in Integrated Services Networks: The Multiple 
Node Case. IEEE/ACM Transactions on Networking, 2(2):137-150, April 1994. 
5! M. Sidi, W. Z. Liu, I. Cidon, and I. Gopal. Congestion Control Through 
Input Rate Regulation. In Proceedings of the IEEE GLOBECOM '89, pages 
1764-1768, 1989. 
6! Jonathan S. Turner. New Directions in Communications (or which way to 
the Information Age?). IEEE Communications Magazine, 24(10):8-15, October 
1986. 
7! Hui Zhang and Domenico Ferrari. Rate-Controlled Service Disciplines. 
Journal of High Speed Networks, 3(4):389-412, 1994. 
8! ATM (Asynchronous Transfer Mode) User Network Interface Specification, 
Version 3.1, ATM Forum, September 1994. 
9! C. Partridge. A Proposed Flow Specification, Internet Network Working 
Group, Request for Comments: 1363, September 1992.