Logical topology design for dynamic traffic grooming in WDM optical networks

Traffic grooming in optical networks refers to consolidation of subwavelength client connections onto lightpaths. Depending on whether client connections are given in advance or randomly arrive/depart, traffic grooming is classified as static and dynamic. Dynamic traffic grooming has been traditionally performed through establishing/releasing lightpaths online. In this paper, the authors propose an alternate approach to design a static logical topology a priori and then route randomly arriving client connections on it to avoid frequent lightpath setup/teardown. Two problems are considered: 1) minimize resource usage constrained by traffic blocking requirements and 2) maximize performance constrained by given resources. These are formulated as integer linear-programming (ILP) problems. The numerical results show that the resource usage dramatically decreases when the blocking requirement is relaxed, and the grooming performance slowly increases when given more resources. In addition, the number of ports at client nodes has more profound impact on traffic grooming than the number of wavelengths.     

一种新的动态流量疏导算法

文章主要研究WDM(波分复用)光网络中动态业务流量疏导的选路算法,提出了基于拓扑融合的动态流量疏导算法。该算法的最大特点在于融合了物理拓扑及其抽象出来的虚拓扑,利用最小权重优先方法进行选路。仿真结果表明,该算法在不增大建路时延的基础上,可以有效提高资源利用率,降低阻塞率,尤其是在高负载情况下,效果显著。     

On optimal traffic grooming in WDM rings

We consider the problem of designing a virtual topology to minimize electronic routing, that is, grooming traffic, in wavelength routed optical rings. The full virtual topology design problem is NP-hard even in the restricted case where the physical topology is a ring, and various heuristics have been proposed in the literature for obtaining good solutions, usually for different classes of problem instances. We present a new framework which can be used to evaluate the performance of heuristics and which requires significantly less computation than evaluating the optimal solution. This framework is based on a general formulation of the virtual topology problem, and it consists of a sequence of bounds, both upper and lower, in which each successive bound is at least as strong as the previous one. The successive bounds take larger amounts of computation to evaluate, and the number of bounds to be evaluated for a given problem instance is only limited by the computational power available. The bounds are based on decomposing the ring into sets of nodes arranged in a path and adopting the locally optimal topology within each set. While we only consider the objective of minimizing electronic routing in this paper, our approach to obtaining the sequence of bounds can be applied to many virtual topology problems on rings. The upper bounds we obtain also provide a useful series of heuristic solutions     

Virtual topology reconfiguration on optical WDM networks considering traffic grooming

This paper investigates the virtual topology reconfiguration (VTR) problem of optical WDM networks by taking the traffic grooming factor into consideration. Firstly, by applying a common “divide and conquer” approach, the problem is categorized and handled as two independent sub-problems, triggering policy and the proper algorithm. Secondly, the VTR problem considering traffic grooming is formulated with new variables and constraints by a mixed-integer linear program (MILP). In order to handle the tradeoff between the advantages and disadvantages of VTR, both network resource utilization and network disruption are examined and quantified in terms of measurable parameters. A new multi-objective VTR algorithm called integrated reconfiguration (IR) algorithm is proposed to provide better overall VTR performance. Different from previous studies this newly proposed VTR algorithm combines three main factors (traffic load, traffic grooming ratio and route length of lightpaths) into one single objective and considers them all when reconfiguring. The results of simulations indicate that proposed VTR policy, periodic VTR triggering policy with IR algorithm, achieves performance improvements for overall VTR performance.     

Constrained light-tree design for WDM mesh networks with multicast traffic grooming

