Feedback flow control, in conjunction with limited buffering in the network, inevitably leads to packet loss. Effective congestion control requires not only effective flow control but also a good retransmission strategy. We present a new retransmission strategy called SMART that combines the best features of the traditional go-back-n and selective-retransmit strategies. We show, first, that go-back-n retransmission with static window flow control leads to congestion collapse when the nominal load exceeds the link capacity. Second, we can avert congestion collapse by replacing go-back-n with SMART retransmission, even with static window flow control. Third, SMART retransmission, when combined with packet-pair rate-based flow control, performs extremely well, both when losses are due to buffer overflows and when losses are random.

This paper is a retrospective on the design of Xunet 2, one of the earliest functional wide-area asynchronous transfer mode (ATM) networks. Work on Xunet 2 began in 1989 and the network, consisting of experimental ATM switches, IP routers, and 45 Mb/s transmission lines, has been operational since October 1991. The network serves as a "laboratory without walls" for eight research groups across the United States. While Xunet 2 has only a small number of nodes, it was designed as a prototype of a nationwide ATM network. This paper reviews some of the design decisions and lessons learned in the project and points out the research directions motivated by this work, focusing on the areas of traffic management, ATM switch design, network control, and the implementation of an IP router.

The mean delay and throughput characteristics of various trunk queuing disciplines of the FIFO (first in, first out) and round-robin types for byte-stream data networks are investigated. It is shown that, under normal traffic, high-speed trunks substantially reduce queuing delays. Almost any queuing discipline will give acceptable delay if the backbone network is sufficiently faster than the access lines. In the absence of high-speed trunks, both the packet FIFO and the round-robin discipline can be augmented with a priority queue that expedites single-packet messages, which may carry network control signals or echoplex characters. In FIFO-type disciplines, the mean delays of messages that do not go through the priority queue depend on the overall message length distribution. A sprinkling of very long messages can significantly increase the mean delays of other messages. In disciplines of round-robin type, the mean delay of each message type is not affected by the presence of very long messages of other types.>

Expressions are derived for the mean message delay, as a function of message length, when data messages of different lengths arrive asynchronously at a trunk and are divided, as they come in, into packets of some maximum length. The packets of different messages are intermingled and are put onto the trunk either from a single first-in-first-out (FIFO) queue, or from a high-priority and a low-priority queue for single-packet and multiple-packet messages, respectively. The results are compared to the case in which messages enter service in order of arrival and each message is served to completion without interruption, so that the mean message delay is independent of message length.>

The performance is compared of first-in-first-out and round-robin packet service disciplines at the trunk nodes of byte-stream networks, including priority service for single-packet messages. Delay and throughput characteristics are surveyed as a function of traffic mix, packet size, traffic intensity, and the ratio of trunk speed to access line speed. Exact and approximate analyses are compared with the results of simulations. Under normal traffic conditions, most disciplines will give acceptable mean delay if the ratio of trunk speed to access line speed is sufficiently high. Under congestion, round-robin disciplines have better fairness properties than first-in-first-out disciplines, in that they protect well-behaved users against hogs.>

The throughput versus window-size behavior of the sliding window protocol is studied on a trunked byte-stream virtual circuit. For the case studied, the node service discipline is processor sharing, background traffic is Poisson with exponentially distributed message lengths, propagation times are a significant fraction of the total delay, and the channel error rate is negligible. Analytic models are compared to the results of simulation. For small windows, the throughput is controlled by the ratio of window size to roundtrip propagation time. For large windows, the throughput is controlled by the background traffic level, the number of hops, and the ratio of window size to background message length.>

Two simple models of queueing on anN \times Nspace-division packet switch are examined. The switch operates synchronously with fixed-length packets; during each time slot, packets may arrive on any inputs addressed to any outputs. Because packet arrivals to the switch are unscheduled, more than one packet may arrive for the same output during the same time slot, making queueing unavoidable. Mean queue lengths are always greater for queueing on inputs than for queueing on outputs, and the output queues saturate only as the utilization approaches unity. Input queues, on the other hand, saturate at a utilization that depends onN, but is approximately(2 -\sqrt{2}) = 0.586whenNis large. If output trunk utilization is the primary consideration, it is possible to slightly increase utilization of the output trunks-upto(1 - e^{-1}) = 0.632asN \rightarrow \infty-by dropping interfering packets at the end of each time slot, rather than storing them in the input queues. This improvement is possible, however, only when the utilization of the input trunks exceeds a second critical threshold-approximatelyln (1 +\sqrt{2}) = 0.881for largeN.