1. Introduction

With the development of WDM technology, the traffic volume carried in a single wavelength has reached tens of gigabits per second. That endues the survivability characteristic more significance as a single element failure in the optical network can lead to a large amount of data loss that traverses it. The strategies providing survivability are generally classified into two categories: protection and restoration [1]. The main difference between the two concepts lies in the occasion when the backup path is setup. In protection, the detour backup path is preplanned and reserved during call setup. In restoration, no redundant resource is reserved for a light path until a failure occurs that interrupt the traffic. Although the restoration scheme has better resource utilization, the slow service recovery time prevents it from being employed in time-critical services [2]. Moreover, no enough resources are guaranteed in restoration when there is a heavy traffic load in the network. In this paper, we focus on the protection strategy.

1.1 Protection classification and defects

Protection strategy has two main paradigms: path protection and link protection [1], which can be further classified into dedicated path/link protection and resource shared path/link protection. In path protection paradigm, two node-disjoint routes between the source and destination are established during the call setup. In dedicated path protection, or 1+1 path protection, the traffic is transferred concurrently on both of the working path and the protection path. While in resource shared protection, or M:N protection, the backup resource can be shared among multiple traffics that will not interrupted by a single failure. In dedicated path protection, the network failure is protected automatically without any signaling process, however, with low resource utilization. While in shared path protection, when a failure interrupting the traffic is detected, a failure indicator signal (FIS) will be sent from the detecting node to the coordinator, namely the source node, to redirect the traffic to protection path. Shared path protection optimizes the resource utilization; while on the other hand, it gives a poor scalability in recovery time. The recovery process mainly consists of the FIS signaling and the optical switching action consecutively. With the increasing number of nodes in a light path, the signaling time from the failure-detecting node to the source node increases proportionally. Thus the QoS demand for short recovery time is not easily guaranteed in large-scale networks using shared path protection. In link protection paradigm, for each link of two neighboring nodes on the working path, a detour is reserved to provide protection. Dedicated link protection and shared link protection are distinguished from whether the resource is shared among different working paths. Link protection gives a fast failure recovery in case of single link failure, but is opposed for too much spare resources pre-allocated and lack of node failures protection.

1.2 Sub-path protection

To overcome the above shortages of path protection and link protection, some proposals have been presented for sub-path protection. The basic idea of sub-path protection is to divide the light path to several segments, each of which has its local detour sub-path. When a failure occurs in one segment, the protection process will be done within the local protection sub-path, not affecting other segments.

Although sub-path protection has the advantages in scalability and flexibility in provisioning protection, some issues around it are still under discussion, such as sub-path segmentation strategy and the domain border node (DBN) failure protection. From the segmentation aspect, sub-path protection can be classified to Uniform Sub-path and Non-uniform Sub-path [6]. In Uniform Sub-path protection, the working path is divided into segments of length h except for the last segment with length less than or equals to h. In Non-uniform Sub-path protection, the segmentation is based on some criteria to divide the working path into various lengths of segments. Uniform Sub-path protection can guarantee the recovery time and simplify route computation, but is suffered with high block probability in practical topology. Non-uniform Sub-path protection can dynamically divide the working path according to the network topology, but needs complicated calculation. Network partitioning is one way to decrease the calculation complexity in Non-uniform Sub-path protection. But network partitioning has the problem lacking the domain border node (DBN) failure protection. The domain border node refers to the node at the end of one segment and beginning of the next segment. If both of the working and protection sub-paths traverse this node, the failure of the node can not be protected. We focus on the network partition method of Non-uniform Sub-path protection.

1.3 Our contribution

In this paper, we present DBN-pair based network partition for sub-path protection to solve the above problems. In this scheme, we assumes a set of the network partition criteria, which require that only pairs of linked DBNs can exist in the intersection of two neighboring domains. Using our network partition criteria, the protection sub-path calculation is simplified and the adaptability to different topologies is enhanced. We also developed the ILP formulation for calculation of network partition configuration. Specifically, a new algorithm called Sub-Path InCorporatE (SPICE) is presented to remedy the flaw of previous proposals in lack of DBN failure protection. Our simulation results show that our new scheme gives better performance in terms of blocking probability, resource utilization, and recovery time scalability than end-to-end path protection.

