On Packet Switches With Infinite Storage
RFC 970

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions

Network Working Group                                         John Nagle
Request for Comments: 970                                 FACC Palo Alto
                                                           December 1985

                On Packet Switches With Infinite Storage

Status of this Memo

   The purpose of this RFC is to focus discussion on particular problems
   in the ARPA-Internet and possible methods of solution.  No proposed
   solutions in this document are intended as standards for the
   ARPA-Internet at this time.  Rather, it is hoped that a general
   consensus will emerge as to the appropriate solution to such
   problems, leading eventually to the adoption of standards.
   Distribution of this memo is unlimited.

Abstract

   Most prior work on congestion in datagram systems focuses on buffer
   management.  We find it illuminating to consider the case of a packet
   switch with infinite storage.  Such a packet switch can never run out
   of buffers. It can, however, still become congested.  The meaning of
   congestion in an infinite-storage system is explored.  We demonstrate
   the unexpected result that a datagram network with infinite storage,
   first-in-first-out queuing, at least two packet switches, and a
   finite packet lifetime will, under overload, drop all packets.  By
   attacking the problem of congestion for the infinite-storage case, we
   discover new solutions applicable to switches with finite storage.

Introduction

   Packet switching was first introduced in an era when computer data
   storage was several orders of magnitude more expensive than it is
   today.  Strenuous efforts were made in the early days to build packet
   switches with the absolute minimum of storage required for operation.
   The problem of congestion control was generally considered to be one
   of avoiding buffer exhaustion in the packet switches.  We take a
   different view here.  We choose to begin our analysis by assuming the
   availablity of infinite memory. This forces us to look at congestion
   from a fresh perspective.  We no longer worry about when to block or
   which packets to discard; instead, we must think about how we want
   the system to perform.

   Pure datagram systems are especially prone to congestion problems.
   The blocking mechanisms provided by virtual circuit systems are
   absent.  No fully effective solutions to congestion in pure datagram
   systems are known.  Most existing datagram systems behave badly under
   overload.  We will show that substantial progress can be made on the

Nagle                                                           [Page 1]



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