American Institute of Mathematical Sciences

Advanced
February  2016, 10(1): 95-112. doi: 10.3934/amc.2016.10.95

The one-out-of-k retrieval problem and linear network coding

Giuseppe Bianchi 1, , Lorenzo Bracciale 1, , Keren Censor-Hillel 2, , Andrea Lincoln 3, and  Muriel Médard 4,

1. 

Dipartimento di Ingegneria Elettronica, Università degli Studi di Roma - Tor Vergata, Via del Politecnico, 1 00133 - Roma, Italy, Italy
2. 

Department of Computer Science, Technion, Haifa 32000, Israel
3. 

160 Sunrise Dr, Woodside, CA 94062, United States
4. 

Room 36-512F, 77 Massachusetts Avenue, Cambridge, MA 02139, United States

Received  December 2014 Revised  December 2015 Published  March 2016

In this paper we show how linear network coding can reduce the number of queries needed to retrieve one specific message among $k$ distinct ones replicated across a large number of randomly accessed nodes storing one message each. Without network coding, this would require $k$ queries on average. After proving that no scheme can perform better than a straightforward lower bound of $0.5k$ average queries, we propose and asymptotically evaluate, using mean field arguments, a few example practical schemes, the best of which attains $0.794k$ queries on average. The paper opens two complementary challenges: a systematic analysis of practical schemes so as to identify the best performing ones and design guideline strategies, as well as the need to identify tighter, nontrivial, lower bounds.
Keywords: linear network coding, lower bounds, Delay tolerant network, mean field arguments., fluid approximations.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.
Citation: Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95
References:
[1]

F. M. Buckley and P. K. Pollett, Limit theorems for discrete-time metapopulation models, Probab. Surveys, 7 (2010), 53-83. doi: 10.1214/10-PS158.  Google Scholar

[2]

L. Chen, T. Ho, S. H. Low, M. Chiang and J. C. Doyle, Optimization based rate control for multi-cast with network coding, in 26th IEEE Int. Conf. Comp. Commun. 2007, 1163-1171. Google Scholar

[3]

R. W. R. Darlings and J. R. Norris, Differential equation approximations for Markov chains, Probab. Surveys, 5 (2008), 37-79. doi: 10.1214/07-PS121.  Google Scholar

[4]

F. De Pellegrini, R. El-Azouzi and F. Albini, Interplay of contact times, fragmentation and coding in DTNs, in 11th Int. Symp. Modeling Optim. Mobile Ad Hoc Wireless Networks, 2013, 580-587. Google Scholar

[5]

S. Deb, M. Medard and C. Choute, Algebraic gossip: a network coding approach to optimal multiple rumor mongering, IEEE Trans. Inf. Theory, 52 (2006), 2486-2507. doi: 10.1109/TIT.2006.874532.  Google Scholar

[6]

A. G. Dimakis V. Prabhakaran and K. Ramchandran, Decentralized erasure codes for distributed networked storage, IEEE Trans. Inf. Theory, 52 (2006), 2809-2816. doi: 10.1109/TIT.2006.874535.  Google Scholar

[7]

P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17-61.  Google Scholar

[8]

L. Keller, E. Atsan, K. Argyraki and C. Fragouli, SenseCode: Network coding for reliable sensor networks, ACM Trans. Sen. Netw., 9 (2013), #25. doi: 10.1145/2422966.2422982.  Google Scholar

[9]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Probab., 7 (1970), 49-58.  Google Scholar

[10]

Y. Lin, B. Li and B. Liang, Efficient network coded data transmissions in disruption tolerant networks, in The 27th IEEE Conf. Comp. Commun., 2008, 2180-2188. doi: 10.1109/INFOCOM.2008.210.  Google Scholar

[11]

M. Luby, LT codes, in The 43rd Ann. IEEE Symp. Found. Comp. Sci., 2002, 271-280. doi: 10.1109/SFCS.2002.1181950.  Google Scholar

[12]

A. Oppenheim, R. Schafer and J. Buck, Discrete-Time Signal Processing, Printice Hall Inc., New Jersey, 1989. Google Scholar

[13]

L. Sassatelli and M. Medard, Inter-session network coding in delay-tolerant networks under Spray-and-Wait routing, Model. Optim. Mob. Ad Hoc Wirel. Netw., 10 (2012), 103-110. Google Scholar

[14]

J. Widmer and J. Y. Le Boudec, Network coding for efficient communication in extreme networks, in ACM SIGCOMM Workshop Delay-Tolerant Networking, 2005, 284-291. Google Scholar

[15]

S. K. Yoon and Z. J. Haas, Application of linear network coding in delay tolerant networks, in Second Int. Conf. Ubiquitous Future Networks (ICUFN), 2010, 338-343. Google Scholar

[16]

X. Zhang, G. Neglia, J. Kurose, D. Towsley and H. Wang, Benefits of network coding for unicast application in disruption-tolerant networks, IEEE/ACM Trans. Networking, 21 (2013), 1407-1420. doi: 10.1109/TNET.2012.2224369.  Google Scholar

show all references

References:
[1]

F. M. Buckley and P. K. Pollett, Limit theorems for discrete-time metapopulation models, Probab. Surveys, 7 (2010), 53-83. doi: 10.1214/10-PS158.  Google Scholar

[2]

L. Chen, T. Ho, S. H. Low, M. Chiang and J. C. Doyle, Optimization based rate control for multi-cast with network coding, in 26th IEEE Int. Conf. Comp. Commun. 2007, 1163-1171. Google Scholar

[3]

R. W. R. Darlings and J. R. Norris, Differential equation approximations for Markov chains, Probab. Surveys, 5 (2008), 37-79. doi: 10.1214/07-PS121.  Google Scholar

