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.