Dynamic load balancing in WDM packet networks with and without wavelength constraints

We develop load balancing algorithms for WDM-based packet networks where the average traffic between nodes is dynamically changing. In WDM-based packet networks, routers are connected to each other using wavelengths (lightpaths) to form a logical network topology. The logical topology may be reconfigured by rearranging the lightpaths connecting the routers. Our algorithms reconfigure the logical topology to minimize the maximum link load. In this paper, we develop iterative reconfiguration algorithms for load balancing that track rapid changes in the traffic pattern. At each reconfiguration step, our algorithms make only a small change to the network topology hence minimizing the disruption to the network. We study the performance of our algorithms under several dynamic traffic scenarios and show that our algorithms perform near optimally. We further show that these large reconfiguration gains are achievable in systems with a limited number of wavelengths.     

Traffic grooming,routing, and wavelength assignment in an optical WDM mesh networks based on clique partitioning

In wavelength routed optical networks, the number of wavelength channels is limited due to several constraints and each wavelength as well as each lightpath support traffic in the Gbps range. On the other hand, the traffic requested by an individual connection is still in the Mbps range. Therefore, to utilize the network resources (such as bandwidth and transceivers) effectively, several low-speed traffic streams have to be efficiently groomed or multiplexed into one or more high-speed lightpaths. The grooming problem of a static demand is considered as an optimization problem. In this work, we have investigated the traffic grooming problem with the objective of maximizing the network throughput for wavelength-routed mesh networks and map this problem to the clique partitioning problem. We have proposed an algorithm to handle general multi-hop static traffic grooming based on the clique partitioning concept. The efficiency of our approach has been established through extensive simulation on different sets of traffic demands with different bandwidth granularities for different network topologies and compared the approach with existing algorithms.     

Reconfiguration of Logical Topologies with Minimum Traffic Disruptions in Reliable WDM-Based Mesh Networks

A wavelength division multiplexing (WDM) network offers a flexible networking infrastructure by assigning the route and wavelength of lightpaths. We can construct an optimal logical topology, by properly setting up the lightpaths. Furthermore, setting up a backup lightpath for each lightpath improves network reliability. When traffic demand changes, a new optimal (or sub-optimal) topology should be obtained by again applying the formulation. Then, we can reconfigure the running topology to the logical topology obtained. However, during this reconfiguration, traffic loss may occur due to the deletion of older lightpaths. In this paper, we consider reconfiguring the logical topology in reliable WDM-based mesh networks, and we propose five procedures that can be used to reconfigure a running lightpath to a new one. Applying the procedures one by one produces a new logical topology. The procedures mainly focus on utilizing free wavelength resources and the resources of backup lightpaths, which are not used usually for transporting traffic. The results of computer simulations indicate that the traffic loss is remarkably reduced in the 14-node network we used as an example.     

Design of wavelength-routed optical networks for packet switchedtraffic

We consider the problem of designing a logical optical network topology for a given physical topology (or fiber layout) and a given traffic demand matrix between the end-users. Traffic between the end-users is carried in a packet-switched form and the objective of our logical topology design is to minimize the maximum congestion on the logical connections in the logical topology. The logical connections are realized by wavelength continuous paths or lightpaths between end-users and they are routed via wavelength-selective routers. Note that a topology with lower maximum link congestion will allow its traffic demand matrix to be scaled up by a larger factor. In the logical topology each node is equipped with a limited number of optical transceivers, hence logical connections cannot be set up between every pair of nodes. In this paper we present an improved lower bound for maximum congestion on any link In the logical topology. The bound is shown to be up to 50% higher than the existing ones. An analytical model for obtaining the maximum and average logical connection loads for a given logical network and traffic demand matrix is also formulated, and it has been confirmed via simulation. Finally, two heuristic algorithms for constructing a logical topology that reduces maximum logical connection congestion are presented     

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.     

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     

Green optical backbone networks: virtual topology adaptation using a page rank‐based rating system

An energy‐aware virtual topology rating system is proposed in this work, which can be utilized as a tool during the virtual topology reconfiguration procedure in an optical backbone network in order to reduce its energy consumption. It is well known that maintaining a static virtual topology in Internet Protocol (IP)‐over‐Wavelength Division Multiplexing (WDM) networks is not energy‐efficient. To that end, virtual topology adaptation algorithms have been developed to adjust the virtual topology to the constantly fluctuating traffic load. While these algorithms achieve significant energy savings, further reduction on the total network energy consumption can be achieved through the proposed rating system. The proposed rating system is a modified version of the page rank algorithm, which ranks websites in the Internet based on their importance. The proposed rating system attributes ratings to lightpaths, which indicate the relative significance of a lightpath in the virtual topology in terms of energy consumption. The rating can be used during the routing procedure as an energy efficiency indicator, in order to increase the number of lightpaths that are deactivated from the reconfiguration mechanism and increase the utilization per lightpath. The proposed reconfiguration scheme (page rank‐based virtual topology reconfiguration) achieves up to 12% additional energy savings in comparison to an existing virtual topology reconfiguration algorithm at the cost of slightly increased average hop distance. Copyright © 2015 John Wiley & Sons, Ltd.     

