Achieving 100% throughput in an input-queued switch

It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in-first-out (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm. We introduce two maximum weight matching algorithms: longest queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100% throughput for all independent arrival processes. LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can lead to the permanent starvation of short queues. OCF overcomes this limitation by favoring cells with large waiting times     

Scheduling cells in an input-queued switch

The authors present two algorithms, IRRM and SLIP-IRRM, for scheduling cells in an input-queued cell switch. Both algorithms exhibit asymptotically 100% use factor under high load, SLIP-IRRM within a single iteration.<>     

On achieving maximum multicast throughput in undirected networks

The transmission of information within a data network is constrained by the network topology and link capacities. In this paper, we study the fundamental upper bound of information dissemination rates with these constraints in undirected networks, given the unique replicable and encodable properties of information flows. Based on recent advances in network coding and classical modeling techniques in flow networks, we provide a natural linear programming formulation of the maximum multicast rate problem. By applying Lagrangian relaxation on the primal and the dual linear programs (LPs), respectively, we derive a) a necessary and sufficient condition characterizing multicast rate feasibility, and b) an efficient and distributed subgradient algorithm for computing the maximum multicast rate. We also extend our discussions to multiple communication sessions, as well as to overlay and ad hoc network models. Both our theoretical and simulation results conclude that, network coding may not be instrumental to achieve better maximum multicast rates in most cases; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.     

Performance of an input-queued ATM switch with even/odd switchingplanes

A switch architecture is proposed for alleviating the HOL blocking by employing even/odd dual FIFO queues at each input and even/odd dual switching planes dedicated to each even/odd queue. Under random traffic, it gives 76.4% throughput without output expansion and 100% with output expansion r=2, with the same amount of crosspoints as for the ordinary output expansion scheme     

STF：PROVIDE RATE GUARANTEES IN INPUT—QUEUED SWITCH

A QoS-aware input-queued scheduling algorithm,called Smallest Timestamp First (stf),is propsed,which is improved upon is LIP and can allocate bandwidth among imputs sharing a common output based on their reservation by assigning suitable finishing timestamps to contending cells .STF can also provide isolation between flows that share a common output link.Misbehaving flows will be restricted to guarantee the behaving flow^s bandwidth .Simulations prove the feasibility of our algorithm.     

Multicast traffic in input-queued switches: optimal scheduling and maximum throughput

The paper studies input-queued packet switches loaded with both unicast and multicast traffic. The packet switch architecture is assumed to comprise a switching fabric with multicast (and broadcast) capabilities, operating in a synchronous slotted fashion. Fixed-size data units, called cells, are transferred from each switch input to any set of outputs in one time slot, according to the decisions of the switch scheduler, that identifies at each time slot a set of nonconflicting cells, i.e., cells neither coming from the same input, nor directed to the same output. First, multicast traffic admissibility conditions are discussed, and a simple counterexample is presented, showing intrinsic performance losses of input-queued with respect to output-queued switch architectures. Second, the optimal scheduling discipline to transfer multicast packets from inputs to outputs is defined. This discipline is rather complex, requires a queuing architecture that probably is not implementable, and does not guarantee in-sequence delivery of data. However, from the definition of the optimal multicast scheduling discipline, the formal characterization of the sustainable multicast traffic region naturally follows. Then, several theorems showing intrinsic performance losses of input-queued with respect to output-queued switch architectures are proved. In particular, we prove that, when using per multicast flow FIFO queueing architectures, the internal speedup that guarantees 100% throughput under admissible traffic grows with the number of switch ports.     

Maximum throughput of an input queueing packet switch with twopriority classes

The maximum throughput of an N×N nonblocking packet switch with input queues and two priority classes is analyzed. Packets are of fixed length and the switch operation is slotted. Packets of both priority classes are queued when waiting for service. High-priority packets preempt low-priority ones and move ahead of all low-priority packets waiting in the queue. A new method of analysis is employed. The calculated results of the maximum throughput obtained are close to the simulation results     

Performance analysis of the multiple input-queued packet switch with the restricted rule

The multiple input-queued (MIQ) switch is the switch which manages multiple (m) queues in each input port, each of which is dedicated to a group of output ports. Since each input port can switch up to m cells in a time slot, one from each queue, it hardly suffers from the head-of-line (HOL) blocking which is known to be the decisive factor limiting the throughput of the single input-queued (SIQ) switch. As a result, the MIQ switch guarantees enhanced performance characteristics as the number of queues m in an input increases. However, the service of multiple cells from an input could cause internal speedup or expansion of the switch fabric, diluting the merit of high-speed operation in the conventional SIQ scheme. The restricted rule is contrived to circumvent this side effect by regulating the number of cells switched from an input port. We analyze the performance of the MIQ switch employing the restricted rule. For the switch using the restricted rule, the closed formulas for the throughput bound, the mean cell delay and average queue length, and the cell loss bound of the switch are derived as functions of m, by generalizing the analysis for the SIQ switch by J.Y. Hui and E. Arthurs (see IEEE J. Select. Areas Commun., vol.SAC-5, p.1262-73, 1987).     

On the stability of input-queued switches with speed-up

We consider cell-based switch and router architectures whose internal switching matrix does not provide enough speed to avoid input buffering. These architectures require a scheduling algorithm to select at each slot a subset of input buffered cells which can be transferred toward output ports. We propose several classes of scheduling algorithms whose stability properties are studied using analytical techniques mainly based upon Lyapunov functions. Original stability conditions are also derived for scheduling algorithms that are being used today in high-performance switch and router architectures     

Packet-mode scheduling in input-queued cell-based switches