Multicast applications such as IPTV, video conferencing, telemedicine and online multiplayer gaming are expected to be major drivers of Internet traffic growth. The disparity between the bandwidth offered by a wavelength and the bandwidth requirement of a multicast connection can be tackled by grooming multiple low bandwidth multicast connections into a high bandwidth wavelength channel or light-tree. Light-trees are known to be especially suited for networks that carry ample multicast traffic. In this paper, we propose new algorithms to address the problem of multicast traffic grooming. In particular, an Integer Linear Programming (ILP) formulation is proposed for optimal assignments of hop constrained light-trees for multicast connections so that network throughput can be maximized. Hop constrained light-trees improve the scalability of the approach by reducing the search space of the ILP formulation. Since solving the ILP problem is very time consuming for realistically large networks, we are motivated to propose a heuristic algorithm with a polynomial complexity, called Dividable Light-Tree Grooming (DLTG) algorithm. This algorithm is based on grooming traffic to constrained light-trees and also divides a light-tree to smaller constrained light-trees on which traffic is groomed for better resource utilization. Simulations show that the proposed DLTG heuristic performs better than other algorithms. It achieves network throughputs which are very close to the ILP formulation results, but with far lower running times.     

Joint scheduling and virtual topology design for sliding periodic traffic

Two possible approaches can be considered for solving the virtual topology design problem for periodic (multi-hour) traffic demands. The first approach attempts to design a static topology that can accommodate all the traffic variations over time. The second option is to determine an appropriate series of virtual topologies to accommodate the different traffic loads at different times. This can lead to some savings in terms of the number of transceivers needed, but it requires the use of costly reconfigurable switching equipment. So, strategies for stable virtual topology design have received considerable attention in recent years. However, all the works reported in the literature so far, focus on the fixed window scheduled traffic model, where the start and end times of the demands are known in advance. In this paper, we propose a new integrated approach using the more general sliding window model, for jointly scheduling the demands in time and designing a logical topology that can accommodate all the scheduled demands. The goal is to a find a suitable static topology that can handle fluctuations in the offered sub-wavelength traffic load, without requiring the use of reconfigurable optical switching equipment. We first present a comprehensive integer linear program (ILP) formulation for designing a cost-efficient, stable logical topology for time-varying demands, and then propose an integrated heuristic algorithm capable of handling larger networks. Simulation results demonstrate the advantages of the proposed approaches, not only compared to holding time unaware models, but also over the traditional fixed window model.     

Algorithms for the global design of WDM networks including the traffic grooming

In this paper, we propose a model and algorithms for the global design problem of wavelength division multiplexing (WDM) networks including the traffic grooming. This problem consists in finding the number of fibres between each pair of nodes (i.e. the physical topology), finding the number of transponders at each node, choosing the set of lightpaths (i.e. the virtual topology), routing these lightpaths over the physical topology and, finally, grooming and routing the traffic over the lightpaths. Since this problem is NP-hard, we propose two heuristic algorithms and a tabu search metaheuristic algorithm to find solutions for real-size instances within a reasonable amount of computational time.     

Resource efficient network design and traffic grooming strategy with guaranteed survivability

In WDM networks, path protection has emerged as a widely accepted technique for providing guaranteed survivability of network traffic. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new design strategy for survivable network design, which guarantees survivability of all ongoing connections that requires significantly fewer network resources than protection based techniques. In survivable routing, the goal is to find a Route and Wavelength Assignment (RWA) such that the logical topology remains connected for all single link failures. However, even if the logical topology remains connected after any single link fault, it may not have sufficient capacity to support all the requests for data communication, for all single fault scenarios. To address this deficiency, we have proposed two independent but related problem formulations. To handle our first formulation, we have presented an Integer Linear Program (ILP) that augments the concept of survivable routing by allowing rerouting of sub-wavelength traffic carried on each lightpath and finding an RWA that maximizes the amount of traffic that can be supported by the network in the presence of any single link failure. To handle our second formulation, we have proposed a new design approach that integrates the topology design and the RWA in such a way that the resulting logical topology is able to handle the entire set of traffic requests after any single link failure. For the second problem, we have first presented an ILP formulation for optimally designing a survivable logical topology, and then proposed a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection schemes.     

A framework for solving logical topology design problems within constrained computation time

