Subject: Re: Controlled-Load comments

From: [email-masked] (Christian Huitema)
Date: Sat, 24 Feb 1996 13:51:49 +0100

At 10:55 AM 23/2/96, Roch Guerin ((914) 784-7038) wrote:

>
>C. Adaptive and Non-conformant (or not necessarily Conformant)
>--------------------------------------------------------------

I guess this is an attempt to encompass Juha's draft and my own remarks.  I
believe that this third class is probably the most important of all, the
second one being "non adaptive and conformant" for our legacy of rigidity,
and anything else making little sense IMHO.

>These are applications which declare a rate parameter r and possibly (more
>on this below) a token bucket size b.  The expectation is that the rate
>parameter r is the minimum guaranteed rate but the application will try to
>send more if needed and possible, and it expects to get a *fair* share of
>any available bandwidth in excess of its guaranteed minimum rate r.
>The application will rely on some higher level mechanism (flow control)
>to throttle its rate in case of congestion.  The applications expects
>that if it sends at its guaranteed rate r, it will experience minimum
>packet loss and a latency *comparable* to that of a dedicated circuit
>at rate r.
>
>For service elements the requirements are as follows:
>
>1). Ensure that the flow is always guaranteed its requested rate r,
>2). Determine how to handle excess packets when the application sends
>    at a rate that exceeds r and the available bandwidth is insufficient
>    to sink this excess traffic,
>3). Allocate *enough* buffers to this class of service to be able to
>    deal with temporary overloads due to the latency in rate adjustments
>    in the presence of congestion.

Well, one caveat here.  Adaptive applications need some signal from the
network in order to adapt.  The widely used signal of the day is "packet
loss".  Attempts to adapt to variations of delay met with little success,
partly because the adaptation loop becomes extremely unstable - or too
stable.  Delay may vary for other reasons than congestion, e.g. rerouting.

Some buffering is OK.  Too much of it is a bad idea, destroying packets and
maintaining fluidity is generally better.

Christian Huitema

---

From: [email-masked] (John Wroclawski)
Date: Wed, 28 Feb 1996 12:07:23 -0400

Gees, this is really long. There's something of a summary in the last page
or so.

At 10:55 AM 2/23/96, Roch Guerin ((914) 784-7038) wrote:
>Specifically, I'd like to categorize applications along the following axes:
>
> 1. Adaptive vs non-adaptive
> 2. Conformant vs non-conformant
>
>where conformance is defined wrt to the traffic parameters that are
>*declared* at the time the service is requested

Roch,
I had a similar division in mind when I wrote C-L. We have come to slightly
different conclusions, but they may not be as far apart as all that.

>A. Non-Adaptive and Conformant
>------------------------------
>
>These are applications that declare traffic parameters, e.g., token
>bucket depth b and token generation rate r, and will comply with this
>declaration.  In exchange, such applications expect *all* their packets
>to be delivered (in order) with a latency *comparable* to what they
>would experience if they had a dedicated circuit of rate equal to
>the service rate they request, i.e., typically the token generation r.

The essence of this class is that because of completely conformant sources
or drop-policing at the edges of the network you know how much traffic a
flow can have in the middle of the network, and do not have to worry about
overload. You can thus design your algorithms to assume that traffic in the
net really should be there.

Controlled load does not claim to explicitly address this class. There are
several reasons, one of which is lame.

1) In a shared-reservation environment, the no-overload assumption above is
often not true even of the sources are conformant. Reservations will
frequently be for some number of senders less than the number present,
causing overload if more than that number send at once. So you have to be
prepared for it. The most extreme case is an RSVP WF reservation, where you
don't -know- the number of senders in advance.

2) The architectural goal of a service which makes each hop independent of
the others for its correct operation. Making use of the no-overload
assumption at a node implies that you are dependent on sources or upstream
routers to enforce traffic policing for you. As discussed in Dallas, we're
trying to avoid this when possible.

3) The continuing issue of denial-of-service to best-effort listeners by
reserved-bw listeners. In a service which tosses over-reservation traffic
or polices according to the reservation request, a reservation of zero
would disconnect best-effort listeners. The ideal result is that a
reservation of zero instead give best-effort service. (this is the extreme
case, of course, but the issue arises whenever the reserved bw is smaller
than the traffic load in an underutilized network.

4) (Lame) The overall int-serv architecture does not currently require that
a node know where it is in the network vis a vis its traffic sources, so it
has no concept of "edge".

Point 3 could be addressed by policing at the fringes based on the sender's
declared parameters rather than the reservation TSpec. There's been some
discussion of this, and making this possible is one reason I suggested
changing RSVP's SENDER_TSPEC object from optional to required a while ago.
A service which did this would take as argument a PSpec, in addition to a
TSpec and Rspec.
It would mean that the service could not be used in situations where the
sender's traffic parameters are not known by the thing setting up the
reservation.

This seems OK at first. However, if you continue to allow reservations
smaller than the sum of the sender Tspecs at any point in the network, you
still have the overload and denial of service possibilities. If you insist
that reservations be for at least the sum of the sender TSpecs, you lose a
key benefit of the RSVP-style shared reservation.

