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     

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

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

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

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

A distributed link scheduling algorithm for CDMA packet radio networks

A distributed algorithm for the conflict-free channel allocation in CDMA (code division multiple access) networks is presented. Dynamic adjustment to topological changes is also considered. Though the schedules produced by our algorithm are not optimal with respect to link schedule length, the algorithm is simple and practical. The link schedule length minimization problem is NP-complete. Here the length of a link schedule is the number of time slots it uses. The algorithm guarantees a bound 2 — 1 time slots on the TDMA cycle length, where is the maximum degree of a station (i.e., maximum number of stations that a station can reach by radio links) in the network. The message complexity of a station isO().     

Adaptive packet scheduling for scalable video streaming with network coding

Over the last decade, the emergence of new multimedia devices has motivated the research on efficient media streaming mechanisms that adapt to dynamic network conditions and heterogeneous devices’ capabilities. Network coding as a rateless code has been applied to collaborative media streaming applications and brings substantial improvements regarding throughput and delay. However, little attention has been given to the recoverability of encoded data, especially for the streaming with a strict deadline. This in turn leads to severe quality of experience. In this paper, we solve the unrecoverable transmission by proposing a multi-generation packet scheduling problem, which is treated as a video quality maximization problem and solved using dynamic programming algorithm. Experimental results confirm that the proposed algorithm brings better data recoverability and better quality of service in terms of video quality, delivery ratio, lower redundancy rate under different network sizes.     

On scheduling optical packet switches with reconfiguration delay

Using optical technology for the design of packet switches/routers offers several advantages such as scalability, high bandwidth, power consumption, and cost. However, reconfiguring the optical fabric of these switches requires significant time under current technology (microelectromechanical system mirrors, tunable elements, bubble switches, etc.). As a result, conventional slot-by-slot scheduling may severely cripple the performance of these optical switches due to the frequent fabric reconfiguration that may entail. A more appropriate way is to use a time slot assignment (TSA) scheduling approach to slow down the scheduling rate. The switch gathers the incoming packets periodically and schedules them in batches, holding each fabric configuration for a period of time. The goal is to minimize the total transmission time, which includes the actual traffic-sending process and the reconfiguration overhead. This optical switch scheduling problem is defined in this paper and proved to be NP-complete. In particular, earlier TSA algorithms normally assume the reconfiguration delay to be either zero or infinity for simplicity. To this end, we propose a practical algorithm, ADJUST, that breaks this limitation and self-adjusts with different reconfiguration delay values. The algorithm runs at O(/spl lambda/N/sup 2/logN) time complexity and guarantees 100% throughput and bounded worst-case delay. In addition, it outperforms existing TSA algorithms across a large spectrum of reconfiguration values.     

A scalable architecture for reducing power consumption in pipelined deep packet inspection system

A scalable architecture for reducing power consumption in pipelined AC-DFA (Aho-Corasick deterministic finite automaton) tries for deep packet inspection (DPI) system is proposed. A new scheme for deciding the strides of the AC-DFA trie is devised where the stride of each pipeline is decided variably to reduce the power consumption. Scaling down the clock frequency of the rarely-used stages is applied to reduce wasted power consumption. As a result, a DPI system with the proposed schemes shows a reduction of up to 27% in power consumption, compared with the state-of-the-art DPI systems.     

On the behavior of PHM distributed schedulers for input buffered packet switches

iSLIP and parallel hierarchical matching (PHM) are distributed maximal size matching schedulers for input-buffered switches. Previous research has analyzed the hardware cost of those schedulers and their performance after a small number of iterations. In this paper, we formulate an upper bound for the number of iterations required by PHM to converge. Then, we compare the number of iterations required by iSLIP and PHM to achieve a maximal throughput under uniform Bernoulli traffic, by means of simulation. Finally, we obtain the corresponding delay performances, which are similar. The results suggest that PHM has both the advantages of previous hierarchical matching algorithms (low hardware complexity) and iSLIP (low number of iterations).     

Fully hardware based WFQ architecture for high-speed QoS packet scheduling

