nach oben

Problems of Information Transmission

Erschienen in:

01.01.2021 | INFORMATION THEORY

Trade-off for Heterogeneous Distributed Storage Systems between Storage and Repair Cost

verfasst von: K. G. Benerjee, M. K. Gupta

Erschienen in: Problems of Information Transmission | Ausgabe 1/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider heterogeneous distributed storage systems (DSSs) having flexible reconstruction degree, where each node in the system has nonuniform repair bandwidth and nonuniform storage capacity. In particular, a data collector can reconstruct the file using some \(k\) nodes in the system and, for a node failure, the system can be repaired by some set of active nodes. Using min-cut bound, we investigate the fundamental trade-off between storage and repair costs for our model of the heterogeneous DSS. Further, the problem is formulated as bi-objective optimization linear programing problem for various heterogeneous DSSs. For some DSSs, it is shown that the calculated min-cut bound is tight.

Vorheriger Artikel Finite Blocklength Analysis of Energy Harvesting Channels

Nächster Artikel The f-Divergence and Coupling of Probability Distributions

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Amazon Elastic Compute Cloud (Amazon EC2). Web Service, Jan. 2013. Available at http://aws.amazon.com/ec2/.

Huang, C., Simitci, H., Xu, Y., Ogus, A., Calder, B., Gopalan, P., Li, J., and Yekhanin, S., Erasure Coding in Windows Azure Storage, in Proc. 2012 USENIX Annu. Technical Conf. (USENIX ATC’12), Boston, MA, June 13–15, 2012, pp. 15–26.

Microsoft SkyDrive Live. Online Storage Service, Jan. 2013. Available at https://skydrive.live.com/.

Sathiamoorthy, M., Asteris, M., Papailiopoulos, D., Dimakis, A.G., Vadali, R., Chen, S., and Borthakur, D., XORing Elephants: Novel Erasure Codes for Big Data, Proc. VLDB Endow., 2013, vol. 6, no. 5, pp. 325–336. https://doi.org/10.14778/2535573.2488339CrossRef

Dimakis, A.G., Godfrey, P.B., Wu, Y., Wainwright, M.J., and Ramchandran, K., Network Coding for Distributed Storage Systems, in Proc. 26th IEEE Annu. Joint Conf. on Computer Communications (INFOCOM’2007), Anchorage, AK, USA, May 6–12, 2007, pp. 2000–2008. https://doi.org/10.1109/INFCOM.2007.232

Dimakis, A.G., Godfrey, P.B., Wu, Y., Wainwright, M.J., and Ramchandran, K., Network Coding for Distributed Storage Systems, IEEE Trans. Inform. Theory, 2010, vol. 56, no. 9, pp. 4539–4551. https://doi.org/10.1109/TIT.2010.2054295CrossRef

Wu, Y., Dimakis, A., and Ramchandran, K., Deterministic Regenerating Codes for Distributed Storage, in Proc. 45th Annu. Allerton Conf. on Communication, Control, and Computing, Monticello, IL, USA, Sept. 26–28, 2007, vol. 1, pp. 242–249.

Wu, Y., Existence and Construction of Capacity-Achieving Network Codes for Distributed Storage, in Proc. 2009 IEEE Int. Symp. on Information Theory (ISIT’2009), Seoul, Korea, June 28 – July 3, 2009, pp. 1150–1154. https://doi.org/10.1109/ISIT.2009.5206008

Wu, Y., Existence and Construction of Capacity-Achieving Network Codes for Distributed Storage, IEEE J. Sel. Areas Commun., 2010, vol. 28, no. 2, pp. 277–288. https://doi.org/10.1109/JSAC.2010.100217CrossRef

10.

Goparaju, S., El Rouayheb, S., and Calderbank, R., New Codes and Inner Bounds for Exact Repair in Distributed Storage Systems in Proc. 2014 IEEE Int. Symp. on Information Theory (ISIT’2014), Honolulu, HI, USA, June 29 – July 4, 2014, pp. 1036–1040. https://doi.org/10.1109/ISIT.2014.6874990

11.

Shah, N.B., Rashmi, K.V., and Kumar, P.V., A Flexible Class of Regenerating Codes for Distributed Storage, in Proc. 2010 IEEE Int. Symp. on Information Theory (ISIT’2010), Austin, TX, USA, June 13–18, 2010, pp. 1943–1947. https://doi.org/10.1109/ISIT.2010.5513353

12.

Dimakis, A.G., Ramchandran, K.,Wu, Y., and Suh, C., A Survey on Network Codes for Distributed Storage, Proc. IEEE, 2011, vol. 99, no. 3, pp. 476–489. https://doi.org/10.1109/JPROC.2010.2096170CrossRef

13.

