Subject: support for packet drop priority

From: Venkat Padmanabhan <[email-masked]>
Date: Fri, 16 Jan 1998 22:15:44 -0800

I was wondering how widespread support for packet drop priority in
today's IP routers is. What I have in mind is a mechanism that would
allow end hosts to mark packets as "low priority" (perhaps using the
IP TOS field) and have routers pick such packets first when they
need to drop a packet. This is similar to CLP in ATM.

I'd appreciate any information on this. Thanks.

-Venkat

---

From: Jean-Yves Le Boudec <[email-masked]>
Date: Tue, 20 Jan 1998 14:07:41 +0200

>need to drop a packet. This is similar to CLP in ATM

This is similar indeed, but also there is a big difference: with ATM, CLP0
and CLP1 flows are policed separately. A user normally pays differently for
CLP1 and CLP0 data (without mentioning CLP used for tagging out of profile
data).

In IP that could work at the edge router performing metering, but probably
not at the end user (I would send all my packets with high prio !)

---

From: Steve Deering <[email-masked]>
Date: Tue, 20 Jan 1998 14:56:17 -0800

> need to drop a packet. This is similar to CLP in ATM.

This is a bad idea unless you can figure out how to make a source stop
sending its low priority packets once congestion occurs and is detected.
Otherwise, your proposed mechanism encourages sources to send low priority
packets continuously into paths that cannot deliver them, thereby
wasting bandwidth that might otherwise be used for the successful delivery
of low priority packets to other (non-congested) destinations.

Steve

---

From: Venkat Padmanabhan <[email-masked]>
Date: Tue, 20 Jan 1998 15:35:40 -0800

> of low priority packets to other (non-congested) destinations.

I agree that such a mechanism should be used with care. But it seems
to me that the potential for misuse is no worse than, say, a broken
TCP congestion control implementation. For example, a TCP
implementation that does not back off in response to packet loss could
lead to a problem similar to the one you outline. I suppose the 
traditional "safeguard" against this has been implementing the end
host algorithms correctly (and fixing bugs if and when they are
found). A more recent approach is monitoring and penalizing of
aggressive traffic streams by routers. Both these approaches could 
(and should) be used in the context of low priority traffic as well.

I am investigating packet drop priority in the context of a modified
TCP sender algorithm. I am assuming that the end hosts cooperate and
implement the "correct" algorithm.

-Venkat

---

From: Geoff Huston <[email-masked]>
Date: Wed, 21 Jan 1998 16:41:52 +1100

Steve,

I'd suggest that this is a pretty tenuous line of reasoning you've given
regarding this being a Bad Idea.

If you are suggesting that the use of some form of packet
drop priority encourages a mode of behaviour which results
in nwetwork oversubscription, then I can't see how you reach this
conclusion.   Surely right now if this were the case we'd all
use aggressively opportunistic data carriage applications like
FSP which relay on oversubscription as a mechanism
of claiming more network space - the fact is that the control
mechanisms for over-use behaviour are quite varied.

In a flat rate pricing system why should I send ANYpackets
with any low priority whatsoever?

If there is a pricing discount for low priority packets then 
the issue is that the lower price still implies a higher drop
probability, and the real issue is whether the total
price paid divided by the total amount of delivered
data is greater or less than the equivalent sum
without use of a drop priority.

My point is that you cannot assume the absense of
non-protocol control issues in this dicussion, and you cannot
attempt to predict user behaviour based on the
behaviour of the protocols alone.

geoff

---

From: Steve Deering <[email-masked]>
Date: Tue, 20 Jan 1998 23:44:10 -0800

At 9:41 PM -0800 1/20/98, Geoff Huston wrote:
> conclusion.

Geoff,

This is a re-play of a discussion that was held on this list a number of
months ago.  If the rest of this reply doesn't satisfy, I suggest you peruse
the archive (just scan for my name -- this is the only issue that agitates
me enough to post to this list).  You'll find lots of messages from other
folks who disagreed with me as well.  :-)