The rest of the paper is organized as follows. Section 2 surveys the related work. Section 3 presents our DBN-Pair based Network Partition scheme on sub-path protection, where 3.1 proposes the network partition criteria, 3.2 resolves the problem using ILP formulation, and 3.3 presents the protection architecture. Section 4 analyzes our simulation results and Section 5 concludes the paper.

2. Related work

In this section, some key efforts for sub-path protection will be briefly reviewed. The early research for sub-path protection in WDM networks can be found in [4]. The authors in [4] present the concept to divide the primary path into segments and to provide protection for each segment individually.

Around the basic idea, some theoretical problems are discussed. In [8], the authors prove that if the two link-disjoint paths exist between a source-destination pair, the segmented protection is always possible, but not end-to-end protection. In [6], the authors made a classification of protection techniques including path and sub-path protection. They prove that the sub-path protection gives a better performance in recovery time than path protection.

Some feasible schemes are also presented for realizing the sub-path protection. In [9] the authors design a Reachability Model to calculate the route of sub-path protection for multi-granularity traffic. In [10], the Integer Linear Program (ILP) and heuristic models are presented for shared segment protection.

Some other proposals give an alternate way to solve the sub-path protection problem. In [3] the authors draw an outline of network partition based sub-path protection. Network partition scheme avoids the complicated route calculation, like ILP iteration, on receiving every connection request. However, the embryo proposal in [3] cannot guarantee the protection of node failures at the domain borders, and no mature method is given to partition a network into protection domains. Another proposal of network partition is presented in [5]. The authors partition the network into overlapped areas to enable resource sharing among neighboring protection domains.

Generally, the above approached for sub-path protection can be categorized as two models: Model 1: In this model, each working path is dynamically divided into overlapped segments [8] as shown in Fig. 1(a). The working path is A-B-C-D-E-F-G-H, which is divided into A-B-C-D (WP1), C-D-E-F (WP2), and E-F-G-H (WP3). WP1 is protected with protection sub-path A-X-Y-Z-D (PSP1), WP2 protected with C-M-N-O-P-F (PSP2), and WP3 protected with E-O-P-Q-R-H (PSP3). Each two neighboring segments have an overlapped link to enable mutually protection of the end node failure, like C, D between WP1, WP2, and E, F between WP2, WP3.

This model has the defects of long latency in connection provisioning and topology dependence [3]. Some iteration methods, like Integer Linear Program (ILP), can be used for route computation. But this process must be repeated on each connection request and the complexity increases fast when the network scale becomes larger. That leads to a long delay in call setup. Another problem is that this model is based on special topology structure. For example, it requires the topology has two consecutive nodes whose degree is larger than 3 on the working route, as C and D in Fig. 1 (a). The degree of a node refers to the number of nodes directly attached to it. This case is not always possible in some topologies.

Model 2: In this model, the whole network is statically partitioned into protection domains [6]. Each inter domain connection is automatically divided into segments at the domain border nodes (DBN) that it traverses, as shown in Fig. 1(b). In this model, the protection sub-path is required to route through the same DBN as the working path. The route computation is simplified, as there is no protection interaction among the domains. Some simple routing algorithm, like Dijkstra’s for instance, can calculate all the working and protection paths. But the defects of this model are obvious as follows. First, the domain border node (DBN) is the joint node of the working path and protection path, so no protection is provided for DBN failures. Besides, this proposal requires that the DBN has a degree no less than 4, and in each domain there are at least 2 links connected to it. These requirements may be not satisfied in some topologies.

 

Fig. 1. Sub-path protection models

Download Full Size | PDF

3. DBN-Pair based network partition

Based on the above analysis, the network partition model for sub-path protection has the advantage of simplified route calculation and quick light path provision over the segmentation model in Section 2. The problem of the network partition model lies in lack of protection for DBN failures. Further, no mature algorithm has been carried out for network partition. In this section, we present a new network partition scheme based on DBN-pair. This scheme solves the DBN failure protection problem and is adapted in various topologies. First, we give the network partition criteria assumption, and then present the ILP formulation to solve the partition problem. We also illustrate the protection architecture to adapt all routing scenarios, where SPICE algorithm is present to solve the problem of DBN failures protection.

