The λ-scheduler: A multiwavelength scheduling switch

We propose a new multiwavelength almost all-optical switch architecture called the λ-scheduler that uses wavelength division multiplexing (WDM) internally to fold the switch architecture in both the space and time domains to reduce the hardware complexity and to improve the signal characteristics through the switch. The λ-scheduler preserves the packet order for a given input-output pair, is consistent with virtual circuit switching, and when combined with appropriate connection and flow control protocols, provides lossless communication for bursty (or nonconstant rate) traffic, provided the traffic satisfies certain smoothness properties. The λ-scheduler uses novel scheduling and wavelength assignment algorithms, in conjunction with a series of feed-forward delay blocks, to avoid packet collisions within the switch or at the switch outputs. We present two implementations of the λ-scheduler when the number of internal wavelengths k equal the number of inputs (and outputs) N to the switch. In the compressed λ-scheduler, the N internal wavelengths are used to fold the architecture in the time domain, which reduces the total number of delay blocks for the switch by 2N log N. In the collapsed λ-scheduler, the N internal wavelengths are used to fold the architecture in the space domain, which reduces the number of delay blocks and total fiber length used for delays by a factor of N. We examine the insertion loss for both λ-scheduler implementations and discuss the trade-offs between the reduction in overall component count and the improvement in the signal characteristics     

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.     

Blocking and nonblocking multirate Clos switching networks

This paper investigates in detail the blocking and nonblocking behavior of multirate Clos switching networks at the connection/virtual connection level. The results are applicable to multirate circuit and fast-packet switching systems. Necessary and sufficient nonblocking conditions are derived analytically. Based on the results, an optimal bandwidth partitioning scheme is proposed to reduce switch complexity while maintaining the nonblocking property. The blocking behavior of blocking switches supporting multicast connections is investigated by means of simulation. We propose a novel simulation model that filters out external blocking events without distorting the bandwidth and fanout (for multicasting) distributions of connection requests. In this way, the internal blocking statistics that truly reflect the switch performance can be gathered and studied. Among many simulation results, we have shown that for point-to-multipoint connections, a heuristic routing policy that attempts to build a narrow multicast tree can have relatively low blocking probabilities compared with other routing policies. In addition, when small blocking probability can be tolerated, our results indicate that situations with many large-fanout connection requests do not necessarily require a switch architecture of higher complexity compared to that with only point-to-point requests     

Optimal cost/performance design of ATM switches

This paper proposes a methodology for performing an evaluation and optimization of the cost of an ATM switching architecture under performance constraints given in terms of virtual connection blocking probability. An analysis of blocking networks is developed, and combined with known results concerning nonblocking networks, provides a theoretical model which relates traffic characteristics, network topology and blocking probability in a multirate/multiservice broadband environment. An analysis of the characteristics determining the cost of a generic ATM switch implementation follows. The model is oriented to optimize both the topological parameters and the speed advantage, with respect to the main cost factors of VLSI-based switching networks i.e., components count and complexity, interconnection costs     

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     

Multifiber Shared-Per-Wavelength All-Optical Switching: Architectures, Control, and Performance

A new wavelength converter sharing strategy for multifiber optical switches, namely shared-per-wavelength (SPW), which employs wavelength converters with fixed input wavelengths is presented. The aim is to reduce switch costs by using simpler optical components and low complexity space switching matrices. Practical implementations of both the well-known shared-per-node (SPN) and the new SPW schemes are presented, as well as the related scheduling algorithms to manage optical packet forwarding in synchronous scenario. An analytical model to evaluate blocking performance of the SPN architecture is also provided. Results show the accuracy of the model in the range of interest for switch design. The proposed architectures are compared in terms of performance and number of optical components employed. The SPW approach is shown to save a large number of semiconductor optical amplifier gates with respect to the SPN one when the number of fibers per interface is suitably not too high. In these cases, the SPW architecture requires a number of wavelength converters higher than the SPN, but simpler, being their inputs tuned on a single wavelength.     

高速信元交换调度算法研究

输入缓存交换结构的特点是缓存器和交换结构的运行速率与端口速率相等、实现容易,但存在队头阻塞(HOL),其吞吐率只有约58%.采用虚拟输出排队方法(VOQ)和适当的信元调度算法可消除HOL,使吞吐率达到100%.本文通过仿真对几种调度算法:PIM、iSLIP和LPF进行了全面地研究、比较和评价.     

The single-queue switch: a building block for switches withprogrammable scheduling

