Subject: Drop-preference implementation

From: Steven L Blake <[email-masked]>
Date: Mon, 20 Oct 1997 11:27:18 EDT

If the objective is to assure service to in-profile traffic while allowing
out-of-profile traffic to fill in the gaps, then the problem with drop-
preference implementations such as WRED (RIO) and its variants is that
well-behaved in-profile traffic cannot fill a link in the event that it
competes with out-of-profile traffic which doesn't back off in the event
of packet loss.  This is because badly behaved out-of-profile (DP) packets
can occupy a steady-state fraction of a persistent queue, even if there
is a low queue drop threshold for this class of packets.  Since service 
rate is a function of steady-state queue occupancy, this traffic can still
claim a fraction of the link even though there are competing in-profile
flows which are eligible to ramp up their rates.

One way to avoid this problem is to deploy a scheme like FRED, which tries
to pick out the badly behaved flows and put them in a "penalty box".  It's
not clear though that these schemes will scale to 10 Gbps links with a 
million separate flows, where the individual mis-behavior of each flow is
small but the cumulative effect is large.  

Another method of addressing this problem is a variant form of priority
pushout discard policy.  In such a scheme the number of DP packets allowed
to reside in a queue is a monotonically decreasing function of the number
of in-profile (non-DP) packets in the queue.  This discard policy has the
flavor of strict priority queues but without the reordering hazard.  One
thing it will not do is enable different delay priorities, although it
could be used on each of separate delay priority queues.

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: Juha Heinanen <[email-masked]>
Date: Mon, 20 Oct 1997 21:13:43 +0300

steve,

nice to read a technically constructive message on the list.  the idea
of giving dp packets buffer space inversely proportionally to the number
of non-dp packets is a good one.  in fact, we had in our fba paper a
very similar idea: when queue occupancy was low, a flow could more that
its fair share of the buffer space and when the queue occupancy grew,
the less extra space it was granted.  this way it was possible to make
sure that new or slow flows got their cells into the buffer and, on the
other hand, make efficient use of the buffer space when only a small
number of flows were simultaneously active.

-- juha

---

From: [email-masked] (Hyogon Kim)
Date: Mon, 20 Oct 1997 15:10:33 -0400 (EDT)

Steven,

>flows which are eligible to ramp up their rates.

With simple, infinite source model, our simulation results show that RIO
variations do guarantee profile rate to (adaptive) sources under the
attack of non-adaptive sources, if the network was not underengineered. 
Yes, non-adpative sources take away a lot, but not to the extent that 
adaptive sources cannot meet their profiles. With infinite source model, 
the non-adaptive sources keep pushing up the average queue length until 
it hovers around the maximum drop threshold for the out-of-profile 
packets. Then their affect is contained, and adpative sources are
protected inside their profile. However, it is also true that the
adaptive sources can't get more than their profiles.

I haven't yet checked if and how the result will change for more realistic 
non-infinite sources, though.

-- 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: Steven L Blake <[email-masked]>
Date: Mon, 20 Oct 1997 16:00:27 EDT

> nice to read a technically constructive message on the list.  the idea

Thanks, but I think you are being too generous to me and too harsh to
others.  :)

> number of flows were simultaneously active.

Is this paper available on-line?  It's quite probable that my idea
originated with your paper, filtered through conversations with fellow
IBM'ers.

---

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

> non-infinite sources, though.

Interesting.  Empirical evidence trumps idle speculation every time.

After talking to Brad Makrucki, I'm now pretty convinced that I was full
of crap and that with a single deterministic drop threshold the steady-
state DP occupancy that I previously claimed cannot occur, and I'm willing
to bet that you're right and that it won't occur with WRED/RIO with
reasonable thresholds.

An alternative justification for pushout is that the max DP threshold needs
to be engineered low to mitigate non-DP delay, and that at this value it
will be too low to permit useful DP utilization when non-DP traffic
is idle, but that is just grasping at straws.

Sorry for flaming other people's work.

---

From: Wu-chang Feng <[email-masked]>
Date: Mon, 20 Oct 1997 17:35:14 -0400

> attack of non-adaptive sources, if the network was not underengineered.

We've also shown in some of our experiments (from the previously posted work)
that you can provide some protection in the presence of non-responsive flows.
One of the things which must be considered is
setting the individual min_th and max_th values so that priority/marked packets
aren't dropped due to an overoccupation of best-effort/unmarked packets.

You basically need the following
  1) min_th(unmark) < max_th(unmark) < min_th(mark) < max_th(mark)
  2) [BW(in) - BW(out)] * [qlen/BW(out)] < min_th(mark) - max_th(unmark)

The second condition roughly ensures that no priority packets are dropped
if the worst case number of unmarked packets (max_th(unmark)) are in the queue.
BW(in) is the sum of the bandwidths of all incoming links.  BW(out) is the
bandwidth of the output link. [qlen/BW(out)] is the time it takes to drain
the queue of unmarked packets.  When the bandwidth mismatches are large,
condition 2 becomes extremely hard to meet.

Of course, if you have a mechanism which goes into the RED queue
and drops unmarked packets whenever the queue is full and a marked
packet needs to be enqueued, you don't have to worry so much about the
settings of min_th and max_th......

Wu

---

From: Roch Guerin <[email-masked]>
Date: Mon, 20 Oct 97 19:40:25 -0400

It's true that with threshold based policies you can achieve some level
of "protection" for higher priority traffic, although you in a way
have to give up the portion of buffers below the threshold, i.e., the
high priority traffic will see the same kind of performance as if it
had a dedicated buffer of size what's above the threshold.

>settings of min_th and max_th......

Now, that's not really true.  Actually, you can show that pushout
policies cannot really give you the same protections as threshold
based ones.  You can easily see it through sample paths arguments, but
it also holds for much more realistic load conditions (not that I want
to advertise it, but we had a paper providing some formal
justification for this and also giving some more realistic examples.
I have appended the ref below ;-)

Roch

Ref: 
I. Cidon, R. Guerin, and A. Khamisy.  "Protective Buffer Management
Policies."  IEEE/ACM Trans. Netw., Vol. 2, No. 3, June 1994,
pp. 240--246.

---

From: Debanjan Saha <[email-masked]>
Date: Mon, 20 Oct 1997 21:35:43 -0400

> I have appended the ref below ;-)

 Roch,
I didn't quite understand your comment. Of course I'll read your paper
:-), but is it really
true that you results hold for the threshold based policy and pushout
mechanism that Wu-chang mentioned in his mail.

Debanjan.

---

From: [email-masked] (Hyogon Kim)
Date: Mon, 20 Oct 1997 23:12:01 -0400 (EDT)

Wu,

>the queue of unmarked packets.  

umm...are we talking instantaneous queue length here (i.e. "qlen" above)? 
I understand rule (2) above is to estimate the (required) gap between 
min_th[mark] and max_th[unmark], but the thresholds are in terms of average 
queue length. Unfortunately the time-averaged queue lengths do not "drain" as 
fast as the rule (2) would suggest, I guess.

In fact, RIO has two average queue lengths for "marked" and "marked+unmarked". 
Where would those two avg qlengths be in your picture "if the worst case
number of unmarked packets are in the queue"...? 

>When the bandwidth mismatches are large, condition 2 becomes extremely hard to meet.

In fact, if the mismatch is large and the sum of the profiles of the incoming 
traffic is constantly larger than BW(out), you should re-engineer the link.
Differentiation effect fades away under underengineering. That may be
why Clark assumes "well-engineered" network in his draft, and shows a
simulation result at an exactly engineered network (sum of profiles
("target rates") = link capacity). In fact that's where the differentiation
effect is maximized.

-- Hyogon

---

From: [email-masked] (Hyogon Kim)
Date: Mon, 20 Oct 1997 23:31:53 -0400 (EDT)

>had a dedicated buffer of size what's above the threshold.

Right, and that's why we should have larger buffer in RIO variations 
than we had in plain RED, as mentioned in Clark's draft. One then would
wonder why we should allocate not-insignificant buffer space for 
out-of-profile packets (causing more queueing delays), but don't forget that 
that much buffer space is what your TCPs see when their (sum of the) profiles 
are smaller than the link capacity. Namely, when your link is underutilized 
by in-profile packets, your throughput is driven by out-of-profile packets, 
and the buffer space for out-of-profile packets is small? I am sure you
will begin to see funny things happening... hence separate queues for
delay-priority packets, I guess.

-- Hyogon

---

From: Wu-chang Feng <[email-masked]>
Date: Tue, 21 Oct 1997 00:34:30 -0400 (EDT)

>>settings of min_th and max_th......

This sounds a lot worse than I had intended.  This was actually meant 
to address the situation where the bandwidth mismatch was large enough 
to make min_th(marked)-max_th(unmarked) a problem.  (i.e. you'd only be 
able to give unmarked packets a miniscule amount of buffer space in order 
to ensure no priority packets get dropped due to overflow on the output 
queue).  Limiting unmarked packets to such an extent is bad for link 
utilization when there aren't a lot of marked packets going through the
network.  I'm definitely not advocating that pushout mechanisms be used in 
place of threshhold-based ones.  Pushout mechanisms allow the router to 
waste its resources in protocol processing, routing, and buffering unmarked 
packets that eventually get dropped in the output queue.  Allowing the 
router to do such things can cause priority packets to eventually get 
dropped due to input queue overflow instead.

Wu

P.S.  Do you have an electronic copy of that protective buffer management 
paper?  Should've gotten a copy of it while I had the chance.....

---

From: Wu-chang Feng <[email-masked]>
Date: Tue, 21 Oct 1997 00:55:32 -0400 (EDT)

> umm...are we talking instantaneous queue length here (i.e. "qlen" above)? 

I guess I should've put max_th(unmark) instead of qlen to be consistent.  
You're correct about the inaccuracy of using averages.  I was hoping
"roughly ensures" would be vague enough to avoid getting called on this. ;)
To be exact and precise, you'd want min_th and max_th to be triggered 
by absolute queue lengths not the EWMA of the queue length.  Since in our 
experiments we treat the sending of marked and unmarked packets with TCP 
windowing, we use the EWMA in order to obtain the benefits that the RED 
algorithm gives to TCP-based congestion control.

Wu

---

From: Roch Guerin <[email-masked]>
Date: Tue, 21 Oct 97 07:01:59 -0400

>paper?  Should've gotten a copy of it while I had the chance.....

Got a postscript version that's essentially similar to what appeared
in ToN.  Can send you a copy.  Roch

---

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

> dropped due to input queue overflow instead.

... only in a poor router design and a bad implementation of push-out.
Routers have to process fast, irrespective of whether the buffers
are full or not. So they always have the resources for protocol
processing and routing. Push-out can additionally help in improving buffer
utilization and isolating the "bad" or mis-behaving users ...

Don't forget also that Drop-From-Front is always better  than
tail drop for adaptive applications. It notifies the sources
about the congestion much faster, and  congestion control 
mechanisms can kick in and prevent further losses. 

(for more info see T.V. Lakshman's et.al Drop-from-front paper
in Infocom'96 )

Dimitri