We consider input-queued switch architectures dealing at their interfaces with variable-size packets, but internally operating on fixed-size cells. Packets are segmented into cells at input ports, transferred through the switching fabric, and reassembled at output ports. Cell transfers are controlled by a scheduling algorithm, which operates in packet-mode: all cells belonging to the same packet are transferred from inputs to outputs without interruption. We prove that input-queued switches using packet-mode scheduling can achieve 100% throughput, and we show by simulation that, depending on the packet size distribution, packet-mode scheduling may provide advantages over cell-mode scheduling.     

Achieving stability in networks of input-queued switches

Research has generated many interesting results on scheduling input-queued switches. However, most of this work focuses on a single switch in isolation. We study the problem of scheduling a network of input-queued switches. We consider the longest-queue-first and longest-port-first scheduling policies that are stable for a single switch, and show that they can be unstable even for a fixed traffic pattern in a simple network of eight input-queued switches. Moreover, this result holds regardless of how the traffic sharing the same port-pair is scheduled at each switch. On the positive side, we present a policy, longest-in-network, that is stable in networks of input-queued switches. This result holds even if the traffic pattern is allowed to change over time.     

输入排队结构交换机分组调度研究

以决定分组调度算法的交换结构为基础,从协调,减少和隔离输入排队交换结构中输入输出竞争裁决冲突的角度,分别讨论了VOQ,CIOQ,CICQ结构中的分组调度问题,并以当前最新的调度算法为例加以说明,进行了定性分析和定量对比,指出了具体有待研究的问题。随后讨论了最近才开始研究的光电混合结构中的分组调度问题。最后从交换结构和算法两个方面探讨了今后的研究方向和发展趋势。     

On the necessary and sufficient requirement of a CIOQ switch to emulate an Output Queued switch

There has been much interest to emulate the behavior of Output Queued switches. The early result of such attempts was reported by Prabhakar and McKeown using the CIOQ switches with speedup factor of 4. Subsequently, Stoica and Zhang and independently Chuang et al. showed that a speedup of 2 in conjunction with their scheduling schemes would be sufficient for CIOQ switches to emulate Output Queued switches.Additionally, Chuang et al. showed that in “Average Sense” a speedup of 2?1/N is necessary and sufficient for CIOQ to emulate Output Queued switch behavior.Our paper reports that in the “Strict Sense” a speedup of 2 is both necessary and sufficient. We show this requirement using examples for 2x2 and 3x3 switches. Then, with a constructed traffic pattern, it is proved that in the “Strict Sense” a speedup of 2 is necessary to emulate the behavior of an Output Queued switch for any switch size N.Combining this result with the previous scheduling schemes, we conclude that in the “Strict Sense”, a speedup of 2 is the necessary and sufficient condition to emulate the behavior of an Output Queued switch, using a CIOQ switch.Additionally, easing the assumptions and allowing the packet segmentation, it is shown that the speedup requirement to emulate the behavior of an Output Queued switch can be reduced to values even smaller than 2?1/N. For this case a lower bound of 3/2 and an upper bound of 2 is proved.     

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 2Gb/s throughput GaAs digital time switch LSI using LSCFL

A GaAs four-channel digital time switch LSI with a 2.0-Gb/s throughput is developed. This switch consists of 4-bit shift registers, data latches, a counter, a control unit, and I/O buffer gates. The LSI includes 1176 devices (FET's, diodes, and resistors) and its equivalent gate number is 231 gates. Low Power Source Coupled FET Logic (LSCFL) operating in a true/complementary mode is used to ensure high-speed and low-power performance. MESFET's with 0.55-µm gate length are fabricated by the buried p-layer SAINT process, which satisfactorily suppresses short channel effects. Dislocation-free wafers are also used to provide high chip yields of 75 percent. The propagation delay time of the LSCFL basic circuit is 48 ps/gate with 1.4-mW/equivalent gate. The total power dissipation including input and output buffers is 0.64 W. The LSI speed performance is evaluated by measuring toggle frequency of the 1/4 frequency divider. The divider operates typically at 5.1 GHz, maximum 7.5 GHz. The newly developed high-speed digital time switch LSI makes possible time division switching services in TV and high-definition TV transmission systems.     

On throughput stabilization of network transport

A number of network applications require stable transport throughput for tasks such as control and coordination operations over wide-area networks. We present a window-based method that achieves stable throughput at a target level by utilizing a variation of the classical Robbins-Monro stochastic approximation algorithm. We analytically show the stability of this method under very mild conditions on the network, which are justified by Internet measurements. Our User Datagram Protocol (UDP)-based implementation provides stable throughput over the Internet under various traffic conditions.     

On improving throughput in packet mobile radio network

A novel random multiaccess protocol is proposed for a packet mobile-radio network employing an idle-signal casting multiple-access (ICMA) with/without collision detection scheme. The protocol takes advantage of the channel control scheme to reduce collisions. The authors show significant improvements in terms of maximum achievable throughput.<>     

A new analytical model for the CQ switch throughput calculation under the bursty traffic

In this paper we propose a new analytical iterative method for the throughput calculation of the Crosspoint Queued (CQ) switch with a random scheduling algorithm under the bursty traffic model. This method is verified by comparing it with the simulation results, which shows a very good match. To the authors’ knowledge, this is the first analytical method for the throughput calculation of such a switch for the bursty traffic model.     

关于TD-LTE网络物理层峰值吞吐率的分析

本文主要着重探讨了TD-LTE网络小区和和终端物理层理论上的峰值吞吐率,分析了上下行不同时隙配比下是否与TD-SCDMA共存系统等不同情况的区别,最后给出相应的理论物理层峰值吞吐率,可供TD-LTE网络规划参考。