P2 Cycle in WDM Networks

Abstract

The Failure Independent Path Protection (FIPP) p cycle is efficient scheme. If failure occurs in pre configured cycle it is protection is reconfigured between those two nodes. In this paper we use Parasitic Protection Links (PPL). PPL’s are p-cycles with have attached links. PPL’s are used to protect the not only failure nodes but it connected to PPL to cycle. P² cycle is known as p cycle with parasitic protection links.

We address The P²– cycle in mesh networks can be analysed by using single link failure. We further propose two P²-cycle based heuristic algorithms, Strict Routing Protection (SRP) and Flexible Routing Protection (FRP), to address the dynamic traffic case. In the dynamic case, both SRP and FRP outperform FIPP p-cycle schemes in terms of blocking probability in most scenarios considered. In general, the P²-cycle protection scheme outperforms the p-cycle based in terms of capacity efficiencies which being slightly slower in terms of traffic recovery speed.

Key words: Parasitic Protection Links (PPL), Strict Routing Protection (SRP), Flexible Routing Protection (FRP).

INTRODUCTION

Network survivability, defined as the Continuous operations of network are performed in case failure occurred in the network [3]. In generally optical networks carry information in terabytes. A failure in network causes lot of loss of data. Ring based networks can easily come due to their structure and fast recovery management. In ring based it takes 50-60ms but it gives capacity redundancy high. As mesh based networks emerged, more capacity efficient protection schemes were proposed which allow backup capacity sharing. These schemes are into three categories: link-based, segment-based and path-based [29].

Link-based protection schemes produce the fast traffic recovery speed but suffer from the worst resource efficiency .

Best resource efficiency is achieved by path based protection scheme. Shared Backup Path Protection (SBPP) is one of the path protection schemes. it is high capacity. upon a network failure. It takes long time o recover from traffic. Segment based protection schemes lie between the link-based and path-based schemes, and offer a better combination of bandwidth efficiency and recovery time.

Path-based protection schemes usually achieve the best resource efficiency. Among them, a path protection scheme, namely, Shared Backup Path Protection (SBPP), was shown to be the most capacity efficient protection scheme [8]. However, it suffers from long traffic recovery time upon a network failure. Segment based protection schemes lie between the link-based and path-based schemes, and offer a better combination of bandwidth efficiency and recovery time .

The pre-configured protection cycle is known as p-cycle, combines the good qualities of mesh and ring based protection schemes and achieves the recovery speed of ring- based with the capacity efficiency of mesh protection. P-cycle has been proven theoretically to be the most efficient pre-configured protection scheme in terms of capacity efficiency and recovery speed .

Dynamic Traffic Scenarios

In dynamic traffic without the prior knowledge of arrival time of future requests. Due to the pre-configuration property of traditional p-cycles, it is extremely difficult to re- provision all the protection cycles whenever a new session arrives in order to minimize overall cost. Each provisioning takes large computation cost and complex network reconfiguration. Therefore, most of the work in the literature assume that established p-cycles should not vary with time or traffic. The authors in proposed three different routing algorithms along with link-based p-cycle protection scheme to deal with dynamic traffic. The results indicate that the proposed p-cycle based design performs better than SBPP in dense networks but worse in sparse networks. Protected Working Capacity Envelopes (PWCE) is another method to address dynamic traffic scenarios. It divides the entire network into two partitions: working and protection. Both static and dynamic traffic can be accommodated as long as the total traffic do not exceed the limit of working envelopes.

Although some decent results have been shown in the literature, p-cycles still have such intrinsic weakness in dealing with dynamic traffic. If an incoming session whose end nodes do not lie on any cycle, it cannot be protected and a new cycle has to be constructed to protect this session, or the existing cycles must be reconfigured. An example shown in Figure 4.2 illustrates such weakness and also reveals the advantage of P2-cycles. In Fig. 4.2(a), session1 has been provisioned and protected by cycle C1(E–C–B–F–E). As session 2 arrives, the primary path of session 2 is provisioned as P2(A–B–C–D). Under FIPP p-cycle scheme, cycle C1 cannot protect it and thus a new cycle C2(A–B–C–D–E–F–A) is constructed to protect it as shown in Fig.4.2(b). However, instead of building a new cycle, using P2-cycle approach we can add two PPLs (A,F) and (D,E) to connect the end nodes of P2 such that C1 can also provide a protection segment (A–F–E–D) for P2 as shown in Fig.4.2(c). Therefore, both sessions are protected by a P²-cycle with much less cost.

