A more accurate analytical model on blocking probability of multicast networks

Multicast communication is one of the most important collective communication operations and is highly demanded in telecommunication environments and scalable parallel and distributed computing systems. In this paper, we consider the issue of supporting multicast in the widely used a three-stage Clos network or /spl upsi/(m,n,r) network. We improve a previously proposed analytical model (Yang and Wang 1998) for the blocking probability of the /spl upsi/(m,n,r) multicast network by introducing more reasonable assumptions based on the properties of multicast communication and the Clos network. We also compare the improved analytical model with the simulation results under three typical routing control strategies. As can be seen, the improved model matches better with the simulation results and further confirms that a /spl upsi/(m,n,r) network with a comparable cost to a permutation network is almost nonblocking for multicast connections.     

A new design for wide-sense nonblocking multicast switching networks

In this paper, we propose a new design for a wide-sense nonblocking multicast switching network, which has many comparable properties to a strictly nonblocking Clos permutation network. For a newly designed four-stage N/spl times/N multicast network, its hardware cost, in terms of the number of crosspoints, is about 2(3+2/spl radic/2)N/sup 3/2/=11.66N/sup 3/2/, which is only a small constant factor higher than that of a three-stage nonblocking permutation network, and is lower than the O(N/sup 3/2/(logN/loglogN)) hardware cost of the well-known three-stage wide-sense nonblocking multicast network. In addition, the proposed four-stage nonblocking multicast network has a very simple routing algorithm with sublinear time complexity, and does not require multicast capability for the switch modules in the input stage.     

Blocking and nonblocking multirate Clos switching networks

This paper investigates in detail the blocking and nonblocking behavior of multirate Clos switching networks at the connection/virtual connection level. The results are applicable to multirate circuit and fast-packet switching systems. Necessary and sufficient nonblocking conditions are derived analytically. Based on the results, an optimal bandwidth partitioning scheme is proposed to reduce switch complexity while maintaining the nonblocking property. The blocking behavior of blocking switches supporting multicast connections is investigated by means of simulation. We propose a novel simulation model that filters out external blocking events without distorting the bandwidth and fanout (for multicasting) distributions of connection requests. In this way, the internal blocking statistics that truly reflect the switch performance can be gathered and studied. Among many simulation results, we have shown that for point-to-multipoint connections, a heuristic routing policy that attempts to build a narrow multicast tree can have relatively low blocking probabilities compared with other routing policies. In addition, when small blocking probability can be tolerated, our results indicate that situations with many large-fanout connection requests do not necessarily require a switch architecture of higher complexity compared to that with only point-to-point requests     

Performance of split routing algorithm for three-stage multicastnetworks

This paper studies three-stage Clos (1953) switching networks for multicast communications in terms of their blocking probabilities on a random traffic model. Even though the lack of multicast capability in input-stage switches requires a prohibitively large number of middle switches to provide compatible requests with nonblocking paths, the probabilistic model gives an observation that the blocking probability decreases drastically and then approaches zero as the number of middle switches is far less than the theoretical bound. The S-shaped curves of blocking probability versus degree of fanout indicate that high fanout requests are mostly blocked at some given reference network utilization. A split routing algorithm and its blocking probability are introduced to enhance the routability of the high fanout requests. We also corroborate the analytic model by performing network simulations based on a random request generator and a random routing strategy     

支持多时隙业务的MTS-Clos网络结构及其建模分析

多级Clos网络是一种典型的可扩展交叉互连结构,在数据通信和计算机并行网络中有着广泛应用。基于传统三级Clos网络C(m, n, r)的理论分析表明,当满足m2n-1时该网络是严格无阻塞的。该文针对多时隙业务,利用可快速实现时隙交叉的单级交换模块,构建了一种新型的MTS-Clos交换网络结构C(m, n, r)(Multiple Time Slot Clos network)。利用时隙交叉能力,该结构在保留原有网络特性的同时可提供更为理想的交换性能。采用随机分析模型,对该结构的阻塞率进行了理论分析,结果表明当中间级规模m=n+k, k是一个很小的非负整数,网络即达到无阻塞。对该结构的数值仿真有同样的结论。因此,该结构及分析结果对下一代大容量交换设备的设计,具有良好的参考价值。     

Multicast nonblocking switching networks

