Design of fault-tolerant genetic algorithm for application placement in heterogeneous cloud environments

Ruben Mennes
Het plaatsen van applicaties is een niet triviaal probleem in heterogene cloud omgevingen. In deze scriptie wordt een methode voorgesteld om applicaties te plaatsen op een cloud waarbij applicaties een minimale beschikbaarheid hebben. Deze methode is maakt gebruik van een genetisch algoritme.

Genetische selectie: de basis voor de cloud van morgen

Normal
0

false
false
false

EN-GB
X-NONE
X-NONE

/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
mso-bidi-font-size:12.0pt;
font-family:"Liberation Serif","serif";
mso-fareast-language:ZH-CN;
mso-bidi-language:HI;}

Beeld je in dat je een dief bent die in een woonkamer staat met een lege rugzak. De rugzak kan maximaal 2 kilogram dragen en in de woonkamer bevinden zich verschillende voorwerpen met een verschillend gewicht en een verschillende waarde. Uiteraard wil je als dief de meest waardevolle voorwerpen in je rugzak steken, maar wat is de optimale oplossing en hoe kan je deze vinden? En hoe kan je dit probleem oplossen als je met een bende (meerdere dieven en meerdere rugzakken) in de woonkamer staat?

De verborgen rekenkracht van het internet

Tal van  apps voor je smartphone of tablet, duizenden websites en verschillende applicaties op je computer maken gebruik van extra rekenkracht en opslagruimte. Deze rekenkracht en opslagruimte worden tegenwoordig voorzien door miljoenen servers in een groot data center (alias ‘the cloud’). Om de rekenkracht te verdelen moet een probleem opgelost worden zoals beschreven in de inleiding. De dief is een machine (ook wel server genoemd) die een maximale capaciteit heeft en de voorwerpen zijn bepaalde applicaties die een bepaalde capaciteit aan middelen vragen. Uiteraard is er hier niet 1 ‘dief’ maar wel duizenden met allemaal dezelfde ‘rugzak’ in een data center. Om de optimale oplossing te vinden zit er niets anders op dan alle mogelijkheden afgaan om te kijken welke mogelijk het meeste applicaties kan verdelen over de verschillende machines. Voor traditionele clouds zijn er tal van algoritmes die dit probleem oplossen door een mogelijke, maar meestal niet optimale, oplossing te zoeken. Dit kan gaan van applicaties die eerst worden verdeeld op de machines met de meeste resterende capaciteit tot ingewikkelde methodes die de cloud modeleren als een markt waarbij de verschillende applicaties bieden op de rekenkracht van machines.

Een shift in strategie

Naast de traditionele clouds zien we tegenwoordig ook verschillende soorten ‘nieuwe clouds’. Deze maken gebruik van verschillende kleinere clouds om 1 grotere te vormen, hebben verschillende soorten servers op verschillende plaatsen staan, of zijn opgebouwd uit mobile machines zoals jouw laptop en smartphone. Het doel van deze nieuwe vormen: de resultaten sneller bij de gebruiker krijgen door bijvoorbeeld data dichter bij de gebruiker op te slaan. In zo’n geval wordt het probleem van applicaties te verdelen over de verschillende machines al meteen veel ingewikkelder. Er is nu meer dan 1 soort rugzak, want deze machines kunnen allemaal verschillend zijn en voor computers is er meer dan 1 parameter die kan variëren. Denk hierbij aan de hoeveelheid geheugen die de machine ter beschikking stelt, het aantal beschikbare rekenunits of processors in de machine en de snelheid van het netwerk om te communiceren met andere machines. In zo’n geval zou je een rugzak kunnen voorstellen als een rugzak die een vaste lengte, breedte en hoogte heeft. De applicaties zijn in dit geval voorwerpen met een bepaalde lengte, hoogte en breedte. Als we hiervoor de optimale oplossing willen vinden, is het eveneens noodzakelijk om alle mogelijkheden na te kijken. Voor kleine problemen kan de rekentijd die nodig is om alle oplossingen te overlopen makkelijk 30 minuten zijn. Waneer deze echter groter worder, zal de rekentijd exponetieel stijgen. Om problemen met een realistische grootte op te lossen heb je dan al snel enkele dagen nodig.

Survival of the fittest

