A novel robust routing algorithm for multi-granularity connection requests in wavelength division multiplexing mesh networks

In this paper, we propose a novel robust routing algorithm based on Valiant load-balancing under the model of polyhedral uncertainty (i.e., hose uncertainty model) for WDM (wavelength division multiplexing) mesh networks. Valiant load-balanced robust routing algorithm constructs the stable virtual topology on which any traffic patterns under the hose uncertainty model can be efficiently routed. Considering there are multi-granularity connection requests in WDM mesh networks, we propose the method called hose-model separation to solve the problem for the proposed algorithm. Our goal is to minimize total network cost when constructing the stable virtual topology that assures robust routing for the hose model in WDM mesh networks. A mathematical formulation (integer linear programming, ILP) about Valiant load-balanced robust routing algorithm is presented. Two fast heuristic approaches are also proposed and evaluated. We compare the network throughput of the virtual topology constructed by the proposed algorithm with that of the traditional traffic grooming algorithm under the same total network cost by computer simulation.     

Effects of wavelength routing and selection algorithms onwavelength conversion gain in WDM optical networks

Wavelength-division multiplexing (WDM) technology is emerging as the transmission and switching mechanism for future optical mesh networks. In these networks it is desired that a wavelength can be routed without electrical conversions. Two technologies are possible for this purpose: wavelength selective cross-connects (WSXC) and wavelength interchanging cross-connects (WIXC), which involve wavelength conversion. It is believed that wavelength converters may improve the blocking performance, but there is a mix of results in the literature on the amount of this performance enhancement. We use two metrics to quantify the wavelength conversion gain: the reduction in blocking probability and the increase in maximum utilization, compared to a network without converters. We study the effects of wavelength routing and selection algorithms on these measures for mesh networks. We use the overflow model to analyze the blocking probability for wavelength-selective (WS) mesh networks using the first-fit wavelength assignment algorithm. We propose a dynamic routing and wavelength selection algorithm, the least-loaded routing (LLR) algorithm, which jointly selects the least-loaded route-wavelength pair. In networks both with and without wavelength converters the LLR algorithm achieves much better blocking performance compared to the fixed shortest path routing algorithm. The LLR produces larger wavelength conversion gains; however, these large gains are not realized in sufficiently wide utilization regions and are diminished with the increased number of fibers     

Routing Algorithms in WDM Networks under Mixed Static and Dynamic Lambda-Traffic

Dynamic traffic is becoming important in WDM networks. In the transition towards full dynamic traffic, WDM networks optimized for a specific set of static connections will most likely also be used to support on-demand lightpath provisioning. Our paper investigates the issue of routing of dynamic connections in WDM networks which are also loaded with high-priority protected static connections. By discrete-event simulation we compare various routing strategies in terms of blocking probability and we propose a new heuristic algorithm based on an occupancy cost function which takes several possible causes of blocking into account. The behavior of this algorithm is tested in well-known case-study mesh networks, with and without wavelength conversion. Moreover, Poissonian and non-Poissonian dynamic traffics are considered.     

Dynamic lightpath provisioning in optical WDM mesh networks with asymmetric nodes

The wavelength selective switch-based reconfigurable optical add/drop multiplexers is a promising switching equipment for future reconfigurable wavelength-division multiplexing (WDM) mesh networks. However, its asymmetric switching property complicates the optimal routing and wavelength assignment problem. In an asymmetric switching scenario, using the classic Dijkstra’s algorithm can lead to invalid paths traversing unconnected ports of an asymmetric node. To solve this problem, we propose both link-state (LS) and distance vector (DV) schemes for dynamic lightpath provisioning in optical WDM mesh networks with asymmetric nodes. The proposed LS schemes include the asymmetric switching-aware (ASA) Dijkstra’s algorithm, the $K$ -shortest path-based algorithm, and the entire path searching (EPS) algorithm. Simulation results show that the ASA-Dijkstra’s algorithm will bring notable improvement of the blocking performance with low computational complexity, while the EPS algorithm has much higher complexity and is not suitable to be employed in large-scale networks. On the other hand, our proposed DV solution, i.e., the information diffusion-based routing (IDBR), can achieve the lowest blocking probability with the lowest computational complexity. Moreover, IDBR does not require the distribution of local asymmetric switching information like the LS schemes, thus having a high level of topology confidentiality.     