Virtual Topology Design and Reconfiguration of Virtual Private Networks (VPNs) over All-Optical WDM Networks

This paper studies the virtual topology design and reconfiguration problem of virtual private networks (VPNs) over all-optical WDM networks. To support VPN service, a set of lightpaths must be established over the underlying WDM network to meet the VPN traffic demands and this set of lightpaths must also be dynamically reconfigurable in response to changing VPN traffic. To achieve good network performance and meet the service requirements of optical virtual private networks (oVPNs), we formulate the problem as an integer programming problem with multi-objectives and present a general formulation of the problem. In the formulation, we take into account the average propagation delay over a lightpath, the maximum link load, and the reconfiguration cost with objectives to minimize the three metrics simultaneously. The formulated problem is NP-hard and is therefore not practical to have exact solutions. For this reason, we use heuristics to obtain approximate optimal solutions and propose a balanced alternate routing algorithm (BARA) based on a genetic algorithm. To make the problem computationally tractable, we approximately divide BARA into two independent stages: route computing and path routing. At the route computing stage, a set of alternate routes is computed for each pair of source and destination nodes in the physical topology. At the path routing stage, an optimal route is decided from a set of alternative routes for each of the lightpaths between a pair of source and destination nodes. A decision is subject to the constraints and objectives in the formulation. To improve the computational efficiency, we use a genetic algorithm in BARA. Through simulation experiments, we show the effectiveness of BARA and the evolution process of the best solution in a population of solutions produced by the genetic algorithm. We also investigate the impact of the number of alternative routes between each pair of source and destination nodes on the optimized solutions.     

An Algorithm for Traffic Grooming in WDM Optical Mesh Networks with Multiple Objectives

This paper studies a traffic grooming in wavelength-division multiplexing (WDM) mesh networks for the SONET/SDH streams requested between node pairs. The traffic could be groomed at the access node before converting to an optical signal carried in the all-optical network. We design a virtual topology with a given physical topology to satisfy multiple objectives and constraints. The grooming problem of a static demand is considered as an optimization problem. The traditional algorithms found in the literatures mostly focus on a single objective either to maximize the performance or to minimize the cost. We propose a multi-objective evolutionary algorithm to solve a grooming problem that optimizes multiple objectives all together at the same time. In this paper we consider the optimization of three objectives: maximize the traffic throughput, minimize the number of transceivers, and minimize the average propagation delay or average hop counts. The simulation results show that our approach is superior to an existing heuristic approaches in an acceptable running time.     

Offline Impairment-Aware Routing and Wavelength Assignment Algorithms in Translucent WDM Optical Networks

Physical impairments in optical fiber transmission necessitate the use of regeneration at certain intermediate nodes, at least for certain lengthy lightpaths. We design and implement impairment-aware algorithms for routing and wavelength assignment (IA-RWA) in translucent optical networks. We focus on the offline version of the problem, where we are given a network topology, the number of available wavelengths and a traffic matrix. The proposed algorithm selects the 3R regeneration sites and the number of regenerators that need to be deployed on these sites, solving the regenerator placement problem for the given set of requested connections. The problem can be also posed in a slightly different setting, where a (sparse) placement of regenerators in the network is given as input and the algorithm selects which of the available regenerators to use, solving the regenerator assignment problem. We formulate the problem of regenerator placement and regenerator assignment, as a virtual topology design problem, and address it using various algorithms, ranging from a series of integer linear programming (ILP) formulations to simple greedy heuristic algorithms. Once the sequence of regenerators to be used by the non-transparent connections has been determined, we transform the initial traffic matrix by replacing non-transparent connections with a sequence of transparent connections that terminate and begin at the specified 3R intermediate nodes. Using the transformed matrix we then apply an IA-RWA algorithm designed for transparent (as opposed to translucent) networks to route the traffic. Blocked connections are re-routed using any remaining regenerator(s) in the last phase of the algorithm.      

波长交换光网络中路由波长分配技术

路由波长分配问题是在给定连接的情况下,为该请求分配适当的光路进行传输。在无波长转换能力的情况下,需要为光路在其传输的链路上分配相同的波长,这就是波长连续性问题。物理层的光损伤极大的限制了光网络的能力,因此需要可感知损伤的路由波长分配算法来保证传输的质量。对于不同的感知损伤的路由波长分配方式,相应地,有不同的控制平面结构。     

Multi-domain grooming algorithm based on hierarchical integrated multi-granularity auxiliary graph in optical mesh networks