Het vinden van de optimale oplossing mag dan heel lang duren, het vinden van een oplossing die ‘goed genoeg’ is kan meestal veel sneller gevonden worden. Een manier om een dergelijke oplossing te zoeken vinden we in de natuur, namelijk het principe van natuurlijke selectie. Het idee is dat we alle mogelijke oplossingen voorstellen in een chromosoom, vergelijkbaar met hoe DNA de genetische informatie van een levend organisme beschrijft. Door te starten met een willekeurige verzameling van chromosomen kunnen we op zoek gaan naar beter individu’s door betere chromosomen te selecteren en deze te gaan combineren. In dit geval betekent het dat er individu’s zijn die meer applicaties kunnen plaatsen (of dat er meer waarde kan meegenomen worden door onze dief). Als we vervolgens op de nieuwe ‘populatie’ of verzameling van chromosomen hetzelfde doen, namelijk de betere individu’s selecteren en die laten ‘paren’, hopen we dat deze methode ons uiteindelijk, na het genereren van een aantal generaties, een benadering geeft van de optimale oplossing. Het chromosoom uit de laatst gegenereerde generatie dat het meeste applicaties kan plaatsen beschouwen we als het beste. Dit resultaat is hopelijk een goede benadering van het optimale en kunnen we vinden in een kortere tijd.

Eerste stap voor een snelle en goede methode

Met het idee om survival of the fittest toe te passen op het probleem van het verdelen van applicaties wordt aan de slag gegaan in deze eindscriptie. Er wordt nagegaan of deze manier van denken ons een resultaat geeft dat dicht genoeg bij de optimale oplossing ligt en of het de benaderende oplossing kan vinden in een korte tijd, voor kleine en grotere problemen. Dit zal echter nog maar de eerste stap zijn in een grotere zoektocht naar een methode die het probleem van onze dief snel kan oplossen om zo de cloud van morgen mobiel te maken. 

Bibliografie
  1. 10gen Inc. Mongodb, sep 2015. URL http://www.mongodb.org.
  2. A. Broder. Generating random spanning trees. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 442–447. IEEE, 1989.

  3. J. Browne. Brewer’s cap theorem. J. Browne blog, 2009.

  4. M. Caramia and P. Dell’Olmo. Multi-objective Management in Freight Logistics. Springer-Verlag London, first edition, 2008.

  5. J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008.

  6. K. Deb. Multi-objective optimization using evolutionary algorithms, volume 16. John Wiley & Sons, 2001.

  7. K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. Lecture notes in computer science, 1917:849–858, 2000.

  8. F. Eckerstorfer. Performance of nosql databases, 2011.

  9. M. Garc ́ıa-Valdez, L. Trujillo, J.-J. Merelo, F. F. de Vega, and G. Olague. The evospace model for pool-based evolutionary algorithms. Journal of Grid Computing, pages 1–21, 2014.

  10. J. F. Gon ̧calves and M. G. Resende. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525, 2011. 

  11. J. F. Gon ̧calves, J. J. de Magalha ̃es Mendes, and M. G. Resende. A hybrid genetic algorithm for the job shop scheduling problem. European journal of operational research, 167(1):77–95, 2005.

  12. Y.-J. Gong, W.-N. Chen, Z.-H. Zhan, J. Zhang, Y. Li, and Q. Zhang. Distribu- ted evolutionary algorithms and their models: A survey of the state-of-the-art. Applied Soft Computing, 2015.

  13. J. H. Holland. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992.

  14. B. Jennings and R. Stadler. Resource management in clouds: Survey and research challenges. Journal of Network and Systems Management, pages 1–53, 2014.

  15. Oracle. Oracle technology network for java developers, sep 2015. URL http: //www.oracle.com/technetwork/java/index.html.

  16. G. Roy, H. Lee, J. L. Welch, Y. Zhao, V. Pandey, and D. Thurston. A distri- buted pool architecture for genetic algorithms. In Evolutionary Computation, 2009. CEC’09. IEEE Congress on, pages 1177–1184. IEEE, 2009.

  17. B. Spinnewyn, B. Braem, and S. Latré. Fault-tolerant application placement in heterogeneous cloud environments. 2015.

  18. The Apache Software Foundation. Apache couchdb: The apache couchdb pro- ject., sep 2015. URL http://couchdb.apache.org.

  19. A. M. Turing. I.computing machinery and intelligence. Mind, LIX(236): 433–460, 1950. doi: 10.1093/mind/LIX.236.433. URL http://mind. oxfordjournals.org/content/LIX/236/433.short.

  20. R. Yu and T. Watteren. Reliable, low power wireless sensor networks for the in- ternet of things: Making wireless sensors as accessible as web servers. Technical report, Dust Networks Product Group, Linear Technology Corp., 2013. 

 

Universiteit of Hogeschool
Master in de informatica: computernetwerken en gedistribueerde systemen
Publicatiejaar
2016
Promotor(en)
Steven Latré
Kernwoorden
Share this on: