Performance of buffered banyan networks under nonuniform trafficpatterns

An analytical method of evaluating the performance of the buffered banyan packet-switching network under nonuniform traffic patterns is presented. It is shown that nonuniform traffic can have a detrimental effect on the performance of the network. The analytical model is extended to evaluate the performance of multibuffer and parallel banyan networks. These modified networks are shown to have better throughput capacity and delay performance than the single-buffer banyan network     

PR-banyan: a packet switch with a pseudorandomizer for nonuniformtraffic

Buffered banyan networks are highly vulnerable to nonuniform traffic, due to the path sharing as well as the existence of only a single path per network input-output pair. Improving on an earlier packet distribution network which is a banyan network itself, a single-stage packet-scattering hardware, called the pseudo-randomizer (PR), is proposed. The PR-banyan, the PR followed by a buffered banyan, is analyzed under nonuniform traffic, and is shown to be highly effective under nonuniform traffic. The analytic results are shown to match the simulation results very closely     

Evaluation of pipelined dilated banyan switch architectures for ATMnetworks

In the pipeline banyan (PB), the reservation cycle in the control plane is made several times faster than payload transmission in data plane. This enables pipelining multiple banyans. It is observed that the ratio of throughput to switching delay (service rate) is relatively low in the PB due to the banyan. For this, we present a scalable pipelined asynchronous transfer mode (ATM) switch architecture employing a family of dilated banyan (DB) networks together with their complexity analysis and performance. A DB can be engineered between two extremes: (1) a low-cost banyan with internal and external conflicts, or (2) a high-cost conflict-free fully connected network with multiple outlets. Between the two extremes lies a family of DBs having different switching delays and throughputs. Increasing the dilation degree reduces path conflicts, which produces noticeable increase in service rate due to increase in throughput and decrease in path delay. Compared to PB, the pipelined dilated banyan (PDB) requires smaller number of data planes for the same throughput, or provides higher throughput for a given number of data planes. Simulation of PDB is carded out under uniform traffic and simulated ATM traffic. We study the switch performance while varying the load, buffer size, and number of data planes. To analyze the robustness of the switch, we show that performance is not degradable under ATM traffic with temporal and spatial burstiness generated using the on-off model. The PDB is scalable with respect to service rate and can be engineered with respect to: (1) cell loss rate; (2) hardware resources; (3) size of buffers; (4) switching delays; and (5) delay incurred to higher priority traffic. The PDB can deliver up to 3.5 times the service rate of the PB with only linear increase in hardware cost     

Design and analysis of a new self-routing network

A new self-routing network constructed from the sorting and the routing cells is proposed. The complexity of the new network is roughly twice as much as that of a pure banyan network. The new network can be viewed as an implementation of the load-sharing network which requires a very simple management. Its performance under uniform and nonuniform traffic models is analyzed for the unbuffered case. It is found that a higher degree of nonuniformity results in a better performance for certain forms of nonuniform traffic matrices. Simulations are performed to obtain the normalized throughputs and mean packet delays for the single-buffered case. Different from single-buffered pure banyan networks, the mean delay of high-traffic packets is smaller than that of low-traffic packets for a particular form of nonuniform traffic matrices. In addition to performance improvement, the new network is easy to diagnose. Some variations of the proposed network are also studied     

Design and analysis of a novel fast packet switch-pipeline banyan

Proposes a new fast packet switch architecture-pipeline banyan. It has a control plane and a number of parallel data planes which are of the same banyan topology. Packet headers are self-routed through the control plane to their destinations. As a result, they establish the corresponding routing paths in the data planes. The data planes do not need to do routing decisions, hence their complexity can be significantly reduced. Pipeline banyan can give a close to 100% maximum throughput and can deliver packets in a sequential order. Through analysis and simulation, the authors show that pipeline banyan has a better throughput and packet loss performance when compared with other banyan-type switch architectures     

PERFORMANCE ANALYSIS OF A PARALLEL BANYAN ATM SWITCH

Asynchronous transfer mode (ATM) switches can be constructed by connecting multiple banyan networks in parallel. To utilize the capacity of the parallel banyan networks fully, it is crucial to allow up to L cells from each input to be switched, and up to L cells to be received by each output simultaneously, where L is the total number of parallel banyan networks. This is possible if the switch operates in L overlapping phases and one banyan network is used to switch cells in each phase. Although a couple of such designs have been proposed and simulated, there is a lack of suitable models for such switches to be analysed mathematically. In this paper, two approximate analyses of a parallel banyan ATM switch are described. A comparison of the analytical and simulation results show that the analyses give reasonably accurate results. © 1997 by John Wiley & Sons, Ltd.     

Distributed routing protocols for ATM extended Banyan networks

