As per Relevance of the word switches, we have this rfc below:
Network Working Group John
Request for Comments: 970 FACC Palo
December 1985
On Packet Switches With Infinite
Status of this
The purpose of this RFC is to focus discussion on particular
in the ARPA-Internet and possible methods of solution. No
solutions in this document are intended as standards for
ARPA-Internet at this time. Rather, it is hoped that a
consensus will emerge as to the appropriate solution to
problems, leading eventually to the adoption of standards
Distribution of this memo is unlimited
Most prior work on congestion in datagram systems focuses on
management. We find it illuminating to consider the case of a
switch with infinite storage. Such a packet switch can never run
of buffers. It can, however, still become congested. The meaning
congestion in an infinite-storage system is explored. We
the unexpected result that a datagram network with infinite storage
first-in-first-out queuing, at least two packet switches, and
finite packet lifetime will, under overload, drop all packets.
attacking the problem of congestion for the infinite-storage case,
discover new solutions applicable to switches with finite storage
Packet switching was first introduced in an era when computer
storage was several orders of magnitude more expensive than it
today. Strenuous efforts were made in the early days to build
switches with the absolute minimum of storage required for operation
The problem of congestion control was generally considered to be
of avoiding buffer exhaustion in the packet switches. We take
different view here. We choose to begin our analysis by assuming
availablity of infinite memory. This forces us to look at
from a fresh perspective. We no longer worry about when to block
which packets to discard; instead, we must think about how we
the system to perform
Pure datagram systems are especially prone to congestion problems
The blocking mechanisms provided by virtual circuit systems
absent. No fully effective solutions to congestion in pure
systems are known. Most existing datagram systems behave badly
overload. We will show that substantial progress can be made on
Nagle [Page 1]
RFC 970 December 1985
On Packet Switches With Infinite
congestion control problem even for pure datagram systems when
problem is defined as determining the order of packet transmission
rather than the allocation of buffer space
A Packet Switch with Infinite
Let us begin by describing a simple packet switch with
storage. A switch has incoming and outgoing links. Each link has
fixed data transfer rate. Not all links need have the same
rate. Packets arrive on incoming links and are immediately
an outgoing link by some routing mechanism not examined here.
outgoing link has a queue. Packets are removed from that queue
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
manner
We assume that packets have a finite lifetime. In the DoD
protocol, packets have a time-to-live field, which is the number
seconds remaining until the packet must be discarded
uninteresting. As the packet travels through the network, this
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
bound; when the queues become sufficiently long, packets will
out before being sent. This places an upper bound on the total
of all queues; this bound is determined by the total data rate
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
rate. The queue length for the outgoing link will then grow
the transit time through the queue exceeds the time-to-live of
incoming packets. At this point, as the process serving the
link removes packets from the queue, it will sometimes find a
whose time-to-live field has been decremented to zero. In such
case, it will discard that packet and will try again with the
packet on the queue. Packets with nonzero time-to-live fields
be transmitted on the outgoing link
The packets that do get transmitted have nonzero time-to-
values. But once the steady state under overload has been reached
these values will be small, since the packet will have been on
queue for slightly less than the maximum time-to-live. In fact,
Nagle [Page 2]
RFC 970 December 1985
On Packet Switches With Infinite
the departure rate is greater than one per time-to-live unit,
time-to-live of any forwarded packet will be exactly one.
follows from the observation that if more than one packet is sent
time-to-live unit, consecutive packets on the queue will
time-to-live values that differ by no more than 1. Thus, as
component of the packet switch that removes packets from the
and either sends them or discards them as expired operates, it
either find packets with negative or zero time to live values (
it will discard) or packets with values of 1, which it will send
So, clearly enough, at the next node of the packet switching system
the arriving packets will all have time-to-live values of 1.
we always decrement the time-to-live value by at least 1 in
node, to guarantee that the time-to-live value decreases as
packet travels through the network, we will in this case decrement
to zero for each incoming packet and will then discard that packet
We have thus shown that a datagram network with infinite storage
first-in-first-out queuing, and a finite packet lifetime will,
overload, drop all packets. This is a rather unexpected result.
it is quite real. It is not an artifact of the infinite-
assumption. The problem still occurs in networks with
storage, but the effects are less clearly seen. Datagram
are known to behave badly under overload, but analysis of
behavior has been lacking. In the infinite-buffer case, the
is quite simple, as we have shown, and we obtain considerable
into the problem
One would expect this phenomenon to have been discovered previously
But previous work on congestion control in packet switching
almost invariably focuses on buffer management. Analysis of
infinite buffer case is apparently unique with this writer
This result is directly applicable to networks with finite resources
The storage required to implement a switch that can never run out
buffers turns out to be quite reasonable. Let us consider a
datagram switch for an ARPANET-like network. For the case of
packet switch with four 56Kb links, and an upper bound on
time-to-live of 15 seconds, the maximum buffer space that could
be required is 420K bytes <1>. A switch provided with this
modest amount of memory need never drop a packet due to
exhaustion
This problem is not just theoretical. We have demonstrated
experimentally on our own network, using a supermini with
megabytes of memory as a switch. We now have experimental
that the phenomenon described above occurs in practice. Our
Nagle [Page 3]
RFC 970 December 1985
On Packet Switches With Infinite
experiment, using an Ethernet on one side of the switch and a 9600
baud line on the other, resulted in 916 IP datagrams queued in
switch at peak. However, we were applying the load over a
transport connection, and the transport connection timed out due
excessive round trip time before the queue reached the time to
limit, so we did not actually reach the stable state with the
at the maximum length as predicted by our analysis above. It
interesting that we can force this condition from the position of
user application atop the transport layer (TCP), and this
further analysis
Interaction with Transport
We have thus far assumed packet sources that emit packets at a
rate. This is a valid model for certain sources such as packet
systems. Systems that use transport protocols of the ISO TP4 or
TCP class, however, ought to be better behaved. The key point
that transport protocols used in datagram systems should behave
such a way as to not overload the network, even where the network
no means of keeping them from doing so. This is quite possible.
a previous paper by this writer [1], the behavior of the
transport protocol over a congested network is explored. We
shown that a badly behaved transport protocol implementation
cause serious harm to a datagram network, and discussed how such
implementation ought to behave. In that paper we offered
specific guidance on how to implement a well-behaved TCP,
demonstrated that proper behavior could in some cases reduce
load by an order of magnitude. In summary, the conclusions of
paper are that a transport protocol, to be well behaved, should
have a retransmit time shorter than the current round trip
between the hosts involved, and that when informed by the network
congestion, the transport protocol should take steps to reduce
number of packets outstanding on the connection
We reference our earlier work here to show that the network
imposed by a transport protocol is not necessarily fixed by
protocol specification. Some existing implementations of
protocols are well-behaved. Others are not. We have observed a
variability among existing TCP implementations. We have reason
suspect that ISO TP4 implementations will be more uniform, given
greater rigidity of the specification, but we see enough open
in the TP4 standard to allow for considerable variability.
suspect that there will be marginal TP4 implementations, from
network viewpoint, just as there are marginal TCP
today. These implementations will typically work quite well
asked to operate over a heavily loaded network with
delays. Then we find out which ones are well-behaved
Nagle [Page 4]
RFC 970 December 1985
On Packet Switches With Infinite
Even if all hosts are moderately well-behaved, there is potential
trouble. Each host can normally obtain more network bandwidth
transmitting more packets per unit time, since the first in,
out strategy gives the most resources to the sender of the
packets. But collectively, as the hosts overload the network,
throughput drops. As shown above, throughput may drop to zero
Thus, the optimal strategy for each host is strongly suboptimal
the network as a whole
Game Theoretic Aspects of Network
This game-theory view of datagram networks leads us to a
on the stability of multi-player games. Systems in which the
strategy for each player is suboptimal for all players are known
tend towards the suboptimal state. The well-known prisoner's
problem in game theory is an example of a system with this property
But a closer analogue is the tragedy of the commons problem
economics. Where each individual can improve their own position
using more of a free resource, but the total amount of the
degrades as the number of users increases, self-interest leads
overload of the resource and collapse. Historically this
was applied to the use of common grazing lands; it also applies
such diverse resources as air quality and time-sharing systems.
general, experience indicates that many-player systems with this
of instability tend to get into serious trouble
Solutions to the tragedy of the commons problem fall into
classes: cooperative, authoritarian, and market solutions
Cooperative solutions, where everyone agrees to be well-behaved,
adequate for small numbers of players, but tend to break down as
number of players increases. Authoritarian solutions are
when behavior can be easily monitored, but tend to fail if
definition of good behavior is subtle. A market solution is
only if the rules of the game can be changed so that the
strategy for players results in a situation that is optimal for all
Where this is possible, market solutions can be quite effective
The above analysis is generally valid for human players. In
network case, we have the interesting situation that the player is
computer executing a preprogrammed strategy. But this alone does
insure good behavior; the strategy in the computer may be
to optimize performance for that computer, regardless of
considerations. A similar situation exists with automatic
devices in telephony, where the user's equipment attempts to
performance over an overloaded network by rapidly redialing
calls. Since call-setup facilities are scarce resources in
systems, this can seriously impact the network; there are
Nagle [Page 5]
RFC 970 December 1985
On Packet Switches With Infinite
that have been forced to prohibit such devices. (Brazil, for one).
This solution by administrative fiat is sometimes effective
sometimes not, depending on the relative power of the
authority and the users
As transport protocols become more commercialized and
systems are available, we should expect to see attempts to tune
protocols in ways that may be optimal from the point of view of
single host but suboptimal from the point of view of the
network. We already see signs of this in the transport
implementation of one popular workstation manufacturer
So, to return to our analysis of a pure datagram internetwork,
authoritarian solution would order all hosts to be "well-behaved"
fiat; this might be difficult since the definition of a well-
host in terms of its externally observed behavior is subtle.
cooperative solution faces the same problem, along with the
additional problem of applying the requisite social pressures in
distributed system. A market solution requires that we make it
to be well-behaved. To do this, we will have to change the rules
the game
Fairness in Packet Switching
We would like to protect the network from hosts that are
well-behaved. More specifically, we would like, in the presence
both well-behaved and badly-behaved hosts, to insure
well-behaved hosts receive better service than badly-behaved hosts
We have devised a means of achieving this
Let us consider a network that consists of high-
pure-datagram local area networks without flow control (Ethernet
most IEEE 802.x datagram systems are of this class, whether based
carrier sensing or token passing), hosts connected to these
area networks, and an interconnected wide area network composed
packet switches and long-haul links. The wide area network may
internal flow control, but has no way of imposing mandatory
control on the source hosts. The DoD Internet, Xerox Network
internetworks, and the networks derived from them fit this model
If any host on a local area network generates packets routed to
wide area network at a rate greater than the wide area network
absorb them, congestion will result in the packet switch
the local and wide area networks. If the packet switches queue on
strictly first in, first out basis, the badly behaved host
interfere with the transmission of data by other, better-
hosts
Nagle [Page 6]
RFC 970 December 1985
On Packet Switches With Infinite
We introduce the concept of fairness. We would like to make
packet switches fair; in other words, each source host should be
to obtain an equal fraction of the resources of each packet switch
We can do this by replacing the single first in, first out
associated with each outgoing link with multiple queues, one for
source host in the entire network. We service these queues in
round- robin fashion, taking one packet from each non-empty queue
turn and transmitting the packets with positive time to live
on the associated outgoing link, while dropping the expired packets
Empty queues are skipped over and lose their turn
This mechanism is fair; outgoing link bandwidth is parcelled
equally amongst source hosts. Each source host with packets
in the switch for the specified outgoing link gets exactly one
sent on the outgoing link each time the round robin algorithm cycles
So we have implemented a form of load-balancing
We have also improved the system from a game theory point of view
The optimal strategy for a given host is no longer to send as
packets as possible. The optimal strategy is now to send packets
a rate that keeps exactly one packet waiting to be sent in
packet switch, since in this way the host will be serviced each
the round-robin algorithm cycles, and the host's packets
experience the minimum transit delay. This strategy is
acceptable from the network's point of view, since the length of
queue will in general be between 1 and 2.
The hosts need advisory information from the network to
their strategies. The existing Source Quench mechanism in DoD IP
while minimal, is sufficient to provide this. The packet
should send a Source Quench message to a source host whenever
number of packets in the queue for that source host exceeds
small value, probably 2. If the hosts act to keep their traffic
below the point at which Source Quench messages are received,
network should run with mean queue lengths below 2 for each host
Badly-behaved hosts can send all the datagrams they want, but
not thereby increase their share of the network resources. All
will happen is that packets from such hosts will experience
transit times through the network. A sufficiently badly-behaved
can send enough datagrams to push its own transit times up to
time to live limit, in which case none of its datagrams will
through. This effect will happen sooner with fair queuing than
first in, first out queuing, because the badly- behaved host
only obtain a share of the bandwidth inversely proportional to
number of hosts using the packet switch at the moment. This is
Nagle [Page 7]
RFC 970 December 1985
On Packet Switches With Infinite
less than the share it would have under the old system, where
verbose hosts obtained more bandwidth. This provides a
incentive for badly-behaved hosts to improve their behavior
It is worth noting that malicious, as opposed to
badly-behaved, hosts, can overload the network by using
different source addresses in their datagrams, thereby
a large number of different hosts and obtaining a larger share of
network bandwidth. This is an attack on the network; it is not
to happen by accident. It is thus a network security problem,
will not be discussed further here
Although we have made the packet switches fair, we have not
made the network as a whole fair. This is a weakness of
approach. The strategy outlined here is most applicable to a
switch at a choke point in a network, such as an entry node of a
area network or an internetwork gateway. As a strategy applicable
an intermediate node of a large packet switching network, where
packets from many hosts at different locations pass through
switch, it is less applicable. The writer does not claim that
approach described here is a complete solution to the problem
congestion in datagram networks. However, it presents a solution
a serious problem and a direction for future work on the
case
The problem of maintaining a separate queue for each source host
each outgoing link in each packet switch seems at first to
considerably to the complexity of the queuing mechanism in the
switches. There is some complexity involved, but the
are simpler than those required with, say, balanced binary trees
One simple implementation involves providing space for pointers
part of the header of each datagram buffer. The queue for
source host need only be singly linked, and the queue heads (
are the first buffer of each queue) need to be doubly linked so
we can delete an entire queue when it is empty. Thus, we need
pointers in each buffer. More elaborate strategies can be devised
speed up the process when the queues are long. But the
complexity is probably not justified in practice
Given a finite buffer supply, we may someday be faced with
exhaustion. In such a case, we should drop the packet at the end
the longest queue, since it is the one that would be
last. This, of course, is unfavorable to the host with the
datagrams in the network, which is in keeping with our goal
fairness
Nagle [Page 8]
RFC 970 December 1985
On Packet Switches With Infinite
By breaking away from packet switching's historical fixation
buffer management, we have achieved some new insights into
control in datagram systems and developed solutions for some
problems in real systems. We hope that others, given this
insight, will go on to make some real progress on the
datagram congestion problem
[1] Nagle, J. "Congestion Control in IP/TCP Internetworks",
Computer Communications Review, October 1984.
Editor's
<1> The buffer space required for just one 10Mb Ethernet with
upper bound on the time-to-live of 255 is 318 million bytes
Nagle [Page 9]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
