Subject: differential services tos octet

From: Juha Heinanen <[email-masked]>
Date: Fri, 3 Oct 1997 11:53:54 +0300

i submitted the enclosed document to the internet drafts editor.  if
there is a differential services bof in washington, i would like to
discuss the document there.  comments on the mailing list are, of
course, also appreciated.  please let me know, if differential services
already has its own mailing list.

-- juha
-------------------------------------------------------------------------

Internet Engineering Task Force                            Juha Heinanen
INTERNET DRAFT                                           Telecom Finland
Expires April 1998                                          October 1997

       Use of the IPv4 TOS Octet to Support Differential Services
                 <draft-heinanen-diff-tos-octet-00.txt>

Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups. Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time. It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as ``work in progress.''

   To learn the current status of any Internet-Draft, please check the
   ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).

Abstract

   This document describes how the TOS octet in the IPv4 header can be
   used to support differential Internet services.  The proposal is
   based on the existing format of the TOS octet as defined in [RFC791]
   and [RFC1349].

1. Introduction

   In order to support differential services within the Internet, such
   as those proposed by [Clark] and [Kilkki], the routers must be able
   to distinguish, how they should treat IP packets in terms of Type of
   Service (TOS) and Drop Preference (DP).  The TOS usually indicates
   the desired delay characteristics of the packet, whereas the DP
   identifies how "important" the packet is if packets need to be
   discarded due to congestion.

   In a typical router implementation, each TOS has its own queue, which
   it serves with such a policy that meets the characteristics of the
   TOS.  The DPs, on the other hand, map to queue thresholds so that an

Heinanen             Differential Services TOS Octet            [Page 1]

INTERNET DRAFT                                             October, 1997

   incoming packet with a DP value i may be discarded if the length of
   the corresponding queue has exceeded a threshold value th(i) of that
   queue.

   The TOS of a packet is set by the application or, if the application
   is unaware of differential Internet services, by the operating system
   or a router.  In the latter two cases, the TOS may be determined from
   the TCP/UDP port numbers of the packet.

   The DP of a packet can also be set by the application, the OS, or a
   router, but the criteria based on which the DP is assigned can vary
   widely.  For example, a packet may be assigned a higher DP if it is
   consider to be "outside" of a given user profile.  For more
   information on policies to set the DP, see [Clark] and [Kilkki].

2. TOS and DP in the IPv4 Header

   Ideally, in order to support a wide range of TOSes and DPs, the IPv4
   header should have several bits available for this purpose.  Luckily,
   the The IPv4 header has an 8 bit TOS octet, that can be used to carry
   the TOS and DP information.

   According to [RFC791], the IPv4 TOS octet is divided into a 3 bit
   Precedence field and a 3 bit TOS field.  The last two bits of the TOS
   octet are reserved for future use:

         Bits 0-2:  Precedence.
         Bit    3:  0 = Normal Delay,       1 = Low Delay.
         Bits   4:  0 = Normal Throughput,  1 = High Throughput.
         Bits   5:  0 = Normal Reliability, 1 = High Reliability.
         Bit  6-7:  Reserved for Future Use.

   The following two sections propose how the TOS and DP information
   needed to provide differential Internet services can be mapped to the
   IPv4 TOS octet.

3. Drop Preference (DP)

   The semantics of the 3 bit Precedence field doesn't contradict its
   use as the DP field:

       "Several networks offer service precedence, which somehow treats
       high precedence traffic as more important than other traffic
       (generally by accepting only traffic above a certain precedence
       at time of high load)."

   However, the actual meaning assigned in [RFC791] to the 3 bits of the
   Precedence field is outdated and not very useful:

Heinanen             Differential Services TOS Octet            [Page 2]

INTERNET DRAFT                                             October, 1997

       111 - Network Control
       110 - Internetwork Control
       101 - CRITIC/ECP
       100 - Flash Override
       011 - Flash
       010 - Immediate
       001 - Priority
       000 - Routine

   On the other hand, [RFC791] further specifies that the Precedence
   field has only local significance within a single network:

       "The Network Control precedence designation is intended to be
       used within a network only.  The actual use and control of that
       designation is up to each network. The Internetwork Control
       designation is intended for use by gateway control originators
       only. If the actual use of these precedence designations is of
       concern to a particular network, it is the responsibility of that
       network to control the access to, and use of, those precedence
       designations."

   This makes it easier to refine the precise semantic of the precedence
   values without breaking possible existing usage of the Precedence
   field.

   It is proposed that differential Internet services use the Precedence
   field of the IPv4 header to indicate the DP of the packet.  The DP of
   the packet can range from value 0, indicating the lowest DP, to value
   7, indicating the highest DP.

   A network does not need to implement all 8 DP levels.  The table
   below shows how a network can map a DP value given in the Precedence
   field of an IPv4 packet to any number of DPs actually supported by
   it:

        DP        Number of Supported DPs
       value     2   3   4   5   6   7   8
       -----------------------------------
         0       0   0   0   0   0   0   0
         1       0   0   0   0   0   0   1
         2       0   0   1   1   1   1   2
         3       0   0   1   1   2   2   3
         4       1   1   2   2   3   3   4
         5       1   1   2   3   4   4   5
         6       1   2   3   4   5   5   6
         7       1   2   3   4   5   6   7

   The above mapping thus supports the 2 DP levels as proposed by

Heinanen             Differential Services TOS Octet            [Page 3]

INTERNET DRAFT                                             October, 1997

   [Clark] and the 4 DP levels as proposed by [Kilkki].

4. Type of Service (TOS)

   The 3 bit TOS field can be used to indicate the actual Type of
   Service that an IP packet expects to receive from a network that
   supports differential services.  As already shown above, [RFC791]
   specifies the following semantics for these 3 bits:

         Bit    3:  0 = Normal Delay,       1 = Low Delay.
         Bits   4:  0 = Normal Throughput,  1 = High Throughput.
         Bits   5:  0 = Normal Reliability, 1 = High Reliability.

   In [RFC1349], the TOS field has been extended by one of the reserved
   bits of [RFC791] resulting in the following semantics for the bits
   3-6 of the IPv4 TOS octet:

         1000   --   minimize delay
         0100   --   maximize throughput
         0010   --   maximize reliability
         0001   --   minimize monetary cost
         0000   --   normal service

   It is not known to the author, what the status of [RFC1349] is in
   terms of the standards' process or implementations.

   Ideally, the whole TOS field of IPv4 TOS octet should be usable by
   differential Internet services to support a wide variety of delay
   characteristics.  However, because it is not known yet, how many
   delay levels will actually be needed and because the standardization
   of the semantics of the TOS field is still at least somewhat open, it
   is proposed that initially networks that support differential
   Internet services only use the bit 3 of the TOS field to indicate the
   desired delay treatment of a packet.

   This is a safe choice, since the Bit 3 of the TOS octet is the delay
   indicator bit according to both [RFC791] and [RFC1349].  By setting
   the Bit 3 to 0 or 1, the packets requests a normal or low delay,
   respectively.  The possibility to request for low delay is believed
   to be important in facilitating large scale deployment of the rapidly
   emerging real-time applications, such as voice and video over IP.

   The use of the Bits 4-7 of the TOS octet in connection with
   differential Internet services is left for further study.

Heinanen             Differential Services TOS Octet            [Page 4]

INTERNET DRAFT                                             October, 1997

5. Summary

   This document has proposed how the IPv4 TOS octet can be used to
   support differential services within the Internet.  The proposal does
   not include any syntactical changes to the IPv4 header and even the
   semantic changes are kept to the very minimum.

   The author hopes that this proposal could help to create a common
   convention on the usage of the TOS octet for the support of
   differential services within the Internet.  Such services will be or,
   more precisely, are being implemented anyhow and it is thus very
   important that the implementations and service offerings will be
   compatible with each other.

6. Security Considerations

   Security is not addressed in the current version of this document.

References

   [Clark]  Clark, D. and Wroclawski, J., "An Approach to Service
   Allocation in the Internet".  draft-clark-diff-svc-alloc-00.txt, July
   1997.

   [Kilkki]  Kilkki, K., "Simple Integrated Media Access (SIMA)".
   <draft-kalevi-simple-media-access-01.txt>, June 1997.

   [RFC791]  Information Sciences Institute, "Internet Protocol".  RFC
   791, September 1981.

   [RFC1349] Almquist, P., "Type of Service in the Internet Protocol
   Suite".  RFC 1349, July 1992.

Acknowledgements

   I would like to thank Kalevi Kilkki for his comments on earlier
   versions of this document.

Author Information

   Juha Heinanen
   Telecom Finland
   PO Box 777
   33101 Tampere
   Finland

   Phone +358 400 500 958
   Email [email-masked]

Heinanen             Differential Services TOS Octet            [Page 5]

---

From: "Eric S. Crawley" <[email-masked]>
Date: Tue, 14 Oct 1997 10:14:22 -0400

Juha,

[Sorry to take so long replying to this, but there hasn't been any other
noise on the topic since your initial message.]

Thanks for writing your draft on TOS octet usage.  It is good to have a
solid starting point for discussions on differential services.  I have a
few comments about your draft.

I don't quite understand the need for multiple drop preferences.  Is the
idea to have different levels of "out of profile-ness" such that as the
amount of data that is out of profile increases, so does the drop
preference?  Implementing the packet marker for such behavior sounds
difficult and it would require different RED thresholds for each drop
preference.  I don't see that this buys much.

Looking at the other field, the delay indicator from the TOS bits, I find
it interesting that you would only want one level of delay/priority
discrimination.  This is an area where I would expect to see more values.
I know it conflicts with the current definitions for the TOS bits but I
would think that offering different levels of priority (for different
amounts of $$) would be very interesting to some ISPs and their customers.
Yes, we can argue that only one level is necessary for separating "real
time" from "best effort" traffic 90% of the time, but we are talking about
service offerings where that extra 10% might be very important to some
customers.

I would rather see only one level of drop preference and multiple levels of
delay /priority indication.  Are there any others with thoughts and
comments in this area?

	Eric

---

From: Roch Guerin <[email-masked]>
Date: Tue, 14 Oct 97 15:15:17 -0400

>delay /priority indication.  Are there any others with thoughts and

Eric,

I totally agree with you.  I'm in the process of writing-up some stuff
to try articulate some reasons behind this position, but I really
think that delay/priority classes is where we need to see more levels,
rather than drop precedence which should really be used only for
non-conformance (out-of-profile) indication.

Roch

---

From: Steven L Blake <[email-masked]>
Date: Tue, 14 Oct 1997 15:28:34 EDT

> preference.  I don't see that this buys much.

