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.     

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.     

一种新型的负载均衡-交叉点缓冲交换结构

针对混合输入-交叉点队列(CICQ)交换结构受限于"流控通信延时"、"需要2倍内部加速仿真输出队列(OQ)交换"以及单纯交叉点缓冲(CQ)存在"非均衡流量模式下吞吐量性能不足"等问题,本文提出一种新型的"负载均衡交叉点缓冲交换结构".采用固定模式时隙轮转匹配进行负载均衡处理,将到达输入端口的非均衡流量转化为近似均衡流量并且平均分配到同一输出端口对应的交叉缓冲中,从而可以利用较小的交叉点缓冲来模拟输出队列调度,简化调度过程并且提高吞吐量.理论分析证明了这种新结构的稳定性以及模拟输出队列交换的能力.同时仿真表明,采用该交换结构可以在不需要内部加速的条件下获得相当于输出队列交换的性能,并且有效地解决了交叉点缓冲队列非均衡流量性能不足的问题.     

Traffic performance evaluation of an optical packet switch with multicast operation

We recently proposed a multicast-enabled optical packet switch architecture utilizing multicast modules. In this paper, we evaluate the traffic performance of our earlier proposed packet switch under a hybrid traffic model through simulations. The multicast packets are given higher priority than unicast packets so that only a small number of multicast modules are needed. The results show that the switch can achieve an acceptable packet loss probability in conjunction with a packet scheduling technique.     

A practical approach for statistical matching of output queueing

We study a practical approach to match the performance of an output-queued switch statistically. For this purpose, we propose a novel switching architecture called a multiple input/output-queued (MIOQ) switch that requires no speedup for providing sufficient switching bandwidth. To operate an MIOQ switch in a practical manner, we also propose a multitoken-based arbiter which schedules the switch at a high operation rate and a virtual first-in first-out queueing scheme which guarantees the departure order of cells belonging to the same traffic flow at output. Additionally, we show that the proposed switch can naturally provide asymmetric bandwidth for inputs and outputs, which may be important in dealing with the links with different bandwidth demands. Finally, we compare the performance of an MIOQ switch with that of an output-queued switch and discuss the design criteria to match the performance of an output-queued switch.     

Output-queued switch emulation by fabrics with limited memory

The output-queued (OQ) switch is often considered an ideal packet switching architecture for providing quality-of-service guarantees. Unfortunately, the high-speed memory requirements of the OQ switch prevent its use for large-scale devices. A previous result indicates that a crossbar switch fabric combined with lower speed input and output memory and two times speedup can exactly emulate an OQ switch; however, the complexity of the proposed centralized scheduling algorithms prevents scalability. This paper examines switch fabrics with limited memory and their ability to exactly emulate an OQ switch. The switch architecture of interest contains input queueing, fabric queueing, flow-control between the limited fabric buffers and the inputs, and output queueing. We present sufficient conditions that enable this combined input/fabric/output-queued switch with two times speedup to emulate a broad class of scheduling algorithms operating an OQ switch. Novel scheduling algorithms are then presented for the scalable buffered crossbar fabric. It is demonstrated that the addition of a small amount of memory at the crosspoints allows for distributed scheduling and significantly reduces scheduling complexity when compared with the memoryless crossbar fabric. We argue that a buffered crossbar system performing OQ switch emulation is feasible for OQ switch schedulers such as first-in-first-out, strict priority and earliest deadline first, and provides an attractive alternative to both crossbar switch fabrics and to the OQ switch architecture.     

保证100%吞吐率的两级组播交换结构

