DIVERSITY CODING IN TWO-CONNECTED NETWORKS
ABSTRACT
In this paper, we propose a new proactive recoveryscheme against single edge failures for unicast connections intransport networks. The new scheme is a generalization ofdiversity coding where the source data AB are split into twoparts A and B and three data flows A, B,andtheirexclusiveOR (XOR) A⊕B are sent along the network between the sourceand the destination node of the connection. By ensuring that twodata flows out of the three always operate even if a single edgefails, the source data can be instantaneously recovered at thedestination node. In contrast with diversity coding, we do notrequire the three data flows to be routed along three disjointpaths; however, in our scheme, a data flow is allowed to splitinto two parallel segments and later merge back. Thus, ourgeneralized diversity coding (GDC) scheme can be used in sparsebut still two-connected network topologies. Our proof improvesan earlier result of network coding, by using purely graphtheoretical tool set instead of algebraic argument. In particular,we show that when the source data are divided into two parts,robust intra-session network coding against single edge failuresis always possible without any in-network algebraic operation.We present linear-time robust code construction algorithms forthis practical special case in minimal coding graphs. We furthercharacterize this question, and show that by increasing thenumber of edge failures and source data parts, we lose thesedesired properties.
PROPOSED SYSTEM:
In this paper we make the following steps towards apractical transport network coding scenario:• The algebraic argument of is a powerful tool formodelling and solving network coding problems. Thework by Rouayheb et al. identifies the graph theoreti-cal nature of the investigated scenario but still focuses onalgebraic properties, such as reducing the field to GF(2).Our insight was to revisit the problem with pure graphtheoretical mindset, and show that in-network coding isactually not required at all.• The coding algorithm in runs in O(|V |) time,because of the computation time of testing the minimalityof the coding graph. Roughly speaking, minimality isimportant only to have a simple coding graph which canbe efficiently handled. To improve the running time weuse a less strict criterion than minimality,2which can beverified in linear time and still results in a sufficientlysimple coding graph. As a result, robust network codescan be constructed in O(|V | +|E|) time for fault-tolerantcoding graphs.• The above simplicity and efficiency makes GDC a viableapproach to provide instantaneous recovery. We furtherdemonstrate that the minimal capacity coding graphs ofGDC can approach the theoretical minimum of capacityrequirement even in 2-connected networks,whereDCalready fails for several connection requests. The trickis that the three data flows A, B and A ⊕ B are routedon three end-to-end routing DAGs instead of disjointend-to-end paths.
EXISTING SYSTEM:
Suurballe’s algorithm provides an edge-disjoint pathpairfor 1+1protection – the simplest and most widespreadinstantaneous recovery approach – in polynomial-time, whichmakes it resilient against single edge failures.11+1does notneed any further code construction for instantaneous recovery,but it allocates an excessive amount of redundant capacity(at least 100% compared to a single shortest path). Diversitycoding (DC) is a promising approach to reducethe high redundancy of 1+1 (from 100% to 50%) by applyingXOR coding at the source. Although core network nodes areintact and only simple coding and decoding is required at theend-nodes, it is beneficial only in transport networks whereeven a third edge-disjoint path exists with a reasonable cost.However, this is rarely the case.The importance of network coding in reducing the capacityconsumption of 1+1 in transport networks has beendemonstrated in several studies indifferent network layers (e.g, electronicdomain). Most of these works assumethat a matrix of traffic demands are given in advance, thus, inter-session network coding can be appliedon the data of different connections. However, recent transportnetwork trends point towards that connection demands arearriving one after another without any knowledge of futureincoming requests. Thus, in these dynamic environments intrasessionnetwork coding is needed for unicast connections,where coding is performed on different parts of the samesource data. Hence, each connection can bedeployed and released independently, while the routing of theother connections remain intac
CONCLUSIONS
In this paper we showed that robust network codes forsingle edge failure resilient unicast connections where userdata can be split into two parts are equivalent with findingthree end-to-end routing DAGs. Built on this observation,we gave linear time algorithms to obtain the routing DAGs infault-tolerant and minimal coding graphs, instead of involvedgadget transformations presented in. We also showedthat such an equivalence between robust network codes andnetwork flow problems may not exist for other transportnetwork scenarios. Through simulations we demonstrated thatthe minimal capacity coding graphs for GDC reach about15-20% resource saving compared to 1+1 protection, whileoutperform DC with 5 -10% even in topologies with a single2-edge-cut. Furthermore, as GDC contains both 1+1and DCas special cases, it is applicable in all network topologies (andeven more) where any of these methods is solvable. Thus,we conclude that GDC might be an alternative of DC in2-connected topologies and its improvement in denser net-works to reduce the resource consumption of 1+1withoutin-network coding.
REFERENCES
[1] Y. Liu, D. Tipper, and P. Siripongwutikorn, “Approximating optimalspare capacity allocation by successive survivable routing,” IEEE/ACMTrans. Netw., vol. 13, no. 1, pp. 198–211, Feb. 2005.
[2] D. Wang and G. Li, “Efficient distributed bandwidth managementfor MPLS fast reroute,” IEEE/ACM Trans. Netw., vol. 16, no. 2,pp. 486–495, Apr. 2008.
[3] M. Medard, R. A. Barry, S. G. Finn, W. He, and S. S. Lumetta,“Generalized loop-back recovery in optical mesh networks,” IEEE/ACMTrans. Netw., vol. 10, no. 1, pp. 153–164, Feb. 2002.
[4] B. Wu, K. L. Yeung, and P.-H. Ho, “ILP formulations for p-cycle designwithout candidate cycle enumeration,” IEEE/ACM Trans. Netw., vol. 18,no. 1, pp. 284–295, Feb. 2010.
[5] S. Rouayheb, A. Sprintson, and C. Georghiades, “Robust network codesfor unicast connections: A case study,” IEEE/ACM Trans. Netw., vol. 19,no. 3, pp. 644–656, Jun. 2011.
[6] P. Babarczi, G. Biczók, H. Øverbyc, J. Tapolcai, and P. Soproni,“Realization strategies of dedicated path protection: A bandwidth costperspective,” Comput. Netw., vol. 57, no. 9, pp. 1974–1990, Jun. 2013.
[7] A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C. N. Chuah, andC. Diot, “Characterization of failures in an IP backbone,” in Proc. IEEEINFOCOM, vol. 4. Mar. 2004, pp. 2307–2317.
[8] A. Fumagalli and L. Valcarenghi, “IP restoration vs. WDM protection:Is there an optimal choice?” IEEE Netw., vol. 14, no. 6, pp. 34–41,Nov. 2000.
[9] E. Ayanoglu, C.-L. I, R. D. Gitlin, and J. E. Mazo, “Diversity codingfor transparent self-healing and fault-tolerant communication networks,”IEEE Trans. Commun., vol. 41, no. 11, pp. 1677–1686, Nov. 1993.
[10] S. N. Avci and E. Ayanoglu, “Link failure recovery over large arbitrarynetworks: The case of coding,” IEEE Trans. Commun., vol. 63, no. 5,pp. 1726–1740, May 2015.