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     

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.     

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     

Minimizing Internal Speedup for Performance Guaranteed Switches With Optical Fabrics

We consider traffic scheduling in an N times N packet switch with an optical switch fabric, where the fabric requires a reconfiguration overhead to change its switch configurations. To provide 100% throughput with bounded packet delay, a speedup in the switch fabric is necessary to compensate for both the reconfiguration overhead and the inefficiency of the scheduling algorithm. In order to reduce the implementation cost of the switch, we aim at minimizing the required speedup for a given packet delay bound. Conventional Birkhoff-von Neumann traffic matrix decomposition requires N2 - 2N + 2 configurations in the schedule, which lead to a very large packet delay bound. The existing DOUBLE algorithm requires a fixed number of only 2N configurations, but it cannot adjust its schedule according to different switch parameters. In this paper, we first design a generic approach to decompose a traffic matrix into an arbitrary number of Ns (N² - 2N + 2 > N_S > N) configurations. Then, by taking the reconfiguration overhead into account, we formulate a speedup function. Minimizing the speedup function results in an efficient scheduling algorithm ADAPT. We further observe that the algorithmic efficiency of ADAPT can be improved by better utilizing the switch bandwidth. This leads to a more efficient algorithm SRF (scheduling residue first). ADAPT and SRF can automatically adjust the number of configurations in a schedule according to different switch parameters. We show that both algorithms outperform the existing DOUBLE algorithm.     

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     

Design and Implementation of Dynamic High-Speed Switches in Super Base Station Architectures

Novel centralized base station architectures integrating computation and communication functionalities have become important for the development of future mobile communication networks.Therefore,the development of dynamic high-speed interconnections between baseband units(BBUs)and remote radio heads(RRHs)is vital in centralized base station design.Herein,dynamic high-speed switches(HSSs)connecting BBUs and RRHs were designed for a centralized base station architecture.We analyzed the characteristics of actual traffic and introduced a switch traffic model suitable for the super base station architecture.Then,we proposed a data-priority-aware(DPA)scheduling algorithm based on the traffic model.Lastly,we developed the dynamic HSS model based on the OPNET platform and the prototype based on FPGA.Our results show that the DPA achieves close to 100%throughput with lower latency and provides better run-time complexity than iOCF and HE-iSLIP,thereby demonstrating that the proposed switch system can be adopted in centralized base station architectures.     

Ultrafast nonlinear interferometer (UNI)-based digital optical circuits and their use in packet switching

Digital optical logic circuits capable of performing bit-wise signal processing are critical building blocks for the realization of future high-speed packet-switched networks. In this paper, we present recent advances in all-optical processing circuits and examine the potential of their integration into a system environment. On this concept, we demonstrate serial all-optical Boolean AND/XOR logic at 20 Gb/s and a novel all-optical packet clock recovery circuit, with low capturing time, suitable for burst-mode traffic. The circuits use the semiconductor-based ultrafast nonlinear interferometer (UNI) as the nonlinear switching element. We also present the integration of these circuits in a more complex unit that performs header and payload separation from short synchronous data packets at 10 Gb/s. Finally, we discuss a method to realize a novel packet scheduling switch architecture, which guarantees lossless communication for specific traffic burstiness constraints, using these logic units.     

The sliding-window packet switch: a new class of packet switch architecture with plural memory modules and decentralized control

Shared-memory based packet switches are known to provide the best possible throughput performance for bursty data traffic in high-speed packet networks and internets compared with other buffering strategies under conditions of identical memory resources deployed in the switch. However, scaling of shared-memory packet switches to a larger size has been restricted mainly due to the physical limitations imposed by the memory-access speed and the centralized control for switching functions in shared-memory switches. A new scalable architecture for a shared-memory packet switch, called the sliding-window (SW) switch, is proposed to overcome these limitations. The SW switch introduces a new class of switching architecture, where physically separate multiple memory modules are logically shared among all the ports of the switch, and the control is decentralized. The SW switch alleviates the bottleneck caused by the centralized control of switching functions in large shared-memory switches. Decentralized switching functions enable the SW switch to operate in a pipeline fashion to enhance scalability and switching capacity compared with that of previously known classes of shared-memory switch architecture.     

