Efficient routing and wavelength assignment for reconfigurable WDM ring networks with wavelength converters

We consider the problem of wavelength assignment in reconfigurable WDM networks with wavelength converters. We show that for N-node P-port bidirectional rings, a minimum number of /spl lceil/PN/4/spl rceil/ wavelengths are required to support all possible connected virtual topologies in a rearrangeably nonblocking fashion, and provide an algorithm that meets this bound using no more than /spl lceil/PN/2/spl rceil/ wavelength converters. This improves over the tight lower bound of /spl lceil/PN/3/spl rceil/ wavelengths required for such rings given in if no wavelength conversion is available. We extend this to the general P-port case where each node i may have a different number of ports P/sub i/, and show that no more than /spl lceil//spl sigma//sub i/P/sub i//4/spl rceil/+1 wavelengths are required. We then provide a second algorithm that uses more wavelengths yet requires significantly fewer converters. We also develop a method that allows the wavelength converters to be arbitrarily located at any node in the ring. This gives significant flexibility in the design of the networks. For example, all /spl lceil/PN/2/spl rceil/ converters can be collocated at a single hub node, or distributed evenly among the N nodes with min{/spl lceil/P/2/spl rceil/+1,P} converters at each node.     

IP over WDM网中的策略路由算法

业务量工程允许管理者通过赋予业务主干不同的业务量工程属性来体现一定的管理策略,在为业务主干建立标记交换路径(LSP)时也应该考虑这些策略的影响,该文讨论了业务主干具有不同优先权属性时的 LSP建立问题,针对中断 LSP个数最少和中断业务量最小两种指标,分别提出不同的解决策略:最小连接数中断法(MCNIM)和最小连接带宽中断法(MCBIM),并在不同负载的动态业务下对所提算法进行了仿真研究,给出了仿真结果。     

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.     

Distributed dynamic grooming routing and wavelength assignment in WDM optical mesh networks

The bandwidth of a wavelength channel in WDM optical networks is very high compared to the user’s requirements for various applications. Therefore, there is a scope for better utilization of channel bandwidth by traffic grooming, in which several user’s channels are multiplexed for transmission over a single channel. Several research works have been reported on traffic grooming routing and wavelength assignment (GRWA) for static and dynamic traffic pattern under centralized environment. Distributed dynamic grooming routing and wavelength assignment (DDGRWA) is a new and quite unexplored area in WDM optical mesh networks. This article introduces the concept of distributed traffic grooming in WDM mesh networks which also includes virtual topology construction, reconfiguration, routing and wavelength assignment in the distributed environment assuming incoming traffic to be dynamic in nature. We have also presented simulation results of our algorithm on dynamically generated traffic under various network topologies.     

Dynamic routing and wavelength assignment in multi-granularity WDM networks

For the purpose of reducing the complexity and cost of optical large-scale cross-connect, wavelengths are grouped into wavebands or fiber to be switched as a single entity, which is called multi- granularity switching. However, it introduces more complexity into the routing and wavelength assignment problem. In this paper, we propose a novel graph model for describing the states of the multi-granularity switching WDM networks. Based on the model, the dynamic routing and wavelength assignment problems for multi-granularity traffic can be solved jointly, and different on-line wavelength grooming policies can be achieved simultaneously. By simulation, we compared the performance of our algorithms under different policy and different percent of fibers for fiber switching. The result proved that our algorithms yield better performance than those deal with the routing and wavelength assignment separately. This work was supported in part by NSFC Project No. 90104003, 60272023, 60372025 and National 863 project No. 2005AA122310.     

WDM网络中支持QoS的路由与波长分配算法

针对波分复用(wDM)网络中的路由与波长分配问题。提出了一种支持服务质量(QoS)的约束搜索算法。基于多目标规划模型,这种搜索算法可为网络各节点创建路由表,根据路由表信息求出非支配路径集合,从而一次性完成寻找路由和分配波长两项任务。仿真实例证明了该算法的有效性。     

Adaptive routing and wavelength assignment algorithm for WDM networks with uniform and non-uniform traffic model

This letter studies routing and wavelength assignment (RWA) problem in wavelength-routed wavelength-division multiplexing networks with both uniform and nonuniform traffic model. Our research shows that the potential traffic load information is a crucial factor for routing algorithm design. Based on our analysis, an adaptive RWA algorithm is proposed. The simulation shows that the proposed algorithm performs much better than other adaptive RWA algorithms.     

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.     

New algorithms for multicast routing and wavelength assignment in multi-hop optical WDM networks

We study the problem of multicast routing and wavelength assignment (MC-RWA) in multi-hop optical WDM networks with respect to several target functions. Specially, we first study the MC-RWA problem under the target of minimize maximum hops, an efficient MC-RWA algorithm was proposed for that case. But for the objective of minimizing the total number of wavelength conversions, problem turns out to be NP-hard, we proposed a new approximation MC-RWA algorithm based on group Steiner tree. At last, combining the two objectives, a bi-factor approximation algorithm was introduced to minimize the both targets in the system simultaneously.     

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.     

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.     

Multicast routing and wavelength assignment with delay constraint in WDM networks with sparse wavelength conversions

