Subject: guaranteed rate service specification

From: "Roch Guerin ((914) 784-7038)" <[email-masked]>
Date: Thu, 13 Jul 95 18:14:35 EDT

Reference:  Your note of Thu, 13 Jul 1995 15:48:46 -0500

>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.

Can't you do that by specifying a bucket depth of one packet and using
the token rate as your rate?

>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.

Not sure I follow the argument here.  If you smooth the traffic at the
access, then you need to make up for the lost time in the network by
asking for a lower delay bound.  Whether this is beneficial is tricky
as on one hand you make the traffic easier to handle (smoother), but
you also make it more constraining as it has tighter delay requirements.
There is a subtle trade-off here, and actually in the single node case
you can prove it's sub-optimal (in the sense of maximizing
schedulability) to do reshaping at the source.  The answer in the general
case is a complex one.

>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.

There is also analytical evidence of this as per the technical report
I mentioned in an earlier note.

>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].

Not sure I understand the meaning of guaranteeing delay but not to all
packets?  In any case, my understanding of the guaranteed delay service
class is that the delay guarantees apply to all packets.

Roch

---

From: Pawan Goyal <[email-masked]>
Date: Thu, 13 Jul 1995 18:38:14 -0500 (CDT)

> the token rate as your rate?

Yes, one can do that also. However, in such a scenario a source
would have to buffer all the packets which would increase the average delay.
If an application does not care about the average delay performance, then
this may be acceptable. The network, IMHO, should allow a source the
flexibility to receive guaranteed worst case performance while achieving a good
average case performance. By reserving buffers and rate separately and not
making leaky bucket a part of the spec, a source
rather than network, can select the tradeoff.

> schedulability) to do reshaping at the source.  The answer in the general

Let us for the sake of simplicity, restrict our attention to 
scheduling algorithms that do not separate throughput allocation
from delay (for example Virtual Clock and  RPPS assignment in PGPS).
In such scheduling algorithms  for an allocated
rate, the maximum e2e delay, considered from the packet generation time to 
the packet delievery time, is the same even if the traffic is reshaped to 
CBR at the access point.  Hence, I am not sure why you believe that 
smoothing would lead to tighter delay requirements in the network.

If the scheduling algorithm separates delay specification from throughput,
then one can  prove the sub-optimality of smoothing. Indeed this
was the motivation for CRST rate assignment in PGPS networks. However,
the current specs do not separate  delay from throughput. 

> class is that the delay guarantees apply to all packets.

The key point is that a network supporting guaranteed delay service  
does not have to explicitly guarantee per packet delay.
If a switch guarantees a rate and a  source conforms to some traffic
specification, then the rate guarantee translates into a delay guarantee
for each packet (the delay guarantee would ofcourse depend on the spec). 
It is upto the source to ensure that packet generation process conforms
to the spec.  If the process does not conform to the spec, although
the packets would not receive a guaranteed delay, the rate would still be 
guaranteed. This issue is elaborated in the paper that I had cited.

Pawan Goyal

---

From: [email-masked]
Date: Thu, 13 Jul 95 21:05 EDT

I agree completely with Pawan in all the points he has raised. I also have
a few comments that take off from his observations.

	>the network [1]. 
In recent work, Matt Grossglauser, David Tse and I have shown that
a renegotiated constant bit rate service provides end-to-end delays
without requiring a LB descriptor of the traffic  (RCBR: A Simple and
Efficient Service for Multiple Timescale Traffic: see 
http://www.cs.att.com/csrc/keshav/papers.html). 

	>is not clear to me. 
There is a clear contradiction in the ID as Pawan point out. If the end
systems don't adapt, then there is no point in sending in bursts into
the network (i.e. having a non-zero token bucket). If they do adapt, then
guaranteed service will take over from `predictive' service ;-0
So, either predictive service has to go, or guaranteed service might
as well be CBR (we'd like that)
	>Delay EDD can separate the two. 
Actually, Delay EDD cannot, but Jitter-EDD and RCSP can do this.

	>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.
	>
Absolutely right. For experimental validation, see 
Saran, Keshav. Kalmanek "A Scheduling Discipline and Admission 
Control algorithm for Xunet II" in Multimedia Systems journal,
Sept. 1994

	>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. 
Thats right, especially considering point 3 above!
	>Pawan Goyal

keshav

---

From: Pawan Goyal <[email-masked]>
Date: Sat, 29 Jul 1995 09:48:20 -0500 (CDT)

Hi Craig,

> 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
						    ^^^^^^^^^^^^^^^^^^

For the sake of correctness, the delay bound for token bucket and  PGPS  
as presented in Parekh's paper "A Generalized Processor Sharing Approach to 
Flow Control in Integrated Services Networks: The Multiple Node Case",
IEEE/ACM Transactions On Networking, pages 137-150, April l994 is

b/r + 2*(k-1)*(..)/r + (..)
      ^^^^^^^
which is different from the  bound in [1]:

b/r + (k-1)*(..)/r + (..)
      ^^^^^^

> 
> 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.
> 

This is true if a source requests only rate but  does not request buffer. Let
me quote a part of my original note:

" 1. .......  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. "

My view point is that defining a traffic spec leads to the notion of 
conforming and non-conforming flows. Since the same functionality can 
be achieved without a traffic spec (at least in the current scope of draft), 
it may be desirable to avoid defining it.

Thanks,

Pawan