Performance analysis of nonblocking packet switch with input andoutput buffers

The performance of nonblocking packet switches such as the knockout switch and Batcher banyan switch for high-speed communication networks can be improved as the switching capacity L per output increases; the switching capacity per output refers to the maximum number of packets transferred to an output during a slot. The N×N switch with L=N was shown to attain the best possible performance by M.J. Karol et al. (1987). Here a N×N nonblocking packet switch with input and output buffers is analyzed for an arbitrary number of L such that 1⩽L⩽N. The maximum throughput and packet loss probability at input are obtained when N=∞     

On the performance of an ATM switch with multichannel transmissiongroups

A routing architecture applying the concept of multichannel transmission groups (MCTGs) for ATM systems is proposed. A queuing analysis of an internally nonblocking ATM switch employing this MCTG concept with partially shared output buffers is presented. The analysis is based on the discrete-time DA///D/c /B queuing model. Both bulk input traffic bulk-size distribution (A) and deterministic traffic (D₁ +. . .+D_N) are considered. The impact of switch speedup on the performance is also taken into account. It is shown that the MCTG architecture yields better performance in terms of delay and cell loss probability than its single channel counterpart. It is also found that the switch speedup required to closely approximate the optimal performance obtained by having the switch fabric run N times as fast as the input and output channels, where N is the size of the switch, is rather small compared to N. This makes the practical realization of the proposed switch architecture feasible     

A photonic knockout switch for high-speed packet networks

A high-performance packet switch is discussed which uses a photonic interconnect fabric to route very-wideband data packets from input to output. Packet contention is accomplished using a much slower electronic controller, based on the knockout principle operating in parallel with the optical interconnect. Specifically, the use of a wavelength-division-multiplex fabric whereby high-speed (2-4 Gb/s) packets are regenerated before modulating a single-frequency laser at each switch input. The optical signals from various inputs are summed in a star coupler and then broadcast to the different coupler outputs. Each coupler is equipped with a small number (L) of tunable receivers arranged in a parallel manner, each preceded by a power splitter so that up to L simultaneous packets can be received by each output. The L packets so received are stored in an L-input one-output first-in first-out (FIFO) buffer so that the FIFO packet sequence is always guaranteed. Not only does this architecture achieve the best delay-throughput performance, but, remarkably, modularity is such that the optical complexity grows linearly with the number of switch ports./     

Markov-modulated flow model for the output queues of a packetswitch

The output queues of an M×N packet switch are studied using a Markov-modulated flow model. The switching element is a central server which sequentially routes packets from the inputs to the outputs. The focus is on systems in which the server speed is such that the bulk of the queuing takes place in the output queues. The conventional point process approach neglects the impact of switching and transmission time. An attempt is made to account for these finite system speeds by using a Markov-modulated continuous flow to approximate the arrival process to an output queue. This model captures the dependency between arrivals at different outputs and reflects the fact that packet arrivals and departures are not instantaneous. The output queue content distribution is obtained, for both infinite and finite buffer systems, from the spectral expansion of the solution of a system of differential equations. Numerical examples and comparisons with the results of an M/M/1 approximation are presented     

Nonblocking property of reverse banyan networks

The authors present a new nonblocking property of the reverse banyan network under a particular input packet pattern at the input ports. The reverse banyan network is the mirror image of the banyan network. If the input packets of the N×N reverse banyan network have consecutive output address as modulo N, then the reverse banyan network is nonblocking. The routing of packets in the reverse banyan network is described, and the nonblocking property of the reverse banyan network is proved. A possible application of this property in the switching network is discussed     

Performance trade-offs in input/output buffer design for a non-blocking space-division packet switch

Performance trade-offs in buffer architecture design for a space-division packet switching system is studied. As described in Figure 1, the system is constructed by a non-blocking switch fabric and input/output buffers. The capacity of the non-blocking switch fabric is defined by the maximum number of packets, denoted by m, which can be simultaneously routed from multiple inputs to each output. The buffer size at each input is considered to be finite, equal to K. The emphasis here is placed on the input packet loss probability for systems constructed by different ms and Ks. From the performance point of view, we conclude:

• (a) choosing m = 3 or 4 is sufficient to exploit the maximum utilization of a non-blocking switch fabric
• (b) introducing input buffers of moderate size K significantly reduces the packet loss probability.

     

A self-routing multistage switching network for broadband ISDN

A switching network that approaches a maximum throughput of 100% as buffering is increased is proposed. This self-routing switching network consists of simple 2×2 switching elements, distributors, and buffers located between stages and in the output ports. The proposed switching requires a speedup factor of two. The structure and the operation of the switching network are described, and its performance is analyzed. The switch has log₂N stages that move packets in a store-and-forward fashion, incurring a latency of log₂ N time periods. The performance analysis of the switch under uniform traffic pattern shows that the additional delay is small, and a maximum throughput of 100% is achieved as buffering is increased     

Performance of the go-back-∞ protocol under correlated packetloses

