A Two-Stage Multi-Objective Optimization of Erasure Coding in Overlay Networks

ABSTRACT

In the recent years, overlay networks have emerged as a crucial platform for deployment of various distributed applications. Many of these applications rely on data redundancy techniques, such as erasure coding, to achieve higher fault tolerance. However, erasure coding applied in large scale overlay networks entails various overheads in terms of storage, latency and data rebuilding costs. These overheads are largely attributed to the selected erasure coding scheme and the encoded chunk placement in the overlay network. This paper explores a multi-objective optimization approach for identifying appropriate erasure coding schemes and encoded chunk placement in overlay networks. The uniqueness of our approach lies in the consideration of multiple erasure coding objectives such as encoding rate and redundancy factor, with overlay network performance characteristics like storage consumption, latency and system reliability. Our approach enables a variety of tradeoff solutions with respect to these objectives to be identified in the form of a Pareto front. To solve this problem, we propose a novel two stage multi-objective evolutionary algorithm, where the first stage determines the optimal set of encoding schemes, while the second stage optimizes placement of the corresponding encoded data chunks in overlay networks of varying sizes. We study the performance of our method by generating and analyzing the Pareto optimal sets of tradeoff solutions. Experimental results demonstrate that the Pareto optimal set produced by our multi-objective approach includes and even dominates the chunk placements delivered by a related state-of-the-art weighted sum method.

References

1. M. K. Aguilera, R. Janakiraman, and L. Xu. Using erasure codes efficiently for storage in a distributed system. In 2005 International Conference on Dependable Systems and Networks (DSN'05), pages 336--345, June 2005.
2. S. Bauer P. Faratin R. Sami D. Clark, B. Lehr and J. Wroclawski. Overlay networks and future of the internet. In Communications and Strategies, volume 63, page 109. ITS Communications and Strategies, 2006.
3. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. Trans. Evol. Comp, 6(2):182--197, April 2002.
4. A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran. Network coding for distributed storage systems. IEEE Trans. Inf. Theor., 56(9):4539--4551, September 2010.
5. J. J. Durillo and A. J. Nebro. jmetal: A java framework for multi-objective optimization. Advances in Engineering Software, 42:760--771, 2011.
6. D. E. Goldberg and R. Lingle. Alleles, loci, and the traveling salesman problem. In Proceedings of an International Conference on Genetic Algorithms and Their Applications, volume 154, pages 154--159. Lawrence Erlbaum, Hillsdale, NJ, 1985.
7. J. L. Hafner. Weaver codes: Highly fault tolerant erasure codes for storage systems. In Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies - Volume 4, FAST'05, pages 16--16, Berkeley, CA, USA, 2005. USENIX Association.
8. O. Al-Haj Hassan, L. Ramaswamy, J. A. Miller, K. Rasheed, and E. R. Canfield. Replication in overlay networks: A multi-objective optimization approach. In Collaborative Computing: Networking, Applications and Worksharing, 4th International Conference, CollaborateCom 2008, Orlando, FL, USA, November 13-16, 2008, Revised Selected Papers, pages 512--528, 2008.
9. T. Kanungo Kk. Rao J. L. Hafner, V. Deenadhayalan. Performance metrics for erasure codes in storage systems. 2004.
10. R. Johnston and Sun il. Kim. Secure distributed storage for information dissemination and retrieval at the tactical edge. In MILCOM 2015-2015 IEEE Military Communications Conference, pages 61--66, Oct 2015.
11. kuo Zuo-koon. Chapter 7: "the k-out-of-n system model".
12. M. Laumanns, L. Thiele, E. Zitzler, and K. Deb. Archiving with guaranteed convergence and diversity in multi-objective optimization. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, GECCO'02, pages 439--447, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.
13. G. Nychis, A. Andreou, D. Chheda, and A. Giamas. Analysis of erasure coding in a peer to peer backup system.
14. K. Pandiarajan and CK. Babulal. Fuzzy ranking based non-dominated sorting genetic algorithm-ii for network overload alleviation. Archives of Electrical Engineering, 63(3):367--384, 2014.
15. S. Saroiu, K. P. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Multimedia Computing and Networking (MMCN), January 2002.
16. R. K. Sitaraman, M. Kasbekar, W. Lichtenstein, and M. Jain. Overlay networks: An akamai perspective. In In Advanced Content Delivery, Streaming, and Cloud Services. Citeseer, 2014.
17. M. Su, L. Zhang, Y. Wu, K. Chen, and K. Li. Systematic data placement optimization in multi-cloud storage for complex requirements. IEEE Trans. Computers, 65(6):1964--1977, 2016.
18. S. Tarkoma. Overlay Networks: Toward Information Networking. Auerbach Publications, Boston, MA, USA, 1st edition, 2010.
19. Y. Wang, S. Jain, M. Martonosi, and K. Fall. Erasure-coding based routing for opportunistic networks. In Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking, WDTN '05, pages 229--236, New York, NY, USA, 2005. ACM.
20. H. Weatherspoon and J. Kubiatowicz. Erasure coding vs. replication: A quantitative comparison. In Revised Papers from the First International Workshop on Peer-to-Peer Systems, IPTPS '01, pages 328--338, London, UK, UK, 2002. Springer-Verlag.