FB-banyans and FB-delta networks: Fault-tolerant networks for broadband packet switching

Many fast packet switches for the broadband integrated services digital network (BISDN) in the literature are based on banyan networks. Although banyan networks possess nice properties such as a simple control and a low hardware cost, they are unique-path networks. Since there is a unique path from an input to an output in a banyan network, a single component failure may disrupt services of some nodes connected to such a network. Moreover, banyan networks are also blocking networks; packets can be lost within the networks. To reduce the packet loss, buffered banyan networks can be used. In an earlier work we have proposed the addition of backward links to otherwise unidirectional banyan networks to create B-banyans (and B-delta networks). Backward links not only function as implicit buffers for blocked packets, but also provide multiple paths for each input-output connection. However, the multiple paths in B-banyans may not be disjoint. In this paper, we enhance B-banyans and B-delta networks in such a way that the resulting networks can provide disjoint multiple paths for each input-output pair. The existence of disjoint multiple paths has a significant effect on the network fault-tolerance. The new networks, called FB-banyans and FB-delta networks, are k fault-tolerant, where k is the number of backward links per switch and is less than the switch size. They are also robust to more than k faults, depending on the locations of faults. The maximal fault-tolerance is achieved when k is the switch size minus 1. The performance of the new networks is analysed and compared to that of other networks of interest. FB-banyans and FB-delta networks can be used as a switch fabric for fast packet switches to provide performance comparable to that of buffered banyan networks and good fault tolerance.     

An 8?×?8 20?Gbps Reconfigurable Load Balanced TDM Switch IC for High-Speed Networking

In this paper, we propose a reconfigurable load balanced symmetric TDM switch fabric. We fold this two-stage switch to reduce 50% hardware complexity, and then implement a 3.65?mm?×?3.57?mm prototype switch fabric IC, including a digital 8?×?8 switch core, eight 16B20B CODECs, eight SERDES ports, eight CML I/O interfaces and a PLL, in 0.18???m CMOS technology. The digital 8?×?8 switch core has reconfigurable connection patterns for the ease of scaling up to an N×N switch (N is power of 4). We propose the 16B20B CODEC scheme to reduce the switch core clock rate by half. In the SERDES, we employ the half-rate scheme and then use static CMOS gates for the low power consumption. We develop a low power, area-efficient and wide-band CML I/O interface with our patented PMOS active load inductive-peaking scheme for high-speed data transmission. With the 16B20B CODEC, the half-rate, and the PMOS active load schemes, almost 50% of the power is saved as compared with the design of the 8B10B CODEC, the full-rate and on-chip inductors CML schemes. Our measurement shows that an 8?×?8 switch fabric IC can achieve 20?Gbps switching rate and consumes only about 690?mW power. A terabit switch fabric can then be constructed by cascading the designed switch ICs.     

Rearrangeable f-cast multi-log2 N networks

Multi-log2 N networks (or vertically stacked banyan networks) have been an attractive class of switching networks due to their small depth O(logN), absolute signal loss uniformity and good fault tolerance property. Recently, F.K.Hwang extended the study of multi-log2 N networks to the generalf-cast case, which covers the unicast case (f = 1) and multicast case (f = N) as special cases, and determined the conditions for these networks to be f-cast strictly nonblocking when the fan-out capability is available at both the input stage and middle banyan stage. In this paper, we study the rearrangeable f-cast multilog2 N networks under both node-blocking scenario (relevant to photonic switches) and link-blocking scenario (relevant to electronic switches). In particular, we consider the following three fan-out cases in our study: 1) no restriction on fan-out capability; 2) input stage has no fan-out capability; 3) middle banyan stage has no fan-out capability. We determine the necessary conditions for the first two cases while obtaining the necessary and also sufficient condition for the third one.     

一种递归构造的合成BANYAN网络

该文提出了一种新的多路径多级互连网络——递归构造的合成BANYAN网络,网络由若干级3×3的开关组成.通过增加中间链路,解决了在已有的由Seo和Feng提出的合成BANYAN网上不能实现所有置换的问题.该网络无需复杂的数值计算,通过二进制操作就可以很容易的产生路由标志,得到更多的路径,从而大大提高了路由成功率和容错能力.该文中还给出了路由算法,并提出通过设置标识开关性能的标志位,使在路由时选取正确的路由标志,提前避开不起作用的开关,达到"预容错"的目的.     

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.     

