Scheduling for Optimal File-Transfer Delay using Chunked Random Linear Network Coding Broadcast
Article No.: 17, Pages 1 - 31
Abstract
We study the broadcast transmission of a single file to an arbitrary number of receivers using Random Linear Network Coding (RLNC) in a network with unreliable channels. Due to the increased computational complexity of the decoding process (especially for large files), we apply chunked RLNC (i.e., RLNC is applied within non-overlapping subsets of the file).
In our work, we show the optimality of the Least Received (LR) batch scheduling policy with regards to the expected file transfer completion time. The LR policy strives to keep the receiver queues balanced. This is done by transmitting packets (corresponding to encoded batches) that are needed by the receivers with the shortest queues of successfully received packets. Furthermore, we provide formulas for the expected time for the file transmission to all receivers using the LR batch scheduling policy and the minimum achievable coding window size in the case of a pre-defined delay constraint. Moreover, we evaluate through simulations a modification of the LR policy in a more realistic system setting with reduced feedback from the receivers. Finally, we provide an initial analysis and further modifications to the LR policy for time-correlated channels and asymmetric channels.
References
[1]
Peter J. Acklam. 2003. An algorithm for computing the inverse normal cumulative distribution function. Peter’s Page (2003).
[2]
Ebad Ahmed, Atilla Eryilmaz, Muriel Medard, and Asuman E. Ozdaglar. 2007. On the scaling law of network coding gains in wireless networks. In Military Communications Conference (MILCOM). IEEE, 1--7.
[3]
Chien-Chung Chen and Christopher W. Tyler. 1999. Accurate approximation to the extreme order statistics of Gaussian samples. Communications in Statistics-Simulation and Computation 28, 1 (1999), 177--188.
[4]
Atilla Eryilmaz and Desmond S. Lun. 2007. Control for inter-session network coding. In Proceedings of the Workshop on Network Coding, Theory 8 Applications. IEEE, 1--9.
[5]
Atilla Eryilmaz, Asuman Ozdaglar, Muriel Médard, and Ebad Ahmed. 2008. On the delay and throughput gains of coding in unreliable networks. Transactions on Information Theory 54, 12 (2008), 5511--5524.
[6]
Constantinos Fragiadakis, Georgios S. Paschos, Leonidas Georgiadis, and Leandros Tassiulas. 2015. Dynamic wireless network coding with overhearing and variable channel rates. Journal on Selected Areas in Communications 33, 2 (2015), 185--198.
[7]
Constantinos Fragiadakis, Georgios S. Paschos, and Leandros Tassiulas. 2013. On the wireless network coding with overhearing and index coding. In IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD’13). IEEE, 23--27.
[8]
Majid Ghaderi, Don Towsley, and Jim Kurose. 2008. Reliability gain of network coding in lossy wireless networks. In The 27th IEEE Conference on Computer Communications (INFOCOM 2008). IEEE.
[9]
Tracey Ho. 2004. Networking from a Network Coding Perspective. Ph.D. Dissertation. Citeseer.
[10]
Tracey Ho, Muriel Médard, Ralf Koetter, David R. Karger, Michelle Effros, Jun Shi, and Ben Leong. 2006. A random linear network coding approach to multicast. IEEE Transactions on Information Theory 52, 10 (2006).
[11]
Gauri Joshi and Emina Soljanin. 2013. Round-robin overlapping generations coding for fast content download. In IEEE International Symposium on Information Theory Proceedings (ISIT’13). IEEE, 2740--2744.
[12]
Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, and Jon Crowcroft. 2008. XORs in the air: Practical wireless network coding. IEEE/ACM Transactions on Networking (ToN) 16, 3 (2008), 497--510.
[13]
Christian Koller, Martin Haenggi, Jörg Kliewer, and Daniel J. Costello. 2011. On the optimal block length for joint channel and network coding. In IEEE Information Theory Workshop (ITW’11). IEEE, 528--532.
[14]
Ruogu Li, Harsha Gangammanavar, and Atilla Eryilmaz. 2012. Optimal dynamic coding-window selection for serving deadline-constrained traffic over time-varying channels. Transactions on Information Theory 58, 10 (2012), 6556--6571.
[15]
Zhen Liu, Philippe Nain, and Don Towsley. 1995. Sample path methods in the control of queues. Queueing Systems 21, 3 (1995), 293--335.
[16]
Georgios S. Paschos, Constantinos Fragiadakis, Leonidas Georgiadis, and Leandros Tassiulas. {n.d.}. Wireless network coding with partial overhearing information. In The 32nd IEEE Conference on Computer Communications (INFOCOM 2013). IEEE, 2337--2345.
[17]
Hassan Shojania and Baochun Li. 2007. Parallelized progressive network coding with hardware acceleration. In 2007 15th IEEE International Workshop on Quality of Service. IEEE, 47--55.
[18]
Danilo Silva, Weifei Zeng, and Frank R. Kschischang. 2009. Sparse network coding with overlapping classes. In Workshop on Network Coding, Theory, and Applications (NetCod’09). IEEE, 74--79.
[19]
Emmanouil Skevakis and Ioannis Lambadaris. 2016a. Decoding and file transfer delay balancing in network coding broadcast. In International Conference on Communications (ICC). IEEE, 1--7.
[20]
Emmanouil Skevakis and Ioannis Lambadaris. 2016b. Optimal control for network coding broadcast. In Global Communications Conference (GLOBECOM). IEEE, 1--6.
[21]
Emmanouil Skevakis and Ioannis Lambadaris. 2017. Delay optimal scheduling for network coding broadcast. In International Conference on Communications (ICC). IEEE, 1--6.
[22]
B. T. Swapna, Atilla Eryilmaz, and Ness B. Shroff. 2013. Throughput-delay analysis of random linear network coding for wireless broadcasting. IEEE Transactions on Information Theory 59, 10 (2013).
[23]
Leandros Tassiulas and Anthony Ephremides. 1993. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Transactions on Information Theory 39, 2 (1993), 466--478.
[24]
Mea Wang and Baochun Li. 2007a. Lava: A reality check of network coding in peer-to-peer live streaming. In IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications. IEEE, 1082--1090.
[25]
Mea Wang and Baochun Li. 2007b. Network coding in live peer-to-peer streaming. IEEE Transactions on Multimedia 9, 8 (2007), 1554--1567.
[26]
Michael J. Wichura. 1988. Algorithm AS 241: The percentage points of the normal distribution. Journal of the Royal Statistical Society. Series C (Applied Statistics) 37, 3 (1988), 477--484.
[27]
Nan Xie and Steven Weber. 2013. Network coding broadcast delay on erasure channels. In Information Theory and Applications Workshop (ITA), 2013. IEEE, 1--8.
[28]
Yang Yang and Ness Shroff. 2015. Throughput of rateless codes over broadcast erasure channels. IEEE/ACM Transactions on Networking 23, 1 (2015), 126--137.
Index Terms
- Scheduling for Optimal File-Transfer Delay using Chunked Random Linear Network Coding Broadcast
Recommendations
Dirty-paper coding versus TDMA for MIMO Broadcast channels
We compare the capacity of dirty-paper coding (DPC) to that of time-division multiple access (TDMA) for a multiple-antenna (multiple-input multiple-output (MIMO)) Gaussian broadcast channel (BC). We find that the sum-rate capacity (achievable using DPC) ...
Interference alignment in MIMO interference broadcast channels with imperfect CSI
In this study, the authors propose four interference alignment (IA) schemes for multiple‐input multiple‐output (MIMO) interference broadcast channels (IBCs) under imperfect channel state information (CSI). They propose two new algorithms based on ...
Linear beamforming and superposition coding with common information for the Gaussian MIMO broadcast channel
A Gaussian multiple-input multiple-output broadcast channel (MIMO GBC) is considered. Throughout the paper it is assumed that 1) input signals are Gaussian and 2) perfect channel state information is available at the transmitter and at the receivers. By ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2019
151 pages
ISSN:2376-3639
EISSN:2376-3647
DOI:10.1145/3343140
- Editors:
- Sem Borst,
- Carey Williamson
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 August 2019
Accepted: 01 June 2019
Revised: 01 April 2019
Received: 01 August 2018
Published in TOMPECS Volume 4, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 84Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format