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.     

Reducing electronic multiplexing costs in SONET/WDM rings with dynamically changing traffic

In this paper, we consider traffic grooming in WDM/SONET ring networks when the offered traffic is characterized by a set of traffic matrices. Our objective is to minimize the cost of electronic add/drop multiplexers (ADMs) in the network, while being able to support any offered traffic matrix in a rearrangeably nonblocking manner. We provide several methods for reducing the required number of ADMs for an arbitrary class of traffic matrices. We then consider the special case where the only restriction on the offered traffic is a constraint on the number of circuits a node may source at any given time. For this case, we provide a lower bound on the number of ADMs required and give conditions that a network must satisfy in order for it to support the desired set of traffic patterns. Circuit assignment and ADM placement algorithms with performance close to this lower bound are provided. These algorithms are shown to reduce the electronic costs of a network by up to 27%. Finally, we discuss extensions of this work for supporting dynamic traffic in a wide-sense or strict sense nonblocking manner as well as the benefits of using a hub node and tunable transceivers. Much of this work relies on showing that these grooming problems can often be formulated as standard combinatorial optimization problems.     

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     

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     

Combining GA with Splitting Methods for Rearrangeably Nonblocking Grooming of Dynamic Traffic in SONET Ring Networks

SONET/WDM rings are widely deployed in today’s networks. To reduce the total cost of such a network, an efficient way is using the traffic grooming technique to minimize the number of add/drop multiplexers (ADMs) on the ring. Since traffic often changes frequently, the problem of supporting dynamic traffic patterns with minimum number of ADMs and wavelengths becomes incresingly important, which is referred to as grooming of dynamic traffic. In this paper, we will deal with rearrangeably nonblocking grooming of arbitrary dynamic traffic in such ring networks. We will discuss in detail the benefit of splitting methods to such a grooming way and apply them to this kind of grooming. A novel genetic algorithm (GA) approach with a hierarchical chromosome structure for each individual is proposed in combination with splitting methods to address such grooming problems. Computer simulation results under different conditions show that our algorithm is efficient in reducing both the numbers of ADMs and wavelengths.     

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     

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     

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 Logd(N,m,p) Networks

Necessary and sufficient conditions for Log_d(N,m,p) network to be point-to-point strictly nonblocking are known. Recently, Kabacinski and Danilewicz obtained necessary and sufficient conditions for the Log₂(N,0,p) network to be broadcast strictly nonblocking. In this paper, we give necessary and sufficient conditions for Log_d(N,m,p) to be f-cast strictly nonblocking for every f, thus covering the point-to-point case (f=1) and the broadcast case (f=N) as special cases     

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     

Dynamic Wavelength Assignment for WDM All-Optical Tree Networks

We develop an on-line wavelength assignment (WA) algorithm for a wavelength-routed WDM tree network. The algorithm dynamically supports all$bf k$-port traffic matrices among$N$end nodes, where$bf k$denotes an integer vector$[k_1 ldots, k_N]$and end node$i, , 1leq ileq N$, can transmit at most$k_i$wavelengths and receive at most$k_i$wavelengths. Our algorithm is rearrangeably nonblocking, uses the minimum number of wavelengths, and requires at most$d^ast-1$lightpath rearrangements per new session request, where$d^ast$is the degree of the most heavily used node. We observe that the number of lightpath rearrangements per new session request does not increase as the amount of traffic$bf k$scales up by an integer factor. In addition, wavelength converters cannot reduce the number of wavelengths required to support$bf k$-port traffic in a tree network. We show how to implement our WA algorithm using a hybrid wavelength-routed/broadcast tree with only one switching node connecting several passive broadcast subtrees. Finally, using roughly twice the minimum number of wavelengths for a rearrangeably nonblocking WA algorithm, we can modify the WA algorithm to be strict-sense nonblocking.     

Optical Switching Networks With Minimum Number of Limited-Range Wavelength Converters

We study the problem of determining the minimum number of limited-range wavelength converters needed to construct strictly, wide-sense, and rearrangeably nonblocking optical cross-connects for both unicast and multicast traffic patterns. We give the exact formula to compute this number for rearrangeably and wide-sense nonblocking cross-connects under both the unicast and multicast cases. We also give optimal cross-connect constructions with respect to the number of limited-range wavelength converters.     

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.     

On Nonblocking Multiconnection Networks

In the paper, four theorems describing conditions under which a three-stage multiconnection network is nonblocking for different routing strategies are formulated and proved. These theorems hold for any values of the structural parameters of a network. For some networks having a small number of outer stage switches, these theorems give significantly lower numbers of required middle stage switches than theorems currently known.     

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.     

Nonblocking property of reverse banyan networks

The authors present a new nonblocking property of the reverse banyan network under a particular input packet pattern at the input ports. The reverse banyan network is the mirror image of the banyan network. If the input packets of the N×N reverse banyan network have consecutive output address as modulo N, then the reverse banyan network is nonblocking. The routing of packets in the reverse banyan network is described, and the nonblocking property of the reverse banyan network is proved. A possible application of this property in the switching network is discussed     

Analysis of nonblocking ATM switches with multiple input queues

An analytical model for the performance analysis of a multiple input queued asynchronous transfer mode (ATM) switch is presented. The interconnection network of the ATM switch is internally nonblocking and each input port maintains a separate queue of cells for each output port. The switch uses parallel iterative matching (PIM) to find the maximal matching between the input and output ports of the switch. A closed-form solution for the maximum throughput of the switch under saturated conditions is derived. It is found that the maximum throughput of the switch exceeds 99% with just four iterations of the PIM algorithm. Using the tagged input queue approach, an analytical model for evaluating the switch performance under an independent identically distributed Bernoulli traffic with the cell destinations uniformly distributed over all output ports is developed. The switch throughput, mean cell delay, and cell loss probability are computed from the analytical model. The accuracy of the analytical model is verified using simulation     

Omega network-based ATM switch with neural network-controlledbypass queueing and multiplexing

Multistage interconnection networks (MINs) have long been studied for use in switching networks. Since they have a unique path between source and destination and the intermediate nodes of the paths are shared, internal blocking can cause very poor throughput. This paper proposes a high throughput ATM switch consisting of an Omega network with a new form of input queues called bypass queues. We also improve the switch throughput by partitioning the Input buffers into disjoint buffer sets and multiplexing several sets of nonblocking cells within a time slot, assuming that the routing switch operates only a couple of times faster than the transmission rate. A neural network model is presented as a controller for cell scheduling and multiplexing in the switch. Our simulation results under uniform traffic show that the proposed approach achieves almost 100% of potential switch throughput     

A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks

As the operation of our fiber-optic backbone networks migrates from interconnected SONET rings to arbitrary mesh topology, traffic grooming on wavelength-division multiplexing (WDM) mesh networks becomes an extremely important research problem. To address this problem, we propose a new generic graph model for traffic grooming in heterogeneous WDM mesh networks. The novelty of our model is that, by only manipulating the edges of the auxiliary graph created by our model and the weights of these edges, our model can achieve various objectives using different grooming policies, while taking into account various constraints such as transceivers, wavelengths, wavelength-conversion capabilities, and grooming capabilities. Based on the auxiliary graph, we develop an integrated traffic-grooming algorithm (IGABAG) and an integrated grooming procedure (INGPROC) which jointly solve several traffic-grooming subproblems by simply applying the shortest-path computation method. Different grooming policies can be represented by different weight-assignment functions, and the performance of these grooming policies are compared under both nonblocking scenario and blocking scenario. The IGABAG can be applied to both static and dynamic traffic grooming. In static grooming, the traffic-selection scheme is key to achieving good network performance. We propose several traffic-selection schemes based on this model and we evaluate their performance for different network topologies.     

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.