Subject: RE: differential services bof

From: [email-masked] (Kilkki Kalevi NRC/Hki)
Date: Thu, 21 Aug 1997 14:59:54 +0200

This is mainly a reply to David Clarks first mail sent 15th August (I try   
to go trough the whole discussion tomorrow).

David make a very good question about  the meaning of quality levels with   
SIMA concept. Here we must distinguish two different cases: (A) flows   
that are able to adjust their bit rate, usually using TCP protocol for   
that purpose, and (B), flows with a fixed bit rate.

In case (A) the effect of priorities in SIMA is that the available   
bandwidth is divided among the competing flows in proportional to the NBR   
of each flow. The accuracy of this division depends on the number of   
priority bits, and I believe that 3 bits = 8 levels give essentially   
better results than 1 or 2 bits. Our intention is to make simulations in   
the near future to analyse the real difference.

The overall behaviour in case (B) is somewhat more difficult to explain.   
In general, the main difference between services using different priority   
levels is that the customer always gets higher certainty for sufficient   
quality (or the probability that the application works properly is   
higher) if the NBR is doubled. We may also express this by using terms   
like long-term average packet loss probability, but that would be   
somewhat misleading. Now we may suppose that with priority 4 (that is,   
the actual bit rate is the same as NBR with certain accuracy) customers   
gets sufficient quality for video with probability of 98%. With priority   
5 the same probability could be 99.9% whereas with priority 3 it could be   
80% (or actually, priority level 3 can be sufficient always except the   
busiest hours). Priority 2 can be sufficient during idle hours. That is   
the main difference between priority levels, although the packet loss   
ratio during a certain period is also different. The significantly   
different values for the certainty is the property that makes reasonable   
the differences in charging levels.

As to the algorithms, I understand well that IETF is not willing to   
standardize any specific measurement or scheduling algorithm, however,   
for any performance analysis we must use some defined algorithms. My   
feeling is that with SIMA the measurement algorithm is not very critical,   
and that there could be various implementations. The scheduling is little   
bit different case. Now I am referring to David Clarks very good   
introduction into this problem area. We shall say for what purpose each   
priority bit is used inside the network: for drop preference, or   
selecting the queue (usually with different delay). Anyway, I think that   
it is very good idea to leave open the number of the bits used for drop   
preference (and for delay, as well), and we shall explicate the idea   
further.

In SIMA 3 priority bits are used for drop preference and rt/nrt bit for   
selecting the proper queue. But again, there could be different   
implementations for the scheduling algorithm itself.

So to apply the term "feel", my proposal is to use 8 "feels" for   
"certainty" and 2 "feels" for delay. But note that the 8 "feels" covers   
both guaranteed services and best effort, and both busies hours and idle   
hours. So we attain quite a much with these 3 bits, I believe, and   
without any resource reservations. That is one key issue, namely, my   
statement is that by using 3 priority bits it is possible to avoid   
resource reservations in the core network, whereas with 1 bit is not   
possible.

The reason to have one delay bit is that there are some applications that   
really need limited delay, like IP-phone and videoconference. In SIMA   
these applications can be integrated very smoothly to internet with   
highly variable data traffic, but we need the bit.

Finally, some words about the misbehaving flow in case of SIMA. Now if   
someone is sending much more than the NBR, he get the lowest priority.   
The key points here are that this traffic flow, however strong, do not   
disturb any of the higher priority levels (no congestion collapse in this   
case, and the operator may even limit the lowest level load at the   
network interface if necessary). So the lowest priority level offers a   
pure best effort service for anyone and for any traffic, but without   
absolutely any guarantees. On the other hand, this service is very cheap.   
This is one more reason to have more than two priority levels :-)

.. Kalevi

PS. The slides of my presentation in Munich are available at   
http://www-nrc.nokia.com/sima/

 ----------
From:  David Clark
Sent:  15. Augustta 1997 7:02 PM
To:  Juha Heinanen; int-serv
Subject:  Re: differential services bof

Precedence: bulk

Juha,
     I think it is good to get this discussion started.  Here are some
thoughts.

     There is one other specific but significant technical issue that   
came
up. Kalivi and I argue that the meaning of the preference bits should be
drop preference, Van argued that the meaning of the preference bits   
should
be priority queues.  This is not a minor difference, but reflects (I   
think)
a basic difference in the goals of the two approaches.

     My argument in favor of drop preference is that it keeps the packets
in order.  In Van's "hard drop if out of profile", he eliminates the   
option
of having a "multi-level priority flow", so out of order packets in a
single flow do not arise.  But that specific mechanical difference may   
just
mask the more basic difference in the goals of the two mechanisms.

     Here is the difference as I see it between drop preference and
