Parallel routing algorithms for nonblocking electronic and photonic switching networks

We study the connection capacity of a class of rearrangeable nonblocking (RNB) and strictly nonblocking (SNB) networks with/without crosstalk-free constraint, model their routing problems as weak or strong edge-colorings of bipartite graphs, and propose efficient routing algorithms for these networks using parallel processing techniques. This class of networks includes networks constructed from banyan networks by horizontal concatenation of extra stages and/or vertical stacking of multiple planes. We present a parallel algorithm that runs in O(lg/sup 2/ N) time for the RNB networks of complexities ranging from O(N lg N) to O(N/sup 1.5/ lg N) crosspoints and parallel algorithms that run in O(min{d* lg N, /spl radic/N}) time for the SNB networks of O(N/sup 1.5/ lg N) crosspoints, using a completely connected multiprocessor system of N processing elements. Our algorithms can be translated into algorithms with an O(lg N lg lg N) slowdown factor for the class of N-processor hypercubic networks, whose structures are no more complex than a single plane in the RNB and SNB networks considered.     

2-Dilated flattened butterfly: A nonblocking switching topology for high-radix networks

High-performance computing is highly dependent on the communication network connecting the nodes. In this paper, we propose a 2-Dilated flattened butterfly (2DFB) network which provides non-blocking performance for relatively low cost overhead. We study the topological properties of the proposed 2DFB network and compare it with different nonblocking switching topologies. We observe that a dilation factor of two is sufficient to obtain nonblocking property for a flattened butterfly structure irrespective of its size or dimension. Dilating each link in a flattened butterfly causes an increase in cost. Therefore, we modeled the implementation cost of a 2DFB network and compared it with other popular nonblocking networks. We observe that the cost of a 2DFB is less than other nonblocking networks, while at the same time providing reduced latency because of its reduced diameter and hop count. We also propose a procedure to develop a conflict-free static routing schedule as well as an adaptive load balanced routing scheme (ALDFB) for 2DFB networks. Finally, we also describe the hardware implementation of a 2DFB network using the NetFPGA as the switching element and verify the nonblocking behavior of a 2DFB. We also show that the 2DFB topology can be used to build high speed switching systems with reduced cost.     

严格无阻塞多播三级Clos网的优化

如何在严格无阻塞情况下保持最低的硬件代价,是多播三级Clos网设计中的一个重要问题.提出一种优化网络硬件代价的方法,分别给出了在没有多播受限和中间级多播受限两种情况下,严格无阻塞多播三级Clos网硬件代价的最优值.分析表明,优化后网络的硬件代价得到了有效降低,在某些情况下甚至低于广义无阻塞网.同时,与广义无阻塞网相比,该网络无需特定的路由算法就能始终保持严格无阻塞状态,在一定程度上降低了时间复杂度.     

一种严格非阻塞Clos型波分复用光置换网络

波分复用光交换网络设计中的一个重要问题是如何在提供完全连接能力的同时保持最低的硬件代价.这里采用波长交换原理,提出一种能同时完成空间交换和波长转换的交叉开关,并将其作为基本模块构造出严格非阻塞Clos型波分复用光置换网络.与现有网络相比,该网络不需要额外的波长转换级,减小了信号衰减;降低了整体硬件代价,在空间交换代价和波长转换代价之间取得了很好的平衡,并具有较好的扩展性.     

Multi-log2N交换网络的性能分析模型及控制算法

高速多平面交换网络解决了其内部冲突问题,但需要相应的路由控制算法的辅助,否则,内部冲突不能彻底解决.这是因为包在输入级路由平面的选择不够恰当,容易导致路由冲突的产生.因此,根据冲突链路集的思想,给出一种Multi-log₂N交换网络的控制算法.该算法控制分组在路由平面间的选择,不仅能够适用于RNB和SNB,还能实现单播和多播的控制,保障Multi-log₂N完全实现无阻塞.另一方面,Multi-log₂N消除了内部的链路冲突,提高了交换速率,但对其交换性能缺乏系统的理论分析.给出一种基于嵌入式马尔可夫链的分析模型,对Multi-log₂N网络中队列的使用及分组在队列中的平均等待时间、平均队长等相关性能指标进行了系统的分析,为基于Multi-log₂N的光交换节点的设计提供了良好的理论依据.     

A method to evaluate the spatial extensibility of a switching unit and network

Switching units and networks have been analyzed as extensible fabrics,mostly in terms of their scheduling algorithms.The traditional literature on switching extensibility has provided complexity theory only relating to the total numbers of inputs(or outputs)and exchange lines.This paper analyzes switching extensibility in terms of not only the scheduling algorithm and also the fabric itself.It is found that determining extensibility from soft complexity related to the number of inputs(or outputs)of the scheduling algorithm and the fabric extensibility in previous studies without quantization is a flawed conception.A method is thus proposed to express the spatial extensibility of a switching unit or network in terms of the connections of a switching resource and capacity.The method calculates parameter ES(the efciency of switching)of an m×n switching unit and obtains two functions of the switching unit to describe spatial extensibility along with the number of unilateral inputs or outputs.It is found that the range of ES is(0,1]and three types of switching unit and two types of crosspoint networks have ES=1.ES is calculated for banyan,Clos,parallel packet,fully interconnected and recirculation switching networks.The ES value for the banyan switching network is larger than that for other networks,and switching networks are classified into three types that have absolute/linear/denied spatial extensibility according to the limES value.It is demonstrated that a switching network has the largest ES value when it contains only the five types of switching unit for which ES=1.Finally,a group-switching-first self-routing banyan switching network with lower blocking probability and time delay is deduced,and the ES method is contrasted with two other methods of evaluating spatial extensibility in terms of their mathematical expressions and intuitive graphics,for the five types of switching network listed above.     

Maximally permissive mutually and globally nonblocking supervision with application to switching control

A supervisor is said to be mutually nonblocking with respect to a pair of specifications if upon completing a task in any of the specifications, it can continue on to complete the task in the other specification, i.e., the two specifications do not block each other. The notion of mutually nonblocking supervisor was introduced in Fabian and Kumar [2000. Automatica, 36(12), 1863-1869]. In this paper, we present an algorithm of polynomial complexity for computing a maximally permissive mutually and globally nonblocking supervisor. In case such a supervisor does not exist, we present a technique for relaxing the specifications for which a supervisor exists. The algorithms are based on a notion of attractability, and as a special case offer a new way of computing the maximally permissive nonblocking supervisors. The results are then applied to design of maximally permissive switching supervisors so as to allow for switching between the specifications at any time while the system is executing.     

A Comparative Study of Switching Methods in Multicomputer Networks

The switching method determines the way messages visit intermediate routers, and has a great impact on network performance. This paper conducts an extensive comparative performance analysis, by means of analytical modelling, of three well-known switching methods proposed for multicomputer networks, namely wormhole switching, circuit switching, and pipelined circuit switching. The results reveal that wormhole switching is the most efficient when messages are short. Pipelined circuit switching can perform better than circuit switching and provides superior performance over wormhole switching when messages are relatively long.     

构建网络的新方法：基于环路的混合交换光网络*

为了能够更好地支持突发性数据业务,提出了一种新型网络交换结构——基于环路的混合交换光网络（cyclebased hybrid switching optical networks,CHSON）。该网络结合了光电路交换（OCS）和光突发交换（OBS）两种交换技术,不仅可以有效地降低网络节点的分组转发压力,而且能够较好地承载突发性数据业务。首先介绍了CHSON的网络结构和虚拓扑设计,然后阐述了节点设计及其执行流程。仿真表明,CHSON具有比OCS网络更低的丢包率,而且在丢包率和平均分组延时方面,CHSON较     

Nonblocking WDM multicast switching networks

With ever increasing demands on bandwidth from emerging bandwidth-intensive applications, such as video conferencing, E-commerce, and video-on-demand services, there has been an acute need for very high bandwidth transport network facilities. Optical networks are a promising candidate for this type of applications. At the same time, many bandwidth-intensive applications require multicast services for efficiency purposes. Multicast has been extensively studied in the parallel processing and electronic networking community and has started to receive attention in the optical network community recently. In particular, as WDM (wavelength division multiplexing) networks emerge, supporting WDM multicast becomes increasingly attractive. In this paper, we consider efficient designs of multicast-capable WDM switching networks, which are significantly different and, hence, require nontrivial extensions from their electronic counterparts. We first discuss various multicast models in WDM networks and analyze the nonblocking multicast capacity and network cost under these models. We then propose two methods to construct nonblocking multistage WDM networks to reduce the network cost     

