Strictly nonblocking three-stage Clos networks with some rearrangeable multicast capability

F.K. Hwang and S.C. Liaw (see IEEE/ACM Trans. Networking, vol.8, p.535-9, 2000) introduced a new nonblocking requirement for 2-cast traffic which imposes different requirements on different types of coexisting calls. The requirement is strictly nonblocking for point-to-point calls among the 2-cast traffic, and is rearrangeable for genuine 2-cast calls. We generalize the 2-cast calls to multicast calls and give a sufficient condition for such networks when the number of multicast calls is upper bounded.     

On the CNET: a rearrangeable nonblocking optical interconnection network

A planar, circular, rearrangeable nonblocking optical switching architecture using N(N-1) Ti:LiNbO/sub 3/ directional coupler switches is suggested. Various figures of merit such as the signal-to-crosstalk ratio (SXR), insertion loss and fault tolerance are presented. The outline for a distributed routing algorithm in O(N) time is given.<>     

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 strictly nonblocking network based on nonblocking 4×4 optical switches

Recently, the demand for communication has been growing rapidly. Hence, optical multistage network technologies are more appreciated nowadays. A double-layer network is a strictly nonblocking network, and it has the lowest system insertion loss of non-dilated networks. A Beneš network is a rearrangeably nonblocking network, and it has the same system insertion loss as a double-layer network. We have proposed the use of modified polarization selection elements (PSEs). The system insertion loss, number of drivers, and number of required components of a double-layer network could be reduced if it is constructed with modified PSEs. A nonblocking 4×4 optical switch with two stages of polarization selective elements has been presented in our previous study. Based on this nonblocking 4×4 optical switch, we propose a strictly nonblocking network structure which features even lower system insertion loss than those of a double-layer network and a Beneš network. The signal-to-noise ratio of the proposed network structure is a constant, and is higher than the constraint, although it is lower than that of the double-layer network. The number of major components of the proposed network is less than that of a double-layer network and larger than that of a Beneš network, since a Beneš network is rearrangeably nonblocking. We also offer a routing algorithm for the new proposed network; the time complexity of the routing algorithm is O(1).     

16×16 strictly nonblocking guided-wave optical switchingsystem

We report the first demonstration of a complete 16×16 strictly nonblocking guided-wave optical switching system. The system, based on a three-stage extended generalized shuffle network, includes 448 directional coupler switch elements in 23 packaged modules. The modules are mounted in a single equipment cabinet and are controlled with a PC-based switching algorithm. We report results of extensive measurements on device and system performance. The devices and system exhibited low uniform voltages. Low loss, low crosstalk, and broad bandwidth. This lithium niobate based system operated continuously and without maintenance for a period of 20 months     

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.     

Logically rearrangeable multihop lightwave networks

The optimization problem of rearrangeable multihop lightwave networks is considered. The authors formulate the flow and wavelength assignment problem, when minimizing the maximum flow in the network, as a mixed integer optimization problem subject to linear constraints. The problem is decomposed into two independent subproblems, the wavelength assignment (or connectivity problem) and the flow assignment (or routing problem). A simple heuristic provides a meaningful formulation to the connectivity problem, in a form similar to a transportation problem. An algorithm is then proposed which finds a heuristic initial logical connectivity diagram and the corresponding routing, and then iterates from that solution by applying branch-exchange operations to the connectivity diagram. The algorithm was tested on illustrative traffic matrices for an 8 node network with two transmitters and two receivers per node, and an improvement in achievable throughput over the Perfect Shuffle interconnection pattern was shown in all cases     

Reduced banyan-type multiplane rearrangeable switching networks

The new concept of the multiplane rearrangeable switching network is presented. The new switching network's architecture is based on the well-known baseline network (the log₂(N, 0, 1) switching network). This new architecture can easily be obtained from the baseline network by the removal of some switching elements. It is therefore called the reduced baseline switching network and is denoted by log^r ₂((N, 0, 1). The new multiplane rearrangeable reduced baseline switching network requires fewer switching elements and crosspoints than the multiplane switching network which is based on the plain baseline network.     

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     

A general class of rearrangeable interconnection networks

A class of rearrangeable interconnection networks which includes the Benes network as a special case is identified. An instance of this class consists of a set of parallel planes each consisting of a Delta network with a suitable number of additional stages. A formal definition is given and a rearrangeability condition is proven which gives a tradeoff between the number of planes and additional stages necessary     

On nonblocking multicast three-stage Clos networks

We give necessary and sufficient conditions for strictly nonblocking three-stage Clos (1953) networks with two types of multicast traffic. Then, we extend the results to other models where the routing is under certain restrictions. Finally, we compare our results with existing literature to mark the differences and similarities     

Performance of rearrangeable nonblocking 4×4 switch matriceson LiNbO3

The design, fabrication, and characterization of rearrangeable nonblocking 4×4 switch matrices and the development of a novel ITO (indium-tin-oxide)/Au multilayer electrode that leads to low switching voltages and low DC drift is reported. Results on electrode systems, insertion loss, crosstalk, tolerances in the coupling length, and stability obtained for eight fabricated matrices are given. In comparison to the SiO₂ buffer layers, a reduction in the switching voltage of a factor of 0.66 has been achieved. Insertion losses of fiber pigtailed modules are in the range between 4 and 7 dB. The crosstalk has still to be improved. The stability of the operating points of the switches has been analyzed, showing that the devices must be operated in closed dark housings with a passivation layer in order to avoid optical damage effects from ambient light and to protect them against physical and chemical influences     

Analytical and simulation study of simple rearrangeable multiexchange networks

Congestion probabilities for calls in simple three-exchange networks operated with and without rearrangements are determined analytically and by digital simulation. Load-loss curves are obtained, from which the gain in traffic capacity due to rearrangement and degradation due to overload can be found. It is concluded that routing control with rearrangements possesses a potential traffic-handling advantage over conventional automatic alternative routing.     

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     

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     

A new decomposition algorithm for rearrangeable Closinterconnection networks

We give a new decomposition algorithm to route a rearrangeable three-stage Clos network in O(nr²) time, which is faster than all existing decomposition algorithms. By performing a row-wise matrix decomposition, this algorithm routes all possible permutations, thus overcoming the limitation on realizable permutations exhibited by many other routing algorithms. This algorithm is extended to the fault tolerant Clos network which has extra switches in each stage, where it provides fault tolerance under faulty conditions and reduces routing time under submaximal fault conditions     

A survey of nonblocking multicast three-stage Clos networks

The author gave a survey on multicast nonblocking multistage interconnection networks in his 1998 book. Here he focuses on the three-stage Clos network and its recursive extensions. Not only does this article bring the literature up to date, but it also provides some fresh viewpoints to either clarify or simplify some issues.     

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     

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.     

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