Subject: guaranteed rate service specification

From: [email-masked] (Pawan Goyal)
Date: Thu, 13 Jul 1995 15:48:46 -0500

I have some questions/comments about the draft internet guaranteed
rate service specification. 

1. It is not clear  why is a leaky bucket specification of
traffic  being assumed.  A source can determine the 
end-to-end delay  by just requesting a rate from the network 
and without specifying its traffic to 
the network [1]. The same analysis carries over for determining  buffer 
requirements.  Hence, I am not sure  whether traffic specification 
should be a part of the guaranteed rate service.  It might be desirable 
for a source to request rate and buffer from the network without specifying
the traffic. This would allow for considerable flexibility.

2. If applications using guaranteed service set the playback point
to the maximum delay, then the motivation for letting a burst into
the network ( i.e allowing burst parameter greater than  packet length)
is not clear to me. It is easy to observe that even if the
burst is buffered at the source, the maximum end-to-end delay is the same
as when  no buffering is done at the source. Letting in a burst 
increases the buffering requirement in the network as well as at 
the destination but does  not improve the bound on maximum end-to-end delay. 
However, allowing a burst into the network would improve the average
delay performance. Hence, applications which require a guaranteed bound
but adapt to the changes in average delay, may  benefit. Is this
the motivation for leaky bucket control?
The current draft seems to indicate that the guaranteed service
applications are non-adaptive in nature.

3. The RSpec  couples throughput reservation  and delay. Though
this may be appropriate for scheduling disciplines like WFQ
and Virtual Clock,  scheduling disciplines like 
Delay EDD can separate the two. There is some preliminary experimental
evidence  that separating delay specification from throughput, 
can lead to significant increase in the achievable
utilization. 

4. Is a policing function being supported to control the buffer requirement
at the downstream nodes or ...?  For a broad 
class of scheduling algorithms which includes WFQ, Virtual Clock and 
Self Clocked Fair Queuing, the end-to-end delay bound for each flow holds 
regardless of the behavior of other flows [1]. Hence, in case a scheduling 
algorithm  has this nice isolation property, policing may  not be required.

5. This refers to "Network Element Data Handling Requirements" section
which states:

  " The network element must ensure that the delay of any packet be less
   than b/R+C/R+D where C and D describe the maximal deviation away from
   the fluid model.  For instance, for Weighted Fair Queuing, C is
   given by MTU of the outbound link and D is zero."

I am not sure whether such a requirement, which is so closely coupled
with leaky bucket, is desirable. A network element is required to allocate a 
rate in order to guarantee delay,
but it may not be required to guarantee a bounded delay per packet [1].
In any case, as per my understanding,  C is a term which depends on the flow and
is  the maximum packet length that a flow transmits (which  can be different
from the MTU). Furthermore, D is the term which depends on the queuing 
discipline at a switch.  For WFQ it is MTU of the outbound link divided by 
the *link* rate.

Pawan Goyal

----------------------------------------------------------------------------

[1] Pawan Goyal, Simon S. Lam and Harrick M. Vin, "Determining End-to-End Delay 
Bounds In Heterogeneous Networks", In the Proceedings of the workshop on Network
and Operating system support for Digital Audio and Video, Pages 287-298, April 1995, Available via URL http://www.cs.utexas.edu/users/dmcl.

---

From: Craig Partridge <[email-masked]>
Date: Fri, 14 Jul 95 07:39:50 -0700

the network [1].

Hi:

    A quick note as I head off for the airport (I'm still working my
way through your note and the accompanying paper).
    
    Scott's note pointed out one reason to like token bucket (I prefer to
use "token bucket" rather than "leaky bucket" for an R,B pair where B holds
credits).  It allows better and more flexible use of the network.

    Another reason is that it is much easier for sources.  Basically,
we could specify source behavior in three ways:

    * peak rate - this is very inefficient but easy to compute and
	requires no special handling of data on transmission

    * token bucket - this is much more efficient (R is usually much less
	than peak rate) and still pretty easy to compute and requires no
	special handling of data on transmission

    * a smoothed rate (i.e., something in which the application carefully
	shapes the traffic before sending it) - this doesn't increase
	bandwidth efficiency (since the smoothed rate R is equal to
	sustained rate R in token bucket), but does increase the work
	that the sending system has to do to make sure that the data,
	when transmitted, conforms to the smoothed shape.

