RFC 970 (rfc970) - Page 1 of 9

On packet switches with infinite storage

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