Subject: Conservative Admission Control

From: "Steve Blake" <[email-masked]>
Date: Wed, 03 Jul 1996 15:16:11 +22299904

While I'm busy spamming the net today, I though that I would raise a
philosophical question: to what extent should IntServ admission control
algorithms trust the Tspec provided by the application (or the reserving
receiver)?  I spoke at the Montreal IntServ meeting, suggesting that
the inclusion of a "trust me" flag in a Controlled Load Rspec could allow
that service to achieve most of the objectives offered by the proposed
Committed Rate service.  John Wroclawski's response, if I remember correctly,
was that the Controlled Load admission control procedure should be intelligent
enough to make admission control decisions that allowed the node to achieve
its service commitments.  I think that his was a fair response, and I
understand and agree that IntServ should not specify the implementation
mechanisms for either the admission control procedure or the Controlled Load
scheduler, and that users should be prepared to reward or punish their service
providers based on the extent to which they honor their service commitments.
I also respect the work that is being done in the area of measurement-based
admission control.  But I am concerned that some admission control algorithms
may make assumptions about how the application selects and adheres to its
Tspec which may not hold for CBR or rate-controlled VBR video, for instance.
I'm worried that admission control algorithms which overbook (i.e., admit
N flows where Sum(r_i) > CL capacity) may loose badly to greedy applications
that shape their transmission rate precisely to their Tspec.  Note that
statistical multiplexing gains for VBR video are still possible with
conservative admission control (see previous note).

So I guess I'm not convinced that a "trust me" flag for Controlled Load v2,
which instructed the admission control algorithm to reserve at least the token
bucket rate for the flow, wouldn't be very useful in certain circumstances.

/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
| Steven L. Blake              [email-masked] |
| Internetworking Technology          (919)254-2030 |
| IBM Networking Hardware Division                  |
| "You like the 'Net?  You ain't seen nothin' yet!" |
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/

---

From: John Wroclawski <[email-masked]>
Date: Wed, 3 Jul 1996 19:11:05 -0400

Steve,

At 3:16 PM -0400 7/3/96, Steve Blake wrote:
>receiver)?

Not sure I understand your phrasing here. The service contract (for both
guaranteed and controlled-load) is that *if* the traffic doesn't exceed the
reservation TSpec *then* the service commitment will be met. There is no
implication at all that the traffic will not exceed the reservation TSpec -
in some normal operating situations, it will. When it does, the network
element is not expected to meet the commitment (although it is expected to
not screw up its commitments to other flows)

>that shape their transmission rate precisely to their Tspec.

Hmmm. Your first two sentences seem contradictory. Either an admission
control algorithm works (for whatever definition the service requires) or
it doesn't. Making bad assumptions about a flow and losing because of it
seems to fall into the category of "doesn't".

Note that measurement-based admission control approaches generally consider
the stated TSpec of the "new" flow and the measured behavior of "old" flows
- in other words, they assume the worst at first and wait to see if it's
really that bad.

This strategy should work for any sort of flow except one which changes its
behavior radically after it has been running for a long time. However, we
know that there are applications (e.g. simulation) where this is true. It
seems to me that a measurement-based adm control approach can deal with it
by being increasingly conservative as the total number of flows falls, so
that when there are few enough flows that one flow changing its behavior
(within the TSpec range) has a noticable effect, the admission control is
using a conservative algorithm so that the effect doesn't matter. The
situation is somewhat more complicated when the flows are not statistically
independent...

The idea of the dont-measure-me bit has been around for a while, and I
actually agree that it has some appeal. The question is how you enforce it.
Presumably there is some cost to a don't-measure-me reservation, because
you are asking the network to keep some resources allocated even though the
application is not using them all the time. Hence setting the bit may well
cost the user something, and it will be to their advantage not to do so,
even if they should. What do you do? Implementing a scheduler that singles
out and zaps people who should have set the bit and didn't appears at first
glance to cost you much of the simplicity of scheduling C-L (though there
are some untested ideas around which might make it more managable). The
other option is to charge/value/whatever both bit-set and bit-not-set
reservations equally, even though they use different amounts of resources,
just so people will set the bit when they should to help you out.

In any case, I hope we'll have enough experience and measurement-based adm
control research in hand to make the situation clearer by the time (if) CL
becomes a final standard.

	-john

---

From: Greg Troxel <[email-masked]>
Date: Fri, 5 Jul 1996 09:16:45 -0400

