Subject: Re: support for packet drop priority

From: "Yeh,WenHung" <[email-masked]>
Date: Thu, 22 Jan 1998 11:33:16 +0800

excerpt from Steve's mail
Date sent:        Wed, 15 Oct 1997 17:36:45 -0700
Subject:          Re: differential services tos octet

>-------
>
>
>
 >    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.

>--------  end of excerpt

>alessio

I think, if RSVP are run on the routers, such a condition
will not occur.
Because the routers will not allow such an resource
reservation. The
request from R1 will be rejected.

Yeh, Wen-Hung
e-mail : [email-masked]

---

From: Jean-Yves Le Boudec <[email-masked]>
Date: Fri, 30 Jan 1998 11:01:34 +0200

The problem mentioned in the example is not due to drop priorities, it is
due to S1 and S2 sending best effort data (video) without feedback control.
The problem exists independent of whether there exists higher priority
traffic or not.

The solution is known: sources sending best effort traffic must adapt to
the bottleneck link, or made to adapt if they don't cooperate.

JY

>> Thus, S1, by sending

---

From: "Alessio Casati" <[email-masked]>
Date: Fri, 30 Jan 1998 11:58:36 +0100

Jean-Yves,

> the bottleneck link, or made to adapt if they don't cooperate.
 
You are perfectly right. DP isn't indeed meant to solve bottleneck link sharing problems.
Nor is intended to per se rule out bad guys (you must add a penalty mechanism anyway). Nor anybody 
is religious on having it. You may do without it.
The real problem is whether we want to standardize (or allow) mechanisms making use of it (such as 
the RIO mechanism in assured service) and whether we want DP to be an end to end tool. In such a 
case, I would want to define syntax and interpretation, as Paul, Juha  Steven and Ed did in their 
proposals.
Some time ago Steve Deering asked to argument why a DP equipped diffserv model is at 
least as powerful as a non DP equipped one. The main reason, IMHO, is that if you turn it off, 
then you have a DP-less model. 
Basically, if a particular service is found out to be better run without DP, turn
DP off. If a service benefits of it (its operation in your network makes it economically
advantageous), you have DP bits in place to be used.

alessio

---

From: Steve Deering <[email-masked]>
Date: Fri, 30 Jan 1998 12:50:35 -0800

> the bottleneck link, or made to adapt if they don't cooperate.

So exactly what is the "known solution" for making best-effort sources adapt
to their share of the bottleneck resource, and when will it be ubiquitously
deployed in the Internet?

In the absence of some other mechanism to force or incent adaptation,
adding support for drop preference simply removes what little incentive
for adaptation exists now (that being: by sending undeliverable lower-
precedence packets, I put my higher-precendence packets at greater risk of
being dropped).

And once an alternative mechanism is in place to cause sources to discover
and adapt to the bottleneck resource, the possible benefits of a drop-
preference feature become very much second-order, since sources can just as
well suppress undeliverable lower-precedence packets at the source, rather
than wasting resources sending them to a router to be discarded.

Let's concentrate on solving the admittedly much harder, but far more
urgent and important, problem of how to make sure best-effort sources adapt
to the available resources, before leaping to install drop-preference
schemes which seem only to make things worse in the near term and are
likely of only marginal benefit in the long term.

Steve

---

From: Jean-Yves Le Boudec <[email-masked]>
Date: Fri, 30 Jan 1998 23:13:39 +0200

>deployed in the Internet?

The known solution is for example the Dec bit by Jain. This is assuming
sources cooperate. If they don't, it's harder, but to quote some friend,
put WFQ per aggregate flows on your bottleneck and shape your traffic
there.

I am not arguing that DE is good or bad, I personally don't have an opinion
on that issue.

>likely of only marginal benefit in the long term.

Again, I see those issues as orthogonal. Priorities have been supported on
all commercial routers for years now. The only thing we are discussing is
standardizing an existing state of affairs, or not.

JL

---

From: Steve Deering <[email-masked]>
Date: Fri, 30 Jan 1998 14:42:00 -0800

At 1:13 PM -0800 1/30/98, Jean-Yves Le Boudec wrote:
> sources cooperate. If they don't, it's harder, ...

The days when you could assume that all sources are cooperative are long past.

> but to quote some friend, put WFQ per aggregate flows on your bottleneck
> and shape your traffic there.

How does shaping of an aggregate cause the desired bahavior of each individual
source contributing to that aggregate?  How does it stop the wastage of
resources along the path preceding the bottleneck?

> Again, I see those issues as orthogonal.

I certainly understand a *desire* that they be orthogonal, because that
makes them a lot easier to think about.  I think my example shows that
the issues are not as orthogonal as we would like.  Features interact.