This should enable some control on the thruput of the individual TCPs,
depending on their particular traffic class (i.e., drop preference).
There are other ways of achieving this though, such as toggling a single
drop-preference bit based on compliance to some traffic profile at the
network ingress (i.e., something like Dave Clark's scheme).  One scheme
requires a little more dynamic state in the network vs. the other, but may
enable finer granularity of control.

> service offerings where that extra 10% might be very important to some

Multiple delay priorities are a critical feature of many corporate networks
today.

> delay /priority indication.  Are there any others with thoughts and

Strict delay and/or loss priority does not cover all of the useful 
applications of a TOS field.  There are others, such as FECN, IntServ
policer conformance/aggregation class, TOS routing, CBQ, etc.  Ed Ellesson
and I are finishing up a draft on issues and applications of packet marking
for differentiated services which we hope to have available in a few weeks. 

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

---

From: Fran Reichmeyer <[email-masked]>
Date: Tue, 14 Oct 1997 16:49:29 -0400

Hi,

Sorry about this, but could somebody re-post, or mail to me, the 
the original message that started this thread? I would appreciate
it.

Thanks!
-Fran

-- 
Francis Reichmeyer             Bay Networks, Inc
Bay Architecture Lab           3 Federal Street
                               Billerica, MA  01821
email: [email-masked]    phone: 508-916-3352

---

From: Tracy Mallory <[email-masked]>
Date: Tue, 14 Oct 1997 15:59:45 -0700

I thought the reason for multiple drop priorities was to allow 
multi-level coded video streams (e.g. video) to use as much bandwidth
as possible, where the number of levels was >2. If you have to drop 
some packets, drop these first, and if you have to drop even more, 
then drop those, but please try your very best for what's left. On the
surface, this seems a reasonable goal, and should not be set aside 
without some explanation.

My excuse for sending this note is my knee-jerk reaction to "I don't 
quite understand the need for...", since this issue was discussed 
on the list.

I think there were some reasons why this wasn't a great idea, and
some alternative schemes for achieving a similar service. It would be
nice if someone could drag them up. I apologize for not having the
time, but I was lucky (although perhaps my audience might disagree;-)
to even have read this set of messages.

Regards,

Tracy Mallory
[email-masked]

---

From: Fred Baker <[email-masked]>
Date: Tue, 14 Oct 1997 18:26:22 -0700

>delay /priority indication.  Are there any others with thoughts and

Juha and I have been having some private discussion on delay vs drop
precedence, which I will summarize and Juha can correct my summary :^)

First, my viewpoint.

Basically, it seems to me that delaying (queuing by some discipline) and
dropping (RED with some priority scheme) are both ways to manage internet
congestion. In some cases, one is appropriate and in some cases the other
is appropriate.

RED is useful at high speed, and RED with a drop precedence is a way to
implement something like Frame Relay CIR in IP. This will be very useful in
implementing a better economic basis for service providers. RED is,
however, stochastic, and while it has tweaks and features that help improve
fairness (see the recent SIGCOMM, or pointers off Sally's RED page, for
details), it is imperfect.

Queuing is far less useful at high speed, both because it takes more memory
cycles and because there are many more flows crossing the typical interface
than there are packets in queue, making sorting by any algorithm a less
effective procedure. However, at lower speeds where the ratio of active
flow count and queue depth makes the sorting effective, sorting is far more
deterministic and demonstrably fair.

But the end system cannot reliably determine what interfaces its traffic
will cross, nor can it know reliably what algorithms the routers and
switches en route will use for congestion management, and it cannot
determine what traffic it will be being compared against in those routers
and switches. Hence, it doesn't make sense for the end system (or its proxy
in a router) to separate the concepts, to say "I have low delay priority by
high drop priority" or some such thing.

What it can say (or its router proxy at the edge of an ISP network can say)
is: "these packets meet my token bucket rate criteria and are therefore
worthy of a higher probability of timely delivery, and those others do not
and are therefore less worthy." SO to me, it seems that we one set of bits
which are a "degree of worthiness of timely delivery" - a higher precedence
setting gets you a higher probability of timely delivery, which when it is
interpreted by a particular router or switch is interpreted in light of the
algorithms that router or switch is using on that interface.

A potential refinement for routers deployed by ISPs and measuring traffic
rates might be to leave the least significant bit of the precedence alone.
The ISP's high/low precedence setting dependent on whether the message fits
in the token bucket then becomes four different values - high/low priority
to the user, and high/low sith respect to the service level agreement. And
it could become six if  RSVP were used as a way to signal to the ISP that a
certain flow was extra special - the ISP would then mark it as "really
high" priority if it were within its RSVP token bucket. Again, this would
be regulated by the service level agreement.

If I can correctly state Juha's perspective, he feels that drop and delay
precedence are different functions semantically, and should be separately
specified by the sender. If the sender always sets them both the same way,
so be it.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  "A beautiful idea has a much greater chance of being a correct idea
   than an ugly one."
                     -- Roger Penrose, "The Emperor's New Mind", 1989

---

From: Keith McCloghrie <[email-masked]>
Date: Tue, 14 Oct 1997 23:56:30 -0700 (PDT)

Roch,
 
>     ... drop precedence which should really be used only for

Why should drop precedence *only* be associated with out-of-profile ?

Wouldn't it be useful to have multiple classes of Best Effort service
in a campus without the sources needing to have a profile, and using
drop precedence as the means for the more "important" traffic to get
through during periods of congestion because the less "important" traffic
gets preferentially dropped ?  (Note that I'm assumming here that both
the more important traffic and the less important traffic have the same
delay/jitter requirements, and so would be placed into the same queue.)

Keith.

---

From: Roch Guerin <[email-masked]>
Date: Wed, 15 Oct 97 08:00:18 -0400

Keith,

Let me clarify what I meant as the term "drop precedence" is indeed
loaded and does not really capture what I wanted to say.

>Why should drop precedence *only* be associated with out-of-profile ?

This is not exactly what I meant to imply.  I think that there are two
separate and important semantics we need to support.  The first is
providing for the specific identification of "out-of-profile" packets,
and I think that we need a bit for that purpose.  Usually, the bit
will then be used to implement some kind of drop precedence, which is
why I linked the two, but this need not be the case.  How the routers
act on the marked packets is essentially implementation specific.  The
main point is that they have an explicit mechanism to identify
out-of-profile packets without having to maintain per flow state.

>delay/jitter requirements, and so would be placed into the same queue.)

The second semantic we need to support is for different service
classes, and for that we most likely need more than one bit.  I
personally view those classes associated with delay differentiation,
but as was mentioned in the note Fred sent earlier, this does depend
on the underlying implementation in the routers.  

Nevertheless, it would be good if we could agree on some definition
for the service specification associated with each class, as otherwise
it will be difficult to provide consistent and predictable service
guarantees.  In that context, I do prefer a delay based definition as
I think it is easier to specify (quantitavely) and also many of the
underlying implementations, e.g., separate queues, can also be used to
provide throughput differentiation through appropriate buffer
management.  I think it is much harder to provide quantitative service
guarantees when using multiple drop thresholds in a single queue.

Roch

---

From: "Eric S. Crawley" <[email-masked]>
Date: Wed, 15 Oct 1997 13:37:07 -0400

Tracy,

Thanks for the reminder on hierarchical video streams.  Yes, I see how
multiple drop priorities could be used in this context.  I do recall the
application but I don't recall the discussion as it relates to differential
services.  

I guess this is a different view of differential services than I had been
thinking about.  To use multiple drop preferences, it is likely that the
end system would have to set the bits rather than the edge router.  It also
confuses what is "in" and "out" of a given profile since the end system, or
something intimate with the encoding, would have to set the drop preference
bits.

I'd like to hear from some service provider types to know if multiple drop
preferences is something they would like to see.  Also, I'm interested to
know if lumping multiple drop preferences to a single bit will completely
screw up the service model.

	Eric

---

From: Steve Deering <[email-masked]>
Date: Wed, 15 Oct 1997 10:53:31 -0700

Support for drop preference creates an undesirable incentive for
applications to send packets that will not reach their destinations
(knowing that the routers will discard the "less important" or "out-
of-profile" packets at a point of congestion).  Packets that fail to
reach their destinations consume bandwidth on all the links up to
the drop point, bandwidth that might otherwise have been productively
used by other traffic flows destined to different places.  It is much
better, from the point of view of efficient use of the Net, to design
the applications to desist from sending undeliverable traffic along
congested paths, but the application designers won't go to the effort
of designing effective congestion-backoff mechanisms if they can rely
on drop preference instead.

Providing quantitative service guarantees removes the desirable incentive
for applications to be adaptive to a wide range of delivered services.
For example, it is likely to lead to Internet telephone/voice-conferencing
applications that fail to work for talking between the earth and the moon
because the delay bound "required" for interactive conversation cannot be
met.

Steve

---

From: Steven L Blake <[email-masked]>
Date: Wed, 15 Oct 1997 17:59:56 EDT

> on drop preference instead.

The Clark/Wroclawski scheme at least assumes that the drop-preference (DP)
bit is set in the network and that the applications utilize traditional
congestion-backoff mechanisms (e.g., TCP).  So your comment doesn't apply
there vis-a-vis application incentives (I don't recall specifically what
was assumed in the SIMA proposal).

As to your concern about doomed DP traffic consuming useful bandwidth on
uncongested links: if the links are uncongested, then the average buffer
occupancy is low (otherwise, the DP packets would automatically get
discarded on these links).  There is no "cost" to forwarding a packet
which arrives to an empty buffer; it doesn't affect the thruput of any
other flow since it doesn't deny it access to the link.  DP packets can
only impact the thruput of non-DP flows if in the aggregate they a) cause
non-DP packet loss, b) add non-trivial queueing delay to non-DP packets,
and c) occupy some steady-state fraction of the queue when there are non-DP
packets in queue.  The way to prevent this is to always drop DP packets
first and to regulate the amount of buffer slots that the DP packets can hold
while there are non-DP packets also in the queue (ultimately so that the
steady-state average is less than one).  I can think of at least four ways
of implementing this.  So all that is needed is a sensible DP discard
policy which renders the DP packets "invisible" to the non-DP packets. 

Now, what is the incentive for applications to backoff from congestion
anyways, with or without DP, and how does DP implemented as described
above worsen this?

> because the delay bound "required" for interactive conversation cannot be

Three points:

1. Adaptive applications are useful only for adaptive users.
2. Not all users are adaptive.
3. Some users will pay more so that some other guy has to adapt.  :)

Regards,

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 16 Oct 97 15:04:54 JST

Steve;

> of-profile" packets at a point of congestion)

It seems to me that, becasue of elastic non-DP traffic, a lot of
links are used up their bandwidth by non-DP traffic.

That is, almost all the congested points are fully congested by
non-DP packets.

Then, what is the point to have DP packets?

							Masataka Ohta

---

From: Juha Heinanen <[email-masked]>
Date: Thu, 16 Oct 1997 10:44:51 +0300

Eric,

as i indicate in the i-d, i too would like to have more bits for
delay/priority.  the only reason why i propose at this point to have
only one bit, is that the tos field as currently defined doesn't have
more available.

what comes to the number of drop preference bits, i could imagine to
live with one, but if an isp wants to support kalevi's scheme
(draft-kalevi-simple-media-access-01.txt), then at least two dp bits
are needed. 

one possibility (that i ssuggested privately to fred) would be to use
the last bit of the precedence field as a delay precedence bit, that is,
if D bit of the tos field is "low", then the last bit of the precedence
field would tell how low.  that would give two levels of time
sensitiveness in addition to normal delay.

the simplest thing, of course, would be to start from scratch and use
two bits for drop preference and two bits for delay, where time
sensitiveness would increase from 0 to 3.  but i don't know how many
existing things would such a change break.

-- juha

---

From: "Alessio Casati" <[email-masked]>
Date: Thu, 16 Oct 1997 12:08:22 +0100

Steve,

As you point out the target Differential Services Model (that is the future
Internet Model) is to be based on a disincentive structure for out of profile users built into the 
network, leading application designers to develop adaptive applications. That was strongly 
stressed by Van at the Munich meeting. This much seems to make sense.
However a DP bit cannot but help in keeping router queues free.
Let us consider your example. Imagine what's the most likely behaviour of users (and applications).

        S1 ---<300>--- A                    E ---<300>--- R2
                        \                  /
                         \                /
                          C ---<300>--- D
                         /                \
                        /                  \
        S2 ---<300>--- B                    F ----<50>--- R1
 
1) Users do want video: both make video with high priority.
R1 won't receive any video. So, good application designer will design the application so that
in such a situation it sends a bit to the sender saying "Please, don't send Video, It's useless 
(and is going to penalize us)"
As soon as S1 refrains from sending video, good news for (S2,R2). Now and then S2 will attempt to
increase the DP to probe for bandwidth (and lower ISP rates) and ultimately (steady state)
It's very likely (S2,R2) will send with higher DP than audio.