Traffic grooming in WDM optical network with grooming resources at Max Connectivity nodes

In this paper, we propose Max Connectivity grooming in WDM mesh networks under static lightpath connection requests. The grooming and wavelength conversion resources are placed at the nodes having maximum connections. We propose a heuristic genetic algorithm (GA) model to solve grooming, routing and wavelength assignment. The GA algorithm has been used to optimize the cost of grooming and wavelength conversion resources. The blocking probability has been investigated under different lightpath connections. The performance of Max Connectivity grooming has been compared with other grooming policies. Our results indicate the improvement of resource utilization with minimum blocking probability.     

Preferred Link Based Distributed Adaptive Routing in Wavelength Routed Optical Network

As the WDM technology matures and the demand for bandwidth increases, dynamic provisioning of lightpaths at the WDM layer becomes an important and challenging problem. In this paper, we consider the problem of dynamic routing and wavelength assignment in wavelength-routed optical networks. The conventional approach to this problem is to select a route from a set of candidate routes, which has a common wavelength available on all the links of the route. In this paper, we propose a distributed algorithm which selects a route based on the state of the network (called preferred link approach). In this approach, a route is selected link by link based on a preference value given to each of the links. We propose three different heuristic functions for calculating the preference of the links, depending on the cost and congestion on the links. We evaluate our routing algorithm in terms of call acceptance ratio, cost of the path, hop length, and call setup time. Our experimental results suggest that our algorithm not only out performs the existing methods with respect to average call acceptance ratio, but, also improves the fairness among different hop connections, which is an important result in the case of WDM optical networks.     

Multicast protection scheme based on Hamiltonian cycle in fault-tolerant optical mesh networks

The increase of multimedia service requirements results in the growing popularity of the multicast in Wavelength-Division Multiplexing (WDM) optical mesh networks. Multicast fault tolerance in WDM optical mesh networks is an important issue because failures caused by the traffic carried in WDM optical mesh networks may lead to huge data loss. Previous works have proposed multicast protection algorithms to address the single-fiber link failure dominant in current optical mesh networks. However, these existing algorithms are all mainly based on path protection or segment protection, which may lead to long restoration times and complicated protection switching procedures. This paper therefore proposes a new heuristic algorithm, called Enhanced Multicast Hamiltonian Cycle Protection (EMHCP), in which all working light-trees of multicast demands can be protected by a Hamiltonian cycle in the network. For each multicast demand, EMHCP computes a least-cost light-tree based on the presented link-cost function that considers load balancing and proper straddling link selection so that backup wavelengths on the Hamiltonian cycle can be reduced. Simulation results show that EMHCP can obtain significant performance improvement compared with the conventional algorithm.     

Wavelength Conversion Placement in WDM Mesh Optical Networks*

Wavelength conversion helps improve the performance of wavelength division multiplexed (WDM) optical networks that employ wavelength routing. In this paper, we address the problem of optimally placing a limited number of wavelength converters in mesh topologies. Two objective functions, namely, minimizing the average blocking probability and minimizing the maximum blocking probability over all routes, are considered. In the first part of the paper, we extend an earlier analytical model to compute the blocking probability on an arbitrary route in a mesh topology, given the traffic and locations of converters. We then propose heuristic algorithms to place wavelength converters, and evaluate the performance of the proposed heuristics using the analytical model. Results suggest that simple heuristics are sufficient to give near-optimal performance.     

