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 consider buffer management policies for shared memory packet switches supporting Quality of Service (QoS). There are two interesting dimensions in which the setting may different. The first is the packet size, whether all the packets of the same fixed size or do packets have variable length. The second is the value of the packets, do all the packets have the same value or do different packets have different values.

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.

This paper introduces the multiaccess mesh (or multimesh) network. Stations are arranged in a two-dimensional (2-D) mesh in which each row and column functions as a conventional linear local-area network (LAN) or metropolitan-area network (MAN) subnetwork. Full connectivity is achieved by enabling stations to merge their row and column subnetworks, under the coordination of a merge control protocol. A two-dimensional token-passing protocol is considered, and a more complex protocol motivated by max-min fairness is also presented. Like conventional LANs and MANs, the multimesh requires no transit routing or store-and-forward buffering. The multimesh is a generalization of the token grid network. Using analysis and simulation, we study the capacity of multimeshes constructed of token rings and slotted rings, under uniform and nonuniform loads. A multimesh can support much higher throughput than conventional linear LAN and MAN networks with the same transmission hardware. Moreover, the multimesh capacity grows with the number of stations, We also present a healing mechanism that ensures full network connectivity regardless of the number of failed stations.

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.>

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.>

Bandwidth balancing is a procedure that gradually achieves a fair allocation of bandwidth among simultaneous file transfers on a distributed-queue dual-bus (DQDB) network. Bandwidth balancing was originally designed for traffic of a single priority level. Three ways are demonstrated to extend this procedure to multi-priority traffic.>

The author studies a simple strategy, proposed independently by E.L. Hahne and R.G. Gallager (1986) and M.G.H. Katevenis (1987), for fairly allocating link capacity in a point-to-point packet network with virtual circuit routing. Each link offers its packet transmission slots to its user sessions by polling them in round-robin order. In addition, window flow control is used to prevent excessive packet queues at the network nodes. As the window size increases, the session throughput rates are shown to approach limits that are perfectly fair in the max-min sense. If each session has periodic input (perhaps with jitter) or has such heavy demand that packets are always waiting to enter the network, then a finite window size suffices to produce perfectly fair throughput rates. The results suggest that the transmission capacity not used by the small window session will be approximately fairly divided among the large window sessions. The focus is on the worst-case performance of round-robin scheduling with windows.>

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.>