Fig 1: P²-cycle deals With Dynamic Traffic

Problem Statement

In dynamic traffic scenarios, a WDM mesh network is given with network resources, such as the maximum number of wavelengths and the cost on each span. Each traffic request arrives to the network in a dynamic fashion such that it needs to be considered individually based on the current network status. The network status consists of the detailed working and available wavelengths on each span as well as all the accepted sessions and P²-cycles provisioned in the network.

Given a network modelled as an undirected graph G = (V;E) where each undirected span e2E has a cost ce, the current network which includes the currently used and available wave- lengths on each span e, each accepted session l and their protection P²-cycles. Provision incoming unicast sessions against any single-link failure with the minimum overall blocking probability by using P²-cycle scheme. The assumptions required in this dynamic traffic case are the same as that in the static case.

We design two heuristics to address the dynamic traffic case. In the first method, named Strict Routing Protection (SRP), the primary and protection path for each incoming session are computed separately. The primary path is firstly provisioned using Dijkstra’s shortest routing algorithm. Based on the primary path, either an existing P²-cycle or a new cycle is found to protect it. In the second method, named Flexible Routing Protection (FRP), the primary and protection paths of an incoming session are constructed jointly. The existing P²-cycles will be preferred to being used first. If no existing one is able to protect the session, a new cycle will be formed. We allow spare capacity sharing between different sessions to increase the capacity efficiency.

A. Strict Routing Protection (SRP):

The motivation of SRP is to always choose the shortest path to route the primary traffic in order to leave more spare capacity for protection, since the capacity used for primary path cannot be shared among different sessions. And then we check whether any available P² cycle can be exploited to protect this newly established session. Once being set up, the cycle for a P²-cycle cannot be changed.

The protection links that are added to PPL’s are one hop away from end nodes. The detail of the algorithm SRP described in following steps:

1. As a new session dl(sl; tl) arrives, establish the primary path fl between sl and tl under current network status by using Dijkstra’s algorithm. If it fails, the session is blocked;

2. Sort all the existing P²-cycles, cp € C, in the increasing order of (dl; cp), which is One hop indicates that there exists a span in the network that connects a node to the cycle. If (dl; cp) = infinite 1 for all cp € C, then no existing cycle is able to protect this new session. Thus, a new cycle needs to be constructed to protect dl.

3. For each existing protection cycle, cp, we construct a temporary graph G0, consisting of only the cycle spans of cp and all the spans connecting the source and destination nodes of l to the cycle . All the spans used by fl should be removed to ensure that its protection path is link-disjoint. Then, all the sessions protected by cp are checked and if an existing session in D can share the same cp with the new session l, we should make sure that either their primary paths or their protection paths are link-disjoint. we remove the protection paths of all the sessions in D whose primary paths are not link-disjoint with fl. If a protection path can still be found in the remaining G0 this protection path will be ql for l. Accordingly, the protection cycle is also determined, which should be updated if some PPLs are also used.

4. If every existing cp fails to protect dl, a new cycle will be constructed to protect it. We first attempt to find two diverse paths to form a cycle that is link-disjoint to fl. If such cycle cannot be found, then we find a path, ql, link-disjoint to fl and the cycle is formed by combining ql with fl.

B. Flexible Routing Protection (FRP):

Different from SRP, the flexible routing protection scheme considers primary and protection paths jointly for each arriving session. Instead of determining the primary path in advance, we examine each existing P²-cycle and find each potential protection path along the cycle that can connect the source and destination. For each potential protection path, we try to discover a primary path for it. If it succeeds, the session is accepted. Otherwise, a new cycle is constructed to protect the session.

Flexible Routing Protection (FRP) Scheme

Algorithm FRP is explained in following steps:

1. Given a new session dl(sl; tl), all the available P²-cycles cp € C are sorted in the increasing order of (dl; cp).
2. For each available cp, list all the possible protection paths for dl. If the end nodes sl and tl are on the cycle, there are two possible segments along the cycle. If sl or(and) tl is not on the cycle, the path will be composed of parasitic links connecting sl or tl to the cycle and an on-cycle segment. We assume the average node degree in a given network is denoted by µ. Each cycle can provide two on cycle segments between any pair of on-cycle nodes. Each end node, sl or tl, can be connected to the cycle by at most µ PPLs given the node degree µ. Hence, the average number of candidate protection paths provided by any P2-cycle
3. For each candidate ql, run Dijkstra’s algorithm to find a primary path fl in G that is not only link-disjoint to ql but also link-disjoint with other primary paths protected by the same cycle if their protection paths are not link-disjoint. If it succeeds, we store the combination < cp; ql; fl> in a temporary set T, which is initialized as ;. After checking all the existing P²-cycles, we check set T and find the combination < cp; ql; fl > with minimum cost of fl. We recover the spans removed from G and update the network status. If no existing P²-cycle can be used to protect session dl, we use Bhandari’s algorithm to find two link-disjoint paths between si and ti to form a new P²-cycle. If it fails, the session is blocked. Otherwise, the session is accepted and one of the paths (usually the shorter one) is used as the primary path fl, and the network is updated.

Results for Dynamic Traffic

Based on two P²-cycle protection algorithms, SRP and FRP, proposed for provisioning dynamic requests, we conduct a simulation study to compare the performance of these algorithms under dynamic traffic. The networks used in the simulations are NSFNET, COST239 and USNET, in which USNET network, shown in Fig. 2 has 24 nodes and 43 edges and the average node degree is 3.58.

Fig.2 USNET(24 nodes, 43 edges)

In each simulation run, 1000 randomly generated unicast requests are loaded to the network sequentially and the reject ratio is recorded. The arrival of traffic follows Poisson distribution with ¸ requests per second and the duration of an accepted connection is exponentially distributed with a mean of ¹. The traffic load measured in Erlangs is λµ Each connection requires an entire wavelength to transmit the traffic. The maximum capacity on each network link is set to 16 wavelengths.

Figures 3,4,and 5 show the blocking probability of dynamic traffic using SRP, FRP and FIPP p-cycle in NSFNET, USNET and COST239 networks, respectively. Each point in the figures is the average value of 200 simulation runs for each traffic load. For FIPP p-cycle scheme, the primary path of each arriving connection is provisioned first by using Dijkstra’s algorithm, and then protected by a p-cycle.

Fig 3(a):Comparison of blocking probability in NSFNET(W=16)

Fig 3(b):Comparison of blocking probability in COST239(W=16)

Fig 3(c):Comparison of blocking probability in USNET(W=16)

The results show that both SRP and FRP achieve lower blocking probability than FIPP under most of the network scenarios. In NSFNET, SRP achieves better performance than the other two schemes. In USNET, FRP outperforms SRP and FIPP under every scenarios. In COST239, however, SRP and FIPP achieves the same session blocking ratio, which is better than FRP, when the traffic load is relatively low. As the traffic load increases where the network is very saturated, FRP turns to perform better than SRP and FIPP.

Based on the results, SRP performs better than other two schemes in relatively small and sparse networks at a low level of traffic load. FRP achieves the best performance in larger and denser networks, especially when the network is very saturated. One of the reason that SRP performs better in small and sparse networks, such as, NSF, is that to provision a session always using the shortest path will save some capacity for protection in a long run. Hence, more capacity can be used for protection such that more cycles can be established. in a network with high nodal degree, a cycle is more likely to reach a large group of nodes compared with a sparse network. In this case, FRP has a higher chance to protect a given session by using existing P²-cycles when network load is very high and the network is over saturated.

Fig 4(a).Comparison of NOR in NSFNET(W=16)

Fig 4(b).Comparison of NOR in cost239(W=16)

Fig 4(c).Comparison of NOR in USNET(W=16)

