Subject: RE: Draft on Advice for Internet Subnetwork Designers

From: Marie-Jose Montpetit <[email-masked]>
Date: Tue, 7 Mar 2000 03:54:12 -0800

On the topic of packet discard especially on those subnet where capacity is
expensive or limited I would add that when possible packets marked form
another subnet should be discarded before transmission on the link.

Actually this discussion raises also the whole issue of reservations. Some
sessions may be reserved so that packet are not randomly discarded but
discarded according to some priority scheme. Do we want to add RSVP or
diffserv issues to the LINK draft? Maybe in a future version?

Marie-Jose
-----Original Message-----
From: Dan Grossman [mailto:[email-masked]]
Sent: Monday, March 06, 2000 1:58 PM
Cc: Falk, Aaron; [email-masked]'; Phil Karn (E-mail)
Subject: Re: Draft on Advice for Internet Subnetwork Designers 

My thoughts on buffers and queueing didn't seem to generate much as much 
discussion as I'd hoped.  However, since the deadline is upon us, here is
some 
text that Phil can insert into the draft.

-----------------------------------------

Buffering, flow control and congestion control
Many kinds of subnets have points at which there is contention for link 
transmission resources.  At some of these points, the rate of the link may 
vary.  At such points, there must be a queueing system, including buffering,

scheduling and a capability to discard excess subnet packets.  These
queueing 
points may also be part of a subnet flow control or congestion control
scheme.

For the purpose of this discussion, a layered model of the interaction
between 
the IP layer and the subnet layer is not helpful.  Instead, we adopt the
frame 
of reference of a packet.  At each queueing point -- whether that point is
at 
the IP layer or at the subnet layer -- the packet experiences delay for a 
period of time (which depends on competing traffic and the scheduling 
discipline), and is subjected to a local discarding policy.   If there are 
flow control or congestion control mechanisms in the subnet that do not rely

on TCP, these must operate on the scheduling discipline and/or the
discarding 
policy in the subnet or in the routers at the edges of the subnet, since TCP

has no way to operate on their semantics and IP has no way to  be able to
pass 
their semantics to TCP;  however, see below for one exception.

TCP traffic, and especially aggregated TCP traffic, is bursty.  As a result,

instantanious queue depth at a queueing point can vary dramatically, even in

nominally stable networks.  For optimal performance, it is desirable that 
packets be dropped in a controlled fashion, rather than due to running out
of 
buffers.  As a rule of thumb, nodes should be engineered to have buffering 
available for each TCP connection equal to the product of the maximum 
instantanious rate at which packets can be transmitted on the link (which is

usually the link rate, but may be further limited by a shaper) and the 
propagation delay of the link.  For links that have variable propagation 
delays (such as having diverse paths, or variable depth interleavers), the 
longest likely propagation delay should be used.   

Unfortunately, since the maximum number of TCP connections at a queueing
point 
can neither be known with certainty a priori, nor limited by an admission 
control policy (except, perhaps, at a PEP), buffer sizes in subnet devices
can 
at best be engineered based on crude estimates.   In general, it is wise to 
err in favor of too much buffering rather than too little.  It may also be 
useful for subnets to incorporate mechanisms for measuring propagation
delay, 
to assist in buffer sizing calculations.

There is a rough consensus in the research community that  active queue 
management is important to improving fairness, link utilization  and 
throughput [RFC2309].   Although there are questions and concerns about the 
efficacy of active queue management (e.g., see [MBDL99]), it is widely 
considered an improvement over tail-drop discard policies.   

One well known example of an active queue management the Random Early 
Detection (RED) algorithm [RED93].  RED maintains an exponential weighted 
moving average of the queue depth.  When this average queue depth is between
a 
maximum threshold max_th, and a minimum threshold min_th, packets are
dropped 
with a probability which is proportional to the amount by which the average 
queue depth exceeds min_th.  When this average queue depth is equal to
max_th, 
the drop probability is equal to a configurable parameter max_p.  When this 
average queue depth is greater than max_th, packets are always dropped.  
Numerous variants on RED appear in the literature, and there are other
active 
queue management algorithms which claim advantages over RED in various 
dimensions.

Active queue management algorithms forms a control regime wherein dropped 
packets are treated as a feedback signal.  Randomization of dropping tends
to 
break up the observed tendency of TCP windows belonging to different TCP 
connections to become synchronized by correlated drops, and also imposes a 
degree of fairness on those connections which properly implement TCP 
congestion avoidance.    Another property of active queue management 
algorithms which is particularly important to subnet designers is that they 
attempt to keep average queue depths short, while accommodating large short 
term bursts. 

