Optimal-constrained multicast sub-graph over coded packet networks

M. A. Raayatpanah (), H. Salehi Fathabadi (), H. Bahramgiri () and P. M. Pardalos ()
Additional contact information
M. A. Raayatpanah: University of Tehran
H. Salehi Fathabadi: University of Tehran
H. Bahramgiri: University of Tehran
P. M. Pardalos: University of Florida

Journal of Combinatorial Optimization, 2015, vol. 29, issue 4, No 4, 723-738

Abstract: Abstract 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.

Keywords: Communication networks; Network coding; Network flow optimization; Multicast (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9617-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:4:d:10.1007_s10878-013-9617-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9617-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().