业务需求感知的虚拟数据中心映射方法研究(英文)

Virtualization is a common technology for resource sharing in data center.To make efficient use of data center resources,the key challenge is to map customer demands(modeled as virtual data center,VDC) to the physical data center effectively.In this paper,we focus on this problem.Distinct with previous works,our study of VDC embedding problem is under the assumption that switch resource is the bottleneck of data center networks(DCNs).To this end,we not only propose relative cost to evaluate embedding strategy,decouple embedding problem into VM placement with marginal resource assignment and virtual link mapping with decided source-destination based on the property of fat-tree,but also design the traffic aware embedding algorithm(TAE) and first fit virtual link mapping(FFLM) to map virtual data center requests to a physical data center.Simulation results show that TAE+FFLM could increase acceptance rate and reduce network cost(about 49%in the case) at the same time.The traffic aware embedding algorithm reduces the load of core-link traffic and brings the optimization opportunity for data center network energy conservation.     

Banyan multipath self-routing ATM switches with shared buffer typeswitch elements

The asynchronous transfer mode (ATM) has been selected as the multiplexing and switching technique for use in the public broadband ISDN (B-ISDN). We propose a large-scale ATM switch architecture in which a banyan multipath self-routing network is combined advantageously with a shared buffer type switch element. The proposed banyan space-division concept yields a simple architecture having the potential to accommodate easily the growth of switch size. Since the interconnection network between switch modules or between switch elements has a twofold banyan architecture, expansion in crosspoints or interconnections with the increase of switch size can be lessened. The multipath self-routing concept makes the switch performance better and leads to an efficient realization of a switch element on a single chip as the fundamental building block of a large-size switch. We analyze the required capacity for queuing buffers in the switching network. The multipath approach inevitably creates information sequence disturbances. Therefore, we also analyze the out-of-sequence phenomenon of a banyan multipath switching system. To satisfy the sequence integrity requirement for ATM, a simple approach is proposed for the multipath switch by using a spacing controller. In addition, we quantify the improvement of out-of-sequence performance under the spacing controller scheme     

Architecture, performance, and implementation of the tandem banyanfast packet switch

The authors propose a new space-division fast packet switch architecture based on banyan interconnection networks, called the tandem banyan switching fabric (TBSF). It consists of placing banyan networks in tandem, offering multiple paths from each input to each output, thus overcoming in a very simple way the effect of conflicts among packets (to which banyan networks are prone) and achieving output buffering. From a hardware implementation perspective, this architecture is simple in that it consists of several instances of only two VLSI chips, one implementing the banyan network and the other implementing the output buffer function. The basic structure and operation of the tandem banyan switching fabric are described, and its performance is discussed. The authors propose a modification to the basic structure which decreases the hardware complexity of the switch while maintaining its performance. An implementation of the banyan network using a high-performance BiCMOS sea-of-gates on 0.8-μm technology is reported     

Neural network design of a banyan network controller

The algorithm for choosing nonblocking sets of data cells from the queues can significantly affect the throughput and queuing behavior. The authors present an algorithm that is shown to have maximum throughput. This algorithm is reduced on a banyan network to a constraint satisfaction problem by using an equivalence approach. To gain the required computational speed, the massive parallelism of neural networks is used. A neural network design using multiple overlapping winner-take-all circuits is defined. This is shown to be stable and to result only in nonblocking sets of data cells. An efficient interface between the neural network and the queue is also defined. The performance of the banyan with a neural network controller is compared to a noninternal-blocking switch with various controllers. The banyan is within a factor of two of the nonblocking switch     

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     

Performance evaluation of the augmented data vortex switch fabric: An all-optical packet switched interconnection network

