Optimizing complexity in Benes-type WDM switching networks

In this paper, we propose a new Benes-type wavelength division multiplexing (WDM) optical network with space-wavelength switching capability. Intuitively, adding wavelength switching capability to space Benes networks requires the use of additional hardware components (i.e., wavelength converters). However, in this paper, we show that a Benes network with full-permutation capability in both space and wavelength domains can be designed using a smaller number of hardware components but the same number of stages as that in a space-only Benes network. In addition, wavelength conversion in the proposed network occurs only between two pre-defined wavelengths, eliminating the need for any expensive wide-range wavelength converters. The proposed Benes network is based on the newly proposed concept of wavelength-exchangeable permutation networks. Wavelength-exchangeable networks implement single-step space and wavelength switching and hence reduces the number of hardware components. We show that, such wavelength-exchangeable networks possess some interesting properties that can be used for designing routing algorithms to improve signal quality.

A scalable optical WDM multicast Beneš network with multi-channel wavelength converters

An optical wavelength division multiplexing (WDM) multicast network interconnects an input signal on a given wavelength to one or more output fibers, possibly on different wavelengths (via wavelength conversion), while maintaining the signal in the optical domain. A key challenge in the design of scalable multicast networks is to reduce conversion complexity without affecting the switching capability and signal quality. In this article, we propose a scalable WDM multicast Beneš interconnection network with minimized conversion complexity. The proposed network is based on the Copy-and-Route architecture, and it uses multi- channel WCs (MCWCs) for wavelength conversion. The conversion complexity of the proposed design is O(F log₂ W) (where F is the number of fibers and W is the number of wavelengths per fiber), which is smaller than the O(FW) complexity of the optimal design based on conventional single-channel WCs (SCWCs). We prove that, for W >  64 and for any value of F, the conversion complexity of the new design is strictly less than that of the optimal SCWC-based design regardless of the total number of wavelengths simultaneously converted by each MCWCs. Analyzes of conversion complexity of the proposed design for large values of W confirm considerable savings compared to the optimal SCWC-based design. For instance, for W = 256 and an for an arbitrary value of F, a practical implementation of the proposed design achieves 87% reduction in conversion complexity as compared to the optimal SCWC-based design.     

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 location‐aware peer‐to‐peer overlay network

This work describes a novel location‐aware, self‐organizing, fault‐tolerant peer‐to‐peer (P2P) overlay network, referred to as Laptop. Network locality‐aware considerations are a very important metric for designing a P2P overlay network. Several network proximity schemes have been proposed to enhance the routing efficiency of existing DHT‐based overlay networks. However, these schemes have some drawbacks such as high overlay network and routing table maintenance overhead, or not being completely self‐organizing. As a result, they may result in poor scalability as the number of nodes in the system grows. Laptop constructs a location‐aware overlay network without pre‐determined landmarks and adopts a routing cache scheme to avoid maintaining the routing table periodically. In addition, Laptop significantly reduces the overlay maintenance overhead by making each node maintain only the connectivity between parent and itself. Mathematical analysis and simulations are conducted to evaluate the efficiency, scalability, and robustness of Laptop. Our mathematical analysis shows that the routing path length is bounded by log_d N, and the joining and leaving overhead is bounded by d log_d N, where N is the number of nodes in the system, and d is the maximum degree of each node on the overlay tree. Our simulation results show that the average latency stretch is 1.6 and the average routing path length is only about three in 10 000 Laptop nodes, and the maximum degree of a node is bounded by 32. Copyright © 2006 John Wiley & Sons, Ltd.     

A new approach to peer-to-peer wireless LANs based on ultra wide band technology

