RFC 970 (rfc970) - Page 2 of 9

On packet switches with infinite storage

RFC 970                                                    December 1985
On Packet Switches With Infinite Storage


   congestion control problem even for pure datagram systems when the
   problem is defined as determining the order of packet transmission,
   rather than the allocation of buffer space.

A Packet Switch with Infinite Storage

   Let us begin by describing a simple packet switch with infinite
   storage.  A switch has incoming and outgoing links.  Each link has a
   fixed data transfer rate.  Not all links need have the same data
   rate. Packets arrive on incoming links and are immediately assigned
   an outgoing link by some routing mechanism not examined here.  Each
   outgoing link has a queue.  Packets are removed from that queue and
   sent on its outgoing link at the data rate for that link.  Initially,
   we will assume that queues are managed in a first in, first out
   manner.

   We assume that packets have a finite lifetime.  In the DoD IP
   protocol, packets have a time-to-live field, which is the number of
   seconds remaining until the packet must be discarded as
   uninteresting. As the packet travels through the network, this field
   is decremented; if it becomes zero, the packet must be discarded.
   The initial value for this field is fixed; in the DoD IP protocol,
   this value is by default 15.

   The time-to-live mechanism prevents queues from growing without
   bound; when the queues become sufficiently long, packets will time
   out before being sent.  This places an upper bound on the total size
   of all queues; this bound is determined by the total data rate for
   all incoming links and the upper limit on the time-to-live.

   However, this does not eliminate congestion.  Let us see why.

   Consider a simple node, with one incoming link and one outgoing link.
   Assume that the packet arrival rate at a node exceeds the departure
   rate.  The queue length for the outgoing link will then grow until
   the transit time through the queue exceeds the time-to-live of the
   incoming packets.  At this point, as the process serving the outgoing
   link removes packets from the queue, it will sometimes find a packet
   whose time-to-live field has been decremented to zero.  In such a
   case, it will discard that packet and will try again with the next
   packet on the queue.  Packets with nonzero time-to-live fields will
   be transmitted on the outgoing link.

   The packets that do get transmitted have nonzero time-to- live
   values. But once the steady state under overload has been reached,
   these values will be small, since the packet will have been on the
   queue for slightly less than the maximum time-to-live.  In fact, if


Nagle