Throughput analysis for input-buffered ATM switches with multipleFIFO queues per input port

Using two different packet scheduling policies, the maximum throughputs of an input-buffered ATM switch with m-FIFO queues per input port are derived when the switch size is large     

Analysis of nonblocking ATM switches with multiple input queues

An analytical model for the performance analysis of a multiple input queued asynchronous transfer mode (ATM) switch is presented. The interconnection network of the ATM switch is internally nonblocking and each input port maintains a separate queue of cells for each output port. The switch uses parallel iterative matching (PIM) to find the maximal matching between the input and output ports of the switch. A closed-form solution for the maximum throughput of the switch under saturated conditions is derived. It is found that the maximum throughput of the switch exceeds 99% with just four iterations of the PIM algorithm. Using the tagged input queue approach, an analytical model for evaluating the switch performance under an independent identically distributed Bernoulli traffic with the cell destinations uniformly distributed over all output ports is developed. The switch throughput, mean cell delay, and cell loss probability are computed from the analytical model. The accuracy of the analytical model is verified using simulation     

Throughput analysis and optimal design of Banyan switches withbypass queues

A Banyan switch with bypass queue can overcome the problem of head of line blocking. This paper presents the throughput analysis for such a switch and the optimal window size for the bypass queue is also obtained. Moreover, to reduce the effect of the internal blocking and to increase the throughput, a parallel Banyan switch with bypass queue is also discussed and analyzed     

Two-dimensional round-robin schedulers for packet switches withmultiple input queues

Presents a new scheduler, the two-dimensional round-robin (2DRR) scheduler, that provides high throughput and fair access in a packet switch that uses multiple input queues. We consider an architecture in which each input port maintains a separate queue for each output. In an N×N switch, our scheduler determines which of the queues in the total of N² input queues are served during each time slot. We demonstrate the fairness properties of the 2DRR scheduler and compare its performance with that of the input and output queueing configurations, showing that our scheme achieves the same saturation throughput as output queueing. The 2DRR scheduler can be implemented using simple logic components, thereby allowing a very high-speed implementation     

FIRM: high-speed distributed scheduling for ATM switches withmultiple input queues

A new distributed scheduling algorithm for advanced input queueing switch architectures called FIRM is introduced. FIRM provides improved performance characteristics at high load compared to the most efficient alternative, improved fairness, and tighter service guarantees     

Burst-based scheduling algorithms for non-blocking ATM switcheswith multiple input queues

This letter quantitatively evaluates two alternative approaches to the scheduling of traffic streams in a high-speed ATM switch with multiple input queues. Specifically, we compare a previously proposed algorithm, called parallel iterative matching (PIM)-which is a cell-based scheduling algorithm-with our newly proposed algorithm-which is a burst-based variation of the PIM scheduling algorithm. Extensive simulation results demonstrate that burst-based PIM scheduling outperforms cell-based PIM scheduling under a variety of realistic parameters     

On the stability of local scheduling policies in networks of packet switches with input queues

A significant research effort has been devoted to the design of simple and efficient scheduling policies for input queued (IQ) and combined input-output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on maximum weight matching (MWM) were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible arrival process satisfying the strong law of large number. On the contrary, it has been shown that the usual MWM policies fail to guarantee 100% throughput in networks of interconnected IQ/CIOQ switches. Hence, new policies suited for networks of interconnected switches were proposed and proved to achieve 100% throughput. All of these new policies require coordination and cooperation among different switches. We identify scheduling policies that require no coordination among switches (and are, thus, said to be local), and that guarantee 100% throughput in a network of IQ/CIOQ switches. The only assumptions on the input traffic pattern are that it is stationary, satisfies the strong law of large numbers and does not oversubscribe any link in the network.     

Write policies for multicast ATM switches

A unicast and multicast-pushout write policy for shared-memory ATM switches is proposed. The scheme allocates buffers based on the service rates of unicast and multicast cells to ensure that maximum throughput can be maintained     

Throughput analysis of bifurcated input-queued packet switches withrestricted contention