The advent of Ultra Wide Band (UWB) technology offers a unique opportunity to consider a new type of peer-to-peer wireless Local Area Network (LAN) that requires neither access at a peak data rate commensurate with the full bandwidth of the medium nor a conventional medium access protocol. Rather, due to the extraordinarily high bandwidth afforded by UWB, which is typically much greater than the peak bandwidth required by any ad-hoc radio node, one might imagine a network for which pairs of nodes are interconnected by one or more dedicated (non-shared) radio channels created by time, frequency, or code division multiplexing. In this paper, we consider a network containing N ad-hoc nodes and 2N independent radio channels. Starting with (1) an N × N power matrix, where element p _i,j represents the power needed for a successful transmission from node i to node j including the effects of path loss and shadow fading, and (2) a second N × N traffic matrix where element t _i,j represents the exogenous traffic originating from node i and destined for node j, we seek to assign radio channels and multi-hop route the traffic between source-destination pairs such that the resulting connectivity pattern and traffic flow minimize the average transmit energy needed to deliver a packet between an arbitrarily chosen pair of nodes. With no medium access protocol needed, collisions cannot occur and retransmissions become unnecessary. Moreover, the available capacity grows with the number of channels created (or, alternatively, as some common set of channels are re-used on a non-interfering basis via sufficient spatial separation). In this fashion, such a UWB ad-hoc network takes on the characteristics of a multi-hop Wavelength-Division Multiplexed (WDM) network well known from the multihop lightwave network art, although the constraints and dynamics are certainly different. Since the optimum connectivity and flow problem is shown to be NP hard, several heuristics are considered and compared. These heuristics seek, first, to establish a “good” connectivity graph, and then to flow the traffic in an optimum fashion. Our results suggest that application of these techniques may provide a distinct wireless LAN advantage achievable only via UWB radio technology, and several opportunities for future work based on this novel approach to ad-hoc local area radio networks are identified and discussed. Marc Krull received his B.S. degree in electrical engineering from Brown University in 2001 and his M.S. degree in electrical engineering from the University of California, San Diego in 2004. His graduate research focused on the investigation of energy efficient routing protocols for ultrawideband networks. He is currently with Raytheon Companys Intelligence and Information Systems division in Aurora, Colorado, where he is involved in software development for satellite ground systems. Anthony Acampora is a Professor of Electrical and Computer Engineering at the University of California, San Diego, and is involved in numerous research projects addressing various issues at the leading edge of telecommunication networks, including the Internet, ATM, broadband wireless access, network management and dense wavelength division multiplexing. From 1995 through 1999, he was Director of UCSDs Center for Wireless Communications, responsible for an industrially funded research effort which included circuits, signal processing, smart antennas, basic communication theory, wireless telecommunications networks, infrastructure for wireless communications, and software for mobility. Prior to joining the faculty at UCSD in 1995, he was Professor of Electrical Engineering at Columbia University and Director of the Center for Telecommunications Research, a National Science Foundation Engineering Research Center. He joined the faculty at Columbia in 1988 following a 20-year career at AT&T Bell Laboratories, most of which was spent in basic research where his interests included radio and satellite communications, local and metropolitan area networks, packet switching, wireless access systems, and lightwave networks. His most recent position at Bell Labs was Director of the Transmission Technology Laboratory where he was responsible for a wide range of projects, including broadband networks, image communications, and digital signal processing. At Columbia, he was involved in research and education programs concerning broadband networks, wireless access networks, network management, optical networks and multimedia applications. He received his PhD. in Electrical Engineering from the Polytechnic Institute of Brooklyn and is Fellow of the IEEE and a former member of the IEEE Communication Society Board of Governors. Professor Acampora has published over 160 papers, holds 33 patents, and has authored a textbook entitled An Introduction to Broadband Networks: MANs, ATM, B-ISDN, Self Routing Switches, Optical Networks, and Network Control for Voice, Data, Image and HDTV Telecommunications. He sits on numerous telecommunications advisory committees and frequently serves as a consultant to government and industry.     

SYNC‐NET: distributed time synchronization in clustered sensor networks

Time synchronization is essential for several ad‐hoc network protocols and applications, such as TDMA scheduling and data aggregation. In this paper, we propose a time synchronization framework for clustered, multi‐hop sensor networks. We assume that relative node synchronization is sufficient, that is, consensus on one time value is not required. Our goal is to divide the network into connected synchronization regions (nodes within two‐hops) and perform inter‐regional synchronization in O(LLSync) × N_iter time, where O(LLSync) denotes the complexity of the underlying low‐level synchronization technique (used for single‐hop synchronization), and N_iter denotes the number of iterations where the low‐level synchronization protocol is invoked. Thus, our main objective is rapid convergence. We propose novel fully distributed protocols, SYNC‐IN and SYNC‐NET, for regional and network synchronization, respectively, and prove that N_iter is O(1) for all protocols. Our framework does not require any special node capabilities (e.g., being global positioning systems (GPS)‐enabled), or the presence of reference nodes in the network. Our framework is also independent of the particular clustering, inter‐cluster routing, and low‐level synchronization protocols. We formulate a density model for analyzing inter‐regional synchronization, and evaluate our protocols via extensive simulations. Copyright © 2007 John Wiley & Sons, Ltd.     

On minimizing the total power of <Emphasis Type="Italic">k</Emphasis>-strongly connected wireless networks

