Light trees: optical multicasting for improved performance inwavelength routed networks

We introduce the concept of a light-tree in a wavelength-routed optical network. A light-tree is a point-to-multipoint generalization of a lightpath. A lightpath is a point-to-point all-optical wavelength channel connecting a transmitter at a source node to a receiver at a destination node. Lightpath communication can significantly reduce the number of hops (or lightpaths) a packet has to traverse; and this reduction can, in turn, significantly improve the network's throughput. We extend the lightpath concept by incorporating an optical multicasting capability at the routing nodes in order to increase the logical connectivity of the network and further decrease its hop distance. We refer to such a point-to-multipoint extension as a light-tree. Light-trees can not only provide improved performance for unicast traffic, but they naturally can better support multicast traffic and broadcast traffic. In this study, we shall concentrate on the application and advantages of light-trees to unicast and broadcast traffic. We formulate the light-tree-based virtual topology design problem as an optimization problem with one of two possible objective functions: for a given traffic matrix, (i) minimize the network-wide average packet hop distance, or (ii) minimize the total number of transceivers in the network. We demonstrate that an optimum light-tree-based virtual topology has clear advantages over an optimum lightpath-based virtual topology with respect to the above two objectives     

Optimal virtual topologies for one-to-many communication in WDM paths and rings

In this paper we examine the problem of constructing optimal virtual topologies for one-to-many communication in optical networks employing wavelength-division multiplexing. A virtual topology is a collection of optical lightpaths embedded in a physical topology. A packet sent from the source node travels over one or more lightpaths en route to its destination. Within a lightpath, transmission is entirely optical. At the terminus of a lightpath the data is converted into the electronic domain where it may be retransmitted on another lightpath toward its destination. Since the conversion of the packet from the optical to the electronic domain introduces delays and uses limited physical resources, one important objective is to find virtual topologies which minimize either the maximum or average number of lightpaths used from the source to all destination nodes. Although this problem is NP-complete in general, we show that minimizing the maximum or average number of lightpaths in path and ring topologies can be solved optimally by efficient algorithms.     

Dynamic Virtual Topology Reconfiguration Algorithms for Groomed WDM Networks

In a Wavelength Division Multiplexing (WDM) optical network, in which the traffic changes dynamically, the virtual topology designed for an old traffic set needs to be reconfigured for a new demand set in order to route more connections. Though reconfiguration increases the throughput, the resulting disruption in traffic is a cause for concern. We present a simple and flexible framework to evaluate the gain achieved by reconfiguration, based on the two conflicting objectives of increasing throughput and reducing disruption. We present adaptive reconfiguration algorithms which determine the change in the virtual topology with a corresponding change in the demand set. These algorithms incrementally add lightpaths to a given virtual topology and delete a minimum number of lightpaths to facilitate their addition. One of the algorithms improves throughput by making changes to the existing virtual topology and another one reduces disruption by making changes to the virtual topology suited for the new demand set. However, in order to reduce the gap in bandwidths between what a wavelength channel can provide and what an individual connection requires, several low-speed connections need to be groomed onto a single wavelength. As our algorithms aim at increasing the throughput with as few lightpath changes as possible, more connections will be accepted without considerable increase in number of lightpaths. This means, more connections are groomed onto the lightpaths. One nice feature of our approach is that it fits not only for groomed networks where traffic demands are at the sub wavelength level, but also for networks where connection demands are at the wavelength level. The extensive simulation studies, wherein we compared the performance of our algorithms with that of two other possible schemes, demonstrated their flexibility and robustness. This work was supported by the Department of Science and Technology, New Delhi, India.     

Virtual-topology adaptation for WDM mesh networks under dynamic traffic