We introduce a new approach to ATM switching. We propose an ATM switch architecture which uses only a single shift-register-type buffering element to store and queue cells, and within the same (physical) queue, switches the cells by organizing them in logical queues destined for different output lines. The buffer is also a sequencer which allows flexible ordering of the cells in each logical queue to achieve any appropriate scheduling algorithm. This switch is proposed for use as the building block of large-stale multistage ATM switches because of low hardware complexity and flexibility in providing (per-VC) scheduling among the cells. The switch can also be used as scheduler/controller for RAM-based switches. The single-queue switch implements output queueing and performs full buffer sharing. The hardware complexity is low. The number of input and output lines can vary independently without affecting the switch core. The size of the buffering space can be increased simply by cascading the buffering elements     

On the design of asynchronous optical packet switch architectures with shared delay lines and converters

Optical packet switching (OPS) is a promising technology to enable next-generation high-speed IP networks. A major issue in OPS is packet contention that occurs when two or more packets attempt to access the same output fiber. In such a case, packets may be dropped, leading to degraded overall switching performance. Several contention resolution techniques have been investigated in the literature including the use of fiber delay lines (FDLs), wavelength converters (WCs), and deflection routing. These solution typically induce extra complexity to the switch design. Accordingly, a key design objective for OPS is to reduce packet loss without increasing switching complexity and delay. In this paper, we investigate the performance of contention resolution in asynchronous OPS architectures with shared FDLs and WCs in terms of packet loss and average switching delay. In particular, an enhanced FDL-based and a novel Hybrid architecture with shared FLDs and WCs are proposed, and their packet scheduling algorithms are presented and evaluated. Extensive simulation studies show that the performance of proposed FDL-based architecture outperforms typical OPS architectures reported in the literature. In addition, it shown that, for the same packet loss ratio, the proposed hybrid architecture can achieve up to 30% reduction in the total number of ports and around 80% reduction in the overall length of fiber as compared to the FDL-based architectures.     

Wavelength-exchanging cross connects (WEX)-a new class of photonic cross-connect architectures

All-optical wavelength division multiplexing (WDM) networks are expected to realize the potential of optical technologies to implement different networking functionalities in the optical domain. A key component in WDM networks is the optical switch that provides the basic functionality of connecting input ports to output ports. Existing WDM switches make use of space switches and wavelength converters (WCs) to realize switching. However, this not only increases the size and the complexity of the switch but also bears heavily on the cost. In this paper, the authors propose a new class of photonic switch architectures called wavelength-exchanging cross connect (WEX) that provides several advantages over existing switches by enabling a single-step space switching and wavelength conversion and thus eliminating the need for a separate conversion stage. This greatly enhances the switch architecture by reducing its size and complexity. The new class of cross-connect architectures is based on the proposed concept of a wavelength-exchange optical crossbar (WOC). The WOC concept is realized using the simultaneous exchange between two optical signals. The proposed WEX architecture is highly scalable. To establish scalability, the authors present a systematic method of developing instances of the switch architectures of an arbitrary large size.     

基于Crossbar的可重构网络输入排队分域调度研究

为解决传统网络技术体系中交换结构无法满足大量差异化业务规模化应用的问题,本文基于可重构网络技术体系,采用选择关闭部分Crossbar交叉节点的分域模型,提出了分域调度的思想,分析并推导了承载组内的SDRR调度算法和域内最长队列优先调度算法。最后采用交换性能仿真平台对该调度算法进行了复杂度和时延的仿真比较,结果表明:分域调度的最长队列优先算法比一般最长队列优先算法相对复杂度低,且随着调度域个数增加,相对复杂度降低。在相同业务源输入条件下,Crossbar三分域调度算法的时延小于非分域调度算法的时延,接近公平输出排队调度算法的时延。     

Traffic scheduling in a photonic packet switching system with QoSguarantee

The main challenge in the design of future broadband networks is to efficiently support high-bandwidth multimedia services. Recent advances in the optical networking reveal that all optical networks offering multigigabit rate per wavelength may soon become economical as the underlying backbone in wide area networks, in which photonic switch plays a central role. Two issues are the essential in the design of photonic packet switching, the support of end-to-end virtual connections and the support of diverse quality-of-service (QoS) services. Existing work in wide-area optical networks has largely focused on the former, relatively less attention has been given to support heterogeneous traffic types and to satisfy the potentially different QoS requirements of different types of traffic. In this paper, we introduce a novel hierarchical scheduling framework to use in a class of photonic packet switching systems based on WDM, in which we separate the flow scheduling from the transmission scheduling. We show such separation is essential for achieving scalability such that large input-output ports can be accommodated, and also for offering flexibility in that optimal scheduling algorithms can be derived in different level that can be best tuned to the specific system requirements. The salient feature of the proposed scheduling mechanism is that it takes into account potentially different QoS requirements from different traffic flows. A number of interesting findings are observed from the results obtained by both analysis and simulation: (1) QoS requirements can be satisfied for both real-time and nonreal-time flows; (2) the impact Of the real-time traffic head-of-line (HoL) blocking on the system throughput can be effectively alleviated with the prevailing number of traffic flows. In addition, we investigate a variety of performance measures under different system configurations     