Modern high-performance computing systems require networks with high capacity, extremely high throughput and low latency in order to pass messages between thousands of processors and memory elements. Optical Interconnection Networks (OIN) offer a potentially viable solution to this requirement. An all-optical packet switched interconnection network called a Data Vortex (DV) switch has already been proposed by Yang et al. for the purpose of large scale photonic interconnections. For any interconnection network, fault tolerance and reliability are crucial issues, evaluation of which lacked attention for the case of the DV switch. In our earlier work we therefore presented the results for fault tolerance and reliability analysis of the primary DV switch. We also proposed a new Augmented Data Vortex (ADV) switch fabric, to improve the fault tolerance of the primary DV switch. The performance as regards fault tolerance of the ADV switch was computed and detailed results were obtained. In this paper, performance of ADV is investigated with reference to parameters such as latency and injection ratio (throughput) by means of numerical simulations. A uniform random traffic model has been used for the performance evaluation. The results obtained are compared with the results reported for the DV switch. The results show that the ADV switch with enhanced fault tolerance also improves the performance regarding latency. For same switch sizes (i.e. the same number of angles A, and height H) the injection ratios (throughput) for the DV and the ADV switches are comparable. Hence it can serve as a suitable candidate for high performance computing.     

Fault tolerance mechanisms for virtual data center architectures

A virtual data center (VDC) is a combination of interconnected virtual servers hosted on a physical data center that hosts multiple such VDCs. This enables efficient sharing of the data center’s resources while handling dynamic resource requirements of the clients. The SecondNet architecture (Guo et al. in Proceedings of ACMSIGCOMM conference on data communication, Barcelona, pp 63–74, 2009) realizes this VDC concept and includes a centralized VDC resource-mapping (virtual to physical) algorithm. Fault tolerance is an important requirement in data center-based services, in order to increase reliability and availability. In this paper, we propose a fault tolerance mechanism to handle server failures by efficiently migrating the virtual machines (VMs) hosted on the failed server to a new location. Using our mechanism, it is shown that recovery from all the faults is possible, even for a server utilization of 90 %. In order to reduce the impact of server failures on the VDCs hosted in the data center, we then present a new load balancing scheme based on clustering that efficiently allocates the VDCs on the data center. Using this scheme, we were able to reduce the affected number of VMs per server failure by 63 %, in case of a BCube network of size 625 nodes, and by 86 %, in case of a BCube network of size 1,296 nodes.     

Switching integrated broadband services by sort-banyan networks

Substantial attention has recently been given to the implementation of sort-banyan networks for switching asynchronous transfer mode (ATM) transmission links in a BISDN (broadband integrated service digital network) network. The author gives a three-dimensional view of the theory and implementation of switching, as well as variations of the basic scheme. ATM switches are classified as blocking versus nonblocking, unicast versus multicast, and input queued versus output queued. Sorting networks structured by a three-dimensional interconnection topology are studied. A sorting network, when coupled with a banyan routing network structured in three dimensions, becomes a self-routing and nonblocking switching network. This three-dimensional topology allows CMOS VLSI implementations of the subnetworks and interconnection of these subnetworks at a speed of 150 Mb/s and beyond. The sorting mechanism can also be used for output conflict resolution, subsequently making the switch suitable for ATM switching. Recent enhancements, which provide features such as parallelism, trunk grouping, and modularity, are also described. These features enhance the throughput/delay performance, provide better fault and synchronization tolerance, and enable more economical growth for switch size     

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     

Performance Evaluation of Symmetric 8 × 10 Gbps TWDM-PON Incorporating Polarization Division Multiplexed Modulation Techniques Under Fiber-Impairments

Today’s access networks are in high demand to fulfill the high bandwidth requirement because of extensive improvement in high transmission rate applications for cloud computing, big data analytics, and other next-generation 5G smart applications. This exponential growth of high capacity and broadband access technologies comprise an essential trend in the development of a passive optical network (PON) access network. In this paper, 80/80 Gbps time wavelength division multiplexing PON (TWDM-PON) incorporating polarization division multiplexing (PDM) based Mach–Zehnder modulator (MZM) and electroabsorption modulator (EAM) techniques have been proposed. The performance of the system consisting of different polarized multiplexed modulation techniques is investigated in both downstream and upstream data transmission for variable transmission distance and received optical power in terms of bit error rate (BER), eye diagrams, power budget (PB) and receiver sensitivity. The results show that the 4?×?20/20 Gbps PDM-EAM modulated signals over 100 km fiber distance at ??60 dBm RS and 70 dB PB are successfully transmitted under fiber non-linearities. The proposed TWDM-PON system provides a next-generation long-reach access network from urban to rural areas.

     