在路由器或交换机的交换结构中实现组播是提高组播应用速度的重要途径之一。传统的交叉开关结构(crossbar)组播调度方案有两种缺陷,一种是性能较低,另一种是实现的复杂度太高,无法满足高速交换的需要。该文提出了一个新的基于交叉开关的两级组播交换结构(TSMS),第1级是组播到单播的交换结构,第2级是联合输入和输出排队(CIOQ)交换,并为该结构设计了合适的最大扇出排队(FCN)优先-均匀分配中间缓存调度算法(LFCNF-UMBA)。理论分析和仿真实验都显示在该结构中,加速比低于22/(N+1)倍时吞吐率不可能实现100%;而采用LFCNF-UMBA调度算法,2倍加速比就可保证在任意允许(admissible)组播的吞吐率达到100%。     

On the speedup required for a multicast parallel packet switch

A parallel packet switch (PPS) is a switch in which the memories run slower than the line rate. Arriving packets are load-balanced packet-by-packet over multiple lower speed center stage packet switches. It is known that, for unicast traffic, a PPS can precisely emulate a FCFS output-queued (OQ) switch with a speedup of two and an OQ switch with delay guarantees with a speedup of three. In this paper we ask: is it possible for a PPS to emulate the behavior of an OQ multicast switch? The main result is that for multicast traffic an N-port PPS can precisely emulate a FIFO OQ switch with a speedup of S>2√N+1, and a switch that provides delay guarantees with a speedup of S>2√(2N)+2     

Derivation of the mean cell delay and cell loss probability formultiple input-queued switches

The multiple input-queued (MIQ) asynchronous transfer mode (ATM) switch has drawn much interest as a promising candidate for a high-speed and high-performance packet switch. The most conspicuous feature of the switch is that each input port is equipped with m(1⩽m⩽N) distinct queues, each for a group of output ports. Since the MIQ switch has multiple queues, an input can serve up to m cells in a time slot, leading to an enhanced performance. We derive the average queue length, mean cell delay, and cell loss probability for the MIQ switch in terms of the number of queues in an input port (m) and input load. The results include a special case of the single input-queued (SIQ) switch (m=1), which is analyzed by Hui et al. (1987)     

The “packing” and the “scheduling packet”switch architectures for almost all-optical lossless networks

This paper proposes two almost all-optical packet switch architectures, called the “packing switch” and the “scheduling switch” architecture, which when combined with appropriate wait-for-reservation or tell-and-go connection and how control protocols provide lossless communication for traffic that satisfies certain smoothness properties. Both switch architectures preserve the order of packets that use a given input-output pair, and are consistent with virtual circuit switching, The scheduling switch requires 2klogT+k² two-state elementary switches (or 2klogT+2klogk elementary switches, if a different version is used) where k is the number of inputs and T is a parameter that measures the allowed burstiness of the traffic. The packing switch requires very little processing of the packet header, and uses k²logT+klogk two-state switches. We also examine the suitability of the proposed architectures for the design of circuit switched networks. We find that the scheduling switch combines low hardware cost with little processing requirements at the nodes, and is an attractive architecture for both packet-switched and circuit-switched high-speed networks     

The design and analysis of an ATM multicast switch with adaptivetraffic controller

The paper describes several improvements to a nonblocking copy network proposed previously for multicast packet switching. The improvements provide a complete solution to some system problems inherent in multicasting. The input fairness problem caused by overflow is solved by a cyclic running adder network (CRAN), which can calculate running sums of copy requests starting from any input port. The starting point can change adaptively in every time slot based on the overflow condition of the previous time slot. The CRAN also serves as a multicast traffic controller to regulate the overall copy requests. The throughput of a multicast switch can be improved substantially if partial service of copy request is implemented when overflow occurs. Call-splitting can also be implemented by the CRAN in a straightforward manner. Nonuniform distribution of replicated packets at outputs of the copy network may affect the performance of the following routing network. This output fairness problem due to underflow is solved by cyclically shifting the copy packets in every time slot. An approximate queueing model is developed to analyze the performance of this improved copy network. It shows that if the loading on each output of the copy network is maintained below 80%, the average packet delay in an input buffer would be less than two time slots     

Multistage shuffle networks with shortest path and deflectionrouting for high performance ATM switching: the open-loopshuffleout