This paper considers three-stage switching networks for which nonblocking conditions with point-to-point traffic are given by the well known Clos (1953) theorem, under the assumption of absence of any optimized routing of the connections inside the network. We give the conditions for such a network to be strict-sense nonblocking under multicast traffic, by showing also that previously published papers, although claiming the same result, only provided sufficient conditions.     

基于共享路径和网络编码的光组播容量优化

为了降低光组播路由 的光域网络编码代价和提高达到理论最大光组播容量的 概率,提出一种基于共享链路和网络编 码的优化光组播容量方法。首先设计一种从多条源－ 宿最短路径中选择能达到最大光组播容量的最短路径簇,然后在 最短路径簇中计算路径的共享度,选择共享度高的组播路径传输网络编码信息,构造网络编 码次数最少的光组播编码子图, 解决传统的网络编码组 播路由和最大共享度链路组播路由中存在的网络编码次数过多和达到最大光组播容量概率过 低的问 题。仿真结果表明:本文提出的方法具有最低的网络编码代价,能以最大的概率达到光组播 理论最大容量。     

A virtually nonblocking self-routing permutation network which routes packets in O(log2 N) time

Asymptotically nonblocking networks are O(log₂ N) depth self-routing permutation devices in which blocking probability vanishes when N (the number of network inputs) increases. This behavior does not guarantee, also for very large N, that all information always and simultaneously reaches its destination (and consequently that a whole permutation passes through the device) which is a requirement of the PRAM machine. In this work the conditions for which an asymptotically nonblocking network becomes asymptotically permutation nonblocking are studied, finally a virtually nonblocking device is obtained by a retransmission procedure which guarantees that all permutations always pass through this permutation device. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multicast wavelength assignment with sparse wavelength converters to maximize the network capacity using ILP formulation in WDM mesh networks

In general, multicast routing and wavelength assignment (MC-RWA) can be subdivided in routing and wavelength assignment issues in wavelength-division multiplexing (WDM) mesh networks. Previous studies on WDM multicast have mainly focused on WDM multicast routing. The multicast wavelength assignment problem is studied in this paper. A unicast routing path can be established by a lightpath in an all-optical network. However, in the multicasting case, a multicast routing tree can be established by a single light-tree or several lightpaths, or a combination of several light-trees and lightpaths. We propose a wavelength assignment algorithm for finding an optimal combination of lightpaths and light-trees to construct a newly required multicast session. First of all, two cost functions are given to evaluate the establishing cost for each feasible wavelength, and then find a set of wavelengths that covers all destinations with the minimal cost using Integer Linear Programming (ILP) formulation. We focus on maximizing the total number of users served in a multicast session and the network capacity. The simulation results show that the proposed algorithm can improve system resource utilization and reduce the blocking probability compared with the First-Fit algorithm.This research was partially supported by the Grant of National Science Council, R.O.C. (NSC 94-2745-E-155-007-URD).     

Optimization of splitting node placement in wavelength-routed optical networks

This paper addresses the placement of multicast nodes in wavelength-routed all-optical networks. This problem is motivated by the expected high cost of optical multicast cross-connects due to fabrication complexity and power considerations. An analytical model for the approximate blocking probability in multicast networks is developed. The blocking performance is used to guide an iterative algorithm, Multicast-ADD, for the placement of multicast nodes. We provide validation of the model and the techniques used. In addition, a simulation study is provided to evaluate the performance of the heuristic. Insights obtained from the simulation results reveal that: (1) only a subset of the nodes (found to be 50%) need to be multicast-capable for acceptable blocking performance; (2) the blocking performance of Multicast-ADD outperforms that of random placement; and (3) employing alternate routing trees is not helpful in the optimization procedure.     

Power-efficient design of multicast wavelength-routed networks

In this paper, we introduce the power-efficient design space for multicast wavelength-routed networks. The power-efficient design space is based on the impact of power on the overall design of wavelength-routed networks. Two cross-connect architectures on this design concept are investigated. One is an existing architecture called splitter-and-delivery (SaD). The other is a new architecture called multicast-only splitter-and-delivery (MOSaD). The MOSaD architecture uses power splitters for multicast connections only, allowing unicast connections to pass without enduring unnecessary power losses. Our cross-connect design provides a strictly nonblocking service for unicast connections while eliminating unnecessary power loss of the SaD cross-connect. Experimental results demonstrate that the MOSaD architecture provides substantial savings in cost and reduction in signal power loss with minimal effects on the blocking performance of the network.     

