Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths

In the present paper, routing and wavelength assignment (RWA) in optical WDM networks is discussed. Previous techniques based on the combination of integer linear programming based lpsolver and graph coloring are complex and require extensive use of heuristics such as rounding heuristic which makes them slow and sometimes practically not reasonable. Another method employs the greedy approach in graph theory for obtaining available edge disjoint paths. Even though it is fast, it produces a solution for any connection request which is far from the optimal utilization of wavelengths. We propose a novel algorithm, which is based on the maximum flow to have the maximum quantity of edge disjoint paths. Here, we compare the offered method with previous edge disjoint paths algorithms applied to the RWA. Comprehensive computer simulation shows that the proposed method outperforms previous ones significantly in terms of running time. Furthermore, the new method shows compatible or better performance comparing to others in number of wavelengths used.The earlier version was published in ICCS 2004, Poland (Krakow). This research was supported by the Ministry of Information and Communication, Korea under the Information Technology Research Center support program supervised by the Institute of Information Technology Assessment, IITA-2005-(C1090-0501-0019).     

网树求解有向无环图中具有长度约束的最大不相交路径

对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为k的最大不相交路径。为了对该问题进行求解,提出了贪婪搜索算法(GP, greedy path),该算法先将一个有向无环图转化为一棵深度为k+1的网树,然后计算每个网树节点的树根叶子路径数,并以此计算图中每个顶点的总路径数,之后从网树的第k+1层节点出发,在当前节点的双亲节点中选择未被使用且总路径数最小的双亲,以此形成一条优化的不相交路径,最后迭代这一过程,直到不再有新的不相交路径为止。GP算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n2)。为了测试GP算法的近似性,又建立了一种能够生成人工数据的算法,该算法能够准确地控制有向无环图中最大不相交路径的数量。通过该算法生成了大量测试用数据,实验结果表明GP算法较其他对比性算法具有良好的近似性且实际求解时间较短,验证了该方法的有效性和可行性。     

A heuristic algorithm for lightpath scheduling in next-generation WDM optical networks

We study the routing and wavelength assignment (RWA) problem of scheduled lightpath demands (SLDs) in all-optical wavelength division multiplexing networks with no wavelength conversion capability. We consider the deterministic lightpath scheduling problem in which the whole set of lightpath demands is completely known in advance. The objective is to maximize the number of established lightpaths for a given number of wavelengths. Since this problem has been shown to be NP complete, various heuristic algorithms have been developed to solve it suboptimally. In this paper, we propose a novel heuristic RWA algorithm for SLDs based on the bee colony optimization (BCO) metaheuristic. BCO is a newborn swarm intelligence metaheuristic approach recently proposed to solve complex combinatorial optimization problems. We compare the efficiency of the proposed algorithm with three simple greedy algorithms for the same problem. Numerical results obtained by numerous simulations performed on the widely used realistic European Optical Network topology indicate that the proposed algorithm produces better-quality solutions compared to those obtained by greedy algorithms. In addition, we compare the results of the BCO–RWA–SLD algorithm with four other heuristic/metaheuristic algorithms proposed in literature to solve the RWA problem in the case of permanent (static) traffic demands.     

On the routing and wavelength assignment in multifiber WDM networks

This paper addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks with limited resources. Given a traffic matrix, the number of fibers per link, and the number of wavelengths a fiber can support, we seek to maximize the carried traffic of connections. We formulate the problem as an integer linear program (ILP), and show that the lightpaths selected by this formulation can indeed be established by properly configuring the optical switches. An upper bound on the carried traffic can be computed by solving the linear programming (LP)-relaxation of the ILP formulation. It is shown that this bound can be also computed exactly, and in polynomial-time, by solving a significantly simplified LP which considers only one wavelength. The bound can, thus, easily scale to an arbitrarily large number of wavelengths. Furthermore, we demonstrate that any instance of the RWA problem is also an instance of the more general maximum coverage problem. This allows us to take a greedy algorithm for maximum coverage and obtain an algorithm which provides solutions for the RWA problem that are guaranteed to be within a factor of (1-(1/e)) of the optimal solution. Each iteration of the greedy algorithm selects a set of lightpaths that realizes, using one wavelength, the maximum number of connection requests not previously realized. Computational results confirm the high efficiency of our proposed algorithm.     