A new class of switching architectures for broadband packet networks, called shuffleout, is described and analyzed in the paper. Shuffleout is basically an output-queued architecture with a multistage interconnection network built out of unbuffered b×2b switching elements. Its structure is such that the number of cells that can be concurrently switched from the inlets to each output queue equals the number of stages in the interconnection network. The switching element operates the cell self-routing adopting a shortest path algorithm which, in case of conflict for interstage links, is coupled with deflection routing. The paper presents the basic shuffleout architecture, called open-loop shuffleout, in which the cells that cross the whole interconnection network without entering the addressed output queues are lost. The key target of the proposed architecture is coupling the implementation feasibility of a self-routing switch with the desirable traffic performance typical of output queueing     

Throughput analysis for multicast switches with multiple input queues

This letter analyzes the saturated throughput for multicast switches with multiple input queues per input port. Under the assumptions of a Poisson uniform traffic model and random packet scheduling policy, we derive the multicast switch saturated throughput under different fanouts. To verify the analysis, extensive simulations are conducted with different switch sizes and fanouts. It is shown that the theoretical analysis and the simulation results have a discrepancy less than 1.9%. Results from this letter can be used as a guidance to design the optimal queuing for multicast switches.     

Matching output queueing with a multiple input/output-queued switch

We have previously proposed an efficient switch architecture called multiple input/output-queued (MIOQ) switch and showed that the MIOQ switch can match the performance of an output-queued switch statistically. In this paper, we prove theoretically that the MIOQ switch can match the output queueing exactly , not statistically, with no speedup of any component. More specifically, we show that the MIOQ switch with two parallel switches (which we call a parallel MIOQ (PMIOQ) switch in this paper) can provide exact emulation of an output-queued switch with a broad class of service scheduling algorithms including FIFO, weighted fair queueing (WFQ) and strict priority queueing regardless of incoming traffic pattern and switch size. To do that, we first propose the stable strategic alliance (SSA) algorithm that can produce a stable many-to-many assignment, and prove its finite, stable and deterministic properties. Next, we apply the SSA algorithm to the scheduling of a PMIOQ switch with two parallel switches, and show that the stability condition of the SSA algorithm guarantees for the PMIOQ switch to emulate an output-queued switch exactly. To avoid possible conflicts in a parallel switch, each input-output pair matched by the SSA algorithm must be mapped to one of two crossbar switches. For this mapping, we also propose a simple algorithm that requires at most 2N steps for all matched input-output pairs. In addition, to relieve the implementation burden of N input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of N physically-separate memories. In conclusion, we demonstrate that the MIOQ switch requires two crossbar switches in parallel and two physical memories at each input and output to emulate an output-queued switch with no speedup of any component.     

在CICQ交换结构下实现分布式的WFQ类加权公平调度算法

传统的基于crossbar的输入排队交换结构在提供良好的QoS方面存在很大的不足,而CICQ(Combined Input and Crosspoint buffered Queuing)交换结构与传统的交换结构相比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。该文基于CICQ结构,提出了在输入排队条件下实现基于流的分布式WFQ类分组公平调度算法的方案,并通过仿真验证了这一方案的有效性。     

An efficient cell-scheduling algorithm for multicast ATM switchingsystems

We propose an efficient multicast cell-scheduling algorithm, called multiple-slot cell-scheduling algorithm, for multicast ATM switching systems with input queues. Cells in an input-queueing system are usually served based on the first-in-first-out (FIFO) discipline, which may have a serious head-of-line (HOL) blocking problem. Our algorithm differs from previous algorithms in that we consider the output contention resolution for multiple time slots instead of the current time slot only. Like a window-based scheduling algorithm, our algorithm allows cells behind an HOL cell to be transmitted prior to the HOL cell in the same input port. Thus, HOL blocking can be alleviated. We have illustrated that the delay-throughput performance of our algorithm outperforms most of those algorithms that consider only the output contention resolution for the current time slot. We also present a simple and efficient architecture for realizing our algorithm, which can dramatically reduce the time complexity. We believe that the proposed architecture is very suitable for multicast asynchronous transfer mode (ATM) switching systems with input queues     