I am assuming that most people who want a drop preference feature envision
hosts (or site aggregators) sending packets of different drop preferences,
where the traffic sent with greater drop preference (i.e., greater
probability of being dropped) is for some reason considered less
important/urgent than the traffic sent with lesser drop preference.  If the
drop preference feature is supported, a host or site is implicitly encouraged
to send all its traffic, and leave it to any congested routers to ensure that
the less important packets are dropped before any of the more important
packets -- otherwise, what's the purpose of the drop preference feature?
On the other hand, if the drop preference feature is *not* supported, then
the host or site is discouraged from sending less important traffic when it
won't fit, because doing so would put its more important traffic at greater
risk of being dropped.

>   Surely right now if this were the case we'd all
> of claiming more network space -

What's FSP?

Fact is, folks *are* currently hacking their TCP implementations to make
them more aggressive in order to claim a greater share of bandwidth
(The use of multiple, parallel TCP conections by web browsers is another
trick to accomplish the same end.)  And it's only band-aids like multicast
tunnel rate-limiters that keep the MBone A/V apps from grabbing all the
bandwidth on some paths.

> the fact is that the control mechanisms for over-use behaviour are quite
> varied.

Seems to me they are mostly speculative, at this point.

I agree that there is an urgent need for mechanisms to discourage the
transmission of packets that can't make it to their destinations (or, if
you happen to *benefit* from useless packet sending, for example by being
an ISP who manages to collect money for every packet sent regardless of
whether or not it reaches its destination, then your customers have an
urgent need to detect when they are sending into a congested path in order
to avoid your charges).  RED-with-penalty-box is one promising candidate
mechanism, in the non-monetary space.  But once you have the needed
mechanism(s) in place to let sources know when they are overdriving a network
path, the drop preference feature becomes unnecessary: the prioritizing and
discarding can and should be done at the source, rather than filling the
links of the path with doomed packets whose only effect is to deny bandwidth
to other sources who might be able to make more productive use of it.

Steve

---

From: "Alessio Casati" <[email-masked]>
Date: Wed, 21 Jan 1998 11:35:19 +0100

> of low priority packets to other (non-congested) destinations.

To me this new thread seems to be much similar to something being discussed
some months ago. I recall Steve's example, for the list convenience

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

So I would suggest to have a look in the archive for the rather lengthy debate following
the quoted message.
In my opinion If the mechanisms are going to leverage on this CLP-like bit, in a sound
and consistent fashion (that is what Steve's worried about is prevented by proper billing, 
policing, ingress shaping, or penalty actions), then OK, what's wrong with it?
On the other hand Steve proposed to rely on adaptation, if I'm not wrong in catching the
meaning of his words. In my opinion, in order to prevent users from misbehaviour, that is
from missing adapting to network conditions, the same set of tools and mechanisms would be needed 
as the ones required by the approach discouraging users from setting bits in a malicious way.

The goal of the WG is very likely to be the definition of a framework letting providers meter
the amount of traffic their users are sending, and, for the allowed part of it, a differentiated 
treatment depending on the subscribtion/peering agreements (and dynamic negotiation?). Adaptation 
will be a consequence of savings and perceived quality improvement adaptation is going to allow. 
But I'm not sure adaptation capable users are to be assumed as the normal source of IP traffic, and 
to build the diffserv model based on this assumption.

alessio

---

From: "Alessio Casati" <[email-masked]>
Date: Wed, 21 Jan 1998 11:56:27 +0100

> to other sources who might be able to make more productive use of it.

The DP may not be necessary in your opinion, but, let me say, it does not play against encouraging
applications to adapt and it can be a powerful tool for penalty action you'd otherwise
be difficult to build. Let me say a DP equipped model is at least as powerful as a non DP
one, but a provider has an additional hook (hammer?) to play his game.

alessio

---

From: Steve Deering <[email-masked]>
Date: Wed, 21 Jan 1998 08:19:57 -0800

> ...what Steve's worried about is prevented by proper billing,
> policing, ingress shaping, or penalty actions

Unless a policing or ingress-shaping point is receiving real-time, per-path
feedback about the occurrence of congestion inside the network, policing
or ingress shaping do not prevent what I am worried about.  The simple-
minded drop preference schemes that most folks are advocating do not include
any such feedback.  And you'll have to tell me exactly what "proper billing"
is before I agree that that would work.  Penalty actions are what I am
advocating.

