Research Project Summary
Protection against link errors and failures using network coding
In this project, we investigate the network protection problem. We want to protect multiple bidirectional unicast connection, each of which is established over one primary path. Rather than temporal redundancy in classical coding theory, we exploit spatial redundancy to provide protection against adversarial errors and failures. Additional bidirectional protection paths are added as resource for protection. And network coded data units are transmitted on those protection paths. It is a significant generalization of the work by Prof.Kamal and Prof. Ramamoorthy [1] since they only provide protection against failures.
Suppose that ne paths which could be primary paths or protections are corrupted by the adversary, under our proposed protocol, the errors can be corrected at all the end nodes with 4ne protection paths. More generally, if there are ne adversarial errors and nf failures, 4ne + 2nf protection paths are sufficient. The number of protection paths only depends on the number of errors and failures being protected against and is independent of the number of unicast connections. Thus, multiple unicast connections can share the same set of protection path, which means we can save network resources.
Key words:
network coding, network protection, adversarial errors, network resilience
[1] Ahmed E. Kamal and Aditya Ramamoorthy, "Overlay Protection Against Link Failures Using Network Coding", 42nd Annual Conf. on Information Sciences and Systems (CISS), 2008.
|
|
| Fig.1: There are three unicast connections, S1-T1, S2-T2 and S3-T3. Only one of the protection path is drawn here (double solid line). The protection path passes through all end nodes of the unicast connections. The data units to be transmitted (d's and u's) are sent over the primary paths. Encoded data units are sent over the protection path. |
1.Shizheng Li and Aditya Ramamoorthy, “Protection against link errors and failures using network coding in overlay networks”, IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, Jul. 2009, pp 986-990 (.pdf)
ISIT09
presentation, 06/30/2009;
Poster at 2nd North American IT
summer school, Aug, 2009,