Secure VM Migration in Cloud: Multi-Criteria Perspective with Improved Optimization Model

Distributed computing has risen as a well-known worldview for facilitating an assortment of online applications and services. The present business distributed computing stages utilize a semi concentrated design, where cloud resources, such as servers and storage are hosted in a few large global data centers. Virtualization in computing is a creation of virtual (not real) of something such as hardware, software, platform or an operating system or storage, or a network device. Further, Virtual Machine (VM) technology has recently emerged as an essential building block for data centers and cluster systems, mainly due to its capabilities of isolating, consolidating, and migrating workload. Migration of VM seeks to improve the manageability, performance, and fault tolerance of systems. In a virtual cloud computing environment, a set of submitted tasks from different users are scheduled on a set of Virtual Machines (VMs), and load balancing has become a critical issue for achieving energy efficiency. Thus to solve this issue and to achieve a good load balance, a new improved optimization algorithm is introduced namely Dual Conditional Moth Flame Algorithm (DC-MFA) that takes into account of proposed multi-objective functions defining the multi-constraints like CPU utilization, energy consumption, security, make span, migration cost, and resource cost. The performance of the proposed model will be analyzed by determining migration cost, energy consumption, and response time, and security analysis as well.

     

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.     

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     

Optical interconnections within modern high-performance computingsystems

Optical technologies are ubiquitous in telecommunications networks and systems, providing multiple wavelength channels of transport at 2.5-10 Gbps data rates over single fiber-optic cables. Market pressures continue to drive the number of wavelength channels per fiber and the data rate per channel. This trend will continue for many years to come as e-commerce grows and enterprises demand higher and reliable bandwidth over long distances. E-commerce, in turn, is driving the growth curves for single-processor and multiprocessor performance in data-base transaction and Web-based servers. Ironically, the insatiable taste for enterprise network bandwidth, which has driven up the volume and pushed down the price of optical components for telecommunications, is simultaneously stressing computer system bandwith-increasing the need for new interconnection schemes-and providing for the first time commercial opportunities for optical components in computer systems. This paper will center primarily on the use of optical interconnects within commercial digital computing systems, particularly workstations and servers, and will address mainly board-board interconnects within a single cabinet or box. We feel this is the most likely utilization of optics in commercial computer systems for the next decade. We will also provide a practical analysis of inter-and intrachip optical interconnects and the difficulties they face in real systems     

MatrixDCN: a high performance network architecture for large‐scale cloud data centers

With the widespread deployment of cloud services, data center networks are developing toward large‐scale, multi‐path networks. Conventional switching‐oriented data center network meets difficulties in terms of scalability and flexibility to support increasing bandwidth requirements for cloud services. To solve this problem, a simple and scalable architecture, MatrixDCN, is proposed in this paper. MatrixDCN is an approximate non‐blocking network, in which switches and servers are arranged in rows and columns that compose a matrix structure. A MatrixDCN network can accommodate up to hundreds of thousands of servers without bandwidth bottlenecks. Furthermore, the physical topology of a MatrixDCN network can be designed consistently with its logic topology, which helps to reduce the complexity of the management and maintenance of a data center. An efficient routing algorithm, named fault‐avoidance routing (FAR), is well designed for MatrixDCN to fully leverage the regularity in the topology. FAR builds two routing tables for a router. A BRT is built based on local topology, and a novel negative routing table (NRT) is increasingly built based on learned partial network failures, which really avoids the problem of network convergence and further shortens the calculating time of routing tables. FAR also greatly reduces the size of routing tables by introducing NRTs at routers. Theoretical analysis and simulations show that MatrixDCN has advantages on the scalability of topology, network throughput, and the performance of FAR. Copyright © 2015 John Wiley & Sons, Ltd.