> Priorities have been supported on all commercial routers for years now.
> The only thing we are discussing is standardizing an existing state of
> affairs, or not.

There are all sorts of things going on in the Internet, many good and many
bad. What better time to stop and think about whether something is a good
idea or a bad idea than when it is proposed to be standardized?

Steve

---

From: [email-masked]
Date: Fri, 30 Jan 98 19:52:36 EST

>>>>> "Steve" == Steve Deering <[email-masked]> writes:

Steve> In the absence of some other mechanism to force or incent adaptation,
Steve> adding support for drop preference simply removes what little incentive
Steve> for adaptation exists now (that being: by sending undeliverable lower-
Steve> precedence packets, I put my higher-precendence packets at greater risk of
Steve> being dropped).

Is the concern here that if drop priorities are adopted then
applications will have little/no incentive to adapt? On the other
hand, (with DP) wouldn't those applications also have the option of
adapting more graciously when the less important packets (if they
exist) are the ones more likely to be dropped? Hence, an enhanced
service will in fact be delivered by the network.

Steve> And once an alternative mechanism is in place to cause sources to discover
Steve> and adapt to the bottleneck resource, the possible benefits of a drop-
Steve> preference feature become very much second-order, since sources can just as
Steve> well suppress undeliverable lower-precedence packets at the source, rather
Steve> than wasting resources sending them to a router to be discarded.

But that seems to be calling for the deployment of new applications
(which can/will adapt). The mechanisms to develop such applications are
outside the scope of this group.  And what about the applications that
exist today that do not adapt? It is rather unlikely they will go away
any time soon.

Enrique

---

From: Steve Deering <[email-masked]>
Date: Fri, 30 Jan 1998 18:42:01 -0800

At 4:52 PM -0800 1/30/98, [email-masked] wrote:
> applications will have little/no incentive to adapt?

Yes, and worse: I think it may well create a positive incentive for
applications to overdrive the network, e.g., by using layered encodings
with no congestion back-off.

> On the other hand, (with DP) wouldn't those applications also have the
> option of adapting more graciously when the less important packets (if
> they exist) are the ones more likely to be dropped? Hence, an enhanced

I fear that the harm done by the non-adaptive apps will far outweigh the
minor benefit of DP for adaptive apps.  And is DP the only way to achieve
the graceful degradation property you seek?  Perhaps ECN (explicit
congestion notification, see <http://ftp.ee.lbl.gov/floyd/ecn.html>)
would be just as effective in reducing drops of the most important packets,
by providing warning of impending congestion soon enough for the source to
decrease the rate of transmission of less important packets?  (Note
that neither approach will be 100% effective, so app designers will still
need to strive for graceful tolerance of occassional losses of the most
important packets.)

> exist today that do not adapt? It is rather unlikely they will go away

I am arguing for designing the network service in a way that provides
incentives for the apps and transport protocols to adapt, which is
certainly within the scope of this group.  Once the incentives are in
place, misbehaving apps will be discarded and replaced by well-behaved apps;
how soon that happens will depend on how strong the incentives are.
Deploying new or replacement applications is relatively easy and fast, when
the users are sufficiently motivated -- it's just a few clicks of the
browser.  It's  getting the network infrastructure upgraded that takes a
long time...

Steve

---

From: Zheng Wang <[email-masked]>
Date: Sat, 31 Jan 1998 21:22:30 -0500

Steve Deering wrote:
> place, misbehaving apps will be discarded and replaced by well-behaved

I believe that one way of achieving this is to provide traffic isolation
between users. Traffic isolation

1) removes the dependence on the cooperation between competing users
2) eliminates the incentive for behaving badly

Once the traffic isolation is in place, people will use adaptive apps
for their own benefits.  

Cheers
Zheng

---

From: Jonathan Stone <[email-masked]>
Date: Sat, 31 Jan 1998 20:17:36 -0800 (PST)

Zheng Wang <[email-masked]> writes:

>> incentives for the apps and transport protocols to adapt
[snipped]

>Once the traffic isolation is in place, people will use adaptive apps