Given a wireless network, we want to assign each node a transmission power, which will enable transmission between any two nodes (via other nodes). Moreover, due to possible faults, we want to have at least k vertex-disjoint paths from any node to any other, where k is some fixed integer, depending on the reliability of the nodes. The goal is to achieve this directed k-strong connectivity with a minimal overall power assignment. The problem is NP-Hard for any k ≥ 1 already for planar networks. Here we first present an optimal power assignment for uniformly spaced nodes on a line for any k ≥ 1. We also prove a number of useful properties of power assignment which are also of independent interest. Based on it, we design an approximation algorithm for linear radio networks with factor min{2,(\frac \Updelta d)^a },\hbox{min}\left\{2,\left(\frac {\Updelta} {\delta}\right)^\alpha \right\}, where Δ and δ are the maximal and minimal distances between adjacent nodes respectively and parameter α ≥ 1 being the distance-power gradient. We then extend it to the weighted version. Finally, we develop an approximation algorithm with factor O(k ²), for planar case, which is, to the best of our knowledge, the first non-trivial result for this problem.     

Joint routing and dimensioning of optical burst switching networks

Existing methods for handling routing and dimensioning in dynamic WDM networks solve the two problems separately. The main drawback of this approach is that a global minimum cost solution cannot be guaranteed. Given that wavelengths are costly resources, determining the minimum network cost is of fundamental importance. We propose an approach which jointly solves the routing and dimensioning problems in optical burst switching (OBS) networks, guaranteeing a target blocking per connection. The method finds the set of routes and the number of wavelengths per network link that minimise the total network cost. To accomplish this, an integer linear programming problem is solved. The proposed method was applied to ring networks, where the optimal solution achieves a reduction in the network cost of 10–40% (for traffic loads <0.4, compared to solving both problems separately). In the case of mesh topologies, to reduce the computational complexity of the method, we applied a variation of it which achieves a local minimum. Even so, a reduction of 5–20% (for traffic loads <0.4) in the network cost was obtained. This ability to lower network cost could make the proposed method the best choice to date for dynamic network operators.     

Importance‐based data transmission optimization in multi‐source single‐sink wireless sensor networks

Energy‐efficient routing becomes one of the most critical technologies for sustaining the overall network lifetime of wireless sensor networks. In this paper, we propose a novel data transmission scheme between a number of specified source nodes and the single sink, which can efficiently restrict the usage frequency of each relay node, measured by the number of source nodes using it for data transmission. On the basis of the importance of source nodes that is closely related to deployed location, they form a descending sequence such that each node finds the minimum energy path earlier than the succeeding one. Then, the energy‐efficient multiple path algorithm with the computational complexity of O(n³) is developed for deriving the minimum energy paths, where n is the number of nodes in the network. Also, a polynomial algorithm is presented for deriving the range of the feasible values of N₀ serving as the threshold of the usage frequency of relay nodes, in which each can guarantee the existence of the solution. Further, we theoretically investigate the existence of the solution and the tree‐structured solution using m‐ary tree. Extensive simulation results show that our proposed scheme can achieve significant performance enhancement. Copyright © 2012 John Wiley & Sons, Ltd.     

Burst scheduling for differentiated services in optical burst switching WDM networks

Optical burst switching (OBS) is one of the most important switching technologies for future optical wavelength division multiplexing (WDM) networks and the Internet. The model of differentiated services has been proposed to support quality of service (QoS) in the IP‐based Internet. It is also very important to have differentiated service support in OBS networks. When the burst scheduling in an OBS network is set up appropriately, network can support differentiated services. In this paper, we proposed a new burst scheduling scheme, called differentiated scheduling with identical priority offset time (DSIPO). In DSIPO, the same priority offset time is used for all the bursts destined to the same edge node regardless of their priorities. Differentiated services in terms of burst loss probability are achieved by processing the control packets of higher priority class bursts, thus reserving resources for their data bursts, more promptly upon their arrival than those of lower priority class bursts. Each intermediate (core) node can adjust the burst loss probabilities of various burst classes by choosing its own differentiated processing delay value for each priority class or its own differentiated processing delay difference value between any pair of adjacent priority classes. We model and analyse DSIPO in terms of the burst loss probability for each priority class with simulation validation. The performance of DISPO is evaluated by simulation. Copyright © 2004 John Wiley & Sons, Ltd.     

An Overview of Scaling Laws in Ad Hoc and Cognitive Radio Networks