2)Video is not a strict requirement for both of the users
Both of them will be happy even in the unlucky setting you depict.

3)(S1,R1) don't want video and quit => Good news for (S2,R2) which begin receiving full
video stream.

4)(S2,R2) don't want video => nobody gets happier, but is likely (S1,R1) will end up with
dropping their video flow and (S2,R2) will have more chances to find the deserved bandwidth
on probing for it.

How can the disincentive structure be implemented? Well, it would make sense to detect
people using applications looking more aggressive in the bandwidth probe/back off mechanism 
just outlined (RED drop statistic would help), so that there would be no advantage resulting from 
too frequent attempts to send out of profile packets (with ISP charging the whole traffic
it accepts).

So, Steve, why should DP bit be dropped, in your opinion?

bye

   Alessio Casati

On 15 Oct 97 at 17:36, Steve Deering wrote:

> At 2:59 PM -0700 10/15/97, Steven L Blake wrote:
> > there vis-a-vis application incentives...
> 
> Are you sure that the Clark/Wroclawski scheme assumes all traffic will be
> well-behaved TCP or similar?  How would they cause that assumption to be
> satisfied?
> 
> In any case, the fact that the Clark/Wroclawski scheme entails setting
> the drop preference at the ISP ingress router does not fix the incentive
> problem.  It encourages opportunistic origination of traffic from a
> customer site in excess of the contracted profile and in excess of the
> current capacity of the used paths in the hopes of "getting lucky".  That
> traffic is the result of the aggregate behavior of applications (or their
> transport protocols) within the customer site.
> 
> > other flow since it doesn't deny it access to the link.
> 
> You are neglecting the impact of undeliverable DP traffic on deliverable
> DP traffic.
> 
> Here's a trivial example.  In the following diagram, S1 and S2 are sources
> of traffic sending to receivers R1 and R2, respectively.  A through F are
> routers, and the numbers in angle brackets are the capacities of the
> links in Kbps.
> 
>        S1 ---<300>--- A                    E ---<300>--- R2
>                        \                  /
>                         \                /
>                          C ---<300>--- D
>                         /                \
>                        /                  \
>        S2 ---<300>--- B                    F ----<50>--- R1
> 
> Assume that each of the two sources is sending a 50 Kbps voice stream
> and a 200 Kbps video stream to its corresponding receiver, as part of a
> teleconferencing application.  And assume that that's the only traffic in
> this simple network.
> 
> Further assume that both S1 and S2 are marking (by use of a 1-bit or multi-
> bit drop-preference field) all their video packets as "less important"
> than their voice packets, so that if congestion is encountered, the video
> packets will be discarded before the audio packets, to avoid audio
> degradation if at all possible.
> 
> Assuming the less important packets are dropped by the routers in favor of
> more important packets, and that packets of the same importance are dropped
> with equal probability, C will discard half of S1's video packets and half
> of S2's video packets, and F will discard the rest of S1's video packets.
> R1 will receive only S1's voice packets.  R2 will receive S2's voice packets
> plus half of S2's video packets.  Thus, S1, by sending video packets that
> cannot be delivered to R1, has denied half of S2's video packets access to
> the C-D link.  (Further, if R2 is unable to produce an acceptible video
> image from only half of the video packets, the bandwidth consumed by
> *those* packets is also wasted, which could, in turn, deny bandwidth to
> other traffic flows in a more general example.)  If S1 were instead
> to refrain from sending its undeliverable video packets, R2 could receive
> the complete video stream from S2.
> 
> I trust that you can see how this bandwidth-denial behavior generalizes
> to richer topologies, more numerous and diverse traffic flows, multicast
> as well as unicast flows, etc.  I don't think this phenomenon goes away
> when it's the ISP-ingress routers setting the drop preference, rather
> than the applications.
> 
> > anyways, with or without DP,
> 
> Keeping DP out of the system is not sufficient -- you also need some sort
> of fairness mechanism (across all traffic flows or within each of some
> number of classes of traffic), such as a statistical approximation of
> Fair Queueing, or RED-with-penalty-box.  With such a mechanism in place
> (at least at the congestion points), then the absence of DP means that
> a source (or a customer site or whatever) sending undeliverable "less
> important" packets increases the probability that its own "more important"
> packets will be dropped, since they compete equally for queue space.  Thus
> there is an incentive to send only as many packets as can reach their
> destinations, and to make sure that those are the most important packets.
> 
> > and how does DP implemented as described above worsen this?
> 
> If DP is supported, a source's more important packets are not put at risk
> by sending any number of DP-marked, less important packets, so there is
> no disincentive to filling the network with DP-marked traffic.
> 
> Non-adaptive users can always decide not to stop using an adaptive
> application when it is failing to deliver the desired quality of service
> -- that way, everyone gets to choose their own "busy signal."  On the
> other hand, if we end up with non-adaptive applications, adaptive users
> will be denied the chance to exploit their adaptibility.
> 
> I have no problem with letting some users pay more to reduce the
> probability of having to adapt (e.g., by buying into a higher-priority
> traffic class), but it would be foolish to assume that you could always
> buy your way out of the need to adapt.  How much would it cost to reduce
> the round-trip-time between the earth and the moon to 20 msec?
> 
> Steve
>

---

From: Philippe OECHSLIN <[email-masked]>
Date: Thu, 16 Oct 1997 14:46:39 +0100

Alessio,

[email-masked] said:
>  So, good application designer will design the application so that in 
> such a situation it sends a bit to the sender saying "Please, don't 
> send Video, It's useless 

If you rely on good applications not to send data which would be dropped in 
the network you don't need different drop priorities in the first place.

> Now and then S2 will attempt to increase the DP to probe for 
> bandwidth (and lower ISP rates)

Here you use the DP bit to signal that you would like to benefit from a lower 
tarif while the network is not congestioned. You can do that with any other 
bits that express your quality of service, it doesn't have to be DP.

Am I missing something?

  Philippe

-- 
Philippe Oechslin                                mailto:[email-masked]
Department of Computer Science                    Phone:      +44 171 380 72 96
University College of London                        fax:      +44 171 387 13 97
Gower Street, London WC1E 6BT          http://www.cs.ucl.ac.uk/staff/p.oechslin

---

From: Wu-chang Feng <[email-masked]>
Date: Thu, 16 Oct 1997 10:04:51 -0400

> you also need some sort of fairness mechanism such
> as a statistical approximation of Fair Queueing, or RED-with-penalty-box.

One of our approaches for dealing with this is to have the marking integrated
with the source and to have the source employ TCP congestion contol in its
sending of both the excess/unmarked packets and the marked packets.  In the
previous audio/video example, S1 would continually see its unmarked packets
being dropped and would back off its unmarked packet sending rate accordingly,
thus allowing S2 to send both its audio and video to R2.  If congestion were
severe enough for the marked packets to be dropped, S1 would then back off its
marked packet sending rate as well.  Without such adaptation for both the
marked and unmarked packets, it is up to the network (through the use of
dropping at the ingress, Fair Queueing, and/or RED with penalty box) to deal
with non-adaptive flows.

Wu

http://www.eecs.umich.edu/~wuchang/pmg/

---

From: Juha Heinanen <[email-masked]>
Date: Thu, 16 Oct 1997 18:56:57 +0300

Here you use the DP bit to signal that you would like to benefit from
   a lower tarif while the network is not congestioned. You can do that
   with any other bits that express your quality of service, it doesn't
   have to be DP.

   Am I missing something?

so what would that field be?  the idea is that you have a queue per tos
and different thresholds to each queue based on dp.

-- juha

---

From: Paul Ferguson <[email-masked]>
Date: Thu, 16 Oct 1997 12:03:50 -0400

Insofar as using a mechanism to deal with no-adaptive flows,
I'm particularly fond of FRED, or Fair Random Early Drop, 
which was presented last month in a paper at the Cannes
ACM/Sigcomm conference.

 http://www.acm.org/sigcomm/sigcomm97/papers/p078.html

- paul

[snip]

Dynamics of Random Early Detection
Dong Lin and Robert Morris (Harvard University)

In this paper, we demonstrate the effectiveness of Random Early
Detection (RED) on three different traffic types: greedy, bursty
and adaptive. We point out that RED contributes to unfair
bandwidth sharing when a mixture of the three traffic types
exist at the shared gateway. This unfairness is caused by
the fact that RED proportionally drops packets from the competing
connections according to their bandwidth usages. We propose Fair
Random Early Drop (FRED), a modified version of RED. FRED detects
incipient congestion by monitoring the average queue length and
decides whether to drop a packet when the running average exceeds
a threshold. While connections in RED experience the same packet
loss rate, FRED makes different dropping decisions over connections
with different bandwidth usages by use of per-active-connection
accounting. We show that FRED provides better protections for
bursty connections. In addition, FRED is able to isolate
ill-behaved greedy traffic more effectively. These improvements
are demonstrated by simulations of TCP and UDP traffic. FRED
does not make any assumptions on the queueing architecture.
The cost of FRED's per-active-connection accounting is only
proportional to the total buffer size and is independent of
the number of connections.

[snip]

---

From: Juha Heinanen <[email-masked]>
Date: Thu, 16 Oct 1997 20:16:19 +0300

fred gave a good summary of our off-line discussions.  i have one
example to clarify, why i'm proposing different bits for drop and delay
precedence:

a network manager of a customer estimates that normally he has, lets
say, at most 20 simultaneous 8 kbps voice over ip calls from his office.
based on that estimate, he orders from his isp a low delay profile of
160 kbps.  in addition he has subscribed to another, normal delay
profile.

now it may occasionally (= rarely) happen that there is more than 20
simultaneous voice over ip calls.  in that kind of situation he is
willing to take the risk that some of his voice over ip packets may get
dropped by the isp network rather that subscribing to a more expensive
low delay profile.  also, in order to secure his job, he configures the
access router in such a manner that if the number of simultaneous calls
exceeds 20, then voice over ip packets from less important people will
get their dp increased.

what i tried to say with the above example is that i need SIMULTANEOUSLY
both dp and delay indication in the packet header.

-- juha

---

From: Juha Heinanen <[email-masked]>
Date: Thu, 16 Oct 1997 21:16:13 +0300

Whiile connections in RED experience the same packet
   loss rate, FRED makes different dropping decisions over connections
   with different bandwidth usages by use of per-active-connection
   accounting. 

i wonder how the connections are identified when people are encrypting
their ip packet payloads before sending the packets to the isp, i.e., is
per connection anything practical in the current world of secure
intranets?

otherwise the idea described in the paper seems to be quite simular to
what we have proposed a couple of years ago for implementing per
connecting fairness for atm
(ftp://lohi.dat.tele.fi/atm/articles/heinanen-fair-buffer.ps).

-- juha

---

From: Fred Baker <[email-masked]>
Date: Thu, 16 Oct 1997 11:45:56 -0700

>say, at most 20 simultaneous 8 kbps voice over ip calls from his office.

First comment - I have yet to see a VoIP stream that was actually 8 KBPS. I
probably have seen 8 KBPS of voice go by, but inside RTP, UDP, IP, and
something lik-layerish, it becomes more like 40 KBPS. 20 of them is 800
KBPS.

>both dp and delay indication in the packet header.

OK, I would suggest that this is that what you are asking for in the case
is not a certain drop preference and a certain delay preference. They all
have the same delay preference - whatever delay they encounter, they want
it to be consistent. What's different is the drop preference - you take the
janitor's phone call and make it the thing to drop if anything is going to
get dropped, and by the way, if there's many drops, you'd like to drop the
whole call.

However, I'll argue again that the sender in each case has no idea what
algorithms are being implemented on the interfaces en route. Some routers
or switches will manage congestion by drops, and some will manage it by
delay. Hence, I claim that in your example, the matter is better served by
taking the three precedence bits as already defined, and on the access
T-1/E-1 link that will be managed using queuing (higher precedence implies
less imposed delay), and on the higher speed links in the ISP network it
will be treated as drop preference (higher precedence implies lower
probability of loss). You differentiate between the boss and the janitor by
(at the user end) taking one bit of precedence and setting it on the boss's
call but not on the janitor's call. You use the other two (more
significant) bits of precedence and encode them as

	11 - network control (routing, etc)
	10 - reserved flow (RSVP or whatever)
	01 - standard contract, within bounds
	00 - reserved flow or standard contract, not within relevant bound