The iSLIP scheduling algorithm for input-queued switches

An increasing number of high performance internetworking protocol routers, LAN and asynchronous transfer mode (ATM) switches use a switched backplane based on a crossbar switch. Most often, these systems use input queues to hold packets waiting to traverse the switching fabric. It is well known that if simple first in first out (FIFO) input queues are used to hold packets then, even under benign conditions, head-of-line (HOL) blocking limits the achievable bandwidth to approximately 58.6% of the maximum. HOL blocking can be overcome by the use of virtual output queueing, which is described in this paper. A scheduling algorithm is used to configure the crossbar switch, deciding the order in which packets will be served. Previous results have shown that with a suitable scheduling algorithm, 100% throughput can be achieved. In this paper, we present a scheduling algorithm called iSLIP. An iterative, round-robin algorithm, iSLIP can achieve 100% throughput for uniform traffic, yet is simple to implement in hardware. Iterative and noniterative versions of the algorithms are presented, along with modified versions for prioritized traffic. Simulation results are presented to indicate the performance of iSLIP under benign and bursty traffic conditions. Prototype and commercial implementations of iSLIP exist in systems with aggregate bandwidths ranging from 50 to 500 Gb/s. When the traffic is nonuniform, iSLIP quickly adapts to a fair scheduling policy that is guaranteed never to starve an input queue. Finally, we describe the implementation complexity of iSLIP. Based on a two-dimensional (2-D) array of priority encoders, single-chip schedulers have been built supporting up to 32 ports, and making approximately 100 million scheduling decisions per second     

具有纵横输入互连方式和缓冲结构的递归Knockout交换网络

本文提出了具有纵横输入（ＣｒｏｓｂａｒＩｎｐｕｔ）互连方式和输入缓冲（ＩｎｐｕｔＢｕｆｅｒｅｄ）结构的递归Ｋｎｏｃｋｏｕｔ交换网络（ＣＩＢＲＫＳ）．通过采用纵横输入互连方式可减少内部小交换单元的数目,并可使信元传送顺序不会受群输出端口数目的影响．而通过在每个输入端放置缓冲器可在保持丢失率性能不变的情况下,可使整个交换网络的级数减少,从而也就减少了信元在群网络中的传输时延．另外,在该结构中,通过把信元滤址的功能从每个小交换单元中提取出来放在每个输入端口,又进一步减少了小交换单元的功能．通过比较,我们认为,作为大规模ＡＴＭ交换网络结构,ＣＩＢＲＫＳ结构比传统的ＲＫＳ结构具有较好的性能／复杂度特性．     

时隙光突发交换网络调度问题研究

光突发交换（OBS）是构造下一代全光网络的潜在技术之一,但存在网络参数设计困难和阻塞性能有限等问题。文章介绍了一种新型基于时隙的OBS网络体系,简要阐明了其各部分功能,并将其与常规OBS网络进行了对比。提出了网络节点中关键的时隙分配与调度问题,并给出相应的在线调度策略,仿真结果表明BF算法性能较优。     

Strictly Non-Blocking Conditions for the Central-Stage Buffered Clos-Network

We consider using the Clos-network to scale high performance routers, especially the space-memory-space (SMS) packet switches. In circuit switching, the Clos-network is responsible for pure connections and the internal links are the only blocking sources. In packet switching, however, the buffers cause additional blockings. In this letter, we first propose a scalable packet switch architecture that we call the central-stage buffered Clos-network (CBC). Then, we analyze the memory requirements for the CBC to be strictly non-blocking, especially for emulating an output-queuing packet switch. Results show that even with the additional memory blockings the CBC still inherits advantages from the Clos-network, e.g., modular design and cost efficiency.     

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     

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

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

A 1.5 Gb/s 8×8 cross-connect switch using a time reservationalgorithm

An input queuing type switching architecture that uses a high-performance contention resolution algorithm to achieve high-speed and large-capacity cross-connect switching is presented. The algorithm, called the time reservation algorithm, features time scheduling and pipeline processing. The performance of this switch is evaluated by computer simulation. The throughput of this switch is about 90%, without requiring high internal operation speeds. Three LSI designs are developed to verify the feasibility of the high-speed switch. They are the input buffer controller LSI, the contention-resolution module LSI, and the space-division switching LSI. The LSIs were constructed with an advanced Si-bipolar high-speed process. Also, 8×8 cross-connect switching boards are introduced. The measured maximum port speed is 1.55 Gb/s