Currently, wireless communications are changing along the lines of three main thrusts. The first is the introduction of secondary spectrum licensing (SSL). Regulations on the usage of licensed spectra are being loosened, encouraging unused primary spectrum to be licensed, often in an opportunistic manner, to secondary devices. The second is the introduction of cognitive radios. These wireless devices are able to sense and adapt in a “smart” manner to their wireless environment, making them prime candidates to becoming secondary users in SSL initiatives. Finally, as we approach the communication limits of point-to-point channels, and as wireless devices become cheap and ubiquitous, the focus is shifting from single to multiple communication links, or networks. In this paper, we provide an overview of the recently established theoretical limits, in the form of sum-rates, or throughput, of two main types of networks: ad hoc networks, in which the devices are homogeneous, and cognitive networks, in which a mixture of primary and secondary (or cognitive) devices are present. We summarize and provide intuition on how the throughput of a network scales with its number of nodes n, as n → ∞, under different network and node capability assumptions.

Models and Approximation Algorithms for Channel Assignment in Radio Networks

We consider the frequency assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with a certain geometric structure. The problem of broadcast scheduling can be cast as a variant of the vertex coloring problem (called the distance-2 coloring problem) on the graph that models a given packet radio network. We present efficient approximation algorithms for the distance-2 coloring problem for various geometric graphs including those that naturally model a large class of packet radio networks. The class of graphs considered include (r,s)-civilized graphs, planar graphs, graphs with bounded genus, etc.     

Optical network design to minimize switching and transceiver equipment costs

We consider a network consisting of N nodes and a certain number of links M that could be used to interconnect these nodes. The problem we address is to determine the smallest subset of switching nodes (in which to provide optical or electronic switching capability) necessary and sufficient to provide full end-to-end connectivity among all nodes. It is shown that this selection leads to the minimum number of transceivers needed to achieve full connectivity. We then address the same problem with the additional requirement of survivability, whereby the failure of any one link does not lead to any disconnection in the network. To solve the above stated problems, we employ heuristic and optimal algorithms; we find that the minimum number of switching sites is well estimated as a function of a single parameter, the network connectivity . (This is an extended version of the paper presented at Broadnets 2006.)     

Distributed Dijkstra sparse placement routing algorithm for translucent optical networks

In this paper we study translucent optical networks as an alternative to fully transparent and fully opaque optical networks. In the former networks, a technique called sparse placement is used to overcome the lightpath blocking caused by the signal quality degradation, using much less regenerators, which must strategically be placed, in contrast to a fully opaque network. In this paper we propose a sparse placement algorithm based on two requirements. The first one is signal regeneration necessary to re-amplify, reshape, and retime the optical signals after some predefined transparent distance in order to successfully receive the signals at the destination node. The other is load balance of the traffic in the network aimed at efficient usage of the network capacity resources. We apply a distributed Dijkstra routing algorithm which dynamically changes weights of links during the process of locating regeneration capable nodes. We compare the performance of the proposed algorithm with commonly used sparse placement algorithms through simulation experiments. The benefits are such that load balancing of the network traffic is fully utilized, and with technological development it will be sufficient to equip up to 30% of nodes in the network with electronic regenerations in order to have the same performance as in an opaque network.

An energy‐efficient localized topology control algorithm for wireless ad hoc and sensor networks

Topology control plays an important role in the design of wireless ad hoc and sensor networks and has demonstrated its high capability in constructing networks with desirable characteristics such as sparser connectivity, lower transmission power, and smaller node degree. However, the enforcement of a topology control algorithm in a network may degrade the energy‐draining balancing capability of the network and thus reduce the network operational lifetime. For this reason, it is important to take into account energy efficiency in the design of a topology control algorithm in order to achieve prolonged network lifetime. In this paper, we propose a localized energy‐efficient topology control algorithm for wireless ad hoc and sensor networks with power control capability in network nodes. To achieve prolonged network lifetime, we introduce a concept called energy criticality avoidance and propose an energy criticality avoidance strategy in topology control and energy‐efficient routing. Through theoretical analysis and simulation results, we prove that the proposed topology control algorithm can maintain the global network connectivity with low complexity and can significantly prolong the lifetime of a multi‐hop wireless network as compared with existing topology control algorithms with little additional protocol overhead. Copyright © 2008 John Wiley & Sons, Ltd.     

Symbiotic Networks: Towards a New Level of Cooperation Between Wireless Networks