An input-queueing scheme is suggested in which a buffer is divided into several smaller buffer blocks for enhancement of the limited throughput of the ordinary input-queued switch. The scheme is analysed and compared with respect to the performance of the scheme with free contention     

Wide-sense non-blocking multicast ATM switches

Non-blocking multicast ATM switches can simplify the call admission control process and increase the utilisation level of external links. The condition for wide-sense non-blocking multicast ATM switches is derived and the routing algorithm is proposed. The required number of middle switches for the wide-sense non-blocking multicast switch is significantly less than that of the strictly non-blocking multicast switch     

Performance of shared-memory switches under multicast burstytraffic

We study shared-memory switches under multicast bursty traffic and characterize the relation between their performance and the multicast distribution that defines the mix of multicast traffic arriving at the switches. We consider two schemes that have been used in practical realizations of these switches to replicate multicast cells: (1) replication-at-receiving (RAR), where multiple copies of a multicast cell are stored in the buffer and served independently, and (2) replication-at-sending (RAS), where a single instance of a multicast cell is stored in the buffer, and the cell is replicated as it is transmitted to the output ports. For each scheme, we study two configurations: (1) the shared-memory-only (SMO) configuration, where the bandwidth of the replication mechanism is sufficient to accommodate even the worst-case replication requirements, and (2) the shared-memory-with-replication-first-in-first-out (SM+RFIFO) configuration, where the bandwidth of the replication mechanism is lower than that required by the worst case, and thus an additional buffer is used in front of the shared memory to temporarily store cells while they are replicated. For all cases, using simulation, we find upper bounds for the buffer requirements to achieve a desired cell-loss rate. We show that these upper bounds are significantly larger than the buffer requirements under unicast traffic and are approached even for very small volumes of multicast traffic; thus, these upper bounds should be used in practice to size the buffers to achieve the desired performance under traffic with general multicast distributions. We also study shared-memory switches with output demultiplexers and characterize and compare the different multicasting schemes that are used in these switches     

Optimum architecture for input queuing ATM switches

An input queueing ATM switch architecture employing the contention resolution called 'scheduling algorithm' is described. A high efficiency of over 90% can be achieved without any considerable increase in the amount of hardware or contention control speed.<>     

Design of wide-sense nonblocking multicast ATM switches

Nonblocking multicast asynchronous transfer mode (ATM) switches can simplify the call admission control process and increase the external links' utilization. We derive the wide-sense nonblocking condition for multicast ATM switches based on a general Clos network. We also propose a routing algorithm to achieve wide-sense nonblocking. It is illustrated by an example that the number of required middle stages in our switch is significantly less than that of strictly nonblocking multicast switches     

Queueing analysis of scheduling policies in copy networks ofspace-based multicast packet switches

Space-based multicast switches use copy networks to generate the copies requested by the input packets. In this paper our interest is in the multicast switch proposed by Lee (1988). The order in which the copy requests of the input ports are served is determined by the copy scheduling policy and this plays a major part in defining the performance characteristics of a multicast switch. In any slot, the sum of the number of copies requested by the active inputs of the copy network may exceed the number of output ports and some of the copy requests may need to be dropped or buffered. We first propose an exact model to calculate the overflow probabilities in an unbuffered Lee's copy network. Our exact results improve upon the Chernoff bounds on the overflow probability given by Lee by a factor of more than 10. Next, we consider buffered inputs and propose queueing models for the copy network for three scheduling policies: cyclic service of the input ports with and without fanout splitting of copy requests and acyclic service without fanout splitting. These queueing models obtain the average delay experienced by the copy requests. We also obtain the sustainable throughput of a copy network, the maximum load that can be applied to all the input ports without causing an unstable queue at any of the inputs, for the scheduling policies mentioned above     

A novel framework of online network coding for multicast switches with constrained buffers

Network coding is able to address output conflicts when fanout splitting is allowed for multicast switching. Hence, it successfully achieves a larger rate region than non-coding approaches in crossbar switches. However, network coding requires large coding buffers and a high computational cost on encoding and decoding. In this paper, we propose a novel Online Network Coding framework called Online NC for multicast switches, which is adaptive to constrained buffers. Moreover, it enjoys a much lower decoding complexity O(n ²) by a Vandermonde matrix based approach, as compared to conventional randomized network coding O(n ³). Our approach realizes online coding with one coding algorithm that synchronizes buffering and coding. Therefore, we significantly reduce requirements on buffer space, while also sustaining high throughputs. We confirm the superior advantages of our contributions using empirical studies.     