We present a framework for solving logical topology design (LTD) problems in a constrained amount of computation time. Our framework uses a search space dimensionality (SSD) reduction technique that exploits a tradeoff between computation time and solution quality. We have demonstrated that our framework offers improved solution quality in comparison to an existing SSD reduction technique reported in the literature.     

Physical topology design for survivable routing of logical rings in WDM-based networks

In a wavelength-division multiplexed (WDM)-based network, a single physical link failure may correspond to multiple logical link failures. As a result, two-connected logical topologies, such as rings routed on a WDM physical topology, may become disconnected after a single physical link failure. We consider the design of physical topologies that ensure logical rings can be embedded in a survivable manner. This is of particular interest in metropolitan area networks, where logical rings are in practice almost exclusively employed for providing protection against link failures. First, we develop necessary conditions for the physical topology to be able to embed all logical rings in a survivable manner. We then use these conditions to provide tight bounds on the number of physical links that an N-node physical topology must have in order to support all logical rings for different sizes K. We show that when K/spl ges/4 the physical topology must have at least 4N/3 links, and that when K/spl ges/6 the physical topology must have at least 3N/2 links. Subsequently, we generalize this bound for all K/spl ges/4. When K/spl ges/N-2, we show that the physical topology must have at least 2N-4 links. Finally, we design physical topologies that meet the above bounds for both K=4 and K=N-2. Specifically, our physical topology for embedding (N-2)-node rings has a dual hub structure and is able to embed all rings of size less than N-1 in a survivable manner. We also provide a simple extension to this topology that addresses rings of size K=N-1 and rings of size K=N for N odd. We observe that designing the physical topology for supporting all logical rings in a survivable manner does not use significantly more physical links than a design that only supports a small number of logical rings. Hence, our approach of designing physical topologies that can be used to embed all possible ring logical topologies does not lead to a significant overdesign of the physical topology.     

On the physical and logical topology design of large-scale optical networks

We consider the problem of designing a network of optical cross-connects (OXCs) to provide end-to-end lightpath services to large numbers of label switched routers (LSRs). We present a set of heuristic algorithms to address the combined problem of physical topology design (i.e., determine the number of OXCs required and the fiber links among them) and logical topology design (i.e., determine the routing and wavelength assignment for the lightpaths among the LSRs). Unlike previous studies which were limited to small topologies with a handful of nodes and a few tens of lightpaths, we have applied our algorithms to networks with hundreds or thousands of LSRs and with a number of lightpaths that is an order of magnitude larger than the number of LSRs. In order to characterize the performance of our algorithms, we have developed lower bounds which can be computed efficiently. We present numerical results for up to 1000 LSRs and for a wide range of system parameters such as the number of wavelengths per fiber, the number of transceivers per LSR, and the number of ports per OXC. The results indicate that it is possible to build large-scale optical networks with rich connectivity in a cost-effective manner, using relatively few but properly dimensioned OXCs.     

基于负载均衡和流量优先级的网络拓扑设计

交换式以太网网络的拓扑结构设计是一个带约束的优化问题,需要同时考虑多种约束条件。本文中定义了两个主要的准则：交换机负载均衡和流量最短路径。根据设计目标而衡量每条准则的权重．对拓扑进行评分而进行网络的拓扑结构设计。该方法以终端节点间网络流量需求矩阵和终端设备间流量优先级矩阵为输入,利用遗传算法从所有的拓扑结构中找出最优拓扑,决定交换机生成树拓扑和终端节点的分布位置。通过网络仿真,可以证明此方法的有效性。     

Cost-effective traffic grooming in WDM rings