Banyan分组交换网络非阻塞方法探讨

文中简述了banyan网络的性质及几种非阻塞方法,对其非阻塞条件进行了论证,指出通过排序网络的分组能部分满足这些条件,并提出了排序网络的一般结构及其算法。利用排序网络、反馈环路和并行banyan网络等部件组成的网络不但能避免分组的内部阻塞,而且能防止输入输出碰撞,使分组丢失概率大大减小。     

A power consumption sensitivity analysis of circuit-switched versus packet-switched backbone networks

While telecommunication networks have historically been dominated by a circuit-switched paradigm, the last decades have seen a clear trend towards packet-switched networks. In this paper we evaluate how both paradigms (which have also been referred to as optical bypass and non-bypass, respectively) perform in optical backbone networks from a power consumption point of view, and whether the general agreement of circuit switching being more power-efficient holds. We consider artificially generated topologies of various sizes, mesh degrees and – not yet previously explored in this context – transport linerates. We cross-validate our findings with a number of realistic topologies.Our results show that circuit switching is preferable when the average node-to-node demands are higher than half the transport linerates. However, packet switching can become preferable when the traffic demands are lower than half the transport linerate. We find that an increase in the network node count does not consistently increase the energy savings of circuit switching over packet switching, but the savings are heavily influenced by the mesh degree and (to a minor extent) by the average link length. Our results are consistent for uniform traffic demands and realistic traffic demands.A key take-away message for other research on power saving solutions in backbone networks is that the ratio between the average demand and the demand bitrate has considerable effect on the overall efficiency, and should be taken into account.     

Performance considerations for integrated voice and data networks

Performance considerations, particularly network delays, for integrated voice and data networks are reviewed. The nature of the delay problem is discussed, followed by a review of concepts, objectives and advances in enhanced circuit, packet and hybrid switching techniques, including fast circuit switching (FCS), virtual circuit switching (VCS), buffered speech interpolation (SI), packetized virtual circuit (PVC), cut-through switching (CTS), composite packets and various frame-management strategies for hybrid switching.In particular, the concept of introducing delay to resolve contention in SI is emphasized and, when applied to both voice talkspurts and data messages, this forms a basis for a relatively new approach to network design called transparent message switching (TMS). This approach and its potential performance advantages are reviewed in terms of various architectural aspects of integrated services networks, such as packet structure, multiplexing scheme, server structure and queuing performance, network topology and network protocols.A number of traffic-management strategies and their grade-of-service implications for voice service are discussed. These strategies include voice call and data session blocking, voice talkspurt and data message buffering, speech loss and data integrity and speech processing techniques, including variable quality, rate, speed and entropy coding. Emphasis is placed on the impact of variable delays on voice traffic, especially the importance of generating and preserving appropriate length speech talkspurts in order to mitigate the effects of variable network delay.     

网络编码下不可靠自组织网络高效路由算法

无线自组织网络(wireless ad hoc network)中链路的不可靠性与高丢包率是影响网络性能和应用的主要缺陷.为了优化多跳的不可靠无线网络中完成数据传输所需的数据分组发送次数,提出了融合路径切换思想的基于网络编码的路由协议(network coding routing with path switching,简称NCPS).为了发现潜在的适合网络编码的路径,首先分析并提出了网络中路径可编码与可解码条件;其次对比于传统的最优路径,分析得出了在网络编码下路径切换所能获取的编码收益;最后以优化网络中数据分组发送次数为目标,设计了网络编码下结合路径切换的路由协议.实验结果表明,在不同的网络环境参数下,NCPS能够有效减少网络中的数据发送次数,获取稳定的编码收益.     

Using Augmented Infinitesimal Perturbation Analysis for Capacity Planning in Intree ATM Networks