John,  

  This strategy should work for any sort of flow except one which
  changes its behavior radically after it has been running for a long
  time. However, we know that there are applications (e.g. simulation)
  where this is true. It seems to me that a measurement-based adm
  control approach can deal with it by being increasingly conservative
  as the total number of flows falls, so that when there are few
  enough flows that one flow changing its behavior (within the TSpec
  range) has a noticable effect, the admission control is using a
  conservative algorithm so that the effect doesn't matter. The
  situation is somewhat more complicated when the flows are not
  statistically independent...

I'm not sure that this is an appropriate solution.  I believe that
another characteristic of distributed simulation is correlated flows
because all the flows of a single simulation are part of the same
distributed system.  I expect this to break most admission control
schemes that make any assumptions about a flow's traffic.  Perhaps the
solution is instead to be conservative when either the total number of
flows is small or the fraction of flows which might be correlated is
high.  I don't know how to measure the latter, though.

  Either an admission control algorithm works (for whatever definition
  the service requires) or it doesn't. Making bad assumptions about a
  flow and losing because of it seems to fall into the category of
  "doesn't".

This will raise interesting questions about what a Tspec really means
- just that the flow conforms to (r, b, m, M), or that it additionally
meets some "typical behavior" with respect to correlation.
If the traffic contract is really that flows which meet the Tspec
receive the service, then any admission control scheme which either
does measurement or assumes any lack of correlation between flows
would seem to fall in the above category of "doesn't work".

Perhaps we need a CL-no-assumptions service class, which has the
slightly fuzzy loss probability properties of CL, but still has them
even if the source behaves "badly" with respect to the typical
behavior of 99% of the other flows.  Or perhaps CL should be this.
Or, perhaps such a service is so close to Guaranteed that it would be
of no additional use, and people with correlated flows shouldn't use
CL.  If so, this needs to be made far more explicit.

It might be a good idea for people implementing CL to speak up about
how their admission control schemes behave - in particular whether
they make statistical multiplexing assumptions.

        Greg Troxel <[email-masked]>

---

From: John Krawczyk <[email-masked]>
Date: Mon, 8 Jul 96 09:04:45 EDT

On Fri, 5 July, Greg Troxel ([email-masked]) wrote:

OK.

First, I've been sort of astonished how people have assumed that CL
implementations _will_ do oversubscribing.  This is an option, and is
not mandated by the spec.  To quote the appropriate section:

   REQUIREMENTS PLACED ON ADMISSION CONTROL ALGORITHM: The intention of
   this service specification is that network elements deliver a level
   of service closely approximating best-effort service under unloaded
   conditions. As with best-effort service under these conditions, it is
   not required that every single packet must be successfully delivered
   with zero queueing delay. Network elements providing controlled-load
   service are permitted to oversubscribe the available resources to
   some extent, in the sense that the bandwidth and buffer requirements
   indicated by summing the TSpec token buckets of all controlled-load
   flows may exceed the maximum capabilities of the network element.
   However, this oversubscription may only be done in cases where the
   element is quite sure that actual utilization is far less than the
   sum of the token buckets would suggest. The most conservative
   approach, rejection of new flows whenever the addition of their
   traffic would cause the strict sum of the token buckets to exceed the
   capacity of the network element (including consideration of resources
   needed to maintain the delay and loss characteristics specified by
   the service) may be appropriate in other circumstances.

For the first pass, we've taken the conservative approach.  We will only
allow reservations up to the point where the combined Tspecs are under
the administratively configured limits.  Only after getting some
additional experience under our belts will we consider doing measurement
based admission control.

-jj

---

From: Greg Troxel <[email-masked]>
Date: Mon, 8 Jul 1996 09:36:51 -0400

JJ,

  First, I've been sort of astonished how people have assumed that CL
  implementations _will_ do oversubscribing.  This is an option, and is
  not mandated by the spec.

I've had several people (from an ATM switch vendor and a long-haul
telco) tell me that of course, ATM switches overadmit, and of course,
telcos will turn up the overadmission fudge factor as long as they are
just barely getting away with it.  Given this attitude (which is quite
understandable given the voice telephony model), and the significant
likelihood that most traffic through a large network element will be
fairly uncorrelated, it therefore seemed likely that at least some CL
implementations would oversubscribe or offer an oversubscription
feature.

I'm glad to hear that you are implementing a conservative strategy.

     However, this oversubscription may only be done in cases where
     the element is quite sure that actual utilization is far less
     than the sum of the token buckets would suggest.

