rfc970.txt

RFC 相关的技术文档

   general, experience indicates that many-player systems with this type
   of instability tend to get into serious trouble.

   Solutions to the tragedy of the commons problem fall into three
   classes: cooperative, authoritarian, and market solutions.
   Cooperative solutions, where everyone agrees to be well-behaved, are
   adequate for small numbers of players, but tend to break down as the
   number of players increases.  Authoritarian solutions are effective
   when behavior can be easily monitored, but tend to fail if the
   definition of good behavior is subtle.  A market solution is possible
   only if the rules of the game can be changed so that the optimal
   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 the
   network case, we have the interesting situation that the player is a
   computer executing a preprogrammed strategy.  But this alone does not
   insure good behavior; the strategy in the computer may be programmed
   to optimize performance for that computer, regardless of network
   considerations.  A similar situation exists with automatic redialing
   devices in telephony, where the user's equipment attempts to improve
   performance over an overloaded network by rapidly redialing failed
   calls.  Since call-setup facilities are scarce resources in telephone
   systems, this can seriously impact the network; there are countries


Nagle                                                           [Page 5]



RFC 970                                                    December 1985
On Packet Switches With Infinite Storage


   that have been forced to prohibit such devices.  (Brazil, for one).
   This solution by administrative fiat is sometimes effective and
   sometimes not, depending on the relative power of the administrative
   authority and the users.

   As transport protocols become more commercialized and competing
   systems are available, we should expect to see attempts to tune the
   protocols in ways that may be optimal from the point of view of a
   single host but suboptimal from the point of view of the entire
   network.  We already see signs of this in the transport protocol
   implementation of one popular workstation manufacturer.

   So, to return to our analysis of a pure datagram internetwork, an
   authoritarian solution would order all hosts to be "well-behaved" by
   fiat; this might be difficult since the definition of a well-behaved
   host in terms of its externally observed behavior is subtle.  A
   cooperative solution faces the same problem, along with the difficult
   additional problem of applying the requisite social pressures in a
   distributed system.  A market solution requires that we make it pay
   to be well-behaved.  To do this, we will have to change the rules of
   the game.

Fairness in Packet Switching Systems

   We would like to protect the network from hosts that are not
   well-behaved.  More specifically, we would like, in the presence of
   both well-behaved and badly-behaved hosts, to insure that
   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-bandwidth
   pure-datagram local area networks without flow control (Ethernet and
   most IEEE 802.x datagram systems are of this class, whether based on
   carrier sensing or token passing), hosts connected to these local
   area networks, and an interconnected wide area network composed of
   packet switches and long-haul links.  The wide area network may have
   internal flow control, but has no way of imposing mandatory flow
   control on the source hosts.  The DoD Internet, Xerox Network Systems
   internetworks, and the networks derived from them fit this model.

   If any host on a local area network generates packets routed to the
   wide area network at a rate greater than the wide area network can
   absorb them, congestion will result in the packet switch connecting
   the local and wide area networks.  If the packet switches queue on a
   strictly first in, first out basis, the badly behaved host will
   interfere with the transmission of data by other, better-behaved
   hosts.


Nagle                                                           [Page 6]



RFC 970                                                    December 1985
On Packet Switches With Infinite Storage


   We introduce the concept of fairness.  We would like to make our
   packet switches fair; in other words, each source host should be able
   to obtain an equal fraction of the resources of each packet switch.
   We can do this by replacing the single first in, first out queue
   associated with each outgoing link with multiple queues, one for each
   source host in the entire network. We service these queues in a
   round- robin fashion, taking one packet from each non-empty queue in
   turn and transmitting the packets with positive time to live values
   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 out
   equally amongst source hosts.  Each source host with packets queued
   in the switch for the specified outgoing link gets exactly one packet
   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 many
   packets as possible.  The optimal strategy is now to send packets at
   a rate that keeps exactly one packet waiting to be sent in each
   packet switch, since in this way the host will be serviced each time
   the round-robin algorithm cycles, and the host's packets will
   experience the minimum transit delay.  This strategy is quite
   acceptable from the network's point of view, since the length of each
   queue will in general be between 1 and 2.

   The hosts need advisory information from the network to optimize
   their strategies.  The existing Source Quench mechanism in DoD IP,
   while minimal, is sufficient to provide this.  The packet switches
   should send a Source Quench message to a source host whenever the
   number of packets in the queue for that source host exceeds some
   small value, probably 2.  If the hosts act to keep their traffic just
   below the point at which Source Quench messages are received, the
   network should run with mean queue lengths below 2 for each host.

   Badly-behaved hosts can send all the datagrams they want, but will
   not thereby increase their share of the network resources.  All that
   will happen is that packets from such hosts will experience long
   transit times through the network.  A sufficiently badly-behaved host
   can send enough datagrams to push its own transit times up to the
   time to live limit, in which case none of its datagrams will get
   through.  This effect will happen sooner with fair queuing than with
   first in, first out queuing, because the badly- behaved host will
   only obtain a share of the bandwidth inversely proportional to the
   number of hosts using the packet switch at the moment.  This is much



Nagle                                                           [Page 7]



RFC 970                                                    December 1985
On Packet Switches With Infinite Storage


   less than the share it would have under the old system, where more
   verbose hosts obtained more bandwidth.  This provides a strong
   incentive for badly-behaved hosts to improve their behavior.

   It is worth noting that malicious, as opposed to merely
   badly-behaved, hosts, can overload the network by using many
   different source addresses in their datagrams, thereby impersonating
   a large number of different hosts and obtaining a larger share of the
   network bandwidth. This is an attack on the network; it is not likely
   to happen by accident. It is thus a network security problem, and
   will not be discussed further here.

   Although we have made the packet switches fair, we have not thereby
   made the network as a whole fair.  This is a weakness of our
   approach. The strategy outlined here is most applicable to a packet
   switch at a choke point in a network, such as an entry node of a wide
   area network or an internetwork gateway.  As a strategy applicable to
   an intermediate node of a large packet switching network, where the
   packets from many hosts at different locations pass through the
   switch, it is less applicable.  The writer does not claim that the
   approach described here is a complete solution to the problem of
   congestion in datagram networks.  However, it presents a solution to
   a serious problem and a direction for future work on the general
   case.

Implementation

   The problem of maintaining a separate queue for each source host for
   each outgoing link in each packet switch seems at first to add
   considerably to the complexity of the queuing mechanism in the packet
   switches.  There is some complexity involved, but the manipulations
   are simpler than those required with, say, balanced binary trees.
   One simple implementation involves providing space for pointers as
   part of the header of each datagram buffer.  The queue for each
   source host need only be singly linked, and the queue heads (which
   are the first buffer of each queue) need to be doubly linked so that
   we can delete an entire queue when it is empty.  Thus, we need three
   pointers in each buffer.  More elaborate strategies can be devised to
   speed up the process when the queues are long.  But the additional
   complexity is probably not justified in practice.

   Given a finite buffer supply, we may someday be faced with buffer
   exhaustion.  In such a case, we should drop the packet at the end of
   the longest queue, since it is the one that would be transmitted
   last. This, of course, is unfavorable to the host with the most
   datagrams in the network, which is in keeping with our goal of
   fairness.


Nagle                                                           [Page 8]



RFC 970                                                    December 1985
On Packet Switches With Infinite Storage


Conclusion

   By breaking away from packet switching's historical fixation on
   buffer management, we have achieved some new insights into congestion
   control in datagram systems and developed solutions for some known
   problems in real systems. We hope that others, given this new
   insight, will go on to make some real progress on the general
   datagram congestion problem.

References

   [1]  Nagle, J. "Congestion Control in IP/TCP Internetworks", ACM
        Computer Communications Review, October 1984.

Editor's Notes

   <1>  The buffer space required for just one 10Mb Ethernet with an
        upper bound on the time-to-live of 255 is 318 million bytes.































Nagle                                                           [Page 9]