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.     

Crosstalk-free conjugate networks for optical multicast switching

High-speed photonic switching networks can switch optical signals at the rate of several terabits per second. However, they suffer from an intrinsic crosstalk problem when two optical signals cross at the same switch element. To avoid crosstalk, active connections must be node disjoint in the switching network. In this paper, a sequence of decomposition and merge operations, called conjugate transformation, performed on each switch element to tackle this problem, is proposed. The network resulting from this transformation is called the conjugate network. By using the numbering schemes of networks, the authors prove that if the route assignments in the original network are link disjoint, their corresponding ones in the conjugate network would be node disjoint. Thus, traditional nonblocking switching networks can be transformed into crosstalk-free optical switches in a routine manner. Furthermore, it has been shown that crosstalk-free multicast switches can also be obtained from existing nonblocking multicast switches via the same conjugate transformation.     

On the blocking performance of EGS networks under multicast traffic

Extended generalized shuffle (EGS) networks are a wide class of interconnection networks introduced by Richards (1993). In this work, we study the blocking performance of EGS networks under point-to-multipoint traffic. Two new routing algorithms for multicast connections in EGS networks are defined, and a theorem proving that these algorithms construct minimum-cost connection trees is enclosed. Simulation results show that the blocking performance of EGS networks under multicast traffic is much better than that of three-stage Clos networks of equal complexity     

On nonblocking switching networks for multichannel connections

This paper deals with switching networks for multichannel connections. The conditions under which the three-stage switching network is nonblocking for s-channel connections are given. Switching networks that are nonblocking in the strict sense as well as the switching networks nonblocking in the wide sense are considered. The conditions for two-sided and for one-sided switching networks are derived     

Rearrangeability of multicast Clos networks with middle-stage fan-out

The sufficient and necessary conditions under which a three-stage Clos network is rearrangeable for multicast connections are given. It is assumed that only switches of the middle stage have the fan-out property. Such an assumption is valid for some practical switching systems, e.g., high-speed crossconnects.     

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     

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.     

An efficient dynamic multicast traffic-grooming algorithm for WDM networks

With the growth of multi-granularity multicast applications, there comes into being a huge gap between the bandwidth of a wavelength provided and a multicast traffic required in the wavelength division multiplexing (WDM) networks. The dynamic multicast traffic-grooming is an effective way for WDM networks to improve the wavelength utilization and decrease the traffic blocking probability. A novel switching node architecture with the multicast switching matrix and traffic-grooming fabric is studied in the paper. Then, an efficient dynamic multicast traffic-grooming algorithm is proposed for the architecture. According to the ratio of network available grooming port number to network transceiver number, the proposed algorithm estimates whether the traffic-grooming port is a scarce resource for input traffic and chooses the appropriate grooming strategy. If the traffic-grooming port is scarce, the minimized use grooming port strategy is designed for the coming traffic. On the contrary, the minimized use node transceiver strategy is applied for the coming traffic. Simulation results show that the proposed algorithm can groom traffic efficiently with low blocking probability and high network throughput constraint by limiting number of node transceivers and grooming ports.     

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.     

On blocking probability of multicast networks

Multicast is a vital operation in both broad-band integrated services digital networks (BISDN) and scalable parallel computers. We look into the issue of supporting multicast in the widely used three-stage Clos network or υ(m, n, r) network. Previous work has shown that a nonblocking υ(m, n, r) multicast network requires a much higher network cost than a υ(m, n, r) permutation network. However, little has been known on the blocking behavior of the υ(m, n, r) multicast network with only a comparable network cost to a permutation network. We first develop an analytical model for the blocking probability of the υ(m, n, r) multicast network and then study the blocking behavior of the network under various routing control strategies through simulations. Our analytical and simulation results show that a υ(m, n, r) network with a small number of middle switches m, such as m=n+c or dn, where c and d are small constants, is almost nonblocking for multicast connections, although theoretically it requires m⩾Θ(n(log r/log log r)) to achieve nonblocking for multicast connections. We also demonstrate that routing control strategies are effective for reducing the blocking probability of the multicast network. The best routing control strategy can provide a factor of two to three performance improvement over random routing. The results indicate that a υ(m, n, r) network with a comparable cost to a permutation network can provide cost-effective support for multicast communication     

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.     

基于GMPLSD的光突发交换网络组播性能仿真

在通用多协议标记交换协议(GMPLS)控制面体系结构下,OBS网络组播的实现面临着一些技术问题.首先分析并解决了其中两个关键问题,即IP组播树与组播标记交换路径(LSP),以及组播LSP与光树间的映射问题;然后提出了支持组播的OBS边缘节点与核心节点的功能模型;并在OPNET仿真环境下,设计和开发了节点仿真模块,验证了OBS组播功能.仿真结果表明:在基于GMPLS的OBS网络体系结构下,光组播树建立时间普遍较短,而且在实现方式上,与光路相比,光树型方式具有较高的链路利用率.     

Multirate Clos networks

Clos networks are a class of multistage switching network topologies that provide alternate paths between inputs and outputs, making it possible to minimize or eliminate the blocking that can otherwise occur in such networks. In his seminal paper in the Bell System Technical Journal in 1953, Charles Clos showed how these networks could be configured to make them nonblocking and effectively launched the systematic study of switching system performance, a field that has developed a rich technical literature, and continues to be very active and of continuing practical importance. This article describes how Clos' results have been generalized to systems that support connections with varying bandwidth requirements. These generalizations have extended the application of Clos networks well beyond their original technological context and have led to a number of interesting new results, especially in connection with systems that support multicast communication.     

Multicast for RSVP switching: An extended multicast model with QoS for label swapping in an IP over ATM environment

The ubiquity of IP associated with the acknowledgment of ATM as a key switching technology has motivated an increasing interest towards the design of a more efficient way of operating IP over ATM networks. This approach is known under the name Label Swapping. A few studies have addressed the primary issue of providing simultaneously quality of service and multicast. We propose a solution where we mix an RSVP architecture with one Label Swapping technique called IP Switching. We discuss problems that arise when using cut-through associated with an RSVP multicast model and propose an application for an IPv6 environment over an ATM switching hardware.     

A Proactive Tree Recovery Mechanism for Resilient Overlay Multicast

Overlay multicast constructs a multicast delivery tree among end hosts. Unlike traditional IP multicast, the non-leaf nodes in the tree are normal end hosts, which are potentially more susceptible to failures than routers and may leave the multicast group voluntarily. In these cases, all downstream nodes are affected. Thus, an important problem for making overlay multicast more dependable is how to recover from node departures in order to minimize the disruption of service to those affected nodes. In this paper, we propose a proactive tree recovery mechanism to make the overlay multicast resilient to these failures and unexpected events. Rather than letting downstream nodes try to find a new parent after a node departure, each non-leaf node precalculates a parent-to-be for each of its children. When this non-leaf node is gone, all its children can find their respective new parents immediately. The salient feature of the approach is that rescue plans for multiple non-leaf nodes can work together for their respective children when they fail or leave at the same time. Extensive simulations demonstrate that our proactive approach can recover from node departures much faster than reactive methods, while the quality of trees restored and the cost of recovery are reasonable     

Wide-sense and strict-sense nonblocking operation of multicastmulti-log2 n switching networks

Multicast connections are used in broad-band switching networks as well as in parallel processing. We consider wide-sense and strict-sense nonblocking conditions for multi-log₂ N switching networks with multicast connections. We prove that such networks are wide-sense nonblocking if they are designed by vertically stacking at least t · 2^n-t-1 + 2 ^n-2t-1 planes of a log₂ N networks together, where 1 ⩽ t ⩽ [n/2] and t defines the size of a blocking window K = 2^t. For t = [n/2] and n even, and for [n/2] ⩽ t ⩽ n the number of planes must be at least t · 2^n-t-1 + 1 and 2^t + (n - t - 1) · 2^n-t-1 - 2^2t-n-1 + 1, respectively. In the case of strict-sense nonblocking switching networks, the number of planes is at least N/2. The results obtained in this paper show that in many cases number of planes in wide-sense nonblocking switching networks is less than those for t = [n/2] considered by Tscha and Lee (see ibid., vol.47, p.1425-31, Sept. 1999). The number of planes given in the paper is the minimum number of planes needed for wide-sense nonblocking operation provided that Algorithm 1 is used for setting up connections. The minimum number of planes for such operation in general is still open issue     

A QoS-based HRWA multicast scheme with resource constraint on WDM mesh networks

Several Internet multicast applications, such as teleconferencing and remote diagnosis, have Quality-of-Service (QoS) requirements. It is a challenging task to build QoS constrained multicast trees with high performance and high success ratio. The Dense Wavelength Division Multiplexing (DWDM) can provide high-speed, high-transmission capacity and bandwidth efficiency to proceed with the multipoint-to-multipoint multicast transmission. Reserved paths with the form of a tree are not the ideal topology for the multipoint-to-multipoint multicast transmission because transceivers and reserved wavelength channels will lead to some other new connections that cannot be held at the same time. This paper presents a new Hybrid Routing and Wavelength Assignment with delay constraint (HRWA-DC) multicast algorithm on WDM mesh networks, which reduces the number of searching ring paths to achieve low complexity and the number of links to increase the number of successful connections. Simulation result shows that HRWA-DC is more effective for resource utilization than tree scheme in terms of lower call blocking probability and link utilization even at tight delay constraint. It is suitable for big group size and long holding time for multipoint-to-multipoint multicast transmission.This research was partially supported by the Grant of National Science Council, R.O.C. (NSC94-2213-E-155-045).     

Multicast connection capacity of WDM switching networks with limited wavelength conversion

Currently, many bandwidth-intensive applications require multicast services for efficiency purposes. In particular, as wavelength division multiplexing (WDM) technique emerges as a promising solution to meet the rapidly growing demands on bandwidth in present communication networks, supporting multicast at the WDM layer becomes an important yet challenging issue. In this paper, we introduce a systematic approach to analyzing the multicast connection capacity of WDM switching networks with limited wavelength conversion. We focus on the practical all-optical limited wavelength conversion with a small conversion degree d (e.g., d=2 or 3), where an incoming wavelength can be switched to one of the d outgoing wavelengths. We then compare the multicast performance of the network with limited wavelength conversion to that of no wavelength conversion and full wavelength conversion. Our results demonstrate that limited wavelength conversion with small conversion degrees provides a considerable fraction of the performance improvement obtained by full wavelength conversion over no wavelength conversion. We also present an economical multistage switching architecture for limited wavelength conversion. Our results indicate that the multistage switching architecture along with limited wavelength conversion of small degrees is a cost-effective design for WDM multicast switching networks.     

A unifying approach to determine the necessary and sufficient conditions for nonblocking multicast 3-stage Clos networks

The 3-stage Clos network is the most-studied switching network. However, exact conditions on the strictly nonblocking multicast three-stage Clos network under various models are difficult to get, due to the messy detail and because each case employs a different argument. Hwang and Liaw (2000) made the latest attempt and pointed out errors in previous attempts. However, they made errors, too. In this paper, we propose a unifying approach to study those models systematically (which also applies to some wide-sense nonblocking (WSNB) networks). We also propose a new routing algorithm, and use the unifying approach to derive a necessary and sufficient condition for WSNB.     

Simulation of the Tree Algorthm in ATM Networks

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