We also studied the average NOR of each accepted connection as in dynamic traffic scenarios and the results are shown in Figures 4(a),4(b) and 4(c). As expected, FIPP achieves the best solution with exact two node reconfigurations for each connection. Meanwhile, SRP also performs better than FRP in three networks. This reveals that connections protected by FRP use more PPLs than those used by SRP, which follows from the basic concept on which the two algorithms are based. It is worth noting that the average NOR achieved by SRP is almost stable below 2.4 in NSF and USNET and 2.7 in COST239. This indicates that most of the connections only need two no reconfigurations upon a network failure, especially in NSF and USNET. FRP has larger average NOR because it iterates every existing p-cycle in the network to protect each session and choose the one with minimum cost but not the one with minimum NOR. Shorter primary paths always results in longer protection paths such that more PPLs are used to protect each session.

Therefore, based on the simulation results, SRP and FRP both achieves the lowest blocking probability than FIPP in most of the network scenarios considered and each scheme has advantage over the other in different network scenarios. SRP has better failure recovery performance than FRP. In dynamic traffic scenarios, the P²-cycle protection scheme is faster protection scheme provides an enhancement of capacity efficiency over the FIPP p-cycle with asmall change in the recovery time.

Extension

The p²-cycles can be extended to link failures can be obtained. If one node can be failed then the data will be passed through alternative paths to reach to the destination. The p²– cycle can be defined as the original p-cycle The protection links that are added to PPL’s are one hop away from end nodes. For p²-cycles the network data can be efficiently transferred to destination which is one hop away from the nodes.

Conclusions

In this paper new p cycle protection is done in mesh based protection networks. By using the parasitic protection links (PPL), FIPP p-cycle can be extended through paths from end nodes which are one hop away from the failure nodes of p cycles. In dynamic traffic scenarios., in dynamic their are two algorithms are proposed Strict Routing Protection (SRP) and Flexible Routing Protection (FRP), to handle dynamic traffic demands in order to minimize the total number of blocked sessions.

In dynamic traffic case the blocking probability less by using algorithms SRP and FRP comparing with FIPP p cycles. The numerical results shows the P²-cycle protection scheme is a more highly capacity efficient than the Failure Independent Path Protection p-cycle scheme in dynamic traffic case. the P²-cycle protection scheme is a more effective alternative of existent p-cycle-based and path-based protection schemes, Considering the factors of capacity efficiency and recovery speed

References

1. D. Zhou and S. Subramanian, “Survivability in optical networks,” IEEE Networks, 2012
2. P. Arijs, B. V. Caenegem, P. Demeester, and P. Lagasse, “Design of ring and mesh based WDM transport networks,” Optical Networks Magazine, vol. 1, no. 3, pp. 27-41, 2011.
3. S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks. Part I-protection,” in Proceedings of IEEE INFOCOM, vol. 2, pp. 744-751, 2011.
4. S.krishna “Survivable WDM mesh network,”, vol. 21, no. 4, pp. 870-883, 2009.
5. P. H. Ho and H. T. Mouftah, “shared protection for optical networks,”
6. IEEE Communications Magazine, pp. 97-103, February 2002.
7. Bharat T. Doshi, Subrahmanyam Dravida, P. Harshavardhana, Oded Hauser, and Yufei Wang, “Optical Network Design and Restoration,” Bell Labs Technical Journal, JanuaryCMarch 1999
8. Caihui Ou, J. Zhang, H. Zhang, L. H. Sahasrabuddhe and B. Mukherjee, “New and Improved Ap-proaches for Shared-Path Protection in WDM Mesh Networks,” IEEE Journal of Lightwave Technology, VOL. 22, NO. 5, MAY 2004
9. Dahai Xu, Y. Xiong and C. Qiao, “Novel algorithms for shared-segment protection,” IEEE Journal of Selected Areas on Communications, v21. p1320-1331, 2003
10. Janos Tapolcai and et al. “A New Shared Segment Protection Method for Survivable Networks with Guaranteed Recovery Time,” IEEE Transactions on Reliability, Vol. 57, pp. 272-282, 2008.
11. W.D D. Stamat, “ Next Generation networks,” in Proc. IEEE ICC’ 98, 1998, pp. 537-543