priority queues  -- Van can tell me if/how I am wrong  :-).

      With priority, the more preferred packets always leave first. So   
they
get the lowest possible delay, subject only to the yet higher priority,
which can totally freeze out the lower priorities.  So priority does a
strong job of giving different levels of service a different "feel".
     Drop preference is intentionally a FIFO discipline among the
preference levels. As I use it, its goal is not to create "different
services", but one service (for example, our old friend best effort), and
to give more or less of it to one or another user.  To illustrate what I
mean,  if there is a queue in place, and then some higher preference
packets show up, they sit in the back of the queue behind the lower
preference packets. The dropper will soon come into play and start   
killing
new lower preference packets as they arrive, but the ones in the queue   
will
still be sent (unless you add a "drop at exit of queue" function as well   
as
my "drop at arrival to queue" function).
     I also said, in my talk, that I agree that we might need a different
service with a different feel, as Ed proposed concerning "SNA-style
transaction traffic",  In my approach, this would be a different queue,
selected by the ToS field, with drop preference optionally within the
queues.
     So both Van and I have two sorts of mechanisms -- different queues   
for
different services, and a way to regulate how much of the service   
different
users got.  Van uses priority as a mechanism inside the network to give
different services with different feel, and then regulates how much each
user gets of each service by hard-dropping at the edge.  I use different
queues in the network (without specifying the inter-queue service
discipline) to give different services with different feel, and use drop
preference to regulate how much each user gets.

    If this analysis is correct, then you cannot just modify Van's scheme
by saying that you prefer the idea of letting the "out traffic into the
system" and controlling it at the point of congestion. You also have to
specify how to allow different users to get different quantities of the
same service. If you start using the priority queues to regulate how much
traffic each user can send, they don't work at the same time to provide
different services with different look and feel.

       If you have different queues for different services (e.g. "normal"
and "low delay" best effort) you may sometimes want to pick different
service disciplines to control how the two are serviced. If you pick
priority, as Van did,  then the "low delay" can totally starve the
"normal". If you pick WFQ, then if you over-provision the "low delay"
queue, it will normally see real low delays, but if something gets out of
whack, and you get much more "low delay" than you thought, then the
"normal" queue can still get a share. Sometimes you may want one, and
sometimes the other. So I am not sure that we should standardize the
implementation approach if we define different services such as "normal"
and "low delay" best effort, just as we did not define the implementation
of "controlled load" real time. Instead, we described multiple
implementation approaches, described the benefits and limitations of   
each,
and left it as a matter for product differentiation.

     If you believe the discussion to this point, then adding more than   
two
levels of preference has a very different impact on the various schemes.
Now let me put words in Kalivi' mouth, so that _he_ can tell me I am
wrong...

    As I read Kalivi's ID, he is somewhere between me and Van, in that he
talks about his scheme delivering different QoS for different preference
levels. But the different QoS is primarily drop rates, I think.  (And, of
course, for good TCPs, drop rates translate into overall sending rate
differentiation.)  I would like to have him clarify if he believes that   
his
scheme can deliver different QoS's that differ in other significant ways.   
I
don't know how to do that with drop preference. It is possible that his
scheme and mine are not far apart.

    If you add more levels of drop preference to my scheme, you get a
finer-grained ability to express different profiles that apply at   
different
levels of congestion. In economics-speak, you are coding the user's   
utility
curve into the packet.  Kalivi sets them according to a fixed algorithm,
and I have not figured out exactly what utility curve that algorithm
expresses. We need some argument that it expresses a function that users
will find useful.  If you extend my scheme, one approach would be to let
the profile meter set the preference levels with some flexibility.  My
concern is that most users don't know their utility curve in any detail,   
so
it is an experiment to see if we can figure out how to use the bits.   In
the military context, where you might get major swings in provisioning,   
it
could be very helpful. Experimentation is needed.

    But this difference is minor compared to what happens if you add more
levels to Van's scheme. There, the consequence is to create more than two
services with different feel. And I would argue that having multiple   
levels
of priority is not helpful.  I don't think that we can construct more   
than
about two levels of best effort service that have a significantly   
different
"feel". We went through the same exercise with real time. Initially, we
proposed to have three levels of real time service, that would be
distinguished by the "feel" of the delay. The delays had to be
substantially different, to make the distinction worth having, and after   
we
screwed around with a range of offered loads and queue service   
disciplines,
we finally realized that if we forced the three levels of delay far   
enough
apart so that they really seemed different, the bottom two were worse   
than
best effort. So we bagged the whole idea, and just went for the very
simple, single level "controlled load". I suspect that the same will   
prove
true for best effort service as well -- I doubt that you can pull the
traffic apart into more than two queues, and still end up with queues   
that
actually have much of a difference in the serice they provide.

     There is also an implementation cost issue.  Priority queues require
