Scalable electronic packet switches

Due to the changed economic environment, the rush to implementing packet switches with switching capacities above 1 Tb/s, which had proceeded at a frantic pace for some years, has slowed down considerably. Most service providers do not foresee the deployment of switches and routers with gigantic capacities in the near future. The immediate interest does now rarely go beyond the subterabit range, with a sweet spot between 120-640 Gb/s, where the emphasis is on feature-rich systems that enable the convergence of legacy services with new emerging data services. Although the current focus is on smaller switches, it is still relevant to understand their evolution path to multiterabit capacities. The scalability issues are also critical to reduce complexity and simplify implementation, in order to push the limits of what can be achieved in the switches within current economic and market constraints. We analyze the current state of the art of practical large packet switches and routers, and discuss the issues affecting their scalability. Our approach is pragmatic, with most of our attention devoted to three major scalability aspects: implementation, support of quality of service, and multicasting. After a general discussion of these issues, we show their impact on the most popular switch architectures.     

Buffering in optical packet switches

This paper consists of a categorization of optical buffering strategies for optical packet switches, and a comparison of the performance of these strategies both with respect to packet loss/delay and bit error rate (BER) performance. Issues surrounding optical buffer implementation are discussed, and representative architectures are introduced under different categories. Conclusions are drawn about packet loss and BER performance, and about the characteristics an architecture should have to be practical. It is shown that there is a strong case for the use of optical regeneration for successful cascading of these architectures     

Photonic fast packet switching

Several approaches to photonic fast packet switching systems are presented. The wavelength-, time-, code-, and space-division approaches, including free-space photonic fast packet switching, are discussed. These approaches to photonic fast packet switching systems show that the research in this area is still in its infancy. Among various solutions, those based on a wavelength-division transport network and an electronic controller are most mature     

COD: alternative architectures for high speed packet switching

Architectures for packet switches are approaching the limit of electronic switching speed. This raises the question of how best to utilize advances in photonic technology to enable higher speeds. The authors introduce cascaded optical delay line (COD) architectures. The COD architectures utilize an extremely simple distributed electronic control algorithm to configure the states of 2×2 photonic switches and use optical fiber delay lines to temporarily buffer packets if necessary. The simplicity of the architectures may also make them suitable for “lightweight” all-electronic implementations. For optical implementations, the number of 2×2 photonic switches used is a significant factor determining cost. The authors present a “baseline” architecture for a 2×2 buffered packet switch that is work conserving and has the first-in, first-out (FIFO) property. If the arrival processes are independent and without memory, the maximum utilization factor is ρ, and the maximum acceptable packet loss probability is ϵ, then the required number of 2×2 photonic switches is O(log(ϵ)/log(γ)), where γ=ρ²/(ρ²+4-4ρ). If one modifies the baseline architecture by changing the delay line lengths then the system is no longer work conserving and loses the FIFO property, but the required number of 2×2 photonic switches is reduced to O(log[log(ϵ)/log(γ)]). The required number of 2×2 photonic switches is essentially insensitive to the distribution of packet arrivals, but long delay lines are required for bursty traffic     

输入队列交换的公平可扩展调度系统

提出了一种基于输入队列交换的公平可扩展网络调度系统FSSA.通过将若干个容量较小的调度器合理连接并使其协同工作,构成多端口大容量网络交换调度系统,解决了单个调度器容量和端口数受集成电路工艺限制的问题.FSSA不仅速度高、规模可扩展而且易于硬件实现.环型连接、管线工作及公平调度技术的采用使FSSA在性能方面得到了进一步优化.仿真结果显示,FSSA的性能可与基于iSLIP、DSRR等算法的单片调度器相比拟,尤其在流量较大时,FSSA的性能明显优于单调度器性能.     

Contention‐tolerant crossbar packet switches