In the future, many wireless networks, serving diverse applications, will co-exist in the same environment. Today, wireless networks are mostly optimized in a rather opportunistic and/or selfish way: optimizations methods only use a local view of the network and environment, as they try to achieve the best performance within its own network. The optimizations are very often limited to a single layer and cooperation between networks is only happening through the use of gateways. In this paper, we suggest an alternative paradigm for supporting cooperation between otherwise independent networks, called ‘symbiotic networking’. This new paradigm can take many forms, such as sharing of network resources, sharing of nodes for communal routing purposes and sharing of (networking) services. Instead of optimizing network parameters within the individual networks, symbiotic networking solutions operate across network boundaries. Parameters are optimized between the networks and communal protocols are developed, leading to a more global optimization of the scarce network resources. In this paper, we describe several scenarios which can profit from symbiotic networking and illustrate a strategy for supporting networking protocols which can operate across network boundaries. Ultimately, through the disappearance of network boundaries and the introduction of cross-layer/cross-node/cross-network cooperation, symbiotic networks takes the notion of cooperation to a new level, paving the way for a true network symbiosis.

Uniform waveband assignment in optical mesh networks

The cost of an optical network in wavelength division multiplexing (WDM) networks can be reduced using optical reconfigurable optical add/drop multiplexers (ROADMs), which allow traffic to pass through without the need for an expensive optical-electro-optical (O-E-O) conversion. Waveband switching (WBS) is another technique to reduce the network cost by grouping consecutive wavelengths and switching them together using a single port per waveband. WBS has attracted the attention of researchers for its efficiency in reducing switching complexity and therefore cost in WDM optical networks. In this paper, we consider the problem of switching wavelengths as non-overlapping uniform wavebands, per link, for mesh networks using the minimum number of wavebands. Given a fixed band size b _s , we give integer linear programming formulations and present a heuristic solution to minimize the number of ROADMs (number of wavebands) in mesh networks that support a given traffic pattern. We show that the number of ROADMs (or number of ports in band-switching cross-connects) can be reduced significantly in mesh networks with WBS compared to wavelength switching using either the ILP or the heuristic algorithm. We also examine the performance of our band assignment algorithms under dynamic traffic.     

QoS‐aware target coverage in wireless sensor networks

Wireless sensor networks have emerged recently as an effective way of monitoring remote or inhospitable physical targets, which usually have different quality of service (QoS) constraints, i.e., different targets may need different sensing quality in terms of the number of transducers, sampling rate, etc. In this paper, we address the problem of optimizing network lifetime while capturing those diversified QoS coverage constraints in such surveillance sensor networks. We show that this problem belongs to NP‐complete class. We define a subset of sensors meeting QoS requirements as a coverage pattern, and if the full set of coverage patterns is given, we can mathematically formulate the problem. Directly solving this formulation however is difficult since number of coverage patterns may be exponential to number of sensors and targets. Hence, a column generation (CG)‐based approach is proposed to decompose the original formulation into two subproblems and solve them iteratively. Here a column corresponds to a feasible coverage pattern, and the idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the maximum lifetime solution. An initial feasible set of patterns is generated through a novel random selection algorithm (RSA), in order to launch our approach. Experimental data demonstrate that the proposed CG‐based approach is an efficient solution, even in a harsh environment. Simulation results also reveal the impact of different network parameters on network lifetime, giving certain guidance on designing and maintaining such surveillance sensor networks. Copyright © 2009 John Wiley & Sons, Ltd.     

Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing

The popularity of broadband streaming applications requires communication networks to support high-performance multicasting at the optical layer. Suffering from transmission impairments in multi-hop all-optical (transparent) WDM multicasting networks, the signal may be degraded beyond the receivable margin at some multicast destinations. To guarantee the signal quality, we introduce a translucent WDM multicasting network to regenerate the degraded signals at some switching nodes with electronic 3R (reamplification, reshaping and retiming) functionality. The translucent network is built by employing three kinds of multicasting capable switching architectures: (1) all-optical multicasting capable cross connect (oMC-OXC), (2) electronic switch and (3) translucent multicasting capable cross connect (tMC-OXC). Among them both the electronic switch and tMC-OXC are capable of electronic 3R regeneration. Furthermore, we propose a multicast-capable nodes placement algorithm based on regeneration weight, and two multicasting routing algorithms called nearest hub first and nearest on tree hub first to provide signal-quality guaranteed routes for the multicasting requests. The numerical simulation on two typical mesh networks shows that it is sufficient to equip 30% of the nodes or less with signal-regeneration capability to guarantee the signal quality.