I submit that your example helps make my point. Treating the existing
precedence bits, with the single bit of user priority, in this way lets you
gracefully deal with the situation proposed.

The one place that seems to me to need some thought is - what bit is the
user's precedence bit? most significant or least? I tend to say "least",
for policy reasons, but in this case I'd be more prone to say "most". Or to
say that the user precedence should be set by the reservation algorithm,
and beccomes a reserved flow.

---

From: Steve Deering <[email-masked]>
Date: Thu, 16 Oct 1997 12:24:09 -0700

At 4:08 AM -0700 10/16/97, Alessio Casati wrote:
> R1 won't receive any video. So, good application designer will design the
> application so that in such a situation it sends a bit to the sender saying
> "Please, don't send Video, It's useless (and is going to penalize us)"

Yes, that's the good thing that happens when the routers treat all the
packets (voice and video, in this example) the same, i.e., no drop preference.

> Both of them will be happy even in the unlucky setting you depict.

But R2 is less happy than it could be, given the capacity of the network.
(There's no way to make R1 happier, but if R1 would refrain from sending
its undeliverable video packets, R2 could become happier.)  Half of the
capacity of the C-D link is being wasted, when it could have been used to
increase customer satisfaction.

I want to put to rest the widespread notion (that I once shared) that
sending DP-marked packets that get discarded at some congestion point
have zero cost.  The reason people want to allow non-essential or out-of-
profile packets to pass through the network, rather than being suppressed
at the source or discarded by the profile policer, is that those packets
are assumed to have *some* value if they make it to their destinations
(e.g., they improve the user experience in a teleconference, or allow a
file transfer to finish sooner, or whatever).  It is that value that is
squandered if applications fail to suppress any non-essential or out-of-
profile traffic that is *not* reaching its destinations.

> 3)(S1,R1) don't want video and quit => Good news for (S2,R2) which begin
> receiving full video stream.
>
> 4)(S2,R2) don't want video => nobody gets happier, but is likely (S1,R1)
> will end up with dropping their video flow and (S2,R2) will have more
> chances to find the deserved bandwidth on probing for it.

Sure, but in those two cases, you just changed the premise of my example,
which was that both R2 and R1 would like to receive the video if they can.

> How can the disincentive structure be implemented? Well, it would make
> sense to detect people using applications looking more aggressive in the
> bandwidth probe/back off mechanism just outlined (RED drop statistic would
> help), so that there would be no advantage resulting from too frequent
> attempts to send out of profile packets (with ISP charging the whole
> traffic it accepts).

I don't entirely understand that paragraph.  If you are saying that an
adequate disincentive could be provided through charging extra for "too
many" discarded packets, yes, that obviously has potential.  However, some
of the schemes under discussion, such as Clark's profile scheme, have as a
major goal avoiding the need for complicated and expensive measurement and
billing infrastructure in the interior of the net (where the discarding
may happen).

> So, Steve, why should DP bit be dropped, in your opinion?

I tried to explain that in my last message.  If DP is supported, an
application acting to maximize its own benefit (i.e., being greedy), has
an incentive to continuously send DP-marked packets along a path where they
will never reach their destination.  There is no penalty to the application
for doing so, since the routers at the dropping points ensure that its DP
traffic is not threatened by its own (or anyone elses) non-DP traffic.
And there is a benefit to the application for doing so: if the congestion
disappears (e.g., the delivery path changes or some competing non-DP traffic
stops), then the application's DP traffic immediately starts being delivered
to the receiver, without all the complication and delay of an end-to-end
adaptive probing mechanism.  Designing adaptive congestion-control algorithms
is hard (we're still trying to understand and fix problems in TCP!), and if
application designers can get optimal behavior without doing that, you can
bet they will not make the effort.  If, instead, the DP mechanism is kept
out of the network (and if other mechanisms are provided, such as SFQ or
RED), the incentives can be made to work the right way, in that an
application acting in its own best interest also acts in the best interest
of the network (i.e., increasing the customer satifaction obtainable from a
given set of resources).

Steve

---

From: Fred Baker <[email-masked]>
Date: Thu, 16 Oct 1997 13:28:09 -0700

>per connection anything practical in the current world of secure

I'll suggest they take a page from a recent RFC - hash the IP Addresses, IP
protocol, and the SPI.

Beyond that, you can't tell, and since RED couldn't tell in the first place
(I'd rather be FRED than RED - ohh, wrong generation for that comment :^) I
submit you've done the best you can.

---

From: Juha Heinanen <[email-masked]>
Date: Fri, 17 Oct 1997 10:01:57 +0300

it to be consistent. 

yes, and that is indicated by all packets having the d bit set to low.

   What's different is the drop preference - you take the
   janitor's phone call and make it the thing to drop if anything is going to
   get dropped, and by the way, if there's many drops, you'd like to drop the
   whole call.

yes.

   delay. 

here we certainly disagree, since if the packet is asking for low delay,
but has high dp, then the semantics of these bits don't allow managing
of congestion in the low delay queue by increasing the delay.  that
would directly contradict the user's request for low delay/high dp.
also, the network should not change the order of packets what have the
same path and the same tos.

   Hence, I claim that in your example, the matter is better served by
   probability of loss). 

this is what you have insisted all the long and i start to feel that you
do it because your implementation can't support thresholds in more than
one queueu.  even if the trunks are high speed (which also means big
buffer space if the design is balanced), it doesn't remove the
requirement of having separate queues for packets asking different
levels of delay.  numerous simulations have shown that the sizes of low
delay queues need to be kept quite small.  it is not possible to use
only one (big) queue and still guarantee low delay.

so if an isp is accepting more low delay traffic to its network that it
can guarantee low delay for (without explicit reservations about 40 % of
trunk capacity), it must have a means to tell switch packets to start
droping when the low delay queues grow too high.  this is why both delay
and dp bits are needed and there is no magic around it.

-- juha

---

From: "Alessio Casati" <[email-masked]>
Date: Fri, 17 Oct 1997 14:21:54 +0100

> packets (voice and video, in this example) the same, i.e., no drop preference.

Yes, but if you have both audio and video with the same DP,  in this case both 
would get some packets dropped in the first place. DP helps you in getting the 
most valuable packets through in times of congestion.

> increase customer satisfaction.

Yes, good application designer will make R2 act as you point out here. I didn't
write it, I'm sorry about that. The penalty mechanism should convince people
to use good applications. You need the DP to build the penalty mechanism

> profile traffic that is *not* reaching its destinations.

That's why the penalty mechanism should force people to send few out of profile
packets, that are those for which the network hasn't (or may not have)
engineered capacity. When the network operator discards non-DP packets in times
of congestion, then something is going wrong with the network engineering.
And users can complain about that (depending on the loss rate and the profile they
subscribed)

> which was that both R2 and R1 would like to receive the video if they can.

Yes, it's an exhaustive aside from your example, sorry for that. :-)
 
> billing infrastructure in the interior of the net (where the discarding

If you want to prevent unfair people from sending too many out of
profile packets, then you must try to penalize them by dropping their out of profile packets
first, for instance. If you give greedy users the same fair share as the
well-behaving ones, then  no disincentive is provided by the net. How to penalize
them is a matter of choice (mostly related to costs of implementation).

> will never reach their destination. 

It's just the opposite of what you are saying now: If you can identify out of profile
packets by DP, then you can enforce users to quit their misbehaviour.

> There is no penalty to the application

Considering the typos here, you are assuming something about a yet to be defined penalty 
mechanism.

> adaptive probing mechanism.

The penalty might prevent right this.

> Designing adaptive congestion-control algorithms

How do you identify out of profile packets inside the net? What about capacity planning?

Is every user going to be fair? I don't think so. A disincentive mechanism
base on out of profile packets identification is needed. 

Bye 

Alessio Casati

---

From: Fred Baker <[email-masked]>
Date: Fri, 17 Oct 1997 10:53:59 -0700

At 10:01 AM +0300 10/17/97, Juha Heinanen wrote:
>i start to feel that you
>one queue

It's just software, if we want to we can do as many queues as we need. I
have been trying to discuss semantics, and the fact that the systems using
delay priority may not be dropping stuff intentionally at all, or only in
extreme cases.

What I have been saying all along is that

>   or switches will manage congestion by drops, and some will manage it by

and that trying solve all problems with one set of semantics (dp) is akin
to saying "I have a hammer, everything looks like a nail."

---

From: David Black <[email-masked]>
Date: Fri, 17 Oct 1997 16:04:29 -0400

Two points to add to the conversation on the tos octet:

(1) Delay vs. Jitter

I think the advocates of multiple priority levels (where each priority level is
reflected by a different queue in the router/switch) should be using jitter in
their arguments instead of delay.  The multimedia apps used as the motivation
for multiple queues are not particularly sensitive to reasonable delays, but
are quite sensitive to jitter (dynamic variations in delay).

Consider audio -- the fact that controllers on the ground can talk to
astronauts on the moon indicates that even an interactive audio application can
tolerate significant delays.  The big problem is jitter, because such dynamic
variation in delays is handled by buffering, and the nature of the application
turns worst case network jitter into common case end to end delay (e.g., a
packet arriving in the best case time must wait through a full buffer so that
the application can draw down the buffer during the interim if the next packet
gets hit with the full jitter and arrives in the worst case time).  Here are a
couple of (contrived) examples:

[A] The minimum network delay is 0.5sec with 0.1 sec of jitter.  The
application need only buffer 0.1 sec of audio data at the receiver to ensure
continuous audio without glitches (in practice it probably buffers a bit
more), and the end to end delay is about 0.6sec.

[B] The minimum network delay is 0.3sec with 0.5sec of jitter.  The application
must buffer a full 0.5sec of audio data at the receiver to ensure continuous
audio, and the end to end delay is about 0.8sec.

Note that for evenly distributed jitter the average case delay is the same in
both cases, but the application works better in case [A] (better end to end
performance with less memory usage).

The point of all this is that using a higher priority queue for multimedia
traffic has positive effects on *both* delay and jitter, AND of the two, the
reduction in jitter is much more important than the reduction in delay.  The
nature of the traffic allowed into a queue (and queues higher priority than it)
dramatically affects jitter, but there's a big win to just pullin the
multimedia traffic out of the best effort pool. Talking about jitter instead of
delay also obviates Steve Deering's "can't talk to the moon" argument against
multiple queues.

(2) Broken Profiles

Much of the discussion of drop preference has focussed on traffic profiles with
the assumption that all "in profile" traffic can be delivered in an essentially
drop-free fashion.  What do you do when this assumption fails? I remind folks
that backhoes and bombs lay waste to the best network capacity engineering and
provisioning plans by taking perfectly good network facilities out of service.

The single bit profile schemes can't cope with this situation -- all the marked
drop preference traffic gets dropped, and after that we're back to the previous
situation before any of these schemes were invented.  There are real customers
who will pay for resilience to backhoes and bombs.  For example, most major
corporations have backup plans for a natural disaster striking a major computer
facility, usually involving otherwise unused computing capacity elsewhere for
which purchase and maintenance $$$s still have to be spent, and the people in
charge of making sure these will work then needed are examples of Steve Blake's
user who "will pay more so that some other guy has to adapt.  In contrast,
SIMA's use of multiple levels of drop preference allows it do something about
this as long as the network isn't reduced to the point where some of the `least
preferred for drop' traffic has to be dropped.  I'm not sure that SIMA is the
best solution for these sort of situations, but it does provide important
leverage in a way that the single bit schemes fail to do so.

--David

============================================================================
David L. Black            THE OPEN GROUP     Voice: +1 (617) 621-7347
The Open Group                                 Fax: +1 (617) 621-8696
Eleven Cambridge Center      RESEARCH       E-Mail: [email-masked]
Cambridge, MA  02142        INSTITUTE         http://www.opengroup.org/~dlb/
============================================================================

---

From: Steve Deering <[email-masked]>
Date: Fri, 17 Oct 1997 14:39:18 -0700

> Talking about jitter instead of delay also obviates Steve Deering's
> "can't talk to the moon" argument against multiple queues.

David,

My "talking to the moon" example was not an argument against multiple
queues, it was an argument against building a network that offers per-
call QoS guarantees.  It's my fear that the programmer who implements
Microsoft Phone (or some such application that becomes a widespread,
defacto standard) decides that interactive human voice conversations
require a delay less than x, jitter less than y, and bandwidth of at
least z, and whenever that application is unable to obtain such a
commitment from the network, it just tells the user: "sorry, network
too busy, try again later".  After all, that's the type of application
for which all this guaranteed QoS stuff is intended, right?

But then years after Microsoft Phone has driven all of its competitors
out of the market (because it offers such marvelous quality of service!),
grandpa tries to use it to call his granddaughter daughter on the moon, or
his son in an earthquake zone where most of the communication links have
been severed, and all he gets is "sorry, network too busy, try again later".
If, instead, the network never made any promises, applications would
naturally evolve to be highly adaptive, lots of effort would be put into
sophisticated compression algorithms to make the best use of whatever
bandwidth is available, and we'd end up with more efficient and more
robust applications (whose quality would usually be just as good as the
guaranteed-QoS version, but which could also deliver more value than just
a busy signal under adverse conditions).  It's another one of those
incentive arguments.

Steve

---

From: David Black <[email-masked]>
Date: Fri, 17 Oct 1997 18:35:25 -0400

> been severed, and all he gets is "sorry, network too busy, try again later".

That is in essence an argument against Integrated Services as represented by
the IntServ and RSVP documents, in which the application is expected to
negotiate with the network for end to end properties.  Differentiated
Services represents a whole variety of approaches, some of which do not
involve the application in negotiating the service parameters.  

> a busy signal under adverse conditions).  It's another one of those

I think you've oversimplified the argument -- it's probably sufficient for the
promises not to be made directly to the application.  As long as the
application is not involved in the service negotiation, and/or has to exist in
an environment in which there is no negotiation possible (e.g., I have bought
no enhanced services from my ISP, hence the answer to every QoS negotiation
request is "NO"), the developer must expect it to run in the case where there
has been no negotiation, and I think you get the desired incentives.
Considering that the target for differentiated services is ISPs who want to
sell enhanced services to corporate network managers (notice that neither party
is a serious application developer), I think there's a good chance of things
working out this way.

It is the case that for most interactive multimedia applications, there really
are limits beyond which there's just no point (e.g. at 30sec to 1minute latency
or jitter, a phone call doesn't work very well).  These limits vary by
situation and individual user, and hence a good developer will not hard code
such limits, but instead make them user-adjustable parameters when developing
for hosts with available resources.  This also provides some incentive towards
the desired compression and adaptivity, because you can never tell how poor
quality some users might be prepared to put up with because they can still
derive useful value.  OTOH, there are other environments that may impose severe
design constraints -- the explanation of jitter should make it clear that
tolerance of larger amounts of jitter translates directly into the need for
more buffering space, and hence it's quite reasonable for the designer of a
handheld wireless Internet Phone to place some rather stringent limits on the
amount of jitter that the device will tolerate (because there are much more
important things to use the memory for, and more memory translates into more
power consumption).

--David

---

From: Steve Deering <[email-masked]>
Date: Fri, 17 Oct 1997 15:57:22 -0700

At 3:35 PM -0700 10/17/97, David Black wrote:
> negotiate with the network for end to end properties.

Yes, that's what I was referring to when I said "per-call QoS guarantees",
and it's that context to which my moon scenario pertains.

> Differentiated Services represents a whole variety of approaches, some
> of which do not involve the application in negotiating the service
> parameters.

Understood.  I am in favor of differentiated services (but not the use
of drop preference as part of that service).

Sorry for mixing two flames in the same thread.

Steve
[off the air till Monday]

---

From: Juha Heinanen <[email-masked]>
Date: Sat, 18 Oct 1997 10:41:42 +0300

what i have been saying is that the above doesn't make any sense at all.
if the user is asking for a packet low delay/high dp and the packet gets
congested, then the network cannot manage the situation by increasing
the delay of the packet, because that would contradict what the user
has asked for.

it is you fred who hold the hammer in your hand by trying to claim that
it is possible to use one bit to indicate both delay and dp.

-- juha

---

From: Juha Heinanen <[email-masked]>
Date: Sat, 18 Oct 1997 11:06:23 +0300

i agree with steve here, but we are not living in the paradise, but
instead in a very competitive world where customers are willing to pay a
lot of money for these promises.

-- juha

---

From: Roch Guerin <[email-masked]>
Date: Sat, 18 Oct 97 13:05:12 -0400

Paul,
FRED is certainly one approach, but contrary to RED whose main
advantage is that you don't have to maintain per flow state, FRED
does.  Many have argued that per flow state goes against scalability
(I think this has been over-stated, but there is nevertheless some
truth in it), so FRED is substantially more expensive than RED.  You
can make the granularity coarser by doing things on a per class
rather than per flow, but then fairness across flows from the same
class is lost (no free lunch).  Furthermore, once you are willing to
bite the bullet of additional state, there are TONS of other buffer
management strategies that will do just as well if not better (Juha's
FBA is one example, and there are many others).

Roch

---

From: Roch Guerin <[email-masked]>
Date: Sat, 18 Oct 97 13:21:21 -0400

Fred,

>get dropped, and by the way, if there's many drops, you'd like to drop the

I think this is a rather narrow view of things.  You'll have the
janitor phone call and the janitor web traffic.  The two don't have
the SAME delay preference.  There are certain applications that need
to go first, but that does not mean you've got to drop others to
achieve that.  If you do that, you'll end-up with a network with
pretty low utilization, and I don't think you want that.  
So, I'll contend that you need BOTH delay priorities and drop
precedence.  

I don't buy the argument that "links are going to be so fast that we
don't need to worry about delay".  As I think you even mentioned
yourself in a previous note, we'll have a heterogeneous environment
with high and low speed links, so that we MUST have mechanisms to
support delay priorities.  And as buffer sizes have been regularly
increasing, I believe we'll need similar capabilities even on high
speed links.  This does not mean that we'll need the same granularity
on all links, i.e., per flow on low speed links and class-based on
high speed links, but support needs to be there.

Concerning drop precedence, I personally think one bit will suffice,
and certainly if we are squeezed for bits I'd use them to specify
delay priorities, but I don't have problems having more than one drop
precedence if there are bits left.  I just don't think you can provide
a  QUANTITATIVELY accurate service definition for multiple drop
precedences. 

Roch

---

From: Dong Lin <[email-masked]>
Date: Sat, 18 Oct 97 16:53:23 -0400

Roch,

> Many have argued that per flow state goes against scalability
> truth in it), so FRED is substantially more expensive than RED.

