Name
Abstract | ||
|---|---|---|
We consider the problem of establishing reliable unicast connections across a communication network with nonuniform edge capacities. Our goal is to provide instantaneous recovery from single edge failures. With instantaneous recovery, the destination node can decode the packets sent by the source node even if one of the network edges fails, without the need of retransmission or rerouting. It has been recognized that the network coding technique offers significant advantages for this problem over standard solutions such as disjoint path routing and diversity coding. We focus on two cases of practical interest: 1) backup protection of a single flow that can be split into two subflows; and 2) shared backup protection of two unicast flows. We present an efficient network coding algorithm that operates over a small finite field (GF(2)). The small size of the underlying field results in a significant reduction in the computational and communication overhead associated with the practical implementation of the network coding technique. Our algorithm exploits the unique structure of minimum coding networks, i.e., networks that do not contain redundant edges. We also consider the related capacity reservation problem and present an approximation algorithm that finds a solution whose cost is at most two times more than the optimum. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TNET.2010.2091424 | Networking, IEEE/ACM Transactions |
Keywords | Field | DocType |
approximation theory,decoding,network coding,telecommunication network reliability,approximation algorithm,backup protection,communication network,destination node,disjoint path routing,diversity coding,instantaneous recovery,packet decoding,reliable unicast connection,robust network coding technique,single edge failure,Instantaneous recovery,network coding,reliable communication,unicast | Linear network coding,Approximation algorithm,Telecommunications network,Computer science,Retransmission,Network packet,Computer network,Unicast,Diversity coding,Backup,Distributed computing | Journal |
Volume | Issue | ISSN |
19 | 3 | 1063-6692 |
Citations | PageRank | References |
20 | 0.88 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| El Rouayheb, S. | 1 | 563 | 29.41 |
| Alex Sprintson | 2 | 279 | 35.35 |
| Costas N. Georghiades | 3 | 301 | 32.18 |