A Novel Shared Segment Protection Algorithm for Multicast Sessions in Mesh WDM Networks

This paper investigates the problem of protecting multicast sessions in mesh wavelength‐division multiplexing (WDM) networks against single link failures, for example, a fiber cut in optical networks. First, we study the two characteristics of multicast sessions in mesh WDM networks with sparse light splitter configuration. Traditionally, a multicast tree does not contain any circles, and the first characteristic is that a multicast tree has better performance if it contains some circles. Note that a multicast tree has several branches. If a path is added between the leave nodes on different branches, the segment between them on the multicast tree is protected. Based the two characteristics, the survivable multicast sessions routing problem is formulated into an Integer Linear Programming (ILP). Then, a heuristic algorithm, named the adaptive shared segment protection (ASSP) algorithm, is proposed for multicast sessions. The ASSP algorithm need not previously identify the segments for a multicast tree. The segments are determined during the algorithm process. Comparisons are made between the ASSP and two other reported schemes, link disjoint trees (LDT) and shared disjoint paths (SDP), in terms of blocking probability and resource cost on CERNET and USNET topologies. Simulations show that the ASSP algorithm has better performance than other existing schemes.     

多光纤波分复用网的一种新的备用路由算法

基于经典的LLR算法,研究了波分复用光网络的路由问题,提出了一种用于多光纤网的新算法—LLHR,该算法综合考虑了链路负载和路由跳数两个因素。文章深入研究了网络光纤数、备用路由数和网络负载对算法性能的影响。计算机仿真结果表明,与LLR算法相比,该算法能有效降低网络的阻塞率,提高网络的性能。     

A computational model for estimating blocking probabilities of multifiber WDM optical networks

In this letter, we propose a computational model for calculating blocking probabilities of multifiber wavelength division multiplexing (WDM) optical networks. We first derive the blocking probability of a fiber based on a Markov chain, from which the blocking probability of a link is derived by means of conditional probabilities. The blocking probability of a lightpath can be computed by a recursive formula. Finally, the network-wide blocking probability can be expressed as the ratio of the total blocked load versus the total offered load. Simulation results for different fiber-wavelength configurations conform closely to the numerical results based on our proposed model, thus demonstrating the feasibility of our proposed model for estimating the blocking performance of multifiber WDM optical networks.     

An Ant-Based Approach for Dynamic RWA in Optical WDM Networks

In this paper, we propose a new ant-based algorithm for the dynamic routing and wavelength assignment (RWA) problem in optical WDM networks under the wavelength continuity constraint. Unlike conventional approaches, which usually require centralized global network information, our new RWA algorithm constructs the routing solution in a distributed manner by means of cooperative ants. To facilitate the ants’ foraging task, we adopt in our algorithm a probabilistic routing table structure for route selection. The new algorithm is highly adaptive in that it always keeps a suitable number of ants in the network to cooperatively explore the network states and continuously update the routing tables, so that the route for a connection request can be determined promptly by the current states of routing tables with only a small setup delay. Some new schemes for path scoring and path searching are also proposed to enhance the performance of our ant-based algorithm. Extensive simulation results upon three typical network topologies indicate that the proposed algorithm has a very good adaptability to traffic variations and it outperforms both the fixed routing algorithm and the promising fixed–alternate routing algorithm in terms of blocking probability. The ability to guarantee both a low blocking probability and a small setup delay makes the new ant-based routing algorithm very attractive for both the optical circuit switching networks and future optical burst switching networks     

Near optimal routing and capacity management for PWCE-based survivable WDM networks

