Buffer management schemes are needed in shared-memory packet switches to regulate the sharing of memory among different output port queues and among traffic classes with different loss priorities. Earlier, we proposed a single-priority scheme called dynamic threshold (DT), in which the maximum permissible queue length is proportional to the unused buffering in the switch. A queue whose length equals or exceeds the current threshold value may accept no new arrivals. We propose, analyze and simulate several ways of incorporating loss priorities into the DT scheme. The analysis models sources as deterministic fluids. We determine how each scheme allocates buffers among the competing ports and loss priority classes under overload conditions. We also note how this buffer allocation induces an allocation of bandwidth among the loss priority classes at each port. We find that minor variations in the DT control law can produce dramatically different resource allocations. Based on this study, we recommend the scheme we call OWA, which gives some buffers and bandwidth to every priority class at every port. Scheme OWA has tunable parameters, which we give rules of thumb for setting. Another scheme, called AWA, is also a good choice. It has an allocation philosophy more akin to strict priority and hence is not tunable.

We propose a novel buffer management scheme in order to regulate the individual queue lengths in a shared-memory switch. The primary motivations of our scheme are: (i) provide differentiated allocations to the queues sharing the memory, where the allocations are directly derived from the call admission control (CAC) parameters; (ii) allow for the co-existence of regulated and best-effort traffic achieving high buffer utilization without violating the guaranteed buffer allocations of the regulated connections; (iii) protect well-behaving connections that conform to their allocations from any misbehaviour in other traffic; and (iv) handle deviations in incoming traffic patterns, from the ones assumed by CAC, by distributing unavoidable losses in an equitable manner. The new scheme, which we call dynamic partitioning, achieves all these objectives, and constitutes a first example of a scheme that is highly efficient, derives its parameters directly from CAC, and is also very robust against misbehaviour. The scheme is simple to implement, and therefore amenable for deployment in current high-speed switches. We present the scheme in the context of ATM switches, together with cell level simulations for its validation.

There has been much interest in using active queue management in routers in order to protect users from connections that are not very responsive to congestion notification. An Internet draft recommends schemes based on random early detection for achieving these goals, to the extent that it is possible, in a system without "per-flow" state. However, a "stateless" system with first-in/first-out (FIFO) queueing is very much handicapped in the degree to which flow isolation and fairness can be achieved. Starting with the observation that a "stateless" system is but one extreme in a spectrum of design choices and that per-flow queueing for a large number of flows is possible, we present active queue management mechanisms that are tailored to provide a high degree of isolation and fairness for TCP connections in a gigabit IP router using per-flow queueing. We show that IP flow state in a router can be bounded if the scheduling discipline used has finite memory, and we investigate the performance implications of different buffer management strategies in such a system. We show that merely using per-flow scheduling is not sufficient to achieve effective isolation and fairness, and it must be combined with appropriate buffer management strategies.

In this paper, we investigate the extent to which fair queueing (and its variants), in conjunction with appropriately tailored buffer management schemes, can be used to achieve the following goals for TCP traffic: (1) alleviate the inherent unfairness of TCP towards connections with long round-trip times, (2) provide isolation when connections using different TCP versions share a bottleneck link (3) provide protection from TCP-unfriendly traffic sources (which might include TCP ACKs since they are not loss-responsive) and misbehaving users, (4) alleviate the effects of ACK compression in the presence of two-way traffic, (5) prevent users experiencing ACK loss (which causes their traffic to be bursty) from significantly affecting other connections, (6) provide low latency to interactive connections which share a bottleneck with "greedy" connections without reducing overall link utilization. The paper proposes new buffer management schemes to be used in conjunction with fair queueing, so as to achieve the above goals for TCP, and compares the performance of the proposed schemes to the performance obtained using random early detection (RED) for packet dropping.

In shared-memory packet switches, buffer management schemes can improve overall loss performance, as well as fairness, by regulating the sharing of memory among the different output port queues. Of the conventional schemes, static threshold (ST) is simple but does not adapt to changing traffic conditions, while pushout (PO) is highly adaptive but difficult to implement. We propose a novel scheme called dynamic threshold (DT) that combines the simplicity of ST and the adaptivity of PO. The key idea is that the maximum permissible length, for any individual queue at any instant of time, is proportional to the unused buffering in the switch. A queue whose length equals or exceeds the current threshold value may accept no more arrivals. An analysis of the DT algorithm shows that a small amount of buffer space is (intentionally) left unallocated, and that the remaining buffer space becomes equally distributed among the active output queues. We use computer simulation to compare the loss performance of DT, ST, and PO. DT control is shown to be more robust to uncertainties and changes in traffic conditions than ST control.

We study a multistage ATM switch in which shared-memory switching elements are arranged in a banyan topology. By "shared-memory," we mean that each switching element uses output queueing and shares its local cell buffer memory among all its output ports. We apply a buffer management technique called delayed pushout that was originally designed for multistage ATM switches with hierarchical topologies. Delayed pushout combines a pushout mechanism, for sharing memory efficiently among queues within the same switching element, and a backpressure mechanism, for sharing memory across switch stages. The backpressure component has a threshold to restrict the amount of sharing between stages. A synergy emerges when pushout, backpressure, and this threshold are all employed together. Using a computer simulation of the switch under bursty traffic, we study delayed pushout as well as several simpler pushout and backpressure schemes under a variety of traffic conditions. Of the five schemes we simulate, delayed pushout is the only one that performs well under all load conditions.

We study a multistage hierarchical asynchronous transfer mode (ATM) switch in which each switching element has its own local cell buffer memory that is shared among all its output ports. We propose a novel buffer management technique called delayed pushout that combines a pushout mechanism (for sharing memory efficiently among queues within the same switching element) and a backpressure mechanism (for sharing memory across switch stages). The backpressure component has a threshold to restrict the amount of sharing between stages. A synergy emerges when pushout, backpressure, and this threshold are all employed together. Using a computer simulation of the switch under symmetric but bursty traffic, we study delayed pushout as well as several simpler pushout and backpressure schemes under a wide range of loads. At every load level, we find that the delayed pushout scheme has a lower cell loss rate than its competitors. Finally, we show how delayed pushout can be extended to share buffer space between traffic classes with different space priorities.

Buffer management schemes are needed to fairly regulate the sharing of memory among different output port queues in a shared memory ATM switch. Of the conventional schemes, static threshold is simple but does not adapt to changing traffic conditions while pushout is efficient and adaptive but difficult to implement. We propose a novel scheme called dynamic threshold which combines the simplicity of static threshold and the adaptability of pushout. The key idea is that the maximum permissible length, for any individual queue at any instant of time, is proportional to the unused buffering in the switch. A queue whose length equals or exceeds the current threshold value may accept no more new cells. The dynamic threshold procedure presented improves the fairness and switch efficiency by guaranteeing access to the buffer space for all output queues. Computer simulation is used to compare the loss performance of the dynamic threshold technique with that of static threshold and pushout. The dynamic threshold scheme is shown to be a good compromise: while nearly as simple as static threshold control, it offers most of the performance benefits of pushout. Like pushout, the dynamic threshold method is adaptive, so it is more robust to uncertainties and changes in traffic conditions than, static threshold control.

We study a multistage ATM switch in which shared-memory switching elements are arranged in a banyan topology. By "shared memory", we mean that each switching element uses output queueing and shares its local cell buffer memory among all its output ports. We apply a buffer management technique called delayed pushout that was originally designed for multistage ATM switches with hierarchical topologies. Delayed pushout combines a pushout mechanism, for sharing memory efficiently among queues within the same switching element, and a backpressure mechanism, for sharing memory across switch stages. The backpressure component has a threshold to restrict the amount of sharing between stages. A synergy emerges when pushout, backpressure, and this threshold are all employed together. Using a computer simulation of the switch under bursty traffic, we study delayed pushout as well as several simpler pushout and backpressure schemes under a variety of traffic conditions. Of the five schemes we simulate, delayed pushout is the only one that performs well under all load conditions.

Studies a multistage hierarchical ATM switch in which each switching component has its own local cell buffer memory that is shared among all its output ports. The authors propose a novel buffer management technique called "delayed pushout" that combines a pushout mechanism, for sharing memory efficiently among queues within the same switching component, and a backpressure mechanism, for sharing memory across switch stages. The backpressure component has a threshold to restrict the amount of sharing between stages. A synergy emerges when pushout, backpressure, and this threshold are all employed together. Using a computer simulation of the switch under bursty traffic, the authors study delayed pushout as well as several simpler pushout and backpressure schemes under a wide range of loads. At every load level, they find that the delayed pushout scheme has a lower cell loss rate than its competitors. Finally, they show how delayed pushout can be extended to share buffer space between traffic classes with different space priorities.>

Regular two-dimensional architectures are being considered as alternatives to the linear topology metropolitan area networks (MANs) that are popular today. Deflection routing is an adaptive routing strategy that performs well on such architectures. A general analytic model has been developed to study the performance of buffered deflection routing in regular networks. The Manhattan street network, the ShuffleNet, and the shuffle exchange network have been studied as candidate two-connected networks with different topological characteristics. The results show that deflection routing performs well on both the Manhattan street network and the ShuffleNet, even under heavy loads, while on the shuffle exchange network it does not perform as well. The introduction of just a few buffers provides significant improvement in the delay-throughput performance over unbuffered deflection routing, especially in networks with large propagation delays. The analytic results are found to match the simulations very closely in most cases.>

It is explained why long distributed queue dual bus (DQDB) networks without bandwidth balancing can have fairness problems when several nodes are performing large file transfers. The problems arise because the network control information is subject to propagation delays that are much longer than the transmission time of a data segment. Bandwidth balancing is then presented as a simple solution. By constraining each node to take only a certain fraction of the transmission opportunities offered to it by the basic DQDB protocol, bandwidth balancing gradually achieves a fair allocation of bandwidth among simultaneous file transfers. Two ways to extend this procedure effectively to multipriority traffic are proposed.>

The fairness problems suffered by distributed-queue-dual-bus (DQDB) networks that span metropolitan areas are examined in detail. The problems arise because the network control information is subject to propagation delays that are much longer than the transmission time of a data segment. A rate control procedure is proposed that requires only a minor modification of the current DQDB protocol. In order to guarantee that a node acquires only 90% of the available slots, every time it inserts nine data segments into its local queue it inserts one extra request slot into its transmission queue. This lets an extra idle slot go by that was not requested by any downstream node.>