Token bucken is the good middle ground, giving efficient use of bandwidth and
while making very limited demands on the sending system.

Craig

---

From: Pawan Goyal <[email-masked]>
Date: Sat, 15 Jul 1995 14:38:00 -0500 (CDT)

This is a response to Craig's and Roch's message.

>
>you still need a traffic spec for the
>source in order for the network to provision resources.  Irrespective
>of the service discipline used, the network must have information
>(traffic envelope) on the traffic for which it is making guarantees.
>
>Roch

Token bucket may be as good way to control a source behaviour. However, the
question is whether a network has to be aware of the source behaviour to
provide guaranteed service (this would further reduce the demands on the 
sending system).  A network may require a traffic envelope:

1. To provide a bound on end-to-end delay: As I had mentioned earlier, a network
does not need to be aware of the traffic spec for this purpose; at least for a
broad class of scheduling algorithms.

2. To exploit the knowledge of the traffic to provide better service:  This
has been used in PGPS networks with CRST assignments to provide low delay to
sources which may have low throughput requirements. However, if a service
is based on the assumption that all sources conform to their advertised
specification, then the guarantees provided by it are conditional and may
be rather weak. The validity of such a service in large networks may
be questionable. Furthermore, this type of service may require all the
sources to conform to one particular type of specification (which 
may not be sufficient).

It is important to note that a network does not necessarily have to be aware
of traffic envelope to separate delay from throughput ( for example: jitter edd
does not require traffic envelope). Hence, we can separate the scheduling
algorithms into broadly three classes (this is just one way, there may be more)
with schedulability region S_1 < S_2 <=S_3 where:

a. S_1  is the schedulability region when only throughput is allocated.
b. S_2 is schedulability region when delay is separated from throughput without
   the knowledge of an envelope.
c. S_3 is schedulability region when delay is separated from throughput with
   the knowledge of an envelope.

Though it is clear that the difference between  S_1 and  S_2 may be significant,
the difference between S_2 and S_3 is much less clear. Given that S_3 implies
assumptions about the traffic, I am not sure whether a network should
try to exploit the difference between S_2 and S_3. In any case, it is
desirable to design  the baseline service with minimal assumptions; additional 
assumptions may be added to derive enhanced services.

3. To  provision resources: Since a network providing deterministic guaranteed
rate service can not overbook its resources, it may be best left to the source
to explicitly request the resources (for example: throughput and buffer).

Based on the above reasons, I believe that the traffic spec should not
be a part of the service.

>My view is that the current specs, complemented by a maximum rate
>value, represent an adequate specification.

>Roch

I believe the current specs, if enhanced and interpreted differently,
may be sufficient. A source should have the flexibility
of requesting the following from the network:

1. Rate
2. Buffer:  in the current spec, the token bucket parameter indirectly requests
buffer from the network. Hence, a change in interpretation may be sufficient.

3. Delay - if  a source requires delay different from what is guaranteed 
by the rate reservation, it  may specify an e2e delay bound. This may require
the network to employ a two pass connection establishment method (e.g. 
tenet groups work) and may impact the RSVP protocol. 

>I think we fully agree here.  We need to make sure that delay and
>throughput are separated.  This was the motivation of the first note
>I sent.  However, as Scott and Craig pointed out, you can do this
>with the current specs even if they were not initially meant for that
>purpose, i.e., set the rate to infinity and use D as your local delay
>bound.  Note that the token rate and clearing rate need not be the
>same.

The current spec does not have provision for delay specification.
D is a parameter which is dependent on the scheduling algorithm employed 
and is independent of source characteristics. In the current specs, the
source does not specify D, only the network is aware of it. Moreover, the
source needs  the ability to specify an e2e delay bound which can be split
suitably across the nodes. Finally, if D is interpreted as local delay
bound, then its interpretation  becomes overloaded.