Protected Working Capacity Envelope (PWCE) has been proposed to simplify resource management and traffic control for survivable WDM networks. In a PWCE-based network, part of the link capacity is reserved for accommodating working routes, and the remaining capacity is reserved for backup routes. The shortest path routing is applied in PWCE-based networks. An arrival call is accepted only when each link along the shortest path has a free working channel. Such a working path routing scheme greatly simplifies the call admission control process for dynamic traffic, and it is especially suitable for implementation in a distributed manner among network nodes. In this article, we investigate two protection strategies: Bundle Protection (BP) and Individual Protection (IDP). In BP, only one backup path can be used to protect a failure component, whereas multiple backup paths can be used in IDP. We formulate four mixed integer non-linear programming (MINLP) problems using BP and IDP strategies for single link and single node failure protection. Each model is designed to determine link metrics for shortest working path routing, working and backup channel assignments, and backup path planning. Our objective is to minimize call-blocking probability on the bottleneck link. Since these models are highly non-linear and non-convex, it is difficult to obtain exact global optimal solutions. We propose a Simulated Annealing-based Heuristic (SAH) algorithm to obtain near optimal solutions. This SAH adopts the concepts of simulated annealing as well as the bi-section technique to minimize call-blocking probabilities. To evaluate the performance, we made simulation comparisons between SAH and the unity link weight assignment scheme. The results indicate that SAH can greatly reduce call-blocking probabilities on benchmark and the randomly generated networks.     

Availability-Aware Provisioning Strategies for Differentiated Protection Services in Wavelength-Convertible WDM Mesh Networks

In an optical WDM mesh network, different protection schemes (such as dedicated or shared protection) can be used to improve the service availability against network failures. However, in order to satisfy a connections service-availability requirement in a cost-effective and resource-efficient manner, we need a systematic mechanism to select a proper protection scheme for each connection request while provisioning the connection. In this paper, we propose to use connection availability as a metric to provide differentiated protection services in a wavelength-convertible WDM mesh network. We develop a mathematical model to analyze the availabilities of connections with different protection modes (i.e., unprotected, dedicated protected, or shared protected). In the shared-protection case, we investigate how a connection's availability is affected by backup resource sharing. The sharing might cause backup resource contention between several connections when multiple simultaneous (or overlapping) failures occur in the network. Using a continuous-time Markov model, we derive the conditional probability for a connection to acquire backup resources in the presence of backup resource contention. Through this model, we show how the availability of a shared-protected connection can be quantitatively computed. Based on the analytical model, we develop provisioning strategies for a given set of connection demands in which an appropriate, possibly different, level of protection is provided to each connection according to its predefined availability requirement, e.g., 0.999, 0.997. We propose integer linear programming (ILP) and heuristic approaches to provision the connections cost effectively while satisfying the connections' availability requirements. The effectiveness of our provisioning approaches is demonstrated through numerical examples. The proposed provisioning strategies inherently facilitate the service differentiation in optical WDM mesh networks.     

支持不同可靠性要求的WDM网状网业务量疏导算法

WDM光网络中不同的业务流具有不同的可靠性要求，本文研究动态业务下如何解决此类业务量疏导问题，提出了一种在WDM网状网中支持多种可靠要求的业务量疏导算法(MRTG)。仿真结果表明该算法具有很好的性能。     

A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks

Optical wavelength-division multiplexed (WDM) networks often include optical cross-connects with multigranularity switching capability, such as switching on a single lambda, a waveband, or an entire fiber basis. In addition, it has been shown that routing and wavelength assignment (RWA) in an arbitrary mesh WDM network is an NP-complete problem. In this paper, we propose an efficient approximation approach, called Lagrangean relaxation with heuristics (LRH), aimed to resolve RWA in multigranularity WDM networks particularly with lambda and fiber switches. The task is first formulated as a combinatorial optimization problem in which the bottleneck link utilization is to be minimized. The LRH approach performs constraint relaxation and derives a lower-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LRH approach employs a new heuristic algorithm to arrive at a near-optimal upper-bound solution. With lower and upper bounds, we conduct a performance study on LRH with respect to accuracy and convergence speed under different parameter settings. We further draw comparisons between LRH and an existing practical approach via experiments over randomly generated and several well-known large sized networks. Numerical results demonstrate that LRH outperforms the existing approach in both accuracy and computational time complexity, particularly for larger sized networks.     

