Subject: Re: Trading off R and B for TBs

From: [email-masked] (Mark Garrett)
Date: Tue, 16 Aug 1994 10:57:16 -0400

Andrew,
  >>	Sigcomm'94 is only couple of weeks away but is your paper ftpable?

Yes, look in URL:  ftp://thumper.bellcore.com/pub/mwg/sigcomm94.ps

  >>	> 	
  >>	>         |  .
  >>	>   B/R   |  .
  >>	>  [sec]  |   .
  >>	>         |   .
  >>	>         |   .
  >>	>         |   .
  >>	>         |    .
  >>	>         |     .............
  >>	>         .-------------------
  >>	>                  R [bits/sec]
  >>	> 
  >>	> This means that there is not a very useful tradeoff between R and B,
  >>	> or between allocated rate and buffers.  It means that you basically
  >>	> want to operate at the knee, because at any other point you can get a
  >>	> big improvement in one resource for a little expense of the other.
  >>	> Unfortunately, it also means that you can't exchange one resource for
  >>	> the other effectively, and so characterizing the behavior away from
  >>	> the knee isn't very useful.
  >>
  >>	So your recommendation is ...?

Hmmm...well let me revise my opinion on this just a bit.
This curve drawn here is typical for VBR video.  I think
the shape will be similar for data traffic (e.g. the Bellcore
ethernet traces---Leland et al, Sigcomm'93), however there
is an important difference in the scale of delay.  For video
there is a delay constraint of 100 msec or so.  Now, one way
to interpret this curve is to note that there is a strong
knee that gives a good operating point.  Typically it
corresponds to 2 msec of buffering, which is not much,
and is far below the 100 msec that we could afford.  Now,
we find the value of R corresponding to having B/R = 100 msec
of buffer, and see if it gives any substantial savings in R.
For my video results the savings are meager.  At best, with
N=1 source you save about 10% by going from 2 msec to 50 msec
of buffering.

Now let's consider delay-tolerant traffic like ethernet/internet.
The relevent delay constraint is much higher.  We could put
several seconds of buffering in---on average you would have
much less delay, but in the worst case before loss, you might
delay data by a couple seconds.  Then the reduction in R
for B/R = 3 sec might be substantial enough to justify the
added buffer and added occasional delay.  At this point
the QOS question has to focus more closely on the applications.
If you do have 3 sec of buffering, what happens when we get
congested enough to use it?  Do the TCP timers go nuts?  Is
it possible to tune TCP to work under both normal and congested
conditions?

So to answer the question about my recommendation, I guess I'd say
that the full token bucket characterization B(R) is worth studying,
but we need to get some experience with how well it predicts the
resource/QOS tradeoff.  The value of B has much more to do with the
delay constraint of the application than the characterization of the
traffic.  For video the delay constraint is clear; for TCP traffic,
there is still a delay constraint which depends on how you tune the
TCP timers.  (I don't know as much as I'd like to about tuning TCP
timers.)  Then the R you allocate can be chosen using the B(R) curve.
Now again, we have this little problem of correlation.  Just because
you choose R from the token bucket curve doesn't mean the user is
happy (which is the goal, after all).  Well, actually let me restate
that---the user is happy if you constructed B(R) as the value of B for
each R which makes the user happy.  Now ``makes the user happy'' is
equivalent to a measure of QOS.  The simple long-term loss rate, p_l,
is probably not good enough because it cannot capture the effect
of how losses occur in time---i.e. is the user happier with rare
but severe losses or frequent but mild losses, it all depends on
the application and how it recovers from loss etc.  So part of the
puzzle is determining an appropriate QOS measure which can be used
to determine B(R), and then B(R) together with the delay constraint
will tell you how to allocate resources.  (This argument is contained
in the part of my thesis Chapter 4 which didn't make it into the
Sigcomm paper.  Too bad, maybe it'll make it into the journal version....)

  >>	Question:
  >>	Given a traffic source characterised by say  PCR/CDVT and SCR/BT  
  >>	is there way of selecting B and R for the TBs were B and R are
  >>	in some way opt. or the best choice?

Well, this is a bit of a trick question, isn't it.  PCR/CDVT and
SCR/BT constitute a double token bucket.  These mean that, starting
from scratch, you can transmit at the line rate (i.e. arbitrarily fast)
exactly CDVT cells (consider CDVT and BT to be measured in cells for
the moment), then at the rate PCR for BT cells, and then at the rate
SCR indefinitely.  Since there are two explicit rates and two buckets,
you can't express this as a single (R,B).

  >>	What I am getting at is that trading off B against R (or vise versa) 
  >>	has an impact on the injected traffic - so what criteria do I use in 
  >>	setting up my TB parameters R and B ? Can anyone point to some work in
  >>	this area - I am sure there is plenty.

I'm not sure there's plenty.  I have a big binder on my shelf labeled
``Traffic Policing--Leaky Bucket'', and it's only got one paper in it.
That paper is Butto et al, ``Effectiveness of the Leaky Bucket Policing
Mechanism in ATM networks'', JSAC April 1991.  They support my point that
the LB can control the peak rate but policing the mean requires long
delays.  If there is extensive work showing how to use token/leaky
bucket traffic characterization for resource allocation and traffic
management, I would also appreciate the pointers.

This whole business about ``policing the mean'', or allocating mean
bandwidth based on TB characterization is quite bothersome to me.
Craig also mentions this in his note: ``Token bucket at least allows
us to allocate roughly the mean bandwidth plus some buffering.''
And I've seen mention of mean rate characterization in many recent papers.
Probably this is a misunderstanding of terms or perspective.  If you
think about mean as an after-the-fact measure, or you think of it
as what you're entitled to on average, whether you use it or not,
you have different concepts of mean.

Here's a simple thought experiment to illustrate how I think of the
mean.  This is an after-the-fact definition of mean, which I think is
the only mathematically consistent definition.

Consider a token bucket policer, and a sample of traffic which
conforms to (R,B)---i.e. no packets are lost over the sample.  Now,
it's a long sample, so for the process x(t), t = 1,2,3, t_max, we have
sum x(t) >>> B and t_max >>> B/R.  Now, what do we know about the
mean rate of the traffic.  The mathematical mean is
		mu = S/t_max

	with S = sum_{x=1}^{x=t_max} x(t).

What bounds mu?  The largest mean possible is mu = (R*t_max + B)/t_max.
But if the trace is long, then S >> B and mu = R, approximately.  The
smallest mu is zero, because zero traffic conforms to (R,B).  Therfore
the mean can be anywhere from zero to approximately R.  So knowing
R tells us only an upper bound on the mean.  And if you allocate
R, you can't say you're allocating anywhere mean.  You only know
that you're allocating somewhere between mean and peak, which only
makes sense.  Now, granted, if you have a lot of small sources combined,
the traffic will be smooth* and the allocated rate R, will be close to
the mean rate mu.  But you can't tell this a priori.

(*Traffic can be smooth and self-similar at the same time, but that's
another discussion.)

This turned out longer than I expected....

-Mark

-------------------------------------------------------------------------------
			Bellcore   Rm. 2Q-265			+1 201 829-4439
Mark W. Garrett		445 South St.			[email-masked]
			Morristown NJ 07960-6438  USA	     (FAX 201 829-2504)
-------------------------------------------------------------------------------

---

From: [email-masked] (Curtis Villamizar)
Date: Wed, 17 Aug 94 21:11:30 +0000

> it possible to tune TCP to work under both normal and congested

A 3 second delay is huge.  The rule of thumb I've heard for TCP is 1-2
D*BW product of queueing capacity which is 1-2 RTT.  US cross country
RTT is 70 msec (NY-SF).  Add Hawaii and get 125.  You can find a few
high speed paths that approach 140 msec.

TCP works extremely well under congested conditions.  This is one
reason the IP community reacts so strongly to the idea of bandwidth
reservation -- TCP works much better than bandwidth reservation when
bandwidth is finite and demand exceeds it.

You should take a look at the "Random Early Detection" paper by Floyd
& Jacobson <ftp://ftp.ee.lbl.gov/papers/early*.ps>.  It is possible to
have 3 seconds worth of queueing capacity, but limit delay to some
more resonable bounds (if you don't mind having unused RAM).

BTW - at 45 Mb/s 70 msec is about 390 KB.  At 155 mb/s it is 1.36 MB.
3 seconds at 155 Mb/s is over 16 MB of queueing (64 MB if you want
2*DBW and consider Hawaii).  At high speed this is usually static RAM.
What kind of router or switch are you using?  :-)

Curtis

---

From: "Amit Gupta" <[email-masked]>
Date: Wed, 17 Aug 1994 16:17:25 PDT

Hi Curtis

 :TCP works extremely well under congested conditions.  This is one
 :reason the IP community reacts so strongly to the idea of bandwidth
 :reservation -- TCP works much better than bandwidth reservation when
 :bandwidth is finite and demand exceeds it.

 Can you please point us to the appropriate references?

 "works better" is rather subjective; some folks are willing to accept
 reduced throughput, the others would prefer that service be denied if
 the provider cannot provide the required bandwidth.

 also, bandwidth reservation does not imply reserving peak/average
 bandwidth; some researchers have proposed schemes with a "minimum"
 bandwidth reservation, and sharing the resources above that minimum.
 in these cases, a given data stream can have bandwidth reservation,
 and yet be subject to end-to-end congestion control.

 I guess we are digressing from the main topic, though.

 -amit

---

From: [email-masked] (Curtis Villamizar)
Date: Thu, 18 Aug 94 00:48:57 +0000

>  Can you please point us to the appropriate references?

I suppose this is an ongoing debate and I'm making too strong a
statement here.  See below.

>  the provider cannot provide the required bandwidth.

True.  I meant better utilizes the total available bandwidth at a
bottleneck under conditions of congestion.  Few people that have
experience with TCP and understand it dispute that TCP does this
better than at least the bandwidth sharing now offered by ATM.

>  and yet be subject to end-to-end congestion control.

Yes.  You are correct.  The peak/average bandwidth reservation in
current ATM products is giving bandwidth reservation a bad name.

The idea of reserving only a minumum and also having end-to-end
congestion control is a combination of the benefits of both.  TCP is
generally fair but not always and fair may not be what you want anyway
so provide QoS minimums.  Reservation tends to waste bandwidth on
congested links (since inevitably some don't use their reservation) so
allow flows to exceed their minimum and provide congestion control.

This seems to be the direction of the int-serv group with predictive
reservations for elastic applications if I'm not mistaken, but I'm
only a bystander.

So I'm agreeing with you.  Thanks for the clarification.

Curtis

---

From: Mark Moran <[email-masked]>
Date: Wed, 17 Aug 1994 19:33:29 PDT

Curtis,

> congested links (since inevitably some don't use their reservation) so
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
There is no reason for this to cause bandwidth to be "unused". In most
reservation schemes, including those that provide guaranteed
performance, unused bandwidth can be used by "best-effort" or other
lower-priority traffic. Overly conservative reservations unnecessarily
limits the amount of *reserved* traffic you can support, not total
traffic in general. Just a clarification.

> allow flows to exceed their minimum and provide congestion control.

mark