Duality relationships among “space”,“time”, and “wavelength” in all-optical networks

All-optical networks (AONs) are emerging as the next generation broadband networks for both wide-area and local-area networks. New optical devices such as wavelength routers, and wavelength division switches are currently being developed to realize these AONs. In this paper, we examine “dual” properties that exist among “space”, “time”, and “wavelength” in multiplexed signals in AONs. This observation will clarify relationships among architectural alternatives and suggest novel space-time-wavelength switching structures. It will also lead to a performance analysis of all-optical networks, by exploiting some well studied results obtained for classical circuit switched systems. A study on call blocking probabilities will be reported in a separate paper     

高性能新型交换结构综述

 目前基于单级交换结构(single-stage switch)集中式调度的路由器已经不能满足Internet网络流量、网络规模和上层应用的快速发展.近年来,旨在提高路由器可扩展性、吞吐率、QoS能力的高性能交换技术,成为路由器技术研究中的一大热点.文章从体系结构、调度策略、QoS特性三个方面对高性能交换结构研究进展进行了综述,以可扩展性、实现复杂度、延迟和吞吐率保证、负载均衡及报文乱序为主要衡量指标分析比较了每一类交换结构调度算法的性能,最后提出下一步的研究课题和思路.     

CR Switch: A Load-Balanced Switch With Contention and Reservation

Load-balanced switches have received a great deal of attention recently as they are much more scalable than other existing switch architectures in the literature. However, as there exist multiple paths for flows of packets to traverse through load-balanced switches, packets in such switches may be delivered out of order. In this paper, we propose a new switch architecture, called the contention and reservation (CR) switch, that not only delivers packets in order but also guarantees 100% throughput. The key idea, as in a multiple-access channel, is to operate the CR switch in two modes: 1) the contention mode in light traffic and 2) the reservation mode in heavy traffic. To do this, we invent a new buffer management scheme, called virtual output queue with insertion (I-VOQ). With the I-VOQ scheme, we give rigorous mathematical proofs for 100% throughput and in-order packet delivery of the CR switch. By computer simulations, we also demonstrate that the average packet delay of the CR switch is considerably lower than other schemes in the literature, including the uniform frame spreading scheme, the padded frame scheme, and the mailbox switch .     

Hardware implementation of fair queuing algorithms for asynchronoustransfer mode networks

Providing quality-of-service guarantees in both cell- and packet-based networks requires the use of a scheduling algorithm in the switches and network interfaces. These algorithms need to be implemented in hardware in a high-speed switch. The authors present a number of approaches to implement scheduling algorithms in hardware. They begin by presenting a general methodology for the design of timestamp-based fair queuing algorithms that provide the same bounds on end-to-end delay and fairness as those of weighted fair queuing, yet have efficient hardware implementations. Based on this general methodology, the authors describe two specific algorithms, frame-based fair queuing and starting potential-based fair queuing, and discuss illustrative implementations in hardware. These algorithms may be used in both cell switches and packet switches with variable-size packets. A methodology for combining a traffic shaper with this class of fair queuing schedulers is also presented for use in network interface devices, such as an ATM segmentation and reassembly device     

A self-timed real-time sorting network

High-speed networks are expected to carry traffic classes with diverse quality of service (QoS) guarantees. For efficient utilization of resources, sophisticated scheduling protocols are needed; however, these must be implemented without sacrificing the maximum possible bandwidth. This paper presents the architecture and implementation of a self-timed real-time sorting network to be used in packet switches that support a diverse mix of traffic. The sorting network receives packets with appropriately assigned priorities and schedules the packets for departure in a highest-priority-first manner. The circuit implementation uses zero-overhead, self-timed, and self-precharging domino logic to minimize the circuit latency. An experimental sorting network chip has been designed using the techniques described in this paper to support 10 Gb/s links with ATM-size packets     