[4]

F. De Pellegrini, R. El-Azouzi and F. Albini, Interplay of contact times, fragmentation and coding in DTNs, in 11th Int. Symp. Modeling Optim. Mobile Ad Hoc Wireless Networks, 2013, 580-587. Google Scholar

[5]

S. Deb, M. Medard and C. Choute, Algebraic gossip: a network coding approach to optimal multiple rumor mongering, IEEE Trans. Inf. Theory, 52 (2006), 2486-2507. doi: 10.1109/TIT.2006.874532.  Google Scholar

[6]

A. G. Dimakis V. Prabhakaran and K. Ramchandran, Decentralized erasure codes for distributed networked storage, IEEE Trans. Inf. Theory, 52 (2006), 2809-2816. doi: 10.1109/TIT.2006.874535.  Google Scholar

[7]

P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17-61.  Google Scholar

[8]

L. Keller, E. Atsan, K. Argyraki and C. Fragouli, SenseCode: Network coding for reliable sensor networks, ACM Trans. Sen. Netw., 9 (2013), #25. doi: 10.1145/2422966.2422982.  Google Scholar

[9]

T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Probab., 7 (1970), 49-58.  Google Scholar

[10]

Y. Lin, B. Li and B. Liang, Efficient network coded data transmissions in disruption tolerant networks, in The 27th IEEE Conf. Comp. Commun., 2008, 2180-2188. doi: 10.1109/INFOCOM.2008.210.  Google Scholar

[11]

M. Luby, LT codes, in The 43rd Ann. IEEE Symp. Found. Comp. Sci., 2002, 271-280. doi: 10.1109/SFCS.2002.1181950.  Google Scholar

[12]

A. Oppenheim, R. Schafer and J. Buck, Discrete-Time Signal Processing, Printice Hall Inc., New Jersey, 1989. Google Scholar

[13]

L. Sassatelli and M. Medard, Inter-session network coding in delay-tolerant networks under Spray-and-Wait routing, Model. Optim. Mob. Ad Hoc Wirel. Netw., 10 (2012), 103-110. Google Scholar

[14]

J. Widmer and J. Y. Le Boudec, Network coding for efficient communication in extreme networks, in ACM SIGCOMM Workshop Delay-Tolerant Networking, 2005, 284-291. Google Scholar

[15]

S. K. Yoon and Z. J. Haas, Application of linear network coding in delay tolerant networks, in Second Int. Conf. Ubiquitous Future Networks (ICUFN), 2010, 338-343. Google Scholar

[16]

X. Zhang, G. Neglia, J. Kurose, D. Towsley and H. Wang, Benefits of network coding for unicast application in disruption-tolerant networks, IEEE/ACM Trans. Networking, 21 (2013), 1407-1420. doi: 10.1109/TNET.2012.2224369.  Google Scholar

[1]

Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021027
[2]

Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[3]

Joachim Crevat. Mean-field limit of a spatially-extended FitzHugh-Nagumo neural network. Kinetic & Related Models, 2019, 12 (6) : 1329-1358. doi: 10.3934/krm.2019052
[4]

Fabio Bagagiolo, Rosario Maggistro, Raffaele Pesenti. Origin-to-destination network flow with path preferences and velocity controls: A mean field game-like approach. Journal of Dynamics & Games, 2021, 8 (4) : 359-380. doi: 10.3934/jdg.2021007
[5]

Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145
[6]

Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044
[7]

András Bátkai, Istvan Z. Kiss, Eszter Sikolya, Péter L. Simon. Differential equation approximations of stochastic network processes: An operator semigroup approach. Networks & Heterogeneous Media, 2012, 7 (1) : 43-58. doi: 10.3934/nhm.2012.7.43
[8]

Ángela Jiménez-Casas, Aníbal Rodríguez-Bernal. Linear model of traffic flow in an isolated network. Conference Publications, 2015, 2015 (special) : 670-677. doi: 10.3934/proc.2015.0670
[9]

Michael Herty, Mattia Zanella. Performance bounds for the mean-field limit of constrained dynamics. Discrete & Continuous Dynamical Systems, 2017, 37 (4) : 2023-2043. doi: 10.3934/dcds.2017086
[10]

Reimund Rautmann. Lower and upper bounds to the change of vorticity by transition from slip- to no-slip fluid flow. Discrete & Continuous Dynamical Systems - S, 2014, 7 (5) : 1101-1109. doi: 10.3934/dcdss.2014.7.1101
[11]

Maria Schonbek, Tomas Schonbek. Moments and lower bounds in the far-field of solutions to quasi-geostrophic flows. Discrete & Continuous Dynamical Systems, 2005, 13 (5) : 1277-1304. doi: 10.3934/dcds.2005.13.1277
[12]

Katrin Gelfert. Lower bounds for the topological entropy. Discrete & Continuous Dynamical Systems, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555
[13]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[14]

Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[15]

Zheng Chen, Liu Liu, Lin Mu. Solving the linear transport equation by a deep neural network approach. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021070
[16]

Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243
[17]

Kai Du, Jianhui Huang, Zhen Wu. Linear quadratic mean-field-game of backward stochastic differential systems. Mathematical Control & Related Fields, 2018, 8 (3&4) : 653-678. doi: 10.3934/mcrf.2018028
[18]

Zhenghong Qiu, Jianhui Huang, Tinghan Xie. Linear-Quadratic-Gaussian mean-field controls of social optima. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021047
[19]

Chjan C. Lim. Extremal free energy in a simple mean field theory for a coupled Barotropic fluid - rotating sphere system. Discrete & Continuous Dynamical Systems, 2007, 19 (2) : 361-386. doi: 10.3934/dcds.2007.19.361
[20]

Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (101)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences