一种近似无阻塞的置换三级Clos网

提出设计一种具有小阻塞概率、低硬件代价的的三级Clos网的方法.通过对阻塞概率与硬件代价的折衷,给出当端口利用率不是特别大时,具有小阻塞、低代价的三级Clos网模型,并且对端口利用率大的情况作了分析讨论.最后通过对于不同网络规模的比较可发现,对于所搭建的网络,其硬件代价比相应的严格无阻塞网络降低将近一半,而阻塞概率却非常小.     

通过改变开关状态实现多源点多播

在并行和分布式环境中 ,多个结点之间的通讯一直是研究工作的焦点问题 ,这些通讯主要包括置换、多播(Multicast)及多源点多播 (Multiple Multicast) .L ai提出了适用于一类与带缓存的 Cube网相互拓扑等价的网络的置换算法 ,硬件代价为 O(N log N ) ,算法的时间复杂度为 O(N ) .Feng提出的 inside- out算法实现了 Omega- 1 × Omega网上的置换 ,总的路由时间复杂度为 O(N log N) ,硬件代价为 O(N log N) .支持严格无阻塞置换的三级 Clos网的总的交叉点数为O(N32 ) .支持严格无阻塞的多播的三级 Clos网为 O(N32 logrloglogr) .Yang提出了一种新的多播网络 ,硬件复杂度为 O(N log2 N ) .为了支持多源点多播 ,多级互联网硬件代价往往大幅上升 .本文借鉴了 L ai提出的规则改变开关状态的方法 ,并把这种算法推广到了多源点多播的情况 .提出了一种新的多源点多播路由算法 ,此算法也同样适用于这一类相互拓扑等价的多级互联网 ,包括 Baseline、Om ega、Cube等 .在此算法中 ,每个数据流被划分为固定大小的数据包 ,在网络中独立传送 ,网络中的每个开关的状态按照固定的状态每个时步规则变化 ,每个数据包两次经过网络后到达目标结点 .此类的网络的硬件代价为 O(Nlog N ) ,此多源点多播路由算法的时间复杂度为 O(N )     

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

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

耐故障Clos网及其路由算法

提出了一种新的耐故障Clos网,通过在基础Clos网各段中增加冗余的交换单元,使其能够在发生少量故障的情况下正常工作,从而提供更可靠的服务。针对耐故障Clos网,给出一种耐故障Clos路由算法,该算法采用最小分布优先的策略逐列计算Clos网连接说明矩阵,通过重排完全实现无阻塞路由,该算法的时间复杂度在最坏情况下仅为O(N3/2)。该耐故障Clos网及其算法设计可以用于实现更为可靠的Clos网络。     

最小分布优先Clos网路由算法

提出了一种新的Clos网无阻塞路由算法、最小分布优先算法,用该算法可以降低Clos路由算法的高时间复杂度。对于Clos网连接说明矩阵,提出并证明了矩阵中某一列的完全性问题是一个独立的问题,并据此提出了以最小分布优先的方式逐列计算Clos连接说明矩阵的策略,消除了产生在矩阵列之间的回溯以及列内元素之间的回溯,能够完全实现无阻塞路由,在最坏情况下的时间复杂度为O(N3/2),可以应用于Clos网路由控制。     

基于二进制寻路法和多Omega网络的自路由无阻塞多级网

提出了一种可以无阻塞地传输其输入与输出间任意多播信号的新型自路由无阻塞多级网。该网络采用了循环重建法,以二进制扩散概念为基础。它由一个二进制扩散网络和两个二分之一大小的多播路由网络循环构建而成。多播信号由第一个Omega网复制并二分扩散到输出端口,进入N×N的Omega×Omega-1网络,再进入紧随其后的N/2×N/2的Omega×Omega-1网络……。每个Omega×Omega-1网络负责依照目的地址的有效标志位将输入置换到输出的上半部分和下半部分,再分别进入上下两个子Omega×Omega-1网络中做同样的处理,如此类推,直到全部地址有效位处理完毕,从而完成自路由无阻塞的多播传输。由于各大小不等的Omega×Omega-1网络皆可并行设置和并行路由,故此种新型多Omega网络的设置时间为O(NlogN),路由时间为O(log2N),硬件代价则为O(Nlog2N)。它比现行已知的多播网络设计具有较优的代价。     

一种基于Omega网的多播实现方案

介绍了一种基于Omega网结构的新型FuO网络模型,并基于该网络模型提出了无阻塞实现多播的解决方案.该网络由1个Omega-1 Omega网和1个简化的Omega-1×Omega网串连构成,其开关总数达到2NlogN-N/2.本文还对FuO网络模型进一步优化,提出了一种循环Omega-1×Omega网,开关总数达到2NlogN-N/2,比FuO网络大大降低,采用Omega网上的特定路由算法,可以无阻塞地实现任意多源点多播.     

一种新型的可重排多播网络

在并行分布式系统中，多播操作（包括一对多播送和多源点多播）是一种常见的操作，关于多播操作（尤其是多源点多播）的研究是一个有一定难度，但又具有重要应用价值的问题，也是目前升级互连网络研究领域中的一个热门课题，已有的关于多播的成果大多只针对现有的多级网络，并且一般只能实现单个多播。Yang在[3]中针对多源点多播的并发。提出了一种新的多播网络，硬件复杂度为O（Nlog^2N).本文提出了一种基于Omega网的多播网络（5－Omega网），通过重排各级开关的状态，可以并发的实现任意的多源点多播，所需开关元件总数为5／2NlongN,与Yang提出的多播网络相比，硬件代价小得多，同时，5－Omega网上的多播路由时间复杂度能达到O（NlogN)，在相关的成果中也算是最优的，并且由于Omega网的结构较为简单，这种网的硬件集成也非常容易，因此更具有实用价值，在这种网络的构造基础上，还提出了一种新的多播网络模型，为以后设计多播网络提供了一种参考方法。     

基于多QoS约束的多播路由算法研究

论文讨论了具有延迟、带宽和低代价等多QoS约束的多播路由算法,提出了适应于研究QoS多播路由的网络模型,并给出了一种具有多QoS约束的动态多播路由算法,分析了算法的复杂度。仿真实验证明,该算法是稳定有效的。它能够在满足多约束的情况下,使多播树的代价优化。     

新的基于MPH的时延约束Steiner树算法

为了在时延约束条件下进一步优化多播树代价并降低算法的复杂度,研究了时延受限的Steiner树问题。在DCMPH算法的基础上,通过改进节点的搜索路径,提出了一种新的基于MPH的时延约束Steiner树算法。该算法中每个目的节点通过最小代价路径加入当前多播树;若时延不满足要求,则通过合并最小时延树进而产生一个满足时延约束的最小代价多播树。仿真实验表明,新算法在性能、空间复杂度方面均优于DCMPH算法。     

Efficient architectures and algorithms for multicasting data in computer communication networks

This paper presents two network architectures with associated routing and multicast algorithms for improved performance under multicasting traffic conditions. A conditionally nonblocking network, referred to as a Clos network, forms the basis for the development of efficient multicast communication networks. The Clos network is first analyzed under multicast traffic conditions for blocking and multicast overflow probability. The analysis determines the overflow probability under two different multicast distribution assumptions. The first distribution assumes all packets request the same number of copies and the second distribution uses a random number of requested copies. An analysis of an extension of the presented network to multiplexed parallel planes of a network shows a significant improvement on the network performance and particularly on the carried traffic load when compared with previously published multicast architectures using different buffering strategies.     

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.     

A class of multistage conference switching networks for group communication

There is a growing demand for network support for group applications, in which messages from one or more sender(s) are delivered to a large number of receivers. Here, we propose a network architecture for supporting a fundamental type of group communication, conferencing. A conference refers to a group of members in a network who communicate with each other within the group. We consider adopting a class of multistage networks, such as a baseline, an omega, or an indirect binary cube network, composed of switch modules with fan-in and fan-out capability for a conference network which supports multiple disjoint conferences. The key issue in designing a conference network is to determine the multiplicity of routing conflicts, which is the maximum number of conflict parties competing a single interstage link when multiple disjoint conferences simultaneously present in the network. Our results show that, for a network of size n /spl times/ n, the multiplicities of routing conflicts are small constants (between 2 and 4) for an omega network or an indirect binary cube network; while it can be as large as /spl radic/n/q + 1 for a baseline network, where q is the minimum allowable conference size. Thus, our design for conference networks is based on an omega network or an indirect binary cube network. We also develop fast self-routing algorithms for setting up routing paths in the newly designed conference networks. As can be seen, such an n /spl times/ n conference network has O(logn) routing time and communication delay and O(nlogn) hardware cost. The conference networks are superior to existing designs in terms of routing complexity, communication delay and hardware cost. The conference network proposed is rearrangeably nonblocking in general, and is strictly nonblocking under some conference service policy. It can be used in applications that require efficient or real-time group communication.     

Convert-and-Deliver: a scalable multicast optical cross-connect with reduced power splitting fan-out

Powerful computing systems interconnected via high-bandwidth wavelength division multiplexing (WDM) fibers are becoming inevitable to meet the needs of emerging computation and communication applications. Enabling multicast over WDM links requires the use of multicast-capable optical cross-connects (MC-OXCs) equipped with power splitters to replicate and interconnect an input signal on a particular wavelength to one or more output fibers, possibly on different wavelengths. All existing design approaches for FW×FW strictly nonblocking MC-OXCs with F fibers, each carries W wavelengths require the use of power splitters with a fan-out degree of O(FW). For typical large values of F and W, complex and power-consuming active devices are needed to compensate for the lost power due to splitting. In this paper, we propose a new class of strictly nonblocking MC-OXC, namely, the Convert-and-Deliver (CAD) cross-connect to reduce power consumption. The new CAD OXC uses power splitters with a fan-out degree of only O(F) instead of O(FW). It is shown that, making the fan-out degree independent of W in the proposed design does not only reduce splitting power loss considerably, but it also enhances the scalability of the design. In particular, for any value of F, upgrading the number of wavelengths per fiber does not incur any changes to the fan-out degree or the power loss in the used splitters; a feature that cannot be obtained with any existing MC-OXC design approach.     

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     

Scalable and Practical Nonblocking Switching Networks

Large-scale strictly nonblocking （SNB） and wide-sense nonblocking （WSNB） networks may be infeasible due to their high cost. In contrast, rearrangeable nonblocking （RNB） networks are more scalable because of their much lower cost. However, RNB networks are not suitable for circuit switching. In this paper, the concept of virtual nonblockingness is introduced. It is shown that a virtual nonblocking （VNB） network functions like an SNB or WSNB network, but it is constructed with the cost of an RNB network. The results indicate that for large-scale circuit switching applications, it is only needed to build VNB networks.     

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.     

Multicast routing protocols in wireless mesh networks: a survey

Wireless mesh networks (WMNs) introduce a new type of network that has been applied over the last few years. One of the most important developing issues in WMNs is multicast routing, which is a key technology that provides dissemination of data to a group of members in an efficient way. In this article, after an introduction about the structure of a WMN, multicast routing algorithms and protocols in WMNs are surveyed in a detailed and efficient manner. Moreover, effort is made to scale the study into one of the important potential capabilities of multicast routing mechanisms in WMNs, which is taking advantage of using different channels and radios association. While nodes in a single-radio mesh network operating on single-channel have restrictions for capacity, equipping mesh routers with multiple radios using multiple channels can decrease the intention of capacity problem as well as increase the aggregate bandwidth available to the network and improving the throughput. Hence, the purpose of channel assignment is to decrease the interferences while increasing the network capacity and keeping the connectivity of the network. Therefore, this article investigates the multicast protocols considering a definition of three types of WMNs, based on channel-radio association including SRSC, SRMC and MRMC. In its follow, a classification for multicast routing algorithms regarding the achieved optimal solutions will be presented. Finally, a study of MRMC and its relevant problems will be offered, considering the joint channel assignment and the multicast tree construction problem.