3.1 Network partition criteria proposal

Partitioning the whole network into protection domains can effectively reduce the route computation complexity [3, 5]. But legacy network partition schemes do not take account for the variation of network topology and the DBN failure protection.

To cover the DBN failure protection and adapt different routing scenarios, we proposed the DBN-pair network partition criteria. Under the criteria, the network is partitioned into overlapped domains, so that the DBNs shared by the neighboring domains are linked as pairs. Fig. 2 shows the partitioning model of our proposal.

 

Fig. 2. The DBN-pair based network partition

Download Full Size | PDF

This proposal is evoked from two aspects: the segmented sub-path protection (segmentation model in Section 2), and overlapped partition strategy [5]. First, the segmented sub-path protection uses overlapped segmentation of working path to enable mutual protection for the end nodes of neighboring segments. The two end nodes form the prototype of our DBN-pair. Second, [5] gives a concept that two domains may be overlapped partitioned to share nodes and links. The two ideas lead us to the proposal of the DBN-pair based network partition criteria.

To test the feasibility of our assumption of the criteria, we have developed the ILP formulation to resolve the partition problem and present the protection architecture in the latter sections. At last, we evaluate its performance by simulation.

3.2 ILP solution for DPNP

We formulate our network partition criteria as an ILP problem. Our target is to find the nodes contained in each domain. The input includes the network topology and the upper threshold of the recovery time for failures. For the convenience of calculation, we translate the topology to a neighboring relation table of link l to node n as T_l,n. T_l,n=1 denotes that link l is attached on node n and vice versa. The recovery time is the proportional function of the length of protection sub-path, which is confined by the number of nodes or links contained in a domain. So the relation between the recovery time and the domain scale can be found out. To constrain the scale of the domains partitioned, we define N _max as the maximum number of nodes, and L _max as the maximum number of links in a single domain. To avoid getting the domains with larger diameter with fewer links, we should adjust the proportional relation d=L _max/N _max. For sake of convenience, we consider the uniformly distributed mesh topology, which is also representative in practice. In such topologies, fixing the average degree of the nodes, or D _avg, we can approximately get the appropriate relation d to guarantee the average degree of the nodes in the domains to be no less than D_avg. Thus each domain partitioned is also a uniformly distributed mesh topology like the whole network. Based on this, the domains with fewer links and larger diameter will be avoided. So we can get N _max and L _max according to the upper threshold of the recovery time.

Given the network topology of a undirectional graph G=(V, E), where V is the node set and E is the link set, we define some binary flags as below: X_n,st=1 (s≠t) if node n is in the intersection of domain s and t; Y_n,s=1 if node n is in domain s; U_l,st=1 (s≠t) if link l is in the intersection of domain s and t; W_l,s=1 if link l is in domain s; D_s=1 if domain s exists. Otherwise the flags are set 0.

The ILP formulation for our partition criteria is given as below:

Objective: Minimize ∑_sD_s+α∑_s≠t∑_l∊EU_l,st

Subject to:

(1). ∑_lW_l,s≤L _max,∀_s. This constrains that in each domain the total number of links is below the preset threshold L _max;

(2). ∑_nY_n,s≤N _max, ∀_s. This constrains that in each domain the total number of nodes is below the preset threshold N _max;

(3). ∑_sW_l,s≥1, ∀l∊E. This means each link l belongs to at least one domain;

(4). ∑_s≠tX_n,st≤1, ∀n∊V. This constrains that one node can be shared by no more than two domains. This constraint is not indispensable in our formulation, but with it a relatively simpler partition result will be obtained;

(5). W_l,s≥T_l,nT_l,m(Y_n,s+Y_m,s-1), ∀l∊E, ∀n≠m∊V, ∀s. This means if node n and m are contained in the same domain s, and are connected by link l, then link l belongs to domain s;

(6). Y_n,s≥W_l,sT_l,n, ∀n∊V, ∀l∊E, ∀s. This means if link l is in domain s and l is attached to node n, then node n must be in domain s;

(7). Y_n,s≤∑_lW_l,sT_l,n, ∀n∊V, ∀s. This means if node n is in domain s, then this node has at least one link contained in domain s;