The go-back-∞ protocol is studied under a two-state Markov chain packet-loss model, where the delay for packet acknowledgements is random. Expressions are presented for the z transform, mean, and variance of the time τ taken to successfully transmit N packets. In addition, the authors discuss how the probability distribution of the delay for packet acknowledgements can affect E |τ|     

Asymptotically optimal design of congestion control for high speeddata networks

The basic mechanism of sliding windows for the congestion control of virtual circuits is examined. A problem concerning the optimal design of windows is formulated and formulas for basic quantities of interest, such as throughput, delay and moments of packet queues, in the optimal operating regime as well as in other regimes, are obtained. All results are asymptotic, in which the main parameter is λ, the delay-bandwidth product. It is shown that K*~λ+O(√λ), where K* is the optimum window size. Also, in the optimal operating regime, the steady-state mean and standard deviation of the queued packets at individual nodes O(√/λ). The design consequences are examined in the contexts of adaptive dynamic windowing, buffer sizing, and shared versus separate buffers in the case of multiple virtual circuits     

Performance of a packet switch with crossbar architecture

A packet having a crossbar architecture with M inputs and N outputs is considered. Following earlier work, the theoretical capacity of such a switch is found in terms of the throughput of a closed queueing network. A state-dependent server model that approximates the rate at which the switch is transferring packets as a function of the work backlog (the number of packets queued at the switch inputs) is then developed. In this way, the model reflects the fact that such a switch tends to function more efficiently as the work backlog increases. This model yields an accurate method for approximating the entire distribution of the work backlog, as well as mean queue lengths and waiting times     

A selective ARQ protocol with a finite-length buffer

Of the automatic-repeat-request (ARQ) techniques commonly used in communication systems, selective protocols, while the most efficient, have the notable drawback of requiring large buffers at the receiver side. A selective ARQ protocol with a finite-length buffer is described. If N is the number of codewords transmittable in the round-trip delay, the protocol requires a buffer length N+N_a , N_a⩾2 being an integer. A lower bound on the throughput of the protocol is derived. It achieves higher throughputs than similar schemes giving results comparable to those for selective protocols with infinite-length buffer for high error rates in the communication channel     

Rapid optimal scheduling for time-multiplex switches using acellular automaton

Many time-multiplex switching systems require that the incoming traffic be scheduled to avoid conflict at the switch output (two or more users converging simultaneously upon a single output). Optimal scheduling provides a means to assign traffic on demand such that either blocking probability is minimized (unbuffered system) or packet waiting time is minimized (buffered system). However, computation of an optimal schedule for switches of a reasonable size (i.e. N=100) may require many seconds or even minutes, whereas the traffic demand may vary much more rapidly. Since the computation time varies as O(N²), the problem becomes readily intractable for large N. This computational bottleneck is overcome by using a scheduling algorithm which is run on a simple special-purpose parallel computer (cellular automaton). A schedule is produced in O(N) time if signal propagation time in the automaton is considered negligible, and therefore increases in computation speed by several orders of magnitude should be possible; the time to compute a schedule for a 1000-input switch would be measured in milliseconds rather than minutes     

The Knockout Switch: A Simple, Modular Architecture for High-Performance Packet Switching

A new, high-performance packet-switching architecture, called the Knockout Switch, is proposed. The Knockout Switch uses a fully interconnected switch fabric topology (i.e., each input has a direct path to every output) so that no switch blocking occurs where packets destined for one output interfere with (i.e., block or delay) packets going to different Outputs. It is only at each output of the switch that one encounters the unavoidable congestion caused by multiple packets simultaneously arriving on different inputs all destined for the same output. Taking advantage of the inevitability of lost packets in a packet-switching network, the Knockout Switch uses a novel concentrator design at each output to reduce the number of separate buffers needed to receive simultaneously arriving packets. Following the concentrator, a shared buffer architecture provides complete sharing of all buffer memory at each output and ensures that all packets are placed on the output line on a first-in first-out basis. The Knockout Switch architecture has low latency, and is self-routing and nonblocking. Moreover, its Simple interconnection topology allows for easy modular growth along with minimal disruption and easy repair for any fault. Possible applications include interconnects for multiprocessing systems, high-speed local and metropolitan area networks, and local or toll switches for integrated traffic loads.     

一种输入输出排队交换机中分布式分组调度方法的研究

针对采用共享缓存(shared memory)做为交换机构(switching fabric)的输入输出排队交换机,该文给出了一个分布式分组调度方法DHIOS(Distriduted Hierarchical Ingress and OutputScheduling)并做了详细的仿真。表明DHIOS可以支持变长分组,能够确保业务流的QoS,性能优良。     

Nonuniform traffic analysis on a nonblocking space-division packetswitch

