Dynamic Establishment Of Differentiated Survivable Lightpaths In

Transcript

Computer Communications 27 (2004) 273–294 www.elsevier.com/locate/comcom Dynamic establishment of differentiated survivable lightpaths in WDM mesh networks Chava Vijaya Saradhia,*, C. Siva Ram Murthyb a Institute for Infocom Research I2R Distributed Systems, 21 Heng Mui Keng Terrace, Singapore, Singapore 119613 b Department of Computer Science and Engineering, Indian Institute of Technology, Madras 600036, India Received 24 April 2002; revised 17 July 2003; accepted 6 August 2003 Abstract In the emerging next-generation transport networks, called intelligent optical transport networks, DWDM-based optical components like add-drop multiplexers and optical cross connects will have full knowledge of the wavelengths in the network, status, and traffic carrying capacity of each wavelength. With such intelligence, these intelligent optical networks could create self-connecting and self-regulating connections on-the-fly. Because these networks carry huge volume of traffic, maintaining a high level of service availability at an acceptable level of overhead is an important and critical issue. It is essential to incorporate fault-tolerance into QoS requirements. Since the delay (response time) becomes unbounded as the load approaches the link capacity, delay is usually dominated by the most heavily loaded links; therefore algorithms must attempt to minimize the delay. In this paper, we take fault-tolerance, delay, bandwidth, and availability as QoS parameters to provide varying classes of services based on the type of primary and backup lightpaths and the number of backup lightpaths for studying the problem of dynamically establishing lightpaths in WDM optical networks. The type of primary and backup lightpaths determines the QoS parameters such as response time and bandwidth. Whereas, the number of backup lightpaths determines the level of faulttolerance and availability of the connection. Based on the service classes, any connection in the network falls into one of the seven classes, viz. single dedicated primary and single dedicated backup, single dedicated primary and multiple dedicated backups, single dedicated primary and single shared backup, single shared primary and single shared backup, single shared primary and multiple shared backup, single dedicated multi-hop primary and single dedicated multi-hop backup, and single shared multi-hop primary and single shared multi-hop backup. We conduct extensive simulation experiments to compare and evaluate the effectiveness of different classes for varying network configurations—varying number of fibers, wavelengths on physical links, and different traffic patterns. q 2003 Elsevier B.V. All rights reserved. Keywords: Wavelength division multiplexing; Fault-tolerance; Survivability; Availability; Class of service; Quality of service 1. Introduction All-optical networks employing wavelength division multiplexing (WDM) and wavelength routing are potential candidates for future wide-area backbone networks [1]. These WDM networks which provide high throughput of the order of terabits per second, low error rates, and low delay, can satisfy the emerging applications such as supercomputer visualization, medical imaging, and distributed CPU interconnect. A WDM network consists of wavelength cross-connects (WXCs) interconnected by * Corresponding author. Tel.: þ 6590062991; fax: þ6567744998. E-mail addresses: [email protected] (C.V. Saradhi), saradhi@ i2r.a-star.edu.sg (C.V. Saradhi), [email protected] (C.S.R. Murthy). 0140-3664/$ - see front matter q 2003 Elsevier B.V. All rights reserved. doi:10.1016/j.comcom.2003.08.004 point-to-point fiber links in an arbitrary mesh topology. WDM technology provides several wavelengths per fiber as logical channels. Present WDM technology allows transmission rates of up to 2.5 or 10 Gbp per channel £ 40 channels at 100 and 50 GHz spacing and standard link distance up to 600 with 80 km between optical amplifiers. In these networks a lightpath is established between any two nodes by allocating the same wavelength on all the links along the chosen route. The requirement that the same wavelength must be used on all the links along the chosen route is known as wavelength continuity constraint [1]. Two lightpaths can use the same wavelength, if and only if they use different fibers (wavelength reuse). A lightpath is uniquely identified by a physical route and a wavelength. If a lightpath is established between any two nodes, traffic 274 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 between these nodes can be routed without requiring any intermediate opto-electrical conversion and buffering. Traffic demand can be either static or dynamic. In static lightpath establishment (SLE), traffic demand between node pairs is known a-priori and the goal is to establish lightpaths so as to optimize certain objective function (maximizing single-hop traffic, minimizing congestion, minimizing average weighted hop count, etc.). The nodes together with the set of lightpaths at the optical layer forms a virtual topology [1]. An optical layer consists of a set of lightpaths and can be used in a wide-area backbone network between the lower physical layer and higher client (electrical) layer. The dynamic lightpath establishment (DLE) problem concerns with establishing lightpaths with an objective of increasing the average call acceptance ratio (or equivalently reducing the blocking probability) when connection requests arrive and depart dynamically. Several heuristic algorithms for routing and wavelength assignment (RWA) problem are available in the literature [2 – 5]. Generally, longer-hop connections are subjected to more blocking than shorter-hop connections. The fairness among the individual connections with different hop length is an important problem in WDM networks. A good RWA algorithm is critically important in order to improve the network performance in terms of average call acceptance ratio. A RWA algorithm has two components, viz. route selection and wavelength selection. Different RWA algorithms have been proposed in the literature to choose best pair of routes and wavelengths. Based on the restriction (if any) on choosing a route from all possible routes, route selection algorithms can be fixed routing (FR), alternate routing (AR), and exhaust routing (ER) [3,6]. Depending upon the order in which wavelengths are searched, the wavelength selection algorithms can be most used (MU), least used (LU), fixed ordering (FX), and random ordering (RN). In Ref. [3], all these wavelength selection algorithms are compared and results showed that MU scheme performs best compared to all other wavelength assignment schemes. But, the MU scheme requires the actual or estimated global state information of the network to determine the usage of every wavelength. This scheme is more suitable for centralized implementation and is not easily amenable for distributed implementation. In WDM networks, a connection request may be rejected because of non-availability of a common wavelength on all the links along the chosen route. Wavelength continuity constraint leads to inefficient utilization of wavelength channels and thus results in higher blocking probability. Wavelength rerouting and wavelength conversion are two possible approaches for improving the average call acceptance ratio [7]. Wavelength rerouting accommodates a new connection request by migrating a few existing lightpaths to new wavelengths while maintaining their route. However, it incurs control overhead and more importantly the service in the rerouted lightpaths need to be disrupted. A wavelength converter is a device capable of shifting one wavelength to another, without converting into electrical form. A wavelength converter is said to have a conversion degree D, if it can shift any wavelength to one of D wavelengths. The wavelength continuity constraint is relaxed at converting nodes and therefore, a convertible network can accept more number of connections. Because, wavelength conversion is a very expensive and immature technology, multi-fiber network is a viable and cost effective approach, which can improve the blocking probability. Like the single-fiber networks, multi-fiber networks also require that route chosen for satisfying a connection request must be wavelength continuous. However, the chances of finding the same wavelength free on all the links along the route is higher, as it can choose the free wavelength on any of the fibers in a link connecting a node pair. A multi-fiber network with F fibers per bundle and l wavelengths per fiber is functionally equivalent to a single-fiber network with F l wavelengths with conversion degree of F [7]. Any communication network is prone to hardware (components like routers, switches, cable cuts) failures and software (protocol) bugs. Because WDM networks carry huge volume of traffic, maintaining a high level of service availability at an acceptable level of overhead is an important issue. It is essential to incorporate fault-tolerance into Quality of Service (QoS) requirements for distributed real-time multimedia applications such as video conferencing, scientific visualization, virtual reality, and distributed real-time control. The optical (wavelength) layer consists of WDM systems, intelligent optical switches that perform all restoration and end-to-end optical layer provisioning. Restoration could be provided at the optical layer or at the higher client (electrical) layer, each of which has its own merits. Optical layer has faster restoration and provisioning times and use the wavelength channels optimally [8,9]. Because of these many of the functions are moving to the optical layer. The foremost of them are routing, switching and network restoration. High-speed mesh restoration becomes a necessity, and this is made possible by doing the restoration at the optical layer using optical switches. Such restorations can be performed within a duration of 50– 200 ms, compared to minutes to tens of minutes taken in traditional mesh restoration architectures of today. 1.1. Outline of the remaining sections The rest of the paper is organized as follows. In Section 2, we review some commonly used terms, and do a brief survey of related work. In Section 3, we provide the motivation for our work and discuss the network model used in our work. In Section 4, we look at different classes of connections. In Section 5, we present numerical results from the simulation experiments. Finally, we conclude our work in Section 6. C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 2. Survivability and provisioning in WDM networks Transport networks with an optical layer between the higher electrical path layer and the lower physical media layer are capable of meeting the new challenges fueled by the ever-increasing demand for bandwidth. WDM networks are prone to failures of components such as links, fibers, nodes, and wavelength channels. Since, these networks carry high volumes of traffic, failures may have severe consequences. Therefore, it is imperative that these networks have some fault-tolerance capability. Fault-tolerance refers to the ability of the network to configure and reestablish communication upon failure. A related term known as restoration refers to the process of rerouting affected traffic upon a component failure. A network with restoration capability is known as survivable network or restorable network. A fiber cable causes a link failure making all its constituent fibers fail. A node failure may be caused due to the failure of the WXC. When a component fails, all the lightpaths that are currently using that component will fail. The lightpath that carries traffic during the normal operation is known as the primary lightpath. When a primary lightpath fails, the traffic is rerouted over a new lightpath known as the backup lightpath. The process of assigning the network resources to a given traffic demand is known as provisioning a network. Given a set of traffic demands, the provisioning problem is to allocate resources to the primary and backup lightpaths for each demand, so as to minimize the spare resources required [8,9]. The resources in this case are the number of wavelengths for single-fiber networks and the number of fibers for multifiber networks. A connection request with a fault-tolerance requirement is called as a dependable connection (D-connection) [10,11]. The restoration methods differ in their assumptions about the functionalities of cross-connects (wavelength selective or wavelength convertible), traffic demand (static or dynamic), performance metric (restoration guarantee, restoration time, spare resource utilization, etc.), and mode of network control (centralized or distributed). The methods designed for establishing connections with fault-tolerance requirements can be broadly divided into reactive and pro-active. In the reactive method of restoration, when an existing lightpath fails, a search is initiated for finding a new lightpath, which does not use the failed components. This has an advantage of low overhead in the absence of failures. However, this does not guarantee successful recovery, as an attempt to establish a new lightpath may fail due to resource shortage at the time of failure recovery. In the pro-active method, backup lightpaths are identified and resources are reserved along the backup lightpaths at the time of establishing primary lightpath itself. Pro-active or reactive restoration method is either link based or path based. The link based method employs local detouring while path based method employs end-to-end 275 detouring. Local detouring reroutes the traffic around the failed component, while in end-to-end detouring a backup lightpath is selected between the end nodes of the failed primary lightpath. Local detouring is inefficient in terms of resource utilization. Furthermore, handling node failures is very difficult in local detouring. A path based restoration method is either failure dependent or failure independent. In a failure dependent method, associated with every link used by a primary lightpath, there is a backup lightpath. When a primary lightpath fails, the backup lightpath that corresponds to the failed link will be used. In a failure independent method, a backup lightpath, which is disjoint with the primary lightpath is chosen. A pro-active restoration method may use a dedicated backup lightpath for a primary lightpath. In dedicated backup scheme wavelength channels are not shared between any two backup lightpaths. For better resource utilization, multiplexing techniques can be employed. If two lightpaths do not fail simultaneously, their backup lightpaths can share a wavelength channel. This technique is known as backup multiplexing [10]. A pro-active restoration method can employ primary-backup multiplexing [11] to further improve resource utilization. This technique allows a wavelength channel to be shared by a primary and one or more backup lightpaths. 2.1. Related work Provisioning restorable single-fiber networks without wavelength conversion is dealt in Refs. [8,9]. In Ref. [8], integer linear programming (ILP) formulations for three different pro-active restoration methods, i.e. dedicated backup reservation, path-based restoration allowing backup multiplexing, and link based restoration using backup multiplexing are developed. The objective here is to minimize the number of wavelengths used on the links. Capacity utilization for path and link based protection schemes for interconnected rings, with a random traffic demand is also computed. In Ref. [12], provisioning restorable single-fiber networks with wavelength conversions is dealt with. The problem is formulated as an ILP problem, where the objective is to minimize the weighted number of wavelengths required. Failure independent path based restoration is used. In Ref. [13], provisioning restorable multi-fiber networks is considered. Two schemes, virtual wavelength path (VWP) and wavelength path (WP), are proposed. They assume the presence of wavelength interchange and wavelength selective cross-connects, respectively. Both schemes are pro-active, path based and failure dependent, employing backup multiplexing. Here, the objective is to reduce fiber requirements. In Ref. [14], provisioning multi-fiber wavelength selective networks is considered. The approach used is proactive, failure dependent path based, employing backup multiplexing. Two iterative design methods, independent and coordinated design, are developed. Here, the objective 276 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 is minimizing the network cost. Provisioning multi-fiber networks for wavelength converting and wavelength selective networks is dealt in Ref. [15]. Three pro-active restoration methods are proposed. These methods are path based failure independent method, path based failure dependent method, and link based method. In Ref. [15], the authors showed that spare capacity requirement is the least in case of failure dependent path based restoration followed by failure independent path based restoration and link based restoration in that order. In case of path based restoration in wavelength selective networks, two methods are considered. In method-1 the same wavelength is used for both primary and backup lightpaths. In method-2 the backup lightpath may use any wavelength independent of its primary lightpath. Unlike static traffic demand, dynamic traffic demand requires computationally simpler algorithms. As the connection requests arrive one by one, the objective of a dynamic routing algorithm is to select the best primarybackup lightpath pair for each request so as to improve the average call acceptance ratio. Some dynamic routing algorithms for fault-tolerant routing in WDM networks have been recently proposed in Refs. [10,11,16,17]. The algorithms proposed in Ref. [10] uses backup multiplexing. Two algorithms are presented, primary dependent backup wavelength assignment (PDBWA) and primary independent backup wavelength assignment (PIBWA). While PDBWA assigns the same wavelength to a primary and its backup lightpath, PIBWA does not impose such restrictions on wavelength assignments. Both the algorithms are pro-active and use failure independent path based restoration. The main idea here is to choose the primary-backup lightpath pair that requires the minimum wavelength channels. Results show that the usefulness of backup multiplexing increases as the network connectivity increases. In Ref. [11], primary-backup multiplexing is used to reduce the blocking probability. This is also pro-active path based restoration approach. Here, the objective is to improve the average call acceptance ratio while allowing an acceptable reduction in the restoration guarantee. In this work, a wavelength channel is allowed to be shared by a primary lightpath and one or more backup lightpaths. In Ref. [17], two on-line RWA algorithms are presented— static method and dynamic method. The static method is used to establish primary and backup lightpaths such that once a route and wavelength have been chosen, they are not allowed to change. On the other hand dynamic method allows for rearrangement of backup lightpaths, i.e. both route and wavelength chosen for a backup path can be shifted to accommodate a new request. Both the methods are based on dedicated path protection scheme and in both the methods primary paths are not allowed to rearrange. Contrary to intuition, the results show that static strategy performs better than dynamic strategy in terms of number of connection requests satisfied for a given number of wavelengths. In Ref. [16], a dynamic rerouting scheme in case of fault occurrence for WDM all-optical networks was proposed. Recently, there has also been considerable interest in carrying IP over WDM networks in an efficient manner. This is because the rapid pace of developments in WDM technology is now beginning to shift the focus more toward optical networking and network level issues. Survivability provisioning in optical multi protocol label switching (MPLS) networks is considered in Ref. [18]. In Ref. [19], some methods to detect and isolate faults such as fiber cuts and router failures have been proposed. In Ref. [20], supporting three classes of service, viz. full protection, no protection, best-effort protection are presented. Two approaches in the best-effort are considered: (1) all connections are accepted and the network tries to protect as many connections as possible, (2) a mix of unprotected and protected connections are accepted and the goal is to maximize the revenue. A comprehensive survey of the restoration schemes available in the literature can be found in Refs. [21 –23]. Recently there has also been considerable interest in providing reliable connections in optical WDM networks. The problem of providing reliable connections in optical ring networks is considered in Refs. [24,25]. Here, in Refs. [24,25], each connection is assigned a maximum failure probability (MFP). The problem of providing the service differentiation is achieved through the primarybackup multiplexing [11]. The lower class connections are assigned protection wavelengths used by the higher class connections. The objective is to find the routes and wavelengths used by the lightpaths in order to minimize the ring total wavelength mileage, subject to guaranteeing the MFP requested by the connection, i.e. problem is considered as provisioning problem. In Refs. [26,27], the problem of providing the service differentiation is achieved through the concept of partial backup lightpaths. Here, the objective is to minimize the blocking probability for a given number of wavelengths and fibers. In this work, we concern ourself with providing various levels of fault-tolerance, availability, delay, and bandwidth for different connections as requested, in a resource efficient manner. This and various other facts discussed in Section 3 motivate us towards our work. 3. Motivation In the emerging next-generation transport networks, called intelligent optical networks, DWDM (Dense WDM)-based optical components like add-drop multiplexers (ADMs) and optical cross connects (OXCs) will have full knowledge of the wavelengths in the network, status, and traffic carrying capacity of each wavelength. With such intelligence, these intelligent optical networks could create self-connecting and self-regulating connections on-the-fly. The facts that motivated us to take C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 bandwidth, delay, fault-tolerance, and availability into QoS parameters are † Although there is an increase in demand for bandwidth, optical transport networks also have to cater to clients who still require only a fraction of wavelength capacity (DS-1, DS-3, OC-3, OC-12, 10 Mbps Ethernet, 200 Mbps ESCON). This poses a bandwidth granularity gap between the electronic and optical domain. In addition, for networks of practical size, the number of available wavelengths is still lower by a few orders of magnitude than the number of source –destination pairs that need to be connected. So given the different types of clients carried in a typical transport network, this wavelength-per-connection approach quickly lead to wavelength exhaust problem and is, therefore, not scalable. Instead, it is much more efficient and more cost effective to aggregate or multiplex lower rate clients into a single, higher capacity wavelength channel. Such techniques have been termed as traffic grooming [28 –31] or sub-rate multiplexing or subwavelength multiplexing. In Ref. [31], an efficient graph theoretic model has proposed to solve the static RWA problem, which optimises the optical layer and electrical layer jointly. † Eventhough sub-rate multiplexing (traffic grooming) allows us to use bandwidth more efficiently, some services (like virtual private network) may require dedicated wavelength. † Delay becomes unbounded as the load approaches the link capacity, delay is usually dominated by the most heavily loaded links. Therefore algorithms must attempt to minimize the delay. † As WDM networks carry huge volume of traffic, maintaining a high level of service availability at an acceptable level of overhead is an important issue. It is essential to incorporate fault-tolerance into QoS requirements. The type of applications being deployed across the public Internet today are increasingly mission-critical, whereby business success can be jeopardized by poor performance of the network. It does not matter how attractive and potentially lucrative our applications are if the network does not function reliably and consistently. In such scenarios (explained above) optical transport networks will not be a viable alternative unless they can guarantee a predictable bandwidth (wavelength), faulttolerance, availability, and delay (response time), to users. Widely scattered users of the network do not usually care about the network topology and implementation details. What they care about is something fundamental, such as † Do I get services with guaranteed timeliness and faulttolerance with an acceptable restoration time at an acceptable level of overhead. 277 † Do I get acceptable response times when I access my mission critical applications from a remote location or server. † Do I have certain reliability and security to my data passing through the network. † Do I have my connection available when I want to access mission critical applications from a remote location. Class of Service (CoS)/QoS aims to ensure that missioncritical traffic has acceptable performance. In real world where bandwidth (resources like wavelengths) is finite for, distributed real-time multimedia applications such as video conferencing, scientific visualization, virtual reality and distributed real-time control must all vie for scarce resources, CoS/QoS becomes a vital tool to ensure that all applications can coexist and function at acceptable levels of performance. CoS mechanisms reduce flow complexity by mapping multiple flows into a few service levels. Network resources are then allocated based on these service levels, and flows can be aggregated and forwarded according to the service class of the packet. Instead of the fine grain control of QoS, not easily achievable with current technology, CoS applies bandwidth and delay to different classes of network services. CoS easily scales with network expansion. Unlike the previous work, here we are looking at the problem of dynamic establishment of primary and backup lightpaths with different QoS requirements based on the following questions. † How to provide services with guaranteed timeliness and fault-tolerance at an acceptable level of overhead. † How to provide bandwidth, response time, and availability based on different customer requirements. The proposed classification separates different connections in the optical domain by providing lightpaths with different fault-tolerant capabilities (availability and resource utilization) and with different response times to meet the different connection requests and their traffic QoS/CoS requirements. Diverse classes of service are possible depending on the QoS parameters discussed above, of these we consider some of the service classes. Different classes of connections and how they vary with respect to fault-tolerance, bandwidth, availability time, and response time are discussed in Section 4. The two primary measures of dependability are reliability and availability. Reliability of a resource (or component) is the probability that it functions correctly (potentially despite faults) over an interval of time. Whereas, availability of a resource (or component) is the probability that it is being operational at any given instant of time. Availability of a connection is the probability that enough resources reserved for this connection are available to communicate from one node to the other at any given instant of time. A 0.999999 availability, for example, 278 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 Table 1 An example showing dynamic establishment of lightpaths for connection requests Node pair Lightpaths (8, 4) (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l0 22, 8, 3, 4, l1 4, 6, 14, l0 22, 8, 3, 4,… 4, 7, 15, l0 Fig. 1. An example network. 4. Different classes of connections means that a system is not operational at most 1 h in every million hours. Whereas, 0.999999 reliability for a 10 h mission means the probability of failure during the mission may be at most 1026. 3.1. Network model Consider a wide area WDM based intelligent transport network with 24 wavelength routed nodes as shown in Fig. 1. We assume each node is equipped with enough number of transmitters and receivers. The edge devices (access nodes) at the border of the transport network provide the interface (electronic – optical, optical – electronic conversion and electronic buffering when contention arises for a lightpath) to the end users, which may be branch offices (or regional networks) that feed into the WDM based intelligent optical transport network. The reasons that motivated us to take this network model are † As all-optical wavelength conversion and all-optical grooming devices are not commercially available presently, we resort to use electronic methods of implementation to incorporate these features into the network. † It is very likely that networks of near-future will employ a hybrid, layered architecture, using both electronic switching and wavelength routing technologies. Example. Consider the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. It is required to establish lightpaths between node pairs (8, 4), (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), and (4, 15). Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the requests as shown in Table 1. Here, the wavelength assignment algorithm uses the first free wavelength for the chosen route. Lightpaths p0 ; p1 ; p2 ; p4 ; and p6 use wavelength l0 and p5 uses l1 . As a result, no lightpath can be established for sixth node pair (22, 4), as the route for this node pair is not wavelengthcontinuous. In this section, we describe different heuristic algorithms to establish different connection requests, which differ from each other in the number and type of primary and backup lightpaths. The number of backup lightpaths determines the level of fault-tolerance and availability required by the connection. The type of lightpath determines the response times and bandwidth required by the connection. Depending on the routing policy and wavelength assignment policy used, different RWA algorithms are possible. The order in which the selection of routes and wavelengths are made does matter. These two methods can be used in any order one after the other or jointly. In our work, we use FR and modified fixed wavelength assignment policy in that order. We use FX wavelength assignment policy because of its simplicity. When a connection request from a source S to a destination D arrives, the algorithm finds all free wavelengths on the predetermined primary path using FX algorithm. Here, wavelengths are not reserved, but the availability of free wavelengths is noted down. If no free wavelength is available, the connection request is rejected. After finding all free wavelengths on the primary path, the algorithm tries to find all the free wavelengths on the predetermined backup path. If no free wavelength is available, the connection request is rejected. After finding all free wavelengths on the primary and the backup paths, the first free wavelength common to both primary and backup path will be chosen and reserved. Our algorithm does not use the wavelength usage factor and thus does not require any global state information. The idea behind using this algorithm is to achieve performance closer to that of the MU algorithm but without requiring any global state information. 4.1. Single dedicated primary and single dedicated backup lightpath In this both primary and backup lightpaths are all-optical and the traffic is carried entirely in the optical domain. Primary and backup lightpaths are called dedicated because primary lightpath will carry exactly one connection request C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 traffic and backup lightpath is not shared between any two (or more) backup lightpaths and acts as cold standby for the corresponding primary lightpath. Since, the traffic is entirely carried in optical domain and is not shared by any other connection request traffic the response times are very low. Since, every lightpath has its own dedicated backup lightpath, it can tolerate single failure. By providing single backup lightpath we can increase the availability of the connection (as explained subsequently through an example). I. Primary route selection. When a connection request from a source S to a destination D arrives, the algorithm finds the shortest path (minimum hop path) using Dijkstra’s shortest path finding algorithm for use as the primary path. II. Backup route selection. For finding backup path all the links along the shortest path are removed, and again the shortest path from source S to the destination D is found for use as the route for backup path using Dijkstra’s shortest path finding algorithm. III. Wavelength assignment for primary and backup paths. When a connection request from a source S to a destination D arrives, the algorithm finds all free wavelengths on the predetermined primary path using modified FX algorithm. Here, wavelengths are not reserved, but the availability of free wavelengths is noted (remembered) down. If no free wavelength is available, the connection request is rejected. After finding all free wavelengths on the primary path, the algorithm tries to find all free wavelengths on the predetermined backup path, again using modified FX algorithm. If no free wavelength is available, the connection request is rejected. After finding all free wavelengths on the primary and the backup paths we study the following two cases Case I. The first free wavelength common to both the primary and backup paths will be chosen and reserved. Note here that we are using PDBWA, because all the backup paths should be on the same wavelength as that of the primary wavelength. There may arise a situation wherein there exist wavelength continuous routes for primary on one wavelength and for the backup path on some other wavelength, but there are no wavelength continuous routes available on the same wavelength for both the primary and backup paths. In such a case, the request is rejected by this method. This is because we assume that the nodes are equipped with only fixed transmitters and receivers. Case II. In this case there is no restriction on the use of wavelength for primary and backup paths. Therefore the best possible primary-backup lightpath pair can be chosen to satisfy the request. Note here that we are using PIBWA, because backup path may be on different wavelength than that of primary wavelength. This method has the advantage of better network performance. But it assumes that the nodes are equipped with tunable transmitters and receivers. Example. Consider again the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. Now, it is required to establish primary and 279 Table 2 An example showing dynamic establishment of lightpaths for SDPSDB – Case I connection requests Node pair Primary lightpaths Backup lightpaths (8, 4) (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 22, 8, 3, 4, l1 4, 6, 14, l0 22, 8, 3, 4,… 4, 7, 15,… 12, 13, 14,… 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 22, 17, 7, 4, l1 4, 12, 13, 14, l0 22, 17, 7, 4,… 4, 6, 15,… 12, 6, 14,… backup lightpaths between node pairs (8, 4), (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), (4, 15), and (12, 14). Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the first four requests as shown in Tables 2 and 3 for Case I and Case II, respectively. Here, no lightpath can be established for sixth node pair (22, 4) which came at the end, as the route for this node pair is not wavelength-continuous. 4.1.1. Availability of the connection with single backup lightpath Availability of a resource (or component) is the probability that it is being operational at any given instant of time. Availability of a connection is the probability that enough resources reserved for this connection are available to communicate from one node to the other at any given instant of time. Availability has a range from 0 (never available) to 1 (always available). It is assumed (with reasonable justification) that availability comes at cost. Therefore, a more available connection comes at a greater cost. However, the relation between cost and availability may not be linear. For simplicity we assume nodes are available at all times, i.e. only links are prone to faults and all the wavelength channels on a link are assumed to have the same availability. The subsequent discussion can be easily extended to include node failures also. We now find the availability of a composite path with a primary and a partial or end-to-end backup paths. Consider a connection Table 3 An example showing dynamic establishment of lightpaths for SDPSDB – Case II connection requests Node pair Primary lightpaths Backup lightpaths (8, 4) (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 22, 8, 3, 4, l1 4, 6, 14, l0 22, 8, 3, 4,… 4, 7, 15, l1 12, 13, 14,… 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 22, 17, 7, 4, l0 4, 12, 13, 14, l0 22, 17, 7, 4,… 4, 6, 15, l1 12, 6, 14,… 280 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 much less than the availability that can be obtained with backup path. 4.2. Single dedicated primary and multiple dedicated backup lightpaths Fig. 2. An example used to calculate the availability of a composite path with primary and backup. from the source to the destination shown in Fig. 2 with partial backup lightpath. The availability of a segment consisting of links with availabilities a1 ; a2 ; …an will be Qn i¼1 ai : Let ap denote the availability of the primary lightpath, as denote that of the primary segment which is covered by a backup lightpath, ab that of the backup lightpath, acp that of the composite path comprising of primary and partial backup lightpaths, and acf that of the composite path comprising of primary and end-to-end Q backup lightpaths. Here, ap ¼ 7i¼1 ai , as ¼ a3 a4 a5 and ab ¼ a8 a9 a10 . Now ac ¼ (availability of part of primary lightpath not covered by the backup lightpath) £ (availability of primary segment and partial backup lightpath together) acp ¼ ap ða þ ab ð1 2 as ÞÞ as s ð1Þ Now, consider the connection shown in Fig. 3, using end-toend backup lightpath. Since, entire primary lightpath is covered by backup lightpath, availability of the primary segment is equal to availability of the primary lightpath, as ¼ ap : Now the availability of composite lightpath is acf ¼ ap þ ab ð1 2 ap Þ ð2Þ Now consider a numerical example with Fig. 3 and assume that the availability of each of the links is 0.9800. The availability of backup lightpath (in this case which has same number of links as primary lightpath), ab ¼ 0:8681: Then using Eq. (2), we calculate acf ¼ 0:9826; which is much more than the availability that can be obtained by only primary path. Now, consider the same connection shown in Fig. 3, using only primary (i.e. no-backup) lightpath. In this case, the composite availability ac ¼ ap ¼ 0:8681; which is Fig. 3. An example showing how backup will improve the availability of the SDPSDB connections. In this both primary and all k backup lightpaths are alloptical and the traffic is carried entirely in the optical domain. All k backup paths being dedicated will carry exactly one connection traffic and act as cold standby for the corresponding primary lightpath. Since we are using kdisjoint paths for backup paths, it guarantees on k failures. Instead, if we use k-shortest paths then we may not give guarantee on k failures. But, in any case by having multiple backup lightpaths (either k-disjoint paths or k-shortest paths), we can further increase the availability of the connection (as explained subsequently through an example) compared to single backup lightpath. This will be the most expensive Class of service and can be allotted to connections which requires highest QoS in terms response time, availability and fault-tolerance for multiple failures, and bandwidth. I. Primary route selection. Same as single dedicated primary and single dedicated backup (SDPSDB) primary route selection. II. Backup route selection. For finding jth backup route for a connection request from source S to destination D all the links and intermediate nodes along the primary and all j 2 1 backup paths are removed, then the shortest path is found. The resulting path is the jth shortest disjoint path for the connection request. Here, k is a parameter and depends on the connection requirement. By providing multiple backup lightpaths for a primary lightpath availability of the connection can be increased as explained latter in an example. III. Wavelength assignment for primary and backup paths. After finding all free wavelengths on the primary and the backup paths as explained in SDPSDB, here also we study the following two cases: Case I. The first free wavelength common to the primary and all the k backup paths will be chosen and reserved. If no free wavelength is available on any of the k backup paths the connection request is rejected. Case II. Here, there is no restriction on availability of the same wavelength along the primary and k backup paths (i.e. any free wavelength along the route can be used). Example. Consider the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. Now, it is required to establish primary and multiple backup lightpaths between node pairs (8, 4), (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), (4, 15), and (12, 14). Let number of backup paths ðkÞ required by the connections are 2. Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the first four requests as shown in Tables 4 and 5 for Case I and Case II, respectively. C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 281 Table 4 An example showing dynamic establishment of lightpaths for SDPSDB– Case I connection requests Node pair Primary lightpaths Backup lightpath 1 Backup lightpath 2 (8, 4) (15, 6) (8, 12) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 (22, 4) 22, 8, 3, 4,… 22, 17, 7, 4,… (4, 14) (22, 4) 4, 6, 14,… 22, 8, 3, 4,… 4, 12, 13, 14,… 22, 17, 7, 4,… (4, 15) (12, 14) 4, 7, 15, l1 12, 13, 14,… 4, 6, 15, l1 12, 6, 14,… 8, 7, 4,l0 15, 14, 6, l0 8, 9, 1, 5, 10, 12, l1 22, 23, 24, 9, 1, 5, 4,… 4, 7, 15, 14,… 22, 23, 24, 9, 1, 5, 4,… 4, 3, 16, 15, l1 12, 4, 7, 15, 14,… 4.2.1. Availability of the connection with multiple backup lightpaths Consider the connection shown in Fig. 4, using two disjoint backup lightpaths. Assume the availability of each of the links as 0.9800. Here, primary lightpath is fully covered by backup lightpath 1. The composite availability of the primary lightpath and backup lightpath 1 (using Eq. (1)) is 0.9826. Since backup lightpath 2 is completely disjoint and fully covers primary and backup lightpath 1, again using Eq. (1), the composite availability of the complete connection is 0.9969, which is much more than the availability that can be obtained with only one backup path. 4.3. Single dedicated primary and single shared backup lightpath In this also both primary and backup lightpaths are alloptical and the traffic is carried entirely in the optical domain. But, here the primary path is dedicated and will carry exactly one connection request traffic. Whereas, backup lightpath is shared between any two (or more depending on connection bandwidth and response time requirement) backup lightpaths and acts as cold standby for Table 5 An example showing dynamic establishment of lightpaths for SDPMDB– Case II connection requests Node pair Primary lightpaths Backup lightpath 1 Backup lightpath 2 (8, 4) (15, 6) (8, 12) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 (22, 4) 22, 8, 3, 4, l1 22, 17, 7, 4, l1 (4, 14) (22, 4) 4, 6, 14,… 22, 8, 3, 4,… 4, 12, 13, 14,… 22, 17, 7, 4,… (4, 15) (12, 14) 4, 7, 15,… 12, 13, 14,… 4, 6, 15,… 12, 6, 14,… 8, 7, 4,l0 15, 14, 6, l0 8, 9, 1, 5, 10, 12, l0 22, 23, 24, 9, 1, 5, 4, l1 4, 7, 15, 14,… 22, 23, 24, 9, 1, 5, 4,… 4, 3, 16, 15,… 12, 4, 7, 15, 14,… Fig. 4. An example showing how multiple backups further improve the availability of the SDPMDB connections. the corresponding primary lightpath. Because backup lightpaths are shared among multiple connections, during failure recovery period this class of connections will experience additional delay (queueing delay) at the access nodes and will get less bandwidth. As far as availability and fault-tolerance are concerned it is same as SDPSDB. Note, here sharing of backup paths is different from backup multiplexing. Backup multiplexing insists on the link disjointness of the primaries whose backup paths can share a wavelength channel. I. Primary route selection. Same as SDPSDB primary route selection. II. Backup route selection. Same as SDPSDB backup route selection. III. Wavelength assignment for primary and backup paths. Here also we consider the two cases as in SDPSDB. Case I. For all free wavelengths along the primary path, check whether the same wavelength along the backup path can be shared with any other backup path; if yes reserve that wavelength along the primary and mark it for sharing along the backup path. If no such wavelength (which satisfies the condition) is available then reserve first common free wavelength along both primary and backup paths. Otherwise, reject the connection request. Case II. Check whether any wavelength along the backup path can be shared with any other backup path. If yes, reserve the first free wavelength along the primary path. And mark for sharing, the wavelength that can be shared along the backup path. If no such wavelength (which satisfies the condition) is available then reserve first free wavelength along the primary. And mark for sharing the first free wavelength along the backup path. Otherwise, reject the connection request. Example. Consider the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. Now, it is required to establish single dedicated primary and single shared backup (SDPSSB) backup lightpaths between node pairs (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), (4, 15), and (12, 14). Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the first four requests as shown in Tables 6 and 7 for Case I and Case II, respectively. 282 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 Table 6 An example showing dynamic establishment of lightpaths for SDPSSB– Case I connection requests Table 8 An example showing dynamic establishment of lightpaths for SSPSSB– Case I connection requests Node pair Primary lightpaths Backup lightpaths Node pair Primary lightpaths Backup lightpaths (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 15, 6, l0 8, 2, 4, 12, l1 22, 8, 3, 4, l0 4, 6, 14, l0 22, 8, 3, 4, l1 4, 7, 15,… 12, 13, 14,… 15, 7, 6, l0 8, 7, 6, 12, l1 22, 17, 7, 4, l0 4, 12, 13, 14, l0 22, 17, 7, 4, l1 4, 6, 15,… 12, 6, 14,… (8, 4) (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 22, 8, 3, 4, l1 4, 6, 14, l0 22, 8, 3, 4, l1 4, 7, 15,… 12, 13, 14,… 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 22, 17, 7, 4, l1 4, 12, 13, 14, l0 22, 17, 7, 4, l1 4, 6, 15,… 12, 6, 14,… 4.4. Single shared primary and single shared backup lightpath In this also both primary and backup lightpaths are all-optical and the traffic is carried entirely in the optical domain. In this class primary and backup lightpaths are shared between any two lightpaths (or more depending on the connections bandwidth and response time requirement). Because primary and backup lightpaths are shared among multiple connections this class of connections will experience additional delay (queueing delay) at the access nodes and will get less bandwidth. As far as fault-tolerance and availability are concerned it is same as SDPSDB. I. Primary route selection. Same as SDPSDB primary route selection. II. Backup route selection. Same as SDPSDB backup route selection. III. Wavelength assignment for primary and backup paths. Here also we consider the two cases as in SDPSDB. Case I. All the wavelengths are indexed and searched in the order of their index numbers. The first common wavelength along both the primary and backup paths that can be shared among other connections (either primary or backup) is chosen and marked for sharing. If no such wavelength is available, then in increasing order of index, the wavelength that can share with other connections along backup path is taken and is checked whether the same wavelength is free on the primary; if free, reserve it along Table 7 An example showing dynamic establishment of lightpaths for SDPSSB– Case II connection requests Node pair Primary lightpaths Backup lightpaths (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 15, 6, l0 8, 2, 4, 12, l0 22, 8, 3, 4, l0 4, 6, 14, l0 22, 8, 3, 4, l1 4, 7, 15, l1 12, 13, 14,… 15, 7, 6, l0 8, 7, 6, 12, l1 22, 17, 7, 4, l0 4, 12, 13, 14, l1 22, 17, 7, 4, l0 4, 6, 15, l1 12, 6, 14,… the primary and mark it sharable backup paths. If such a wavelength is not available then the first free wavelength common to both the primary and backup path will be chosen and reserved. If no common free wavelength is available, then reject the connection request. Case II. In this case the best possible primary-backup lightpath pair that can be shared among other connections (either primary or backup) is chosen to satisfy the request. That is we use PIBWA because backup path may be on different wavelength than that of primary wavelength. Example. Consider the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. Now, it is required to establish single shared primary and single shared backup (SSPSSB) lightpaths between node pairs (8, 4), (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), (4, 15), and (12, 14). Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the first four requests as shown in Tables 8 and 9 for Case I and Case II, respectively. 4.5. Single shared primary and multiple shared backup lightpaths In this also both the primary and backup lightpaths are all-optical and the traffic is carried entirely in the optical domain. In this class primary and all k backup lightpaths are shared between any two lightpaths (or more depending on the connections bandwidth and response time requirement). Because primary and backup lightpaths are shared among Table 9 An example showing dynamic establishment of lightpaths for SSPSSB– Case II connection requests Node pair Primary lightpaths Backup lightpaths (8, 4) (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 22, 8, 3, 4, l1 4, 6, 14, l0 22, 8, 3, 4, l1 4, 7, 15, l1 12, 13, 14,… 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 22, 17, 7, 4, l0 4, 12, 13, 14, l0 22, 17, 7, 4, l0 4, 6, 15, l1 12, 6, 14,… C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 multiple connections this class of connections will experience additional delay (queueing delay) at the access nodes and will get less bandwidth. As far as fault-tolerance and availability are concerned this is same as single dedicated primary and multiple dedicated backups SDPMDB. I. Primary route selection. Same as SDPSDB primary route selection. II. Backup route selection. Same as SDPMDB backup route selection. III. Wavelength assignment for primary and backup paths. Here also we consider the two cases as in SDPSDB. Case I. The first common wavelength along the primary and k backup paths that can share among other connections (either primary or backup) is chosen. If no such wavelength is available, then take in increasing order of index, the common wavelength among k backups that can share with other connections and check whether the same wavelength is free on the primary, if free, mark it as sharable along the primary and k backup paths. If such a wavelength is not available then the first free wavelength common to the primary and k backup paths will be chosen. Otherwise, reject the connection request. Case II. In this case the best possible primary and k backup lightpaths which share among other connections (either primary or backup) is chosen to satisfy the request. In this case there is no restriction on the use of wavelength for primary and k backup paths, i.e. k backup paths may be on different wavelengths than that of primary wavelength. If not reserve the first free wavelengths along the primary and k backup paths. If no free wavelength available reject the connection request. Example. Consider the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. Now, it is required to establish single shared primary and multiple shared backup (SSPMSB) lightpaths between node pairs (8, 4), (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), (4, 15), and (12, 14). Let number of backup paths ðkÞ required by the connections are 2. Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the first four requests as shown in Tables 10 and 11 for Case I and Case II, respectively. 4.6. Single dedicated multi-hop primary and single dedicated multi-hop backup lightpaths In this both primary and backup lightpaths are multi-hop lightpaths (depending on the availability of resources). That is, a message may reach its destination via one hop or it may be routed via a multi-hop path with opto-electronic conversions and processing at intermediate nodes. This incurs additional delay due to electronic –optical, optical – electronic conversions at junction of two lightpaths. This class of connections assume that nodes are equipped with tunable transceivers. I. Primary route selection. Same as SDPSDB primary route selection. 283 Table 10 An example showing dynamic establishment of lightpaths for SSPMSB– Case I connection requests Node pair Primary lightpaths Backup lightpath 1 Backup Lightpath 2 (8, 4) (15, 6) (8, 12) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 (22, 4) 22, 8, 3, 4,… 22, 17, 7, 4,… (4, 14) (22, 4) 4, 6, 14,… 22, 8, 3, 4,… 4, 12, 13, 14,… 22, 17, 7, 4,… (4, 15) (12, 14) 4, 7, 15, l1 12, 13, 14,… 4, 6, 15, l1 12, 6, 14,… 8, 7, 4,l0 15, 14, 6, l0 8, 9, 1, 5, 10, 12, l1 22, 23, 24, 9, 1, 5, 4,… 4, 7, 15, 14,… 22, 23, 24, 9, 1, 5, 4,… 4, 3, 16, 15, l1 12, 4, 7, 15, 14,… II. Backup route selection. Same as SDPSDB backup route selection. III. Wavelength assignment for primary and backup paths. Check any wavelength is free along the primary and backup paths. If on some link no free wavelength is available reject the connection. Otherwise, the first free wavelength along the primary and backup paths (may not be same) is chosen and reserved. If free wavelengths are not available along the complete paths, then take in increasing order of free wavelengths on the first link of the paths and reserve the wavelength, which results in maximum wavelength continuous path. Do it recursively for complete path. Example. Consider the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. Now, it is required to establish multi-hop primary and backup lightpaths between node pairs (8, 4), (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), (4, 15), and (12, 14). Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the requests as shown in Table 12. Table 11 An example showing dynamic establishment of lightpaths for SSPMSB– Case II connection requests Node pair Primary lightpaths Backup lightpath 1 Backup lightpath 2 (8, 4) (15, 6) (8, 12) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 (22, 4) 22, 8, 3, 4, l1 22, 17, 7, 4, l1 (4, 14) (22, 4) 4, 6, 14,… 22, 8, 3, 4, l1 4, 12, 13, 14,… 22, 17, 7, 4, l1 (4, 15) (12, 14) 4, 7, 15,… 12, 13, 14,… 4, 6, 15,… 12, 6, 14,… 8, 7, 4,l0 15, 14, 6, l0 8, 9, 1, 5, 10, 12, l0 22, 23, 24, 9, 1, 5, 4, l1 4, 7, 15, 14,… 22, 23, 24, 9, 1, 5, 4, l1 4, 3, 16, 15,… 12, 4, 7, 15, 14,… 284 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 Table 12 An example showing dynamic establishment of lightpaths for SDMPSDMB connection requests Table 13 An example showing dynamic establishment of lightpaths for SSMPSSMB connection requests Node Pair Primary Lightpaths Backup Lightpaths Node pair Primary lightpaths Backup lightpaths (8, 4) (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l1 22, 8, 3, 4, l1 4, 6, 14, l0 22, 8, 3, 4,… 4, 7, 15, l1 12, 13, 14, l1 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l1 22, 17, 7, 4, l0 4, 12, 13, 14, l0 22, 17, 7, 4,… 4, 6, 15, l1 12, 6, l0 , 14, l1 (8, 4) (15, 6) (8, 12) (22, 4) (4, 14) (22, 4) (4, 15) (12, 14) 8, 3, 4, l0 15, 6, l0 8, 2, 4, 12, l0 22, 8, 3, 4, l0 4, 6, 14, l0 22, 8, 3, 4, l0 4, 7, 15, l0 12, 13, 14, l0 8, 2, 4, l0 15, 7, 6, l0 8, 7, 6, 12, l0 22, 17, 7, 4, l0 4, 12, 13, 14, l0 22, 17, 7, 4, l0 4, 6, 15, l0 12, 6, 14, l0 4.7. Single shared multi-hop primary and single shared multi-hop backup lightpaths In this both primary and backup lightpaths are multi-hop lightpaths (depending on the availability of resources). That is, a message may reach its destination via one hop or it may be routed via a multi-hop path with opto-electronic conversions and processing at intermediate nodes. In this class of connections delay is due to electronic –optical, optical – electronic conversions at junction of two lightpaths and also due queueing delay. This class of connections also expects that nodes be equipped with tunable transceivers. I. Primary route selection. Same as SDPSDB primary route selection. II. Backup route selection. Same as SDPSDB backup route selection. III. Wavelength assignment for primary and backup paths. When a connection request from a source S to a destination D arrives, the algorithm finds the first sharable wavelength (i.e. the wavelength for which sharing limit is not crossed) on the predetermined primary and backup paths using modified FX algorithm. If no sharable wavelength is available, on a particular link of either primary or backup path, algorithm searches for first free wavelength on that particular link. If no free wavelength is available on a particular link, then the connection is rejected. Example. Consider the network shown in Fig. 1. Assume that two wavelengths l0 and l1 per fiber is available. Now, it is required to establish multi-hop primary and backup lightpaths between node pairs (8, 4), (15, 6), (8, 12), (22, 4), (4, 14), (22, 4), (4, 15), and (12, 14). Assuming that the requests arrive in the same order as given here, a dynamic RWA algorithm establishes lightpaths to the requests as shown in Table 13. 5. Simulation results and discussion In this section, first we present simulation model and assumptions and then discuss the results obtained from the simulation experiments. In the discussion below, W denotes number of wavelengths on each fiber, F denotes number of fibers per physical link, k denotes number of backup paths, S is the sharing limit (i.e. maximum number of connection requests that can share the lightpath between a node pair, B denotes the blocking probability, and SPWU denotes the spare wavelength utilization. 5.1. Simulation details We studied our proposed classification (described in Section 4) by carrying out extensive simulation experiments on the 24 node regional network (Fig. 1). The implementation was in Cþ þ , running under Linux on a Pentium-II 800 MHz. For the above network, we consider the physical links having single-fiber and multi-fibers. Lightpaths are assumed to be bidirectional, and all the links are assumed to have same number of fibers. All the fibers are assumed to have same number of wavelengths. The delay of each link was set to one unit. The connections are requested between node pairs chosen randomly, with a condition that any node is chosen with the same probability. All the primary and backup paths are computed as explained in Section 4. The primary and backup wavelength assignments are done as explained in Section 4. In simulation experiments we consider incremental traffic as in Ref. [17]. In incremental traffic once a connection is admitted, the primary and backup lightpaths stay till the end of simulation. In each simulation experiment, given number of connections requests are generated one after the other, and the results are averaged over many simulation experiments. At any time, if a connection request cannot be satisfied using the heuristics, the connection request is rejected. All simulation results are for S ¼ 3 unless, otherwise, specified. Because of space limitations we have not shown results for varying k and S values. We have also obtained results for other networks, which are similar and hence are not shown. The network shown in Fig. 1 do not have two end-to-end disjoint backup paths for 107 node pairs. In our simulation studies we added some links to the network, so that every node pair will have two backup paths and the network is shown in Fig. 5. After adding the links, we study the effect of number of wavelengths available on the blocking probability and spare wavelength utilization. In the discussion below we C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 (b) Fig. 5. An example network after adding some links. call the network without adding links is called as old network and the network after adding links is called as new network. (c) (d) 5.2. Results and discussion The performance metrics used are blocking probability and the spare wavelength utilization. The effect of design parameters such as, F; W; k, and S on the performance metrics for different networks are studied. The results are shown in Figs. 6 –21. We now give a detailed analysis of the results. In Figs. 6– 13 the blocking probability is plotted for various number of wavelengths and fibers for all the Classes. The following observations can be made. (a) The blocking probability is high for Case I wavelength assignment compared to Case II wavelength (e) (f) 285 assignment for all the Classes. It is because the chances of finding a common free wavelength on the primary and backup paths is less compared to finding one free wavelength on the primary and other free wavelength on backup paths. The blocking probability of Class II and Class V is high compared to all other Classes. This is because of requirement of multiple backup paths. As each connection of this class requires multiple backup lightpaths, the resources reserved for each connection will be more. So, the chances of finding a free wavelength for future connections will be less. The blocking probability of Class II and Class V is high for old network compared to new network. For old network many source –destination pairs do not have multiple backup paths leading to higher blocking probability. For a given number of wavelengths (or fibers) as the number of connections increases, the blocking probability increases. As the number of connections increases the number of wavelengths reserved for primary and backup paths increases reducing the chances of acceptance for future connections. For a given number of wavelengths as the number of fibers increases, the blocking probability decreases. As the number of fibers increases the chances of finding the common free wavelength on all the links along the route increases, as it can choose the free wavelength on any of the fibers connecting a node pair. For a given number of connections as the number of wavelengths increases, the blocking probability decreases. It is also because of the same reason as explained above, but, the decrease in blocking Fig. 6. Single-fiber Case I blocking probability results for old network. 286 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 Fig. 7. Single-fiber Case II blocking probability results for old network. probability is not sharp as in case of increase in number of fibers (because we still have wavelength continuity constraint). (g) For a given number of connections as the number of fibers increases, the blocking probability decreases. As the number of fibers increases the chances of finding the same wavelength free on all the links along the route increases, as it can choose the free wavelength on any of the fibers connecting a node pair. (h) The relation between blocking probabilities of different Classes is b2 . b5 . b1 . b3 . b4 . b6 ; where bi (i) denotes the blocking probability of Class I. This relation holds for both Case I wavelength assignment and Case II wavelength assignment. This we observed from the simulation results and can be easily deduced from the above explanation. As the hot-pair percentage increases the blocking probability of Class III, Class IV, and Class V decreases. Because in all these classes some of the wavelengths can be shared by more number of connections. In other words, the effect of sharing increases as the hot-pair percent increases. As Fig. 8. Two and three fibers Case I blocking probability results for old network. C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 287 Fig. 9. Two and three fibers, Case II blocking probability results for old network. (j) the sharing limit increases the blocking probability of Class III, Class IV, Class V, and Class VI decreases. As the number of connections allowed to share a wavelength increases, remaining resources can be used for future connections. As the number of backup lightpaths ðkÞ required increases the blocking probability increases in case of Class II and Class V. As the number of backup paths required increases number of wavelengths reserved for a connection also increases, reducing the chances of finding a common free wavelength for future connections. 2. Figs. 14– 21 show the spare wavelength utilization for various number of wavelengths and fibers for all the Classes. The following observations can be made. (a) The spare wavelength utilization is high for Case II wavelength assignment compared to Case I wavelength assignment for all the Classes. As the Class I Fig. 10. Single-fiber Case I blocking probability results for new network. 288 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 Fig. 11. Single-fiber Case II blocking probability results for new network. wavelength assignment demands same wavelength to be assigned for both the primary and backup paths, the number of accepted connections in Case I will be less compared to Case II. Since, the number of accepted connection is more in case of Case I, the spare wavelengths reserved will be more. (b) The spare wavelength utilization of Class II and Class V is high compared to all other Classes. As the number of backup lightpaths required for these classes are more, more backup wavelengths need to be reserved leading to higher spare wavelength utilization compared to other classes, i.e. as the number of backup lightpaths required ðkÞ increases the spare wavelength utilization increases. (c) As the sharing limit increases the spare wavelength utilization of Class III, Class IV, Class V, and Class VI decreases. As the number of connections allowed to share a wavelength increases number of wavelengths reserved for backup lightpaths also decreases. Fig. 12. Two and three fibers Case I blocking probability results for new network. C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 289 Fig. 13. Two and three fibers Case II blocking probability results for new network. (d) As the hot-pair percentage increases the spare wavelength utilization of Class III, Class IV, and Class V decreases. This is because, the effect of sharing increases as the hot-pair percent increases. (e) For a given number of connections as the number of wavelengths increases, the spare wavelength utilization increases. For a given number of connections as the number of fibers increases, the spare wavelength utilization increases. As the number of fibers increases the chances of finding the same wavelength free on all the links along the route increases, as it can choose the free wavelength on any of the fibers connecting a node pair. So, more number of connection will be accepted leading to more spare wavelength utilization. 6. Conclusions and future work In this paper, we studied different classes of connections over WDM optical networks based on level of faulttolerance required, availability of the connection, response Fig. 14. Single-fiber Case I spare wavelength utilization results for old network. 290 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 Fig. 15. Single-fiber Case II spare wavelength utilization results for old network. time, and bandwidth. The effectiveness of different classes has been evaluated using extensive simulation experiments on 24 node regional network. The proposed classification helps in providing better QoS guarantees on response time, availability of the connection, and bandwidth. Further, the proposed classification is highly flexible to control the level of fault-tolerance of each connection, independently of other connections, to reflect its criticality. Comparison of different classes of connections is given in Table 14. In general the response time of the dedicated lightpaths will be less compared to the shared lightpaths because of queuing delays in shared lightpaths. The bandwidth reserved for the dedicated lightpaths will be a complete wavelength and for shared lightpaths it depends on the sharing limit. Connections with single backup lightpaths can tolerate a single failure and with k backup lightpaths tolerate can tolerate up to k number of failures. The availability of the connections increases with the number of backup lightpaths. Connection requests with more number of backup lightpaths need to pay more for the service they get. As the number of backup lightpaths increases the pay for the service also increases. The connection requests, which require more number of backup lightpaths reserve more Fig. 16. Two and three fibers Case I spare wavelength utilization results for old network. C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 291 Fig. 17. Two and three fibers Case II spare wavelength utilization results for old network. number of wavelengths for backup lightpaths, so the spare wavelength utilization for these connections will be more. As more number of wavelengths are reserved for these connections finding a common free wavelength for future connections will be difficult, so the blocking probability is more. Applications/end users differ in their willingness to pay for a service, which provides guarantees on faulttolerance, availability, bandwidth, and response time. Considering the requirements of different applications/ end users it is essential for service provider to provide services with different levels of fault-tolerance, availability, bandwidth, and response time. The end user depending on the application requirements chooses the QoS parameters needed. For one application faulttolerance may be critical than other parameters and for some other application fault-tolerance may not be important, but, the delay and bandwidth are important. The classification given in Section 4 does not include multiple primary paths. If a certain connection requires multiple primary lightpaths ðmÞ to be established (1) find k þ m-disjoint paths as in SDPSSB or SSPMSB (depending on response time and bandwidth), (2) reserve wavelengths Fig. 18. Single-fiber Case I spare wavelength utilization results for new network. 292 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 Fig. 19. Single-fiber Case II spare wavelength utilization results for new network. along m primary paths, (3) reserve wavelengths along k backup paths. In SDPMDB and SSPMSP, we can find kshortest paths to reduce the spare wavelength utilization. But, we choose k-disjoint paths, because it can guarantee recovery up to k failures simultaneously. In all cases we reserved only one wavelength per connection. However, if certain connection request requires more bandwidth, then we can assign two or more wavelengths to it. In this paper, we have not considered the backup multiplexing and primary-backup multiplexing for low rate clients. These multiplexing techniques can be combined with sharing technique to further increase the efficiency in bandwidth utilization. In this paper we have taken the performance metrics as blocking probability and spare wavelength utilization. The performance metric delay also becomes important, as (1) the load on the link approaches link capacity (example, shared lightpaths) and (2) the number of opto-electronic – optical conversions increases (example, multi-hop lightpaths) when actually routing the traffic and need to be studied. Fig. 20. Two and three fibers Case I spare wavelength utilization results for new network. C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 293 Fig. 21. Two and three fibers Case II spare wavelength utilization results for new network. Table 14 Comparison among different classes of connections Connection type QoS parameters Pay for service Remarks Response time Bandwidth Fault-tolerance Service availability SDPSDB Low Tolerates single failure High High Only propagation delay (dp ) SDPMDB Low Tolerates k failures Highest Highest SDPSSB Low Tolerates single failure High Medium Can use some of the backups for FEC During failures medium response times SSPSSB Medium Tolerates single failure High Lower Queueing delay ðdq Þ þ dp SSPMSB Medium Tolerates k failures Highest Low SDMPSDMB High Tolerates single failure High High SSMPSSMB Highest Full wavelength for primary and backup lightpaths Full wavelength for primary and all backup lightpaths Full wavelength for primary and shared wavelength for backup Shared wavelength for primary and backup paths Shared wavelength for primary and all backup paths Dedicate multi-hop lightpaths for primary and backup paths Shared multi-hop lightpaths for primary and backup paths Tolerates single failure High Lowest Can use some of the backups for FEC Opto-electronic conversion delay ðdc Þ þ dq þ dp dc þ dq þ dp Acknowledgements This work was supported by the Department of Science and Technology, New Delhi, India. References [1] I. Chlamtac, A. Ganz, G. Karmi, Lightpath communications: an approach to high bandwidth optical WANs, IEEE Transactions on Communications 40 (7) (1992) 1171–1182. [2] R. Ramaswami, K.N. Sivarajan, Routing and wavelength assignment in all-optical networks, IEEE/ACM Transactions on Networking 3 (5) (1995) 489–500. [3] A. Mokhtar, M. Azizoglu, Adaptive wavelength routing in all-optical networks, IEEE/ACM Transactions on Networking 6 (2) (1998) 197–206. [4] K. Bala, T. Stern, K. Simchi, Routing in linear lightwave networks, IEEE/ACM Transactions on Networking 3 (4) (1995) 459–469. [5] D. Banerjee, B. Mukherjee, A. Practical, Approach for routing and wavelength assignment in large wavelength routed optical networks, IEEE Journal on Selected Areas in Communications 14 (5) (1996) 903–908. 294 C.V. Saradhi, C.S.R. Murthy / Computer Communications 27 (2004) 273–294 [6] H. Harai, M. Murata, H. Miyahara, Performance of alternate routing methods in all-optical switching networks, Proceedings of IEEE (1997). [7] G. Mohan, C. Siva Ram Murthy, Efficient rerouting in WDM singlefiber and multi-fiber networks with and without wavelength conversion, Journal of High Speed Networks 8 (1999) 149– 171. [8] S. Ramamurthy, B. Mukherjee, Survivable WDM mesh networks. Part I—protection, Proceedings of IEEE INFOCOM (1999) 744–751. [9] S. Ramamurthy, B. Mukherjee, Survivable WDM mesh networks. Part II—restoration, Proceedings of ICC99 (1999). [10] G. Mohan, C. Siva Ram Murthy, Routing and wavelength assignment for establishing dependable connections in WDM networks, Proceedings of IEEE International Symposium Fault-Tolerant Computing, June (1999) 94–101. [11] G. Mohan, C. Siva Ram Murthy, A.K. Somani, Efficient algorithms for routing dependable connections in WDM optical networks, IEEE/ ACM Transactions on Networking 9 (5) (2001) 533–566. [12] B.T. Doshi, S. Dravid, P. Harshavardhana, O. Hauser, Y. Wang, Optical network design and restoration, Bell Labs Technical Journal 4 (1) (1999) 58–84. [13] N. Nagatsu, S. Okamoto, K. Sato, Optical path cross-connect system scale evaluation using path accommodation design for restricted wavelength multiplexing, IEEE Journal on Selected Areas in Communications 14 (5) (1996) 893–902. [14] M. Alanyali, E. Ayanoglu, Provisioning algorithms for WDM optical networks, IEEE/ACM Transactions on Networking 7 (5) (1999) 767–778. [15] S. Baroni, P. Bayvel, R.J. Gibbens, S.K. Korotky, Analysis and design of resilient multi-fiber wavelength routed optical transport networks, IEEE/OSA Journal of Lightwave Technology 17 (5) (1999) 743–758. [16] S. Bandyopadhyay, A. Sengupta, A. Jaekel, Fault-tolerant routing scheme for all-optical networks, Proceedings of SPIE Conference on All-Optical Communication Systems (1998). [17] V. Anand, C. Qiao, Dynamic establishment of protection paths in WDM networks, part-I, Proceedings of ICCCN, October (2000). [18] N. Ghani, Survivability provisioning in optical MPLS networks, Proceedings of ECNOC, June (2000). [19] C.S. Li, R. Ramaswami, Automatic fault detection, isolation, and recovery in transparent all-optical networks, IEEE/OSA Journal of Lightwave Technology 15 (10) (1997) 1784–1793. [20] M. Sridharan, A.K. Somani, Revenue maximization in survivable WDM networks, Proceedings of SPIE Optical Networking and Communications 4233 (2000) 291 –302. [21] G. Mohan, C. Siva Ram Murthy, Lightpath restoration in WDM networks, IEEE Network Magazine 14 (6) (2000) 24 –32. [22] T. Wu, Emerging technologies for fiber network survivability, IEEE Communications Magazine 33 (2) (1995) 58–74. [23] Y. Ye, S. Dixit, M. Ali, On joint protection/restoration in IP-centric DWDM-based optical transport networks, IEEE Communications Magazine 38 (6) (2000) 174– 183. [24] A. Fumagalli, M. Tacca, Optimal design of differentiated reliability (DiR) optical ring networks, Proceedings of International Workshop on QoS in Multiservice IP Networks (QoS-IP) 2001, January (2001). [25] A. Fumagalli, M. Tacca, Differentiated reliability (DiR) in WDM ring without wavelength converters, Proceedings of ICC00 (2000). [26] C. Chava Vijaya Saradhi, C. Siva Ram Murthy, Routing differentiated reliable connections in single and multi-fiber WDM optical networks, Proceedings of SPIE Optical Networking and Communications 4599 (2001) 24–35. [27] C. Vijaya Saradhi, C. Siva Ram Murthy, Routing differentiated reliable connections in WDM optical networks, SPIE Optical Networks Magazine 3 (3) (2002) 50–67. [28] O. Gerstel, R. Ramaswami, G.H. Sasaki, Cost-effective traffic grooming in WDM rings, IEEE/ACM Transactions on Networking 8 (5) (2000) 618–630. [29] E. Modiano, A. Chiu, Traffic grooming algorithms for minimizing electronic multiplexing costs in unidirectional SONET/WDM ring networks, Proceedings of Information Science and Systems, March (1998). [30] X. Xijun, C. Qiao, An effective and comprehensive solution to traffic grooming and wavelength assignment in WDM rings, Proceedings of SPIE Optical Networking and Communications 3531 (1998) 221 –232. [31] T. Cinkler, D. Marx, C. Popp Larsen, D. Fogarzs, Heuristic algorithms for joint configuration of the optical and electrical layer in multi-hop wavelength routing networks, Proceedings of IEEE INFOCOMM (2000) 1000–1009. Chava Vijaya Saradhi received his B.Tech. degree in Electronics and Communications Engineering from College of Engineering, Jawaharlal Nehru Technological University, Hyderabad, India, the MS (by Research) degree in computer science from the Indian Institute of Technology(IIT), Madras, India. He worked as a Project Associate at IIT, Madras, from January 2002 to June 2002. Currently he is a senior research engineer at Institute for Infocomm Research (I2R), formerly known as Kent Ridge Digital Labs, Singapore. He is also pursuing Ph.D degree at National University of Singapore (NUS), Singapore. His current research involves the development of signaling protocols for GMPLS based optical network test-bed under Optical Network Focus Interest Group (ONFIG) project. His research interests include Optical Networks, Wireless Networks, and Real-Time Systems. C. Siva Ram Murthy obtained the B.Tech. degree in electronics and communications engineering from Regional Engineering College, Warangal, India in 1982, the M.Tech. degree in computer engineering from the Indian Institute of Technology (IIT), Kharagpur, India, in 1984, and the Ph.D. degree in computer science from the Indian Institute of Science, Bangalore, India, in 1988. He joined the Department of Computer Science and Engineering at IIT, Madras as a Lecturer in September 1988, became an Assistant Professor in August 1989 and an Associate Professor in May 1995. He is currently a Professor with the same department since September 2000. He has to his credit over 150 research papers in international journals and conferences. He is a co-author of the textbooks Parallel Computers: Architecture and Programming (Prentice-Hall of India, New Delhi, 2000), New Parallel Algorithms for Direct Solution of Linear Equations (John Wiley & Sons, Inc., USA, 2000), Resource Management in Realtime Systems and Networks (MIT Press, USA, 2001), and WDM Optical Networks: Concepts, Design, and Algorithms (Prentice-Hall, USA, 2001). He is a recipient of the Best Ph.D. Thesis Award and also of the Indian National Science Academy Medal for Young Scientists. He is a co-recipient of Best Paper Awards from 5th IEEE International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS’97) held in Geneva, Switzerland in 1997 and 6th International Conference on High Performance Computing (HiPC’99) held in Calcutta, India in 1999. He is a fellow of Indian National Academy of Engineering. He has held visiting positions at German National Research Centre for Information Technology (GMD), Sankt Augustin, Germany, University of Washington, Seattle, USA, University of Stuttgart, Germany, and EPFL, Switzerland. His research interests include Parallel and Distributed Computing, Real-time Systems, Lightwave Networks, and Wireless Networks.