We present a new approach to the virtual-topology reconfiguration problem for a wavelength-division-multiplexing- based optical wide-area mesh network under dynamic traffic demand. By utilizing the measured Internet backbone traffic characteristics, we propose an adaptation mechanism to follow the changes in traffic without a priori knowledge of the future traffic pattern. Our work differs from most previous studies on this subject which redesign the virtual topology according to an expected (or known) traffic pattern, and then modify the connectivity to reach the target topology. The key idea of our approach is to adapt the underlying optical connectivity by measuring the actual traffic load on lightpaths continuously (periodically based on a measurement period) and reacting promptly to the load imbalances caused by fluctuations on the traffic, by either adding or deleting one or more lightpath at a time. When a load imbalance is encountered, it is corrected either by tearing down a lightpath that is lightly loaded or by setting up a new lightpath when congestion occurs. We introduce high and low watermark parameters on lightpath loads to detect any over- or underutilized lightpath, and to trigger an adaptation step. We formulate an optimization problem which determines whether or not to add or delete lightpaths at the end of a measurement period, one lightpath at a time, as well as which lightpath to add or delete. This optimization problem turns out to be a mixed-integer linear program. Simulation experiments employing the adaptation algorithm on realistic network scenarios reveal interesting effects of the various system parameters (high and low watermarks, length of the measurement period, etc.). Specifically, we find that this method adapts very well to the changes in the offered traffic.     

Comprehensive design methodology for control and data planes in wavelength-routed optical networks

We propose a comprehensive design methodology for control and data planes of wavelength-routed optical networks (WRONs) employing mixed-line-rate (MLR) transmission for cost-effective resource provisioning. The proposed approach attempts to minimize the maximum lightpath capacity demand in Gbps (representing the measure of lightpath congestion) in network for a given traffic matrix by using a mix of a heuristic scheme and linear programming (LP). In the first step of the proposed three-step design, some lightpaths are set up on a set of judiciously selected fiber links (with point-to-point lightpaths between neighboring nodes), on a specific wavelength throughout the network, and an appropriate fraction of the same set of lightpaths is utilized for carrying control information, forming therefore the control plane (CP) of the WRON. The remaining bandwidth of these lightpaths is utilized to carry the data traffic along with all other designed lightpaths of the WRON using appropriate algorithm, forming the overall data plane (DP) of the WRON. In the second step, traffic routing is carried out through LP to minimize lightpath congestion in the network. In the third step, we utilize the results of LP to assign rates to lightpaths, such that the cost (considering only the transceiver cost) of the network is minimized. This design leads to congestion-aware MLR network with due consideration to cost-effectiveness without compromising the network restoration response against link failures. We carry out simulation studies employing possible CPs using both symmetric (CP topology being same as the physical topology) as well as asymmetric (using fewer fiber links than the symmetric case) topology. The results of our simulations indicate that the proposed design of CP with symmetric/asymmetric topology and in-band transmission with sub-lightpath capacity can bring down network congestion and cost with respect to symmetric out-of-band transmission (using fully reserved lightpaths for CP), without any perceptible sacrifice in respect of the network restoration time. Failure can occur either in CP or DP, or in both the planes. We investigate the effect of design of CP with symmetric/asymmetric topology on network restoration time for single- and double-link failures. We further present DP design methodology with hybrid restoration scheme, i.e., combination of dedicated (1:1) path protection and path restoration. We analyze the effect of symmetric CP topology and degree of protection on the congestion of the network. Some lightpaths, that support more traffic, are protected against failures, while the others are left for path restoration in the event of failures. As more lightpaths are protected, the congestion and power consumption of network increase. We provide an analysis of the factors that come into play while altering the degree of protection and observe how the choice for the degree of protection in DP can be arrived at using an appropriate design methodology.     

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.     

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.     

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 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.     

Selective survivability with disjoint nodes and disjoint lightpaths for layer 1 VPN

This paper deals with the problem of survivable routing and wavelength assignment in layer 1 virtual private networks (VPNs). The main idea is routing the selected lightpaths by the layer 1 VPN customer, in a link-disjoint manner. The customer may freely identify some sites or some connections, and have their related lightpaths routed through link-disjoint paths through the provider’s network. This selective survivability idea creates a new perspective for survivable routing, by giving the customer the flexibility of selecting important elements (nodes or connections) in its network. This study is different from previous studies which aim to solve the survivable routing problem for the whole VPN topology. The proposed scheme is two-fold: disjoint node based, and disjoint lightpath based. In disjoint node scheme, all lightpaths incident to a node are routed mutually through link-disjoint paths. In disjoint lightpath scheme, a lightpath is routed in a link-disjoint manner from all other ligthpaths of the VPN. We present a simple heuristic algorithm for selective survivability routing. We study the performance of this algorithm in terms of resources allocated by the selective survivability routing scheme compared to shortest path routing with no survivability. The numerical examples show that the amount of used resources by the selective survivability scheme is only slightly more than the amount used in shortest path routing, and this increase is linear. The extra resources used by the new scheme are justified by better survivability of the VPN topology in case of physical link failures, and the simplicity of the implementation.     

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.     