> On the other hand Steve proposed to rely on adaptation, if I'm not wrong in
> catching the meaning of his words.

That's correct.  I am proposing as a fundamental design principal that all
internet applications (except possibly those that have a flow-granularity
bandwidth guarantee, such as might be obtained through int-serv "guaranteed"
service) perform effective end-to-end congestion control, and that the
router/network behavior be designed to penalize those applications that
do not.

[Note that this does not rule out providing multiple priority levels in order
to allow customers to pay more to get better service (e.g., implemented by
WFQ in the routers, with subscription-time or finer-grain admission-control
to ensure that the higher priority levels are kept lightly subscribed).
Effectively, each priority level can then act as a distinct virtual network,
in which end-to-end congestion control operates independently of the other
levels.]

Steve

---

From: Steve Deering <[email-masked]>
Date: Wed, 21 Jan 1998 08:47:54 -0800

At 2:56 AM -0800 1/21/98, Alessio Casati wrote:
> The DP may not be necessary in your opinion, but, let me say, it does not
> play against encouraging applications to adapt and it can be a powerful tool
> for penalty action you'd otherwise be difficult to build. Let me say a DP
> equipped model is at least as powerful as a non DP one, but a provider has
> an additional hook (hammer?) to play his game.

What are the arguments that support that assertion?  I've yet to see a
description of *one* effective hook/hammer to encourage adaptive applications,
other than router penalty boxes, and those are still not fully fleshed out.
Let's solve that harder but much more important problem first, before rushing
to deploy a DP mechanism which, at best, is likely to have only second-order
benefits and which, in the absence of a solution to the first problem, just
encourages very inefficient use of network capacity.

Steve

---

From: "Alessio Casati" <[email-masked]>
Date: Wed, 21 Jan 1998 18:30:29 +0100

On 21 Jan 98 at 8:19, Steve Deering wrote:

> or ingress shaping do not prevent what I am worried about. 

What I was meaning is that the metering activity may police the traffic so that excess traffic
either gets discarded or marked. If it gets discarded, than we are using you approach (correct me
if I misunderstand) if it gets marked than we are in a departing from your approach, but
here we get the tool to identify bad guys (and that's were I think you can agree, since
you tell that you want penalty actions later). Yes, you are using up some link bandwidth,
but this use can be economically sustainable depending on the service the provider is willing to 
offer. I cannot prevent a provider from deciding to allow this, if it thinks it's good for 
itself.

As you may cuncur here you do not need any kind of feedback info.

Ingress shaping can be used to constrain the tolerable marked unmarked traffic mix and
this, once again, does not require feedback. I'm not saying that any operator should use one
approach or another, I'm only showing what the alternatives are, and that they are not
necessarily implying bad news for anybody.

> The simple- minded drop preference schemes that most folks are advocating do not include

"Proper billing" is service dependent, so it would be hard to think to a general billing
I may tell you so that you agree with me, but the principle is, as I'm sure you are assuming,
the more you try to play against other people benefit, the more you'll have to pay.

> router/network behavior be designed to penalize those applications that

I cannot but agree that active congestion control would be of great benefit.

> in which end-to-end congestion control operates independently of the other

Is DP affecting negatively your approach?

alessio

---

From: Wu-chang Feng <[email-masked]>
Date: Wed, 21 Jan 1998 12:51:29 -0500

> packets continuously into paths that cannot deliver them,

If I recall correctly, the scheme Venkat is describing was posted on end2end
several months ago and is based on improving the recovery phase of TCP
connections (small ones, in particular) by quickly re-establishing ACK
clocking.  Because the scheme is still based in TCP and only sends the low
priority packets based on connection history, it does not continuously allow
non-deliverable, low priority packets into the network.  I don't think anyone
here is advocating bypassing congestion control with the use of DP bits (or
am I mistaken?)

Wu

---

From: Venkat Padmanabhan <[email-masked]>
Date: Wed, 21 Jan 1998 10:58:43 -0800

