Routing and dimensioning in optical networks under traffic growth models: an asymptotic approach

We consider the problem of routing and dimensioning in a large optical network where traffic is growing over time. A model of traffic in optical network lightpaths is presented. Lightpaths arrive randomly according to a time-varying Poisson process and hold for a random time with a general distribution. We propose a wavelength division multiplexing network that requires no capacity upgrading in a given time period T while allowing the operator to accommodate all the lightpath requests. We obtain an exact solution of the routing and dimensioning problem under an asymptotic regime where both the capacities and the arrival rates are large. For moderate link capacities, we propose a method to dimension the links so that the first lightpath request rejection occurs, with high probability, after the specified time T. This involves the computation of capacity-exhaustion probability $the probability that at least one lightpath request is rejected in the time period (0, T) due to lack of bandwidth/capacity on some link. Computation of the exact capacity-exhaustion probability is possible for a few specific holding time distributions (e.g., exponential). Since this requires large computing resources, it is feasible only for small networks. We propose a method to estimate the capacity-exhaustion probabilities for a large optical network with general holding time distribution based on the results of an asymptotic analysis. We show that this method has a low computational complexity and is quite accurate in the desired range of low capacity-exhaustion probabilities.     

Dependency-based analytical model for computing connection blocking rates and its application in the sparse placement of optical converters

In this paper, we present a new analytical model that captures link dependencies in all-optical wavelength-division multiplexing (WDM) networks under uniform traffic and enables the estimation of connection-blocking probabilities more accurately than previously possible. The basic formula of the dependency between two links in this model reflects their degree of adjacency, the degree of connectivity of the nodes composing them, and their carried traffic. Our validation tests have shown that the analytical dependency model gives accurate results and successfully captures the main dependency characteristics observed in the simulation measurements. The usefulness of the model is illustrated by showing how to use it in enhancing a simulation-based algorithm that we recently proposed for the sparse placement of full wavelength converters in WDM networks. To analytically handle the presence of wavelength converters, a lightpath containing converters is divided into smaller subpaths, such that each subpath is a wavelength-continuous path, and the nodes shared between these subpaths are full wavelength-conversion-capable. The blocking probability of the entire path is obtained by computing the probabilities in the individual subpaths. We validate the analytically-based sparse placement algorithm by comparing it with its simulation-based counterpart using a number of network topologies.     

A Virtual Wavelength Translation Scheme for Routing in All-Optical Networks

This paper considers wavelength routed WDM networks where multiple fibers are used for each communication link. For such networks, the effect of wavelength translation can be achieved without explicit use of wavelength translators. We call this as virtual wavelength translation and study the routing issues considering dynamic lightpath allocation. Using multiple (or a bundle of) fibers for each link also allows us to have bundles of varying sizes to accommodate anticipated differences in traffic through different communication links of the network. The paper considers the blocking probabilities of all-optical networks when centralized and distributed lightpath allocation schemes are used.     

Traffic grooming in an optical WDM mesh network

In wavelength-division multiplexing (WDM) optical networks, the bandwidth request of a traffic stream can be much lower than the capacity of a lightpath. Efficiently grooming low-speed connections onto high-capacity lightpaths will improve the network throughput and reduce the network cost. In WDM/SONET ring networks, it has been shown in the optical network literature that by carefully grooming the low-speed connection and using wavelength-division multiplexer (OADM) to perform the optical bypass at intermediate nodes, electronic ADMs can be saved and network cost will be reduced. In this study, we investigate the traffic-grooming problem in a WDM-based optical mesh topology network. Our objective is to improve the network throughput. We study the node architecture for a WDM mesh network with traffic-grooming capability. A mathematical formulation of the traffic-grooming problem is presented in this study and several fast heuristics are also proposed and evaluated     

Routing Mechanisms Employing Adaptive Weight Functions for Shortest Path Routing in Optical WDM Networks