Efficient routing and wavelength assignment for reconfigurable WDMnetworks

Through the use of configurable wavelength-division-multiplexing (WDM) technology including tunable optical transceivers and frequency selective switches, next-generation WDM networks will allow multiple virtual topologies to be dynamically established on a given physical topology. For N node P port networks, we determine the number of wavelengths required to support all possible virtual topologies (PN lightpaths) on a bidirectional ring physical topology. We show that if shortest path routing is used, approximately N wavelengths are needed to map N lightpaths. We then present novel adaptive lightpath routing and wavelength assignment strategies that reduce the wavelength requirements to [(N/2)] working wavelengths per port for protected networks and [(N/3)] wavelengths in each direction per port for unprotected networks. We show that this reduced wavelength requirement is optimal in the sense that it is the minimum required to support the worst case logical topology. Furthermore, we prove that a significant number of logical topologies require this minimum number of wavelengths. We also develop joint routing and wavelength assignment strategies that not only minimize the number of wavelengths required to implement the worst case logical topologies but also reduce average wavelength requirements. Finally, methods for extending these routing and wavelength assignment results to general two-connected and three-connected physical topologies are presented     

Design of logical topologies: a linear formulation forwavelength-routed optical networks with no wavelength changers

We consider the problem of constructing logical topologies over a wavelength-routed optical network with no wavelength changers. We present a general linear formulation which considers routing traffic demands, and routing and assigning wavelengths to lightpaths, as a combined optimization problem. The formulation also takes into account the maximum number of hops a lightpath is permitted to take, multiple logical links in the logical topology, multiple physical links in the physical topology, and symmetry/asymmetry restrictions in designing logical topologies. The objective is to minimize congestion. We show by examples how equality and inequality logical degree constraints have a bearing on congestion. We prove that, under certain conditions, having equality degree constraints with multiple edges allowed in the design of logical topologies does not affect congestion. This helps in reducing the dimensionality of the search space and hence speeds up the search for an optimal solution of the linear formulation. We solve the linear formulation for small examples and show the tradeoff between congestion, number of wavelengths available and the maximum number of hops a lightpath is allowed to take. For large networks, we solve the linear formulation by relaxing the integer constraints. We develop topology design algorithms for large networks based on rounding the solutions obtained by solving the relaxed problem. Since the whole problem is linearizable, the solution obtained by relaxation of the integer constraints yields a lower bound on congestion. This is useful in comparing the efficiency of our heuristic algorithms. Following Bienstock and Gunluk (1995), we introduce a cutting plane which helps in obtaining better lower bounds on congestion and also enables us to reduce the previously obtained upper bounds on congestion     

Optical BGP Routing Convergence in Lightpath Failure of Optical Internet

Optical Border Gateway Protocol (OBGP) is an extension to BGP for Optical Cross Connects (OXCs) to automatically setup multiple direct optical lightpaths between many different autonomous domains. With OBGP, the routing component of a network may be distributed to the edge of the network while the packet classification and forwarding is done in the core. However, it is necessary to analyze the stable convergence functions of OBGP in case of lightpath failures. In this paper, we first describe the architecture of the OBGP model and analyze the potential problems of OBGP, e.g., virtual BGP router convergence behavior in the presence of lightpath failure. We then propose an OBGP convergence model derived from an inter‐AS (Autonomous System) relationship. The evaluation results show that the proposed model can be used for a stable OBGP routing policy and OBGP routing convergence under lightpath failures of the optical Internet.     

Design of logical topologies for wavelength-routed optical networks

The problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology is studied. The physical topology consists of the nodes and fiber links in the network. On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics. The set of lightpaths along with the nodes constitutes the logical topology. For a given network physical topology and traffic pattern, our objective is to design the logical topology and the routing algorithm so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology). Ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays. On the other hand, in all our examples, imposing it results in a minimal increase in congestion. While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small. We formulate the combined logical topology design and routing problem described above as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network. This programming problem is split into two subproblems: logical topology design, and routing. We then compare the performance of several heuristic topology design algorithms against that of randomly generated topologies, as well as lower bounds     

Optical network design with mixed line rates