It is well known that a multistage banyan network, which is a single-path blocking structure, becomes rearrangeable nonblocking in a circuit-switching environment if the number of its stages is increased so as to obtain a Benes network. Banyan networks, provided with a shared queue in each switching element, have often been proposed as the core of an interconnection network for an ATM packet switching environment. In this scenario, if the classical interstage backpressure protocols are used, adding stages to a banyan network can even degrade the banyan network performance, in spite of the multipath capability given by the additional stages. A class of new simple interstage protocols is here defined to operate in the added stages of the banyan network so that a sort of sharing of the queueing capability in each added stage is accomplished. Large improvements in the traffic performance of these extended banyan networks are obtained, especially in the region of offered loads providing a low packet loss probability     

New performance bounds of a class off self-routing networks

Conventional bounds for the maximum throughput of an unbuffered banyan network and its topology equivalents are based on the parallel path setup (PPS) assumption, i.e. paths are set up simultaneously. But the bounds derived under the PPS assumption can be surpassed with a slight variation on the path setup scheme. The authors study the maximum throughputs of an unbuffered banyan network and its topology equivalents in an incremental path setup (IPS) environment. The results represent the ultimate bounds for the maximum throughputs of unbuffered banyan networks. Although the exact analysis of this problem involves a combinatorial explosion, an approximate analysis is given in this work to verify the simulation results     

自由空间二维榕树网实现方法

鉴于榕树网在自由空间光子交换网络中具有重要的应用价值,分析了榕树网的特点和4×4二维榕树网的空间拓扑结构,通过偏振光分光棱镜、微闪耀光栅阵列、平面反射镜、半反半透镜和液晶空间光调制器的集成,构建二维的榕树交换网实验模块,利用微闪耀光栅的衍射特性,控制每块微闪耀光栅的周期,以实现入射光信号不同方向的闪耀输出,最终完成二维榕树网自由空间水平和竖直方向上的交叉互连,直通则由平面镜反射实现。对二维榕树网实验模块的功能分析表明,该实验模块理论上可以完成4×4二维面阵内光信号(或数据)的排序、交换、组播、广播、矩阵变换等操作,具有交换透明、速度快、空间带宽高等特点,在全光交换和光通信中具有一定的应用。     

A high-throughput energy-efficient passive optical datacenter network

Datacenter applications impose heavy demands on bandwidth and also generate a variety of communication patterns (unicast, multicast, incast, and broadcast). Supporting such traffic demands leads to networks built with exorbitant facility costs and formidable power consumption if conventional design is followed. In this paper, we propose a novel high-throughput datacenter network that leverages passive optical technologies to efficiently support communications with mixed traffic patterns. Our network enables a dynamic traffic allocation that caters to diverse communication patterns at low power consumption. Specifically, our proposed network consists of two optical planes, each optimized for specific traffic patterns. We compare the proposed network with its optical and electronic counterparts and highlight its potential benefits in terms of facility costs and power consumption reductions. To avoid frame collisions, a high-efficiency distributed protocol is designed to dynamically distribute traffic between the two optical planes. Moreover, we formulate the scheduling process as a mixed integer programming problem and design three greedy heuristic algorithms. Finally, simulation results show that our proposed scheme outperforms the previous POXN architecture in terms of throughput and mean packet delay.     

Reducing cell loss in banyan based ATM switching fabrics

In this paper, we propose a new technique for reducing cell loss in multi‐banyan‐based ATM switching fabrics. We propose a switch architecture that uses incremental path reservation based on previously established connections. Path reservation is carried out sequentially within each banyan but multiple banyan planes can be concurrently reserved. We use a conflict resolution approach according to which banyans make concurrent reservation offers of conflict‐free paths to head of the line cells waiting in input buffers. A reservation offer from a given banyan is allocated to the cell whose source‐to‐destination path uses the largest number of partially allocated switching elements which are shared with previously reserved paths. Paths are incrementally clustered within each banyan. This approach leaves the largest number of free switching elements for subsequent reservations which has the effect of reducing the potential of future conflicts and improves throughput. We present a pipelined switch architecture based on the above concept of path‐clustering which we call path‐clustering banyan switching fabric (PCBSF). An efficient hardware that implements PCBSF is presented together with its theoretical basis. The performance and robustness of PCBSF are evaluated under simulated uniform traffic and ATM traffic. We also compare the cell loss rate of PCBSF to that of other pipelined banyan switches by varying the switch size, input buffer size, and traffic pattern. Copyright © 2001 John Wiley & Sons, Ltd.     

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     

Data Center Switch for Load Balanced Fat-Trees

With the growing of cloud computing, the need of computing power no longer can be satisfied with a few powerful servers or small scale parallel computer systems. More and more servers are connected together as a data center network. Then, fault tolerance becomes an import issue when building a massive data center network. Currently, many researches focus on building fat-tree data center networks. In this paper, we propose a load balanced fat-tree architecture with uniform mapping connection patterns to provide higher fault tolerance capability for heavy traffic load networks. Two fault tolerated 4 × 4 banyan type switch designs are introduced to improve the fault tolerance capability of fat-tree networks. Finally, fault tolerance capability evaluations of link or switch faults in fat-tree network are given to support our idea, and a 4 × 4 banyan type switch IC is demonstrated as the commodity switch for building the fault tolerant fat-tree data center networks. The 4 × 4 banyan type switch IC is fabricated in 90 nm CMOS technology, and the maximum operation rate of the IC is 5.8 Gbps per channel or 23.2 Gbps total data rate with only 23 ps peak-to-peak jitter.     

