rfc896.txt

RFC 相关的技术文档

at once, just as in the no-control case.  The user  will  see  no
visible  delay.   Thus,  our  scheme  performs as well as the no-
control scheme and provides better responsiveness than the  timer
scheme.

The second case to examine is the same Telnet  test  but  over  a
long-haul  link  with  a  5-second  round trip time.  Without any
mechanism to prevent  small-packet  congestion,  25  new  packets
would be sent in 5 seconds.* Overhead here is  4000%.   With  the
classic timer scheme, and the same limit of 2 packets per second,
there would still be 10 packets outstanding and  contributing  to
congestion.  Round-trip time will not be improved by sending many
packets, of course; in general it will be worse since the packets
will  contend  for line time.  Overhead now drops to 1500%.  With
our scheme, however, the first character from the user would find
an  idle  TCP connection and would be sent immediately.  The next
24 characters, arriving from the user at 200ms  intervals,  would
be  held  pending  a  message from the distant host.  When an ACK
arrived for the first packet at the end of 5  seconds,  a  single
packet  with  the 24 queued characters would be sent.  Our scheme
thus results in an overhead reduction to 320% with no penalty  in
response  time.   Response time will usually be improved with our
scheme because packet overhead is reduced, here by  a  factor  of
4.7 over the classic timer scheme.  Congestion will be reduced by
this factor and round-trip delay will decrease sharply.  For this
________
  * This problem is not seen in the pure ARPANET case because the
    IMPs will block the host when the count of packets
    outstanding becomes excessive, but in the case where a pure
    datagram local net (such as an Ethernet) or a pure datagram
    gateway (such as an ARPANET / MILNET gateway) is involved, it
    is possible to have large numbers of tiny packets
    outstanding.


RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84


case, our scheme has a striking  advantage  over  either  of  the
other approaches.

We use our scheme for all TCP connections, not just  Telnet  con-
nections.   Let us see what happens for a file transfer data con-
nection using our technique. The two extreme cases will again  be
considered.

As before, we first consider the Ethernet case.  The user is  now
writing data to TCP in 512 byte blocks as fast as TCP will accept
them.  The user's first write to TCP will start things going; our
first  datagram  will  be  512+40  bytes  or 552 bytes long.  The
user's second write to TCP will not cause a send but  will  cause
the  block  to  be buffered.  Assume that the user fills up TCP's
outgoing buffer area before the first ACK comes back.  Then  when
the  ACK  comes in, all queued data up to the window size will be
sent.  From then on, the window will be kept full,  as  each  ACK
initiates  a  sending  cycle  and queued data is sent out.  Thus,
after a one round-trip time initial period when only one block is
sent,  our  scheme  settles down into a maximum-throughput condi-
tion.  The delay in startup is only 50ms on the Ethernet, so  the
startup  transient  is  insignificant.  All three schemes provide
equivalent performance for this case.

Finally, let us look at a file transfer over the  5-second  round
trip  time connection.  Again, only one packet will be sent until
the first ACK comes back; the window will then be filled and kept
full.   Since the round-trip time is 5 seconds, only 512 bytes of
data are transmitted in the first 5 seconds.  Assuming a 2K  win-
dow,  once  the first ACK comes in, 2K of data will be sent and a
steady rate of 2K per 5 seconds will  be  maintained  thereafter.
Only  for  this  case is our scheme inferior to the timer scheme,
and the difference is only in the startup transient; steady-state
throughput  is  identical.  The naive scheme and the timer scheme
would both take 250 seconds to transmit a 100K  byte  file  under
the  above  conditions  and  our scheme would take 254 seconds, a
difference of 1.6%.

Thus, for all cases examined, our scheme provides at least 98% of
the  performance  of  both other schemes, and provides a dramatic
improvement in Telnet performance over paths with long round trip
times.   We  use  our  scheme  in  the  Ford  Aerospace  Software
Engineering Network, and are able to run screen editors over Eth-
ernet and talk to distant TOPS-20 hosts with improved performance
in both cases.

                  Congestion control with ICMP

Having solved the small-packet congestion problem and with it the
problem  of excessive small-packet congestion within our own net-
work, we turned our attention to the problem of  general  conges-
tion  control.   Since  our  own network is pure datagram with no
node-to-node flow control, the only  mechanism  available  to  us


RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84


under  the  IP standard was the ICMP Source Quench message.  With
careful handling,  we  find  this  adequate  to  prevent  serious
congestion problems.  We do find it necessary to be careful about
the behavior of our hosts and switching  nodes  regarding  Source
Quench messages.

               When to send an ICMP Source Quench

The present ICMP standard* specifies that an ICMP  Source  Quench
message  should  be  sent whenever a packet is dropped, and addi-
tionally may be sent when a gateway finds itself  becoming  short
of  resources.   There is some ambiguity here but clearly it is a
violation of the standard to drop a  packet  without  sending  an
ICMP message.

Our basic assumption is that packets ought not to be dropped dur-
ing  normal  network  operation.   We  therefore want to throttle
senders back before they overload switching nodes  and  gateways.
All  our  switching  nodes  send ICMP Source Quench messages well
before buffer space is exhausted; they do not wait  until  it  is
necessary to drop a message before sending an ICMP Source Quench.
As demonstrated in our  analysis  of  the  small-packet  problem,
merely  providing  large  amounts of buffering is not a solution.
In general, our experience is that Source Quench should  be  sent
when  about  half  the  buffering space is exhausted; this is not
based on extensive experimentation but appears to be a reasonable
engineering  decision.   One  could  argue for an adaptive scheme
that adjusted the quench generation  threshold  based  on  recent
experience; we have not found this necessary as yet.

There exist other gateway implementations  that  generate  Source
Quenches  only after more than one packet has been discarded.  We
consider this approach undesirable since any system for  control-
ling congestion based on the discarding of packets is wasteful of
bandwidth and may be susceptible  to  congestion  collapse  under
heavy  load.   Our understanding is that the decision to generate
Source Quenches with great reluctance stems from a fear that ack-
nowledge  traffic  will  be quenched and that this will result in
connection failure.  As will be shown below, appropriate handling
of  Source  Quench in host implementations eliminates this possi-
bility.

        What to do when an ICMP Source Quench is received

We inform TCP or any other  protocol  at  that  layer  when  ICMP
receives  a Source Quench.  The basic action of our TCP implemen-
tations is to reduce the amount of data  outstanding  on  connec-
tions to the host mentioned in the Source Quench. This control is
________
  * ARPANET RFC 792 is the present standard.  We are advised by
    the Defense Communications Agency that the description of
    ICMP in MIL-STD-1777 is incomplete and will be deleted from
    future revision of that standard.


RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84


applied by causing the sending TCP to behave as  if  the  distant
host's  window  size  has been reduced.  Our first implementation
was simplistic but effective;  once  a  Source  Quench  has  been
received  our  TCP behaves as if the window size is zero whenever
the window isn't  empty.   This  behavior  continues  until  some
number  (at  present 10) of ACKs have been received, at that time
TCP returns to normal operation.* David Mills  of  Linkabit  Cor-
poration  has  since  implemented  a  similar  but more elaborate
throttle on the count of outstanding packets in his DCN  systems.
The  additional  sophistication seems to produce a modest gain in
throughput, but we have not made formal tests.  Both  implementa-
tions effectively prevent congestion collapse in switching nodes.

Source Quench thus has the effect of limiting the connection to a
limited number (perhaps one) of outstanding messages.  Thus, com-
munication can continue but at a reduced rate,  that  is  exactly
the effect desired.

This scheme has the important property that Source Quench doesn't
inhibit  the  sending of acknowledges or retransmissions.  Imple-
mentations of Source Quench entirely within the IP layer are usu-
ally unsuccessful because IP lacks enough information to throttle
a connection properly.  Holding back acknowledges tends  to  pro-
duce  retransmissions and thus unnecessary traffic.  Holding back
retransmissions may cause loss of a connection by  a  retransmis-
sion  timeout.   Our  scheme  will  keep  connections alive under
severe overload but at reduced bandwidth per connection.

Other protocols at the same layer as TCP should also  be  respon-
sive  to  Source  Quench.  In each case we would suggest that new
traffic should be throttled but acknowledges  should  be  treated
normally.   The only serious problem comes from the User Datagram
Protocol, not normally a major traffic generator.   We  have  not
implemented  any  throttling  in  these protocols as yet; all are
passed Source Quench messages by ICMP but ignore them.

                    Self-defense for gateways

As we have shown, gateways are vulnerable to  host  mismanagement
of  congestion.  Host misbehavior by excessive traffic generation
can prevent not only the host's own traffic from getting through,
but  can interfere with other unrelated traffic.  The problem can
be dealt with at the host level but since one malfunctioning host
can  interfere  with others, future gateways should be capable of
defending themselves against such behavior by obnoxious or  mali-
cious hosts.  We offer some basic self-defense techniques.

On one occasion in late 1983, a TCP bug in an ARPANET host caused
the  host  to  frantically  generate  retransmissions of the same
datagram as fast as the ARPANET would accept them.   The  gateway
________
  * This follows the control engineering dictum  "Never bother
    with proportional control unless bang-bang  doesn't work".


RFC 896    Congestion Control in IP/TCP Internetworks      1/6/84


that connected our net with the ARPANET was saturated and  little
useful  traffic  could  get  through,  since the gateway had more
bandwidth to the ARPANET than to our  net.   The  gateway  busily
sent  ICMP  Source  Quench  messages  but the malfunctioning host
ignored them.  This continued for several hours, until  the  mal-
functioning  host  crashed.   During this period, our network was
effectively disconnected from the ARPANET.

When a gateway is forced to  discard  a  packet,  the  packet  is
selected  at  the  discretion of the gateway.  Classic techniques
for making  this  decision  are  to  discard  the  most  recently
received packet, or the packet at the end of the longest outgoing
queue.  We suggest that a worthwhile practical measure is to dis-
card  the  latest  packet  from the host that originated the most
packets currently queued within the gateway.  This strategy  will
tend  to  balance throughput amongst the hosts using the gateway.
We have not yet tried this strategy, but it  seems  a  reasonable
starting point for gateway self-protection.

Another strategy is to discard a  newly  arrived  packet  if  the
packet  duplicates  a  packet already in the queue.  The computa-
tional load for this check is not a problem if hashing techniques
are  used.   This  check will not protect against malicious hosts
but will provide some protection against TCP implementations with
poor  retransmission  control.   Gateways between fast local net-
works and slower long-haul networks may find this check  valuable
if the local hosts are tuned to work well with the local network.

Ideally  the  gateway  should  detect  malfunctioning  hosts  and
squelch them; such detection is difficult in a pure datagram sys-
tem.  Failure to  respond  to  an  ICMP  Source  Quench  message,
though,  should be regarded as grounds for action by a gateway to
disconnect a host.  Detecting such failure is non-trivial but  is
a worthwhile area for further research.

                           Conclusion

The congestion control problems  associated  with  pure  datagram
networks  are  difficult, but effective solutions exist.  If IP /
TCP networks are to be operated under heavy load, TCP implementa-
tions  must address several key issues in ways at least as effec-
tive as the ones described here.