Prakash, N. and Krishnan, M.N., The Storage-Repair-Bandwidth Trade-off of Exact Repair Linear Regenerating Codes for the Case \(d = k = n - 1\), https://arXiv.org/abs/1501.03983v2 [cs.IT], 2015.

14.

Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Weimer, W., Wells, C., and Zhao, B., OceanStore: An Architecture for Global-Scale Persistent Storage, ACM SIGPLAN Notices, 2000, vol. 35, no. 11, pp. 190–201. https://doi.org/10.1145/356989.357007CrossRef

15.

Bianchi, G. and Melen, R., Performance and Dimensioning of a Hierarchical Video Storage Network for Interactive Video Services, Eur. Trans. Telecommun., 1996, vol. 7, no. 4, pp. 349–358. https://doi.org/10.1002/ett.4460070407CrossRef

16.

Pawar, S., El Rouayheb, S., Zhang, H., Lee, K., and Ramchandran, K., Codes for a Distributed Caching Based Video-on-Demand System, in Conf. Rec. 46th Asilomar Conf. on Signals, Systems and Computers (ASILOMAR’2011), Pacific Grove, CA, USA, Nov. 6–9, 2011, pp. 1783–1787. https://doi.org/10.1109/ACSSC.2011.6190328

17.

Ntranos, V., Caire, G., and Dimakis, A.G., Allocations for Heterogenous Distributed Storage, https://arXiv.org/abs/1202.1596 [cs.IT], 2012.

18.

Li, Z., Ho, T., Leong, D., and Yao, H., Distributed Storage Allocation for Heterogeneous Systems, in Proc. 51st Annu. Allerton Conf. on Communication, Control, and Computing, Monticello, IL, USA, Oct. 2–4, 2013, pp. 320–326. https://doi.org/10.1109/TIT.2012.2191135

19.

Leong, D., Dimakis, A.G., and Ho, T., Distributed Storage Allocations, IEEE Trans. Inform. Theory, 2012, vol. 58, no. 7, pp. 4733–4752. https://doi.org/10.1109/TIT.2012.2191135MathSciNetCrossRef

20.

Gerami, M., Xiao, M., and Skoglund, M., Optimal-Cost Repair in Multi-hop Distributed Storage Systems, in Proc. 2011 IEEE Int. Symp. on Information Theory (ISIT’2011), St. Petersburg, Russia, July 31 – Aug. 5, 2011, pp. 1437–1441. https://doi.org/10.1109/ISIT.2011.6033777

21.

Akhlaghi, S., Kiani, A., and Ghanavati, M.R., Cost-Bandwidth Tradeoff in Distributed Storage Systems, Comput. Commun., 2010, vol. 33, no. 17, pp. 2105–2115. https://doi.org/10.1016/j.comcom.2010.07.022CrossRef

22.

Akhlaghi, S., Kiani, A., and Ghanavati, M.R., A Fundamental Trade-off between the Download Cost and Repair Bandwidth in Distributed Storage Systems, in Proc. 2010 IEEE Int. Symp. on Network Coding (NetCod’2010), Toronto, ON, Canada, June 9–11, 2010, pp. 97–102. https://doi.org/10.1109/NETCOD.2010.5487685

23.

Yu, Q., Shum, K.W., and Sung, C.W., Minimization of Storage Cost in Distributed Storage Systems with Repair Consideration, in Proc. 2011 IEEE Global Telecommunications Conf. (GLOBECOM’2011), Houston, TX, USA, Dec. 5–9, 2011, pp. 2931–2935. https://doi.org/10.1109/GLOCOM.2011.6133729

24.

Pernas, J., Yuen, C., Gastón, B., and Pujol, J., Non-homogeneous Two-Rack Model for Distributed Storage Systems, in Proc. 2013 IEEE Int. Symp. on Information Theory (ISIT’2013), Istanbul, Turkey, July 7–12, 2013, pp. 1237–1241. https://doi.org/10.1109/ISIT.2013.6620424

25.

Gastón, B., Pujol, J., and Villanueva, M., A Realistic Distributed Storage Systems That Minimizes Data Storage and Repair Bandwidth, in Proc. 2006 Data Compression Conf. (DCC’2006), Snowbird, UT, USA, Mar. 20–22, 2013, p. 491. https://doi.org/10.1109/DCC.2013.72

26.

Ernvall, T., El Rouayheb, S., Hollanti, C., and Poor, H.V., Capacity and Security of Heterogeneous Distributed Storage Systems, in Proc. 2013 IEEE Int. Symp. on Information Theory (ISIT’2013), Istanbul, Turkey, July 7–12, 2013, pp. 1247–1251. https://doi.org/10.1109/ISIT.2013.6620426

27.