Optical dense wavelength division multiplexed (DWDM) networks are an attractive candidate for the next generation Internet and beyond. In this paper, we consider routing and wavelength assignment in a wide area wavelength routed backbone network that employs circuit-switching. When a session request is received by the network, the routing and wavelength assignment (RWA) task is to establish a lightpath between the source and destination. That is, determine a suitable path and assign a set of wavelengths for the links on this path. We consider a link state protocol approach and use Dijkstras shortest path algorithm, suitably modified for DWDM networks, for computing the shortest paths. In [1] we proposed WDM aware weight functions that included factors such as available wavelengths per link, total wavelengths per link. In this paper, we present new weight functions that exploit the strong correlation between blocking probability and number of hops involved in connection setup to increase the performance of the network. We also consider alternate path routing that computes the alternate paths based on WDM aware weight functions. The impact of the weight functions on the blocking probability and delay is studied through discrete event simulation. The system parameters varied include number of network nodes, wavelengths, degree of wavelength conversion, and load. The results show that the weight function that incorporates both hop count and available wavelength provides the best performance in terms of blocking probability.     

Efficient algorithms for routing dependable connections in WDMoptical networks

We consider the problem of establishing dependable connections in WDM networks with dynamic traffic demands. We call a connection with fault-tolerant requirements a dependable connection (D-connection). We consider the single-link failure model in our study and recommend the use of a proactive approach, wherein a D-connection is identified with the establishment of the primary lightpath and a backup lightpath at the time of honouring the connection request. We develop algorithms to select routes and wavelengths to establish D-connections with improved blocking performance. The algorithms use the backup multiplexing technique to efficiently utilize the wavelength channels. To further improve channel utilization, we propose a new multiplexing technique called primary-backup multiplexing. Here, a connection may not have its backup lightpath readily available throughout its existence. We develop algorithms based on this technique to route D-connections with a specified restoration guarantee. We present an efficient and computationally simple heuristic to estimate the average number of connections per link that do not have backup lightpaths readily available upon a link failure. We conduct extensive simulation experiments on different networks to study the performance of the proposed algorithms     

Ant Colony Optimization for Dynamic RWA in WDM Networks with Partial Wavelength Conversion

Dynamic routing and wavelength assignment (RWA), which supports request arrivals and lightpath terminations at random times, is needed for rapidly changing traffic demands in wavelength division multiplexed, (WDM) networks. In this paper, a new distributed heuristic algorithm based on ant colony optimization for dynamic RWA is put forward. We consider the combination of route selection and wavelength assignment as a whole using a multilayer-graph model. Therefore, an extended multilayer-graph model for WDM networks with limited wavelength conversion is presented. Compared with other RWA methods, the Ant Colony heuristic algorithm can achieve better global network optimization and can reduce communication overhead cost of the networks. Simulation showed that a lower blocking probability and a more rational wavelength resource assignment can be achieved.     

Performance analysis of multicast routing and wavelength assignment protocol with dynamic traffic grooming in WDM networks

The need for on‐demand provisioning of wavelength‐routed channels with service‐differentiated offerings within the transport layer has become more essential because of the recent emergence of high bit rate Internet protocol (IP) network applications. Diverse optical transport network architectures have been proposed to achieve the above requirements. This approach is determined by fundamental advances in wavelength division multiplexing (WDM) technologies. Because of the availability of ultra long‐reach transport and all‐optical switching, the deployment of all‐optical networks has been made possible. The concurrent transmission of multiple streams of data with the assistance of special properties of fiber optics is called WDM. The WDM network provides the capability of transferring huge amounts of data at high speeds by the users over large distances. There are several network applications that require the support of QoS multicast, such as multimedia conferencing systems, video‐on‐demand systems, real‐time control systems, etc. In a WDM network, the route decision and wavelength assignment of lightpath connections are based mainly on the routing and wavelength assignment (RWA). The multicast RWA's task is to maximize the number of multicast groups admitted or minimize the call‐blocking probability. The dynamic traffic‐grooming problem in wavelength‐routed networks is generally a two‐layered routing problem in which traffic connections are routed over lightpaths in the virtual topology layer and lightpaths are routed over physical links in the physical topology layer. In this paper, a multicast RWA protocol for capacity improvement in WDM networks is designed. In the wavelength assignment technique, paths from the source node to each of the destination nodes and the potential paths are divided into fragments by the junction nodes and these junction nodes have the wavelength conversion capability. By using the concept of fragmentation and grouping, the proposed scheme can be generally applied for the wavelength assignment of multicast in WDM networks. An optimized dynamic traffic grooming algorithm is also developed to address the traffic grooming problem in mesh networks in the multicast scenario for maximizing the resource utilization and minimizing the blocking probability. Copyright © 2011 John Wiley & Sons, Ltd.     