The number of flows a router can support is proportional to the number
of buffers it has. Therefore, none of drop-tail/RED/FRED is scalable
given a fixed buffer size. The maximum number of states FRED can have
is capped by the total buffer size as FRED has no states for flows not
consuming buffers. RED and FRED scale no worse than drop-tail because
they degrade to tail-dropping in the worst case when buffers are
exhausted.

One can show that simply adding buffers to drop-tail or RED routers
not only causes longer queueing delays but also worsens fairness. FRED
avoids these problems by providing no more than a constant number of
buffers (usually two to four) per flow under severe congestion
(Qave>maxth). As a result, one can add large buffers to FRED gateways
to accommodate large number of flows. But one cannot do the same to
drop-tail or RED.

Dong

---

From: Jon Crowcroft <[email-masked]>
Date: Sun, 19 Oct 1997 13:10:33 +0100

Avery important aspect of the differential services proposal
was the serparateion of User-Network, from network-Network qos as an
aid to deployment

essentially, a VERY simple (preferably pre-existing) inband per packet
signal allows one to choose profiles installed by some more expensive
mechanism (e.g. RSVPng, or other)

since these profiles can say just about anything, and can be keyed,
not JUST off the bit, but also off measurement based admission and
other classifications (and/or src/dst-prefix and/or port and/or
protocol) then the MOST important thing to preserve is this
deployability

multiple priority and delay levels are inappropriate - if you want
them, then use RSVP end to end.....in the places you can deploy that
(which will be _empowered_ b the simple scheme, since it will lead to
auuthenticaion and pricing, which are pre-requisite for any qos scheme
whatsoever, succeding  in the
open internet

so my vote is to keep things simple, at the expense of fancy high
utilisation of high percentage GS traffic....we can get that later,
but we do not want to "thro the baby out with the bath water".....

 jon

---

From: Andrew Campbell <[email-masked]>
Date: Sun, 19 Oct 1997 18:40:39 -0400

Hi Jon:

Is the recent move toward differential services because of
the IETF's (int-serv and RSVP WGs) failure to convince 
people/vendors to implement "circuit overlays" (i.e. RSVP 
flows with GS or CL) for NGI? Or is the another reason?

Andrew

--
Andrew T. Campbell  
http://comet.ctr.columbia.edu/~campbell
Wireless Media Systems Project 
http://comet.ctr.columbia.edu/wireless

---

From: Wu-chang Feng <[email-masked]>
Date: Sun, 19 Oct 1997 19:54:30 -0400

FRED is definitely more scalable than something which
keeps per-flow queuing information, but it also compromises
a certain degree of fairness in doing so.  The question
is how much fairness do we really need the network to enforce
and what costs in overhead are we willing to pay for it.

By not keeping per-flow state, FRED cannot eliminate unfairness.
For example....

1) FRED mechanisms (and for that matter, the mechanisms proposed by Fall
and Floyd) degrade when all sources or a large percentage of them are
non-adaptive.  For FRED, a large number of non-responsive flows will
drive up Qave causing more unfairness.  For RED w/ drop history,
it becomes harder to identify "malicious" flows from the packet history
(they'll all have an equal share of the drops).

2) FRED assumes a malicious flow will always have > 0 packets queued at
the bottleneck all the time.
   a) A malicious flow can stop sending for long enough to clear
        the bottleneck queue (thus clearing all of its strikes) and
        then start sending a large amount of data.  Several malicious
        flows alternating such behavior can kill well-behaved flows.
   b) If the queues at the bottleneck are kept small (which is desirable
        from a delay standpoint) and the number of flows going across
        the bottleneck greatly exceeds the buffering capacity, malicious
        flows can still grab more than their fair share of the bottleneck

        bandwidth without having more than 2 packets queued at the
        bottleneck.  (i.e. even with the two-packet buffer extension,
        FRED can be defeated)

FRED is certainly an improvement over traditional drop-tail/RED, but
it remains to be seen if it does enough.

Wu

---

From: Gisli Hjalmtysson <[email-masked]>
Date: Sun, 19 Oct 1997 20:59:01 -0400

