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.     

Toward a General Class of Time-Division-Multiplexed Connecting Networks

A new technique for designing a general class of time-division-multiplexed (TDM) connecting networks is presented. The technique is based on an equivalence transformation operating on a pure space-division network. The methods developed can be used for generating networks that are rearrangeable, conditionally nonblocking or strictly nonblocking. A first-degree TDM network is derived using vertical multiplexing on a pure space Clos network. Analytic equations are presented describing the number of cross-points as well as the distribution of fixed delay elements. A second-degree TDM network is formed by extending the multiplexing scheme an additional degree. The resulting network can be horizontally multiplexed to produce a compact and efficient TDM structure.     

Two-module stage optical switch network

A large-scale optical switch array based on guided-wave technology using two-module-stage network architecture is proposed. Networks are derived from a generalized three-stage switch network. Two types of architecture are demonstrated. In the first, building blocks in each module are 1×n, n×m nonblocking switches or n×r switch that can route limited numbers of input signal. In the second, crossbar, Banyan, or four-stage wide-sense nonblocking network is used as building blocks. The interconnection is simpler than for the first type. Network architectures that use Banyan or wide-sense nonblocking network building blocks are classed as thinned-out Banyan networks     

Nonblocking, repackable, and rearrangeable Clos networks: fifty years of the theory evolution

The article gives an overview of major theoretical issues associated with a switching network structure proposed by C. Clos (1953). The concepts of strict-sense and wide-sense nonblocking as well as repackable and rearrangeable networks are described, showing the development of major research areas. A taxonomy of Clos switching networks and some important results for the basic network structure are given and discussed. Other research issues are enumerated.     

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     

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     

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     

Optimal cost/performance design of ATM switches

This paper proposes a methodology for performing an evaluation and optimization of the cost of an ATM switching architecture under performance constraints given in terms of virtual connection blocking probability. An analysis of blocking networks is developed, and combined with known results concerning nonblocking networks, provides a theoretical model which relates traffic characteristics, network topology and blocking probability in a multirate/multiservice broadband environment. An analysis of the characteristics determining the cost of a generic ATM switch implementation follows. The model is oriented to optimize both the topological parameters and the speed advantage, with respect to the main cost factors of VLSI-based switching networks i.e., components count and complexity, interconnection costs     

Cost-effective traffic grooming in WDM rings

We provide network designs for optical add-drop wavelength-division-multiplexed (OADM) rings that minimize overall network cost, rather than just the number of wavelengths needed. The network cost includes the cost of the transceivers required at the nodes as well as the number of wavelengths. The transceiver cost includes the cost of terminating equipment as well as higher-layer electronic processing equipment, which in practice can dominate over the cost of the number of wavelengths in the network. The networks support dynamic (i.e., time-varying) traffic streams that are at lower rates (e.g., OC-3, 155 Mb/s) than the lightpath capacities (e.g., OC-48, 2.5 Gb/s). A simple OADM ring is the point-to-point ring, where traffic is transported on WDM links optically, but switched through nodes electronically. Although the network is efficient in using link bandwidth, it has high electronic and opto-electronic processing costs. Two OADM ring networks are given that have similar performance but are less expensive. Two other OADM ring networks are considered that are nonblocking, where one has a wide-sense nonblocking property and the other has a rearrangeably nonblocking property. All the networks are compared using the cost criteria of number of wavelengths and number of transceivers     

Design of photonic rearrangeable networks with zero first-orderswitching-element-crosstalk

The development of optical cross-connect architectures is a very important topic today. We consider here in particular the class of optical space-division switching fabrics configured as multistage structures built with 2×2 optical switching elements (SEs) and derived from a combination of vertical replication and horizontal expansion of Banyan networks. We determine the necessary and sufficient conditions for these matrices to be rearrangeably nonblocking and free of first-order crosstalk in SEs. This impairment is one of the major limitations in optical cross-connect performance. We focus on rearrangeable matrices since they have lower complexity than their strict-sense nonblocking counterparts. Given the current high cost of optical SEs, the rearrangeable solution looks attractive today     

Yet another result on multi-log2N networks

One-to-many connection (i.e., multicast) is an important communication primitive used in parallel processing and high-speed switching in order to simultaneously send data from an input to more than one output. We prove that for even (respectively, odd) n, a multi-log₂N network is strictly nonblocking for a one-to-many connection traffic if it is designed by vertically stacking at least (δn)/4+1((δ/2)(n-1)+1) planes of a log₂N network together, where N=2ⁿ, δ=2^[n/2], and [x] denotes the greatest integer less than or equal to x. We thus give answer to the open problem and introduce yet another strictly nonblocking multicast network. The characterized network has self-routing capability, regular topology, O(2log₂N+2log₂(log₂N)) stages, and fewer crosspoints than the Clos network for N⩾512. We then extend multi log₂N multicast networks to the fanout restricted nonblocking networks. It turns out that the multi-log₂N network nonblocking in a strict-sense for a one-to-one connection traffic is also wide-sense nonblocking for a multicast traffic in which the fanout of any connection does not exceed δ, provided that for even (respectively, odd) n, the fanout capability of each log₂N network is restricted to stage (n/2)(((n-1)/2)+1) through n-1     

Extended baseline architecture for nonblocking photonic switching

A new switch architecture called extended baseline networks (EBN) is proposed for nonblocking photonic switching. This switch is a space-division multistage network using 2×2 optical switch elements which may be directional couplers fabricated on titanium diffused lithium niobate (Ti:LiNbO₃) substrates. A recursive definition for the proposed architecture is presented. Some properties including the number of switch elements required, blocking characteristics, number of crossovers, system attenuation, and signal-to-noise ratio (SNR) are derived and analyzed. Most of the characteristics are shown to be better than those of other well-known networks fabricated on single Ti:LiNbO₃ substrates     

A Simple Control Algorithm for Rearrangeable Switching Networks with Time Division Multiplexed Links

A simple control algorithm is proposed for a three-stage rearrangeable switching network with time division multiplexed links. The nonblocking condition is shown for the rearrangeable network controlled by the proposed algorithm. The rearrangeable nonblocking network controlled by the proposed method is more cost effective in hardware than a strictly nonblocking network for a large number of channels multiplexed on links. The computing complexity of the algorithms is not more than that for controlling the strictly nonblocking network. In the proposed algorithm, only one path must be moved in the rearrangement, thus reducing the difficulty in implementing the rearrangeable network. This algorithm is efficient for broadband switching systems or cross-connect devices where nonblocking switches are needed.     

Wide-sense nonblocking multicast in a class of regular optical WDMnetworks

Multicast communication involves transmitting information from a single source node to multiple destination nodes, and is becoming an important requirement in high-performance networks. We study multicast communication in a class of optical WDM networks with regular topologies such as linear arrays, rings, meshes, tori and hypercubes. For each type of network, we derive the necessary and sufficient conditions on the minimum number of wavelengths required for a WDM network to be wide-sense nonblocking for multicast communication under some commonly used routing algorithms     

Comments on "Wide-sense nonblocking multicast Log/sub 2/(N,m,p) Networks"

Recently, Hwang and Lin derived nonblocking conditions for multicast connections in Log/sub 2/(N,m,p) networks. They improved some conditions obtained earlier by Kabacin/spl acute/ski and Danilewicz. In this letter, we identify some inaccuracy in present results concerning wide-sense nonblocking Log/sub 2/(N,m,p) multicast networks, and give the correct results.     

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     

Generalized Survivable Network

Two important requirements for future backbone networks are full survivability against link failures and dynamic bandwidth provisioning. We demonstrate how these two requirements can be met by introducing a new survivable network concept called the generalized survivable network (GSN), which has the special property that it remains survivable no matter how traffic is provisioned dynamically, as long as the input and output constraints at the nodes are fixed. A rigorous mathematical framework for designing the GSN is presented. In particular, we focus on the GSN capacity planning problem, which finds the edge capacities for a given physical network topology with the input/output constraints at the nodes. We employ fixed single-path routing which leads to wide-sense nonblocking GSNs. We show how the initial, infeasible formal mixed integer linear programming formulation can be transformed into a more feasible problem using the duality transformation. A procedure for finding the realizable lower bound for the cost is also presented. A two-phase approach is proposed for solving the GSNCPP. We have carried out numerical computations for ten networks with different topologies and found that the cost of a GSN is only a fraction (from 39% to 97%) more than the average cost of a static survivable network. The framework is applicable to survivable network planning for ASTN/ASON, VPN, and IP networks as well as bandwidth-on-demand resource allocation.     

The theory of connecting networks and their complexity: A review

Connecting networks are key subsystems of communications switching systems. This paper reviews what is known about the theoretical minimum complexity of connecting networks of several different types and presents the best known explicit constructions for them. In some cases, such as for strictly nonblocking connection networks, there is a significant difference between the best known construction and the theoretical minimum complexity. In other cases, such as for rearrangeably nonblocking connecting networks, the best construction differs from the minimum by only a constant.     

A nonblocking architecture for broadband multichannel switching

The paper investigates multichannel switching as a promising alternative to traditional single-channel switching where virtual paths established in a switch are between a single input channel and a single output channel. A particular non-blocking condition is derived for flip networks, which is exploited to realize a multichannel switching architecture that supports an arbitrary number of channel groups. The architecture is internally nonblocking and bufferless. Using one flip network recursively a number of times based on the number of channel groups, the resulting architecture becomes efficient in the sense that the cross point complexity is O(N log₂ N) for N inputs. Other distinguishing features are the abilities to provide multicasting, superrate switching (i.e., rates that exceed the capacity of a single channel are accommodated), multirate switching (i.e., bit pipes of different rates are supported simultaneously), multiple performance requirements (i.e., services with different performance requirements are treated accordingly), and fair access to all inputs (i.e., no input is systematically discriminated against). In multichannel switching, cells belonging to a single session can traverse multiple channels. Providing the cell sequencing integrity becomes a challenging issue. The architecture proposed in the paper accomplishes the task without employing any cell resequencing mechanism     

A New Architecture for Nonblocking Optical Switching Networks

With the current technology, all-optical networks require nonblocking switch architectures for building optical cross-connects. The crossbar switch has been widely used for building an optical cross-connect due to its simple routing algorithm and short path setup time. It is known that the crossbar suffers from huge signal loss and crosstalk. The Clos network uses a crossbar as building block and reduces switch complexity, but it does not significantly reduce signal loss and crosstalk. Although the Spanke's network eliminates the crosstalk problem, it increases the number of switching elements required considerably (to 2N ² - 2N). In this paper, we propose a new architecture for building nonblocking optical switching networks that has much lower signal loss and crosstalk than the crossbar without increasing switch complexity. Using this architecture we can build non-squared nonblocking networks that can be used as building block for the Clos network. The resulting Clos network will then have not only lower signal loss and crosstalk but also a lower switch complexity.