Subject: Re: various questions about Generic QoS Socket Interface

From: Craig Partridge <[email-masked]>
Date: Mon, 15 Aug 94 15:37:10 -0700

Hi Mark:

    Thanks for your note.  The funny thing is I agree with most of your
technical points but disagree on the general conclusion, mostly because
I think stat muxing is all wrong.

    Let me go after the token bucket argument, since I feel more comfortable
with that one, and then we can debate taxonomies later.

    Executive summary -- I think stat muxing of guaranteed streams is
inconsistent in a world using switches and routers and we shouldn't design
the network around stat muxing of guarantees.  I think token bucket is a good
first swipe at trying to optimize network usage by guaranteed streams
in a world where stat muxing is the wrong answer.

On to arguments.

    The argument is that token bucket gives peaks.  I'd argue that token
bucket gives something closer to means.  I've done a tiny bit of experimenting
with token bucket parameters on real data, and what I've seen is that there's
typically an (R,B) trough in the curve, where if you increase R, B decreases
very slowly relative to increases in R, and vice-versa.  I had a grad student
make a good argument to me that self-similar traffic sort of implies this (as
you increase R, you're decreasing your averaging period for peaks, but since
traffic is self-similar, you'll probably still have relative peaks in your
sub-section that need the large B -- as you increase B you're increasing
your averaging unit but increasing your chance of a larger peak that limits
your chance to reduce R).

    But beyond this, I'm not convinced that stat muxing works if you don't
allocate a guaranteed amount.  In general stat muxing assumes my traffic
flows balance, and that the number of flows N is large enough for the balancing
to work.  Since most of the networking work, including for ATM switches,
suggests that if left to its own devices, the traffic will develop correlations
between streams I think the balance argument is suspicious.  And we are
certainly looking at guaranteeing single streams whose consumption is on the
order of 75-90% of total link bandwidth -- so N is often 1, 2 or 3 in this
world.  So I think trying to achieve R(N) and B(N) is dangerous because 
you'll lose data frequently unless R(N) = SUM (R1, R2, R3) and
B(N) = SUM (B1, B2, B3). And note that we have lots of ways (plenty of
datagrams) to sop up the bandwidth when R(N) of the video sources drops
below SUM (R1, R2, R3).

    If stat muxing doesn't work, then we have to find some way to allocate
enough resources in each switch to make sure that we've achieve our performance
requirements (with near zero loss, another ATM requirement).  We could allocate
the peak bandwidth for each stream, but that's clearly wasteful.  Token bucket
at least allows us to allocate roughly the mean bandwidth plus some buffering.
Further one can easily design the call setup.  At worst, all you need to
check for call admission is if there's buffering = B in each switch and
available bandwidth = R at each hop.

    Taking the ATM params, I'll note that Parekh's thesis says that CTD
can be derived direct from (R,B) and at worst, I can set CDV=CTD.

    From my perspective this is nifty.  A general expression of a solution,
that doesn't require me to know my application behavior in advance and
around which I can build switches and determine admission rules.

    If this is too hand waving, let me know and I'll try to tighten it up
(which may take some time).

Craig

---

From: [email-masked] (Mark Garrett)
Date: Mon, 15 Aug 1994 17:36:59 -0400

Craig,

  > Third, Gopal at Wash University suggested using QoS structures based on
  > application classes (isochoronous, etc).

  >     I confess that personally I really dislike this approach.  It tends to
  >     create a multiplicity of QoS structures based on (what I consider to be
  >     arbitrary) taxonomies of applications.  Part of my dislike comes from
  >     the fact that token-bucket schemes (what ATM and FR use) can express
  >     the range of applications from isochronous to bursty using a single
  >     QoS structure.  So I'd prefer a generic structure if we can do it.
  >     (The major impediment I see is if some new real-time protocol comes up
  >     with a QoS system which is richer than token bucket and thus we cannot
  >     easily map from our generic token bucket into the richer QoS space).

I'd like to take a stab at an argument for a service class-structured
approach to QOS.  Your two objections are:

	A taxonomy of applications is (or can be) arbitrary.

	The Token-bucket as a characterization of traffic is general
	enough to express a large range of applications, from isochronous
	to bursty, using a single QoS structure.

Since this argument will take a few pages, here's the exec summary
(for all you very busy people...):

The token bucket measures something about the highest peaks only.  It
does not give you any handle on how to allocate buffers and bandwidth
for a statistically multiplexed set of sources (which is what we're
most interested in, really).  Good QOS with stat-muxing can be had
without using a token bucket characterization.  The token bucket is a
good thing for characterizing a constant rate source with jitter
(sometimes that's a perfectly useful thing to do).

A service class taxonomy tells you qualitatively what to do with an
application.  It is too hard to derive your qualitative behavior from
a purely quantitative description---how do you know where the break
points are which change your goals abruptly.  Service classes are hard
because they are abstractions which implicitly group similar
applications and the related network functionality.  They are not
concrete objects, as are the applications and the network mechanisms
(e.g. scheduling, feedback flow control alg etc.).  I think we can
make a taxonomy of service categories which make sense fundamentally;
i.e. we can get agreement about the core structure and then the
differences around the edge will be matters of style.

Detailed discussion:

First, the second point, because it's easier to shoot at.  The token
bucket is a characterization of the size of the peaks above a certain
rate.  Consider a traffic process, expressed as the number of bytes or
cells in each small, fixed delta-T of time.  (I.e. scribble a wavy
line on a piece of graph paper and call it traffic).  The token bucket
has parameters R and B.  Now choose a value for R, draw a horizontal
line at R and examine the peaks which exceed R.  Now the smallest
value of B for which the traffic is (R,B) compliant is a measure of
the largest peak above the R-line.  This is simplified, of course
because after a peak, it takes some time to refill the token bucket.
The main point is that only the largest peak is measured by (R,B).
Real traffic (as you know) has large rare peaks.  (This would not be
surprising, except that most of us were raised on a steady diet of
Poisson processes and Markov chains).

Now we could extend the token-bucket description to be the entire
locus of points (R,B) to which a traffic trace conforms.  Imagine our
traffic trace curve, start with a rate above the largest peak, and as
we lower R, watch the behavior of B.  First the highest peak is
measured, and as R decreases, B increases.  Then we may hit some other
peaks, and if any of them are wider than our first one, they will
control the function B(R) for a while.  Of course, when we get to R =
average rate for the given trace, then the required B is "infinite",
or as large as possible for the experiment.

I think in general (and I have some experience with this, see my
thesis, and/or our Sigcomm'94 paper), the curve shape has a strong
knee, like this:
	
        |  .
  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.

More importantly, for VBR traffic (either real-time or not), what we
want the traffic description to do is tell us how to mix traffic
effectively.  If I have 150 ethernets, or 27 VBR MPEG-encoded video
channels, for example, interconnected through a switch or router, how
much bandwidth and buffers do I need to allocate so that everyone
stays happy, and yet, I'm saving significantly over peak-allocating
resources for each source independently.  The token bucket, as a
measure of traffic, does not give any clue about allocation as a
function of the number of sources multiplexed (N).  And fundamentally,
a single (R,B) point cannot solve this problem.  To do resource
allocation, the peak behavior is most important for N=1, and the
average behavior tells about N -> infinity.  Now, the complete
function B(R) is a start.  But it contains no time-correlation
information, which has a large effect on statistical multiplexing.

Here is a more realistic design for statistical multiplexing: Consider
a single source type, e.g. VBR MPEG video coders with a common avg
rate (for instance, with quantizers fixed at a certain point, but all
coding different programs).  Now we could empirically (with subjective
testing for video, and perhaps a convenient objective measure for TCP
traffic) determine the bandwidth allocation as a function of the
number of sources multiplexed, R(N), which provides good quality.
Then we need a method to tell that a new source is enough like the
test source to use R(N) as an engineering rule for it.

There may be other methods, such as observing the aggregation of
traffic without ever knowing that all sources are alike in any sense.
However, I don't know of any claim that R(N) and B(N) can be derived
from (R,B) or even R(B).

The token bucket is, however, a very useful way to characterize a
constant rate source, and the traffic from a CBR source as it
traverses the network and accumulates jitter.  Given an absolutely
periodic CBR source, it will conform to (R,B) with B=1.  Now if we run
the traffic through a few nodes, it has the same rate, in some sense,
certainly in the long-term average sense; but the jitter prevents it
from conforming it (R, 1).  Now if we find the B to which the jittered
traffic conforms, this is very useful.  B is a measure, not only of
the jitter itself, but also of the ``goodness'' of the scheduler in
the node, the amount of buffering necessary to allocate for the flow
at the next node, and the policing function that it will pass---if,
for example, you needed to pass the traffic to another jurisdiction,
and they wanted to know what it was like before accepting it.

Discussion on a Class-Based Service Model:

First, the problem with *not* having a class structure.  If you
describe QOS using a list of 8 quantitative parameters, such as
ATM's favorite list:

	PCR = peak cell rate
	CDVT= cell delay variation tolerance (i.e. the bucket param for PCR,
			don't ask *me* why they picked a name like that!)
	SCR = sustainable cell rate
	BT  = burst tolerance (i.e. the bucket param for SCR)
	CTD = cell transfer delay
	CDV = cell delay variation
	CLR = cell loss rate
	MCR = minimum cell rate (and there's probably more...)

then we're saying that every application, and the treatment which is
appropriate for its traffic, is uniquely identified by a point in this
8-dimensional parameter space.  Now, first, this space is completely
unstructured.  There are areas with important applications and areas
with none.  We could not derive a switch design from this service
model, in the absence of knowledge about the applications we care
about, because we wouldn't know where to start.  Also, if there is a
qualitative change in the scheduler's behavior as a parameter (such as
CDV) increases (e.g. we go from real-time to non-real-time timing
requirements), then how do we know where in the continuum to change?
If we did the design based on knowing about applications, then perhaps
the signaled description of the application traffic/QOS spec should
reflect the same structure as our knowledge of applications.  This is
what the service class set does.

Or, consider Craig's flow spec (A fine job, Craig, don't get me wrong....
I'm not so much picking on you as, er..., building on your work! :-) ):

	Version
	Maximum Transmission Unit
	Token Bucket Rate
	Token Bucket Size
	Maximum Transmission Rate
	Minimum Delay Noticed
	Maximum Delay Variation
	Loss Sensitivity
	Burst Loss Sensitivity
	Loss Interval
	Quality of Guarantee

Even in this case where a parameter is somewhat qualitative (e.g. the
Quality of Guarantee codepoints correspond to descriptions like
``imperfect'', ``predicted'', ``guaranteed'' etc.), then it doesn't do
enough to convey the qualitatively different treatment required for
qualitatively different applications.  These parameters may be useful,
perhaps necessary, but not sufficient.

So now, what are the service classes, beyond just an arbitrary
grouping of things?  Fundamentally, the service class is an abstract
reference to a group of applications which are similar enough that
they can be appropriately handled by the same qualitative mechanism
with perhaps only quantitative differences among them.  (Starting to
sound a little pompous, I know---like the relational group-theoretic
approach to tenure...well, let's press on, I think there's more here
than idle academics...)  The trouble is that while applications and
network mechanisms are concrete, the service class is an abstraction
which refers to the concrete things.  If we lose sight of that, the
problem will again lose any useful sense of structure.

Now, the method of defining the service model should be to make the
most important distinctions first, in the space of application
requirements and associated network functional mechanisms.  If we do
this well, then we should find that any new applications will fall
into existing classes, and only rarely do we need to create new
classes.  The obvious disaster to avoid is where the set of classes
grows as fast as the set of applications.

Here's my approach to defining service classes: First, get a big list
of applications and ask, what network treatment is appropriate for
each?  How do they differ?  Which ones are similar?  Etc.  We get a
list of considerations like this:

	constant/variable rate
	degree of burstiness
	statistical multiplexing
	real-time delay constraints
	delay tolerance in non-real-time applications
	interactiveness
	loss tolerance
	priority
	use of leftover bandwidth
	multiresolution coding (e.g.\ for loss concealment)
	QOS consistency
	fairness.

Now, without getting into too much details, the bottom line (at least
in my thinking so far) is that the real-time delay constraint is the
single most important distinction.  Next we can consider the simplest
method for dealing with real-time and delay-tolerant applications.
This gives a Guaranteed-CBR class, and a Best Effort class.  Next, for
each, find the quality which improves the behavior for each type of
application.  For real-time this is statistical multiplexing, hence a
real-time VBR class.  For delay-tolerant apps, we can improve the
delay behavior, the loss behavior and/or the fairness.

Interestingly, the ATM Forum is choosing to improve loss (and perhaps
fairness) in its ABR service, while Scott Shenker, in his taxonomy,
chose to improve delay with the Assured-ASAP class.  Gopal, in his
previous message, mentioned both a ``rate bounded message class'' and
a ``delay bounded message class''.  I don't know what distinguishes
them, without going through his work, but they seem to be different
flavors of improving the timing characteristics for delay-tolerant
(i.e.  non-real-time) traffic.

At this point, with about 4 classes, we're probably as far as we can
go without doing some more serious thinking about both applications
and implementation.  Given a new feature or requirement, the question
becomes whether it should be built into one of these 4 classes, or
whether it justifies spinning off a new class.

A useful exercise, which I suggested at the July IETF int-serv
meeting, might be to brainstorm on the superset of all these classes
that people have come up with, and see if they can be combined and
then reduced to a still-reasonably small number, like six.  In the
process, I suspect we'll learn what is fundamental and what is just
arbitrary distinctions of style.

-Mark Garrett

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

---

From: Zheng Wang <[email-masked]>
Date: Wed, 17 Aug 94 12:57:31 +0100

>differences around the edge will be matters of style.

Mark,

I think that craig's "token bucket" flowspec and the
"traffic-classes" flowspec you described present
two fundamentally different approaches in forming the
service contract between the application and the network.

"Token bucket" flowspec is based on what I call
the *network-oriented* approach, where the starting
point is what the network can do, then we decide what
traffic types it can support.

"Traffic-classes" flowspec is based on what I call
the *traffic-oriented* approach, where the starting
point is the traffic types, then we decide what the network
should do to the traffic.

The advantage of a network-oriented flowspec is that we are
certain that we can support it. For the "token bucket" flowspec,
we know that there is the WFQ algorithm which requires
close-to-average bandwidth and has a delay bound with
token-bucket traffic.

A traffic-oriented flowspec is certainly more attractive
if the stat multiplexing can be increased. But the difficulty
is to find a reasonably efficient mechanism to
support it in the network. It may not be very difficult to
work out R(N) and B(N) for MPEG video but there are H261, CellB
and NV etc. And what if different types are mixed or if the
traffic is shaped by a router.

Cheers
Zheng

---

From: Mr A Campbell <[email-masked]>
Date: Tue, 16 Aug 1994 12:29:28 +0100 (BST)

Mark:

I really enjoyed digesting your technical note.

> thesis, and/or our Sigcomm'94 paper), the curve shape has a strong

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

>  [sec]  |   .

So your recommendation is ...?

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?

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.

Andrew