With the size of traffic demands ranges from sub-wavelength-level to wavelength-level, traffic demands need to be aggregated and carried over the network in a cost-effective manner to make sure that the resources are utilized effectively. Therefore, the technique called multi-granularity grooming is proposed to save the cost by reducing the number of switching ports in optical cross-connects. However, the existing multi-granularity grooming algorithms are mostly limited in single-domain optical networks. Since the current optical backbone keeps enlarging and is actually divided to multiple independent domains for achieving the scalability and the confidentiality, it is necessary to study the multi-granularity grooming in multi-domain optical networks. In this paper, we propose a new heuristic algorithm called hierarchical multi-domain multi-granularity grooming (HMMG) based on hierarchical integrated multi-granularity auxiliary graph (H-IMAG) to reduce the total number of optical switching ports. The H-IMAG is composed of the inter-domain virtual topology graph (VTG) and the intra-domain integrated layered auxiliary graph (ILAG), where VTG includes a wavelength virtual topology graph (WVTG) and a waveband virtual topology graph (BVTG), and ILAG includes a wavelength layered auxiliary graph (WLAG) and a waveBand layered auxiliary graph (BLAG). Then, we can groom the sub-wavelength-level demands into lightpaths based on WVTG and WLAG and groom the wavelength-level demands into high-capacity wavebands based on BVTG and BLAG. Simulation results show that performances of H-IMAG can be significantly improved compared with previous algorithm.     

Distributed virtual network topology control mechanism in GMPLS-based multiregion networks

This paper proposes a distributed virtual network topology (VNT) reconfiguration method for Internet Protocol over a wavelength-division-multiplexing network under dynamic traffic demand. We have developed a simple heuristic algorithm for calculating the VNT for distributed control. A generalized multiprotocol label switching (GMPLS)-based routing protocol has been developed. The VNT is quickly reconfigured by setting up and/or tearing down lightpaths using a GMPLS signaling protocol. Traffic demand is measured at the ingress node and advertised by the extended GMPLS routing protocol. Performance of the proposed method is investigated using variable traffic model.     

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.     

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     

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     

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.     

Virtual topology transition sequence problem on WDM networks with dedicated protection

Wavelength-division multiplexing (WDM) technology has emerged as a promising technology for backbone networks. The set of all-optical communication channels (lightpaths) in the optical layer defines the virtual topology for the upper layer applications. Since the traffic demand of upper layer applications fluctuates from time to time, it is required to reconfigure the underlying virtual topology in the optical layer accordingly. However, the reconfiguration for the virtual topology is reluctantly disruptive to the network since some lightpaths should be torn down and some traffic has to be buffered or rerouted during the reconfiguration process. Therefore, it needs to have an efficient transition method to shift the current virtual topology to the new one so as to minimize the effect of the reconfiguration on the upper layer traffic. In this article, the WDM virtual topology transition sequence problem (WVTTSP) which minimizes the average weighted delay (AWD) is studied. Since the WVTTSP is NP-hard, a heuristic solution model is proposed to solve it. Simulation results show that the proposed least weighted distance first (LWDF) method can find the best result and the time spent by it is less than 4 s for a middle-sized network with 100 links and with 30 wavelengths per link.

Information Theoretic Approach to Traffic Adaptive WDM Networks

WDM networks adapt to the changes in traffic by reconfiguring the virtual topology. Though reconfiguration is done with the objective of utilizing resources efficiently, the resulting disruption in traffic is a cause for concern. Hence, policies are formed to decide on the time (i.e., when) to trigger reconfiguration and the new virtual topology that is most beneficial to the network. We present a simple, general and flexible framework, based on the two conflicting objectives of efficient resource utilization and minimizing traffic disruption, to evaluate reconfiguration policies. Instead of re-determining the reconfiguration policy whenever the traffic changes, we present Incremental Clustering Algorithm (ICA) to pre-plan the reconfiguration policy for a fully predictable finite sequence of traffic matrices. Since full predictability of such a sequence is not possible in practice, we learn the traffic sequences in order to probabilistically predict the future ones. From an information theoretic point of view, we quantify the predictability of traffic sequences and the number of times the reconfiguration policy is re-determined for any WDM network. To optimally predict the future traffic sequences and to incur optimal cost in the re-determination of the reconfiguration policy, we propose Universal Reconfiguration Management System (URMS). A Prediction-based Incremental Clustering Algorithm (PICA) that extends ICA is used by URMS to predict the reconfiguration policy. Within URMS, the probabilities are assigned to the traffic sequences by the prediction schemes of LZ78. We performed extensive simulations to study the effectiveness and efficiency of URMS when compared to the fully predictable and totally unpredictable models. The performance of URMS improves with learning and nearly achieves the performance of a fully predictable model.     

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.