But doesn't this beg the question of what counts as a `user' for
purposes of traffic isolation?  It's clearly well-defined in the
telephony world.  But any choice you make for a `user' of IP flows
address must either aggregage traffic from different connections into
a single `user', or alternatively, give users of timeshared machines
(or even multiple machines) the opportunity to game their way around
your `isolation'.

More exclusive definitions of `user' (in the limit, a single IP/TCP
flow) will allow more gaming, and less exclusive (entire machine,
entire subnet, a subscriber's site) can _reduce_ the disincentive for
bad behaviour, by punishing an class of users when any one member of
that class is ill-behaved. Viewed from within that class, you have
what amounts to a failure-of-the-commons.

Exactly what is a `user', and where is the `isolation' enforced?  

And what about inherently different-sized flows?  If we're talking
about different-sized flows with metered charging and WFQ throughout
the network for isolation, surely the customers are going to expect
what they're paying for, rather than adapting to what's available?

And if we're talking about one-size-fits-all isolation, isn't that an
equally good market incentive to create apps and protocols which
multiplex their traffic so's to look to the network like multiple `users'?

---

From: Shivkumar Kalyanaraman <[email-masked]>
Date: Sun, 1 Feb 1998 12:49:01 -0500 (EST)

> need to strive for graceful tolerance of occassional losses of the most

If we remove DP, how does an ISP (or provider) 
provide different levels of "assured" or "best effort" service ?
I am assuming you are implying a scenario where we do away
with standardizing things like the profiler, special router schemes like
RIO or the SIMA scheduler....

-Shivkumar

---

From: Shivkumar Kalyanaraman <[email-masked]>
Date: Sun, 1 Feb 1998 13:36:45 -0500 (EST)

> need to strive for graceful tolerance of occassional losses of the most

As an addendum to my previous note, I want to propose an intermediate
approach between no-DP and DP-without feedback.

We are experimenting with here with a scheme which enhances the
profiler + DP model with ECN-like feedback from the
routers (needs another bit or a bit combination). 

Initially the profiler is in the "MARK" state. Out-of-profile packets
are marked by the profile and not dropped. When the network detects
congestion, ECN in the ack is set (as described in the ECN draft, with
RIO instead of RED), the profiler moves to a "DROP" state.
The next out-of-profile packet is dropped, and the profiler moves back to
the "MARK" state. In the worst case, this would drop an out-of-profile
packet for every ack with an ECN bit set. 

This allows the application some elasticity to be able to
grab unused bandwidth (i.e. not all its out-of-profile packets are dropped
at the edge). At the same time, when the network is congested,
out-of-profile packets at dropped at the edge, saving network resources on
the way to the bottleneck. Other advantages: allows ECN to be deployed in
IPv4 itself, and doesn't add extra state except at the edge. Also this
scheme can be deployed with any DP scheme, not necessarily profile meter +
RIO.

Of course, other responses to the bit feedback are possible and one must
be careful not to cause performance problems when the application in fact
uses ECN-capable TCP. 

BTW, the 2-bit diff services proposal resets the DP bits set by the
applications -- does this mean that sources cannot prioritize traffic ?

-Shiv

---

From: Zheng Wang <[email-masked]>
Date: Sun, 01 Feb 1998 16:06:51 -0500

> (or even multiple machines) the opportunity to game their way around

A "user" is defined based on the customer-ISP relationship.
For example, Lucent pays AT&T for its Internet services. Then
Lucent is a "user" of AT&T. If Lucent's traffic is isolated from
AT&T's other customers, there is no incentive for Lucent's 
applications to "game" their way around. 

> what they're paying for, rather than adapting to what's available?

Within the Lucent's aggregated flow, adaptation will still be necessary
for individual flows to use the network bandwidth efficiently. Since
all flows are under the control of a single admin domain, it would be
easy to enforce. Also it opens doors for different ways of adapting
(e.g., use different window openning algorithms as UCL is proposing).

Cheers
Zheng
-- 
Zheng Wang                  
Bell Labs Lucent Technologies
http://www.bell-labs.com/user/zhwang

---

From: Jonathan Stone <[email-masked]>
Date: Sun, 1 Feb 1998 14:20:07 -0800 (PST)

>> And what about inherently different-sized flows?  [snip]

>(e.g., use different window openning algorithms as UCL is proposing).

Thanks very much for the clarification. 

This kind of `virtual pipe per customer' isolation probably works
extremely well for corporate customers.  But what about one user
inside Lucent gaming around _other_ Lucent users?  More concretely,
what if someone across the corridor for me starts a webserver and who
installed more parallel webcrawler servers until they're getting a
`big enough' fraction of Stanford's off-campus bandwidth to keep them
happy?  (This isn't a hypothetical case at all.)

One answer is that maybe the webcrawling bandwidth-hogs should be
treated as a separate `customer' and negotiate their own agreement ;
but that approach reduces opportunities for statistical-multiplexing,
or for the bandwidth hogs to use whatever idle capacity is available.

When you say:

  >easy to enforce.

That sounds rather like saying ``let all customers do traffic-shaping
at the exitpoint to their ISP''. Which is a better place to do it than
in the core of the network. But if you assume the individuals making
up a single network customer -- all Lucent employees, say -- really
are co-operative rather than Byzantine academics, then marking drop
preferences sounds like a rather useful tool for doing better
enforcement.  On the other hand, if each ISP customer really does
`enforce' adaptivity, they're doing traffic shaping.  In that case how
is isolation an incentive for apps to be adaptive?  It seems to me
you're relying on some unspecified `enforce' stick from the
administrative domain, not on customer isolation per se.

Or does `enforce' mean a corporate acceptable-use policy statement
rather than active dropping in customer's border gateways?

Sure, isolation may be a useful tool, but I dont think it's a complete
answer on its own, which I think is what you were saying originally.

---

From: Zheng Wang <[email-masked]>
Date: Mon, 02 Feb 1998 09:52:58 -0500

> or for the bandwidth hogs to use whatever idle capacity is available.

A user organization (e.g. Stanford U) should have policies to 
enforce it's own allocation among its own users. But the policies and
mechanisms do not have to be visible to Stanford U's ISP. Such a
hierarchical structure is essential for scalability.

Take telephone services for an example, Lucent subscribes for the
telephone services and pays for outgoing calls. How Lucent distibutes
the cost among its operating units is an internal matter. Since it
is under the same admin domain, some simple policy is usually
sufficient to prevent mishaving.

> enforcement.   

See above. Lcuent's ISP only deal with all Lucent's traffic
collectively. Lucent has to deal with individual flows/users
within Lucent's aggregated pipe. But we can assume that the
cooperative assumption is still valid within a single admin domain.

Cheers
Zheng

---

From: Steve Deering <[email-masked]>
Date: Mon, 2 Feb 1998 17:14:10 -0800

> provide different levels of "assured" or "best effort" service ?

By priority queueing, rather than priority dropping.  That is, segregating
the different traffic classes into different queues (link shares), with
a larger per-link bandwidth share and/or a smaller number of admitted
subscribers assigned to the higher priorities.  A customer could subscribe
to a particular priority level either for all of its traffic, or for a
subclass of its traffic (e.g., all RTP traffic to or from the CEO's PC).
In the latter case, traffic policers/shapers at ISP ingress would be used
to keep a customer's higher priority traffic within contracted bounds.

Steve

---

From: Steve Deering <[email-masked]>
Date: Mon, 2 Feb 1998 17:49:43 -0800

> 2) eliminates the incentive for behaving badly

There are a number of flavors of "traffic isolation" to which you might be
referring:

	(1) fixed bandwidth commitments to each user (TDM),
	(2) assignment of link-shares to each user, providing a lower-bound
	    on available bandwidth for each user, but allowing "sharing"
	    of unused bandwidth,
	(3) fair queueing, where the available bandwidth is evenly divided
	    among the working set of active users, or
	(4) something else?

Only (1) would allow the use of drop preference without the need/desire for
cooperation between competing users, but at the cost of giving up the
bandwidth efficiency of statistical multiplexing.

(1) and (2) require the use of signalling/admission-control/etc. wherever
the number or rate of change of potential users exceeds the capacity of
manual configuration.

(3) presents the problems of granularity and cheating that Jonathan Stone
mentioned.

Could you please be more precise about what you mean by "traffic isolation"?

Steve

---

From: Zheng Wang <[email-masked]>
Date: Tue, 03 Feb 1998 10:29:57 -0500

> Could you please be more precise about what you mean by "traffic isolation"?
 
First, I was trying to make the point that, to eliminate 
the incentives or behaving badly, the network has to be 
able to isolate traffic from competing flows.

As for what level of traffic isolation should be used and the
actual mechanisms, I outlined one scheme at the Dec IETF 
meeting (http://www.bell-labs.com/user/zhwang/diff-serv/usd.txt). 

In that proposal, the traffic is isolated between different user
organizations, for example, traffic belongs to company A and 
traffic belong to company B. Each user organization is assigned 
with a number called "share" which is proportional to the price
the user organization paid for the service. At the point of
congestion, the bandwidth is allocated in proportion to the
share the user organization has.

If one knows the exact path (e.g., in VPNs), fixed bandwidth
commitments is easy. However, to support traffic isolation 
everywhere in an ISP, fixed bandwidth is difficult to support
(one has to do worst-case allocation). Essentially, what I 
proposed is to maintain the proportional fairness among the
traffic belongs to different user organizations.

Frank Kelly proposed

---

From: Zheng Wang <[email-masked]>
Date: Tue, 03 Feb 1998 10:33:18 -0500

Sorry that the previous message sent out prematurely. I would 
like to point out that Frank Kelly has a web page on the issue
of "Proportional Fairness". See http://www.statslab.cam.ac.uk/~frank/pf/

Cheers
Zheng