×

Optimal-constrained multicast sub-graph over coded packet networks. (English) Zbl 1320.90096

Summary: Network coding is a technique which can be used to improve the performance of multicast communications by performing encoding operations at intermediate nodes. In real-time multimedia communication applications, there are usually several weights associated with links, such as cost, delay, jitter, loss ratio, security, and so on. In this paper, we consider the problem of finding an optimal multicast sub-graph over coded packet networks, where the longest end-to-end weight from the source to each destination does not exceed an upper bound. First, a mixed integer programming model is proposed to formulate the problem which is NP-hard. Then, a column-generation approach is described for this problem, in which the problem is decomposed into a master linear programming problem and several integer programming sub-problems. Moreover, two methods based on linear and Lagrangian relaxation are proposed to compute a tight lower bound of the optimal solution value. Computational results show that the proposed algorithm provides an efficient way for solving the problem, even for relatively large networks.

MSC:

90C35 Programming involving graphs or networks
90B18 Communication networks in operations research
90C11 Mixed integer programming

Software:

CPLEX; BARON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahlswede R, Cai N, Li S, Yeung R (2000) Network information flow. IEEE Trans Inf Theory 46(4):1204-1216 · Zbl 0991.90015 · doi:10.1109/18.850663
[2] Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms, and applications. Prentice-Hall, Englewood Cliffs · Zbl 1201.90001
[3] Bazaraa M, Sherali H, Shetty C (2006) Nonlinear programming: theory and algorithms. Wiley-interscience, Hoboken · Zbl 1140.90040
[4] Cai N, Yeung R (2002) Secure network coding. In: Proceedings of the IEEE International Symposium on Information Theory, pp 323-229 · Zbl 1273.94228
[5] Desaulniers G, Desrosiers J, Solomon M (2005) Column generation. Springer, New York · Zbl 1084.90002
[6] Desrochers M, Soumis F (1986) A generalized permanent labelling algorithm for the shortest path problem with time windows. Université de Montréal, Centre de recherche surles transports, Montréal · Zbl 0652.90097
[7] Fragouli C, Soljanin E (2008) Network coding applications. Now Publishers · Zbl 1188.68022
[8] Garey M, Johnson D (1979) Computers and interatability: a guide to the theory of NP-completeness. W. H. Freeman and Company, New York · Zbl 0411.68039
[9] Ghasvari H, Raayatpanah M, Khalaj B, Bakhshi H (2011) Optimal sub-graph selection over coded networks with delay and limited-size buffering the authors consider. IET Commun 5(11):1497-1505 · Zbl 1273.94228 · doi:10.1049/iet-com.2010.0612
[10] Gupta O, Ravindran A (1985) Branch and bound experiments in convex nonlinear integer programming. Manag Sci 31(12):1533-1546 · Zbl 0591.90065 · doi:10.1287/mnsc.31.12.1533
[11] Jaggi S, Sanders P, Chou P, Effros M, Egner S, Jain K, Tolhuizen L (2005) Polynomial time algorithms for multicast network code construction. IEEE Trans Inf Theory 51(6):1973-1982 · Zbl 1288.94098 · doi:10.1109/TIT.2005.847712
[12] Lee W, Hluchyi M, Humblet P (1995) Routing subject to quality of service constraints in integrated communication networks. IEEE Netw 9(4):46-55 · doi:10.1109/65.397043
[13] Li S, Yeung R, Cai N (2003) Linear network coding. IEEE Trans Inf Theory 49(2):371-381 · Zbl 1063.94004 · doi:10.1109/TIT.2002.807285
[14] Lun D, Médard M, Koetter R, Effros M (2008) Linear network coding. Phys Commun 1(1):3-20 · doi:10.1016/j.phycom.2008.01.006
[15] Lun D, Ratnakar N, Médard M, Koetter R, Karger D, Ho T, Ahmed E, Zhao F (2006) Minimum-cost multicast over coded packet networks. IEEE Trans Inf Theory 52(6):2608-2623 · Zbl 1317.94010 · doi:10.1109/TIT.2006.874523
[16] ILOG Inc (2005) Using the CPLEX callable library and CPLEX mixed integer library. ILOG Inc. · Zbl 1317.94010
[17] Oliveira CAS, Pardalos PM (2011) Mathematical aspects of network routing optimization. Springer, New York · Zbl 1225.90002
[18] Raayatpanah M, Fathabadi HS (2012) Minimum cost multiple multicast network coding with quantized rates. Comput Netw 57:1113-1123
[19] Resende MGC, Pardalos PM (2006) Handbook of optimization in telecommunications. Springer, New York · Zbl 1100.90001
[20] Sahinidis N (1996) Baron: a general purpose global optimization software package. J Glob Optim 8(2):201-205 · Zbl 0856.90104 · doi:10.1007/BF00138693
[21] Xi Y, Yeh EM (2010) Distributed algorithms for minimum cost multicast with network coding. IEEE/ACM Trans Netw 18(2):379-392 · doi:10.1109/TNET.2009.2026275
[22] Yeung R, Li S, Cai N, Zhang Z (2005) Network coding theory: single sources. Found Trends Commun Inf Theory 2(4):241-329 · Zbl 1143.94356 · doi:10.1561/0100000007I
[23] Ziegelmann M (2007) Constrained shortest paths and related problems-constrained network optimization. VDM Verlag · Zbl 1063.94004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.