(8). X_n,st≥Y_n,s+Y_n,t-1, ∀n∊V, ∀s≠t. This means if node n is contained in both domain s and t, then X_n,st=1;

(9). U_l,st≥W_l,s+W_l,t-1,∀l∊E, ∀s≠t. This means if link l is contained in both domain s and t, thenU_l,st=1;

(10). U_l,st≤W_l,s;U_l,st≤W_l,t, ∀l∊E, ∀s≠t. This means if link l is not in domain s or t, thenU_l,st=0;

(11). X_n,st+X _m,st≥T_l,nT_l,m(Y_n,s+Y_m,t-1), ∀n≠m∊V, ∀s≠t. This constrains if the link l between node n and m connects domain s and t, then domain s and t must overlap with each other at node n or node m or both.

(12). ∑_lU_l,stT_l,n≥X_n,st, ∀n∊V, ∀s≠t. This constrains if node n is in the intersection of domain s and t, then this node has at least one link contained in the same intersection.

(13). ∑_l∑_m(Y_m,s-X_m,st)T_l,nT_l,m≥X_n,st, ∀s≠t. This constrains if node n is in the intersection of domain s and t, there exists at least one node m connected to n by link l in domain s, but node m can not belong to domain t.

(14). W_l,s≤D_s, ∀l∊E,∀s. This means domain s is a valid domain if any link belongs to it.

End ▪

The objective of the formulation is to minimize the total number of domains partitioned and the number of links in the intersection of the domains. The coefficient α is used to adjust the contribution proportion of the number of shared links to the whole result. Commonly we can set α to 1/|E|, where |E| is the number of total links. By increasing α we can reduce the number of shared links among neighboring domains, but the number of domains may increase.

The constraint (1) and (2) limits the scale of each domain. Constraints (3–7) state the basic rules of nodes and links in a domain that can exist according to the given topology. Constraints (8–10) come from the definition of X_n,st and U_l,st. Constraint (11) guarantees that each two neighboring domains must be overlapped with each other. Constraints (12) and (13) express the feature of our partition criteria, which demands that only DBN pairs can exist in the intersection of overlapped domains. That implies in (12), if there is a node in the intersection, at least one link attached to the node is also contained in the same intersection, and in (13), if there is a node in the intersection of two domains, the node must have at least one unshared link in each domain respectively. At last, constraint (14) denotes the existence of a domain if any links belong to it.

We run our ILP formulation for 18 nodes and 32 nodes NSFNET with the free ILP software, lp_solve [11], with a PC with the CPU of P4 2.4GHz and RAM of 512MB. Table 1 shows the input parameters for our partition formula and the time consumed for each calculation. Fig. 3 (a–d) shows the partition results under each condition. For NSFNET with 18 nodes, the whole network is partitioned into 2 protection domains, which are overlapped at the DBN-pair (6, 8) and (11, 14) when we restrict N_max=12 and L_max=17. While if we restrict N_max=9 and L_max=13, the network must be partitioned into at least 3 domains, with DBN-pair (2, 4) between domain 1 and 2, (11, 14) between domain 1 and 3, and (10, 12) between domain 2 and 3. It is the same for NSFNET with 32 nodes, with a longer calculation time. It is not a problem for us to get the result with a reasonably long time, as the calculation needs to be done only once for a topology and given parameters.

Table 1. Network partition input parameters for the ILP formulation

View Table

 

Fig. 3. Network partition results using our ILP formulation by lp_solve software, where each cloud or dotted line indicates a protection domain

Download Full Size | PDF

3.3 Protection architecture for DPNP

In most of the previous schemes, there are always some restrictions in route selection. In [4] the authors constrain that the working route must traverse two consecutive nodes with the degree no less than 3 at the domain borders. In [3] the authors only deal with the conditions where the DBN’s degree is larger than 4. To eliminate such routing dependency, our scheme adapts to each routing situation and eliminates the constraints in routing. Therefore, the application scale is widened and the route computation is optimized. In our scheme, the protection architecture consists of two routing scenarios, as illustrated below.

