Broadcasting a file in a communication network

Kai-Simon Goetzmann, Tobias Harks () and Max Klimm ()
Additional contact information
Kai-Simon Goetzmann: Technische Universität Berlin
Tobias Harks: Universität Augsburg
Max Klimm: Humboldt-Universität zu Berlin

Journal of Scheduling, 2020, vol. 23, issue 2, No 4, 232 pages

Abstract: Abstract We study the problem of distributing a file, initially located at a server, among a set of n nodes. The file is divided into $$m\ge 1$$ m ≥ 1 equally sized packets. After downloading a packet, nodes can upload it to other nodes, possibly to multiple nodes in parallel. Each node, however, may receive each packet from a single source node only. The upload and download rates between nodes are constrained by node- and server-specific upload and download capacities. The objective is to minimize the makespan. This problem has been proposed and analyzed first by Mundinger et al. (J Sched 11:105–120, 2008. https://doi.org/10.1007/s10951-007-0017-9 ) under the assumption that uploads obey the fair sharing principle, that is, concurrent upload rates from a common source are equal at any point in time. Under this assumption, the authors devised an optimal polynomial time algorithm for the case where the upload capacity of the server and the nodes’ upload and download capacities are all equal. In this work, we drop the fair sharing assumption and derive an exact polynomial time algorithm for the case when upload and download capacities per node and among nodes are equal. We further show that the problem becomes strongly NP-hard for equal upload and download capacities per node that may differ among nodes, even for a single packet. For this case, we devise a polynomial time $$\smash {(1+2\sqrt{2})}$$ ( 1 + 2 2 ) -approximation algorithm. Finally, we devise two polynomial time algorithms with approximation guarantees of 5 and $$2 + \lceil \log _2 \lceil n/m\rceil \rceil /m$$ 2 + ⌈ log 2 ⌈ n / m ⌉ ⌉ / m , respectively, for the general case of m packets.

Keywords: Broadcasting problem; Content distribution; File sharing; Load balancing; Makespan; Peer-to-peer; Approximation algorithm (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-020-00643-w 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:jsched:v:23:y:2020:i:2:d:10.1007_s10951-020-00643-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-020-00643-w

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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