Self-firing cell scheduler for input queueing ATM switches

The authors propose a simple cell scheduler for input queueing ATM switches. The proposed self-firing cell scheduler consists of N² processing elements connected by a two dimensional torus network, where each processing element can determine the diagonal by itself in a distributed manner. It allows a simple implementation for high speed ATM switches     

Scheduling of multicast traffic in high-capacity packet switches

Switches with input buffers are scalable due to their simplicity. In these switches, the port that sources a multicast session might easily get congested as it becomes more popular. We propose that destination ports should forward copies of multicast packets to other destination ports in a specified order. In this way, the multicast traffic load is evenly distributed over the switch ports. Packets are scheduled according to the weighted sequential greedy algorithm.     

Scalable reliable multicast using multiple multicast channels

We examine an approach for providing reliable, scalable multicast communication, involving the use of multiple multicast channels for reducing receiver processing costs and reducing network bandwidth consumption in a multicast session. In this approach a single multicast channel is used for the original transmission of packets. Retransmissions of packets are done on separate multicast channels, which receivers dynamically join and leave. We first show that protocols using an infinite number of multicast channels incur much less processing overhead at the receivers compared to protocols that use only a single multicast channel. This is due to the fact that receivers do not receive retransmissions of packets they have already received correctly. Next, we derive the number of unwanted redundant packets at a receiver due to using only a finite number of multicast channels, for a specific negative acknowledgment (NAK)-based protocol. We then explore the minimum number of multicast channels required to keep the cost of processing unwanted packets to a sufficiently low value. For an application consisting of a single sender transmitting reliably to many receivers we find that only a small number of multicast channels are required for a wide range of system parameters. In the case of an application where all participants simultaneously act as both senders and receivers a moderate number of multicast channels is needed. Finally, we present two mechanisms for implementing multiple multicast channels, one using multiple IP multicast groups and the other using additional router support for selective packet forwarding. We discuss the impact of both mechanisms on performance in terms of end-host and network resources     

A high-performance input access scheme for ATM multicast switching

In this paper, we propose an input access scheme for input-queued ATM multicast switches, achieving high system throughput, low packet delay and packet loss probability. Multicast and unicast packets of each input port are separately queued. Multicast queues take priority over the unicast queues, and both types of queues are fairly served in a cyclic-priority access discipline. In particular, each unicast queue is handled on a window-service basis, and each multicast packet is switched in a one-shot scheduling manner. To evaluate the performance of the access scheme, we propose an approximate analysis based on a simplified cyclic-priority model for anN×N finite-buffer multicast switch possessing Bernoulli multicast and unicast arrivals, with window-service (for unicasting) and one-shot scheduling (for multicasting) both taken into account. Finally, we show simulation results to demonstrate the accuracy of the approximate analysis and the superiority of the scheme over existing schemes with respect to normalized system throughput, mean packet delay, and packet loss probability.An earlier version of this paper appeared in IEEE ICC'96.     

Equalizers for multiple input/multiple output channels and PAMsystems with cyclostationary input sequences

The author studies minimum mean square error (MMSE) linear and decision feedback (DF) equalisers for multiple input/multiple output (MIMO) communication systems with intersymbol interference (ISI) and wide-sense stationary (WSS) inputs. To derive these equalizers, one works in the D-transform domain and uses prediction theory results. Partial-response MMSE equalizers are also found. As an application, the author considers a pulse amplitude modulation (PAM) communication system with ISI and cyclostationary inputs. The MMSE linear and DF equalizers are determined by studying an equivalent MIMO system. The resulting filters are expressed in compact matrix notation and are time-invariant, whereas the corresponding single input/single output filters are periodically time-invariant. The author also considers MMSE equalizers for a wide-sense stationary process by introducing a `random phase'. To aid in the performance evaluation of various equalizers, the author derives their mean square errors