Algorithms for Dynamic Routing in All-Optical Networks

In this paper, we have studied a number of algorithms for routing in all-optical wavelength routed networks. We have considered situations where a lightpath is dynamically created in response to a request for communication and the WDM channels constituting the lightpath are reclaimed when the communication is over. We have looked at two schemes for dynamic wavelength allocation. In the first scheme we have assumed the existence of a central agent to maintain a database of existing lightpaths where the central agent attempts to generate a new lightpath in response to a request for communication. In the second scheme, we attempt to generate a new lightpath using a distributed algorithm. In the first scheme we have exploited the existence of multiple paths between any pair of nodes in a network in order to reduce the blocking probability. For the second scheme, we have proposed three distributed strategies to determine, if possible, a lightpath when there is a request for communication. Each of these strategies have their advantages and disadvantages in terms of the expected blocking probability and the set-up time. We have studied the performances of both the schemes using Monte Carlo simulation.     

Optical resources provisioning: multipoint‐to‐point lightpaths mapping in all‐optical networks

In wavelength‐division multiplexing (WDM) optical networks, the bandwidth request of a traffic stream can be much lower than the capacity of a lightpath. Efficiently grooming low‐speed connections onto high‐capacity lightpaths will improve the network throughput and reduce the network cost. In this paper, we propose and evaluate a new concept of traffic aggregation in WDM mesh networks that aims to eliminate both the bandwidth under‐utilization and scalability concerns that are typical in all‐optical wavelength routed networks. This approach relies on the multipoint‐to‐point lightpath concept. In order to assess the efficiency of our proposal, all underlying network costs are compared. To achieve this aim, we devise a new provisioning algorithm to map the multipoint‐to‐point lightpaths in the network. Our results show that the proposed aggregation technique can significantly improve the network throughput while reducing its cost. Copyright © 2005 John Wiley & Sons, Ltd.     

Quantifying the benefit of configurability in circuit-switched WDMring networks with limited ports per node

In a reconfigurable network, lightpath connections can be dynamically changed to reflect changes in traffic conditions. This paper characterizes the gain in traffic capacity that a reconfigurable wavelength division multiplexed (WDM) network offers over a fixed topology network where lightpath connections are fixed and cannot be changed. We define the gain as the ratio of the maximum offered loads that the two systems can support for a given blocking probability. We develop a system model to approximate the blocking probability for both the fixed and reconfigurable systems. This model is different from previous models developed to analyze the blocking probability in WDM networks in that it accounts for a port limitation at the nodes. We validate our model via simulation and find that it agrees strongly with simulation results. We study high-bandwidth calls, where each call requires an entire wavelength and find that reconfigurability offers a substantial performance improvement, particularly when the number of available wavelengths significantly exceeds the number of ports per node. In this case, in a ring with N nodes, the gain approaches a factor of N/2 over a fixed topology unidirectional ring, and N/4 over a fixed topology bidirectional ring. Hence, a reconfigurable unidirectional (bidirectional) ring can support N/2(N/4) times the load of a fixed topology unidirectional (bidirectional) ring. We also show that for a given traffic load, a configurable system requires far fewer ports per node than a fixed topology system. These port savings can potentially result in a significant reduction in overall system costs     

Multiwavelength optical networks with limited wavelength conversion

This paper proposes optical wavelength division multiplexed (WDM) networks with limited wavelength conversion that can efficiently support lightpaths (connections) between nodes. Each lightpath follows a route in a network and must be assigned a channel on each link along the route. The load λ_max of a set of lightpaths is the maximum over all links of the number of lightpaths that use the link. At least λ_max wavelengths will be needed to assign channels to the lightpaths. If the network has full wavelength conversion capabilities, then λ_max wavelengths are sufficient to perform the channel assignment. Ring networks with fixed wavelength conversion capability within the nodes are proposed that can support all lightpath sets with load λ_max at most W-1, where W is the number of wavelengths in each link. Ring networks with a small additional amount of wavelength conversion capability within the nodes are also proposed that allow the support of any set of lightpaths with load λ_max at most W. A star network is also proposed with fixed wavelength conversion capability at its hub node that can support all lightpath sets with load λ_max at most W. These results are extended to tree networks and networks with arbitrary topologies. This provides evidence that significant improvements in traffic-carrying capacity can be obtained in WDM networks by providing very limited wavelength conversion capability within the network     