With the developments in multimedia and other real-time group applications, the question of how to establish multicast trees satisfying Quality-of-Service (QoS) requirements is becoming a very important problem. In this paper, multicast routing and wavelength assignment with delay constraint (MCRWA-DC) in wavelength division multiplexing (WDM) networks with sparse wavelength conversions is studied. We propose a colored multigraph model for the temporarily available wavelengths. Based on this colored multigraph model, two heuristic algorithms are proposed to solve the MCRWA-DC problem. The proposed algorithms have the following advantages:(1) finish multicast routing and wavelength assignment in one step; (2) the total cost of the multicast tree is low; (3) the delay from the source node to any multicast destination node is bounded; and (4) locally minimize the number of wavelength conversions and the number of different wavelengths used to satisfy a multicast request. Simulation results show that the proposed algorithms work well and achieve satisfactory blocking probability.     

On-line integrated routing in dynamic multifiber IP/WDM networks

This paper focuses on dynamic integrated routing in multifiber Internet protocol/wavelength-division multiplexing (IP/WDM) networks, which can be implemented through either one-step routing (OSR) or two-step routing (TSR) approach. Based on an extended layered-graph, two resource assignment strategies, termed channel-level balance (CLB) and link-level balance (LLB), are proposed to balance the traffic in the network at different levels. To further improve the performance, a parameter K is introduced to make a dynamic tradeoff between the logical-layer links and the optical-layer links. Simulation studies are carried out for various topologies. The results show that LLB is better than CLB in most cases, and LLB combined with OSR has the optimal performance. Also, we find that the routing approach and the resource assignment strategy individually play different roles with different values of r/sub l/ that is introduced to indicate the resource richness of the network. As a multifiber network is functionally equivalent to a single-fiber network with limited wavelength conversion, we investigate the effects of wavelength conversion by studying the multifiber IP/WDM networks. The analysis shows that, when the granularity of each connection request is much smaller than the wavelength granularity, wavelength conversion may increase the request blocking probability in the network.     

IP/MPLS over WDM网中的动态选路和波长分配算法

该文研究了IP/MPLS over WDM网中,利用综合路由法为到达的业务流建立标签交换路径(LSP)时,如何选择是在WDM层为它新建一条光路,还是利用现有的逻辑IP链路来满足其要求,提出一种带宽碎片消除的策略,该策略在决定是否利用逻辑IP链路来建立LSP时,总是尽量减少造成带宽碎片,从而可以有效提高全网的资源利用率,仿真结果表明带宽碎片消除策略可以进一步改善综合路由算法的性能。     

抗毁WDM网中支持QoS的选路和波长分配算法

该文首先探讨了抗毁WDM网中支持QoS的分层图模型,在此基础上提出一种抗毁WDM网中支持QoS的选路和波长分配算法。该算法根据上层业务不同的QoS要求,对其光路建立请求区别对待,以满足它们不同的阻塞率和恢复率要求。计算机仿真结果表明该算法既满足了上层业务不同的QoS要求,同时又充分利用了有限的网络资源,使全网的平均阻塞率降低。     

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.

WDM网络中支持优先级的波长分配算法

本文提出了一种在WDM网络中支持优先级的波长分配算法,通过计算相对容量损失,力图在对较高优先级光路建立请求进行波长分配时,找到对较优先级请求影响最小的波长分配方案,这样,该算法既保证了较高优先级光路建立请求具有较低的阻塞率,同时又对较低优先级请求进行了优化,从而改善了全网的平均阻塞率。文中给出了计算机仿真结果。     

WDM网络中的一种波长分配算法

本文研究了动态业务下，采用固定选路和备用选路的波分复用光传送网中的波长分配问题，提出了一种波长分配算法-相对最小影响算法。与己朋的利用全网信息分配波长的算法相比，该算法能更精确地描述波长分配对全网状态的影响，使网络资源的充分利用成为可能。计算机仿真表明，该波长分配算法性能较好。     

Routing and wavelength assignment in WDM all-optical networks

A new mathematical formulation of the routing and wavelength assignment in wavelength division multiplexing (WDM) all-optical networks is proposed. Which yields tight linear programming lower bounds on the wavelength requirements both theoretically and computationally. An efficient procedure computing lower bounds is also presented together preliminary computational results.     

A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks

Unlike traditional heuristics, we provide in this paper an optimization framework for the routing and wavelength assignment (RWA) problems with the objective of minimizing the rejection penalty of the connection demands in an all-optical wavelength-division-multiplexing (WDM) network. Our new link-based formulation takes the fairness issue and the limited wavelength conversion into consideration. The framework employs a decomposition approach to decide on the rejection/selection of the route and wavelength assignment for a semilightpath, by appropriately relaxing some of the constraints in the Lagrangean relaxation (LR) method. At the higher level, we update Lagrange multipliers iteratively with the subgradient method. At the lower level, we propose the modified minimum cost semilightpath (MMCSLP) algorithm to solve all the subproblems. A heuristic algorithm is also proposed to generate a feasible RWA scheme based on the solution to the dual problem. When compared with some latest methodology in the literature, we demonstrate that our framework can achieve better performance in terms of the computation time and the number of connection demands rejected. The much shorter computation time is due to the polynomial time complexity of our framework. In addition to achieving a very good (near-optimal) solution, the influence from the change of the number of converters is studied. Finally, we demonstrate that our framework produces fairer routing decisions by adjusting some design parameters in our framework.