Augmented Infinitesimal Perturbation Analysis is used to determine asymptotically unbiased and strong consistent gradient estimates for use in the capacity planning of intree ATM networks. These gradients are used to determine the locally optimal minimum average network delay by applying a steepest descent algorithm with projection and an Armijo line search to solve the capacity assignment (CA) problem. The network capacities are governed by a linear cost constraint. It is assumed that input regulators (e.g., leaky bucket regulators) are used at the source of each virtual circuit. All virtual circuit external arrivals are modeled as independent Poisson processes. Regenerative simulation is used to determine gradient estimates.     

Hybrid circuit-switched network for on-chip communication in large-scale chip-multiprocessors

Large-scale chip-multiprocessors (CMPs) need a scalable communication structure characterized by low cost, low power, and high performance to meet their on-chip communication requirements. This paper presents a hybrid circuit-switched (HCS) network for on-chip communication in the large-scale CMPs. The HCS network, which is Advanced Microcontroller Bus Architecture (AMBA) compatible, is composed of bufferless switches, pipeline channels, and network interfaces. Furthermore, packets are transferred in a hybrid transmission scheme. If a message has only one packet, the transmission scheme for this message is packet switching. Conversely, if a message contains multiple packets, the transmission scheme for this message is circuit switching. We evaluate HCS networks with different channel depths and then compare the HCS network with the Stanford elastic buffer (EB) network. Our results show that the HCS network with two-depth channel requires 83% less power and occupies 32% less area compared with the EB network. Furthermore, under maximum frequency and single traffic, the HCS network with two-depth channel provides 37% lower zero-load latency, 390% higher maximum throughput per unit power, and 19% higher maximum throughput per unit area compared with the EB network.     

2阶多智能体网络在切换拓扑下的群一致性

针对2阶多智能体网络的群一致性问题,提出了基于牵引控制方法的群一致性协议.考虑到网络模型具有切换拓扑结构,在模型中引入相应的虚拟领导者.对于网络中的每一个智能体,其一致性协议依赖于智能体邻居的状态及速度信息,并受到虚拟领导者的牵引控制;进一步地,来自虚拟领导者的牵引控制可以随时间发生变换.利用代数图论、线性矩阵不等式和李亚普诺夫稳定性理论,对网络进行群一致性分析,给出了切换拓扑下2阶多智能体网络达到群一致性的充分条件.最后,数值仿真验证了理论结果的有效性.     

Modelling and analysis of pipelined circuit switching in interconnection networks with bursty traffic and hot-spot destinations

Pipelined circuit switching (PCS) that combines the advantages of both circuit switching and wormhole switching is an efficient method for passing messages in interconnection networks. Analytical modelling is a cost-effective tool and plays an important role in achieving a clear understanding of the network performance. However, most of the existing models for PCS are unable to capture the realistic nature of message behaviours generated by real-world applications, which have a significant impact on the design and performance of communication networks. This paper presents a new analytical model for PCS in interconnection networks in the presence of bursty and correlated message arrivals coupled with hot-spot destinations, which can capture the bursty message arrival process and non-uniform distribution of message destinations. Such a traffic pattern has been found in many practical communication environments. The accuracy of the proposed analytical model is validated through extensive simulation experiments. The model is then applied to investigate the effects of the bursty message arrivals and hot-spot destinations on the performance of interconnection networks with PCS.     

Nonblocking k-fold multicast networks

Multicast communication involves transmitting information from a single source to multiple destinations and is a requirement in high-performance networks. Current trends in networking applications indicate an increasing demand in future networks for multicast capability. Many multicast applications require not only multicast capability, but also predictable communication performance such as guaranteed multicast latency and bandwidth. In this paper, we present a design for a nonblocking k-fold multicast network, in which any destination node can be involved in up to k simultaneous multicast connections in a nonblocking manner. We also develop an efficient routing algorithm for the network. As can be seen, a k-fold multicast network has significantly lower network cost than that of k copies of ordinary 1-fold multicast networks and is a cost effective choice for supporting arbitrary multicast communication.     

企业网中的VLAN设计初探

随着网络技术的发展和信息应用的爆炸式增长,企业对网络应用的需求与日剧增,但是传统的网络应用难以满足传统基于以太网的帧交换和基于ATM的信元交换,当工作站数量较多和信息流较大时,轻易形成广播风暴,严重影响了网络运行速度,甚至造成网络瘫痪。为避免这个问题采用了划分网络的办法。