On Packet Switches With Infinite Storage
RFC 970
|
Document |
Type |
|
RFC - Unknown
(December 1985; No errata)
|
|
Last updated |
|
2013-03-02
|
|
Stream |
|
Legacy
|
|
Formats |
|
plain text
html
pdf
htmlized
bibtex
|
Stream |
Legacy state
|
|
(None)
|
|
Consensus Boilerplate |
|
Unknown
|
|
RFC Editor Note |
|
(None)
|
IESG |
IESG state |
|
RFC 970 (Unknown)
|
|
Telechat date |
|
|
|
Responsible AD |
|
(None)
|
|
Send notices to |
|
(None)
|
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
Show full document text