Routing Scenario 1: The working path traverses both of the nodes of the DBN pair in the intersection of two neighboring domains. Fig. 4 shows part of the NSFNET in Fig. 3(d), where (A, B) is the DBN pair (12, 17) between domain 1 and 2. The working path from S to D traverses both A and B at the domain border. In this case, working path segment S-7-6-A-B (WP1) and A-B-16-D (WP2) are overlapped at this DBN pair. Using the Dijkstra’s algorithm, the protection sub-path in Domain 1 may be chosen as S-3-5-9-B (PSP1), and in Domain 2 A-14-21-D (PSP2). The failures in WP1 can be protected by switching the traffic to PSP1, and the failures in WP2 can be protected by PSP2. As each DBN is within one segment, the DBN failure is protected automatically.

 

Fig. 4. Scenario 1: the working route traverses both of nodes of the DBN pair

Download Full Size | PDF

Routing Scenario 2: The working path traverses only one node of the DBN pair. Fig. 5 shows part of the NSFNET in Fig. 3(d), where (A, B) is the DBN pair (22, 21) at the intersection of Domain 2 and 3. The inter-domain working path traverses only node A at the border of the domains. From our network partition criteria, node B is on a parallel route connecting the two domains. Thus the protection sub-paths may be selected with Dijkstra’s algorithm as S-12-14-B-A (PSP1) for segment S-16-A (WP1) in Domain 2, and A-B-28-27-D (PSP2) for A-29-D (WP2) in Domain 3. In normal protection procedures, the failures within WP1 can be notified to the coordinator, namely the source node S, to switch the traffic to PSP1 and the failures within WP2 can be notified to A to switch the traffic to PSP2 for protection. But if the node A encounters a node failure, neither PSP1 nor PSP2 could give a hand to protect it.

 

Fig. 5. Scenario 2: the working route traverses only one node of the DBN pair

Download Full Size | PDF

We present the algorithm SPICE to solve the DBN failure protection problem. The basic idea of SPCIE is to combine the two neighboring protection sub-path to bypass the failed DBN. The Sub-Path InCorporatE (SPICE) algorithm can be described as below.

Definitions:

WorkDBN: the DBN on the working path;

ProtectDBN: the DBN on both of the two neighboring protection sub-path;

Coordinator: the node responsible for switching the traffic from failed working segment to the protection sub-path;

InterNode: the intermediate nodes in a segment, excluding the two end nodes;

FIS: the failure indication signal that tell the coordinator to trigger protection;

Event definitions:

WORK_DBN_ DOWN: the WorkDBN encounters a node failure;

DBNS_LINK_DOWN: the link between the two DBNs is down;

DBNS _LINK_UP: the link between two DBNs is up;

INNER_ FAILURE: the intermediate link or node in a segment encounters a failure;

FIS_RECV: a Failure Indicator Signal (FIS) is received.

Algorithm:

while (SYSTEM_IS_RUNNING) do

switch Event:

case WORK_DBN_ DOWN:

ProtectDBN: Switch the optical cross-connect to combine the two protection sub-path into a large one;

InterNode: Send FIS to coordinator to trigger protection;

case DBNS_LINK_DOWN:

ProtectDBN: Switch the optical cross-connect to combine the two protection sub-paths into a large one;

case DBNS_LINK_UP:

ProtectDBN: Switch the optical cross-connect to disjoin the combined large protection sub-path into two individual ones;

case INNER_ FAILURE:

InterNode: Send FIS to coordinator to trigger protection;

Coordinator: Switch the traffic from the working segment to protection sub-path;

case FIS_RECV:

InterNode: Relay this FIS message toward coordinator;

Coordinator: Switch the traffic from the working segment to protection sub-path;

end switch;

end while;

This algorithm defines four node types, the WorkDBN, the ProtectDBN, the Coordinator, and the InterNode. In the example of Fig. 5, on detecting the failure of the link to the WorkDBN, the ProtectDBN, or node B, regardless whether it is caused by the failure of node A or by a fiber cut, just switches the optical cross-connect to combine the PSP1 and PSP2 into a large protection sub-path. If the InterNode, namely node 16 in Fig. 5, detects the failure of the link to A, FIS will be sent to the Coordinator, node S, along the working path. On receiving FIS, the Coordinator switches the traffic to protection sub-path. In case of WorkDBN failure, the ProtectDBN, or node B, the InterNode, or node 16, and the Coordinator, or node S, will act as above, and the traffic will be protected by the new sub-path, for instance, S-12-14-B-28-27-D. In case of other link or node failures, only the InterNode and the Coordinator act as above to protect as normal sub-path protection process.