We provide network designs for optical add-drop wavelength-division-multiplexed (OADM) rings that minimize overall network cost, rather than just the number of wavelengths needed. The network cost includes the cost of the transceivers required at the nodes as well as the number of wavelengths. The transceiver cost includes the cost of terminating equipment as well as higher-layer electronic processing equipment, which in practice can dominate over the cost of the number of wavelengths in the network. The networks support dynamic (i.e., time-varying) traffic streams that are at lower rates (e.g., OC-3, 155 Mb/s) than the lightpath capacities (e.g., OC-48, 2.5 Gb/s). A simple OADM ring is the point-to-point ring, where traffic is transported on WDM links optically, but switched through nodes electronically. Although the network is efficient in using link bandwidth, it has high electronic and opto-electronic processing costs. Two OADM ring networks are given that have similar performance but are less expensive. Two other OADM ring networks are considered that are nonblocking, where one has a wide-sense nonblocking property and the other has a rearrangeably nonblocking property. All the networks are compared using the cost criteria of number of wavelengths and number of transceivers     

支持多优先级QoS的业务量疏导算法

文章针对当前波分复用(WDM)光网络中业务量疏导技术研究的局限性,提出支持多优先级服务质量(QoS)的业务量疏导算法--MTGA.该算法基于业务流QoS的需求,将业务标记为不同等级,然后尽量选择占用跳数最少的通路来建立连接.仿真结果显示,与已有算法相比,MTGA能够有效地降低有时延约束连接请求的阻塞率.     

Algorithms for multicast traffic grooming in WDM mesh networks

Several of the new applications in high-performance networks are of the multicast traffic type. Since such networks employ an optical network infrastructure, and since most of these applications require subwavelength bandwidth, several streams are usually groomed on the same wavelength. This article presents an account of recent advances in the design of optical networks for multicast traffic grooming in WDM mesh networks. The article addresses network design and session provisioning under both static and dynamic multicast traffic. Under static traffic conditions, the objective is to accommodate a given set of multicast traffic demands, while minimizing the implementation cost. Optimal and heuristic solution techniques for mesh network topologies are presented. Under dynamic traffic conditions, techniques for dynamic routing and session provisioning of multicast sessions whose objective is to minimize session blocking probabilities are explained. The article also presents a number of open research issues     

一种新的动态流量疏导算法

基于层叠网络模型,将饱和割集的方法应用于IP over WDM光网络的动态流量疏导中.该方法通过提取IP层网络的拓扑特征,并应用该特征触发多种方式建立光路,增加了在光层建立光路的灵活性.仿真结果显示,该方法可以有效降低网络阻塞率.     

基于拓扑信息挖掘的动态流量疏导算法

在迭加模型的IP over WDM 网络中,文章作者进一步利用饱和割集算法来提取IP层的有效拓扑信息,利用该信息优化建立光路的方法,降低了整个网络的阻塞率.仿真结果显示,应用了双重饱和割集算法的网络比只用一种饱和割集算法的网络的阻塞率更低.     

波长变换技术对全光网络设计和性能的影响

波长变换技术是波分复用全光网关键技术之一。本文综述了波长变换技术对网络的逻辑拓扑结构设计、网络的性能以及网络的管理和控制的影响。     

WDM光网络中的动态流量疏导

针对波分复用光网络中的业务疏导问题,文章基于通道组交换网络模型,采用波分复用网络中的相对容量算法来解决业务疏导的路由、波长分配和时隙分配问题.基于该模型的算法能够将波长和时隙分配这两个通常分开解决的问题一步解决,因此比现有方法具有更好的效能,仿真也验证了这一点.     

A traffic grooming problem of SONET-WDM rings

In this paper, we present a traffic grooming problem of the SONET-WDM ring. The objective is to minimize the total cost of optical add-drop multiplexers (OADMs) and inter-ring hub equipment, while satisfying intra-ring and inter-ring capacities. We develop integer programming (IP) formulations for the problem and devise some reformulations for enhancing the mathematical representation of the proposed IP model. By investigating the polyhedral structure of the problem, we develop some valid inequalities that provide a tight lower bound for the problem. Dealing with the inherent computational complexity of the problem, we also devise an effective tabu search procedure for finding a feasible solution of good quality within reasonable computation time. Computational results are provided to demonstrate the relative strength of the proposed formulations, and to reveal the efficacy of the lower and upper bound procedures for solving the problem.