Routing and wavelength assignment in optical networks

The problem of routing and wavelength assignment (RWA) is critically important for increasing the efficiency of wavelength-routed all-optical networks. Given the physical network structure and the required connections, the RWA problem is to select a suitable path and wavelength among the many possible choices for each connection so that no two paths sharing a link are assigned the same wavelength. In work to date, this problem has been formulated as a difficult integer programming problem that does not lend itself to efficient solution or insightful analysis. In this work, we propose several novel optimization problem formulations that offer the promise of radical improvements over the existing methods. We adopt a (quasi-)static view of the problem and propose new integer-linear programming formulations, which can be addressed with highly efficient linear (not integer) programming methods and yield optimal or near-optimal RWA policies. The fact that this is possible is surprising, and is the starting point for new and greatly improved methods for RWA. Aside from its intrinsic value, the quasi-static solution method can form the basis for suboptimal solution methods for the stochastic/dynamic settings.     

Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information

The paper presents new algorithms for dynamic routing of restorable bandwidth-guaranteed paths. We assume that connections are requested one-by-one and there is no prior knowledge of future arrivals. In order to guarantee restorability an alternate link (node) disjoint backup (restoration) path has to be determined, as well as an active path, when the connection is initiated. This joint on-line routing problem is particularly important in optical networks and in MPLS networks for dynamic provisioning of bandwidth-guaranteed or wavelength paths. A simple solution is to find two disjoint paths, but this results in excessive resource usage. Backup path bandwidth usage can be reduced by judicious sharing of backup paths amongst certain active paths while still maintaining restorability. The best sharing performance is achieved if the routing of every path in progress in the network is known to the routing algorithm at the time of a new path setup. We give a new integer programming formulation for this problem. Complete path routing knowledge is a reasonable assumption for a centralized routing algorithm, but is not often desirable, particularly when distributed routing is preferred. We show that a suitably developed algorithm which uses only aggregated information, and not per-path information, is able to perform almost as well as one using complete information. Disseminating this aggregate information is feasible using proposed traffic engineering extensions to routing protocols. We formulate the dynamic restorable bandwidth routing problem in this aggregate information scenario and develop efficient routing algorithms. The performance of our algorithm is close to the complete information bound.     

Topological optimization for spare-sharing-based wavelength-routed all-optical networks

In this paper, we propose a two-level fault tolerance strategy for wavelength-routed all-optical networks. The first-level strategy is applied to handle the large-scale disaster induced failures while the second-level strategy protects the network against regular single-link failures. The first-level fault tolerance is achieved by solving a topological optimization problem to re-regulate the traffic away from the disaster-affected area with minimum resource cost. Shared lightpath protection is applied in the second-level fault tolerance design to reduce resource allocation. First, by comparing with a simple greedy approach that we develop, we show that the traditional Routing and Wavelength Assignment (RWA) method, in which the routing and wavelength assignment are considered in a separate fashion, cannot lead to satisfying performance. Next, in order to obtain better performance, based on drawback analysis of the greedy approach, we propose a two-phase heuristic algorithm, in which the first phase is designed to generate an initial feasible solution and the second phase iteratively perfects the initial solution until no improvement can be made. For the design of the first phase, two variations are proposed featuring different types of initial solution generation. The numerical results show that, combined with perfection phase, both design variations can lead to considerable performance improvement over the greedy solutions. Finally, we propose a Performance Indicator (PI) that provides insight into the reason for performance difference among algorithms.     

Multi‐constrained Shortest Disjoint Paths for Reliable QoS Routing

