Diversity Coding in Two-Connected Networks

Babarczi, Péter and Tapolcai, János and Pasic, Alija and Rónyai, Lajos and Bérczi-Kovács, Erika and Médard, Muriel (2015) Diversity Coding in Two-Connected Networks. IEEE/ACM Transactions on Networking. pp. 1-10. ISSN 1063-6692 (Submitted)

Text ToN coding submitted.pdf - Submitted Version Restricted to Registered users only Download (301kB)

Abstract

In this paper we propose a new instantaneous recovery scheme against single edge failures for unicast connections in transport networks. The new scheme is a generalisation of diversity coding where the source data AB is split into two parts A and B and three data flows A, B and their exclusive OR (XOR) A+B are sent along the network between the source and destination node of the connection. By ensuring that two data flows out of the three always operate even if a single edge fails, the source data can be instantaneously recovered at the destination node. In contrast with diversity coding we do not require the three data flows to be routed along three disjoint paths, but each data flow is allowed to split into two parallel segments if needed, forming a directed acyclic graph. We show that our Generalised Diversity Coding (GDC) scheme requires only the theoretically minimal bandwidth, and thus can be used in sparse but still 2-connected network topologies. Our proof is based on the theory of network coding, but using a graph theoretical toolset. In particular we show that when the source data is divided into two parts, robust end-to-end intra-session network coding against single edge failures is always feasible. We present linear-time robust code construction algorithms for this practical special case in optimal coding graphs. We further characterise this question, and show that by increasing the number of edge failures and source data parts we lose these desired properties.

Actions (login required)

Edit Item