SPICE algorithm solves the problem of DBN failure protection. The precondition for SPICE is that the protection sub-paths could be found. That is, if in a domain the protection sub-path is node-disjoint with the working path, SPICE can give full protection for both nodes and links failures, including DBN. While if the protection sub-path is links-disjoint with the working path, SPICE can give protection for link failures and DBN failures.

The major advantage of DPNP lies on three aspects as below. First, an ILP formulation is given for calculation of network partition. By adjusting the input parameters, we can get the desirable partition result to guarantee QoS demand of recovery time in case of network failures. Second, the route computation can be simplified and optimized with fewer restrictions in our scheme. Using our network partition criteria, each free selected working path is adapted for sub-path protection. Finally, the problem of DBN failure protection is solved using our SPICE algorithm in each routing scenarios. This algorithm, based on our network partition criteria, utilizes the DBN-pair to flexibly join or disjoin the protection sub-paths to protect DBN failures.

4. Performance evaluation

To evaluate the performance of our DBN-pair based sub-path protection scheme, we develop a discrete-event simulation tool based on the NS-2 [12] platform. We implement the protection models, including our DBN-pair based scheme and end-to-end path protection scheme. The network connection blocking probability, resource utilization, and average recovery time are investigated. The simulation is conducted on the 32 nodes NSFNET as shown in Fig. 3 (d). Each link in the network is supposed bidirectional and the number of wavelengths on each fibre is set to be eight. No wavelength conversion is available in the network. The light path connection requests arrival rate at each node is a Poisson process, and the connection duration is negative exponentially distributed. Each node has the same probability as others to be selected as the source or destination of a connection. The shortest path first (SPF) algorithm is used to find the optimal route for working path and protection path/sub-path. We assume that the administrative policy requires the working path and protection path/sub-path to be node-disjoint.

Figure 6 shows the blocking probability of DBN-pair based sub-path protection scheme and end-to-end path protection scheme with respect to traffic loads over the network. This figure indicates that in case of medium or light traffic load, our scheme gives a higher connection success ratio than end-to-end path protection.

 

Fig. 6. Connection blocking probability comparison

Download Full Size | PDF

Figure 7 shows the relationship of the amount of links used and the number of connections, given the traffic load at 10 Erlangs. With the increasing number of connections, much fewer links are used in our DBN-pair based scheme than path protection. This figure proves the higher efficiency of our scheme in term of network resource utilization.

 

Fig. 7. Resource utilization efficiency comparison

Download Full Size | PDF

Figure 8 shows the average recovery time of 2000 connections under different traffic loads when applying our novel scheme and the path protection scheme. We assumed that the failure detection time T_d=10µs, the FIS propagation time per link T_l=0.2ms, the time used to process the FIS T_p=0.2ms, and the optical cross-connect configuration time T_c=2ms. Given the average number of links on the protection path be N_lp, the recovery time can be estimated as T_r=T_d+2×N_lp×(T_l+T_p)+T_c. In our DBN-pair based network partition scheme, the average number of protection sub-path is limited by the size of the domain, so the recovery time scalability of DPNP is proved.

 

Fig. 8. Average length of protection path and according failure recovery time

Download Full Size | PDF

5. Conclusions

In this paper, the DPNP for sub-path protection scheme has been proposed to enable full-scale and routing independent protection. In this scheme, we proposed the network partition criteria and ILP solution for network configuration calculation. We also analyzed the protection architecture of all routing scenarios, where the signaling procedures are illustrated, including SPICE algorithm for DBN failure protection. The major advantage of our work is enhancing the recovery time scalability and simplifying the route computation complexity in sub-path protection paradigm. DPNP scheme can also provide guidance in designing large scale networks. We conducted the simulation on 32-node NSFNET for our DPNP and end-to-end protection. The simulation results show that DPNP gives better performance in terms of blocking probability, resource utilization, and recovery time.