Graph independent field size bounds on failure protecting network codes

Erika Bérczi-Kovács


Network coding is an information transmission method with several possible advantages compared to simple routing. Specifically, possible arc failures of a network during a multicast transmission can be tackled by a failure protecting network code, which requires minimal occupation of the network but enables instant recovery. In this paper we show efficient algorithms and lower field size bounds for network code construction that protects any set of arc failures of size at most d. Best known results from Harvey, Karger and Murota gave a polynomial time algorithm for failure protecting network code construction. we give a better lower bound on the required field size that is a function of |T|, k and d, where T is the set of receivers and k denotes the number of messages sent in the network. This new bound is independent of the network size, and also yields a faster algorithm for the problem. The proof is based on results from network encoding complexity and uses similar techniques as Rouayheb, Soljanin and Sprintson.

Bibtex entry:

AUTHOR = {B{\'e}rczi-Kov{\'a}cs, Erika},
TITLE = {Graph independent field size bounds on failure protecting network codes},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-01}

Last modification: 13.3.2018. Please email your comments to Tamás Király!