An analytical model on network blocking probability

We present a new analytical model on the blocking probability of the three-stage Clos (1953) network. Due to the effect of approximations, a common problem with previously proposed analytical models is that they may not be very accurate in some cases. In particular, the blocking probability in these models contradicts the well-known deterministic nonblocking condition for the Clos network. The most notable feature of the newly proposed model is that it can more accurately describe the blocking behavior of the network and is consistent with the deterministic nonblocking condition     

基于多条件约束的ASON动态组播路由算法

在将自动交换光网络(ASON)建模成着色多重图的基础上采用综合成本策略,设计了一种新的最小综合成本路径计算算法,并结合组播成员的动态变化特性提出一种满足多条件约束的动态组播路由(DMRMC)算法,使组播路由和波长分配在同一过程内完成,且尽可能使组播树的综合总成本最小,同时局部优化波长转换次数、分光次数和不同波长的使用数量。仿真实验表明,本文算法有效可行,与采用单成本策略的组播算法相比,其取得了更低的综合成本和更好的连接阻塞性能。     

Design of wide-sense nonblocking multicast ATM switches

Nonblocking multicast asynchronous transfer mode (ATM) switches can simplify the call admission control process and increase the external links' utilization. We derive the wide-sense nonblocking condition for multicast ATM switches based on a general Clos network. We also propose a routing algorithm to achieve wide-sense nonblocking. It is illustrated by an example that the number of required middle stages in our switch is significantly less than that of strictly nonblocking multicast switches     

Resource requirements and layouts for field programmableinterconnection chips

Field-programmable interconnection chips (FPIC's) provide the capability of realizing user programmable interconnection for any desired permutation. Such an interconnection is very much desired for supporting rapid prototyping of hardware systems and for providing programmable communication networks for parallel and distributed computing. An FPIC should realize any possible permutation of input to output pins via a set of programmable switches. In this paper, we show that any such architecture requires a minimum of Ω(n log n) switches, where Ω is the number of I/O pins. The result stems from an analysis of the underlying permutation network. In addition, for networks of bounded degree d, we prove an Ω(log_d-1 n) bound on the routing delay (maximum length of routing paths for specific I/O permutations) and an Ω(n log_d-1 n) bound on the average utilization of programmable switches used by the FPIC to implement a specific permutation. For the same type of networks, we prove an Ω(n log_d-1 n) bound on the number of nodes of the network. Furthermore, we design efficient architectures for FPIC's offering a wide variety of routing delays, high average programmable resource utilization, and O(n²)-area two-layer layouts. The proposed structures are called hybrid Benes-Crossbar (HBC) architectures and clearly exhibit a tradeoff between performance (routing delay utilization) and area of the layout     

Dynamic Multicast Session Provisioning in WDM Optical Networks with Sparse Splitting Capability

In this work, we study dynamic provisioning of multicast sessions in a wavelength-routed sparse splitting capable WDM network with an arbitrary mesh topology where the network consists of nodes with full, partial, or no wavelength conversion capabilities and a node can be a tap-and-continue (TaC) node or a splitting and delivery (SaD) node. The objectives are to minimize the network resources in terms of wavelength-links used by each session and to reduce the multicast session blocking probability. The problem is to route the multicast session from each source to the members of every multicast session, and to assign an appropriate wavelength to each link used by the session. We propose an efficient online algorithm for dynamic multicast session provisioning. To evaluate the proposed algorithm, we apply the integer linear programming (ILP) optimization tool on a per multicast session basis to solve off-line the optimal routing and wavelength assignment given a multicast session and the current network topology as well as its residual network resource information. We formulate the per session multicast routing and wavelength assignment problem as an ILP. With this ILP formulation, the multicast session blocking probability or success probability can then be estimated based on solving a series of ILPs off-line. We have evaluated the effectiveness of the proposed online algorithm via simulation in terms of session blocking probability and network resources used by a session. Simulation results indicate that our proposed computationally efficient online algorithm performs well even when a fraction of the nodes are SaD nodes.     

Simulation of the Tree Algorthm in ATM Networks

ＡＴＭｉｓｄｅｐｅｎｄｅｎｔｏｎｔｈｅｄｉｆｆｅｒｅｎｔｃｈａｒａｃｔｅｒｉｓ ｔｉｃｓｉｎａｎｉｎｔｅｇｒａｔｅｄｗａｙｔｏｔｒａｎｓｍｉｔｓｅｒｖｉｃｅｓ[1 ] .ＡＴＭｎｅｔｗｏｒｋｍａｙｉｎｃｌｕｄｅｖｉｄｅｏ ,ｖｏｉｃｅａｎｄｉｍａｇｅｓ,ｉｎｔｅｒａｃｔｉｖｅｃｏｍｐｕｔｅｒｄａｔａａｎｄｆｉｌｅｔｒａｎｓｆｅｒｓ.Ａｎｉｍ ｐｏｒｔａｎｔａｐｐｌｉｃａｔｉｏｎｏｆａｎＡＴＭｎｅｔｗｏｒｋｉｓｔｏｓｕｐｐｏｒｔｍｕｌｔｉｍｅｄｉａｓｙｓｔｅｍｓ,ｓｕｃｈａｓｖｉｄｅｏｃｏｎｆｅｒｅｎｃｉｎｇ…     

Performance analysis of multicast routing and wavelength assignment protocol with dynamic traffic grooming in WDM networks

The need for on‐demand provisioning of wavelength‐routed channels with service‐differentiated offerings within the transport layer has become more essential because of the recent emergence of high bit rate Internet protocol (IP) network applications. Diverse optical transport network architectures have been proposed to achieve the above requirements. This approach is determined by fundamental advances in wavelength division multiplexing (WDM) technologies. Because of the availability of ultra long‐reach transport and all‐optical switching, the deployment of all‐optical networks has been made possible. The concurrent transmission of multiple streams of data with the assistance of special properties of fiber optics is called WDM. The WDM network provides the capability of transferring huge amounts of data at high speeds by the users over large distances. There are several network applications that require the support of QoS multicast, such as multimedia conferencing systems, video‐on‐demand systems, real‐time control systems, etc. In a WDM network, the route decision and wavelength assignment of lightpath connections are based mainly on the routing and wavelength assignment (RWA). The multicast RWA's task is to maximize the number of multicast groups admitted or minimize the call‐blocking probability. The dynamic traffic‐grooming problem in wavelength‐routed networks is generally a two‐layered routing problem in which traffic connections are routed over lightpaths in the virtual topology layer and lightpaths are routed over physical links in the physical topology layer. In this paper, a multicast RWA protocol for capacity improvement in WDM networks is designed. In the wavelength assignment technique, paths from the source node to each of the destination nodes and the potential paths are divided into fragments by the junction nodes and these junction nodes have the wavelength conversion capability. By using the concept of fragmentation and grouping, the proposed scheme can be generally applied for the wavelength assignment of multicast in WDM networks. An optimized dynamic traffic grooming algorithm is also developed to address the traffic grooming problem in mesh networks in the multicast scenario for maximizing the resource utilization and minimizing the blocking probability. Copyright © 2011 John Wiley & Sons, Ltd.     

Performance analysis of k-fold multicast networks

Multicast involves transmitting information from a single source to multiple destinations, and is an important operation in high-performance networks. A k-fold multicast network was recently proposed as a cost-effective solution to providing better quality-of-service functions in supporting real-world multicast applications. To give a quantitative basis for network designers to determine the suitable value of system parameter k under different traffic loads, in this paper, we propose an analytical model for the performance of k-fold multicast networks under Poisson traffic. We first give the stationary distribution of network states, and then derive the throughput and blocking probability of the network. We also conduct extensive simulations to validate the analytical model, and the results show that the analytical model is very accurate under the assumptions made. The analytical and simulation results reveal that by increasing the fold of the network, network throughput increases very fast when the fanouts of multicast connections are relatively small, compared with the network size.     

基于无色无向无冲突可重构光分插复用器节点的全光IP组播能效调度

为了提高无色无向无冲突灵活的可重构光分插复用器(CDC-F ROADM)节点的弹性光网络IP组播频谱-能耗效率,该文提出一种全光组播能效调度算法(AMEESA)。在算法路由阶段,考虑能耗和链路频谱资源使用情况设计链路代价函数,构建最小代价光树算法组播光树。在频谱分配阶段,设计基于高效光谱分辨率(HSR)光树中间节点频谱转换方法,选择节能频谱转换方案为组播光树分配频谱块资源。仿真分析表明,所提算法能有效提升网络能效,降低IP组播带宽阻塞率。