Considering these issues, I decided that CL should not specifically support
this case. Since the case is a simplification of the others, I suspect
it'll work reasonably well anyway.

>
>B. Non-Adaptive and Non-conformant (or not necessarily Conformant)
>------------------------------------------------------------------
>
>These are applications which also declare traffic parameters, e.g., (r,b),
>and expect the same kind of service as applications from category A
>for traffic within this advertised traffic envelope.  The difference is
>that the application may occasionally send at a higher rate, and is
>willing to see degraded service for these excess packets.  For a service
>element, the issues are
>
>1). Allocate enough resources for the declared traffic parameters
>2). Identify excess traffic
>3). Determine what to do with excess traffic
>

No disagreement with your description of allocating resources and
identifying excess traffic, although I'll point out that the criticality of
identifying excess traffic completely accurately depends on what you do
with it afterwords.
Getting it just right is more important if you are then going to drop it
immediately than if you are going to buffer it in-order, say.

>Once packets have been identified as excess, the options are then to:
>
>a). Keep delaying them as long there is buffer space available,
>b). Drop them,
>c). Send them as best effort.
>

True as far as it goes. If "send them best-effort" means "dump them in a
separate lower-priority queue", there is a fourth option; buffer and send
them in-order as long as the actual experienced delay is not excessive. The
exact definition of "excessive", in terms of both delay and duration of the
excess-delay event, comes back below.

This raises the question of -why- the non-conformance occurred. Since we
are talking here about non-rate-adaptive applications, the usual cause of
overload will be that too many sources sent something at once through a
shared reservation. The expectation in this case is that the flow will
receive poor service - either higher transient delay or packet loss. The
expectation is also that the overload situation is transient - eventually
the extra people will stop talking, or whatever, and the congestion will
clear.

If the reservation is too small for the number of continually sending
sources (say it is smaller than a single source, for clarity) and the
network does not have enough excess capacity to send the traffic with low
delay, the delay will get high and the dropper will start dropping pkts.
That is an expected and acceptable result.

In either case, there is no expectation that an over-profile flow in an
overloaded network will get decent service. The only goal of the service in
this case is to protect -other- traffic from the non-adaptive over-profile
flow.

>Option a) is probably not desirable for a non-adaptive application as it
>will impact subsequent packets that may then see a much increased latency.

Yes, although because the common cause of congestion is self-correcting, it
may actually not be a serious problem, as long as other flows are
protected.

>So, the choice is most likely between dropping and sending as best effort.

The choices are immediately dropping all excess traffic, sending the excess
traffic in-order as long as there is enough b/w, and sending the excess
traffic out-of-band by putting it into a separate best-effort queue.

The C-L spec specifies that you can't do immediate dropping for the same
reasons given above - denial of service to best-effort receivers and so on.
Either of the latter two choices are allowed.

I discussed the send-in-a-separate-best-effort-queue case in my note to
Curtis yesterday. I said that it seemed like a less desirable solution than
sending in-band, but that it was cheap and easy to implement and worked
acceptably for one class of network, so I had allowed it.

The other option is to send the pkts in-band as long as there is b/w to do
so, and drop them otherwise. The question now becomes how and how fast you
need to start dropping.

If I were Juha or perhaps you, I would have said that "enough b/w to do so"
means "fair share". I didn't, because I have some worries about the
definition and implementability of that phrase. But I would say that that
is the ideal.

One possibility is that you try to write a spec which requires the
scheduler to do this completely accurately, so that -no- "excessively
excess" packets are ever queued. However, as I argued above, I think that
the controlled-load usage pattern for this class of source allows for
transient delay events and so on under overload, so I am prepared to let
you use something like RED to manage the excess b/w.

The above paragraphs are what the C-L spec intends to say. As I said to
Curtis, if you think it says something drastically different, then there is
a problem with the wording of the spec.

>C. Adaptive and Non-conformant (or not necessarily Conformant)

Sounds good, though again I would avoid the specific words "fair share".

Now, the question is how much the mechanisms needed to implement this
differ from those implementing the non-rate-adaptive non-conformant case.

You mention two choices:

>If the flow specified a b term, then this value can be used to decide when
>a packet is an excess packet.  One option, if the flow is tolerant of
>reordering and there is a lower priority best effort service class, is to
>send the excess packets [in that class].

This is the same as one of the choices for the non-adaptive case. I talked
about it above, as a less desirable choice. I think it is less desirable
primarily because it's not great for today's rate-adaptive applications
(such as TCP), and I suspect that rate-adaptive multicast applications will
work more like Steve Mccanne's VIC, using multiple fixed-rate mcast groups
to do rate adaption.
So it may turn out that there are no "rate-adaptive-per-flow" appications
(as opposed to the mcast join-leave model) for which this option is a good
choice.
In any event, the C-L spec says basically the same thing you did about how
it should be done, and it is the same for both classes.

>Another option, that is more suitable for application that are sensitive
>to packet reordering, is to buffer excess packets as long as there is
>buffer space available, and keep transmitting them at whatever rate is
>available to the flow, i.e., at least r.  When buffer space is exhausted,
>packets will be dropped.