The nonuniform traffic performance on a nonblocking space division packet switch is studied. When an output link is simultaneously contended by multiple input packets, only one can succeed, and the rest will be buffered in the queues associated with each input link. given the condition that the traffic on each output is not dominated by individual inputs, this study indicates that the output contention involved by packets at the head of input queues can be viewed as an independent phase-type process for a sufficiently large size of the switch. Therefore, each input queue can be modeled by an independent Geom/PH/1 queueing process. Once the relative input traffic intensities and their output address assignment functions are defined, a general formulation can be developed for the maximum throughput of the switch in saturation. The result indicates under what condition the input queue will saturate. A general solution technique for the evaluation of the queue length distribution is proposed. The numerical study based on this analysis agrees well with simulation results     

Analysis of N×N passive optical starcoupler based on the normal modes of N input waveguides

An integrated passive N×N optical star coupler on silicon wafer is described. Antiresonant reflecting optical waveguides (ARROWs) are analyzed and utilized as the input and output waveguides of the N×N coupler. Combining the exact solutions of the slab ARROW waveguide with the effective index method, a 5×5 coupler is analyzed. In the slab waveguide analysis, the input waveguides are coupled to their neighbors. The interaction of the waveguides is described in terms of the normal modes of propagation. The resultant field distribution is then diffracted into the free space region which separates the input and output sections. The radiation illuminates the receiving aperture from which the receiving N waveguides branch out, each output element obtaining equal power levels. Different types of loss such as spillover loss and mismatch loss were analyzed and estimated for N=5. A 5×5 star coupler with a transmission efficiency of 56% at a wavelength of 1.3 μm is achievable     

The tone sense multiaccess protocols with partial collisiondetections (TSMA/PCD) for packet satellite communications

The tone sense multiaccess with partial collision detection (TSMA/PCD) protocol is particularly suitable for a packet satellite system serving an area with a dense population of earth stations. By incorporating a narrowband ground radio channel for broadcasting busy ones, the earth stations are able to avoid packet collisions by sensing for the absence of busy tones before transmitting packets. Partial collision detection capability can also be achieved. Single-tone TSMA/PCD gives 97% of the carrier-sense multiaccess with collision detection (CSMA/CD) throughput when N=10 tones are used, while for multitone and slot-by-slot announcement TSMA/PCD protocols only N=8 and N=2, respectively, are sufficient to drive the system to the CSMA/CD performance     

A Knockout Switch for Variable-Length Packets

The Knockout Switch is a new packet switch architecture recently proposed for high-speed local and metropolitan area networks, multiprocessor interconnects, and local or toll switches for integrated traffic loads. We describe an approach to extend the original Knockout Switch to work with variable-length packets. This new architecture employs an input broadcast bus arrangement to achieve complete interconnection of the inputs and outputs. Consequently, there is no congestion in the switch fabric other than the unavoidable conflict of multiple simultaneous packets destined for the same output. It is with this output contention that the Knockout principle is fully utilized to efficiently concentrate and store contending packets while maintaining the first-in first-out discipline of the packet sequence; and yet the fabric speed required is no more than the input/output line speeds, Under these design goals, no switch can yield better delay/ throughout performance. These are the most important attributes that have been preserved in the current proposal from the original Knockout Switch. For anN times Nswitch configuration, the variable-length packet Knockout Switch consists ofNinput broadcast buses, and anN:Lconcentrator (L ll N) and a shared buffer for each output. The design of each subsystem is discussed with emphasis on possible VLSI realization. Using today's technology, we should be able to implement the proposed switch with both input/output lines and internal hardware operating at 50 Mbits/s. The dimension of the switch (N times N) can grow modularly from say 32 × 32 to 1024 × 1024, rendering a total throughput in the range of tens of gigabits per second. Future upgrading of the line interfaces to much higher speed without modification to the internal switch hardware is also possible with a modest restriction on the minimum length of new packets.     

The bypass queue in fast packet switching

The telecommunications networks of the future are likely to be packet switched networks consisting of wide bandwidth optical fiber transmission media, and large, highly parallel, self-routing switches. Recent considerations of switch architectures have focused on internally nonblocking networks with packet buffering at the switch outputs. These have optimal throughput and delay performance. The author considers a switch architecture consisting of parallel plans of low-speed internally blocking switch networks, in conjunction with input and output buffering. This architecture is desirable from the viewpoint of modularity and hardware cost, especially for large switches. Although this architecture is suboptimal, the throughput shortfall may be overcome by adding extra switch planes. A form of input queuing called bypass queuing can improve the throughput of the switch and thereby reduce the number of switch planes required. An input port controller is described which distributes packets to all switch planes according to the bypass policy, while preserving packet order for virtual circuits. Some simulation results for switch throughput are presented     

Real-time packet switching: a performance analysis

The authors model the internal structure of a packet-switching node in a real-time system and characterize the tradeoff between throughput, delay, and packet loss as a function of the buffer size, switching speed, etc. They assume a simple shared-single-path switch fabric, though the analysis can be generalized to a wider class of switch fabrics. They show that with a small number of buffers the node will provide a guaranteed delay bound for high-priority traffic, a low average delay for low-priority traffic, no loss of packets at the input and low probability of packet loss at output