QoS aware traffic grooming and integrated routing on IP over WDM networks

In this article, we consider traffic grooming and integrated routing in IP over WDM networks. The challenges of this problem come from jointly considering traffic grooming, IP routing, and lightpath routing and wavelength assignment (RWA). Due to the high bandwidth of optical fiber, there exists a mismatch between the capacity needed by an IP flow and that provided by a single lightpath. Traffic grooming is therefore used to increase the network utilization by aggregating multiple IP flows in a single lightpath. However, traffic grooming incurs additional delays that might violate Quality-of-Service (QoS) requirements of IP users. In this work, the tradeoff between traffic grooming and IP QoS routing is well-formulated as a mixed integer and linear optimization problem, in which the revenue from successfully provisioning IP paths is to be maximized. Problem constraints include IP QoS, routing, optical RWA, and the WDM network capacity. We propose a novel Lagrangean relaxation (LGR) algorithm to perform constraint relaxation and derive a set of subproblems. The Lagrangean multipliers are used in the proposed algorithm to obtain a solution in consideration of grooming advantage and resource constraints simultaneously. Through numerical experiments and comparisons between the proposed algorithm and a two-phase approach, LGR outperforms the two-phase approach under all experimental cases. In particular, the improvement ratio becomes even more significant when the ratio of IP flow to the wavelength capacity is smaller.     

Rerouting technique with dynamic traffic in WDM optical networks

In this paper, we have proposed an efficient wavelength rerouting algorithm for dynamic provisioning of lightpath. In wavelength division multiplexed (WDM) networks rerouting of lightpath can be used to improve throughput and to reduce blocking probability. We have proposed a shortest path wavelength rerouting (SPWRR) algorithm for dynamic traffic in WDM optical networks. The results have shown that SPWRR algorithm can improve blocking performance of the network. In this paper, low complexity algorithm has been developed which is used for the calculation of blocking probability of network. The proposed algorithm has also been applied on the realistic network such as NSFnet for calculation and optimization of blocking probability of the network.     

Physical layer performance benchmarking of two metropolitan area network configurations

This paper investigates the problem of dynamic survivable lightpath provisioning against single-node/link failures in optical mesh networks employing wavelength-division multiplexing (WDM).We unify various forms of segment protection into generalized segment protection (GSP). In GSP, the working path of a lightpath is divided into multiple overlapping working segments, each of which is protected by a node-/link-disjoint backup segment. We design an efficient heuristic which, upon the arrival of a lightpath request, dynamically divides a judiciously selected working path into multiple overlapping working segments and computes a backup segment for each working segment while accommodating backup sharing. Compared to the widely considered shared-path protection scheme, GSP achieves much lower blocking probability and shorter protection-switching time for a small sacrifice in control and management overhead.On the basis of generalized segment protection, we present a new approach to provisioning lightpath requests according to their differentiated quality-of-protection (QoP) requirements. We focus on one of the most important QoP parameters—namely, protection-switching time—since lightpath requests may have differentiated protection-switching-time requirements. For example, lightpaths carrying voice traffic may require 50 ms protection-switching time while lightpaths carrying data traffic may have a wide range of protection-switching-time requirements. Numerical results show that our approach achieves significant performance gain which leads to a remarkable reduction in blocking probability.While our focus is on the optical WDM network, the basic ideas of our approaches can be applied to multi-protocol label switching (MPLS) networks with appropriate adjustments, e.g., differentiated bandwidth granularities.     

Some principles for designing a wide-area WDM optical network