Since TCP neither knows nor cares whether packet loss due to congestive 
discard is due to congestion at the IP layer or in a subnet, it may be 
advisable for subnets  that perform queueing and discarding to consider 
implementing some form of active queue management.  This especially holds if

large aggregates of TCP connections are likely to share the same queue.  
However, active queue management may be less effective in the case of many 
queues carrying smaller aggregates of TCP connections, as for  example, in
an 
ATM switch that implements per-VC queueuing.  

Note,  incidentally, that the performance of active queue management 
algorithms is highly sensitive to settings of configurable parameters, and 
also to factors such as RTT [MBB00][FB00].  

Some subnets, most notably ATM, perform segmentation and reassembly at the 
edge of the subnet, so as to be able to forward subnet packets of size less 
than an MTU.  There are advantages and disadvantages to doing this.
However, 
if this is done, care should be taken in designing discard policies. Subnet 
packets with missing fragments must be destroyed by the subnet, as they are
of 
no use to  TCP.  Thus, if the subnet discards random and uncorrelated 
fragments of IP  packets, then the balance of these packets constitute an 
unproductive load on the subnet and can markedly degrade end-to-end 
performance. [RF95]  Therefore, subnets should attempt to discard entire IP 
packets.  If a portion of an IP packet has been forwarded and discarding of 
subnet packets which are fragments of the IP packet becomes unavoidable,
then 
either all remaining fragments or all but the fragment marking the end of
the 
packet should be discarded.   For ATM subnets, this specifically means using

Early Packet Discard and Partial Packet Discard [ATMFTM]. 

Some subnets might includes flow control mechanisms that effectively require

that the rate of traffic flows be shaped as they enter the subnet.  One 
example of such a subnet mechanism is in the ATM Available Bitrate (ABR) 
service category [ATMFTM].   Such flow control mechanisms have the effect of

making the subnet nearly lossless by pushing congestion into the IP routers 
edges of the subnet.  In such a case, adequate buffering and discard
policies 
are needed in these routers to deal with a subnet which appears to have 
dynamically varying bandwidth.   Whether or not there is benefit in this
kind 
of flow control is controversial, and there have been numerous simulation
and 
analytical studies that go both ways.  It appears that some of the issues
that 
lead to such different results include sensitivity to ABR parameters, use of

binary rather than explicit rate feedback, use (or not) of per-VC queueing, 
and the specific ATM switch algorithms selected for the study.
Anecdotally, 
some large networks have used IP over ABR to carry TCP traffic, and have 
claimed it to be sucessful, but have published no results.
 
Another possible approach to flow control in the subnet would be to work
with 
TCP Explicit Congestion Notification (ECN) semantics [RFC2481].  Routers at 
the edges of the subnet, rather than shaping, would set the ECN bit in those

IP packets that are received in subnet packets that have an ECN indication.

Nodes in the subnet would need to implement an  active queue management 
protocol which marks subnet packets rather than dropping. However, RFC2481
is 
presently experimental, and TCPs which can use ECN are not widely deployed. 

------------
References 
 
[ATMFTM] The ATM Forum, "Traffic Management Specification, Version 4.0",
April 
1996, document af-tm-0056.000 (www.atmforum.com).

[FB00] Firoiu V., and Borden M., "A Study of Active Queue Management for 
Congestion Control" to appear in Infocom 2000

[MBB00] May, M., Bonald, T., and Bolot, J-C., "Analytic Evaluation of RED 
Performance" to appear INFOCOM 2000

[MBDL99] May, M., Bolot, J., Diot, C., and Lyles, B., Reasons not to deploy 
RED, technical report, June 1999.

[RF95] Romanow, A., and Floyd, S., Dynamics of TCP Traffic over ATM
Networks. 
IEEE JSAC, V. 13 N. 4, May 1995, p. 633-641.

[RFC2481] Ramakrishan, K. and Floyd S.,  "A Proposal to add Explicit
Congestion
          Notification (ECN) to IP" RFC2481 January 1999

---

From: Phil Karn <[email-masked]>
Date: Thu, 9 Mar 2000 00:17:36 -0800

>another subnet should be discarded before transmission on the link.

Is this an issue for the subnetwork designer, or for the router that
drives the subnetwork?

Phil