In the early 1980s, a revolution in telecommunications networks began that was spawned by the use of a relatively unassuming technology, fiber-optic cable. Since then, the tremendous cost savings and increased network quality has led to many advances in the technologies required for optical networks, the benefits of which are only beginning to be realized.
History
Telecommunication networks have evolved during a century-long history of technological advances and social changes. The networks that once provided basic telephone service through a friendly local operator are now transmitting the equivalent of thousands of encyclopedias per second. Throughout this history, the digital network has evolved in three fundamental stages: asynchronous, synchronous, and optical.
Asynchronous
The first digital networks were asynchronous networks. In asynchronous networks, each network element's internal clock source timed its transmitted signal. Because each clock had a certain amount of variation, signals arriving and transmitting could have a large variation in timing, which often resulted in bit errors. More importantly, as optical-fiber deployment increased, no standards existed to mandate how network elements should format the optical signal. A myriad of proprietary methods appeared, making it difficult for network providers to interconnect equipment from different vendors.
Synchronous
The need for optical standards led to the creation of the synchronous optical network (SONET). SONET standardized line rates, coding schemes, bit-rate hierarchies, and operations and maintenance functionality. SONET also defined the types of network elements required, network architectures that vendors could implement, and the functionality that each node must perform.
Optical
The one aspect of SONET that has allowed it to survive during a time of tremendous changes in network capacity needs is its scalability. Based on its open-ended growth plan for higher bit rates, theoretically no upper limit exists for SONET bit rates. However, as higher bit rates are used, physical limitations in the laser sources and optical fiber begin to make the practice of endlessly increasing the bit rate on each signal an impractical solution. Additionally, connection to the networks through access rings has also had increased requirements. Customers are demanding more services and options and are carrying more and different types of data traffic. To provide full end-to-end connectivity, a new paradigm was needed to meet all the high-capacity and varied needs. Optical networks offer the required bandwidth and flexibility to enable end-to-end wavelength services.
Today's optical networks are carrying huge traffic which is doubling almost every year. The traffic includes voice, video, data and various real time application services like remote monitoring and control, remote surgery etc. The internet has become part of almost each home. The existence of World Wide Web (WWW) and internet can be said to be built on optical long haul networks. The first generation of optical networks is using an optical transmission medium in the form of optical fibers as point-to-point (P2P) links. Generally SONET (Synchronous Optical Network) /SDH (Synchronous Digital Hierarchy) standard is used to deploy these networks. At each one network node, traffic is subjected to O-E-O (Optical-Electrical-Optical) conversions. The node decide transmission bit rate, protocol and format. The improvement in optical devices like optical multiplexers, optical cross connects, erbium doped fiber amplifier converters, tunable transmitters and receivers etc., has eliminated the need of O-E-O conversion at each node and made way for the second generation of optical networks.
1.2 BASIC CONCEPT OF WDM :
Optical fiber has become the dominant transport medium in telecommunication systems because of its advantages in capacity, reliability, cost, and scalability. An attractive feature of optical fiber is its enormous capacity, on the order of a few terabits per second. The fiber optic medium is the only one capable of providing high-bandwidth service cost-effectively. Today, optical fiber is widely deployed in backbone networks. However, only a small fraction of the full capacity of the installed optical fiber has been realized so far. The primary reason for this inefficiency is the large mismatch between peak electronic processing and source rates, and fiber capacity. Therefore, multiplexing techniques such as wavelength-division multiplexing (WDM) have been used in order to utilize fiber capacity more efficiently. In a WDM system, a single fiber can carry many channels, and the total utilized capacity can be increased dramatically. Scientists from Bell Laboratories have successfully demonstrated the transmission of 100 wavelengths over a fiber, with each wavelength modulated at 10 Gb/s, to provide a throughput of 1Tb/s. Thus, WDM technology is paving the way for the development of new services, and one can be sure that it is about to play a major role in the expansion of optical networks. Optical networks based on wavelength division multiplexing (WDM) can effectively and economically satisfy the explosive growth of demand for high bandwidth in transport networks.
Wavelength division multiplexing divides the tremendous bandwidth of a fiber into many nonoverlapping wavelengths (WDM channels), which can be operated at any desirable speed, e.g., peak electronic speed of a few gigabytes per second. An access station may transmit signals on different wavelengths, which are joined into the fiber using wavelength multiplexers. An optical cross-connect (OXC) can route an optical signal from an input fiber to an output fiber without performing optoelectronic conversion. In a wavelength-routed optical network, a connection between a source node and a destination node is called a lightpath. A lightpath is an optical channel that may span multiple fiber links to give an all- optical connection between two nodes. In absence of wavelength converters, a lightpath would occupy the same wavelength on all fiber links that it traverses. Two lightpaths on a fiber link must be on different wavelength channels to avoid the interference of the optical signals.
The failure of a network element such as a fiber link can lead to the failure of all the lightpaths that traverse the failed link. Since each lightpath is expected to operate at a rate of several gigabytes per second, a failurein fiber can lead to a severe data loss. Although higher protocol layers [such as asynchronous transfer mode (ATM) and Internet protocol (IP)] have recovery procedures to recover from link failures, the recovery time is still considerably large (on the order of seconds), whereas we expect that restoration times at the optical layer will be on the order of a few milliseconds to reduce data losses.
1.3 THESIS OBJECTIVES:
To study the different capacity allocation strategies for protection and restoration of single link failure scenario in mesh-based survivable networks.
1.4 REPORT ORGANIZATION:
Chapter-1-Inroduction, Chapter-2 deals with Optical Network Survivability. Chapter-3 discusses about the Concept of p-cycle. Chapter- 4 deals with concept of working capacity allocation model in mesh-based survivable networks. Chapter- 5 deals with concept of spare capacity allocation model in mesh-based survivable networks. Chapter- 6 deals with concept of Joint Capacity Planning Models & Summary of results. Chapters- 7 presents the Conclusion.
SURVIVABILITY IN OPTICAL NETWORK CHAPTER 2
2.1 SURVIVABILITY :
In this chapter survivability in optical network has been discussed. Network survivability is the ability of a telecommunication network to continue to provide service in the event of failures, and comprises both planning and operations aspects. The planning aspects involve different protection schemes for allocating spare capacity to the network, which is to be used upon the occurrence of a failure event. From a network operations standpoint, protection schemes are implemented via restoration mechanisms which are activated to restore service to affected customers when failure events happen.
There are several approaches to ensure optical fiber network survivability. Survivable fiber network architectures are based either on dedicated resources or on dynamic restoration. In dedicated-resource protection (which includes automatic protection switching (APS) and self-healing rings), the network resources may be dedicated for each failure situation, or the network resources may be shared among different failure scenarios. In dynamic restoration, the spare capacity available within the network is utilize for restoring services affected by a failure. Normally, dynamic restoration schemes are more efficient in utilizing capacity due to the multiplexing of the spare-capacity requirements and provide resilience against different kinds of failures, while dedicated-resource protection schemes have a faster restoration time and provide guarantees on the restoration ability.
2.2 Fault-Management Schemes
This study examines different approaches to survive link failures in fiber network. These approaches are based on two basic survivability paradigms:
Path protection/restoration
Link protection/restoration
If backup resources (routes and wavelengths) are pre-computed and reserved in advance, we call it a protection scheme. Otherwise, when a failure occurs, if another route and a free wavelength have to be discovered dynamically for each interrupted connection, we call it a restoration scheme. Generally, dynamic restoration schemes are more efficient in utilizing network capacity because they do not allocate spare capacity in advance and provide resilience against different kinds of failures (including multiple failures); but protection schemes have faster recovery time .
Fig. 1: Different schemes for surviving link failures.
2.2.1 Path protection/restoration
In path protection, backup resources are reserved during connection setup, while in path restoration; backup routes are discovered dynamically after the link failure. When a link fails [illustrated in Fig. 2], the source node and the destination node of each connection that traverses the failed link are informed about the failure via messages from the nodes adjacent to the failed link, as illustrated in Fig. 3.
In WDM systems, path-based protection refers to the reservation of a protection path and wavelength (protection wavelength path) for each working wavelength path and each link failure. Upon failure of a link, the source and destination nodes of each affected connection switch to the corresponding protection wavelength paths. As opposed to link-based protection, which involves only the nodes adjacent to the link failure, path-based protection needs a mechanism to notify the affected connection end nodes of the failure. This requires the cooperation of several network nodes, and may not be easily achievable.
The protection wavelength paths for every link failure are usually reserved at connection setup, and should be disjoint with the failed link. Upon link failure, the wavelength paths reserved for this failure scenario are activated. As a special case, when a protection wavelength path is disjoint with every link of the working path, the same wavelength path can be used to restore a connection upon any single-link failure along the working path.
Path restoration reroutes the broken traffic between the end nodes of the affected paths. In this way, spare capacity all over the network is used and a lower spare capacity requirement is expected than in Link restoration. In this case, many more nodes are involved in the restoration phase, since every broken path needs to be restored separately.
Fig. 2. Path protection
Fig. 3. Link-fail messages sent to all source and destination
nodes of connection traversing a failed link
2.2.1.1 Dedicated-path protection
In dedicated-path protection (also called 1:1 protection), the resources along a backup path are dedicated for only one connection and are not shared with the backup paths for other connections.
Fig. 4. Dedicated-path protection
In dedicated path protection, the backup wavelength on the links of a protection path is reserved for a specific working connection. This implies that two over-lapping protection paths must use different wavelengths even if the working paths do not overlap. For example, Fig. 4 shows two working paths, 4-5-6 and 1-2-3, both using λ1. The protection wavelength path for connection 1 is λ2 on 4-1-2-6 (λ1 is a working wavelength on link 1-2 and cannot be used for protection). The protection wavelength path for connection 2 is 1-5-2-6-3. Since these two protection paths have the common link 2-6, and λ2 is assigned to protection path 1, protection path 2 has to be assigned a different wavelength (e.g., λ1).
Dedicated path protection requires a large amount of extra capacity for protection purposes, and when there is no failure, the protection resources are kept idle. The positive aspect is that it is able to provide recovery from not only single-link failures, but also some multilink failures.
2.2.1.2 Shared-path protection
In shared-path protection, the resources along a backup path may be shared with other backup paths. As a result, backup channels are multiplexed among different failure scenarios (which are not expected to occur simultaneously), and therefore, shared-path protection is more capacity efficient when compared with dedicated-path protection.
Fig. 5: Shared-path protection
Shared path protection allows the use of the same wavelength on a link for two different protection paths if the corresponding working paths are link-disjoint. Thus, it is possible to utilize the capacity more efficiently, while still achieving 100 percent recovery from single-link failures. An example of shared path protection is given in Fig. 5. The two backup paths can now share λ2 on link 2-6. Therefore, only one wavelength on this link has to be reserved for protection, as opposed to two for dedicated path protection.
2.2.1.3 Path restoration
In path restoration, the source and destination nodes of each connection traversing the failed link participate in a distributed algorithm to dynamically discover an end-to-end backup route. If no routes are available for a broken connection, then the connection is dropped.
2.2.2 Link protection/restoration
In link protection, backup resources are reserved around each link during connection setup, while in link restoration, the end nodes of the failed link dynamically discover a route around the link. In link protection/restoration [illustrated in Fig.6 & 7], all the connections that traverse the failed link are rerouted around that link, and the source and destination nodes of the connections are oblivious to the link failure.
Fig. 6. Link protection
Figure 7. Backup paths using link protection strategy
2.2.2.1 Dedicated-link protection
In dedicated-link protection, at the time of connection setup, for each link of the primary path, a backup path and wavelength are reserved around that link and are dedicated to that connection. In general, it may not be possible to allocate a dedicated backup path around each link of the primary connection and on the same wavelength as the primary path. For example, Fig. 8 shows a bidirectional ring network with one connection request between Node 1 and Node 5. The backup path around link (2,3), viz. (2,1,8,7,6,5,4,3), and the backup path around link (3,4), viz. (3,2,1,8,7,6,5,4), share links in common and hence cannot be dedicated the same wavelength. Since our experience indicates that dedicated-link protection Utilizes wavelengths very inefficiently.
Fig. 8. Illustrative example showing that dedicated-link protection is not
possible in a bidirectional ring network.
Fig. 9. Dedicated-link protection
Dedicated link protection means that a protection wavelength path is dedicated to a working channel on a particular link. Therefore, if the protection paths for (some wavelengths on) two different links overlap, different wavelengths must be assigned to the protection path on the overlapping portion even if the working wavelengths on the two links are the same. As an example, consider Fig. 9. Let λ1 on path 5-2-6 (labeled protection path 1) be the protection wavelength path for a working channel on link 5-6, and the protection path for a working channel on link 1-2 be 1-5-2 (labeled protection path 2). Then a different wavelength, say λ2, must be assigned to protection path 2, even if the working wavelengths on links 5-6 and 1-2 are the same, say λ1. Note that this requires wavelength conversion if link 1-2 fails. The above example indicates the difficulty in designing efficient protection schemes in large networks. Efficient design is especially difficult if wavelength conversion facilities are unavailable. On the other hand, dedicated link protection may offer protection against the failure of multiple links. For example, in Fig. 9 both working channels can be recovered if both links 1-2 and 5-6 fail simultaneously. However, note that recovery of working channel 5-6 is not possible if both links 5-2 and 5-6 fail at once.
2.2.2.2 Shared-link protection
In shared-link protection, the backup resources reserved along the backup path may be shared with other backup paths. As a result, backup channels are multiplexed among different failure scenarios (which are not expected to occur simultaneously), and therefore shared-link protection is more capacity-efficient when compared with dedicated-link protection.
Fig. 10. Shared-link protection
Shared link protection allows different protection paths to share a wavelength on the overlapping portion if the corresponding working channels are on different links. Shared link protection utilizes capacity more efficiently than dedicated link protection, and can provide 100 percent recovery from single link failures. Fig. 10 shows an example of shared link protection. Protection paths 1 and 2 (used to protect a working channel on links 5-6 and 1-2, respectively) can share wave-length λ1 on link 5-2. Note, however, that a different wavelength must be used to protect a different working channel on link 5-6 if protection path 1 is used for that working channel.
2.2.2.3 Link restoration
In link restoration, the end nodes of the failed link participate in a distributed algorithm to dynamically discover a route around the link. If no routes are available for a broken connection, then the connection is dropped.
p-CYCLE CONCEPT CHAPTER 3
3.1 CONCEPT OF p-CYCLE :
Before going deep into the different dual failure restoration approaches and techniques the concept of cycle becomes mandatory because it plays an important role in all the approaches later discussed in this report .Restoration time less than 50 ms is required property of self healing rings of SONET. In the ring structure, after the detection of failure and signaling, any two switching actions are required at the adjacent nodes of the failed span to restore the traffic. Such a fast restoration is provided with 1+1 path protection in case of mesh networks. However this requires a lot of spare capacity, or in the other words this is not capacity efficient.
The p-cycle concept is a recent strategy to recover from network failures. It provides a protection mechanism for spans and for transiting traffic through failed nodes. p-Cycles can be described as pre-configured closed protection paths in a mesh network. Cycle-oriented pre configuration remains fundamentally a mesh restorable network technology in terms of its capacity efficiency and in its functional differences from self-healing rings .They are physical structures formed in the spare capacity of a channelized network or virtual structures that use the "slack" (unused working) capacity of links in an ATM or MPLS network. Like rings, the protection capacity is pre-connected in advance of any failure and the protection switching is very fast and simple. Unlike rings, however, p-cycles support shortest-path routing of working paths over a network and protect spans that straddle the cycle of protection capacity, as well as failures on the cycle itself. It turns out that the latter, apparently simple, difference leads to an enormous improvement in capacity-efficiency (the ratio of capacity reserved for p-cycles on all spans and the total capacity needed for shortest working paths). Studies have repeatedly found that p-cycle networks are essentially as capacity-efficient as span - restorable mesh networks.p-Cycles provide an attractive way for network protection, since the benefits of both ring-based protection and mesh-based restoration can be utilized.
Two basic types of p-cycles exist. Link p-cycles protect the individual channels within a link. Node encircling p-cycles are routed through all neighbour nodes of a specific node and protect all the connections traversing this node. The protected node is not contained in the respective p-cycle. An emphasis is put on link p-cycles, assuming the nodes to be very reliable, e.g., using internal redundancy. Fig. 11 (a) depicts a network with one link p-cycle. The p-cycle is able to protect on-cycle links as shown in Fig. 11 (b). Furthermore, a p-cycle is able to protect straddling links. A straddling link is an off-cycle link having p-cycle nodes as endpoints. In the case of a straddling link failure, a p-cycle can simultaneously protect two working paths on the straddling link by providing the two alternative paths around the p-cycle as shown in Fig. 11 (c)-(d).p-Cycles can be installed as a fixed cycle infrastructure in the network
Fig. 11. A network with one link p-cycle (a) which can protect
on-cycle links (b) and straddling links (c)-(d)
This is similar to the deployment of SDH /Sonet rings, although p-cycle nodes differ from ADMs (e.g., by providing ports for straddling links). Another possibility are virtual p-cycles, where the individual cycles are (re-)configurable by a network management system or by distributed self-organization. The network configuration process of p-cycles in an existing network can be sketched as follows. First, a given demand for connections is routed through the network, so that the links reserve (working) capacity for the demands. The spare capacity of the links is the remaining available capacity. Then the p-cycles are formed in the spare capacity of the network. The set of link p-cycles is chosen such that for every link the working connections are protected by p-cycles of corresponding capacity. The routing of the demands has to be adapted, if a protecting set of p-cycles cannot be found. Like SDH / Sonet line-switched rings the p-cycles protection capacity can also be used for low-priority pre-emptible traffic. p-Cycles have the outstanding property that protection switching decisions can be made quickly, since only the nodes neighbouring the failure need to perform any real-time actions. Switching times in the order of some 10 ms comparable to SDH/Sonet line-switched rings can be achieved. Therefore, p-cycles can be deployed efficiently using non-real-time configuration (centralized network management system or distributed self-organization) while the (distributed, node internally processed) reaction to failures is very quick.
ADVANTAGES OF p-CYCLES:
The most important advantage of p-cycles is that it provides ring like speed and mesh like efficiency and flexibility. The recovery with p-cycles is very fast (50ms) as in ring-based networks.
3.3 COMPARISON OF p-CYCLES WITH RINGS:
ATTRIBUTE
p-CYCLE
SONET RINGS
Modularity
Any add drop or cross-connection signal unit
OC-n
Protection yield
Up to two useful restoration paths per unit of p-cycle capacity
One restoration path per unit of ring protection capacity
Protection flexibility
Restoration failure on the cycle and on straddling spans
Routing must confirm to deployed (ring) structures and inter-ring transition restriction
Network redundancy
Essentially that of a span restorable mesh network
Significantly over 100% investment in spare capacity
WORKING CAPACITY ALLOCATION
MODEL CHAPTER 4
The simplest telecommunication network design problem is to determine the least capacity required to satisfy a set of given point-to-point demands. This is called the working capacity allocation problem and can be modeled as an integer linear program (ILP) using either a node-arc or an arc-path formulation method. Both models will be given in this section. For this arrangement, a link denotes the bi-directional connection between a pair of nodes. For a modern DWDM telecommunication network, a link between nodes consists of many pairs of fiber optic cable co-located in a single fiber optic duct. One member of the pair is for traffic from while the other is for traffic in the reverse direction. In practice most large carriers use a separate cable for each direction of transmission.
4.1. The node-arc model
Let be a graph where denotes the set of nodes and L denotes unordered pairs of nodes corresponding to links. Let be a set of ordered pairs called arcs corresponding to the links. Flow on arc implies that flow is from . Flow in the opposite direction must be on arc . The directed graph (network) is given by . Let denote the demand for traffic with origin node and destination node . Traffic demand need not be symmetrical (i.e., it's possible that ), and it's assumed that = 0 for The corresponding matrix is called the demand or traffic matrix. Since all the traffic prescribed by the demand matrix must share the same network represented by , the problem is a member of the class of multicommodity network flow problems. An individual commodity can be expressed as either an pair for each such that , or an aggregation of such -pairs by their source (or destination) nodes. Usually smaller models result from the second strategy which is adopted here. Hence, there will be commodities, each having up to destinations, corresponding to each of the other nodes in N rather than (as many as) commodities corresponding to each demand pair in the traffic matrix. Note that this approach sets up a multi-commodity flow problem, where each commodity has a single "source" and multiple "sinks" corresponding to the nodes of a given commodity's demand matrix.
Let the n-component requirement vector for commodity be given by
For a given commodity, a node requirement greater than zero corresponds to a supply node, a node requirement less than zero corresponds to a demand node, and a node requirement of zero corresponds to a transshipment node. For each arc let the variable denote the flow of commodity k on arc The node-arc formulation of the working capacity allocation model is stated mathematically as follows:
minimize total working capacity:
subject to flow conservation:
subject to capacity in normal direction:
subject to capacity in reverse direction:
subject to nonnegativity and integrality:
and integer
This model assumes symmetrical capacity, so that the capacity of on link can accommodate a simultaneous flow of in both directions. In the classical multicommodity network flow problem the capacities are constant and need not be identical in both directions.
Link
Demand
(1,2)
10
(1,4)
10
(2,3)
10
(2,4)
10
(2,5)
10
(3,4)
10
(3,5)
10
(3,6)
10
(4,5)
10
(5,6)
10
Fig.12 Example problem with the following demand matrix
A software implementation of all the models presented in this manuscript and the data file for the test case illustrated in Fig. 12. This code was used to solve the example problem illustrated. An optimal solution of node-arc formulation of the working capacity allocation model for is illustrated in Fig. 13 in this case we give 120 backup path in data file and it we reduce the backup path to 90 then the solution to node-arc formulation of the working capacity allocation model for is illustrated in Fig. 14.
Fig. 13 solution to node-arc formulation of the working capacity allocation model for (total working capacity is 100)
Fig. 14 solution to node-arc formulation of the working capacity allocation model for (total working capacity is 100)
The advantage of this model is that it requires very little input data and implicitly considers all possible paths for every demand pair. One slight disadvantage is that some additional analysis or post processing of the LP solution is required to find the paths and flow for a given demand pair. This can be easily accomplished with a procedure similar to that suggested by Dijkstra[13] for finding shortest paths. Also some of the paths in the optimal solution may use a large number of arcs. The number of arcs in a path is known as the hop count and this cannot be restricted in the node-arc model.
4.2. The Arc-Path Model
A directed path from node s to node t in the network is a sequence of nodes and arcs where and each arc and node are distinct. Let D denote the set of demand pairs. That is, implies that Let denote the set of the directed paths from to in for all and let. Let denote the set of paths that contain arc , and let denote the flow on path p. The arc-path formulation of the working capacity allocation model is stated mathematically as follows:
Minimize total working capacity:
Subject to Demand:
Subject to Capacity in Normal Direction:
Subject to Capacity in Reverse Direction:
Subject to Nonnegativity and Integrality:
and integer .
Fig. 15 solution to arc-path formulation of the working capacity allocation model for (total working capacity is 100)
Fig. 16 solution to arc-path formulation of the working capacity allocation model for (total working capacity is 100)
One advantage of this model is that the hop count for all paths can be restricted. Paths that exceed the hop count do not appear in the sets . A disadvantage is that the cardinality of the sets can be very large. For most applications is replaced with where only a few of the shortest paths from appear in . When this substitution is made, however, there is no guarantee that the arc-path model will give as good a solution as the node-arc model. The solution for the example problem is illustrated in Figure 15 &16. Note that the total working capacity is identical for both the node-arc and arc-path formulations, but the individual link capacities are different. The comparison of both node-arc and arc-path formulation of the working capacity allocation model is illustrated in Figure 16.
Fig. 17. Solution to working capacity allocation models
SPARE CAPACITY ALLOCATION
MODEL CHAPTER 5
This chapter presents optimization models for the spare capacity allocation problem in a mesh telecommunications network. Since the users of these networks require high reliability, these networks are designed to continue to provide service when a single link failure occurs. It is commonly assumed that the probability of multiple link failures during the time required to repair a failure is so small that network designers plan restoration strategies based on single link failures. Designers have identified two basic strategies to protect a network against single link failures: dedicated protection strategies and shared protection strategies. A discussion of each strategy follows.
The simplest idea for protecting the links in a path is to provision a node-disjoint backup path. This is also called 1+1 protection since each working path has a backup path in reserve that will be used whenever, and only when, a link in the working path fails (see [14]). In shared protection strategies, the spare capacity on a link is not dedicated to any given demand pair and may be used in the restoration of various demand pairs. Shared protection strategies come in two varieties: link restoration and path restoration. Models for each follow.
5.1. Link Restoration
In link restoration model, it is assumed that each node has the capability of detecting link failures and implementing a rerouting algorithm around the defective link. If link fails, then restoration requires that all working traffic that uses link be rerouted on the reduced graph. For the network illustrated in Figure 16, 10 units of spare capacity on links in one or more paths from node 1 to node 2 must be available to protect link {1, 2}. Similarly, 20 units of spare capacity on links in one or more paths from node 1 to node 4 must be available to protect link {1, 4}. Of course, the failure of link {1, 4} implies the loss of both the working capacity and spare capacity on that link. That is, the working capacity and the spare capacity are both assigned to fibers that are carried in the same duct. A catastrophic failure usually refers to a cut that destroys all fiber in a duct. However, the spare capacity used to restore {1, 2} is also available for the restoration of {1, 4}. Link restoration models come in node-arc, arc-path, and p-cycle varieties.
5.1.1. The node-arc model for link restoration
Let for all denote the known volume of working traffic on link Suppose link fails. Then units of flow must be rerouted from node to node and vice versa. In the node-arc model for link restoration, the requirement at node is given by
Let the variable denote the spare capacity assigned to link and the variable denote the restoration flow on arc when fails. The node-arc formulation of the link restoration version of the spare capacity allocation model is stated mathematically as follows:
Minimize Total Working Plus Spare Capacity:
Subject to Flow Conservation:
Subject to Capacity in Normal Direction:
Subject to Capacity in Reverse Direction:
Subject to Link Failures:
Subject to Non-negativity:
and integer
where for all are fixed (usually to values determined by solving a working capacity allocation model).
This model assumes symmetrical working and spare capacity. That is, the capacity is the same in both directions on all links. This model also assumes that the working traffic was routed separately prior to determining the routing for restoration. In Chapter 6 we discuss models where the working and restored traffic are routed jointly. The solution for of the problem instance given in Figure 18 and the solution for of the problem instance given in Figure 19. Note that for 70 units of spare capacity are required to protect 100 units of working capacity and for 90 units of spare capacity are required to protect 100 units of working capacity. This is typical for this type of problem. The first investigations of the node-arc formulation for this problem may be found in Whitler [16] and Kennington and Whitler [15].
Fig. 18 solution to the node-arc formulation of the link restoration version of the spare capacity
allocation model for (total spare capacity is 70)
Fig. 19 solution to the node-arc formulation of the link restoration version of the spare capacity
allocation model for (total spare capacity is 90)
A clever, but different linear programming model for this problem can be found in Sakauchi et al. [17]. Their model is based on the concept of a cut and we call it the spare capacity cutest model. Let and be distinct nodes in , and let and be a partition of the nodes such that and The cutset or By numbering the links in every cutset can be represented by an m-component vector where if link is in and otherwise. Suppose link fails and define as the binary matrix whose rows are cutset vectors corresponding to all cuts in Then the spare capacity vector h must satisfy where is a vector of all Since this must hold for each link in L, the spare capacity cutest model is minimize
Of course, the disadvantage of this formulation is that it is very difficult to generate all cutsets for a given link. However, such a model is amenable to a decomposition scheme, and one such algorithm can be found in Herzberg [18]. Herzberg also presents an extension of the basic spare capacity cutset model along with pre-processing rules that can speed convergence. A distributed real-time algorithm for finding a backup path for link restoration has been presented by Chow et al. [19]. It is a real-time version of the efficient two-tree procedure examined in Helgason et al. [20].
5.1.2. The Arc-Path Model for Link Restoration
The arc-path model for link restoration uses the set for all to denote the set of directed paths from node s to node t excluding the direct arc Therefore, the set of all potential backup paths is given by The variable for all denotes the spare capacity on link and the variable denotes the restoration flow on path when link fails. The arc-path formulation of the link restoration version of the spare capacity allocation model may be stated as follows:
Minimize Total Working Plus Spare Capacity:
Subject to Lost Working Capacity:
Subject to Link Capacities Normal Direction:
Subject to Link Capacities Reverse Direction:
Subject to Nonnegativity:
where for all are fixed. The solution for the test problem is illustrated in Figure 20 & 21. Note that for the total spare capacity is as opposed to in Figure 18. This is due to the fact that not all paths are included in
Fig. 20 solution to the arc-path formulation of the link restoration version of the spare capacity
allocation model for (total spare capacity is 80)
Fig. 21 solution to the arc-path formulation of the link restoration version of the spare capacity
allocation model for (total spare capacity is 100)
5.1.3. The P-Cycle Model for Link Restoration
The objective of the p-cycle concept is to obtain the restoration speed of self-healing rings (which use protection) while simultaneously retaining the total capacity reduction offered by the shared protection paradigm. This novel idea is developed in the following series of manuscripts: Grover and Stamatelakis [21], Stamatelakis and Grover [22,23], and Grover [24].
A directed cycle containing arc is a directed path from to followed by the arc In this application, the set of links that correspond to any directed cycle is called a p-cycle which is equivalent to a ring. Since a p-cycle is composed of bi-directional links, restoration flow in any p-cycle can be in either a clockwise or a counter-clockwise direction. A link in L is said to be a chord-link of a given p-cycle if the p-cycle contains nodes and but does not contain arc or arc The P-cycle model requires that every link that carries working traffic be protected by a p-cycle. That is, there must be a p-cycle containing both of the nodes incident to the link.
Let for denote the set of potential p-cycles (rings) that contain as a link and for all denote the set of potential p-cycles that contain as a chord-link. The set of potential p-cycles that can protect is and the set of all potential p-cycles is given by Let for all denote the set of links in p-cycle The variable for all denotes the capacity of p-cycle and denotes the spare capacity of link Let denote the restoration flow on p-cycle when link fails, and let be a binary variable that is one if and is zero, otherwise. The p-cycle spare capacity allocation model may be stated mathematically as follows:
Minimize total working plus spare capacity:
Subject to restoration flow:
Subject to the relationship between x and z:
Subject to one cycle for restoration:
Subject to cycle capacity number 1:
Subject to cycle capacity number 2:
Subject to link capacity:
Subject to Non-negativity and Integrality:
Fig. 22. Optimal solution for p-cycle protection for (total spare capacity = 100)
Fig. 23. Optimal solution for p-cycle protection for (total spare capacity = 140)
Table 1
p-cycles for example problem
Cycles
Protection path
C[1]
(1,2) (1,4) (2,4)
C[2]
(2,3) (2,5) (3,5)
C[3]
(2,4) (2,5) (4,5)
C[4]
(3,5) (3,6) (5,6)
C[5]
(1,2) (1,4) (2,5) (4,5)
C[6]
(2,3) (2,4) (3,5) (4,5)
C[7]
(2,3) (2,5) (3,6) (5,6)
C[8]
(1,2) (1,4) (2,3) (3,5) (4,5)
C[9]
(2,3) (2,4) (3,6) (4,5) (5,6)
The nine potential p-cycles given in Table 1 along with the given working capacities were used to solve the problem illustrated in Figure 15 & 16. An optimal solution using p-cycles is illustrated in Figure 22 & 23. P-cycle protection for the total spare capacity is 100 compared to the 80 units required for the arc-path link restoration model and for the total spare capacity is 140 compared to the 100 units required for the arc-path link restoration model.
5.2. Path Restoration
Failure of a link may affect one or more paths that are used to carry working traffic. Therefore, restoration requires allocation of spare capacity to a set of paths that do not use the failed link. The distinction between path restoration and link restoration is that path restoration uses alternative routes from the origins to the destinations of the demand pairs affected by the failed link rather than simply taking a "detour" around it. Thus it is a distinction between "global" and "local" rerouting. Notice that p-cycles reroute all of the traffic affected by a link failure on one or two paths around the link whereas a path restoration scheme may distribute the rerouted traffic over a larger number of backup paths. Thus, path restoration will generally require less total spare capacity than either link or p-cycle restoration at the expense of a more sophisticated restoration scheme. The set is the set of paths available for restoration from to when link fails. That is, is the set of directed paths from to that do not use link Let be the set of directed paths from to that are not available for working traffic when link fails. That is, or The arc-path formulation of the path restoration version of the spare capacity allocation model may be stated mathematically as follows:
Minimize total working plus spare capacity:
Subject to spare demand 1:
Subject to spare demand 2:
Subject to spare capacity normal direction:
Subject to spare capacity reverse direction:
Subject to non-negativity:
Where and are constants determined by solving the arc-path formulation of the working capacity allocation model.
Fig. 24. Solution to the arc-path formulation of the path restoration version of the spare capacity allocation model for (spare capacity =75).
Fig. 25. Solution to the arc-path formulation of the path restoration version of the spare capacity allocation model for (spare capacity =90).
When this model is applied to the example problem, the total spare capacity for needed was only 75 compared to 100 and 80 for p-cycle and link restoration, respectively. The solution is illustrated in Figure 24 &25. Of course, a more sophisticated restoration procedure is needed to achieve these savings. The comparison of both node-arc, arc-path formulation of the link restoration, p-cycle and arc-path formulation of the path restoration version of the spare capacity allocation model is illustrated in Figure 26.
Fig. 26. Solution to spare capacity allocation models
JOINT CAPACITY PLANNING
MODEL CHAPTER 6
A joint capacity model is one in which both working and spare capacity can be determined in a single model. In the previous chapter, working capacity was determined with one model and then spare capacity was determined to protect the optimal working capacity against single link failures. Of course, the amount of working capacity on a link determines the amount of spare capacity needed elsewhere to provide for restoration, as a result joint optimization should require less total capacity.
One of the first investigations using a joint capacity model was by Murakami and Kim [25]. A column-generation method was used to obtain new variables as needed. They experimented with a pair of problems from the literature achieving a 10% cost savings for their joint capacity model. A full report of their investigation can be found at Murakami and Kim [26].
Fig.27. Solution to the joint model for (working capacity = 100 and spare capacity = 65)
Fig.28.Solution to the joint model for (working capacity = 100 and spare capacity = 73.5)
The joint capacity model is a combination of the arc-path formulation of the working capacity allocation model and the arc-path formulation of the path restoration version of the spare capacity allocation model. When applied to the example problem, the total capacity to the joint model for needed was 165 compared to 175 for the two-phase approach. This solution is illustrated in Figure 27 & 28. The routing for the traffic demands in the nonappearance of failure is split across multiple paths, which results in a smaller overall spare capacity requirement than was the case with the two-stage approaches considered earlier. The reduction in spare capacity when using a joint capacity model is significant, but comes at the expense of splitting the working traffic routing and, possibly, an increase in the overall working traffic requirements. Table 2 & 3 gives a summary of the results those presented in the preceding sections, on the test case illustrated in Figure 12.
Table 2
Summary of results example problem: |N| = 6, |L| = 9, |D| = 10, |T | = 120, |E| = 18, |U| = 9
Model Working Spare Total
Capacity Capacity Capacity
Node-arc formulation of the working capacity allocation model 100 - -
Arc-path formulation of the working capacity allocation model 100 - -
Node-arc formulation of the link restoration version of the spare 100 70 170
capacity allocation model
Arc-path formulation of the link restoration version of the spare 100 80 180
capacity allocation model
p-cycle spare capacity allocation model 100 100 200
Arc-path formulation of the path restoration version of the spare 100 75 175
capacity allocation model
Joint working and spare capacity model 100 65 165
Table 3
Summary of results example problem: |N| = 6, |L| = 9, |D| = 10, |T | = 90, |E| = 18, |U| = 9
Model Working Spare Total
Capacity Capacity Capacity
Node-arc formulation of the working capacity allocation model 100 - -
Arc-path formulation of the working capacity allocation model 100 - -
Node-arc formulation of the link restoration version of the spare 100 90 190
capacity allocation model
Arc-path formulation of the link restoration version of the spare 100 100 200
capacity allocation model
p-cycle spare capacity allocation model 100 140 240
Arc-path formulation of the path restoration version of the spare 100 90 190
capacity allocation model
Joint working and spare capacity model 100 73.5 173.5
CONCLUSION CHAPTER 7
Protection and survivability are very important problems in optical network. With the rapid development of WDM optical network, protection technology is paid more and more attentions. In the dedicated path protection schemes, spare capacity is reserved for each individual end-to-end lightpath whilst in the shared path protection schemes, spare capacity is shared among multiple lightpaths, as long as those lightpaths do not fail simultaneously. Lightpaths sharing the same backup resources must be path-disjoint. Survivability, or resilience against failure, is critical in today's network operation. Internet service providers typically ensure survivability of their networks via a system of backup capacity, backup routers, and recovery mechanisms.