A full hardware implementation of a Weighted Fair Queuing (WFQ) packet scheduler is proposed. The circuit architecture presented has been implemented using Altera Stratix II FPGA technology, utilizing Reduced Latency DRAM (RLDRAM) II and Quad Data Rate (QDR) II SRAM memory components. The circuit can provide fine granularity Quality of Service (QoS) support at a line throughput rate of 12.8 Gb/s in its current implementation. The authors suggest that, due to the flexible and scalable modular circuit design approach used, the current circuit architecture can be targeted for a full ASIC implementation to deliver 50 Gb/s throughput. The circuit itself comprises three main components; a WFQ algorithm computation circuit, a tag/time-stamp sort and retrieval circuit, and a high throughput shared buffer. The circuit targets the support of emerging wireline and wireless network nodes that focus on Service Level Agreements (SLA's) and Quality of Experience.     

FIRM: high-speed distributed scheduling for ATM switches withmultiple input queues

A new distributed scheduling algorithm for advanced input queueing switch architectures called FIRM is introduced. FIRM provides improved performance characteristics at high load compared to the most efficient alternative, improved fairness, and tighter service guarantees     

Queueing analysis of scheduling policies in copy networks ofspace-based multicast packet switches

Space-based multicast switches use copy networks to generate the copies requested by the input packets. In this paper our interest is in the multicast switch proposed by Lee (1988). The order in which the copy requests of the input ports are served is determined by the copy scheduling policy and this plays a major part in defining the performance characteristics of a multicast switch. In any slot, the sum of the number of copies requested by the active inputs of the copy network may exceed the number of output ports and some of the copy requests may need to be dropped or buffered. We first propose an exact model to calculate the overflow probabilities in an unbuffered Lee's copy network. Our exact results improve upon the Chernoff bounds on the overflow probability given by Lee by a factor of more than 10. Next, we consider buffered inputs and propose queueing models for the copy network for three scheduling policies: cyclic service of the input ports with and without fanout splitting of copy requests and acyclic service without fanout splitting. These queueing models obtain the average delay experienced by the copy requests. We also obtain the sustainable throughput of a copy network, the maximum load that can be applied to all the input ports without causing an unstable queue at any of the inputs, for the scheduling policies mentioned above     

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.     

一种面向分组业务的新型OADM结构

分析了一种面向分组业务的新型光分插复用器(OADM)结构,采用光正交码的自相关性与互相关性,给出了全光地址的识别机理,并将其原理应用于新型的光网元节点中,说明了设计方法、应用示例和仿真结果。     

分布式队列服务算法在无线网状网包调度中的应用

根据无线网状网的包调度特点,结合已有的差分队列服务算法和分布式贝尔曼-福特算 法,将有线网络中的差分队列服务算法改进为分布式队列服务算法（DQS）,使之实用于无 线网状网中多任务条件下实现系统的吞吐量最大化。仿真实验证明了DQS算法能有效地避免 传统多径传输中的按“类”或 “流”来进行调度的缺陷,有效地减少了数据包的端到端 延时和缓冲区需求,尤其是DQS算法的实际平均吞吐量性能有了很大的提高。     

一种面向分布式网络管理的自适应可扩展模型

本文针对大规模分布式网络的特点，提出了一种灵活、动态、自适应伸展性网络管理方案。它采和层次型体系结构，支持多个管理域的分布式网络管理，适应了大规模网络的规模可变性和弹性的特点。为了解决网络事件大量性、多样性和相关性的问题，本文将网络事件分为简单事件和复合事件两种类型，采用层次型事件处理机制和基于动态时间窗的事件合成方法，保证了事件检测的可靠性，平衡了系统负载，降低了网络资源的占有率。     

A new scalable VLSI architecture for Reed-Solomon decoders

A very-large-scale integration architecture for Reed-Solomon (RS) decoding is presented that is scalable with respect to the throughput rate. This architecture enables given system specifications to be matched efficiently independent of a particular technology. The scalability is achieved by applying a systematic time-sharing technique. Based on this technique, new regular, multiplexed architectures have been derived for solving the key equation and performing finite field divisions. In addition to the flexibility, this approach leads to a small silicon area in comparison with several decoder implementations published in the past. The efficiency of the proposed architecture results from a fine granular pipeline scheme throughout each of the RS decoder components and a small overhead for the control circuitry. Implementation examples show that due to the pipeline strategy, data rates up to 1.28 Gbit/s are reached in a 0.5 μm CMOS technology     

Human perception-based distributed architecture for scalable video conferencing services: theoretical models and performance

This research work proposes a human perception-based distributed architecture for the multiparty video conferencing services. The new architecture can effectively reduce the unnecessary traffic of the multilayer video streams on the overlay network. Rich theoretical models of the three different architectures: the proposed perception-based distributed architecture, the conventional centralized architecture, and perception-based centralized architecture have been constructed by using queuing theory to reflect the traffic generated, transmitted, and processed by the three architectures. The performance has been considered in different aspects from the total waiting time to the required service rates. Together, the modeling tools, the analysis, and the numerical results help to answer the common concern about advantages and disadvantages of the centralized and distributed architectures. Overall, the proposed human perception-based distributed architecture can maintain a smaller total waiting time with a much smaller requirement of service rate in comparison with the conventional centralized architecture and perception-based centralized architecture.     

A scalable pipelined architecture for fast buffer SRAMs

The design of synchronous buffer SRAMs for packet switching and signal processing applications is described. Called scalable cellular RAM (SCRAM), the approach configures memory blocks in a 2-D array with fully pipelined address and data distribution. The memory is scalable in that the access frequency is determined by the access time of a single block and is independent of the number of blocks. An experimental 0.5 μm CMOS 256 Kb SCRAM chip is described that operates at 240 MHz. Simulation results show that larger arrays are feasible using the suggested power reduction and redundancy techniques     

Multicast scheduling for input-queued switches

We design a scheduler for an M×N input-queued multicast switch. It is assumed that: 1) each input maintains a single queue for arriving multicast cells and 2) only the cell at the head of line (HOL) can be observed and scheduled at one time. The scheduler needs to be: 1) work-conserving (no output port may be idle as long as there is an input cell destined to it) and 2) fair (which means that no input cell may be held at HOL for more than a fixed number of cell times). The aim is to find a work-conserving, fair policy that delivers maximum throughput and minimizes input queue latency, and yet is simple to implement. When a scheduling policy decides which cells to schedule, contention may require that it leave a residue of cells to be scheduled in the next cell time. The selection of where to place the residue uniquely defines the scheduling policy. Subject to a fairness constraint, we argue that a policy which always concentrates the residue on as few inputs as possible generally outperforms all other policies. We find that there is a tradeoff among concentration of residue (for high throughput), strictness of fairness (to prevent starvation), and implementational simplicity (for the design of high-speed switches). By mapping the general multicast switching problem onto a variation of the popular block-packing game Tetris, we are able to analyze various scheduling policies which possess these attributes in different proportions. We present a novel scheduling policy, called TATRA, which performs extremely well and is strict in fairness. We also present a simple weight-based algorithm, called WBA