>The source is certainly free to send more, knowing that the guarantees
>may then not be provided to all packets.  The only thing the network
>should ensure is that it will at least give the guaranteed service
>to a subset of the packets sent which corresponds to a compliant
>behavior.  Some networks may drop all non-compliant packets up front,
>while others may try to get them across.  Any such behavior should
>be acceptable.
>
>Roch

If a source requests resources explicitly (e.g. buffer),
a network need not define the notion of compliant and non-compliant traffic.

>
>On the other hand, I don't think that reserving buffers (or/and rate)
>alone is a good solution as it implies a particular approach in the
>network.

A solution based on a particular traffic spec may be even more restrictive.

Pawan

---

From: Craig Partridge <[email-masked]>
Date: Fri, 28 Jul 95 15:21:49 -0700

Hi Pawan:

I'm sorry to take so long in replying to your note (I did read it before
the INT SERV meeting last week in Stockholm but have been travelling
so much I haven't had a chance to sit down and reply).

    1. It is not clear  why is a leaky bucket specification of
    traffic  being assumed.  A source can determine the 
    end-to-end delay  by just requesting a rate from the network 
    and without specifying its traffic to the network [1].

We needed to choose some way to characterize the source behavior.
And as I read the paper, [1], it doesn't get rid of the need for
characterizing source behavior, it just moves the error terms related
to source characterization to different places.

I'd love to see the work -- the basic problem is that we need to finish the
standards NOW and preliminary work that hasn't gotten wide review isn't
something we can base the standard on.

    4. Is a policing function being supported to control the buffer requirement
    at the downstream nodes or ...?

Policing is occuring for several reasons. We police at the edges to detect
misbehaving flows early (over rate traffic etc).  We police (and based on
last week's meeting, reshape) at merge points and split points to account
for variations caused by remixing traffic.

It is certainly true that isolation provides sufficient policing for individual
flows.  I'm not sure that's true once we start mixing them.

Thanks!

Craig

---

From: Pawan Goyal <[email-masked]>
Date: Fri, 28 Jul 1995 19:58:40 -0500 (CDT)

Hi Craig,

> to source characterization to different places.

I disagree. I believe [1] does demonstrate and  get rid of the need for  
characterizing source behavior to the network.

> something we can base the standard on.

Some experimental evidence is presented in:

Sanjeev Rampal and Douglas S. Reeves, "Routing and Admission Control
Algorithms for Multimedia Traffic", In Proc. of the 5th
IFIP Conf. on High-Performance Networks, Grenoble, June 1994

> flows.  I'm not sure that's true once we start mixing them.

I do not understand the above statement coFrom [email-masked]  Fri Jul 28 11:59:32 1995
To: Pawan Goyal <[email-masked]>
Cc: int-serv
Subject: Re: guaranteed rate service specification 
Date: Fri, 28 Jul 95 18:59:32 -0700
From: Craig Partridge <[email-masked]>

    > to source characterization to different places.

    I disagree. I believe [1] does demonstrate and  get rid of the need for  
    characterizing source behavior to the network.

Well let's work this through briefly.

Let's consider the GR model defined in [1] as applied to PGPS [Abhay's
thesis] with token bucket.  If one works through sections 2.2 and 3.21
of [1], the results show that one can produce the same delay results with
a GR system as a PGPS, *BUT* that GR abstracts out the b/r (bucket size
divided by rate term) of PGPS and makes it a property of the arrival
process AP.

Now, in a real network, making b/r part of the arrival process and not
telling the network about b only works if the queue for b sits at the
source node -- otherwise internal nodes can and will receive a bucket
size worth of traffic and discard it because they didn't know to allocate
buffering for it.

So, GR either (1) translates the b/r delay term (and I should have used delay
in my original note, not "error term") into a delay term in the
source arrival process (which I think matches my statement that the
terms just get moved around) or (2) suffers loss (which is certainly
moving the term around -- a buffer size term suddenly became a loss rate).

Note that I'm not saying [1] is not a useful paper -- I did find it useful
to read.

Thanks!

Craig