Journal Home > Volume 20 , Issue 2

The diversity provided by disjoint paths can increase the survivability of communication networks. This paper considers the allocation of network error correction flow on a network that consists of disjoint paths from the source node to the destination node. Specifically, we propose an algorithm of allocating the path-flows to support the given rate with minimum cost. Our analysis shows that the asymptotic time complexity of this algorithm is linearithmic, and this algorithm is optimal in general.


menu
Abstract
Full text
Outline
About this article

Allocation of Network Error Correction Flow on Disjoint Paths

Show Author's information Zhiqing XiaoYunzhou Li( )Jing Wang
Department of Electronic Engineering, Tsinghua University, Beijing 100084, China.
Research Institute of Information Technology, Tsinghua University, Beijing 100084, China.

Abstract

The diversity provided by disjoint paths can increase the survivability of communication networks. This paper considers the allocation of network error correction flow on a network that consists of disjoint paths from the source node to the destination node. Specifically, we propose an algorithm of allocating the path-flows to support the given rate with minimum cost. Our analysis shows that the asymptotic time complexity of this algorithm is linearithmic, and this algorithm is optimal in general.

Keywords: network survivability, disjoint paths, maximum distance separable codes, network error correction

References(12)

[1]
Haider A. and Harris, R. Recovery techniques in next generation networks, IEEE Comm. Surveys and Tutorials, vol. 9, no. 3, pp. 1-17, 2007.
[2]
Lang J. and Drake, J. Mesh network resiliency using GMPLS, Proc. IEEE, vol. 90, no. 9, pp. 1559-1564, 2002.
[3]
Cai N. and Yeung, R. W. Network coding and error correction, in IEEE Inf. Theory Workshop, Bangalore, India, 2002, pp. 20-25.
DOI
[4]
Kim, S. Ho, T. Effros, M. and Avestimehr, A. Network error correction with unequal link capacities, in Proc. 47th Annual Allerton Conf. Commun., Control, Comput., Monticello, USA, 2009, pp. 1387-1394.
DOI
[5]
Kim, S. Ho, T. Effros, M. and Avestimehr, A. Network error correction with unequal link capacities, IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 1144-1164, 2011.
[6]
Ho, T. Kim, S. Yang, Y. Effros, M. and Avestimehr, S. On network error correction with limited feedback capacity, in Inf. Theory Appl. Workshop, La Jolla, USA, 2011, pp. 1-3.
DOI
[7]
Yang, S. Yeung, R. and Ngai, C. Refined coding bounds and code constructions for coherent network error correction, IEEE Trans. Inf. Theory, vol. 57, no. 3, pp. 1409-1424, 2011.
[8]
Guang, X. Fu, F. and Zhang, Z. Construction of network error correction codes in packet networks, IEEE Trans. Inf. Theory, vol. 59, no. 2, pp. 1030-1047, 2013.
[9]
Bhandari, R. Optimal physical diversity algorithms and survivable networks, in Proc. 2nd IEEE Symp. Comput. and Commun., Alexandria, Egypt, 1997, pp. 433-441.
[10]
Bellman, R. On a routing problem, Quart. Appl. Math., vol. 16, pp. 87-90, 1958.
[11]
Ford J. and Lester, R. Network Flow Theory. Santa Monica, California, USA: RAND Corporation, 1956, p. 923.
[12]
Yen, J. An algorithm for finding shortest routes from all source nodes to a given destination in general networks, Quart. Appl. Math., vol. 27, pp. 526-530, 1970.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 10 January 2014
Revised: 17 June 2014
Accepted: 21 July 2014
Published: 23 April 2015
Issue date: April 2015

Copyright

© The author(s) 2015

Acknowledgements

This work was supported by the National Key Basic Research and Development (973) Program of China (No. 2013CB329002), the National High-Tech Research and Development (863) Program of China (No. 2014AA01A703), the National Science and Technology Major Project (No. 2013ZX03004007), the Program for New Century Excellent Talents in University (No. NCET-13-0321), the International Science and Technology Cooperation Program (No. 2012DFG12010), and the Tsinghua Research Funding (No. 2010THZ03-2).

The authors would like to thank Shenghao Yang, Britt Fugitt, and the editor Li Zhang for their helpful comments.

Rights and permissions

Return