Performance evaluation of input-buffered replicated banyan networks

Input-buffered replicated networks are considered for broadband switching applications. They are characterized by many design parameters such as the replication factor, the traffic management policy, and input buffer location and length. To show the influence of these parameters on switching performance, an analytical model is defined based on a Markov chain representation of the input buffer. This model is suitable for application to input buffered architecture having different routing network choices. The results, expressed in terms of throughput, packet delay, and packet loss probability, outline the performance improvements with respect to other well-known networks with input buffers, such as banyan and crossbar, reached through the flexibility offered by this architectural solution     

A survey of data multicast techniques, architectures, andalgorithms

This article presents a survey of architectures, techniques, and algorithms for multicasting data in communication switching networks. We start with a broadcast architecture using a separate copy network and a routing network. A few versions of this idea using Delta and Benes networks exist. Another multicast architecture is a recycling network where internal nodes act as relay points, accept packets from the switching fabric, and recycle them back into the fabric after relabeling the packets. Next, we give an overview of a system that uses the Boolean splitting multicast algorithm. In this system a nonblocking self routing broadcast banyan copy network has been proposed. The network consists of several components including a running adder network to generate running sums of copy numbers specified in the headers of input packets. We then describe a multicasting technique presented for a different class of switching networks called deflection-routing networks. Finally, the idea of extending a nonblocking network to a three-dimensional structure consisting of multiple parallel planes is also presented. At the end of this article, we compare the efficiencies of the presented multicast architectures     

The helical switch: a multipath ATM switch which preserves cellsequence

The paper presents a new cell switching architecture for ATM-based networks. The proposed helical switch is a multistage interconnection network which implements the self-routing technique with efficient buffer sharing. Although the switch may route cells along multiple paths, the connection-oriented mode required by the ATM-based network is supported. Cell sequence integrity is guaranteed by introducing a virtual helix which forces cells routed along different paths to proceed in order and fill the internal buffers uniformly. The performance of the helical switch is investigated under uniform and nonuniform traffic patterns. Unlike single-path multistage networks such as buffered banyan networks which can degrade significantly under nonuniform traffic, the helical switch is shown to be quite robust with respect to nonuniform traffic conditions     

A high-speed-retry banyan switch architecture for giga-bit-rate BISDN networks

This paper proposes a high-speed ATM switch architecture for handling cell rates of several Gb/s in a broadband communication switching system or cross-connect system. The proposed switch architecture, named the high-speed-retry banyan switch, employs a bufferless banyan network between input and output buffers; a cell is repeatedly transmitted from an input buffer until it can be successfully transmitted to the desired output buffer. A simple cell-retransmission algorithm, is employed as is a ring-arbitration algorithm for cell conflict. They are suitable for FIFO type buffers and bufferless highspeed devices. Good traffic characteristics which are independent of switch size are achieved for an internal speed ratio of only four times the input line speed. A prototype system with the internal speed of 1·2 Gb/s is constructed in order to confirm the basic operation of the high-speed-retry banyan switch. The prototype system, even in its present state, could be used to realize a giga-bit-rate BISDN switching system.     

Performance analysis of ATM banyan networks with shared queueing.I. Random offered traffic

The paper develops the analysis of multistage banyan interconnection networks in which the switching elements are provided with a buffer shared among all the inlets and outlets of the element. The packet transfer within the network takes place according to absence or presence of backpressure signals between adjacent stages. In this latter case four different modes for operating backpressure have been studied: local and global backpressure with acknowledgment or grant backward signaling. The paper describes three models for the analysis of these networks when loaded by a random traffic. These models are based on an increasing degree of accuracy (and hence of complexity) in the representation of the state of the generic switching elements. The accuracy of these models in evaluating the network performance is assessed in the paper also in comparison with the results given by previously proposed models     

The Batcher-banyan self-routing network: universality andsimplification

It is shown that the Batcher-banyan network performs as a universal self-routing switch when inputs with unassigned destinations are present. This is demonstrated by first proving that banyan networks can realize permutations represented by bitonic sequences, and then noting that the sorted output of the Batcher network can be viewed as a bitonic sequence. Two methods are proposed for reducing the complexity of the Batcher-banyan network. In the first method, one stage of the banyan network is eliminated by assigning proper destination tags to the unassigned inputs. In the second, a self-routing switch based on the binary-radix sorting scheme is shown to be more economical for a small number of lines     

Nonblocking property of reverse banyan networks

The authors present a new nonblocking property of the reverse banyan network under a particular input packet pattern at the input ports. The reverse banyan network is the mirror image of the banyan network. If the input packets of the N×N reverse banyan network have consecutive output address as modulo N, then the reverse banyan network is nonblocking. The routing of packets in the reverse banyan network is described, and the nonblocking property of the reverse banyan network is proved. A possible application of this property in the switching network is discussed