Steve,

Knowing what you get may be of value.  For example said phone app., might 
behave differently based on different network conditions, e.g., enable 
duplex mode only if delay is within some bound, but otherwise restrict 
communication to simplex.  For real-time controls delay and jitter impact
the control granularity.

To achieve this reservation networks should rather reply with what they 
are willing to give, rather than simply replying "NO - cannot do it."  
Such "can do" message could in effect be suggesting a class which most 
closely matches the wants of the user.

There is also the issue of to what level applications need to adapt, i.e.,
i) not at all, ii) to different characteristics for different flows, 
iii) to slowly changing conditions iv) or continuously changing, highly
variable network conditions, v) more.  In many cases the choice of which 
of these is desirable is a trade-off between system processing (to amend 
poor quality connections) and network processing (to guarantee QOS and 
simplify end-systems).  Restricting solutions to push all of this processing
into the end-systems may greatly increase the complexity of the overall
solution. 

Yet another issue is what the common case is.  Although agreeable that
it would be nice to have the same system used for local phone calls as one
could use to call the moon, it is hardly of significance.  How many phone
calls do we expect to make to the moon before the next version of the MS
phone app is released?  All efficient systems, especially the Internet, make
trade-offs to favor the common case. If the Microsoft Phone app., is to 
compete with current telephony, it is only reasonable that it would designed 
optimally _only_ for common terrestrial network conditions, and quite OK if
it would not work for conversations to the moon. (How many wireless devices 
would work from the moon?)

Gisli Hjalmtysson

---

From: Steven L Blake <[email-masked]>
Date: Mon, 20 Oct 1997 15:50:17 EDT

Steve,

  Thanks for taking the time to explicate the problem scenario.  I apologize
in advance for the length of my reply.

> well-behaved TCP or similar?  How would they cause that assumption to be

I spoke too broadly.  Their intention (I understand) is to work with
existing applications.  I don't think that they intend their scheme to
enable (or motivate) new application behaviors.  How to enforce this is
an interesting research problem.  :)
 
> transport protocols) within the customer site.

I want to separate the analysis of the problem of drop-preference into
two cases: 1) where the network sets DP based on a service profile and
ignores/overwrites any application's settings, and 2) where the application
sets DP based on some utility function of the individual packets.  I want
to do this not because I dispute that there is a potential incentive problem
for both uses of DP, but because I think that whatever the incentive problems
are, they are different.  Also, I don't want to imply that the two approaches
(network or application setting of DP) are mutually exclusive, I just want
to simplify the analysis.

Now, the incentive problem you claimed for drop-preference was that an
application could opportunistically transmit DP packets in excess of the
network's carrying capacity without impacting the loss/thruput of its non-DP
packets, and that this condition would benefit the application at the expense
of other sources (since some DP packets may occassionally sneak through).
Without disputing this claim, I hope you see that this particular problem
doesn't exist in case 1 where the network determines the DP value of a
packet.  A source would have to carefully model the network service meter
to properly prioritize its packets and if the service meter was stochastic
then I don't think that this is practically possible.

There is another incentive problem for case 1 where the application sends
traffic in excess of its service profile and hopes for the best.  As long
as the application can't determine which packets are DP/non-DP then I don't
think that this incentive is any different that the current situation in
the Internet today; there are always tricks (such as sending duplicate
streams with ECC, or the Netscape hack) which allow an application to try
to use an inequitable share of the network's resources.  Adding DP (or
strict priority) doesn't make this problem any worse (in case 1) and I
hope to show that it makes it better.

> You are neglecting the impact of undeliverable DP traffic on deliverable

Yes I did (see below).

> when it's the ISP-ingress routers setting the drop preference, rather

Ok, in response I want to argue the following points:

a) You've shown that there can be unfairness between sources of DP
   traffic (due to the assumed application behavior).

b) You haven't disputed that the DP discard policy (or whatever
   differentiation policy is implemented between in-profile/high priority
   and out-of-profile/low priority packets) can be engineered so that the
   level of out-of-profile/low priority traffic doesn't noticably impact
   the service of the in-profile/high-priority packets.

   [In fairness, you may not have been interested in addressing this topic].

c) In the case of scenario 1, where only the network can set DP based on
   the source's service profile, the unfairness of DP service is actually
   a *feature* of the system rather than a bug, since it motivates the
   source to pay for the service it actually wants, thus further motivating
   service providers to scale up the network to satisfy the expressed demand.
   Mis-behaving applications will drive the network to an equilibrium where
   some non-trivial fraction of DP packets are routinely discarded (don't
   be surprised if service providers randomly nuke DP packets even when the
   network is uncongested :), and users are purchasing larger profiles to
   satisfy their actual service requirements.

d) In the case of case 2, where the application is allowed to set DP,
   I'm not convinced that the application incentive problem is as bad as
   you claim.  For example, S2 has the incentive to either reduce its video
   rate to determine the available DP capacity, or to mark some of the video
   packets with higher priority relative to the others, either by marking
   them non-DP, or by using different lower levels of a multi-level DP
   mechanism.  S1 has the same incentive.  In fact, in the example above,
   there is nothing preventing S2 from marking all of its video packets     
   non-DP, locking out S1's video packets (S1 won't do the same thing since
   this will result in S1 audio loss).  Assuming however that S2 doesn't do
   this, and that there is only one level of DP, and assuming that both
   sources determine that they have saturated the non-DP capacity of the
   network (due to service profiles, and/or the detection of non-DP loss),
   what will probably happen is that S1 and S2 will achieve an equilibrium
   where S1 persistently sends some level of video packets (marked DP)
   corresponding to its minimal tolerable video service, while S2 will
   reduce its coding rate so that it can decode the video signal that gets
   delivered.  Only if the minimal tolerable rate of video service is >= 100
   Kbps for both S1 and S2 will S2 be locked out.  This is unfair for S2, but
   if applications/users are as adaptive as you claim, then the minimal
   tolerable level for S1 will be low enough that the impact to S2 relative
   to its demand is small.

   How this generalizes I can't begin to imagine, but I think it is a fact
   of networking that there will always be a tier of service in the network
   which is potentially (persistently?) unfair.  Tragedy-of-the-commons
   situations can only be averted by legislation or privatization.  :)

e) Some differentiation mechanism (either a buffer management or a 
   scheduling mechanism, or a combination of both) needs to be implemented
   in each router if the network is going to differentiate service between
   different classes of packets.  Whatever incentive problems may exist
   causing applications to generate "excess" out-of-profile packets are
   independent of whether the routers implement drop-preference or strict
   priority queueing.  This is because any drop-preference discard policy
   which doesn't allow in-profile flows to ramp up to whatever share of a
   link they can achieve is broken anyway (excepting some administrative
   policy which allows say 20% out-of-profile minimal service).  So the only
   relevant difference between the two differentiation mechanisms is the 
   packet ordering behavior and the levels of delay priority that are
   provided.

> destinations, and to make sure that those are the most important packets.

This incentive to back-off only exists if the application can rank the
importance of its packets.  If they are all equally important, then the
user has the incentive to activate TCP TURBO mode.  :)  Link-fairness
mechanisms like FQ or FRED won't solve the undeliverable packet problem
either.

> no disincentive to filling the network with DP-marked traffic.

Except if the user can rank the value of the DP packets, in which case the
incentive to mis-behave is mitigated somewhat.

> Non-adaptive users can always decide to stop using an adaptive

The issue isn't whether or not applications should be written so that the
hosts don't burst into flames in the event of a service degradation.  The
issue is whether the user of the application can achieve his or her goals
under all service conditions, and whether that user should have an 
opportunity to purchase a reliable service.  But based on what you wrote
below, I don't imagine you disagree fundamentally with this. 

Regards,

---

From: Jon Crowcroft <[email-masked]>
Date: Tue, 21 Oct 1997 09:46:47 +0100

Andrew

its not a fgailure to convince - in my opinion, it is just that after
the memphis BOF, it was clear that right now we need soemthing simpler
and that the synergy between asking providers and subscribers and
router vendors what they could
i) make a profit from
ii) feel happy about paying for
iii) feel they could ship real soon
was in favour of this simplified approach....

unfortunately
every time we start talking about QoS, the arguments suddenly become
opacified - people keep proposing pathologically behaved soruces and
then trying to devise ever more complex queueing schemes to support
policing of them, when in reality,
any reasonably ISP will monitor sources and ban (fine, or over charge
these) - the incentives/profile idea is VERY powerful - it appies not
just on the timescales of RTT, or flow session life, but also to the
timeescales of microsoft implementing a new web access protocol and
trying to ship it.....

note also that there was careful discussion by the origianl
RSVP/int-serv community of the types of sources we envisaged

this new discussion seems confused between the simple +differentiated
services+ model ("better service") and full parameterized QoS.......

that way madness (sorry) lies....actually, that way is solved - but
requires the full metal jacket of rsvp and int-serv and issll etc
etc...

if we keep to the straight and _narrow_ of what is implementable,
chargeable for and payable for, but admits of service violations,
though not too often or undetecteably, then we may get somewhere...

by the way, circuit underlays may not be popular yet, but circuit
underlays sure are....and my take is that RSVP + IP with ISSL on FRo(or
atm if you must:-)
and other link layer reservation schems
 is a very nice stopgap for intranets right
now...

 jon

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Tue, 21 Oct 1997 20:11:05 -0400 (EDT)

> of buffers it has. Therefore, none of drop-tail/RED/FRED is scalable
It is exactly this observation that makes any per-flow scheme
so attractive and so easy to implement. I  belong to 
the camp that says that per-flow queueing is actualy simple.

For a router the definition of the flow is not the same as it is
in places like IP switches etc. The maximum number of flows
that a router sees is no more than the maximum number of packets
it can store. There are not millions of flows in a router
(unless the buffers are millions of packets and the delays are in
terms of seconds). In the worst case, each packet belongs 
in a different queue.

And a simple calculation: if average packets are 256 bytes and 
you need a buffer size of 200ms for an OC-3 link, then the 
maximum number of packets is simply 16K packets. It is definately
NOT dificult to handle 16K queues.

Dimitri

---

From: Jim Boyle <[email-masked]>
Date: Thu, 23 Oct 1997 03:09:19 -0700

>and what costs in overhead are we willing to pay for it.

I'm glad to see this as a question.  I'd state that life's not fair and
much of what I've seen described as "fair" realy isn't.  Is a T3 customer's
fair-share of a network the same as someone dialed in at 56k ?  Do we want
to create an incentive for creating multiple conversations to transfer the
same information in order to grab more fair share (ie open tcp connection
for each piece of a web page?).  I say no.  Now if an ISP could group
classes and specify the fair share of that class - that might be interesting.

Jim

---

From: "Alessio Casati" <[email-masked]>
Date: Thu, 23 Oct 1997 18:10:02 +0100

Dimitrios,

> NOT dificult to handle 16K queues.

Maybe I'm missing something, but if I got the picture then I think there's something
to be pointed out. It's correct that at some sampling instant in a router (but
let me also say in a switch) you have in the worst case each packet belonging to a
different flow, that is the number of flows with "representatives" in the box at most
equals the number of packets. But the actual number of flows which at some istant are "crossing"
the box might be higher, since you must not consider only the sampling time, but a
longer time window. You must allocate a number of queues(and resouces) sufficient to accommodate
packets belonging to flows with representatives in earlier and later times, in addition
to those neccessary for packets in the box at the sampling time.
I would like you to tell where I'm going wrong.

Bye

Alessio Casati

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Thu, 23 Oct 1997 14:28:30 -0400 (EDT)

> I would like you to tell where I'm going wrong.