Finding link‐disjoint or node‐disjoint paths under multiple constraints is an effective way to improve network QoS ability, reliability, and so on. However, existing algorithms for such scheme cannot ensure a feasible solution for arbitrary networks. We propose design principles of an algorithm to fill this gap, which we arrive at by analyzing the properties of optimal solutions for the multi‐constrained link‐disjoint path pair problem. Based on this, we propose the link‐disjoint optimal multi‐constrained paths algorithm (LIDOMPA), to find the shortest link‐disjoint path pair for any network. Three concepts, namely, the candidate optimal solution, the contractive constraint vector, and structure‐aware non‐dominance, are introduced to reduce its search space without loss of exactness. Extensive simulations show that LIDOMPA outperforms existing schemes and achieves acceptable complexity. Moreover, LIDOMPA is extended to the node‐disjoint optimal multi‐constrained paths algorithm (NODOMPA) for the multi‐constrained node‐disjoint path pair problem.     

A new approach for routing and wavelength assignment for permanent and reliable wavelength paths in wide all-optical WDM networks

This article proposes a new approach for routing and wavelength assignment (RWA) for permanent and reliable wavelength paths (WP) in wide all-optical WDM networks with wavelength continuity constraint. Given a number of available wavelengths on each optical fiber, for each simple link failure of the network, we seek to maximize the number of satisfied requests for connections. This is known as RWAP problem. In our algorithm, called RWA with Minimum Loaded Link for Permanent and Reliable wavelength paths (MLL-PR), routing is based on the search for the optimal path while trying to minimize the maximum load on the links of the network in order to minimize the maximum link capacity and then minimize the number of dropped lightpaths after any link failure. The wavelength assignment is based on a graph coloring method using tabu-search. A series of experiments using two well-known networks (ARPANET and NSFNET) have been carried out in order to evaluate the performance of our approach, in terms of the number of blocked demands, for different failure scenarios. Generally, our results are better than those provided by the current solving approaches taken as reference.

All-optical multipoint-to-point routing in WDM mesh networks

In this article, the routing and wavelength assignment (RWA) problem for supporting multipoint-to-point communications in all-optical WDM mesh networks is investigated. Two efficient algorithms, namely reverse shortest path tree routing (RSPT) and k-bounded edge disjoint path routing (EDPR), are proposed. We proved that the problem of minimizing the total cost while establishing a multipoint-to-point session can be solved in polynomial time of O(|V|log|V|?+?|V|?+?|E|) by the RSPT algorithm, where |V| and |E| denote the number of nodes and the number of edges in the network, respectively. Nevertheless, the solution provided by the EDPR algorithm produces a significant reduction in the maximum number of wavelengths required per link (i.e., the link stress) for a multipoint-to-point session compared to RSPT algorithm. EDPR algorithm can also approximate to the optimal total cost with a ratio of k. Simulations are done to assess these two algorithms. Numerical results demonstrate their efficiencies in supporting multipoint-to-point communications in all-optical WDM networks.     

The most congested cutset: deriving a tight lower bound for the chromatic number in the RWA problem

Routing and wavelength assignment (RWA) is an important issue in the design of routing protocols in an all-optical network. A solution for the RWA problem should determine the least possible number of wavelengths, also known as the chromatic number. In this letter, we introduce the concept of cutset congestion, and show that the congestion of the most congested cutset of a graph representing the network is a tight lower bound for the chromatic number in the RWA problem. In contrast to other existing techniques, our method can be applied to any network and any traffic pattern.     

Binary quadratic programming formulation for routing and wavelength assignment problem in all-optical WDM networks

Routing and wavelength assignment (RWA) is the most concern in wavelength routed optical networks. This paper proposes a novel binary quadratic programming (BQP) formulation for the static RWA problem in order to balance traffic load among a network links more fairly. Subsequently, a greedy heuristic algorithm namely variable-weight routing and wavelength assignment (VW-RWA) is proposed to solve the developed BQP problem. In this method, the weight of a link is proportional to the link congestion. Performance evaluation results for different practical network topologies show that our proposed algorithm can decrease the number of required wavelengths in the network, blocking rate and variance of used wavelengths in each link. Besides, it is shown that the number of required wavelengths to establish call requests for a given network topology can be reduced at lower cost compared to other heuristics.     