> here is advocating bypassing congestion control with the use of DP bits (or

Yes, I had posted this to the end2end list sometime in August '97.
The idea is for a TCP sender, that is re-starting after an idle
period, to optimistically use the old value of the congestion window.
But to guard against the possibility of this leading to congestion
losses for other connections, the TCP sender attempting "fast start"
marks its packets as low priority. If the fast start packets get
through without suffering losses, then all is well (ack clocking
would set in and TCP would progress as in the nornal case). But if they do
suffer losses, the TCP sender would fall back to standard slow start
with an initial window size of 1 segment. Therefore, as Wu observes,
this modified TCP is sensitive to losses as any other TCP, and would
not continuously overload the network with low priority packets.

-Venkat

---

From: Steve Deering <[email-masked]>
Date: Wed, 21 Jan 1998 11:18:58 -0800

At 10:58 AM -0800 1/21/98, Venkat Padmanabhan wrote:
>                                          Therefore, as Wu observes,

But what will cause TCPs to continue to be well-behaved, given that an
individual TCP can win by misbehaving, and what will discourage non-TCP
traffic from misusing the drop-preference feature?

Steve

---

From: Wu-chang Feng <[email-masked]>
Date: Wed, 21 Jan 1998 14:50:20 -0500

> traffic from misusing the drop-preference feature?

The lack of incentives to be well-behaved with DP is no different than it
is now without DP.  However, you could do strict policing of the high
priority packets at the first hop coupled with an enhanced (DP-enabled)
RED queue which runs the "RED-with-penalty-box" mechanism on the low
priority packets in order to give the misbehaving application some
incentive to behave.  I've been looking at building such an ERED queue in
ns.

Wu

---

From: Zheng Wang <[email-masked]>
Date: Wed, 21 Jan 1998 15:12:27 -0500

Steve Deering wrote:
 
> I've yet to see a
 
To encourage adaptive applications, we have to ensure that the traffic
is 
isolated from each other - why should I back off when I know others may
grab 
the released bandwidth.

This is why I am in favor of enforcing fairness at per-customer basis.
If company A's traffic is protected from company B's traffic, 
company A will see benefits by adjusting its traffic rate.

Cheers
Zheng

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

---

From: Shivkumar Kalyanaraman <[email-masked]>
Date: Wed, 21 Jan 1998 16:18:33 -0500 (EST)

> traffic from misusing the drop-preference feature?

What if the router ran rate control algorithms; converted the rate into a
window value and decremented the receiver window field ? A TCP would
interpret this as equivalent to the receiver dropping its window value. 

Any good algorithm from the ATM ABR work can be taken, multiply the rate 
feedback calculated by a reasonable RTT number (30 ms or so) and get a
window value. 

Of course, a misbehaving TCP could still ignore the receiver window field
...

-Shiv

---

From: Steve Deering <[email-masked]>
Date: Wed, 21 Jan 1998 13:46:24 -0800

> interpret this as equivalent to the receiver dropping its window value.

This wouldn't work for non-TCP traffic (which is probably the more serious
problem at this stage).

This wouldn't work if the TCP headers were encrypted end-to-end (which is
likely to become common at some future stage).

Steve

---

From: Steve Deering <[email-masked]>
Date: Wed, 21 Jan 1998 14:17:57 -0800

At 11:50 AM -0800 1/21/98, Wu-chang Feng wrote:
> is now without DP.

I disagree.  For sources that have traffic of different importance/urgency,
the current (non-DP-supporting) world encourages them to send only as much
traffic as can get through, because sending excess (less important) traffic
puts the more important traffic at greater risk of being dropped, i.e.,
the less important traffic competes on an equal footing with the more
important traffic.  If you add support for DP, you break that (admittedly
weak) incentive structure: if sending less important traffic no longer
threatens delivery of the more important traffic, sources may as well
send all their traffic as fast as they can.

Steve

---

From: Shivkumar Kalyanaraman <[email-masked]>
Date: Wed, 21 Jan 1998 17:44:39 -0500 (EST)

> This wouldn't work for non-TCP traffic (which is probably the more serious

^^^ Is the need of the hour an end-to-end flow control enhancement to UDP,
RTP etc which is lightweight enough ? (Probably which does not worry
about error control ?) Or should this be done only at the application
layer ?

What are the other non-TCP flows one should be seriously worried about ? 
How do we force them to do any form of end-to-end control ? 

How does a well-meaning UDP application which is sending useless packets 
avoid doing so ?

