Routing and Wavelength Assignment Algorithms for WDM Networks

Abstract

The Internet traffic and on-line e-business are growing all day and night, how to support the rapidly growing bandwidth demand and different Quality of Service (QoS) requirements has become an important issue. Wavelength Division Multiplexing (WDM) is an important technique to exploit the huge bandwidth of the optical fiber. There has been a wide deployment of WDM transmission technology in today’s optical networks. WDM is based on the transmission of several light beams of different wavelength simultaneously through an optical fiber. A wavelength typically operates in hundreds of Mbps or even Gbps needs to be utilized better if the connection request is less than 100 Mbps bandwidth, otherwise there is a tremendous wastage of bandwidth in a fiber for data transmission. Though the fiber bandwidth has been improved due to the advancements in fiber-optic technologies and the increase in number of wavelengths in a fiber, there has not been much research in the area of fault tolerance, routing and wavelength assignment. These technologies are becoming a technology-of-choice to meet the ever-increasing demand for high-bandwidth. The large usable bandwidth (nearly 50 THz), reduced processing cost, protocol transparency, low bit-error rates and effective network component failure handling are some of the important advantages which have made wavelength routed WDM optical networks a standard for high-speed transport networks. A WDM optical network consists of wavelength routing nodes interconnected by optical fiber links in an arbitrary topology. In these networks a message can be sent from one node to another node using a wavelength continuous path called a lightpath and is uniquely identified by a physical route and a wavelength. It is required that the same wavelength should be used on all the links along the selected route and this constraint is known as the wavelength continuity constraint. Typically the traffic demand in these networks can be static, dynamic or scheduled. In Static Lightpath Establishment (SLE), the goal is to establish lightpaths so as to optimize certain objective function (minimizing wavelength usage, congestion, blocking and maximizing single-hop traffic, etc.). The Dynamic Lightpath Establishment (DLE) problem is concerned with the establishment of lightpaths with an objective of increasing the average call acceptance ratio when connection requests arrive and depart from the network dynamically. Hence, the objective is to route the demands to maximize the reuse of network resources. Like any communication network WDM networks are prone to hardware failure (such as routers and/or switches and cable cuts) and software (protocol) bugs. WDM networks carry a huge volume of traffic maintaining a high level of service availability. It is essential to incorporate fault- tolerance into QoS requirements. The deployment of WDM network is increasing in today’s public Internet. Reliability and consistency are the important factors which must be taken into consideration before the deployment of any system. The fault tolerance could be provided at the optical layer or at the higher client (electrical) layers, each of which has its own merits. The optical layer has faster fault tolerance time and the use of wavelength channels in an optical layer is very optimal. Routing problem, Wavelength Assignment (WA) problem, Routing and Wavelength Assignment (RWA), Fault tolerance and survivability are some of the important problems which can increase the efficiency of WDM networks and are thus receiving a lot of attention recently. Keeping in view these aspects, the objectives of research were formulated which are listed as below: 1. To study and analyse the existing wavelength assignment algorithms and to develop new algorithm of wavelength assignment for better performance in wavelength division multiplexed networks. 2. To study and analyse the existing routing algorithms and to develop new effective routing algorithms for survivable wavelength division multiplexed networks. 3. To compare the newly developed routing and wavelength assignment algorithms with the existing algorithms in terms of blocking for wavelength division multiplexed network. To provide methods for effectively addressing the RWA problem, a novel framework has been developed that relies on mathematical models for routing in static and dynamic scenarios. In this thesis, probabilistic mathematical models are proposed and investigated for achieving better blocking performance of such networks. It has been demonstrated that these proposed mathematical models are capable of achieving better performance than the earlier models. To arrive at this result, we have defined various metrics for measuring the efficiency of routing algorithms for both the static and dynamic demands. Using these metrics, a variety of simulations have been performed. It has been shown in the thesis that the use of proposed mathematical models is the key to achieve superior performance in all-optical networks. Wavelength assignment algorithms and routing schemes for restoration have also been proposed for the better performance of the optical WDM networks. Further, routing and wavelength assignment problem has been dealt as a single problem and solutions for this problem have been proposed and compared with the conventional solutions. We have proposed the low complexity probabilistic mathematical models for the calculation and reduction of blocking probability in wavelength convertible as well as in wavelength non-convertible WDM optical networks. We have proposed four mathematical models; two of these models have been proposed for wavelength non– convertible WDM Networks, one model for wavelength convertible WDM networks and one of the models has been proposed which can be implemented on both wavelength convertible and non–convertible WDM Networks. These probabilistic mathematical models proposed have closed-form expression and do not require any simulated statistics. These models possess low implementation complexity and the computation used is quite efficient. These models suggest the choice of best optimum path and appropriate number of free wavelengths in the network. These models were then used to evaluate and improve the blocking performance and fairness of network topology such as NSFnet. The results showed that the models work well for larger networks having higher number of wavelengths and even for those networks which have larger load per link. These models can also be implemented easily on any network. Further, the blocking probability can be reduced to a large extent using these models. Also, it has been shown that the computation efficiency of the proposed models is very high. Two effective algorithms named Most Used Wavelength Conversion (MUWC) and First Fit Wavelength Conversion (FFWC) have also been proposed and the performance of new wavelength assignment algorithms has been evaluated in terms of blocking probability. The results of proposed algorithms were compared with conventional wavelength assignment algorithms such as first-fit, best-fit, random and most-used wavelength assignment algorithms. These proposed approaches were found very effective for minimization of blocking probability of the optical WDM networks. The response of blocking probability of existing wavelength assignment algorithms with network having 10 nodes for varying load have also been analysed. Two new wavelength assignment strategies which used sparse wavelength conversion have been proposed which proved to be very effective as compared to the earlier algorithms in situations where there is no possibility of changing the mathematical model. Further, two wavelength routing schemes have been proposed for survivable networks. These schemes have been proposed for dynamic provisioning of lightpath which proved to be very efficient in calculation and minimization of blocking probability and produced very effective results. To improve performance of all optical survivable WDM networks, techniques based on wavelength rerouting have been applied. Two rerouting algorithms named Shortest Path Wavelength Rerouting (SPWRR) algorithm and Lightpath Rerouting Algorithm (LRRA) for dynamic traffic in WDM optical networks have been proposed. These wavelength rerouting algorithm have also been employed on realistic WDM optical network topology (NSFnet) to investigate blocking performance and resource utilization. The key advantage of these algorithms as compared to conventional routing and wavelength assignment algorithms is that these are very simple in nature and require less service disruption time. The results have also proved that LRRA can be implemented to huge networks for good blocking performance of the network. Also, grooming and RWA problems have been dealt as a single problem and different solutions have been provided for this problem. These solutions have been used to evaluate the blocking performance of realistic networks such as NSFnet and EUPAN Networks. Hence these solutions can be used to improve the performance of a network on the basis of blocking probability. Further, a problem of enhancing multiple-fault tolerance in the path protected wavelength–routed all optical WDM networks has been discussed. Different mechanisms have been proposed for fault tolerance which were used to combat multiple link failures such as, Fault Tolerant Routing and Wavelength Assignment (FTRWA) algorithm and Survivable Routing and Wavelength Assignment Algorithm (SRWA). The comparison of these algorithms has been made with algorithms mentioned in literature. These algorithms have been implemented on different optical networks with multiple faults and proved to be effective for variable load on the nodes. These algorithms worked well with the changing load. Two generic routing and wavelength assignment algorithms (GRWA-I & GRWA-II) have been proposed for optimization and minimization of blocking probability. Using these routing and wavelength assignment algorithm the blocking probability can be reduced to a large extent. The proposed algorithms have also been compared with conventional routing and wavelength assignment algorithms. The investigations thus carried out in this thesis results in blocking free environment in an optical network. The mathematical models and the algorithms proposed in the thesis are very simple in operation and do not require any simulation statistics. Some of the solutions suggested in this thesis can be used for fault tolerance in survivable wavelength Division multiplexed optical network.