Path diversified multi-QoS optimization in multi-channel wireless mesh networks

Wireless mesh networks (WMNs) have become a promising solution for quick and low-cost spreading of Internet accesses and other network services. Given the mesh topology, multiple paths are often available between node pairs, which thus naturally endorse path-diversified transmission. Unfortunately, like in wired networks, discovering completely disjoint paths in a WMN remains an intractable problem. It indeed becomes more challenging given the interferences across wireless channels in a WMN, not to mention that applications may demand heterogeneous QoS optimizations across different paths. The availability of multiple channels in advanced WMNs however sheds new lights into this problem. In this paper, we show that, as long as the best channels with different QoS metrics are not overlapped between neighboring node pairs, complete disjoint paths with heterogeneous QoS targets are available in a multi-channel WMN. We present efficient solutions to discover such paths, particularly for bandwidth- and delay-optimization. We also develop novel algorithms for accurately estimating path bandwidth and delay in the multi-channel environment. These lead to the design of a practical protocol that extends the classical Ad hoc On-demand Multi-path Distance Vector (AOMDV). Through extensive simulations, we show that our protocol yields significant improvement over state-of-the-art multi-path protocols in terms of both end-to-end throughput and delay.     

Routing and wavelength assignment in all optical networks using differential evolution optimization

The routing and wavelength assignment (RWA) problem, known to be an NP-complete problem, seeks to optimally establish routes and adequate wavelengths for the requested connections according to an objective function. This paper presents the use of a novel approach based on a differential evolution (DE) algorithm to the RWA problem in wavelength-routed dense division multiplexing (DWDM) optical networks. The proposed DE-RWA algorithm is modeled to optimize not only the network wavelength requirement ( $ NWR $ , which is the minimum number of wavelengths needed to fulfill traffic demand) but also the average path length ( $ APL $ ). We present the impact of the control parameters of the DE algorithm on the improvement of system’s performance. Additionally, we present two strategies to improve the efficiency of the algorithm, knowing as the disjoint cut-set paths (DCS-P) algorithm and the use of a random mutation ( $ random -M$ ) parameter for DE. The proposed approach is evaluated for test bench optical networks with up to 40 nodes. Experiments show that the DE-RWA algorithm obtains results that equal the $ NWR $ lower bound for networks with and without wavelength conversion capability, whereas reduce the $ APL $ . The performance of the DE-based approach is compared against results obtained with the particle swarm optimization (PSO) and genetic algorithm (GA) models, showing that the DE-RWA outperform those algorithms. The presented DE-RWA model is simple to implement and could also be extended by adding other features such as impairment-aware, energy efficient, survivability among others in optical networks.     

Routing and wavelength assignment strategies in optical networks

We consider the routing and wavelength assignment (RWA) problem on wavelength division multiplexing (WDM) networks without wavelength conversion. When the physical network and required connections are given, RWA is the problem to select a suitable path and wavelength among the many possible choices for each connection such that no two paths using the same wavelength pass through the same link. In WDM optical networks, there is need to maximize the number of connections established and to minimize the blocking probability using limited resources. This paper presents efficient RWA strategies, which minimizes the blocking probability. Simulation results show that the performance of the proposed strategies is much better than the existing strategy.     

An algorithm for optimal assignment of a wavelength in a tree topology and its application in WDM networks

In this paper, we present a polynomial time algorithm that gives an optimal solution to the routing and wavelength assignment (RWA) problem in a tree topology. One of the major design issues in wavelength-division multiplexed networks is the assignment of the limited number of wavelengths among network stations so that greater capacity can be achieved. The problem of RWA is known to be NP-hard problem. Many researchers have tackled the problem of RWA with a number of efficient heuristic algorithms. This paper presents an algorithm that optimally assigns a single wavelength to maximize one-hop traffic in a tree topology. The algorithm uses dynamic programming and is shown to be optimal with a time complexity of O(N/sup 4/). We also propose a heuristic scheme to use our optimal algorithm for wavelength assignment in a general graph. The heuristic works on the tree subgraphs of a given graph and the remaining spare wavelengths can be assigned with an existing RWA policy.     