Now here we differ. I would say that rather than buffering "as long as
buffer space is available", you should run RED or similar, to allow
transient buffering while pushing back to cause adaptation against
long-term overload.

Further, I suggested above that this sort of buffer management was also
acceptable for the non-adaptive case, given the sources of over-profile
behavior in that case. So the basic structure of the queue management can
be the same.

The open question is whether the specific parameters of this buffer
management algorithm are similar enough for the two cases that you can just
make them the same. There is some reason to think that it is, because the
RTT of a TCP connection and the response time people will accept for
non-adaptive congestion management (basically a human factors question) are
of the same timescale. If the parameters can be the same, we are back to
the situation where the service provided for the two cases is identical.

>Note that the value of b should not be used as the threshold value
>beyond which to start dropping packets.  This is
>because you would then run into the problem pointed out by Curtis, where
>you would need to specify a very large b in order to ensure decent
>performance when you are blasting at a rate much higher than r.

The network element is managing (at least) two resources, b/w and buffer space.
They are somewhat orthogonal. If you want to -ensure- decent performance
(assuming b/w is available) you have to ask the router to allocate you some
buffers. This is a resource reservation as much as reserving b/w is; you
are asking the router to preferentially allocate you something.

If you are willing to take your chances on the router's buffer pool as well
as the b/w, then you don't need to ask for much b; you'll get whatever is
available. This is what C-L says today.

>Here, the value of b should be used for buffer management to determine the
>respective amount of excess traffic of different flows.  This could
>then be used to determine which arriving packets to drop.

Well, which arriving packets to subject to the unreserved-resource buffer
allocation competition. But yes, basically. This does not differ from the
non-adaptive case.

This is getting really long. let me jump to your summary.

>SUMMARY
>-------

>- Guaranteed Bandwidth (non-adaptive, conformant flows)
>
>  User specifies TSpec (r, b) and agrees to comply with it, i.e., allows
>  policing at the boundary and reshaping within the network.

C-L does not address this, or more precisely it does not take advantage of
the garanteed conformance because of shared-reservation and
bes-effort-receiver issues. For what it's worth, Guaranteed-Delay is a
fairly close match. But if it turns out that C-L is inadequate for this
class of application, I think a new service should be defined.

>- Controlled Load (non-adaptive, not necessarily conformant flows)
>  Two flavors CLa and CLb as a function of how excess traffic is treated
>  (could be specified through a bit or a different service number)
>
>  User specifies TSpec (r, b) but does not agree to comply with it, i.e.,
>  may be sending more occasionally.  The user understand that no
>  guarantees can be provided for its excess traffic.  However, it
>  specifies either one of two handling for its *excess* traffic:
>
>  a. Delay and drop, i.e., preserve ordering,
>  b. Send as best effort, i.e., do not necessarily preserve ordering.
>
>  The service elements guarantee the availability of a bandwidth at least r
>  to the flow, a fair share of any additional bandwidth available, and
>  dedicate enough buffer to it so that losses of non-excess packets are
>  rare and few non-excess packets get classified as excess (to be engineered
>  for each service element).
>
>- Protected Best Effort (adaptive flows)
>  Two flavors PBEa and PBEb as a function of how excess traffic is treated
>  (could be specified through a bit or a different service number)
>
>  User specifies TSpec (minimum guaranteed rate r, and optionally a *buffer
>  sizing* parameter b).  It expects to be guaranteed a bandwidth of at
>  least r, plus a fair share of any additional bandwidth that is available.
>  In case of congestion, packets sent in excess of the guaranteed rate r
>  will be handled in either one of two ways as specified by the user:
>
>  a. Buffer as long as there is space available, [i.e perserve ordering]
>  b. Send as best effort when flow backlog exceeds given value, i.e., b.
>
>  The service elements guarantee the availability of a bandwidth at least r
>  to the flow, a fair share of any additional bandwidth available, and
>  dedicate enough buffer to this service class to accommodate temporary
>  overloads, i.e., there better be large buffers for this service class.

I quoted this at length to show how similar they are. The -only- difference
in these two things is the line:

>  dedicate enough buffer to it so that losses of non-excess packets are
>  rare and few non-excess packets get classified as excess

vs.

>  dedicate enough buffer to this service class to accommodate temporary
>  overloads,

I argued above that in either case the way to do this is to do it with an
active buffer management algorithm such as RED, which allows transient
overload, keeps average buffer use & delay low, and deals brutally with
overload by non-adaptive sources. I suggested that it seems quite possible
that the parameters of this algorithm could be identical for the two cases,
although if it turned out that they weren't there would then be a need to
distinguish between the two.
Finally, I claimed that of the two options

>  a. Delay and drop, i.e., preserve ordering,
>  b. Send as best effort, i.e., do not necessarily preserve ordering.

the second was fairly consistantly less desirable, in the sense that any
application which wanted it could also use the first choice, while the
opposite was not true. This suggests that making it an application option
(and thus asking everyone implement both) might not be necessary, although
allowing it with a warning label (for use in those networks being designed
for one type of application) would make sense.

        -john