I realize the specification implies that overadmission may only be
done when it may be safely gotten away with, based on some notion of a
router being 'quite sure'.

My concern about measurement-based or overadmitting schemes remains,
however, in that one can gain experience with a particular traffic mix
and then be in an operational environment with new types of traffic.
Since these schemes seem appropriate in many circumstances, perhaps
the eventual result will be for operators to configure measurement and
overadmission on or off depending on whether the responsible humans
are 'quite sure' utilization will be less.

	Greg

---

From: Curtis Villamizar <[email-masked]>
Date: Mon, 08 Jul 1996 13:02:55 -0400

> additional experience under our belts will we consider doing measurement

What is really useful in this case is if weighted packet scheduling is
set according to the reservations.  If so, then elastic traffic,
particularly if using TCP sack, can exceed its reservation and get a
proportional share of any excess bandwidth, but never less than their
reservation if all of the flows are active.  Delay tolerant real time
which intends to remain within its reservation and expects no loss
will also work.

Curtis

---

From: John Wroclawski <[email-masked]>
Date: Tue, 9 Jul 1996 03:12:44 -0400

>are 'quite sure' utilization will be less.

Hi Greg,
This seems about right to me too, except that "on or off" is probably too
binary. I'd expect to find an agressiveness knob, which could be adjusted
(perhaps automatically, perhaps continually over time) until the actual
performance of the router/switch/whatever was acceptable to the operator
and their customers...

-john

---

From: Roch Guerin <[email-masked]>
Date: Wed, 10 Jul 1996 16:19:45 -0400

>which intends to remain within its reservation and expects no loss

Curtis,

I'd like to point out that while scheduling mechanisms such as WFQ,
that provide per flow bandwidth guarantees, are very important in
preventing excess traffic from some flows to impact (TSpec) conformant
traffic from other flows, they are only HALF of the story.  In
particular, you better make sure you also implement some appropriate
buffer management policy.   Buffers are just as important a resource
as bandwidth, and if the excess traffic from one flow is allowed to
deprive other flows from too much buffer space, then it does not help
that your scheduler enforces *fair* bandwidth sharing.

Dealing with elastic traffic or with traffic specifications that allow
excess traffic while providing guarantees to conformant traffic,
requires that you have BOTH bandwidth and buffer sharing mechanisms.
How sophisticated and, therefore, complex your buffer sharing
mechanisms will be depends on a number of things, but it is definitely
a component that needs to be accounted for in addition to the need for
per flow scheduling.  

As a side issue, I'd like to mention that
tagging, if available, can help quite a bit in making sure that you can
fully protect conformant traffic from excess traffic.  We had actually
tried to determine what would be required from a buffer management
policy in order to make such a statement a little more formal, and
reported on this in a paper that appeared in the June 1994 issue of
the IEEE/ACM Transactions on Networking and was entitled "On
Protective Buffer Policies".  Since then there has been plenty of work
done on various buffering policies, but I still think that for most of
them tagging would still help.  

Roch

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 10 Jul 1996 16:39:10 -0400

> a component that needs to be accounted for in addition to the need for

I've mentioned buffering so many times that I thought I'd spare the
list and not repeat it.

I'm sure you remember the suggestion to set an "r" according to the
minimum rate you are shooting for and "b=0" to allow a router to do
creative things with a shared set of buffers, such as run combinations
of WFQ and EPD or RED, dropping prematurely to reduce delay and keep
bandwidth utilization under control.  Then do what elastic traffic
does best and don't bother traffic shaping but use TCP congestion
avoidance.

I'll spare the list and not repeat the whole thing.

> them tagging would still help.  

Protecting the conformant traffic is easy.  Dealing with the excess
traffic in a way that is optimal for TCP or other adaptive window
congestion control is a bit more interesting.

Regards,

Curtis

---

From: Roch Guerin <[email-masked]>
Date: Wed, 10 Jul 1996 16:52:16 -0400

>Protecting the conformant traffic is easy.  

As long as you can do per flow accounting, i.e., have some counters
for each flow and be able to modify them each time a packet from that
flow is received AND transmitted, then you are right, it's easy....

>Dealing with the excess

TCP is clearly one of the main application for which you want to
understand this.  However, I'd be somewhat leery of designing some
buffer management hardware support (and you'll need that) that would
be too specifically tailored to a given application, unless it also
provided robust performance for others (and there certainly will be
others)

Roch