Future telecommunication networks employing optical wavelength-division multiplexing (WDM) are expected to be increasingly heterogeneous and support a wide variety of traffic demands. Based on the nature of the demands, it may be convenient to set up lightpaths on these networks with different bit rates. Then, the network design cost could be reduced because low-bit-rate services will need less grooming (i.e., less multiplexing with other low-bit-rate services onto high-capacity wavelengths) while high-bit-rate services can be accommodated on a wavelength itself. Future optical networks may support mixed line rates (say over 10/40/100 Gbps). Since a lightpath may travel a long distance, for high bit rates, the effect of the physical impairments along a lightpath may become very significant (leading to high bit-error rate (BER)); and the signal’s maximum transmission range, which depends on the bit rate, will become limited.In this study, we propose a novel, cost-effective approach to design a mixed-line-rate (MLR) network with transmission-range (TR) constraint. By intelligent assignment of channel rates to lightpaths, based on their TR constraint, the need for signal regeneration can be minimized, and a “transparent” optical network can be designed to support all-optical end-to-end lightpaths. The design problem is formulated as an integer linear program (ILP). A heuristic algorithm is also proposed. Our results show that, with mixed line rates and maximum transmission range constraints, one can design a cost-effective network.     

Capacity performance of dynamic provisioning in optical networks

This paper describes an architecture and analyzes the performance of dynamic provisioning of lightpaths in an optical network. In dynamic provisioning, a lightpath is set up in real-time without rearranging the working and protection routes of existing lightpaths, and without the knowledge of future lightpath provisioning events. This paper develops a general model of the physical topology of the optical network, and outlines routing approaches for dynamic provisioning of lightpaths. It analyzes via simulations the performance of dynamically provisioned unprotected, 1+1 protected and mesh-restored lightpaths. The analysis of the efficiency of network utilization of dynamic provisioning focuses on the spare capacity needed for protection, and in particular focuses on the impact of sharing of wavelength channels for mesh-restored lightpaths. The main conclusion from the performance studies is that significant capacity gains are achieved with sharing of wavelength-channels for mesh-restored lightpaths with dynamic provisioning even for sparse topologies, and even at moderate loads     

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.     

Post‐Disaster least loaded lightpath routing in elastic optical networks

Disaster events directly affect the physical topology of core networks and may lead to simultaneous failure of multiple lightpaths leading to massive service outages for network operators. To recover from such a failure scenario, the existing routing algorithms running on network nodes (routers or switches) typically attempt to reestablish the connections over new routes with shortest distances and hop count approach. However, this approach may result in congestion on some links, while other links may have the unutilized capacity. Hence, intelligent lightpath computing techniques are required to efficiently route network traffic over the new routes by considering traffic load of each link in addition to distance and hop count to minimize network congestion. In this paper, we have proposed a capacity‐constrained maximally spatial disjoint lightpath algorithm to tackle the provisioning and restoration of disrupted lightpaths in a postdisaster scenario in the context of elastic optical networking. This algorithm computes an alternate least loaded lightpath for disrupted primary lightpath using capacity‐constrained shortest lightpath. Alternate lightpath selection is based on a criteria parameter for a lightpath to be least loaded and constrained by either the length or the spatial distance between primary and alternate lightpaths. The spatial distance between lightpaths enables to reestablish the disrupted connection request away from disaster proximity. The performance of the proposed algorithm is evaluated through simulation for several parameters like blocking probability, network utilization, connection success rates, and minimum spatial distance.     

Providing traffic tolerance in optical packet switching networks: a reinforcement learning approach

The servitization of network resources leads to new challenges for optical networks. For instance, to provide on-demand lightpaths as a service while keeping the probability of packet loss (PPL) low, issues such as lightpath setting up, resource reservation and load balancing must be addressed. We present a self-adaptive framework to process lightpath requests on packet switching optical networks that considers and handles the aforementioned issues. The framework is composed of a dimensioning phase that adds up new resources to an initial topology and a learning phase based on reinforcement learning that provides self-adaptation to tolerate traffic changes. The framework is tested on three realistic mesh topologies achieving a PPL between \(1 \times 10^{-1}\) and \(1 \times 10^{-6}\) for different traffic loads. Compared to fixed multi-path routing strategies, our framework reduces PPL between \(19\%\) and up to \(80\%\). Furthermore, no packet loss can also be achieved for traffic loads equal to or lower than 0.4.