Availability of survivable Valiant load balancing (VLB) networks over optical networks

Valiant load balancing (VLB) network has been proposed as a capacity-efficient solution to handle highly dynamic traffic in future backbone networks. In this paper, we study the availability of VLB networks that are overlaid over an optical infrastructure. The main challenges in such a context arise from the unique routing and protection scheme that goes beyond the definition of conventional connection-level service availability as well as the logical link failure correlation that prohibits the use of traditional analytical methods. We propose a network-level availability model to compute the probability that a VLB network is congestion-free under all traffic patterns. Numerical results show that with a proper truncation level, our calculation on availability can be accelerated significantly by generating tight lower and upper bounds. Our main finding is that physical link sharing in a two-layer setting degrades the network availability drastically by several orders of magnitude due to the full mesh requirement for VLB networks, and may remove the capacity efficiency advantage of VLB networks.     

Differentiated reliability in optical networks: theoretical and practical results

This paper presents both theoretical and experimental studies carried on wavelength-division multiplexing (WDM) networks with arbitrary (mesh) topology that provide optical circuits with differentiated reliability (DiR). Reliability is obtained by means of a modified shared path protection (SPP) switching scheme-here referred to as SPP-DiR. As explained in the paper, SPP-DiR networks provide multiple degrees of circuit reliability that satisfy client-specific reliability requirements in a cost-effective way. The theoretical study first defines the problem of optimally designing SPP-DiR WDM networks. It then presents a time-efficient suboptimal algorithm that determines the routing and the reliability degree of each demand in the given traffic matrix by applying both the conventional SPP and the SPP-DiR scheme. When compared to dedicated path protection switching, results obtained for the pan-European network using the proposed algorithm indicate cost reductions of about 16% when SPP is applied, and up to 34% when SPP-DiR is applied. The experimental study describes the /spl Omega/ testbed-a WDM optical circuit-switched mesh network with an IP control plane-which is believed to be the first testbed ever built that makes use of the SPP-DiR scheme. Experimental results performed on the /spl Omega/ testbed report restoration times of the optical circuits-disrupted by a fiber fault-that are few tens of milliseconds.     

A novel domain-by-domain survivable mechanism in multi-domain wavelength-division-multiplexing optical networks

In multi-domain wavelength-division-multiplexing (WDM) optical networks, the inter-domain routing is a challenge since each single-domain cannot view the full network topology. At the same time, survivability is also an important issue in optical networks since the failures of fiber links or network nodes may lead to a lot of traffic being blocked. In this paper, we study the survivability in multi-domain WDM optical networks, and propose a new survivable mechanism called load balanced domain-by-domain routing (LBDDR). In LBDDR, in order to obtain the efficient inter-domain survivable routes, we present the domain-by-domain routing (DDR) method which can find the intra-domain sub-working path and sub-backup path in each single-domain to form the inter-domain working path and backup path for each demand. In order to reduce the blocking probability, we present the load balanced routing method which can encourage the traffic to be uniformly distributed on the links with more free wavelengths. Simulation results show that, compared with conventional mechanism, LBDDR can obtain better performances.     

MPLS over WDM光互联网中多优先级标记交换路径路由算法研究

该文针对分层图模型的局限,设计了结点光收发器数受限的MPLS over WDM光互联网的扩展分层图。提出并研究了MPLS over WDM光互联网中具有不同QoS约束的多种优先级标记交换路径的路由算法区分综合路由算法(Differentiating Integrated Routing Algorithm , DIRA)。该算法综合考虑了对标记交换路径QoS的满足和网络资源的优化利用。与目前实用的WDM光网络路由算法的性能仿真对比表明,DIRA在提高网络总的吞吐量,降低有时延约束标记交换路径的阻塞率方面,性能更优。