multiple real queues, with a service discipline. So the complexity seems   
to
go up as the number of queues.  Multi-level drop preference has constant
(more or less) complexity -- you just run one of N copies of a RED
dropper,extending my proposal, where you executed one of 2 copies.

     So -- to summarize.

1) You cannot just change Van's scheme by removing the "drop if out of
profile" rule, since you leave his scheme with no way to regulate how   
much
of each service the users get.

2) Adding multiple levels of preference to my scheme is not a big deal,   
but
I am not convinced that you need it, so long as the provisioning is   
stable.

3) I think that adding more priority levels to Van's scheme is not   
useful.
It has a very different consequence.

4) I think that any scheme we use to allocate more or less of one service
to different users should keep the packets in order. Both drop preference
and "hard drop if out of profile" do this, but my scheme is more general,
and lets you offer a wider range of service profiles. With my scheme, you
could still create a sub-set of the profiles that did hard policing at   
the
profile meter.

Having said all that, let me put a question about which I am puzzled.   
Sally
Floyd objected to drop preference, on the following grounds.  If you have
responsive flows that adapt their sending rate, it may work fine. But if
you have hostile flows that just keep sending, you get the network full   
of
useless "out" packets, which flow part way through the net, messing up
other out packets on the way, only to be discarded. Sally  catagorizes   
this
as a form of congestion collapse.

Of course, this is the way that the Internet works today. Today,
non-responsive flows can flood the net with useless packets, killing off
well-behaved TCPs and each other.

If you take Van's approach, and "drop if out of profile" at the edge,   
then
(at least for the premium ToS) you absolutely elimiate this sort of   
stupid
flooding of the net by uncontrolled sources.

In my scheme, I have no cure for this silly behavior. My single service
class, regulated by drop preference, works just like the Internet today,   
in
that the outs make it all the way to the point of congestion before being
dropped. In my simulations, we demonstrated that we can discard massive
"out floods" without disturbing the "in" flows, but it is still true that
the "outs" are flowing part way through the net, messing each other up.

So now let me put words in _Sally's_ mouth...  I think what she said was
that if we used priority rather than drop preference, this would get
better. That implies to me that we are intending to use the priority to
regulate how much of the one service each person gets, rather than to
create different services. But (and I don't know how to use priority to   
do
a good job of that) if we are taking that approach, does priority queuing
help control the "flood of outs" problem?  I don't see how.

 (Note, hard policing to a fixed rate does not motivate adaptive sources,
but quite the opposite. It motivates sources that run at a fixed rate,
which is just below the profile they have been given. If it is fixed, why
build in adaptation?)

Enough, already...

Dave

---

From: Paul Ferguson <[email-masked]>
Date: Thu, 21 Aug 1997 22:06:42 -0400

It was my understanding that we were investigating ways
to differentiate traffic. The bit values, whether they
are indicated in the TOS or Precedence field, is a good
way to carry per-packet indications, but they are just
that -- indicators. The semantics aren't of much concern
to me at present as are the consequent actions which
certain bit values may trigger, or map into, as the
case may be.

Now, having said that, if by 'delay' you mean to
use these bit value semantics to vary the queuing
behavior, that's fine. However, if you have something
else in mind, then by all means, please elaborate on
what that might be. Or perhaps I missed something in
Munich or here on the mailing list.

I think we agree that precedence values can be used
for drop-preference, but I would very much like to
hear how delay fits into this scheme, if it is by some
other mechanism than ingress mapping into a CBQ or
WFQ scheme.

Thanks,

- paul

At 09:14 PM 08/21/97 -0400, Wu-chang Feng wrote:

>  >> "certainty" and 2 "feels" for delay.
>
>I would argue that you would need the reverse: one bit for bandwidth
>allocation and a lot more for delay.  The drop preference bit allows
>you to control bandwidth usage.  Simply varying the amount you mark
>(or unmark) a connection's packets gives you fine-grained control over
>the bandwidth usage of the connection.  On the other hand, because
>delay is a per-packet property, you need the extra levels in the
>packet to be able to control its behavior in a fine-grained manner.
>

---

From: Wu-chang Feng <[email-masked]>
Date: Fri, 22 Aug 1997 09:01:34 -0400

>> Now, having said that, if by 'delay' you mean to use these 
  >> bit value semantics to vary the queuing behavior, 

yup, that's what i mean.  if we want to provide differentiated delay
at the IP level, a single bit is rather frugal.  if i labeled
everything that was delay-sensitive with this bit, then without
looking outside of the IP header i wouldn't be able to to
differentiate between something like telnet (delay matters but isn't
that important) versus something like live audio/video.

wu