In congestion instances you are mainly interested in distributing the
bandwidth/resources in a fair manner among the congested connections.
There is absolutely no requirement to remember what flows have done
earlier or what they will do later. This is a saficient action for 
preventing some users (either they are called short fast-reacting
connections or mis-behaving connections, or reverse ack streams) for
monopolizing the bandwidth. 

And if we follow the fair queueing model, the service offered to
a connection is a function of its weight and the other connections
that are BACKLOGGED in the system. This definition shows immediately
that connections that are not present, do NOT affect the bandwidth
distribution. As a result, there is no need to reserve resources for 
these connections.

Dimitri

---

From: Jon Crowcroft <[email-masked]>
Date: Thu, 23 Oct 1997 22:28:16 +0100

on "fairness" and "stateless queueing"

unnless you get an RSVP path/resv, or a router looks at
SYN/SYNACK, and FIN/FIN-ACK, you have to keep state by sampling
src/dst pairs present in packets in the queue - even if you do, you
don't know the RTT of the flows so you simply cannot tell what share a
src/dst flow _should_ have

the simplest and cutest assumption is to assume ALL flows always have
data ready to send, and all cooperaete or are bad....if they cooperate,
then RED is reasonable, FRED maybe better...if not, then RED is ok,
and FRED is better...actually, the systematic RTT unfairness present
in flow delay ignorant policing is actually a bonus (it gives an
incentive for clients to use nearby rather than distant servers - i.e.
gives leverage for caches....)

the point is that we want an _opportunity for fairness, not precise
fairness, as the bae level "best effort" service....

however, the definition of a differntial service (e.g. premium) is up
to the profile, and can be ANYTHING AT ALL - e.g. guaranteed, or
controlled load, or whatever - it is a contractual matter.....

which is why you only need 1 bit (and 2 queues...:-)
and lots of clever registration software........

cheers

 jon

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Thu, 23 Oct 1997 17:54:48 -0400 (EDT)

> src/dst flow _should_ have

may be not, but you can tell a lot from other flow characteristics.
and you can definately do a better job, the more information you
have.

> and FRED is better...actually, the systematic RTT unfairness present

Since when FRED and RED are the only two solutions under the sky ?

> to the profile, and can be ANYTHING AT ALL - e.g. guaranteed, or
     ^^^^^^^^^^^^> 

I don't know if I have missed this point, but I have a very basic
question about these profiles. As is my understanding the network
will be able to police traffic based on the profiles and (probably) charge
users. My question is : What happens with re-transminsions ?

What if a user is perfectly within its profile, but we, network 
designers, did a very poor job, and the user looses packets. Then
the user has to re-transmit and either exceed his perfectly nice
profile and loose more packets, or corporate and see throughput
much lower than the profile. In any case, the user looses, the ISP
wins (what a great business to be in ... :)

My point is: What is the plan for bringing together a closed-loop
congestion control algorithm (like the windows of TCP) with
a traditionally open-loop mechanism (leaky-bucket) ?

In addition to that: Are users going to be penalized for re-transmissions
that made them exceed their profiles ?  And if they are not, how
can we find which packets are due to re-transmissions and 
which are not ?

Are there any obvious solutions to my concerns ?

Thanks a lot,

Dimitris

---

From: [email-masked] (Hyogon Kim)
Date: Thu, 23 Oct 1997 20:27:43 -0400 (EDT)

If your original packets were "in-profile", their drop probabilities
in RIO variations are minimal if your network has been well engineered
(i.e. link capacity > sum of the profiles of the competing flows,
regardless whether this condition is practical or not).
So you don't have to worry about the loss of your "paid" packets.
With the infinite sources, the "in-profile" packet drop probabilities
were usually less than 0.1% in our simulations. What you should worry
about is, the _pattern_ of the "out-of-profile" packet losses. That's
what will hurt your throughput - it will even throttle your TCP so
that it cannot send even "in-profile" packets. I.e. - if the losses 
bunch up, then older TCP congestion control algorithms don't
cope with it as nicely as newer ones like newreno or sack. That's why
Clark briefly discusses TCP-friendly meter design in his draft.

Hyogon

-- 
------------------------------------------------------------------------------
Hyogon Kim ([email-masked])	       		       |        (201) 829-4728
Research Scientist				       |           MCC 1B-225B
Internet Architecture Research Laboratory	       |      445 South Street 
Bell Communications Research			       |  Morristown, NJ 07960
------------------------------------------------------------------------------

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Thu, 23 Oct 1997 21:07:44 -0400 (EDT)

> were usually less than 0.1% in our simulations. What you should worry

I would say that this too abstract of an approach to the 
problem. I haven't seen any theory around that will allow
me to provision the links of the network and keep the above
condition under all cases when traffic has VBR patterns. 
Unless all profiles are CBR and only CBR, provisioning 
can become a very difficult task. And even then,
how can somebody predict the exact load of the network at every 
point and at every second to guarantee the above condition. So,
as you correctly state, this condition is not very practical. 

I am NOT advocating that provisioning is not usefull or it can
not provide very good results. The opposite rather. I was 
simply probing whether anybody has any concrete knowledge 
of how to quatitantively do this provisioning 
(not qualitative arguments ) and what kind of profiles
will be more usefull for such an approach. (For example:
a simply leaky-bucket doesn't look very promising to me ...)

Cheers,

Dimitris

---

From: Fred Baker <[email-masked]>
Date: Thu, 23 Oct 1997 18:00:22 -0700

>negotiate with the network for end to end properties.

I disagree. What they negotiate is the token bucket description of the
traffic's rate, and (in the guaranteed service) one of the outputs is a set
of numbers that will permit the receiver to calcuate the worst case end to
end delay. The Guaranteed Spec talks a lot about end to end delay
measurements, but does not in fact enable anyone to specify maximum
acceptable end to end delay or jitter.

---

From: Zheng Wang <[email-masked]>
Date: Thu, 23 Oct 1997 23:21:50 -0400

>as you correctly state, this condition is not very practical. 

Even all profiles are CBR, there is the issue of traffic distribution.
Unless we can overprovision the network for the case-worst distribution,
it is highly unlikely that we can just do admission control at the edges
and have a loss-free network. 

Cheers
Zheng

---

From: Jon Crowcroft <[email-masked]>
Date: Fri, 24 Oct 1997 08:48:04 +0100

>and you can definately do a better job, the more information you

no - the more information you use, the more expensive manageing the
router infrastructure becomes - there is a tradfeoff 

that is the main difference between differnetial services and
(classic) integrated services - the tradeoff has been recognized at last....

 >Since when FRED and RED are the only two solutions under the sky ?

sure - there are loads of others - stochastic fair queueing, drop from
head fifo, CBQ, Worst Case Fair Weighted Fair Queueing etc etc
etc.....but the  key point is that the work is done by looking at
small numbers of bits in packets usually, and by aggregating
classification keysas you get ear the middle of the net so that the
more packets yo uhave to look at, the _less_ compelx the
lookup.....AND the less complex the queue insertion procedure...

please delete my remark on RED/FRED sa it was typed ratehr too late at
night to be coherent!

 >users. My question is : What happens with re-transminsions ?

hunh?

if a spec says we wil lget x packets per second through contyrolled
load, and the net is reasoanbly engineered, then the RTT wont vary
wildly, and TCP will rarely retransmit....

 >wins (what a great business to be in ... :)

then the user chooses a different ISP with a better net engineering
solution (roll on IPv6 so that chaning provider is easier though!)

 >a traditionally open-loop mechanism (leaky-bucket) ?

actually, this is one of the profiles that john wroclawski and dave
clark have _specifically  desgned for anyhow (but this is a KEY
difference between their scheme and Van's) - there is a TCP "friendly"
profile that is aware of the congestion control/retransmit/backoff
algorithms in a "good citizen" TCP....and gives a
queue/reward/punishment cycle that matches the TCP behaviour so as to
not cause retransmits.....

 >can we find which packets are due to re-transmissions and 

depends on the profile.....
 
 >Are there any obvious solutions to my concerns ?

no, its not obvious (for example clark and wroclawski  did NOT give
details at the munich ietf of the TCP freidnly scheme - for papers o
nTCP behaviour and clues as to how it might work, i guess the
"Macroscopic bnehaviour of TCP " paper in ACM CCR by Matt Mathis and
others in July might give some clues....

cheers

 jon

---

From: "Alessio Casati" <[email-masked]>
Date: Fri, 24 Oct 1997 10:22:25 +0100

> bandwidth/resources in a fair manner among the congested connections.

What you state here is just a choice among a set of possible actions a box could
take in times of congestion. You might randomly drop, selectively drop,
identify bad flows and filter them out (either locally or remotely, near the sources,
thus implementing a strong disincentive). And the most appropriate behaviour in times of 
congestion in my opinion is going to be in the drop actions, rather than in fair queueing,
Fair queueing cannot assure fairness when buffers are full (some well-behaved 
flows will be lock-out by greedy ones). You must augment fair queueing with selective discard
and remember the set of active flows in the box (and the fair share you are going to grant them).
This furtherly entangles your sheduling/Buffer management functionalities by creating
undesirable interdependencies between them.

> earlier or what they will do later. 

And this will end-up in a probability 1 well-behaved flows lock-out. The point is you must consider
far more flows than the ones you are optimistically considering now. Typically in a box located in 
a point of the network with high degree of multiplexing you have millions of flows. This is the 
reason why people realized that stateful per flow queueing is unscalable. Stateless per flow 
queueing is scalable, but useless. It's solving the problem by neglecting its existence.

> This is a saficient action for preventing some users (either they are called short fast-reacting

As I hope I could demonstrate, this is a sufficient condition to flows lock-out, that
straightly leads to monopolizing bandwidth.

> distribution.

So let our routers serve the flows which win the contention in accessing them
(typically they are misbehaving or congestion unresponsive ones, by the way).

> As a result, there is no need to reserve resources for 
> these connections.

I'm afraid Lixia, Bob and RSVP people are going to tell something about it ;-)

Bye

Alessio Casati

---

From: Jon Crowcroft <[email-masked]>
Date: Fri, 24 Oct 1997 10:16:32 +0100

>straightly leads to monopolizing bandwidth.

an assumption in the differential services is that we have some
hierarcy to our network - most commercial ISPs have restricted link
speeds on their access networks - tihs means that
i) the use cannot monoopolize the backbone
ii) there is a single ingress router point where we can choke them
anyhow....

once this is done, the remaining flow is multiplexible with high gain,
and can i nfgact result i nhigher utilisation in the backbone(s)

for sites with aggregated access (e.g. i nthe UK academic net, we have
100Mbps site LANs and 155Mbps MAN and WAN access) the problelm has to
be devolved back nearer sub-sites, or we need to do finer grain
policing in the access router....

 >I'm afraid Lixia, Bob and RSVP people are going to tell something about it ;-)
 
if someone can make RSVP and WFQ work for large number of per flow
state (setup and mainatenance) then thats fine - right now, i don't
see how to extend degermark;s work on the detaintaion based routign
table lookup size and performance to include the generalized port
specification (i can see how to extend it for source based or group
based looups for multricas,t but not for all 5 fields....), and i'm
not convinced that the per flow queue insertion operations can be done
fast enough for per flow WFQ for any large number of entries.....

or that we have to, since once we admit we have a hierarhcical
network, we only have to do it for smal numbers of flows at the
"edges"

 jon

---

From: Shivkumar Kalyanaraman <[email-masked]>
Date: Fri, 24 Oct 1997 05:54:03 -0400 (EDT)

> wins (what a great business to be in ... :)

Or even when the user exceeds its profile once and is penalized 
and remains idle for a while due to, say timeout. The ultimate 
throughput of this user might be small compared to what it negotiated
in the first place - especially if it is not long-lived.

Follow up question: have the premium services been defined with the 
possibility that TCP-like mechanisms should/could run end-to-end ? 

> a traditionally open-loop mechanism (leaky-bucket) ?

Counter question: do you expect premium services to use TCP ? 
How about multicast then ? 

> can we find which packets are due to re-transmissions and 

It seems to me that the network is doing too much if it is 
going to isolate retransmissions from normal transmissions.

> Are there any obvious solutions to my concerns ?

Shivkumar Kalyanaraman   
Assistant Professor, Dept of Electrical, Computer and Systems Engg,
Rensselaer Polytechnic Institute
110, 8th Street, Rm JEC 6042, Troy NY 12180-3590
Ph: 518 276 8979  Secy (6313)	 Fax: 518 276 2433
Email: [email-masked]

---

From: "Alessio Casati" <[email-masked]>
Date: Fri, 24 Oct 1997 12:05:57 +0100

> and have a loss-free network. 

David Clark, John Wroclawski in draft-clark-diff-svc-alloc-00.txt raised
the issues you are concerned about and gave some tentative approach to their solution
By the way,Dimitrios, you can find somenthing about TCP too there. 
As to whether the WG should give guidelines for network provisioning is 
questionable. What has to be taken care of is to devise a service model letting
ISPs have handles to perfom it in a not too cumbersome way. This is in my opinion
one of the issues to be put in the first rows of a todolist.

Bye

Alessio Casati

---

From: Roch Guerin <[email-masked]>
Date: Fri, 24 Oct 97 08:15:53 -0400

Fred,

>The Guaranteed Spec talks a lot about end to end delay

Do you mean that the spec does not let the SENDER specify a maximum
acceptable e2e delay?  Because the spec does allow you (the receiver)
to specify to the network the maximum e2e delay you want.  That's
basically what the RSpec rate implies, and btw you could also use the
slack term if you wanted to tell the network:  "I really want this
delay that corresponds to the rate I'm giving you, but I'm willing to
live with more if necessary -where how much more is given in the
slack".  I'll grant you that this goes a little bit further than the
initial intention for the slack and will also work better with delay
than rate-based schedulers, but it can nevertheless give you
additional flexibility in negotiating the service.

As far as jitter is concerned, the GS spec does not let you explicitly
specify a jitter bound, but it implicitly gives you one since you have
an upper bound on the QUEUEING delay which is the only real source of
jitter.  There are services, e.g., ATM CBR and rt-VBR, that let you
specify/determine a bound on jitter, but none that also tell you how
it is going to be actually computed (see the still ongoing debate in
the ATM Forum on the "right" way to do it!) and consistently supported
(implemented).  So, given that supporting bounds on BOTH the max and
min delays, which is what you need to control jitter, is not a simple
task, I think that the approach taken in GS is a reasonable first
step.  Plus, you can certainly tune your GS implementation to also
provide very good jitter performance (see our Sigcomm'96 paper ;-).

Roch

---

From: Wu-chang Feng <[email-masked]>
Date: Fri, 24 Oct 1997 08:43:06 -0400

> How about multicast then ?

Actually, one of our approaches is to treat the use of premium services using
TCP congestion control.  There are several
advantages of integrating the packet marking inside the end-host
TCP.

1) Source can detect if any service differentiation is being done and
    turn off marking if
     a) the bottleneck link does not support service differentiation
     b) something in the network is unmarking its packets
   This allows sources to get what they pay for.

