Allocation of Network Error Correction Flow on Disjoint Paths

Zhiqing Xiao; Yunzhou Li; Jing Wang

doi:10.1109/TST.2015.7085631

| Sign up

PDF (472.8 KB)

Cite

EndNote(RIS) BibTeX

Collect

Submit Manuscript

Show Outline

Figures (1)

Tables (1)

Table 1

Open Access

Allocation of Network Error Correction Flow on Disjoint Paths

Zhiqing Xiao, Yunzhou Li(), Jing Wang

Department of Electronic Engineering, Tsinghua University, Beijing 100084, China.

Research Institute of Information Technology, Tsinghua University, Beijing 100084, China.

Show Author Information

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

[1]

Haider

and Harris,

Recovery techniques in next generation networks, IEEE Comm. Surveys and Tutorials, vol. 9, no. 3, pp. 1-17, 2007.

Crossref Google Scholar

[2]

Lang

and Drake,

Mesh network resiliency using GMPLS, Proc. IEEE, vol. 90, no. 9, pp. 1559-1564, 2002.

Crossref Google Scholar

[3]

Cai

and Yeung,

R. W.

Network coding and error correction, in IEEE Inf. Theory Workshop, Bangalore, India, 2002, pp. 20-25.

Crossref

[4]

Kim,

Ho,

Effros,

and Avestimehr,

Network error correction with unequal link capacities, in Proc. 47th Annual Allerton Conf. Commun., Control, Comput., Monticello, USA, 2009, pp. 1387-1394.

Crossref

[5]

Kim,

Ho,

Effros,

and Avestimehr,

Network error correction with unequal link capacities, IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 1144-1164, 2011.

Crossref Google Scholar

[6]

Ho,

Kim,

Yang,

Effros,

and Avestimehr,

On network error correction with limited feedback capacity, in Inf. Theory Appl. Workshop, La Jolla, USA, 2011, pp. 1-3.

Crossref

[7]

Yang,

Yeung,

and Ngai,

Refined coding bounds and code constructions for coherent network error correction, IEEE Trans. Inf. Theory, vol. 57, no. 3, pp. 1409-1424, 2011.

Crossref Google Scholar

[8]

Guang,

Fu,

and Zhang,

Construction of network error correction codes in packet networks, IEEE Trans. Inf. Theory, vol. 59, no. 2, pp. 1030-1047, 2013.

Crossref Google Scholar

[9]

Bhandari,

Optimal physical diversity algorithms and survivable networks, in Proc. 2nd IEEE Symp. Comput. and Commun., Alexandria, Egypt, 1997, pp. 433-441.

[10]

Bellman,

On a routing problem, Quart. Appl. Math., vol. 16, pp. 87-90, 1958.

Crossref Google Scholar

[11]

Ford

and Lester,

Network Flow Theory. Santa Monica, California, USA: RAND Corporation, 1956, p. 923.

[12]

Yen,

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.

Crossref Google Scholar

Tsinghua Science and Technology

Volume 20 Issue 2,
April 2015

Pages 182-187

DOI: 10.1109/TST.2015.7085631

Cite this article:

Xiao Z, Li Y, Wang J. Allocation of Network Error Correction Flow on Disjoint Paths. Tsinghua Science and Technology, 2015, 20(2): 182-187. https://doi.org/10.1109/TST.2015.7085631

i	$ψ \leftarrow ψ_{i}$	Compare $ϕ$ with $n_{r} ψ$	$n_{r} \leftarrow n_{r} + 1$	$ϕ \leftarrow ϕ + ψ$
0 (init)			$- 2$	0
1	1	$0 > - 2$	$- 1$	1
2	2	$1 > - 2$	0	3
3	2	$3 > 0$	1	5
4	2	$5 > 2$	2	7
5	3	$7 > 6$	3	10
6	3	$10 > 9$	4	13
7	3	$13 > 12$	5	16
8	8	$16 ⩽ 40$ (break)