PetaStar: a petabit photonic packet switch

This paper presents a new petabit photonic packet switch architecture, called PetaStar. Using a new multidimensional photonic multiplexing scheme that includes space, time, wavelength, and subcarrier domains, PetaStar is based on a three-stage Clos-network photonic switch fabric to provide scalable large-dimension switch interconnections with nanosecond reconfiguration speed. Packet buffering is implemented electronically at the input and output port controllers, allowing the central photonic switch fabric to transport high-speed optical signals without electrical-to-optical conversion. Optical time-division multiplexing technology further scales port speed beyond electronic speed up to 160 Gb/s to minimize the fiber connections. To solve output port contention and internal blocking in the three-stage Clos-network switch, we present a new matching scheme, called c-MAC, a concurrent matching algorithm for Clos-network switches. It is highly distributed such that the input-output matching and routing-path finding are concurrently performed by scheduling modules. One feasible architecture for the c-MAC scheme, where a crosspoint switch is used to provide the interconnections between the arbitration modules, is also proposed. With the c-MAC scheme, and an internal speedup of 1.5, PetaStar with a switch size of 6400 /spl times/ 6400 and total capacity of 1.024 petabit/s can be achieved at a throughput close to 100% under various traffic conditions.     

Round-robin selection with adaptable-size frame in a combined input-crosspoint buffered switch

As an alternative to input-buffered switches, combined input-crosspoint buffered switches relax arbitration timing and provide high-performance switching for packet switches with high-speed ports. It has been shown that these switches, with one-cell crosspoint buffer and round-robin (RR) arbitration at input and output ports, provide 100% throughput under uniform traffic. However, under admissible traffic patterns with nonuniform distributions, only weight-based selection schemes are reported to provide high throughput. We propose an RR based arbitration scheme for a combined input-crosspoint buffered packet switch that provides nearly 100% throughput for several admissible traffic patterns, including uniform and unbalanced traffic, using one-cell crosspoint buffers. The presented scheme uses adaptable-size frames, so that the frame size adapts to the traffic pattern.     

Packet dispatching using module matching in the modified MSM Clos-network switch

A modified memory-space-memory (MSM) Clos-network switch, called MCNS, with a module-level matching packet dispatching scheme, is presented in the paper. The MCNS is a modification of the MSM Clos-network switch proposed to simplify the packet dispatching scheme. In this paper, we evaluate the combinatorial properties of the MCNS, as well as a new module-level matching packet dispatching algorithm. We also show how this algorithm can be implemented in an field-programmable gate array chip. Selected simulation results obtained for the MCNS are compared with the results obtained for the MSM Clos-network switch using other module-level matching algorithms.     

Saturn: a terabit packet switch using dual round robin

Large input-output buffering with a moderate speedup has been widely considered as the most feasible solution for large-capacity switches. We propose a new terabit per second packet switch and call it the Saturn switch. It uses a simple dual round-robin arbitration scheme to schedule packets, and achieves high throughput and low statistical delay bound. It employs a bit-sliced crossbar fabric to switch packets at 10 Gb/s at inputs and outputs, and adopts a novel token-tunneling technique to arbitrate contending packets at high speed (e.g., within 10 ns), thus achieving a switch capacity of more than 1 Tb/s with existing electronic technology.     

基于帧填补的MMM Clos网络按序分组交换算法

与其它类型的Clos网络相比,各级带缓存的MMM(Memory-Memory-Memory)Clos网络使得交换网络的配置时间最小化,但是MMM交换中间级缓存的存在会引起输出端口的信元乱序。该文提出了一种满帧填补扩展算法(EPF),采用逐帧转发的方式来避免MMM Clos网络中的乱序问题。新算法在输入级和输出级采用固定周期轮转方式,中间级采用最早信元优先输出调度,具有复杂度低,可分布式控制,以及不需要缓存加速的特点。分析和仿真结果表明该算法是稳定的,即输入输出为可允许业务时,算法可达100%吞吐率。     

Fast ping‐pong arbitration for input–output queued packet switches

Input–output queued switches have been widely considered as the most feasible solution for large capacity packet switches and IP routers. In this paper, we propose a ping‐pong arbitration scheme (PPA) for output contention resolution in input–output queued switches. The challenge is to develop a high speed and cost‐effective arbitration scheme in order to maximize the switch throughput and delay performance for supporting multimedia services with various quality‐of‐service (QoS) requirements. The basic idea is to divide the inputs into groups and apply arbitration recursively. Our recursive arbiter is hierarchically structured, consisting of multiple small‐size arbiters at each layer. The arbitration time of an n‐input switch is proportional to log₄?n/2? when we group every two inputs or every two input groups at each layer. We present a 256×256 terabit crossbar multicast packet switch using the PPA. The design shows that our scheme can reduce the arbitration time of the 256×256 switch to 11 gates delay, demonstrating the arbitration is no longer the bottleneck limiting the switch capacity. The priority handling in arbitration is also addressed. Copyright © 2001 John Wiley & Sons, Ltd.     

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.     