2) Overloaded situations will cause end-hosts to simply revert to
    TCP using priority packets.  TCP is much better understood than
    all of the proposed schemes.

3) Source can do an optimal amount of marking in order to get the
    service it requires.  If the source needs 2Mbs and can get 1Mbs
    over a single best-effort TCP connection, it will only mark at a
    1Mbs rate to get its desired 2Mbs rate.  Any marking done within
    the network necessarily marks at a higher rate which can flood
    the ERED/RIO/etc. queues with marked packets causing it to act
    like a normal queue.

Wu

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Fri, 24 Oct 1997 09:36:10 -0400 (EDT)

> congestion in my opinion is going to be in the drop actions, rather than in fair queueing,

Absolutely agree ... you couldn't be more correct on this. The scheduling
mechanism simply selects who transmits, it is the drop mechanism that
under finite buffers will determine the bandwidth. 

> and remember the set of active flows in the box (and the fair share you are going to grant them).

Absolutely agree with that as well. 

> undesirable interdependencies between them.

I have to disagree here :( ... There are independencies but they 
are easily solvable. Push-out schemes can be very helpfull
on that.
> queueing is scalable, but useless. It's solving the problem by neglecting its existence.

I have to disagree with you once more. If you combine the proper
buffer management with stateless queueing you can improve things
much more than if you simply ignore any per-flow state. (if
temporary and local). A correct push-out mechanism can easily
identify mis-behaving flows, and keep the good ones in. Remember,
that all these mechanisms kick in when we have congestion. If 
congestion is there, because every flow has one packet, no 
matter what you use it is the same. If congestion is there,
because some flows take substantially more banwdith than
others, then it is easy to see which flows are creating this
problem.

> (typically they are misbehaving or congestion unresponsive ones, by the way).
Your first comment simply contradicts with this comment. As you
mentioned it is not per-flow queueing that prevents you from 
providing good service, but wrong buffer management. 

Cheers,

Dimitri

---

From: Dimitrios Stiliadis <[email-masked]>
Date: Fri, 24 Oct 1997 09:43:16 -0400 (EDT)

> the issues you are concerned about and gave some tentative approach to their solution

I have seen the draft, and I don't think I saw any "quantitative"
solution there.

> one of the issues to be put in the first rows of a todolist.

I agree. However, the WG should not define a service model that
nobody knows how to use. It won't be used anyway. Any service
model comming out of this group, must be easily understantable
and used (in a cook-book approach) by providers. The implementation
issues should be taken into account and the administrative
issues as well. Saying simply that provisioning will improve
the performance of the network is not good enough for me.
Saying that if you do it this you will improve the performance
by x% under Y load, then it is a solution !

Cheers,

Dimitrios

---

From: Zheng Wang <[email-masked]>
Date: Fri, 24 Oct 1997 10:35:18 -0400

> And the most appropriate behaviour in times of 
> flows will be lock-out by greedy ones).  
 
I think the fairness property of WFQ only holds when you have large/infinite
buffer or you have a FQ-style of buffer allocation.

We observe similar phenomenon where there are are a large amount of short-lived
TCP connections (http get) over a very congested link. Many TCP connections
never manage to get to the connected state because the SYN packets are lost.

If you cannot get on the shortlist, you will never be selected:-)

Cheers
Zheng

---

From: "Alessio Casati" <[email-masked]>
Date: Fri, 24 Oct 1997 16:43:26 +0100

Thanks for you reply, Dimitrios.
Some comments follow.

> are easily solvable. Push-out schemes can be very helpfull

First of all I'm happy you agree with me we need good Buffer Management.
If you make (a proper) Buffer Management independent from Scheduling, I contend things
are going no worse than with dependencies. So why should I follow you in your
(legitimate) choice?  I only remember you the WG has to define a router semantic in treating 
packets (either "in" or "out"). So we have only to comply with that. I hope your solution
is going to achieve better compliance! Good luck! (we both need it).
> others, then it is easy to see which flows are creating this

I agree with you: stateles queueing with proper buffer management is the winner.
Let's use two queues (in case of 1 bit Delay Priority), instead of one per flow.
And let's use RIO or something similar to manage the queues. And let's kill
bad guys :-).

> providing good service, but wrong buffer management. 
 
As a matter of fact I cannot detect contradictions in my message wrt what I was saying here.
Obviously the reason why I wrote this statement was related to yours

"This definition shows immediately that connections that are not present, do NOT affect the 
bandwidth distribution."

So if only bad guys enter the router are you happy to serve them? Yes, OK, now you tell me
there's push out in place. But I could not read it in your message. 

It was only my assumption you where not considering Buffer Management sufficiently. 
I apologize :-).

Have a good WE.

Bye

Alessio Casati

---

From: Philippe OECHSLIN <[email-masked]>
Date: Fri, 24 Oct 1997 16:13:08 +0100

[email-masked] said:
> Even all profiles are CBR, there is the issue of traffic 
> distribution. Unless we can overprovision the network for the 
> case-worst distribution, it is highly unlikely that we can just do 
> admission control at the edges and have a loss-free network.  

I would like to add to this:

Since we don't know the traffic distribution, there is no way we can offer 
hard guarantees. If we are not offering hard guarantees, then why should we 
police the users?

The information we get from inforcing profiles is not of much use since we
don't know where the users are sending or getting traffic to/from. We still 
have to rely on predictions to dimension the resources in the network.

Wouldn't it be simpler (and fairer) to let the user set the tos bits himself 
and let him send how much he wants, provided it is less than an absolute 
maximum (say 10Mb/s). Then we just charge by usage. 

Is there any fundamental advantage in using quotas as long as the traffic 
distribution is not known?

 Philippe

---

From: [email-masked] (Hyogon Kim)
Date: Fri, 24 Oct 1997 11:24:09 -0400 (EDT)

Dimitris,

I re-checked your previous mail and I frankly don't think it was about
provisioning :-), but anyhow since this monster came out of the box...(partly
due to my slip of the tongue)..

As an ISP, what you will probably do is _not_ over-provisining all links
for all kinds of traffic distribution. Over-provisioning all links
against the sum of the profiles is not a practical/profitable thing to do. 
What you will do, however, is to find "strategic" points where there is 
chronic congestion due to this particular ISP's traffic flow pattern(before 
the deployment of differentiation mechanisms). 
Then you deploy the differentiation mechanisms there with adequate 
provisioning which enables the mechanisms to function properly. 

And speaking of concrete theoretical analysis or quantititive approach, 
there are a couple of practical difficulties - one is the lack of good,
representative Internet traffic model (and "VBR" and "CBR" sound 
as abstract as anthing to me in that sense), and the lack of good 
theoretical analysis of RED (not even RIOs). I will be surprised to see 
any good theoretical contributions on provisioning for service-differentiated 
Internet before the above two are done.

Hyogon

---

From: Craig Partridge <[email-masked]>
Date: Fri, 24 Oct 97 08:30:40 -0700

Actually, one of the beauties of the token bucket + WFQ-style schemes
(of which Guaranteed is a version), is that the applications can compute
*without asking the network*, approximately what their guaranteed delay will
given a particular token bucket.

So you don't have to specify a maximum acceptable delay -- you know, given
the token bucket you're asking, what the result will be.  And if you don't
like that result, you know how to change your token bucket to get a better
one.  And the math is simple.

So this question of specifying a maximum end-to-end delay is a red herring --
you can do it now, without having to say anything (pretty neat).

Jitter is a different matter -- the philosophy was that jitter is easy for
the application to fix and a pain for the network.  So ask the ends to
be smart.

Craig

---

From: Zheng Wang <[email-masked]>
Date: Fri, 24 Oct 1997 13:38:10 -0400

> provisioning which enables the mechanisms to function properly. 
 
But the traffic patterns change from day to day. The Internet does not have
nice statistical properties that telephone networks have (or used to have).

Good provisioning and admission control will certainly reduce congestion
but I dont think they will eliminate congestion in the Internet. When
there is congestion, inevitably the customers who are willing to pay
more will get more. A service model has to take this aspect into consideration.

Cheers
Zheng

---

From: Juha Heinanen <[email-masked]>
Date: Sat, 25 Oct 1997 09:53:37 +0300

the traffic distribution can be learned by experience and congestion of
guaranteed trafic can be prevented by engineering the network so that
its amount on all links is low enough (a figure of 40 % has been often
used in simulations).  in order to help in that process, the network has
to be able to regulate inbound traffic using the profiles.

-- juha