A memory-effective fast algorithm for computing the reliability of complex systems/networks

Boolean reliability analysis of complex technical systems, as well as of technical net-systems (such as telecommunication systems), leads to the problem of computing the terminal pair reliability R^s,t of a netgraph. Among the fastest methods of computing R^s,t is the path method. In enumerates all minimal s−t paths of the net and then makes the paths mutually disjoint. Unfortunately, all paths and all disjoint terms must be available (stored) at the same time. Therefore, the computer memory effort for that method increases exponentially. In contrast, the reliability branching algorithm (RBA) that builds up a branching tree with disjoint tree-nodes (corresponding to the terms of a symbolic reliability expression) is also effective and needs only a low, quadratically increasing memory effort.The present paper gives a new method for symbolic reliability analysis. It is a fusion of the RBA with the path method. We search for one s−t path and compute its reliability. Then we formulate conditions that ensure disjointness for all paths we search on that condition and so on. A condition always reduces the network. The new method combines the advantages of the path method (fast) and the RBA (low memory effort). The algorithm is simple for computation by hand and effective for the use of computers.     

Heuristic and Hybrid Methods for Solving Optimal Multiple Multicast Problem on WDM Ring Network

The Optimal Multiple Multicast Problem (OMMP) on wavelength division multiplexing (WDM) ring networks without wavelength conversion is considered in this paper. When the physical network and the set of multicast requests are given, OMMP is the problem that selects a suitable path (or paths) and wavelength (or wavelengths) among the many possible choices for each multicast request such that not any pair of paths using the same wavelength pass through the same link. In this paper, a formulation of OMMP is given; this problem is NP-hard since the famous RWA problem which has been proved NP-hard is a special case of OMMP. In this paper, the OMMP is divided into two subproblems: path routing and wavelength assignment subproblems. For each subproblem, two heuristic algorithms are proposed to solve it. Moreover, a hybrid method which combines heuristic and simulated annealing algorithm is proposed to find the near optimal solution. Experimental results indicate that these algorithms are efficient.     

A Minimizing Algorithm for Sum of Disjoint Products

This paper describes a minimizing version of the Abraham sum-of-disjoint products (sdp) algorithm, called the Abraham-Locks-Revised (ALR) method, as an improved technique for obtaining a disjoint system-reliability formula. The principal changes are: 1) Boolean minimization and rapid inversion are substituted for time-consuming search operations of the inner loop. 2) Paths and terms are ordered both according to size and alphanumerically. ALR reduces the computing cost and data processing effort required to generate the disjoint system formula compared to the seminal 1979 Abraham paper, and obtains a shorter formula than any other known sdp method. Very substantial savings are achieved in processing large paths of complex networks.     

Application of complex ray tracing to scattering problems

Representations and geometric constructions associated with complex points, complex lines, and complex rays are introduced. They are applied to the problem of scattering of an evanescent plane wave by a conducting circular cylinder. This problem has an exact solution, which provides a check of the validity of complex ray tracing and suggests more general applications. An important role is played by the transformation that maps the point of reflection, on the complex extension of the scattering surface, onto the trace in real space of the complex reflected ray. For the particular problem considered, the phase and amplitude of the reflected field are computed and the "phase paths" and "phase fronts" are constructed. The reflected field and phase paths obtained in this manner are not to be taken in their entirety because some reflection points are not "illuminated" by the incident wave, and because the reflector may be only part of the cylinder. Tentative selection and truncation rules are used which yield good agreement with the exact solution over some regions. The disagreement, where it occurs, comes-as it does for real rays-from neglecting the diffracted field such as the creeping waves around smooth surfaces and, in the case of truncation, the edge waves from the discontinuity. Some consideration is given to scattering by an arbitrary smooth conductor. Some problems peculiar to the use of complex rays are stated.