Distributed arbitration scheme for on-chip CDMA bus with dynamic codeword assignment

Several code-division multiple access (CDMA)-based interconnect schemes have been recently proposed as alternatives to the conventional time-division multiplexing bus in multicore systems-on-chip. CDMA systems with a dynamic assignment of spreading codewords are particularly attractive because of their potential for higher bandwidth efficiency compared with the systems in which the codewords are statically assigned to processing elements. In this paper, we propose a novel distributed arbitration scheme for dynamic CDMA-bus-based systems, which solves the complexity and scalability issues associated with commonly used centralized arbitration schemes. The proposed arbitration unit is decomposed into multiple simple arbitration elements, which are connected in a ring. The arbitration ring implements a token-passing algorithm, which both resolves destination conflicts and assigns the codewords to processing elements. Simulation results show that the throughput reduction in an optimally configured dynamic CDMA bus due to arbitration-related overheads does not exceed 5%.     

星上Clos交换网络的分治调度算法

针对星上交换的特殊要求,该文提出了基于MSM (Memory-Space-Memory)型Clos交换网络的分治调度算法。通过引入冲突域的概念,分治调度算法将MSM型Clos网络中的匹配问题分解成在冲突域内为每个中间级模块选择信元的问题。该调度算法限制了冲突发生的范围,简化了调度的复杂度,并且具有硬件实现简单、能适应多种业务等优点。仿真表明,分治调度算法在各种业务模型下的吞吐率都能接近100%,并具有良好的时延性能,满足了卫星通信的要求。     

Fuzzy logic arbiters for multiple-bus multiprocessor systems

This paper describes and evaluates the use of fuzzy logic arbiters for multiple-bus shared memory multiprocessor system. Multiple-bus systems allow multiple and simultaneous bus transfer in addition to a high degree of fault tolerance. In such systems, arbiters are used to resolve conflicts to system resources, which are the shared memory modules and the buses. Typically, these conflicts are resolved by using two-stage arbitration schemes that employ policies such as random choice, daisy chaining, round-robin, etc. A new way of implementing these arbiters is the use of fuzzy logic to resolve resource request conflicts based on the system state and performance variables. This paper describes a new technique for implementation of fuzzy logic in the system arbiters and presents a simulation program that evaluates the system performance. The program is coded in such a way as to accommodate any arbitration scheme, from which the fixed priority and fuzzy priority have been implemented. Parameters affecting multiple-bus system performance are considered and used as inputs to the fuzzy arbiters. The inputs are fuzzified by using appropriate membership functions, and rules have been defined in such a way as to increase and distribute evenly the acceptance probability of each processor in the system. Results from the simulation program using a prioritized arbitration scheme are compared against other published results and show very close agreement. Furthermore, results show an increase in the acceptance probability of the processors using fuzzy arbiters.     

Two-dimensional round-robin schedulers for packet switches withmultiple input queues

Presents a new scheduler, the two-dimensional round-robin (2DRR) scheduler, that provides high throughput and fair access in a packet switch that uses multiple input queues. We consider an architecture in which each input port maintains a separate queue for each output. In an N×N switch, our scheduler determines which of the queues in the total of N² input queues are served during each time slot. We demonstrate the fairness properties of the 2DRR scheduler and compare its performance with that of the input and output queueing configurations, showing that our scheme achieves the same saturation throughput as output queueing. The 2DRR scheduler can be implemented using simple logic components, thereby allowing a very high-speed implementation     

一种可综合的轮换仲裁控制器设计

Round-robin算法是一种简易，有效的公平仲裁方法。文章介绍了一种改进的算法原理，给出证明。最后给出了此种算法的电路实现方案。     

A pipeline-based approach for maximal-sized matching scheduling ininput-buffered switches

This letter proposes an innovative pipeline-based maximal-sized matching scheduling approach, called PMM, for input-buffered switches. It dramatically relaxes the timing constraint for arbitration with a maximal matching scheme. In the PMM approach, arbitration operates in a pipelined manner. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of them provides the matching result. The subscheduler can adopt a pre-existing efficient round-robin-based maximal matching algorithm. We show that PMM provides 100% throughput under uniform traffic since it preserves a desynchronization effect of the round-robin pointers as in the preexisting algorithm. In addition, PMM maintains fairness for best-effort traffic due to the round-robin-based arbitration     

On the combined input-crosspoint buffered switch with round-robin arbitration

Input-buffered switches have been widely considered for implementing feasible packet switches. However, their matching process may not be time-efficient for switches with high-speed ports. Buffered crossbars (BXs) are an alternative to relax timing for packet switches with high-speed ports and to provide high-performance switching. BX switches were originally considered expensive, as the memory amount required in the crosspoints (XPs) is proportional to the square of the number of ports (O(N/sup 2/)). This limitation is now less stringent with the advances on chip-fabrication techniques, and when considering small crosspoint (XP) buffer sizes. In this paper, we study a combined input-crosspoint buffered packet switch, named CIXB, with virtual output queues (VOQs) at the inputs, and arbitration based on round-robin selection. We show that the CIXB switch achieves 100% throughput under uniform traffic, and high performance under nonuniform traffic, using one-cell XP buffer size and no speedup.     

Design of multicast ATM switch

The proposed ATM switch has very high throughput under heavy-traffic conditions. The cell blocking scenario described in the comment [see ibid., vol. 35, no 5, 1999] is of no importance. Directly after the switch is reset, the first four cells will not be placed in the same RAM with the help of the cell-in stage. Under heavy-traffic conditions, the number of cells in each RAM is well balanced and no blocking effect would occur for unicast traffic. That scenario would only arise at the end of transmission when no more cells would be entering the switch. However, the probability of that scenario ocurring is extremely low. Therefore, an internal memory speedup would not be needed and the throughput would not be degraded. The proposed dynamic multicast scheme can fully utilise the available bandwidth     

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.     

星载Clos网络的全分布式容错调度算法

针对星载交换结构受空间辐射影响造成的可靠性严重下降问题,该文提出了一种支持全分布式调度的三级Clos网络及其全分布式容错(Fully Distributed Fault Tolerant, FDFT)调度算法,以提高星载交换结构在交叉点故障下的容错能力。该Clos网络的中间级和输出级采用联合输入交叉点队列,以支持Clos网络和交换单元内部的全分布式调度。FDFT采用一种分布式故障检测算法获得交叉点故障信息。基于对交叉点故障影响范围的分析,FDFT在输入级采用一种容错信元分发算法,实现无故障路径的负载均衡。理论分析证明,当任一输入/输出级交换单元故障个数不超过(m-n)或所有中间级交换单元故障个数不超过(m-n)时,其中m, n分别为输入级交换单元输入、输出端口数,FDFT能够达到100%吞吐率。仿真结果进一步验证,故障随机发生情况下,FDFT能够抵抗比故障任意发生情况下更多的故障,且在不同的业务场景下具有良好的吞吐率和时延性能。     

MAC层协作的VHT WLAN吞吐量增强方案及其性能研究

本文针对超高吞吐量无线局域网(VHT WLAN)引入多用户和带宽扩展后造成的载波侦听机制呈现的一些问题,提出了基于MAC协作的两层网络分配矢量(Two Level Network Allocation Vector, TLNAV)方案,该方案不仅有效解决了传统机制存在的问题而且在实际应用中简单易行,并能获得系统吞吐量的有效提升;在此基础上,本文提出了超高吞吐量无线局域网的不等带宽发送方案,该方案不仅解决了多用户模式发送时带宽的浪费问题,而且获得了系统吞吐量的进一步提高;本文对所提方案进行了性能分析,获得了所提方案在单用户和多用户发送模式下的吞吐量增益;最后本文通过仿真验证了所提方案的有效性以及理论分析的正确性,从仿真结果可以看到随着传输机会内剩余时长的增加所提方案能获得显著的吞吐量性能增益。      

Efficient fair queuing using deficit round-robin

Fair queuing is a technique that allows each flow passing through a network device to have a fair share of network resources. Previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement; specifically, the work required to process a packet in these schemes was O(log(n)), where n is the number of active flows. This is expensive at high speeds. On the other hand, cheaper approximations of fair queuing reported in the literature exhibit unfair behavior. In this paper, we describe a new approximation of fair queuing, that we call deficit round-robin. Our scheme achieves nearly perfect fairness in terms of throughput, requires only O(1) work to process a packet, and is simple enough to implement in hardware. Deficit round-robin is also applicable to other scheduling problems where servicing cannot be broken up into smaller units (such as load balancing) and to distributed queues     

Concurrent fault detection for a multiple-plane packet switch

In high-speed and high-capacity packet switches, system reliability is critical to avoid loss of huge amounts of information and retransmission of traffic. We propose a series of concurrent fault-detection mechanisms for a multiple-plane crossbar-based packet switch. Our switch model, called the m+z model, has m active planes and z spare planes. This switch has distributed arbiters on each plane. The spare planes, used for substitution of faulty active ones, are also used in the fault-detection mechanism, thus providing fault detection and fault location for all switching planes. Our detection schemes are able to detect a single fault quickly without increasing transmission overhead. The proposed schemes can be used for switches with different numbers of active planes and a small number of spare planes.