Equivalent permutation capabilities between time-division opticalOmega networks and non-optical extra-stage Omega networks

Because signals carried by two waveguides entering a common switch element would generate crosstalk, a regular N×N multistage interconnection network (MIN) cannot be directly used as an optical switch between N inputs and N outputs in an optical network. A simple solution is to use a 2N×2N cube-type MIN to provide the N×N connections, which needs a much larger hardware cost. A previous research proposed another solution, called the time-domain approach, that divides the N optical inputs into several groups such that crosstalk-free connections can be provided by an N×N regular MIN in several time slots, one for each group. Researchers studied this approach on Omega networks and defined the class set &thetas; to be the set of N-permutations realizable in two time slots on an Omega network. They proved that the size of &thetas; is larger than the size of class Ω, where Ω consists of all N-permutations admissible to a regular N×N (nonoptical) Omega network. This paper first presents an optimal O(NlogN) time algorithm for identifying whether a given permutation belongs to class &thetas; or not. Using this algorithm, this paper then proves an interesting result that the class &thetas; is identical to the class Ω+1 which represents the set of N-permutations admissible to a nonoptical N×N one-extra stage Omega network     

A universal analytic model for photonic Banyan networks

One of the important considerations in designing waveguide-based photonic switching networks is to avoid crosstalk. Two approaches have been proposed which dilate a network in the space and time domains, respectively, to establish crosstalk-free connections. The space-domain dilation uses more hardware, representing cost in space, while the time-domain dilation uses more rounds (or time slots), representing cost in time. In order to evaluate the space-time tradeoffs involved in these two approaches, an analytical model is developed. We describe a recursive procedure which calculates the probability that a new connection can be established without crosstalk in a Banyan (or dilated Banyan) network by taking into consideration the dependency between traffic distributions at different stages. A Markov process based on such probabilities is then used to determine the average number of rounds needed for a set of one-to-one random connections. The model is applicable to both Banyan and dilated Banyan networks, with either stage or individual control. Simulation results are also obtained and compared to the analytic results. We show that the time-domain approach can achieve better space-time tradeoffs than the space-domain approach. One of the practical implications of this result is that a multiplane Banyan network may be more cost-effective than a dilated Banyan in avoiding crosstalk     

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.     

A New Scheme to Realize Crosstalk-Free Permutation in Vertically Stacked Optical MINs*

Vertical stacking is a novel alternative for constructing nonblocking multistage interconnection networks (MINs). Rearrangeably nonblocking optical MINs are attractive since they have lower complexity than their strictly nonblocking counterparts. In this paper, we study the realization of crosstalk-free permutations in rearrangeably nonblocking, self-routing banyan-type optical MINs built on vertical stacking. An available scheme for realizing crosstalk-free permutation in this type of optical MINs requires to first decompose a permutation into multiple crosstalk-free partial permutations based on the Euler-Split technique, and then to realize them crosstalk-free in different planes (stacked copies) of the MIN simultaneously. The overall time complexity of this scheme to realize a crosstalk-free permutation in an N × N optical MIN is O(N log N) which is dominated by the complexity of crosstalk-free decomposition. In this paper, we propose a new scheme for realizing permutations in this class of vertically stacked optical MINs crosstalk-free. The basic idea of the new scheme is to classify permutations into permutation classes such that all permutations in one class share the same crosstalk-free decomposition pattern. By running the Euler-Split based crosstalk-free decomposition only once for a permutation class and applying the obtained crosstalk-free decomposition pattern to all permutations in the class, crosstalk-free decomposition of permutations can be realized in a more efficient way. We show that the number of permutations in a permutation class is huge (N!)^N when log₂N is even and (2N!)^N/2 when log₂N is odd), and thus the average time complexity of crosstalk-free decomposition of a permutation becomes O(N).     

Parallel routing algorithms in Benes-Clos networks

A new parallel algorithm for route assignments in Benes-Clos (1962, 1953) networks is studied. Most known sequential route assignment algorithms, such as the looping algorithm, are designed for circuit switching systems where the switching configuration can be rearranged at relatively low speed. In packet switching systems, switch fabrics must be able to provide internally conflict-free paths simultaneously, and accommodate packets requesting connections in real time as they arrive at the inputs. In this paper, we develop a parallel routing algorithm for Benes networks by solving a set of Boolean equations which are derived from the connection requests and the symmetric structure of the networks. Our approach can handle partial permutations easily. The time complexity of our algorithm is O(log/sup 2/ N), where N is the network size. We also extend the algorithm and show that it can be applied to the Clos networks if the number of central modules is M=2/sup m/, where m is a positive integer. The time complexity is O(log N/spl times/log M) in this case.     

Optical crossconnects of reduced complexity for WDM networks withbidirectional symmetry

One promising approach to provisioning and restoration in long-haul wavelength-division-multiplexing (WDM) networks is to deploy a mesh of optical crossconnects that operate on individual wavelengths. As wavelength-count and traffic demand rapidly increase, however, this approach will likely require high-port-count optical crossconnects that severely strain the capabilities of known device technologies. Thus, it is critical to devise ways to build large crossconnects from a small number of constituent switches, each with reduced port count. We present a general means of accomplishing this for networks, such as current long-haul networks, that demonstrate bidirectional symmetry. We describe a broad class of symmetry-exploiting architectures that yield N×N crossconnects, both rearrangeably nonblocking and strictly nonblocking, using constituent switch fabrics no larger than N/2×N/2. By exploiting connection-symmetry, these architectures reduce the number of such N/2×N/2 fabrics by 30%-50% compared with corresponding fully connected three-stage Benes and Clos switch structures     

A novel switching architecture for ATM networks

It is known that the flexibility and capacity of asynchronous transfer mode (ATM) networks can meet the bandwidth requirements of multimedia applications. In ATM networks, switching is one of the major bottlenecks of end-to-end communication. We propose using a multiple partitionable circular bus network (MPCBN) as an ATM switch. Connection requests are first transformed into a graph where vertices and edges represent connection requests and conflicts among connection requests, respectively. We then use a graph traversal algorithm to select a maximal set of requests for execution in physically partitioned buses. An approach of using finite projective planes is then used to reduce the number of switch points from O(N²) to O(N √N), where N is the number of ports of a switch. A performance evaluation for both uniform and bursty data sources shows that the approach of using finite projective planes to reduce the number of switch points results in a small increase of cell loss probability     

Blocking performance of time switching in TDM wavelength routing networks

Advances in optical WDM technology have paved the way for high-capacity wavelength channels capable of carrying information at Gb/s rates. However, with current traffic streams requiring only a fraction of a wavelength’s bandwidth, it becomes necessary to groom these independent low rate traffic streams on to higher capacity wavelength channels. An all-optical approach to grooming is to allow many connections to time-share a wavelength. Accordingly, in a TDM wavelength routing network, the establishment of a connection requires the assignment of time slots in addition to routing and wavelength assignment. One of the primary challenges in such networks is the need for quick reconfiguration at the routing nodes. In this paper, we investigate the effects of switch reconfigurability, wavelength conversion and time slot interchangers (TSIs) on the blocking performance of connections with multiple rates. Heuristics for time slot assignment that consider constraints imposed by six different node architectures are proposed, and the blocking performance of the TDM wavelength routing network is evaluated through simulations. Results indicate that limited reconfigurability at the nodes is sufficient to attain the performance obtained with full reconfigurability, especially when connections occupy only a small fraction of the wavelength capacity. Furthermore, the blocking performance is not seen to benefit significantly with the introduction of wavelength converters and TSIs, thus signifying that the improvement in blocking is largely dependent on the switch reconfigurability at the nodes.     

Tunable laser-based design and analysis for fractional lambda switches

Fractional lambda switching (FlambdaS) is a novel approach for traffic management over all-optical networks with sub-wavelength provisioning capability. The unique characteristic of FlambdaS is the utilization of UTC (coordinated universal time) for switching with minimum or no buffers. Several central research issues are still open in FlambdaS and need to be formally defined and analyzed. In this paper, we introduce three novel switch designs that are based on the use of tunable lasers (which can be replaced in the future with wavelength converters). First, the paper presents analytical results of scheduling feasibility, which measures the total number of possible different schedules for each switch design. Then it is shown that the architecture with the highest scheduling feasibility is strictly non blocking in the space domain. Next, the paper provides a closed form analysis of the blocking probability in the time domain, which is applicable for any strictly non-space blocking switch, using combinatorics. In addition, the paper provides measures of the switching hardware complexity, which, for the strictly non-blocking architecture, has the same switching complexity as Clos interconnection network, i.e., O(N'radic(N')) where N' is the number of optical channels.     

DEC-MAC: delay- and energy-aware cooperative medium access control protocol for wireless sensor networks

This paper deals with two critical issues in wireless sensor networks: reducing the end-to-end packet delivery delay and increasing the network lifetime through the use of cooperative communications. Here, we propose a delay- and energy-aware cooperative medium access control (DEC-MAC) protocol, which trades off between the packet delivery delay and a node’s energy consumption while selecting a cooperative relay node. DEC-MAC attempts to balance the energy consumption of the sensor nodes by taking into account a node’s residual energy as part of the relay selection metric, thus increasing the network’s lifetime. The relay selection algorithm exploits the process of elimination and the complementary cumulative distribution function for determining the most optimal relay within the shortest time period. Our numerical analysis demonstrates that the DEC-MAC protocol is able to determine the optimal relay in no more than three mini slots. Our simulation results show that the DEC-MAC protocol improves the end-to-end packet delivery latency and the network lifetime significantly compared to the state-of-the-art protocols, LC-MAC and CoopMAC.     

Birkhoff-von Neumann input-buffered crossbar switches forguaranteed-rate services

Based on a decomposition result by Birkhoff (1946) and von Neumann (1953) for a doubly sub-stochastic matrix, in this letter we propose a scheduling algorithm that is capable of providing guaranteed-rate services for input-buffered crossbar switches. Our guarantees are uniformly good for all nonuniform traffic. The computational complexity to identify the scheduling algorithm is O(N^4.5) for an N×N switch. Once the algorithm is identified, its on-line computational complexity is O(log N) and its on-line memory complexity is O(N³ log N)     

Time slot switching for integrated services in fiber optic PBX/LAN

A medium-access protocol called time-slot switching (TSS) is proposed for use in optical-fiber local area networks. This protocol incorporates features of time division, space division, and time compression for users to share a common medium. Very-large-integration (VLSI) CMOS electric crosspoints are used to switch traffic within individual time slots. With these features, data, voice, and video services can all be combined in a single network. In addition, the speed of the electronics can be maximized to match the available optical bandwidth. Operational principles of the TSS protocol are explained. A performance analysis is presented to show the tradeoffs among traffic capacity, frame guard time, blocking probability, and the results show that TSS is more attractive than broadcast protocols for voice traffic or constant-rate data traffic. An approach to integrating voice, data, and video traffic within TSS is also described     

Timing Synchronization in MF-TDMA Systems for Geostationary Satellites[Topics in Radio Communications]

The most expensive costs in satellite communication are incurred by the space segment. Therefore, effort should be focused on the efficient use of this resource. One aspect is the optimization of the physical layer, to approach the Shannon limit of channel capacity. In IP-based networks, communication between arbitrary terminals can be established, which must hold for IP-based satellite networks as well. A commonly used topology is the star network, where data are routed via the master station, which in case of satellite communications introduces a double hop for terminal-to-terminal connections [1]. A double hop requires twice the bandwidth and twice the response time, which is very unattractive for interactive services. This drawback is avoided with a fully meshed topology, where terminals can communicate directly. Of course, an appropriately designed access system is required in this context. The well-known multi-frequency, time-division multiple access (MF-TDMA) scheme slices the channel capacity along both time and frequency axes. Each fragment (slot) can be used by any station for direct communication [2, 3]. This article describes the method on an abstraction layer, starting with the high-level timing that copes with frame numbers; the low-level timing that maps the frame numbers to time instants of the local time scale; and ends with the time stamp handled in the hardware, where calculation delays and filter flushing affect the received time stamp. Compared to commercial systems, the method described in this article uses differential time stamps, which reduces the effort of the synchronization procedure.     

The λ-scheduler: A multiwavelength scheduling switch

We propose a new multiwavelength almost all-optical switch architecture called the λ-scheduler that uses wavelength division multiplexing (WDM) internally to fold the switch architecture in both the space and time domains to reduce the hardware complexity and to improve the signal characteristics through the switch. The λ-scheduler preserves the packet order for a given input-output pair, is consistent with virtual circuit switching, and when combined with appropriate connection and flow control protocols, provides lossless communication for bursty (or nonconstant rate) traffic, provided the traffic satisfies certain smoothness properties. The λ-scheduler uses novel scheduling and wavelength assignment algorithms, in conjunction with a series of feed-forward delay blocks, to avoid packet collisions within the switch or at the switch outputs. We present two implementations of the λ-scheduler when the number of internal wavelengths k equal the number of inputs (and outputs) N to the switch. In the compressed λ-scheduler, the N internal wavelengths are used to fold the architecture in the time domain, which reduces the total number of delay blocks for the switch by 2N log N. In the collapsed λ-scheduler, the N internal wavelengths are used to fold the architecture in the space domain, which reduces the number of delay blocks and total fiber length used for delays by a factor of N. We examine the insertion loss for both λ-scheduler implementations and discuss the trade-offs between the reduction in overall component count and the improvement in the signal characteristics     

Matching output queueing with a combined input/output-queued switch

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N×N switch, a “speedup” of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies     

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.     

A large scalable ATM multicast switch

This paper focuses on designing a large N×N high-performance broad-band ATM switch. Despite advances in architectural designs, practical switch dimensions continue to be severely limited by both the technological and physical constraints of packaging. Here, we focus on augmentation in a “single-switch” design: we provide ways to construct arbitrarily large switches out of modest-size components and retain overall delay/throughput performance. We propose a growable switch architecture based on several key principles: 1) the knockout principle exploits the statistical behavior of cell arrivals, and thereby reduces the interconnect complexity; 2) output queueing yields the best possible delay/throughput performance; 3) distributed control in routing (multicast) cells through the interconnect fabric without internal path conflicts; and 4) simple basic building blocks facilitate scalability. Other attractive features of the proposed architecture include: 1) intrinsic broadcast and multicast capabilities; 2) built-in priority sorting functionality; and 3) the guarantee of first-in, first-out cell sequence, To achieve 10^-14 cell loss probability, only maximum size 32×16 basic building modules are required, and no crossover interconnects exist between modules in a three-dimensional configuration     

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     

Architecture, performance, and implementation of the tandem banyanfast packet switch

The authors propose a new space-division fast packet switch architecture based on banyan interconnection networks, called the tandem banyan switching fabric (TBSF). It consists of placing banyan networks in tandem, offering multiple paths from each input to each output, thus overcoming in a very simple way the effect of conflicts among packets (to which banyan networks are prone) and achieving output buffering. From a hardware implementation perspective, this architecture is simple in that it consists of several instances of only two VLSI chips, one implementing the banyan network and the other implementing the output buffer function. The basic structure and operation of the tandem banyan switching fabric are described, and its performance is discussed. The authors propose a modification to the basic structure which decreases the hardware complexity of the switch while maintaining its performance. An implementation of the banyan network using a high-performance BiCMOS sea-of-gates on 0.8-μm technology is reported     

A network coding based interference cancelation scheme for wireless ad hoc networks

The performance of wireless networks is limited by multiple access interference (MAI) in the traditional communication approach where the interfered signals of the concurrent transmissions are treated as noise. In this paper, we treat the interfered signals from a new perspective on the basis of additive electromagnetic (EM) waves and propose a network coding based interference cancelation (NCIC) scheme. In the proposed scheme, adjacent nodes can transmit simultaneously with careful scheduling; therefore, network performance will not be limited by the MAI. Additionally we design a space segmentation method for general wireless ad hoc networks, which organizes network into clusters with regular shapes (e.g., square and hexagon) to reduce the number of relay nodes. The segmentation method works with the scheduling scheme and can help achieve better scalability and reduced complexity. We derive accurate analytic models for the probability of connectivity between two adjacent cluster heads which is important for successful information relay. We proved that with the proposed NCIC scheme, the transmission efficiency can be improved by at least 50% for general wireless networks as compared to the traditional interference avoidance schemes. Numeric results also show the space segmentation is feasible and effective. Finally we propose and discuss a method to implement the NCIC scheme in a practical orthogonal frequency division multiplexing (OFDM) communications networks. Copyright © 2009 John Wiley & Sons, Ltd.