Performance comparison of switch architectures with shareable parallel memory modules

The class of switches with shareable parallel memory modules include those switches that use parallel memory modules which are physically separate but logically shared. The two main classes of such architectures namely the Shared Multibuffer (SMB) based switch and the Sliding-Window (SW) based packet switch both deploy shareable parallel memory modules, however they differ in the switching scheme used by them to store incoming packets and transfer packets among different switch ports. In this letter, we investigate and compare the performance of switching schemes deployed by these two classes of switching architectures. We compare throughput and packet loss performance of these two switches under conditions of identical traffic type, switch configuration and memory resource deployed.     

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     

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

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N×N switch, a “speedup” of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies     

Architecture design for ATM statistical multiplexers

Both high-speed packet switches and statistical multiplexers are critical elements in the ATM (asynchronous transfer mode) network. Many switch architectures have been proposed and some of them have been built, but relatively fewer statistical multiplexer architectures have been investigated to date. It has been considered that multiplexers are a special kind of switches which can be implemented with similar approaches. The main function of a statistical multiplexer, however, is to concentrate traffic from a number of input ports to a comparatively smaller number of output ports; ‘switching’ in the sense that a cell must be delivered to a specific output port is often not required. This implies that the channel grouping design principle, in which more than one path is available for each virtual circuit connection, can be applied in the multiplexer. We show that this technique reduces the required buffer memory and increases the system performance significantly. The performances of three general approaches for implementing an ATM statistical multiplexer are studied through simulations with various bursty traffic assumptions. Based on the best performing approach (sharing output channels and buffers), we propose two architecture designs to implement a scalable statistical multiplexer that is modularly decomposed into many smaller multiplexers by using a novel grouping network.     

Performances of the Data Vortex switch architecture under nonuniform and bursty traffic

The Data Vortex switch architecture has been proposed as a scalable low-latency interconnection fabric for optical packet switches. This self-routed hierarchical architecture employs synchronous timing and distributed traffic-control signaling to eliminate optical buffering and to reduce the required routing logic, greatly facilitating a photonic implementation. In previous work, we have shown the efficient scalability of the architecture under uniform and random traffic conditions while maintaining high throughput and low-latency performance. This paper reports on the performance of the Data Vortex architecture under nonuniform and bursty traffic conditions. The results show that the switch architecture performs well under modest nonuniform traffic, but an excessive degree of nonuniformity will severely limit the scalability. As long as a modest degree of asymmetry between the number of input and output ports is provided, the Data Vortex switch is shown to handle very bursty traffic with little performance degradation.     

Approximating Fluid Schedules in Crossbar Packet-Switches and Banyan Networks

We consider a problem motivated by the desire to provide flexible, rate-based, quality of service guarantees for packets sent over input queued switches and switch networks. Our focus is solving a type of online traffic scheduling problem, whose input at each time step is a set of desired traffic rates through the switch network. These traffic rates in general cannot be exactly achieved since they assume arbitrarily small fractions of packets can be transmitted at each time step. The goal of the traffic scheduling problem is to closely approximate the given sequence of traffic rates by a sequence of transmissions in which only whole packets are sent. We prove worst-case bounds on the additional buffer use, which we call backlog, that results from using such an approximation. We first consider the NtimesN, input queued, crossbar switch. Our main result is an online packet-scheduling algorithm using no speedup that guarantees backlog at most (N+1)² /4 packets at each input port and each output port. Upper bounds on worst-case backlog have been proved for the case of constant fluid schedules, such as the N²-2N+2 bound of Chang, Chen, and Huang (INFOCOM, 2000). Our main result for the crossbar switch is the first, to our knowledge, to bound backlog in terms of switch size N for arbitrary, time-varying fluid schedules, without using speedup. Our main result for Banyan networks is an exact characterization of the speedup required to maintain bounded backlog, in terms of polytopes derived from the network topology     

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.