> likely to become common at some future stage).

But, aren't other protocols which violate the layering principle similarly
(like RSVP, IP switching) vulnerable to the same problem ? 

-Shiv

---

From: Gisli Hjalmtysson <[email-masked]>
Date: Wed, 21 Jan 1998 18:11:09 -0500

>send all their traffic as fast as they can.

I believe that there is a point missing in this whole debate, the issue of 
time scales.

I think it is a valid point that DP weakens the incentive to back-off.  
However, it takes a full round-trip for congestion indication to arrive at 
the source, by which time a _transient_ congestion may already have abated.  
The dynamics of a router buffer are on much shorter time scale.  As a 
consequence a _well_ behaved flow (source) may find it difficult to maintain
consistent (perceived) service quality (using only end-to-end congestion 
indication).  

A DP bit allows a _well behaved_ source to mark packets as lower class, so
that when a router must drop packets due to transient congestion, it can
drop the low priority packets, presumably minimizing the effect on the 
service quality.

I think that this is the primary potential of a DP bit.  However, more 
studies are needed to (re)introduce stronger incentives to have sources 
back-off in reaction to changes in load or network conditions (as opposed to 
transient congestion). A TCP-like solution could be that loosing K low class 
packets would be equivalent to loosing a single upper class packet.  Another
idea would be to linearly reduce the send window for every low class packet,
dropping by half for every upper class one.  

Best wishes/Gisli

---

From: Dorgham Sisalem <[email-masked]>
Date: Thu, 22 Jan 1998 09:35:59 +0100

> This wouldn't work for non-TCP traffic (which is probably the more serious

well not really, if we were using an RTP based application the routers 
can write the rate information into the RTCP packets which carry the 
rate indication to the receivers, who send them back to the senders. 
This way we would be even having a even more ABR-like approach.  I 
believe that the main question here is: is this worth the trouble, or 
can an adaptive application figure out the appropriate rate to use by 
itself. That is as the RTCP packets are only sent every 5 seconds or so,
the information from the routers might actually be too old by the time 
they reach the senders so that a rate estimation based on the loss and 
delay information carried in the RTCP packets anyway might just be 
enough

> likely to become common at some future stage).
this is anothet problem to look at

Dorgham

-- 
---
Dorgham Sisalem                   email:   [email-masked]
GMD-Fokus                         phone:   ++49 30 34 63 71 70
Kaiserin-Augusta-Allee 31         fax:     ++49 30 34 63 81 70
D-10589 Berlin 			  
URL:   http://www.fokus.gmd.de/usr/sisalem

---

From: [email-masked]
Date: Thu, 22 Jan 98 08:23:40 -0500

TCP is somewhat elastic. (Congestion decreases offered load.) 
Voice and Multimedia traffic (using UDP) "behave badly" (no elasticity).
Whether or not it uses RSVP, it introduces a relatively rigid load to
the net.   At least some people think this will grow and become
important.

Steve  Silverman

---

From: Zheng Wang <[email-masked]>
Date: Thu, 22 Jan 1998 11:06:47 -0500

> the net.   At least some people think this will grow and become
 
You are still missing the point. We *cannot* design the system based
on the assumption that end systems will follow the standard TCP 
congestion control. People will hack if there are incentives to do so.

Cheers
Zheng

---

From: Shivkumar Kalyanaraman <[email-masked]>
Date: Thu, 29 Jan 1998 08:29:49 -0500 (EST)

There were several references to RED+penalty box in this thread.  Could
someone point me to a reference describing this ?

Thanks in advance
Shiv
===
Shivkumar Kalyanaraman   
Assistant Professor, Dept of Electrical, Computer and Systems Engg,
Rensselaer Polytechnic Institute (RPI)
110, 8th Street, Rm JEC 6042, Troy NY 12180-3590
Ph: 518 276 8979  Secy (6313)	 Fax: 518 276 2433
Email: [email-masked]
Internet: http://www.ecse.rpi.edu/Homepages/shivkuma

---

From: "Alessio Casati" <[email-masked]>
Date: Fri, 30 Jan 1998 10:39:35 +0100

> someone point me to a reference describing this ?

http://www-nrg.ee.lbl.gov/floyd/red.html

alessio