We propose an innovative agile crossbar switch architecture called contention‐tolerant crossbar, denoted by CTC(N). Unlike the conventional crossbar and the crossbar with crosspoint buffers, which require complex hardware resolvers to grant one out of multiple output requests, CTC(N) can tolerate output contentions by a pipelining mechanism, with pipeline stages implemented as buffers in input ports. These buffers are used to decouple the scheduling task into N independent parts in such a way that N schedulers are located in N input ports, and they operate independently and in parallel. Without using arbiters and/or crosspoint buffers that require additional chip area, the CTC(N) switch is more scalable than existing crossbars. We analyze the throughput of CTC(N) switch, and find 63% throughput bottleneck. For achieving 100%, we consider two approaches: using internal speedup and using space multiplexing without internal speedup. We prove that 100% throughput can be achieved with internal speedup 2 or using two layers of CTC(N) fabric mathematically. Our simulation results validate our theoretical analysis. Copyright © 2010 John Wiley & Sons, Ltd.     

Future directions in packet radio architectures and protocols

The technology of packet switching over multihop, multiple-access channels has evolved to the point at which its protocols can now support internetwork operation of medium-size networks whose nodes possess some degree of mobility. As regards the needs and challenges of the future operating environment, it is clear that these can be met only by enhancing the packet radio architecture and its protocols. We discuss several enhancements that allow the organization of large, dynamic networks that can operate over multiple channels, adapt to varying conditions, and possess self-monitoring and self-control capabilities. As these areas are examined, the attendant issues and tradeoffs are discussed; in addition, some protocols and information regarding their performance are presented.     

Reservation-based contention resolution mechanism forBatcher-Banyan packet switches

The authors introduce a new method, called ring reservation, to design high-capacity packet switches. Input buffering is used with output port reservations to eliminate packet collisions. They describe a 32×32 prototype packet switch, built as a part of a broadband ISDN prototype, which has a per-port capacity of 30-55 Mbit/s     

Flexible bandwidth allocation in high-capacity packet switches

This paper introduces a protocol for scheduling of packets in high-capacity switches, termed weighted sequential greedy scheduling (WSGS). WSGS is a simple, greedy algorithm that uses credits to reserve bandwidth for input-output pairs. By using a pipeline technique, WSGS implemented by the current technology readily supports a switching capacity exceeding 1 Tb/s. Admission control is straightforward, allowing bandwidth reservations on a submillisecond time scale. Namely, the central controller readily determines if the newly requested bandwidth can be assigned to the given input-output pair. We have shown that a newly requested bandwidth should be assigned if both the input and output have enough capacity, which requires checking of only two inequalities. Therefore, WSGS is well suited for switching in data networks where sessions might require high bit rates and last for a short time. The WSGS allows bandwidth reservations with fine granularity, e.g., bandwidth can be reserved for individual web sessions, video streams, etc     

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

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

Input wavelength conversion in optical packet switches

This letter analyzes an architecture for optical packet switches in which the wavelength converters are shared per input line (SPIL). The architecture performance are evaluated by means of an analytical model and are compared with those of an optical packet switch architecture in which the wavelength converters are shared per output line (SPOL). The obtained results show that in both balanced and unbalanced traffic scenarios the proposed architecture allows for a remarkable saving in terms of number of converters. In some cases this saving can reach 50%.     

Captured-frame eligibility and round-robin matching for input-queued packet switches

A variety of matching schemes for input-queued (IQ) switches that deliver high throughput under traffic with uniform distributions has been proposed. However, there is a need of matching schemes that provide high throughput under several admissible traffic patterns, including those with nonuniform distributions, while keeping implementation complexity low. In this letter, first, we introduce the captured frame concept for matching schemes in IQ switches. Second, we propose a round-robin based matching scheme, uFORM, which uses the proposed concept for cell matching eligibility. We show via simulation that our matching scheme delivers high throughput under several nonuniform traffic patterns, and retains the high performance under uniform traffic that round-robin matching schemes are known to offer.     

Analysis of packet switches with input and output queuing

A single-stage nonblocking N*N packet switch with both output and input queuing is considered. The limited queuing at the output ports resolves output port contention partially. Overflow at the output queues is prevented by a backpressure mechanism and additional queuing at the input ports. The impact of the backpressure effect on the switch performance for arbitrary output buffer sizes and for N to infinity is studied. Two different switch models are considered: an asynchronous model with Poisson arrivals and a synchronous model with Bernoulli arrivals. The investigation is based on the average delay and the maximum throughput of the switch. Closed-form expressions for these performance measures are derived for operation with fixed size packets. The results demonstrate that a modest amount of output queuing, in conjunction with appropriate switch speedup, provides significant delay and throughput improvements over pure input queuing. The maximum throughput is the same for the synchronous and the asynchronous switch model, although the delay is different.<>     

Photonic packet WDM ring networks architecture and performance

This article reviews various WDM ring architectures and pays special attention to their implementation in the metropolitan environment. A number of possible network architectures as well as protocols are reviewed. The article also proposes and analyses a WDM slotted-ring network architecture with nodes that use one fixed transmitter and fixed receivers. Used as a metropolitan access network, it is shown through simulation how a simple slotted MAC protocol can be implemented in this network to achieve efficient bandwidth utilization. Throughput, delay and packet dropping probability results are presented under Poisson and self-similar traffic.     

Dynamic queue length thresholds for shared-memory packet switches

In shared-memory packet switches, buffer management schemes can improve overall loss performance, as well as fairness, by regulating the sharing of memory among the different output port queues. Of the conventional schemes, static threshold (ST) is simple but does not adapt to changing traffic conditions, while pushout (PO) is highly adaptive but difficult to implement. We propose a novel scheme called dynamic threshold (DT) that combines the simplicity of ST and the adaptivity of PO. The key idea is that the maximum permissible length, for any individual queue at any instant of time, is proportional to the unused buffering in the switch. A queue whose length equals or exceeds the current threshold value may accept no more arrivals. An analysis of the DT algorithm shows that a small amount of buffer space is (intentionally) left unallocated, and that the remaining buffer space becomes equally distributed among the active output queues. We use computer simulation to compare the loss performance of DT, ST, and PO. DT control is shown to be more robust to uncertainties and changes in traffic conditions than ST control     

A three-stage architecture for very large packet switches

This paper proposes a three-stage broadband packet switch architecture with more than 16,000 ports for a future central office. The switch is constructed by interconnecting many independent switch modules of small size which can be implemented using modifications of various well-studied switch fabric designs. Channel grouping is used to provide multiple paths for each input-output pair in order to decrease delay and increase throughput. We show that, for a given size, switch modules with channel grouping are simpler to realize than those without channel grouping. A datagram packet routeing approach is adopted in order to avoid table look-up that would be required by virtual-circuit routeing. Ways of preserving the sequence integrity of packets under this situation are presented. Performance analyses show that a 32,768 x 32,768 switch with acceptable performance can be constructed based on switch fabrics of no more than 128 ports.     

A modular architecture for very large packet switches

Switch modules, the building blocks of this system, are independently operated packet switches. Each module consists of a Batcher sorting network, a stack of binary trees, and a bundle of banyan networks. The modular architecture is a unification of the Batcher-banyan switch and the knockout switch, and can be physically realized as an array of three-dimensional parallel processors. Switch modules are interconnected only at the outputs by multiplexers. The partitioned switch fabric provides a flexible distributed architecture, which is the key to simplify the operation and maintenance of the whole switching system. The modularity implies less stringent synchronization requirements and makes higher-speed implementation possible. The proposed modular switch is intended to meet the needs of broadband telephone offices of all sizes. It is estimated that a modular switch with terabit capacity can be built using current VLSI technologies     

A distributed scheduling architecture for scalable packet switches

The continuous growth in the demand for diversified quality-of-service (QoS) guarantees in broadband networks introduces new challenges in the design of packet switches that scale to large switching capacities. Packet scheduling is the most critical function involved in the provision of individual bandwidth and delay guarantees to the switched flows. Most of the scheduling techniques proposed so far assume the presence in the switch of a single contention point, residing in front of the outgoing links. Such an assumption is not consistent with the highly distributed nature of many popular architectures for scalable switches, which typically have multiple contention points, located in both ingress and egress port cards, as well as in the switching fabric. We define a distributed multilayered scheduler (DMS) to provide differentiated QoS guarantees to individual end-to-end flows in packet switches with multiple contention points. Our scheduling architecture is simple to implement, since it keeps per-flow scheduling confined within the port cards, and is suitable to support guaranteed and best-effort traffic in a wide range of QoS frameworks in both IP and ATM networks     

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.     

Work-conservingness of CIOQ packet switches with limited outputbuffers

We demonstrate that no combined input- and output-queued (CIOQ) switch with limited speedup (i.e., smaller than the number of ports) and limited output buffering can be strictly work-conserving by constructing a counterexample traffic scenario