In this paper we investigate the problem of designing a survivable IP over WDM networks. We present a novel integrated protection scheme to dynamically allocate restorable bandwidth guaranteed path. Restoration implies that a flow of data is successfully routed if both an active path and another alternate link-disjoint path are setup at the same time. The new scheme takes advantage of the recent development in MPLS/MP(lambda) S to provide integrated end-to-end survivability, and incorporates network state information (such as the cost information in physical links, the bandwidth usage on each lightpath, and intermediate router forwarding speed) into protection path allocation. We design a survivable logical topology on top of the underlying physical connectivity that connects IP routers. Unlike the conventional approach for designing a static logical topology where the traffic demand is known a priori, we dynamically construct the logical connections between IP routers. This approach leads to a new QoS routing problem where it is necessary to dynamically route both an active path and a backup path in order to satisfy a request to set-up a restorable bandwidth guaranteed paths. Simultaneously establishing backup paths ensures fast restoration by eliminating path computation and path set-up signaling delays.
In this paper we discuss a quantitative framework for best- effort protection of the optical layer. This framework provides a way to bridge the gap between two known protection grades of fully protected connections vis-a-vis unprotected protection. The framework allows to specify the probability with which the connection will be protected, providing the customer with a full range of protection guarantees at possibly different prices. Since connections may be partially protected, the required protection bandwidth can be reduced. The amount of protection bandwidth is shown to depend on an 'equivalent survivable bandwidth.' The framework also extends to preemptable (low priority) connections and to different ring architectures.
Wavelength division multiplexing (WDM) networks are matured to provide, scalable data centric infrastructure, capable of delivering flexible, value added, high speed and high bandwidth services directly from the optical (WDM) layer. Different applications/end users need different levels of fault tolerance and differ in how much they are willing to pay for the service they get. The current optical networks are capable of providing either full protection in presence of single failure or no protection at all. So, there is a need for a way of providing the requested level of fault tolerance (reliability) to different applications/end users. We choose the reliability of a connection as a parameter to denote the different levels of fault tolerance. In this paper, we consider the problem of dynamically establishing reliable connections (R-connections) in wavelength routed WDM optical networks. We develop an efficient algorithm to select routes and wavelengths to establish an R-connection with a specified reliability guarantee, in a resource efficient manner, using primary-backup approach. In our scheme, we provide partial backup lightpaths for varying lengths of the primary lightpath to enhance the reliability of the connection. The length of the primary lightpath for which the backup lightpath is provided depends on the reliability required by the application/end user but not on the actual length of the primary lightpath, network topology, and design constraints. We present the initial experimental results which suggest that our scheme is attractive enough in terms of resource utilization and average call acceptance ratio.
We study the benefit of reconfigurability for single-hub WDM ring networks with dynamic single-hubbed traffic. We show that using reconfigurable wavelength add-drop multiplexers (R- WADMs) in place of non-reconfigurable ones can reduce the number of expensive line terminating equipments (LTEs) by a factor of W, where W is the number of wavelengths in the network. In addition, we show that for a general class of traffic, optical networks using R-WADMs guarantee to be (almost) as bandwidth-efficient as full wavelength add-drop networks (that is, opaque networks). For such traffic, we introduce several fast algorithms that achieve or approximate the optimal performance guarantees. The comparison between reconfigurable networks and opaque networks is quantified using a performance metric called capacity ratio, which captures the relative throughput performance of a reconfigurable network compared to the opaque network.
This paper addresses the problem of dynamically establishing dependable low-rate traffic stream connections in WDM mesh networks with traffic grooming capabilities. To establish a dependable connection, we set up link-disjoint primary and backup traffic stream paths between the source and destination and use backup multiplexing to reduce the overhead of backup traffic streams. We present a dynamic algorithm to obtain the optimal spare capacity on a wavelength on a link when a number of backup traffic streams are multiplexed onto it. We propose two schemes for grooming traffic streams onto wavelengths: Mixed Primary-Backup Grooming Policy (MGP) and Segregated Primary-Backup Grooming Policy (SGP). We illustrate how these schemes can be applied in a WDM mesh network scenario along with a routing and wavelength assignment algorithm. We conduct simulation experiments to evaluate the effectiveness of the proposed schemes on different network topologies, using different routing and wavelength assignment methods. The effect of change in granularity and change in the number of alternate paths on the grooming policies are also presented. From the simulation results, it is inferred that SGP is useful in network topologies, such as mesh-torus, characterized by good connectivity and a good amount of traffic switching and mixing at the nodes. On the other hand, MGP is useful in network topologies, such as a ring, characterized by low connectivity and high load correlation.
Recently, it is expected by a number of engineers that an intelligent optical network will be used for transport network of Internet. A MP(Lambda) S (Multiprotocol Lambda Switching), that is based on both wavelength routing technology and MPLS control plane protocols, is an approach IETF proposed for intelligent optical network. In this article, we propose a network architecture for the MP(lambda) S network, called an Integrated MPLS network. This article also applies a merging mechanism to MP(lambda) S network to improve connectivity, likely MPLS. The Merging mechanism can reduce the number of labels requested and blocking probability for label requests. However, wavelengths, unlikely electrical label, cannot be merged at optical level. To solve this problem, we define a merging module that interleaves two different data streams at electrical level. In addition, we examine the routing problem of the proposed MP(Lambda) S network and propose a graph model for solving this problem, simply. For evaluation of the proposed mechanism, we use simulation mode. The simulation results show that the merging mechanism may offer significant improvement of network performance.
Control architectures have recently been proposed to aid in unifying the packet and optical layers, with a goal of enabling network efficiency and operational simplicity for Internet service providers. Network applications that use the inter-layer information and control interfaces of these architectures are examined and analyzed for their value to different service providers and for their fit within the architectural models.
This paper addresses the suitability of WDM coarse packet switching solutions for IP traffic. Our findings show that the combination of traffic grooming at the higher layers and coarse packet switching at the optical layer provides at least the same performance as more sophisticated and difficult to realize photonic packet switching solutions. We propose a network architecture named files-over-lightpaths that not only simplifies the network optical and electronic design by making use of coarse packet switching, but also serves to the purpose of decreasing the TCP transaction latency in comparison to a flat or split Internet organization with fine grain photonic packet switching.
No doubt, there is a need to introduce intelligence into the control plane of the optical network to provide dynamic and real-time provisioning and effective survivability. However, the traffic pattern migration from static to dynamic gives rise to many challenging issues. One such issue is the route assignment. For static traffic, the route assignment can generally be optimized using a variety of offline algorithms. For dynamic traffic, however, such a global optimization is impossible. Nevertheless, it is possible to perform individual optimization for each new call in the dynamic traffic pattern. In this paper, we propose an enhanced route assignment mechanism for the optical control plane and evaluate its performance benefits.
In this paper we present a new localized distributed routing approach, called Multi-Path routing, for real time provisioning in a WDM network. Under the proposed approach, no global state information exchange among network nodes is needed and the destination node makes adaptively both routing and wavelength selection decisions. Two path selection schemes are considered and their performance is compared, namely First-Come-First-Serve (FCFS) path selection scheme and least- congested path (LCP) selection scheme. Time discrete simulation tool is developed to analyze the blocking performance, the connection set up time and the bandwidth required for control messages. Results show that the new adaptive multi-path routing algorithm outperforms the conventional alternate shortest-path routing algorithm.
This paper has outlined a method (called OBGP) of extending BGP to support lightpath setup and management across an optical network. The development of OBGP has been discussed by reviewing current BGP behavior and design requirements for OBGP. An implementation of OBGP using simulation tools has been presented, along with initial test results, which have shown that a seamless migration from BGP to OBGP is possible.
A major challenge of optical network design is deciding where spare capacity is needed and how much, so that interrupted traffic may be rerouted in the event of a failure. Given the optical network topology and traffic forecast, the network design needs to map the traffic forecast into optical connection demands. For each optical connection demand, two paths need to be computed, i.e., a service path and a restoration path. In most cases, optical network design mainly considers single failure. If two service paths do not share any single failure, their restoration paths can share the same capacity on any links that they have in common. In this way, the total spare capacity needed for restoration can be dramatically reduced. However, due to the layered architecture in optical networks, a pair of diverse paths in a particular layer won't necessarily be diverse when the lower layer topology is considered. For example, optical networks are typically built on top of a network of fiber spans. A single span cut in the fiber network can cause multiple link failures in the optical layer. In this paper, we investigate fiber span failure protection scenarios in mesh optical networks. Specifically, we provide an algorithm to find two fiber span disjoint paths for each demand, such that the total spare capacity allocated in the network is minimized. Another problem that arises in restoration path computation is the existence of a trap topology. In a trap topology, the pre- selected service path may not have a diverse restoration path even though two diverse paths exist in the network. For simple link-disjoint protection, the min-cost max-flow algorithm can be used to avoid this problem. For fiber span failure protection, the trap topology problem becomes complicated. We show that it is NP-hard problem to find the maximum number of fiber-span disjoint paths between two nodes. We provide two heuristic algorithms to solve this trap topology problem. We have implemented fiber span failure protection in our restoration capacity planning toolkit Cplan. We describe an application of fiber span failure protection at the end of the paper.
In a connection-oriented network, shared protection provides the same level of protection against single path failures as dedicated protection, with potentially higher network utilization. This paper lists the requirements of path protection and proposes a heuristic routing algorithm for shared protection provisioning. Simulations were conducted to verify the algorithm and to compare network utilization of shared protection to that of dedicated protection.
In order to construct a reliable IP over WDM network, backup paths as well as primary paths should be embedded within a wavelength-routed topology (or logical topology). However, many conventional approaches assume that the traffic demand is known a priori. In this paper, we propose a new approach, called an incremental capacity dimensioning approach, to build the logical topology. Our incremental approach consists of three steps for designing the logical topology: an initial phase, an incremental phase, and a readjustment phase. By our approach, the logical topology can be adjusted according to the incrementally changing traffic demand. During the incremental phase, the backup lightpaths are reconfigured when the new primary path is set up since the backup lightpaths do not affect the carried traffic on the primary paths. Our proposed algorithm, called MRB (Minimum Reconfiguring for Backup lightpath), assigns the wavelength route in such a way that the number of backup lightpaths to be reconfigured is minimized. Then, the backup lightpaths are actually reconfigured. For this purpose, we also formulate an optimality problem for reconfiguring the backup lightpaths. Our results show the total traffic volume which the IP over WDM network can accommodate is improved by using our MRB algorithm.
We consider a scheduling problem, which we call the Scheduling and Wavelength Assignment (SWA) problem, arising in optical networks that are based on the Wavelength Division Multiplexing (WDM) technology. We prove that the SWA problem is (Nu) (Rho) -hard for both the preemptive and the non- preemptive cases. Furthermore, we propose two efficient approximation algorithms. The first is for the preemptive case and it is based on a natural decomposition of the problem to the classical multiprocessor scheduling and open-shop problems. For the non-preemptive case, we prove that a naive implementation of list scheduling produces a schedule that can be m times far from the optimum, where m is the number of processors (equivalently, WDM channels). Finally, we give a more refined version of list scheduling and we prove it to be a 2-approximation algorithm for both the off-line and the on- line contexts.
Multicasting in the optical layer has gained significant importance in the recent years due to several factors. Most of the research work in this area concentrate either on minimizing the number of wavelengths required to meet a given static demand or on multicast route selection algorithms to achieve efficient utilization of fiber bandwidth. Very few significant research has been found, to the best of authors' knowledge, in developing an analytical model for evaluating the blocking performance of tree establishment in optical networks, which motivates this research. In this paper, an analytical model for evaluating the blocking performance of multicast tree establishment in time-space switched optical networks is developed. The performance of different switch architectures are then studied using the analytical model. it is observed that if the multicast tree has very low degree of branching, the blocking probability of establishing the tree is the same as that of establishing a path with same number of links.
The problem of assigning wavelengths and routing multicast sessions in DWDM networks has given rise to a host of heuristic and approximate techniques. In this paper we demonstrate that it is feasible to find optimal solutions for many instances of this problem using integer linear programming. The technique presented is also useful as an optimal standard to which heuristics can be compared in order to determine the quality of solutions they generate. The goal of this paper is to document an integer programming tableau for routing multicast sessions in DWDM networks, while accounting for a variety of limits on the abilities of the nodes in the network to drop, split and convert wavelengths. Examples of applying the tableau to problems of moderate size are included.
This paper addresses the problem of wavelength assignment and wavelength routing in a wide-area optical network, where Wavelength Division Multiplexing (WDM) technology has emerged as the transmission and switching choice. One of the major design issues in this network is the assignment of the limited number of wavelengths among network stations so that higher aggregate capacity can be achieved. The problem of wavelength assignment and routing is proved to be NP-hard problem. The present literature on this topic is a large repertoire of heuristics that produce good solutions in a reasonable amount of time. These heuristic, however, have restricted applicability in a practical environment because they have a number of fundamental problems including high time complexity, lack of scalability with respect to optimal solutions. In this paper, we propose genetic based algorithm with an objective to simultaneously meet the goals of height performance and fast running time. In addition, we propose to apply the Greedy Random Adaptive Search Procedure (GRASP) to solve the wavelength assignment problem. We demonstrate that our proposed algorithms can achieve lower blocking probability while taking considerably less running time when compared to one of the best known heuristic wavelength assignment algorithms proposed by Zhang and Acampora, in which close to optimal solution can be obtained.
In this paper we consider the routing and wavelength assignment problem in a wavelength routed all optical network. Inspired by techniques from artificial intelligence, in particular the Blocking Island (BI) abstraction, we propose a simple and intelligent routing and wavelength assignment (RWA) algorithm: BI_RWA. This algorithm can be used in arbitrarily connected optical networks. In addition, it is general enough such that with some simple modifications, it can be applied to different optical networking scenarios: static or dynamic traffic, single or multiple fiber links between node pairs, with or without wavelength converters. We have conducted simulation experiments to evaluate the performance of our algorithm. The simulation is carried out in two parts: static traffic and dynamic traffic. The results will demonstrate that our RWA algorithm outperforms state-of-the-art related algorithms.
Existing approaches for logical topology design and routing for multi-hop optical networks become intractable for large networks. One approach is to treat the logical topology design problem separately from the routing problem which can be solved as a LP problem. The straightforward formulation of the LP problem has been reported but this is also feasible only for relatively smaller networks since the basis size for the simplex method is O(n(superscript 3)) where n is the number of nodes in the network. In this paper, by exploiting the special structure of the routing problem, we present an efficient column generation scheme embedded into the revised simplex method. This approach makes it feasible to handle networks with relatively large number of nodes. To study the approach experimentally we have used a number of traffic based heuristics for generating the logical topologies. These include a variation of the well known HLDA heuristic and two simple traffic based heuristics to generate logical topologies based on regular graphs. Many researchers feel that regular graphs are not well suited for wide area optical networks. The interesting result is that logical topologies based on regular graphs perform quite well compared to others. This suggests that it is useful to consider regular graphs as possible topologies for wide area networks and should be included as potential candidates for large wide area networks.