We explore design principles for next-generation optical wide-area networks, employing wavelength-division multiplexing (WDM) and targeted to nationwide coverage. This optical network exploits wavelength multiplexers and optical switches in routing nodes, so that an arbitrary virtual topology may be embedded on a given physical fiber network. The virtual topology, which is used as a packet-switched network and which consists of a set of all-optical “lightpaths”, is set up to exploit the relative strengths of both optics and electronics-viz. packets of information are carried by the virtual topology “as far as possible” in the optical domain, but packet forwarding from lightpath to lightpath is performed via electronic switching, whenever required. We formulate the virtual topology design problem as an optimization problem with one of two possible objective functions: (1) for a given traffic matrix, minimize the network-wide average packet delay (corresponding to a solution for present traffic demands), or (2) maximize the scale factor by which the traffic matrix can be scaled up (to provide the maximum capacity upgrade for future traffic demands). Since simpler versions of this problem have been shown to be NP-hard, we resort to heuristic approaches. Specifically, we employ an iterative approach which combines “simulated annealing” (to search for a good virtual topology) and “flow deviation” (to optimally route the traffic-and possibly bifurcate its components-on the virtual topology). We do not consider the number of available wavelengths to be a constraint, i.e., we ignore the routing of lightpaths and wavelength assignment for these lightpaths. We illustrate our approaches by employing experimental traffic statistics collected from NSFNET     

Dynamic light trail routing in WDM optical networks

Fiber optics have replaced copper as the primary transmission medium. Wavelength Division Multiplexing (WDM) networks effectively increase single-link bandwidth from 10 Mbps to over 160 Gbps, and have been considered as a promising candidate for the next-generation backbone network. All optical circuits each on a separate wavelength called lightpaths represent the first major method for optical communication. The granularity provided between a source and destination node is that of a complete wavelength. Once a lightpath is set up, the entire wavelength is used exclusively by the connection’s source and destination node-pair. No sub-wavelength sharing between nodes along the lightpath is allowed. However, it is often observed that the bandwidth requirement in today’s network is often dynamically varying and does not justify the need for allocating an entire wavelength. Therefore, the wavelength capacity may be underutilized. A new technology termed light trail was proposed to avoid the inability of intermediate nodes to use a connection wavelength, and the constant reconfiguration of switches. In this article, we study dynamic light trail routing in a WDM optical network. We present an efficient algorithm for establishing a light trail routing for a new connection request, while using minimum network resources. We also study survivable network routing using the proposed light trail technology. We present an efficient heuristic for computing a pair of working and protection light trails for a dynamic incoming connection request. Simulation results are presented which demonstrate the advantages of our routing schemes.     

Survivable traffic grooming with non‐service‐interruptive wavelength retuning in a WDM mesh network

This paper proposes a new survivable traffic grooming wavelength retuning (STGWR) scheme in an all‐optical wavelength division multiplexing (WDM) network. In a dynamic WDM network, a connection may require a bandwidth less than a wavelength capacity. In addition, a connection should be protected against any network failures. Survivable traffic grooming (STG) can protect connections at subwavelength granularities. Wavelength retuning is a promising approach in an all‐optical WDM network, where a signal must remain on the same wavelength from its source to the destination, to alleviate the wavelength continuity constraint and reduce the connection blocking probability. Although both STG and wavelength retuning have attracted extensive research attentions nowadays, no effort has been made to combine these two promising approaches in one network. In this paper, we propose a wavelength retuning scheme with no service interruption in an all‐optical network with STG capability. The scheme allocates two routes, one for the active path and other for the backup path, in a shared mesh restoration manner to each incoming connection request and conducts wavelength retuning only on the backup path. Both wavelength retuning and mesh protection are done at the connection level instead of at the lightpath level. The simulation results of the proposed schemes are also presented. Copyright © 2008 John Wiley & Sons, Ltd.     

A new approach to dimensioning optical networks

A network dimensioning method allocates appropriate capacities to the links based on the network topology and traffic requirements. We introduce the concept of absorption probability instead of blocking probability which is a more appropriate measure to express the grade of service of an optical network, in many cases. Absorption probability can be obtained from transient analysis of a Markov chain. Computation of exact absorption probabilities requires large computing resources and is thus feasible only for small networks. We present a method to approximate the absorption probability of a wavelength-routed network with arbitrary topology and traffic patterns assuming the nodes have full wavelength conversion capability. We show that the approximation method performs well especially in the desired range of absorption probabilities and it is computationally efficient