Design of a non-blocking shared-memory copy network for ATM

The design of a copy network is presented for use in an ATM (asynchronous transfer mode) switch supporting BISDN (broadband integrated services digital network) traffic. Inherent traffic characteristics of BISDN services require ATM switches to handle bursty traffic with multicast connections. In typical ATM switch designs a copy network is used to replicate multicast cells before being forwarded to a point-to-point routeing network. In such designs, a single multicast cell enters the switch and is replicated once for each multicast connection. Each copy is forwarded to the routeing network with a unique destination address and is routed to the appropriate output port. Non-blocking copy networks permit multiple cells to be multicasted at once, up to the number of outputs of the copy network. Another critical feature of ATM switch design is the location of buffers for the temporary storage of transmitted cells. Buffering is required when multiple cells require a common switch resource for transmission. Typically, one cell is granted the resource and is transmitted while the remaining cells are buffered. Current switch designs associate discrete buffers with individual switch resources. Discrete buffering is not efficient for bursty traffic as traffic bursts can overflow individual switch buffers and result in dropped cells, while other buffers are under-used. A new non-blocking copy network is presented in this paper with a shared-memory input buffer. Blocked cells from any switch input are stored in a single shared input buffer. The copy network consists of three banyan networks and shared-memory queues. The design is scalable for large numbers of inputs due to low hardware complexity, O (N log₂ N), and distributed operation and control. It is shown in a simulation study that a switch incorporating the shared-memory copy network has increased throughput and lower buffer requirements to maintain low packet loss probability when compared to a switch with a discrete buffer copy network.     

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     

An Efficient Scheduling Discipline for Packet Switching Networks Using Earliest Deadline First Round Robin

This paper addresses a frame-oriented scheduling discipline, EDF-RR (earliest deadline first round robin), for OQ (output-queued) switch architecture and data traffic consisting of fixed-length cells. Bandwidth reservation for an active session is performed by holding a number of cell slots for the session in a repeatedly-transferred frame. Each cell that is going to be transferred in the frame is assigned a virtual release time and a virtual deadline according to the bandwidth reservation scheme. The transmitting order of the cells in the frame is determined by non-preemptive non-idling EDF algorithm so that cells of a backlogged session in the frame are distributed as uniformly as possible. Through the analysis applying real-time scheduling theory and network calculus as well as network simulation, EDF-RR takes the advantage of O(1) computational complexity, and possesses tight delay bounds and lenient buffer requirements. The proposed scheduling discipline is appropriate for distributed real-time systems as we show that sessions can be configured based on message traffic models and deadline requirements. Also, a modified version of EDF-RR, called EDF-DRR, can be applied as traffic regulator when jitter requirements exist among active sessions. This work was sponsored in part by the Federal Aviation Administration (FAA) via grant DTFA03-01-C-00042. Findings contained herein are not necessarily those of the FAA.     

Packet loss in a bufferless optical WDM switch employing sharedtunable wavelength converters

We propose an architecture for a bufferless packet optical switch employing the wavelength dimension for contention resolution. The optical packet switch is equipped with tunable wavelength converters shared among the input lines. An analytical model Is proposed in order to determine the number of converters needed to satisfy prefixed packet loss probability constraints. This analytical model very accurately fits with simulations results. A sensitivity analysis of the required number of converters as a function of the main system parameters (number of input and output lines, number of wavelengths, …) and traffic parameters has been carried out. Making use of the introduced dimensioning procedure we have observed that the proposed architecture allows a saving in terms of employed number of converters with respect to the other architectures proposed in literature. Such a saving can reach about 95% of the number of converters