Benerjee, K.G. and Gupta, M.K., On Heterogeneous Regenerating Codes and Capacity of Distributed Storage Systems, https://arXiv.org/abs/1402.3801 [cs.IT], 2014.

28.

Yu, Q., Shum, K.W., and Sung, C.W., Tradeoff between Storage Cost and Repair Cost in Heterogeneous Distributed Storage Systems, Trans. Emerg. Telecommun. Technol., 2015, vol. 26, no. 10, pp. 1201–1211. https://doi.org/10.1002/ett.2887CrossRef

29.

Kiani, A. and Akhlaghi, S., Selective Regenerating Codes, IEEE Commun. Lett., 2011, vol. 15, no. 8, pp. 854–856. https://doi.org/10.1109/LCOMM.2011.061611.102271CrossRef

30.

Senthoor, K., Sasidharan, B., and Kumar, P.V., Improved Layered Regenerating Codes Characterizing the Exact-Repair Storage-Repair Bandwidth Tradeoff for Certain Parameter Sets, in Proc. 2015 IEEE Information Theory Workshop (ITW’2015), Jerusalem, Israel, Apr. 26 – May 1, 2015, pp. 224–228. https://doi.org/10.1109/ITW.2015.7133121

31.

Sasidharan, B., Senthoor, K., and Kumar, P.V., An Improved Outer Bound on the Storage-Repair-Bandwidth Tradeoff of Exact-Repair Regenerating Codes, in Proc. 2014 IEEE Int. Symp. on Information Theory (ISIT’2014), Honolulu, HI, USA, June 29 – July 4, 2014, pp. 2430–2434. https://doi.org/10.1109/ISIT.2014.6875270

32.

Sasidaran, B. and Kumar, P.V., On the Interior Points of the Storage-Repair Bandwidth Tradeoff of Regenerating Codes, in Proc. 51st Annu. Allerton Conf. on Communication, Control, and Computing, Monticello, IL, USA, Oct. 2–4, 2013, pp. 788–795. https://doi.org/10.1109/Allerton.2013.6736605

33.

Duursma, I.M., Outer Bounds for Exact Repair Codes, https://arXiv.org/abs/1406.4852 [cs.IT], 2014.

34.

Ahmad, I. and Wang, C.C., When and by How Much Can Helper Node Selection Improve Regenerating Codes?, in Proc. 52nd Annu. Allerton Conf. on Communication, Control, and Computing, Monticello, IL, USA, Sept. 30 – Oct. 3, 2014, pp. 459–466. https://doi.org/10.1109/ALLERTON.2014.7028491

35.

Ahlswede, R., Cai, N., Li, S.-Y.R., and Yeung, R.W., Network Information Flow, IEEE Trans. Inform. Theory, 2000, vol. 46, no. 4, pp. 1204–1216. https://doi.org/10.1109/18.850663CrossRef

36.

Elias, P., Feinstein, A., and Shannon, C., A Note on the Maximum Flow Through a Network, IEEE Trans. Inform. Theory,1956, vol. 2, no. 4, pp. 117–119. https://doi.org/10.1109/TIT.1956.1056816CrossRef

37.

Ford, L.R., Jr. and Fulkerson, D.R., Maximal Flow through a Network, Canad. J. Math., 1956, vol. 8, pp. 399–404. https://doi.org/10.4153/CJM-1956-045-5MathSciNetCrossRef

38.

lp_solve (mathematical optimization software). A Mixed Integer Linear Programming (MILP) Solver. Version 5.5.2.0, 2011. Available at http://lpsolve.sourceforge.net/5.5/.

Titel: Trade-off for Heterogeneous Distributed Storage Systems between Storage and Repair Cost
verfasst von: K. G. Benerjee
M. K. Gupta
Publikationsdatum: 01.01.2021
Verlag: Pleiades Publishing
Erschienen in: Problems of Information Transmission / Ausgabe 1/2021
Print ISSN: 0032-9460
Elektronische ISSN: 1608-3253
DOI: https://doi.org/10.1134/S0032946021010026

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Nachhaltigkeitsaward Key Visual/© Cometis AG/Global ESG Monitor | Daniel Rupp | Generiert mit KI, Search Icon, Banner Hanser, Jonas Klose/© Pine Valley Capital GmbH, Carina Kießling von der Strategieberatung Roland Berger/© Monika Walther Fotografie | ATZ, Beijing Auto Show 2024: Deutsche Hersteller wollen angreifen./© EKH-Pictures / Generated with AI / Stock.adobe.com, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2021

Finite Blocklength Analysis of Energy Harvesting Channels

On the Generalized Concatenated Construction for Codes in and Lee Metrics

The f-Divergence and Coupling of Probability Distributions

Affine Variety Codes over a Hyperelliptic Curve

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.