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     

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.     

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     

On Noninterruptive Rearrangeable Networks

In this paper, we study a new class of nonblocking networks called noninterruptive rearrangeable (NIR) networks, which are rearrangeable under the additional condition that existing connections are not interrupted while their paths being possibly rerouted to accommodate a new request. We give a complete characterization of NIR Clos networks built of switching elements of various nonblocking properties. In particular, we propose a novel class of NIR Clos networks that leads to recursive constructions of various cost-efficient multistage NIR networks. Finally, we present examples of such constructions and compare them with the best previously known results.     

One-Sided Switching Networks Composed of Digital Switching Matrices

One-sided switching networks composed of uniform digital switching matrices are considered. Such matrices mix in the same integrated circuit or in the same printed circuit board time and space switching. The conditions under which one-sided networks are nonblocking and rearrangeable are discussed.     

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.     

One-stage one-sided rearrangeable switching networks

Switching networks consisting of subscriber lines and crosswires connected by switches are considered. A connection between two subscribers is made along one crosswire via two switches. The minimum number of switches necessary for such a switching network to be rearrangeably nonblocking is determined and a switching arrangement which achieves this minimum for any (even) number of subscriber lines is constructed. Two procedures for assignment of crosswires to subscriber line pairs are described. One makes the correct choice of connection route without backtracking provided all connections are known beforehand; the other determines a rearrangement of existing assignments when a new connection is required. The switching networks which have the minimum number of switches for networks with up to eight subscriber lines and give nonisomorphic solutions for larger networks are characterized     

A new concept-repackable networks

The following classes of connecting networks, based on their combinatorial properties, have been previously defined: networks nonblocking in the strict sense, networks nonblocking in the wide sense, rearrangeable networks, and blocking networks. To these the authors add the class of repackable networks, i.e., networks in which blocking can be avoided by using call repacking control algorithms. The conditions under which a three-stage Clos network is repackable are formulated and proved. The numbers of middle-stage switches in all network classes are compared, and the differences between repackable and rearrangeable networks are discussed     

Strictly Nonblocking $f$-Cast Photonic Networks

The multicast capability and crosstalk issue need to be deliberately considered in the design of future high performance photonic switching networks. In this paper, we focus on the photonic switching networks built on the banyan-based architecture and directional coupler technology. We explore the capability of these networks to support general f-cast traffic, which covers the unicast traffic (f = 1) and multicast traffic (f = N) as special cases, and determine the conditions for these networks to be f-cast strictly nonblocking under various crosstalk constraints. In particular, we propose an optimization framework to determine the nonblocking condition of an f-cast photonic network when a general crosstalk constraint is imposed.     

On Nonblocking Switching Networks Composed of Digital Symmetrical Matrices

Significant advances in semiconductor technology make it possible to construct new components called digital symmetrical matrices, which mix in the same integrated circuit, time and space switching. In this paper, structures of multistage nonblocking networks composed of such matrices are described. The condition under which the network will be nonblocking is formulated, and the relationship between the maximal capacity of the network and the number of switching stages is discussed. Formulas for designing optimal threeand five-stage networks are derived. It is shown that general multistage networks should have as few stages as possible for minimizing the cost.     

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.     

Tradeoff of horizontal decomposition versus vertical stacking inrearrangeable nonblocking networks

A class of rearrangeable nonblocking networks is presented. The proposed networks are fault-tolerant, self-routing, and intended for a very-high-speed environment. Self-routing networks have one major problem when applied to switching: they are blocking networks. To solve this problem, two methods have been used to create self-routing rearrangeable nonblocking networks: horizontal cascading (HC) and vertical stacking (VS). The authors unify the two approaches and propose a novel class of switching networks. The proposed design principle allows the best tradeoffs among design parameters such as fault tolerance, hardware cost, and the frequency of rearrangement activities. A study of the frequency of rearrangement activities is also presented     

Semi-rearrangeably nonblocking operation of Clos networks in themultirate environment

We study the semi-rearrangeably nonblocking (SRN) operation of asymmetrical three-stage Clos (1953) switching networks in the multirate environment. We develop a basic algorithm that balances the established connections among middle-stage switches by performing a small number of rearrangements per disconnection. For this algorithm, we first derive general conditions under which rearranging from a single middle-stage switch is sufficient to achieve SRN operation. In the most general case, however, a sequence of rearrangements from several middle-stage switches may be required for SRN operation. An algorithm to achieve this sequence of rearrangements is presented and its correctness is proved. The minimum resource requirements to achieve SRN operation, in terms of the number of middle-stage switches, are derived for various cases     

Strictly nonblocking directional-coupler-based switching networksunder crosstalk constraint

Directional-coupler (DC)-based switching systems can switch signals at the rate of several terabits per second. Such switches can also transmit signals with multiple wavelengths simultaneously. Despite these advantages, DCs suffer from an intrinsic crosstalk problem that must be overcome in building a robust switching system. In this paper, the principles of constructing strictly nonblocking DC-based photonic switching systems under various crosstalk constraints are explored. We demonstrate how crosstalk adds a new dimension to the theory of switching systems. We find the sufficient nonblocking condition for photonic networks under crosstalk constraints and demonstrate that some well-known nonblocking networks can tolerate a stricter crosstalk constraint while retaining their hardware complexity. The theory developed in the paper can guide us in making the design tradeoff between the level of crosstalk and the amount of hardware     

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.     

Nonblocking multirate distribution networks

Results for nonblocking distribution networks are generalized for the multirate environment in which different user connections share a switch's internal data paths for arbitrary fractions of the total capacity. Conditions under which network proposed by Y.P. Ofman (1965), C.D. Thompson (1978), and N. Pippenger (1973) lead to multirate distribution networks are derived. The results include both rearrangement and wide-sense nonblocking networks. The complexity of the rearrangement multirate network exceeds that of the corresponding space-division network by a log log factor, while the complexity of the wide-sense nonblocking network is within a factor of two of the corresponding space-division network     

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     

Nonblocking WDM switching networks with full and limited wavelength conversion

In previous years, with the rapid exhaustion of the capacity in wide area networks led by Internet and multimedia applications, demand for high bandwidth has been growing at a very fast pace. Wavelength-division multiplexing (WDM) is a promising technique for utilizing the huge available bandwidth in optical fibers. We consider efficient designs of nonblocking WDM permutation switching networks. Such designs require nontrivial extensions from the existing designs of electronic switching networks. We first propose several permutation models in WDM switching networks ranging from no wavelength conversion, to limited wavelength conversion, to full wavelength conversion, and analyze the network performance in terms of the permutation capacity and network cost, such as the number of optical cross-connect elements and the number of wavelength converters required for each model. We then give two methods for constructing nonblocking multistage WDM switching networks to reduce the network cost.     

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.     

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.