plaatsing van service workflows in clouds

Netwerk- bewuste plaatsing van service workflows in clouds Brecht Hanssens

Promotoren: prof. dr. ir. Filip De Turck, prof. dr. ir. Bart Dhoedt Begeleider: ir. Hendrik Moens Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: elektrotechniek

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2012-2013

Netwerk- bewuste plaatsing van service workflows in clouds Brecht Hanssens

Promotoren: prof. dr. ir. Filip De Turck, prof. dr. ir. Bart Dhoedt Begeleider: ir. Hendrik Moens Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: elektrotechniek

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2012-2013

Voorwoord

Bij cloud computing wordt er wereldwijd op aanvraag van gebruikers hardware, software en gegevens op een flexibele manier beschikbaar gesteld via het internet. Gebruikers beschikken over toegang tot een in omvang en mogelijkheden schaalbare infrastructuur waarop ze applicaties kunnen uitvoeren, opslagruimte en servers kunnen huren, en dergelijke. Verscheidene algoritmen en heuristieken worden hierbij gebruikt om deze aanvragen te kunnen behandelen, die rekening houden met randvoorwaarden opgelegd door gebruikers, het netwerk van de provider, en dergelijke. Het vinden van een optimale allocatie voor de verschillende hard- en software is echter een probleem dat zeer tijdsintensief is en amper schaalbaar. Er is aldus nood aan een algoritme dat een bijna-optimale oplossing kan berekenen binnen een aanvaardbare tijd. In deze masterproef wordt dan ook gezocht naar een oplossing voor dit probleem, die zich specifiek richt op cloud omgevingen. Er wordt in dit werk ook rekening gehouden met verschillende randvoorwaarden opgelegd door gebruikers en provider, waarbij speciale aandacht is gevestigd op de impact van de netwerkinfrastructuur van een cloud provider.

Dankwoord

Graag zou ik mijn promotoren prof. dr. ir. Filip De Turck en prof. dr. ir. Bart Dhoedt willen bedanken. Bij hen kon ik altijd terecht voor verbeteringen, opmerkingen en suggesties. Zonder hen was dit eindwerk nooit tot stand gekomen.

In het bijzonder wens ik mijn begeleider ir. Hendrik Moens te bedanken voor zijn oneindige inzet gedurende het voorbije jaar, en om mij bij te staan met raad en daad waar nodig. Zonder zijn steun had ik dit nooit tot een goed einde kunnen brengen.

Brecht Hanssens, juni 2013

Toelating tot bruikleen

De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van de scriptie te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze scriptie.

Brecht Hanssens, juni 2013

Netwerk-bewuste plaatsing van service workflows in clouds Brecht Hanssens Promotoren: prof. dr. ir. Filip De Turck, prof. dr. ir. Bart Dhoedt Begeleider: ir. Hendrik Moens Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: elektrotechniek Vakgroep Informatietechnologie Faculteit Ingenieurswetenschappen en Architectuur Voorzitter: prof. dr. ir. Daniël De Zutter Academiejaar 2012-2013

Samenvatting Deze masterproef bestudeert het reserveren van apparatuur in een cloud-netwerk, voor het plaatsen van applicaties die aangevraagd worden door gebruikers. In eerste instantie wordt er onderzocht welke verschillende methoden er momenteel gebruikt worden om dit probleem op te lossen. Vervolgens wordt er in deze masterproef zelf een architectuur voorgesteld die op een hiërarchische manier een oplossing voor dit probleem kan bieden. Hiervoor werden twee algoritmen ontworpen, gebaseerd op de meta-heuristieken Particle Swarm Optimization en Genetische Algoritmen. Tevens werd er gebruik gemaakt van Integer Linear Programming om een exacte oplossing voor dit probleem te bieden bij kleine testopstellingen, dewelke kan dienen als maatstaf voor de ontworpen algoritmen.

Trefwoorden Cloud computing, Application placement, Resource allocation, Network structure, ServiceOriented Architecture, Hierarchical management, Integer Linear Programming, Meta-Heuristics, Particle Swarm Optimization, Genetic Algorithm, Performance management, Simulation

1

Hierarchical Network Aware Placement of Service Workflows in Clouds Brecht Hanssens Supervisor(s): prof. dr. ir. Filip De Turck, prof. dr. ir. Bart Dhoedt Attendant(s): ir. Hendrik Moens

Abstract—In cloud-networks, users can request a variety of applications. When calculating a decent placement for these applications, they are often still considered to be monolithic entities. Recent architectural trends however tend to built applications around communicating services, such as in a Service-Oriented Architecture (SOA). However, few placement algorithms really take the underlying network-infrastructure into account. We propose a model for the placement problem which copes with the network-aspect of a cloud provider, and is designed to deal with applications built conforming a SOA. This model was used to define an Integer Linear Program to calculate exact solutions. Two hierarchically algorithms, based on Particle Swarm Optimization and Genetic Algorithms, were designed to calculate scalable near-optimal solutions for this problem. Index Terms—Cloud, Application Placement, Service-Oriented Architecture, Particle Swarm Optimization, Genetic Algorithms

T

I. I NTRODUCTION

HE Application Placement Problem (APP) in cloudnetworks is an important aspect for many providers. Applications that are requested by end-users need to be instantiated on various resources, such as servers or specialized hardware. Solutions for this problem need to be in accordance to certain preconditions, making the task to calculate a decent placement not a trivial one. Exact solutions can be computed by making use of Integer Linear Programming (ILP), but are NP-hard. This makes the calculation very time-consuming, and hardly scalable when the number of requests, applications, or resources changes over time. In our research, we consider that applications are built conforming a Service-Oriented Architecture (SOA). In such an architecture, applications are constructed by combining a set of communicating services. The services of each application are then instantiated on resources in the network, which are possibly physically separated. In this scenario, communication is required between these different resources, and the impact on the underlying network should therefore not be abstracted in the problem statement. We propose a model for the APP which takes the networkinfrastructure of a cloud provider into account, and is designed to deal with applications built conforming a SOA. This model was used to define an Integer Linear Program to calculate exact solutions, for benchmarking purposes. Two hierarchically algorithms, based on Particle Swarm Optimization (PSO) [1] and Genetic Algorithms (GA) [2], were designed to calculate scalable near-optimal solutions for this problem. Both approaches make use of a population of possible solutions in

each iteration. However, both tackle the problem in a different way, making them interesting to compare with each other. In Section II, the APP is stated. A system architecture to tackle this problem is discussed in Section III, while the algorithms that were implemented to solve it are explained in Section IV. An evaluation of these algorithms can be found in Section V, while some of the conclusions of our research are summarized in Section VI. II. P ROBLEM S TATEMENT The APP can be stated as follows: consider a set of applications that are constructed by combining different communicating services, and a set of resources on which these services can be instantiated. Given both sets, calculate a placement of which services need to be instantiated on which resources, in order to satisfy a given objective. It was already noted that solutions for this problem need to be in accordance to various preconditions. A list of these preconditions is given below: • Resources have limited CPU- and memory-capacities. • Some services cannot be instantiated on every resource, due to the requirement of specific hardware, software, or because of business- or security policies. • Communication links between resources in the network have limited bandwidth-capacities. We consider a dynamic placement, where the amount of requests per application changes over time. The objectives of the APP during each iteration are summarized as follows: • Accept those requests of end-users, ensuring that as much CPU-capacity is placed in the network as possible. • Use the least possible amount of resources to do so. • Minimize the amount of service-instance changes between two iterations of the APP solver. • Maximize the workflow-demand between two communicating services, with a minimum of 80% guaranteed. • When taking the hop count between resources into account as a cost metric per unit flow, minimize the total cost of all service workflows in the network [3]. III. S YSTEM A RCHITECTURE In this work, we assume that all resources in the network of a cloud provider are divided in a hierarchical manner into managing- and executing-resources [4]. This process is done according to parent-child relationships between resources, allowing the network to be represented as a hierarchical tree. In our approach, we use four layers to manage the

2

network, organized as in Fig. 1. The top three layers represent managing-resources, hierarchically managing other managingresources or executing-resources. The bottom layer solely consists of executing-resources, which are used to execute the service-instances. A hierarchical approach requires a limited view of the network on each layer, making the calculation of a placement faster and more robust and scalable than a centralized approach. remaining requests

In a first evaluation, we consider a small setup with no bandwith limitations. Here, we take a look at the number of accepted requests for applications, compared to the total amount of requests. The CPU Load Factor (CLF) indicates how much CPU-capacity is needed to accept all requests, compared to the total CPU-capacity of the network. It can be noticed from Fig. 2 that both the PSO- and GA-algorithm perform reasonably well compared to the ILP, which only performs 8% better than both algorithms given a CLF of 1.

…

…

Executing resources

System architecture for the APP.

Initially, all requests are passed to the managing-resource whose children are executing-resources, and is the least occupied when considering the ratio between occupied and total available CPU-capacity. This managing-resource will first execute the APP solver. All requests that could not be placed by this resource are passed on to higher managing-resources. IV. A PPLICATION P LACEMENT A LGORITMS A. Integer Linear Programming (ILP) The problem statement, discussed in Section II, was used to define an ILP which was implemented in Java with CPLEX, a commercial ILP solver. This solver yields the optimal solution for the APP using Simplex and Branch and Bound algorithms.

1.2

Ratio of placed requests

Figure 1.

A. ILP versus PSO and GA, small setup

Managing resources

remaining requests

…

V. E XPERIMENTAL R ESULTS

0.8 0.6 0.4 0.2 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00

CPU Load Factor (CLF)

Figure 2.

Ratio of placed requests versus received requests.

B. PSO versus GA, large setup In a second evaluation, we consider a large setup with bandwidth limitations. Here, the workflow-demand of two communicating services will have a significant impact on the network infrastructure. Some workflows will not be able to guarantee a satisfaction of at least 80% due to bandwidth preconditions in the network, limiting the amount of requests that can be accepted. The average amount of workflowsatisfaction is illustrated in Fig. 3. 1

B. PSO- and GA-based algorithms

PSO GA

0.98 0.96 Workflow voldoening

To cope with the issue of scalability we designed two hierarchically algorithms, based on PSO and GA, to calculate scalable near-optimal solutions for this problem. PSO works with a swarm of particles, represented by positions, and evolve in each iteration based on the knowledge of each particle and the entire swarm. The genetic algorithm on the other hand works with a pool of individuals, and mimics the process of natural evolution to search for different solutions. We have used JGraphT, a Java library, to cope with the placement of service workflows in the network. By extending this library to implement the Successive Shortest Path algorithm (SSP) [5], we can solve the Minimum Cost Flow Problem (MCFP) to minimize the total cost of all workflows. Initially, all workflow-demands will be guaranteed a satisfaction of 80%. When the amount of requests for applications that could be accepted under all considered circumstances is determined, all workflows are processed again. In this final stage, the amount of workflow-satisfaction is maximized under the limited bandwidth precondition in the network.

ILP PSO GA

1

0.94 0.92 0.9 0.88 0.86 0.84 0.82 0.8 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figure 3.

Average workflow-satisfaction.

In Fig. 3, we can see that the amount of workflowsatisfaction will start taking a drop from a CLF of 0.40 on. When the CLF gets higher than 0.80, communication-links in the network will start getting saturated, and form a significant bottleneck towards the placement of applications. From this CLF on, only a certain amount of requests for applications will be able to get accepted by a cloud provider, under the limited bandwidth precondition of his network infrastructure.

3

Ratio of placed requests

1.2

PSO GA

1 0.8 0.6 0.4 0.2 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figure 4.

Ratio of placed requests versus received requests.

In Fig. 4, the ratio of placed requests for applications versus received requests is illustrated. We can see that the placement of applications indeed decreased from a CLF of 0.40 on, as predicted by the average workflow-satisfaction. Both algorithms almost perform equally well, with the PSObased algorithm capable of handling more requests than the GA-based one up until a CLF of 0.80. Due to the fact that the average workflow-satisfaction with the PSO-based algorithm is lower than with the GA-based one, all communicationlinks in the network are less saturated. This in turn explains why the PSO-based algorithm is capable of accepting more requests for applications. From a CLF of 0.80 on, the network is expected to be fully saturated, and both algorithms have the same performance. VI. C ONCLUSION In this work, a model for the APP was presented which takes the network-infrastructure of a cloud provider into account, and was designed to deal with applications built conforming a SOA. Two hierarchically algorithms based on PSO and GA were designed to calculate scalable near-optimal solutions for this problem. Based on our theoretical model, an ILP was defined in order to estimate the performance of both algorithms. Results have indicated that in a worst case scenario, where the total amount of CPU-capacity in the network is needed to handle all requests, the ILP only performs 8% better than both implemented algorithms. Under circumstances with bandwidth limitations in the network of a cloud provider, the PSO-based algorithm slightly outperforms the GA-based algorithm up until the point where this network is bandwidth-wise fully saturated. R EFERENCES [1] J. Kennedy and R. Eberhart, “Particle Swarm Optimization,” in Proceedings of the 4th IEEE International Conference on Neural Networks (ICNN). IEEE Computer Society, 1995, pp. 1942–1948. [2] M. Mitchell, An Introduction to Genetic Algorithms. MIT Press, 1998. [3] C. Low, “Decentralised Application Placement,” Future Generation Computer Systems, vol. 21, no. 2, pp. 281–290, 2005. [4] H. Moens, J. Famaey, S. Latré, B. Dhoedt, and F. De Turck, “Design and Evaluation of a Hierarchical Application Placement Algorithm in Large Scale Clouds,” in Proceedings of the 12th IFIP/IEEE International Symposium on Integrated Network Management (IM). IEEE Computer Society, 2011, pp. 137–144. [5] J. Edmonds and R. M. Karp, “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems,” ACM, vol. 19, no. 2, pp. 248– 264, 1972.

Inhoudsopgave 1 Introductie

1

1.1

Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Oplossing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Opdeling van de masterproef . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2 Literatuurstudie 2.1

2.2

2.3

2.4

5

Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1.1

Algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1.2

Kenmerken van Cloud Computing . . . . . . . . . . . . . . . . . . . . . .

7

Application Placement Problem (APP) . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2.1

Algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2.2

Nood aan heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2.3

Kwaliteitsmaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2.4

APP met netwerk-onbewuste algoritmen . . . . . . . . . . . . . . . . . . .

15

2.2.5

APP met netwerk-bewuste algoritmen . . . . . . . . . . . . . . . . . . . .

16

Variability Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.3.1

Algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.3.2

Service-Oriented Architecture (SOA) binnen Variability Modeling

. . . .

19

2.3.3

Software Product Line Engineering (SPLE) . . . . . . . . . . . . . . . . .

20

2.3.4

Complexiteit bij APP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

Resource beheer in de cloud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.4.1

Architectuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.4.2

Schaalbaarheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

i

ii

INHOUDSOPGAVE

2.4.3

Dynamische plaatsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Probleemstelling

26 29

3.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.2

Netwerk-bewuste plaatsing van service workflows . . . . . . . . . . . . . . . . . .

32

3.2.1

Maximaliseren van het aantal geaccepteerde aanvragen . . . . . . . . . . .

34

3.2.2

Maximaliseren van de communicatie-voldoening van elke workflow . . . .

37

3.2.3

Minimaliseren van het aantal gebruikte nodes bij de plaatsing . . . . . . .

40

3.2.4

Minimaliseren van het aantal verplaatsingen tussen twee iteraties . . . . .

41

3.2.5

Maximaliseren van de service workflow efficiëntie . . . . . . . . . . . . . .

42

4 Architectuur

45

4.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.2

Architecturale vereisten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.3

Voorgestelde systeemarchitectuur . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.3.1

Hiërarchische boomstructuur binnen het netwerk . . . . . . . . . . . . . .

47

4.3.2

Schematische voorstelling van het volledige systeem . . . . . . . . . . . .

48

4.3.3

Benodigde bouwblokken . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

Gebruiksscenario: behandelen van nieuwe aanvragen . . . . . . . . . . . . . . . .

54

4.4

5 Algoritmen

57

5.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

5.2

Integer Linear Programming (ILP) . . . . . . . . . . . . . . . . . . . . . . . . . .

58

5.2.1

ILP APP algoritme

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

5.2.2

Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

Particle Swarm Optimization (PSO) . . . . . . . . . . . . . . . . . . . . . . . . .

59

5.3.1

PSO algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

5.3.2

PSO APP algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

Genetische Algoritmen (GA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.4.1

GA algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.4.2

GA APP algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

5.3

5.4

6 Evaluatie 6.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79 79

INHOUDSOPGAVE

6.2

6.3

iii

Vergelijkende studie tussen ILP, PSO en GA . . . . . . . . . . . . . . . . . . . .

79

6.2.1

Testopstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

6.2.2

Bepaling van het aantal aanvragen per applicatie . . . . . . . . . . . . . .

81

6.2.3

Plaatsing van CPU-capaciteit . . . . . . . . . . . . . . . . . . . . . . . . .

82

6.2.4

Plaatsing van aanvragen . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

6.2.5

Aantal gebruikte nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

6.2.6

Aantal verplaatsingen tussen twee iteraties . . . . . . . . . . . . . . . . .

87

6.2.7

Totale netwerkkost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

6.2.8

Benodigde verwerkingstijd . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

Vergelijkende studie tussen PSO en GA . . . . . . . . . . . . . . . . . . . . . . .

92

6.3.1

Testopstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

6.3.2

Beperkte bandbreedte in het netwerk . . . . . . . . . . . . . . . . . . . . .

92

6.3.3

Plaatsing van CPU-capaciteit . . . . . . . . . . . . . . . . . . . . . . . . .

95

6.3.4

Plaatsing van aanvragen . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

6.3.5

Aantal gebruikte nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . .

97

6.3.6

Aantal verplaatsingen tussen twee iteraties . . . . . . . . . . . . . . . . .

98

6.3.7

Totale netwerkkost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

6.3.8

Benodigde verwerkingstijd . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

7 Conclusie

103

7.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.2

Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.3

Verder onderzoek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.3.1

Hiërarchische boomstructuur . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.3.2

Ontworpen algoritmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Bibliografie

114

Lijst van figuren

116

Lijst van tabellen

117

Lijst van algoritmen

119

Lijst met acroniemen ACO

Ant Colony Optimization

APP

Application Placement Problem

BRS

Best Resource Selection

CLF

CPU Load Factor

CVF

CPU Voldane Factor

EA

Evolutionary Algorithms

FPP

Feature Placement Problem

FPS

Fitness Proportionate Selection

GA

Genetic Algorithms

IaaS

Infrastructure as a Service

ILP

Integer Linear Programming

LP

Linear Programming

MCFP Minimum-Cost Flow Problem NIST

National Institute of Standards and Technology

PaaS

Platform as a Service

PSO

Particle Swarm Optimization

QoS

Quality of Service

RVF

Request Voldane Factor

SaaS

Software as a Service

SOA

Service-Oriented Architecture

SPLE

Software Product Line Engineering

SSP

Successive Shortest Path

UML

Unified Modeling Language

Hoofdstuk 1

Introductie 1.1

Probleemstelling

Bij cloud computing wordt er wereldwijd op aanvraag van gebruikers hardware, software en gegevens op een flexibele manier beschikbaar gesteld via het internet. Gebruikers beschikken over toegang tot een in omvang en mogelijkheden schaalbare infrastructuur waarop ze verschillende applicaties kunnen uitvoeren. Deze worden dan toegewezen aan allerlei vormen van apparatuur (servers, databases) in het netwerk. Bij dit probleem worden verscheidene algoritmen en heuristieken gebruikt om deze aanvragen te kunnen behandelen, die voldoen aan randvoorwaarden opgelegd door gebruikers en provider. Er kan onder andere rekening worden gehouden met de fysische topologie van het netwerk van de provider [44, 20, 42], kwaliteitseisen opgelegd door de eindgebruikers [26, 9] en de architectuur van het systeem op zich [32, 40, 18]. Het vinden van een optimale allocatie voor de verschillende apparatuur onder zulke voorwaarden is een probleem dat NP-hard is [55, 48]. Dit maakt dat het vinden van een exacte oplossing zeer tijdsintensief is en amper schaalbaar wat betreft het aantal aanvragen, applicaties en resources. Het bekomen van zulke exacte oplossingen kan gebeuren door middel van Integer Linear Programming (ILP) [59], doch het toepassen van deze techniek is amper bruikbaar in de praktijk wegens de grote uitvoertijd en de beperkte schaalbaarheid. Bij het berekenen van een geschikte plaatsing voor deze applicaties, worden deze nog te vaak beschouwd als monolithische entiteiten. Recente architecturale trends bouwen echter applicaties door een aantal communicerende services met elkaar te verbinden, zoals wordt gedaan binnen

1

2

HOOFDSTUK 1. INTRODUCTIE

een Service-Oriented Architecture (SOA). Echter, weinig algoritmen houden rekening met de impact daarvan op de onderliggende netwerkinfrastructuur van een provider. Er is aldus nood aan een schaalbaar algoritme dat een bijna-optimale oplossing kan berekenen binnen een aanvaardbare tijd. In deze masterproef wordt dan ook gezocht naar een oplossing voor dit probleem, die zich specifiek richt op cloud omgevingen. Er wordt in dit werk ook rekening gehouden met verschillende randvoorwaarden opgelegd door gebruikers en provider, waarbij speciale aandacht is gevestigd op de impact van de netwerkinfrastructuur. Clouds zijn een relatief nieuw gegeven, waardoor nog veel onderzoek mogelijk is naar technieken om deze plaatsing zo efficiënt mogelijk te maken onder variërende omstandigheden en randvoorwaarden.

1.2

Doelstelling

Het doel van deze masterproef is om vertrekkende vanuit het standpunt van de cloud provider een bijna-optimale plaatsing te berekenen van de applicaties en resources die gebruikers aanvragen. Hierbij wordt speciale aandacht gevestigd op de netwerkinfrastructuur van zo’n provider (fysische ligging en capaciteiten van de nodes, beperkte communicatie tussen nodes). In dit werk wordt verondersteld dat applicaties opgebouwd zijn op basis van een SOA, waardoor het uitvoeren van zulke applicaties gebeurt door middel van verscheidene services die met elkaar communiceren. Deze services worden in het netwerk van een provider uitgevoerd op resources die fysisch verspreid kunnen liggen, waardoor er communicatie vereist is tussen de verschillende nodes waarop deze applicatie wordt uitgevoerd. In deze masterproef wordt geprobeerd om bestaande state of the art algoritmen voor dit probleem te verbeteren door gebruik te maken van verscheidene heuristieken. Er wordt vooral gekeken naar hoe de aanvragen en specificaties van eindgebruikers zich vertalen naar de uiteindelijke plaatsing van applicaties op resources, en hoe verschillende metrieken die gepaard gaan met deze plaatsing kunnen geoptimaliseerd worden. Er wordt hierbij uitgegaan van een dynamische situatie, waarbij de aanvragen van gebruikers en aldus ook de optimale allocatie van resources variabel is in de tijd. Dit maakt dat er onder deze wisselende omstandigheden telkens een nieuwe oplossing gevonden moet worden binnen een aanvaardbare tijd. Er wordt ook onderzocht hoe schaalbaar deze oplossing is wanneer er gekeken wordt naar grootschalige problemen, en hoe accuraat de plaatsing gebeurt in vergelijking met een exacte oplossing. Het bekomen van zulke exacte oplossingen is zoals eerder aangehaald zeer tijdsintensief en am-

1.3. OPLOSSING

3

per schaalbaar. Heuristieken zijn daarom vaak een bruikbaar alternatief, doordat ze benaderde oplossingen kunnen bekomen binnen een aanvaardbare tijd. Verscheidene heuristieken worden dan ook ge¨ımplementeerd en onderzocht op basis van hun schaalbaarheid en efficiëntie.

1.3

Oplossing

Deze masterproef bestudeert het reserveren van apparatuur in een cloud-netwerk, voor het plaatsen van applicaties die aangevraagd worden door gebruikers. In eerste instantie wordt er een literatuurstudie uitgevoerd van welke verschillende methoden er momenteel gebruikt worden om dit probleem op te lossen [20, 42, 9, 60, 32, 17]. Vervolgens wordt zelf een architectuur voorgesteld die op een hiërarchische manier een oplossing voor dit probleem kan bieden. Hiervoor werden twee algoritmen ontworpen, gebaseerd op de meta-heuristieken Particle Swarm Optimization (PSO) [25] en Genetische Algoritmen (GA) [39]. Tevens werd een wiskundig model opgesteld van dit probleem om exacte oplossingen te verkrijgen, dewelke ge¨ımplementeerd is met behulp van Integer Linear Programming (ILP) [59]. Het toepassen van deze techniek is amper bruikbaar in de praktijk wegens de grote uitvoertijd en de beperkte schaalbaarheid, doch kan dienen als maatstaf voor de ontworpen algoritmen bij een kleine testopstelling. PSO en GA zijn beiden iteratieve algoritmen die telkens werken met een verzameling van mogelijke oplossingen. In elke iteratie worden nieuwe oplossingen gegenereerd die kenmerken bezitten van de huidige oplossingenverzameling. Hoe dit concreet gebeurt bij beide algoritmen is echter verschillend, wat beide algoritmen interessant maakt om ze te vergelijken. PSO maakt gebruik van een oplossingenruimte waarbij de oplossingen worden voorgesteld als geometrische punten in een wiskundige ruimte. Om elke oplossing te verbeteren wordt bij PSO gebruikt gemaakt van vectoren waarbij de posities en snelheden van andere oplossingen in acht worden genomen. GA daarentegen maken gebruik van een populatie van oplossingen, waarin elke oplossing een bepaald individu voorstelt. Om een nieuwe populatie van individuen te creëren wordt bij het GA gebruik gemaakt van technieken ge¨ınspireerd op de natuurlijke evolutie. De nadruk ligt in deze masterproef vooral op de implementatie en evaluatie van deze algoritmen, alsmede op verscheidene inspanningen om de impact op het onderliggende netwerk zo klein mogelijk te houden. Hierbij wordt onder andere rekening gehouden met de kost omtrent het gebruik van resources, het instantiëren van services, alsmede de impact op het netwerk die resulteert uit de communicatie tussen de verschillende services.

4

1.4

HOOFDSTUK 1. INTRODUCTIE

Opdeling van de masterproef

Het verdere verloop van deze masterproef is als volgt opgedeeld. In hoofdstuk 2 wordt onderzocht welke technologieën en methoden er momenteel gebruikt worden om het betreffende probleem op te lossen. De verschillende oplossingsmogelijkheden worden er tegen elkaar afgewogen, en er wordt uitgelegd waarom er voor een alternatieve aanpak is gekozen. In hoofdstuk 3 wordt uitvoerig de probleemstelling besproken onder de vorm van een wiskundig model, waarna in hoofdstuk 4 de architectuur wordt uitgelegd waarbinnen ons probleem zich afspeelt. Hoofdstuk 5 biedt vervolgens een overzicht van de ontworpen algoritmen die gebruikt werden om dit probleem op te lossen. In hoofdstuk 6 volgt er een evaluatie van het geleverde werk inzake de efficiëntie van een oplossing, de schaalbaarheid ervan, en hoe snel deze oplossing bekomen kan worden. Ten slotte wordt er in hoofdstuk 7 afgerond met een aantal conclusies en voorstellen voor toekomstige onderzoek.

Hoofdstuk 2

Literatuurstudie 2.1 2.1.1

Cloud Computing Algemeen

Bij public cloud computing wordt er wereldwijd op aanvraag van gebruikers hardware, software en gegevens op een flexibele manier beschikbaar gesteld via het internet. Gebruikers beschikken over toegang tot een in omvang en mogelijkheden schaalbare infrastructuur waarop ze applicaties kunnen uitvoeren, opslagruimte en servers kunnen huren, en dergelijke. Het concept van cloud computing heeft een groot voordeel ten opzichte van traditionele hosting, namelijk dat er geen initiële kost verbonden is aan het huren van de resources. Er kan ook veel sneller ingespeeld worden op een toenemende of afnemende vraag naar deze resources, waarbij men simpelweg betaalt voor wat men effectief gebruikt [5]. Dit is allemaal in tegenstelling tot traditionele hosting, waarbij men contractueel op voorhand bepaalt om een vaste hoeveelheid resources te huren gedurende een overeengekomen periode [56]. Cloud computing kan op deze manier gezien worden als een nutsvoorziening zoals water of elektriciteit, waarbij het merendeel van de kost ook bepaald wordt door de hoeveelheden die men gebruikt [8]. De cloud staat voor een netwerk dat met alle componenten die erop aangesloten zijn een soort wolk vormt, zoals ook voorgesteld wordt in figuur 2.1. Gebruikers beschikken echter vaak over weinig informatie en inspraak omtrent de onderliggende infrastructuur. De details hiervan worden voor de gebruikers door middleware geabstraheerd. Deze middleware zorgt voor de informatie-uitwisseling tussen de software van gebruikers en de hard- en software die door een

5

6

HOOFDSTUK 2. LITERATUURSTUDIE

cloud provider wordt beheerd. Gebruikers hoeven aldus niet meer in te staan voor het virtualiseren van resources, onderhoud van servers, opslag van data en bepaalde netwerkaspecten. Ze hoeven op deze manier dus geen eigenaar meer te zijn van de gebruikte hard- en software, en zijn dus ook niet meer verantwoordelijk voor het onderhoud ervan [43].

Figuur 2.1: Een grafische weergave van cloud computing.

De cloud volgens NIST Het National Institute of Standards and Technology (NIST), een wetenschappelijk instelling die zich inzet voor het normaliseren van uitdrukkingen en standaarden, beschrijft de cloud als volgt [33]: Cloud computing is een model voor het inschakelen van alomtegenwoordige, handige, netwerktoegang op aanvraag tot een gedeelde bron van configureerbare IT-middelen (bijvoorbeeld netwerken, servers, opslag, applicaties en diensten) die snel kunnen worden gereserveerd en vrijgegeven met minimaal beheer, moeite of interactie met een dienstverlener.

2.1. CLOUD COMPUTING

7

De evolutie naar cloud computing leidt ertoe dat de informaticawereld stelselmatig verschuift naar het ontwerpen van software voor miljoenen gebruikers tegelijkertijd. Gebruikers kunnen dan simpelweg software consumeren als een dienst bij een software provider, in plaats van ze zelf uit te voeren op hun eigen machines. Deze provider maakt op zijn beurt gebruik van de cloud om een flexibele infrastructuur te bekomen die in omvang zeer schaalbaar en robuust is tegen falen. Enkele kenmerken van deze manier van computing worden hieronder behandeld.

2.1.2

Kenmerken van Cloud Computing

Elasticiteit van resources Een voordeel van cloud computing is de elasticiteit waarmee resources (servers, databases) kunnen worden toegekend aan gebruikers [33]. Zoals eerder al aangehaald kan er veel sneller ingespeeld worden op een toenemende (of afnemende) aanvraag van resources dan bij een conventioneel datacenter. Het toevoegen of verwijderen van deze hoeveelheid apparatuur kan immers gebeuren binnen een periode van enkele minuten [5]. Dit zorgt ervoor dat er veel beter ingespeeld kan worden op de overeenkomst tussen de huidige werklast van de eindgebruikers en de hoeveelheid resources die wordt gehuurd in de cloud. Eindgebruikers ervaren de cloud immers als een soort entiteit die een ongelimiteerde hoeveelheid middelen ter beschikking heeft, die ze op aanvraag kunnen huren. De cloud is daardoor zeer aantrekkelijk bij bedrijven die klein willen starten, waarna ze simpelweg soft- en hardware bijhuren wanneer daar nood aan is. Instanties bij Amazon kunnen toegekend worden in een tijdsperiode van 2 à 5 minuten [5]. Vele Java 2 Enterprise Edition (J2EE) applicaties hebben een vergelijkbare tijd nodig om op te starten [53]. De grootteorde van het algoritme dat een plaatsing berekent van welke applicaties dienen uitgevoerd te worden op welke resources is aldus ook enkele minuten.

Service modellen Een cloud provider kan verschillende diensten via het internet aanbieden aan zijn gebruikers. De voornaamste worden hieronder kort even opgesomd: • Software as a Service (SaaS): De cloud provider biedt software aan als een online dienst. De gebruiker hoeft deze software niet meer in zijn eigen omgeving te installeren, en betaalt dus ook geen licentie- of onderhoudskosten meer [52]. Het is de cloud provider die zorgt voor

8


de installatie, het onderhoud en beheer van de software [33]. De gebruiker benadert dan de software via het internet met behulp van een webbrowser. • Platform as a Service (PaaS): Hierbij wordt een gemeenschappelijke infrastructuur aangeboden waar applicaties op kunnen worden aangemaakt en uitgevoerd. Omdat het volledige platform wordt aangeboden als een SaaS is er geen installatie van servers en applicaties nodig, aangezien het management van de infrastructuur wordt afgehandeld door de cloud provider zelf [10]. De gebruiker kan op deze manier wel verder instaan voor de applicaties en services, waarbij vaak wordt gewerkt met een ontwikkelingstaal zoals Python, .NET of Java. • Infrastructure as a Service (IaaS): Dit is een vorm van cloud computing waarbij infrastructuur virtueel wordt aangeboden aan gebruikers. Deze infrastructuur bestaat vooral uit hardware zoals onder andere servers, netwerkapparatuur, opslagmedia en workstations. De gebruiker staat niet zelf in voor het beheer van de onderliggende infrastructuur, doch heeft wel controle omtrent het gebruik ervan [33]. De desktopomgeving voor de configuratie en het beheer van deze hardware wordt virtueel aangeboden aan de gebruikers via het internet. Het besturingssysteem en alle verdere software worden afgehandeld door de cloud provider.

Cloud modellen Clouds bestaan onder verschillende vormen. De belangrijkste worden hier kort even opgesomd: • Publiek: In de algemene vorm van cloud computing werkt men altijd publiek, ook wel extern genoemd. De software en data staan hierbij volledig op de servers van een externe provider [33], en worden aangeboden op een ‘pay-as-you-go’ manier aan gebruikers [5]. Publieke cloud providers zoals Amazon, Microsoft and Google beheren volledig de infrastructuur, en bieden enkel toegang tot de cloud via het internet. Een directe connectiviteit naar de cloud is bij deze vorm van cloud computing niet mogelijk. • Privaat: Bij een private cloud wordt de interne infrastructuur van een organisatie ingericht als een cloud-omgeving [51]. Applicaties worden via deze private cloud beschikbaar gemaakt voor leden en klanten van deze organisatie, maar worden niet gedeeld met anderen [5]. Een nadeel van een private cloud is dat er binnen deze interne infrastructuur maar een gelimiteerde hoeveelheid middelen ter beschikking is voor de gebruikers ervan. Binnen deze omgeving dient er gewerkt te worden met de resources die de organisatie ter beschikking stelt.

2.1. CLOUD COMPUTING

9

• Community: In een community cloud is de toegang gelimiteerd tot een specifieke gemeenschap, bijvoorbeeld een groepering van organisaties die gedeelde belangen hebben (inzake doelstelling, beveiliging, bedrijfspolicy of andere) [33]. De cloud wordt voorzien en beheerd door een of meerdere van de organisaties in de gemeenschap, en kan intern gehost worden (infrastructuur van een bepaalde organisatie) of extern (datacenter ingericht als cloud). • Hybride: Bij een hybride cloud zal een deel van de services uitgevoerd worden in een externe cloud omgeving, terwijl een ander deel wordt uitgevoerd binnen de eigen infrastructuur van een organisatie. In het publieke deel van deze soort cloud kan men een ogenschijnlijk onbeperkt aantal resources aanvragen [5]. In de private omgeving dient men zich echter te houden aan eindige netwerken server capaciteiten [42]. Vaak kan er niet anders dan met een hybride cloud worden gewerkt, aangezien sommige taken niet uitgevoerd kunnen/mogen worden in een publieke cloud. Denken we hierbij bijvoorbeeld aan gespecialiseerde apparatuur of software die enkel in het eigen netwerk terug te vinden zijn, of om beleidsredenen van een bedrijf [42]. Werken met een hybride cloud maakt het plaatsen van applicaties op resources complexer, aangezien het mogelijk is dat bepaalde services enkel kunnen uitgevoerd worden in het private deel van het netwerk, doch wel communiceren met andere services in de publieke cloud. Dit heeft een impact op de complexiteit van het algoritme dat een plaatsing berekent, en kan mogelijk grote tijdsvertragingen introduceren als de verschillende nodes waarop services uitgevoerd worden ver uit elkaar liggen [7].

Pay-as-you-go Een ander voordeel van cloud computing ten opzichte van conventionele hosting is dat het risico bij het over- of onderschatten van de hoeveelheid resources die men denkt nodig te hebben, verschoven wordt van de aanbieder van de service zelf naar de cloud provider toe [5]. Zoals eerder al aangehaald zal men bij traditionele hosting vooraf een contract opstellen waarin overeengekomen wordt om een vaste hoeveelheid resources (bijvoorbeeld servers) te huren gedurende een specifieke periode. De belangstelling voor de applicaties die op deze servers draaien is echter vaak afhankelijk van het moment van de dag. Voor heel wat applicaties is er bijvoorbeeld ’s nachts veel minder vraag naar dan overdag. Bij de huur van servers in een datacenter zal er echter gekeken worden naar het piekmoment inzake aanvragen, waardoor men aldus met een overschot aan resources zit op andere, mindere drukke, momenten. Wanneer men deze piek overschat zit

10


men met een extra verspilling van resources, aangezien deze nooit gebruikt worden. Wanneer men dan weer deze piek onderschat zit men met een inkomstenverlies, aangezien gebruikers niet bediend zullen worden wegens een gebrek aan servers om hen daarbij te assisteren. Als ze echter wel bediend worden zullen ze mogelijk grote tijdsvertragingen ondervinden, aangezien alle servers aan hun volle capaciteit werken [5]. Aangezien cloud computing veel sneller kan inspelen op de elasticiteit waarmee diensten en resources worden aangevraagd, kan men de uitgaven van een bedrijf sterk verlagen. Men betaalt immers enkel voor wat men effectief gebruikt, waarbij gesproken wordt van ‘pay-as-you-go’ [5].

2.2 2.2.1

Application Placement Problem (APP) Algemeen

Het Application Placement Problem (APP) kan als volgt omschreven worden: gegeven een bepaalde set van applicaties en nodes, zoek uit welke applicaties op welke nodes moeten uitgevoerd worden om zoveel mogelijk aan de vraag van eindgebruikers te kunnen voldoen. Deze gebruikers kunnen bij hun aanvragen prioriteiten voorop stellen, en tevens uitgesproken eisen hebben in verband met de diensten die worden geleverd door de cloud [26, 20, 9]. Wanneer gebruikers bijvoorbeeld een bepaalde responstijd verwachten van de applicaties die ze in de cloud uitvoeren, zal dit de complexiteit van het algoritme dat de plaatsing berekent alleen maar verhogen. Communicerende services die uitgevoerd worden op nodes die geografisch ver uit elkaar liggen, of verbonden zijn met een communicatielink waarover veel dataverkeer stroomt, kunnen daardoor een hoge responstijd opleveren. Algoritmen die een plaatsing berekenen zullen dus best dit soort nodes vermijden om een paar communicerende services op uit te voeren. Tevens dienen deze algoritmen ook rekening te houden met het feit dat niet elke server beschikt over de gepaste instanties om een bepaald type van applicatie of service op uit te voeren. Bij het APP dient er ook rekening gehouden te worden met verschillende beperkingen. Servers hebben immers eindige capaciteiten inzake CPU en geheugen, alsmede beperkingen omtrent welk type van applicatie of service erop uitgevoerd kan worden. Indien applicaties gebruik maken van specifieke randapparatuur, of wegens bedrijfspolicy niet overal uitgevoerd mogen worden [42], zal er maar een beperkte set van alle servers geschikt zijn voor de uitvoering van deze applicatie. Communicatielinks tussen servers beschikken dan weer over een beperkte bandbreedte en een bepaalde tijdsvertraging. Het doel van het APP is om onder deze omstandigheden zoveel mo-

2.2. APPLICATION PLACEMENT PROBLEM (APP)

11

gelijk aan de vraag van eindgebruikers te voldoen, aldus rekening houdend met de verschillende beperkingen opgelegd door de gebruikte netwerkinfrastructuur. Algoritmen die het APP behandelen kunnen opgesplitst worden in twee grote groepen. Er zijn diegene die rekening houden met het onderliggende fysische netwerk van een cloud provider, en er zijn diegene die er abstractie van maken. Het is vrij evident dat de complexiteit van de gebruikte algoritmen om een oplossing te berekenen voor het APP alleen maar toeneemt wanneer dit netwerkaspect in acht wordt genomen. Deze algoritmen zullen dan ook vaak een grotere uitvoertijd nodig hebben dan diegene die dit niet doen. Immers, er zijn meer randvoorwaarden waarmee zulke algoritmen rekening moeten houden, wat ook zijn impact zal hebben op de resulterende plaatsing. Het grote voordeel van deze algoritmen is dan weer dat ze de werkelijkheid beter benaderen, waardoor de bruikbaarheid ervan in de praktijk vele malen groter is.

2.2.2

Nood aan heuristieken

Algemeen Heuristieken zijn speculatieve oplossingstrategieën die aangewend worden om (bijna-optimale) oplossingen te berekenen voor bepaalde problemen. Ze worden gebruikt daar waar klassieke methoden geen exacte oplossing kunnen vinden, of simpelweg te traag en dus onbruikbaar zijn om een praktisch nut te hebben. Heuristieken hebben het voordeel dat ze veel sneller een oplossing kunnen bekomen dan een klassieke methode, doch bieden geen inzicht in hoe optimaal deze oplossing is. De oplossing van een heuristiek is dan ook vaak een benaderde oplossing van het probleem. Echter, omdat accuraatheid en precisie geruild worden voor snelheid, kunnen ze een zodanige oplossing bekomen die ‘goed genoeg’ is om het probleem op te lossen.

P versus NP Computationele problemen kunnen gezien worden als de problemen die een gegeven input omzetten naar een zekere output, waarbij de oplossing moet voldoen aan een zeker aantal randvoorwaarden. Enkele van zulke problemen zijn bijvoorbeeld beslissingsproblemen, zoekproblemen en optimalisatieproblemen. Computationele problemen worden ingedeeld in twee grote categorieën, namelijk de makkelijke- en moeilijke problemen (P- en NP-problemen), beiden begrippen uit de complexiteitstheorie.

12


Stel bijvoorbeeld dat een computer een berekening dient uit te voeren waarvan de invoer uit n getallen bestaat (meer bepaald het totaal aantal bits om deze n getallen voor te stellen). Deze berekening kan een optelling of vermenigvuldiging zijn van deze getallen, het genereren van permutaties om ze te rangschikken, of een andere bewerking. De tijd die een computer nodig heeft om deze berekening uit te voeren is afhankelijk van n, en noemen we de looptijd. Deze looptijd kan dan ook voorgesteld worden als een functie van de invoer n, en zal zich ofwel manifesteren in polynomiale tijd (waarbij de complexiteit O(a × nc ) is), of in exponentiële tijd (waarbij de complexiteit O(a × cn ) is). Hierbij zijn a en c positieve constanten. Het verloop van beide functies, polynomiale- versus exponentiële tijd, is voorgesteld in figuur 2.2. 1200

2n2 (exponentieel) n (polynomiaal)

1000

f(n)

800

600

400

200

0 0

2

4

6

8

10

n

Figuur 2.2: Tijdscomplexiteit van polynomiale tijd versus exponentiële tijd. De P-problemen zijn alle problemen die ten minste één polynomiale-tijd-algoritme hebben. Dit betekent dat het algoritme in staat moet zijn om het juiste antwoord voor dit probleem te genereren in ten hoogste O(a × nc ) stappen. De problemen waarvoor geen polynomiale-tijdalgoritme bestaat kunnen niet sneller worden opgelost dan in exponentiële tijd. Dit laatste kan beschouwd worden als alle mogelijke uitkomsten berekenen, en vervolgens controleren of deze uitkomst wel degelijk een oplossing is het van het te beschouwen probleem. Deze problemen kunnen geformuleerd worden als de zogeheten ‘beslissingsproblemen’, problemen waarvoor het antwoord als ‘ja’ of ‘nee’ valt te omschrijven. De klasse van NP-problemen zijn de niet-deterministisch polynomiale problemen. Het is de verzameling van problemen waarbij enkel de juistheid van een ‘ja’ oplossing (eventueel zelfs bekomen in polynomiale tijd) kan worden geverifieerd in polynomiale tijd. Het gaat er hierbij om dat de gegenereerde oplossingen efficiënt te verifiëren zijn, ongeacht de benodigde tijd om


13

tot zo’n oplossing te komen. Deze oplossingen mogen in feite zelfs worden gegokt, waardoor het niet-deterministisch karakter van deze problemen duidelijk wordt. Een bijzondere klasse van NP-problemen heet ‘NP-volledig’. Voor deze problemen geldt dat als je kunt bewijzen dat één zo’n probleem een eenvoudige oplossing heeft, alle andere NP-problemen ook eenvoudig oplosbaar zijn (dus in polynomiale tijd).

Tijdscomplexiteit van het APP Het APP dat wordt beschouwd in deze thesis, waarbij applicaties bestaan uit verschillende services die geplaatst moeten worden op een set van nodes, bevindt zich in de reeks van NPharde problemen [55, 48]. Dit zijn de problemen uit de complexiteitstheorie die ‘minstens zo moeilijk zijn als de moeilijkste problemen in NP’. Een probleem H is NP-hard als en slechts als er een NP-volledig probleem bestaat dat in polynomiale tijd Turing-reduceerbaar is tot H. De klasse van NP-harde problemen hoeven zich niet in NP te bevinden. De oplossingen ervan moeten dus niet verifieerbaar zijn in polynomiale tijd. Het mathematische bewijs dat het APP zoals besproken in deze thesis NP-hard is, is te vinden in het werk van Urgaonkar [55] en Shachnai [48], doch laten we hier buiten beschouwing. Het gevolg hiervan echter is dat het APP geen exacte oplossingen heeft die kunnen bekomen worden in polynomiale tijd. Dat maakt dat het vinden van zulke exacte oplossingen enkel kan worden bekomen in exponentiële tijd, bijvoorbeeld door middel van Integer Linear Programming (ILP) [59] die het ‘Branch and Bound’ algoritme gebruikt [29], of een 2n algoritme die alle mogelijke combinaties van inputwaarden zal uitproberen. Het toepassen van zulke technieken is echter zelfs voor kleine netwerken amper bruikbaar in de praktijk, wegens de grote uitvoertijd en de beperkte schaalbaarheid. Immers, als het aantal aanvragen, applicaties, services of nodes toeneemt, zal de benodigde tijd om een oplossing te berekenen exponentieel toenemen. Dit verklaart dan ook de nood aan heuristieken om benaderende oplossingen te berekenen voor het APP, doch met het gevolg dat men geen inzicht heeft in hoe optimaal deze oplossingen zijn. Echter, vanwege de mogelijkheid om relatief snel benaderende oplossingen te berekenen in polynomiale tijd, zijn heuristieken veel bruikbaarder in de praktijk dan klassieke methoden.

14

2.2.3


Kwaliteitsmaten

Traditioneel Een optimale oplossing voor het APP kan verschillende zaken inhouden. In een traditionele aanpak zal men kijken naar het aantal aanvragen van gebruikers in een bepaalde tijdsperiode, en er hiervan zoveel mogelijk aanvaarden voor uitvoering. Deze aanpak neigt echter naar het aanvaarden van applicaties die lage eisen hebben inzake CPU en geheugen, doordat deze makkelijker uitgevoerd kunnen worden in de cloud. Dit leidt ertoe dat bij batch processing de CPU intensievere aanvragen starvation kunnen ondergaan [9]. Het aantal servers dat deze CPU intensieve applicaties kan uitvoeren is namelijk veel kleiner dan het aantal die de eenvoudigere kunnen uitvoeren, wat de plaatsing bemoeilijkt. Het fenomeen waarbij applicaties nooit (of zelden) aan bod kunnen komen om uitgevoerd te worden wordt starvation genoemd. Starvation kan echter tegengegaan worden door eerst de intensievere aanvragen te behandelen, of door prioriteiten toe te kennen aan deze aanvragen. Dit zorgt ervoor dat hun plaatsing leidt voor een grotere ‘beloning’ in de objectieffunctie die men optimaliseert. Men kan ook proberen om de CPU-capaciteit te maximaliseren die wordt gebruikt bij de plaatsing van applicaties. Bij cloud providers zoals Google App Engine worden gebruikers immers afgerekend op het aantal CPU-cycles dat ze gebruiken. Omwille van deze reden wordt er vaak gekozen om die aanvragen voor applicaties te aanvaarden, die zorgen voor de grootste toekenning van CPU-capaciteit doorheen het netwerk.

Utility functies Een andere manier die gebruikt wordt om de toestand van een systeem te definiëren is door middel van utility functies. Een utility functie zal elke mogelijke toestand van een systeem vertalen naar een bepaalde scalaire waarde, een utility genaamd. Ze worden gebruikt om de voorkeuren van gebruikers, zoals prioriteiten, responstijd, doorvoer of beschikbaarheid, op een wiskundige manier te definiëren. In eerste instantie zal men aan elk van de verscheidene objectieven een bepaalde gewichtsfactor toekennen. Vervolgens zal men de sommatie nemen van alle gewichten, maal hun overeenkomstige objectief, en wordt er tenslotte geprobeerd om deze nieuwe functie te maximaliseren of te minimaliseren. Hierbij worden toestanden met een hoge utility altijd verkozen boven toestanden met een lage utility. Op deze manier herleiden vele optimalisatieproblemen zich tot het vinden van de maximale utility doorheen een systeem [26].


15

Beschouwen we ter illustratie een systeem dat twee diensten kan leveren, en gebruikers als belangen ‘goud’ en ‘zilver’ hechten aan deze diensten. Stel ook dat men de utility functie U (RTG , RTS ) kent die de tevredenheid van gebruikers voorstelt wat betreft de responstijden voor deze twee diensten. Deze responstijden noemen we RTG en RTS , respectievelijk voor goud en zilver. Men kan de waarde van deze responstijden op hun beurt weer voorstellen als het gevolg van het aantal resources (bijvoorbeeld CPU-capaciteit) dat men reserveert voor beide diensten. Aldus schrijft men RTG (CP UG ) en RTS (CP US ). Het optimalisatieprobleem herleidt zich in deze situatie tot het vinden van de waarden CP UG en CP US die U (RTG , RTS ) maximaliseert. In [57] wordt een gedistribueerde architectuur beschreven waarin aangetoond wordt hoe zulke utility functies kunnen zorgen voor een continue verbetering van de manier waarop resources gereserveerd worden. Verschillende deelsystemen kunnen daarbij telkens hun eigen utility functie Uj (nj ) hebben, die afhankelijk is van het aantal toegekende resources nj . Een algoritme staat P vervolgens in om de systeemomhullende utility functie j Uj (nj ) te maximaliseren. In [9] en [60] wordt tevens een utility-gebaseerd systeem beschreven. Hierbij wordt de tevredenheid van elke applicatie met betrekking tot het aantal resources die ervoor gereserveerd wordt, ook voorgesteld met behulp van utility functies. In plaats van echter de systeemomhullende P utility functie j Uj (nj ) te maximaliseren, proberen ze in hun werk de minimale utility Uj onder alle applicaties te maximaliseren. Deze aanpak is eerlijker wat betreft de behandeling van applicaties, systemen of diensten in het algemeen. Dit staat ook gekend als maximale-minimale eerlijkheid (engels: max-min fairness) [9].

2.2.4

APP met netwerk-onbewuste algoritmen

In [24] wordt de middleware beschreven van een gecentraliseerde aanpak voor het APP. Het algoritme die wordt voorgesteld in dit werk probeert zoveel mogelijk aanvragen van gebruikers voor applicaties te aanvaarden. Tevens probeert het algoritme ook om het aantal verplaatsingen van applicatie-instanties ten opzichte van een vorige plaatsing te minimaliseren. Verplaatsingen van applicaties worden immers beschouwd als een kostbare verspilling van tijd en resources. Men moet ze immers op de ene plaats in het netwerk afbreken om op een andere plaats terug op te starten. Dit maakt ook dat ze de hoeveelheid communicatie doen toenemen in het netwerk [50]. Hun aanpak houdt echter enkel rekening met CPU- en geheugencapaciteiten van nodes. Verder wordt er aangenomen dat elke node in het netwerk elke mogelijke applicatie kan uitvoeren.

16


Een variant van dit algoritme wordt voorgesteld in [2], waarin de beperkte schaalbaarheid van een gecentraliseerd algoritme tegen wordt gegaan door een gedecentraliseerd model op te stellen. In dit werk wordt een middleware voorgesteld die gebruik maakt van overlays, en zal een algoritme wederom zoveel mogelijk aanvragen van gebruikers proberen aanvaarden. Ook hier wordt echter enkel rekening gehouden met CPU- en geheugencapaciteiten van nodes. Dit algoritme werd verder verfijnd in [3]. Hierbij kennen alle nodes maar een beperkte hoeveelheid informatie omtrent de toestand van hun buren, in tegenstelling tot een globaal overzicht van alle nodes. In [27] en [53] wordt eveneens geprobeerd om het aantal verplaatsingen van applicatie-instanties ten opzichte van een vorige plaatsing te minimaliseren. Het werk voorgesteld in [27] gaat er vanuit dat applicaties met een gereduceerde capaciteit kunnen worden uitgevoerd op nodes, waarbij er echter geen minimale waarden worden vooropgesteld inzake vereiste CPU- en geheugencapaciteit. Ook ligt de focus in dit werk op het minimaliseren van het aantal verplaatsingen tussen twee allocaties, waarbij er echter gewerkt wordt met een te kleine opstelling om relevante conclusies uit te kunnen trekken. Het werk in [53] introduceert het concept van load shifting, ook wel load balancing genoemd. Het idee hierachter is om de werklast van elke node zoveel mogelijk te balanceren doorheen het netwerk, zodat er zo weinig mogelijk afgeweken wordt van de benuttingsgraad ρ van het volledige systeem. Hierbij wordt de toegewezen hoeveelheid CPU-capaciteit La,n van een applicatie a op node n genomen, en vervolgens gesommeerd over alle applicaties op alle nodes. Dit resultaat wordt vervolgens genormaliseerd ten opzichte van de totale beschikbare hoeveelheid CPU-capaciteit in het systeem, wat niet anders is dan de sommatie over alle nodes van de beschikbare CPU-capaciteit Ωn van een bepaalde node n. P P La,n a∈A P n∈N ρ= n∈N Ωn

(2.1)

Load shifting wordt ook toegepast in [9], waarbij tevens een utility-gebaseerd systeem wordt gebruikt om ervoor te zorgen dat de responstijden van applicaties voldoen aan de eisen vooropgesteld door de eindgebruikers.

2.2.5

APP met netwerk-bewuste algoritmen

In [32] wordt een hiërarchisch model opgesteld dat het APP oplost, rekening houdend met netwerkgerelateerde factoren zoals beperkte bandbreedte en transmissietijd tussen nodes. In dit werk wordt er gebruik gemaakt van utility functies om de efficiëntie en bruikbaarheid van


17

een plaatsing te evalueren. Wanneer zulke netwerkparameters in acht worden genomen bij het APP, maakt dit het mogelijk om end-to-end garanties te leveren met betrekking tot Quality of Service (QoS) eisen van gebruikers [31]. De nadruk in dit werk ligt op het continu proberen verbeteren van de kwaliteit van een plaatsing, door te steunen op resource trading. Hierbij worden onderdelen van een applicatie geruild tussen verscheidene resources, doch enkel indien dit de kwaliteit van de uiteindelijke plaatsing ten goede komt. De verschillende onderdelen van zo’n applicatie worden hierbij zoveel mogelijk geplaatst op dit deel van het netwerk dat gebruik maakt van dezelfde access switch. Indien dit niet mogelijk is zal er gecommuniceerd moeten worden op een hoger niveau in het netwerk, waarbij vervolgens geprobeerd wordt om de kost van deze communicatie zo klein mogelijk te houden. Hierbij wordt telkens rekening gehouden met randvoorwaarden opgelegd door de gebruikte connecties, zijnde beperkte bandbreedte en transmissietijd. Dit werk is echter louter een theoretisch model, waarbij er geen concrete resultaten worden voorgesteld op basis van simulaties. In [20] wordt een algoritme voorgesteld dat het APP oplost, waarbij tevens bandbreedte en tijdsvertraging in acht worden genomen bij de plaatsing van applicaties en services in een overlay netwerk. In dit werk wordt er vooral gefocust op implementaties van gecentraliseerde gretige algoritmen [15]. Dit zijn algoritmen die gedurende elke iteratie streven naar een lokaal optimum, met de hoop om uiteindelijk een globaal optimum te bereiken. Dit werk legt zich toe op overlay netwerken, waardoor de aanwezigheid van een cloud omgeving buiten beschouwing wordt gelaten. Ook wordt er geen rekening gehouden met de communicatiekost in het netwerk, alsmede met de impact van het gebruik van de verscheidene servers. In [17] wordt een dynamisch en latency-aware algoritme voorgesteld, die zich bij het plaatsen van services in overlay netwerken baseert op utility functies. Het algoritme kan rekening houden met een dynamische situatie, waarbij de aanvragen variëren in de tijd, en die rekening houdt met tijdsvertragingen tussen nodes. Hierbij wordt er echter slechts een vergelijking gemaakt ten opzichte van triviale network-unaware algoritmen, waardoor er geen uitspraak mogelijk is omtrent de performantie van dit algoritme ten opzichte van andere in zijn soort. Er wordt ook aangetoond dat dit algoritme slechts goed presteert ten opzichte van triviale algoritmen in niet overbelaste scenario’s. Dit zijn scenario’s waarbij er dus meer dan genoeg CPU-capaciteit in het systeem beschikbaar is om aan alle aanvragen van gebruikers te kunnen voldoen. Voor de meeste conclusies in dit werk wordt er uitgegaan van een te onderbelast scenario om echt passende besluiten te kunnen trekken.

18


In [44] wordt een Particle Swarm Optimization (PSO) [25] algoritme voorgesteld die een oplossing kan berekenen voor het APP. Applicaties bestaan in dit werk uit workflows, en deze worden geplaatst op resources rekening houdend met de kosten inzake communicatie en het uitvoeren van zo’n workflow. In dit werk wordt er gefocust op het minimaliseren van de totale uitvoeringskost van workflows in een cloud-omgeving, waarbij het beschreven algoritme vergeleken wordt met een Best Resource Selection (BRS) aanpak, steunend op het gebruik van Genetisch Algoritmen (GA) [63]. Bij zo’n BRS aanpak worden resources geselecteerd op basis van hun performantie, waarbij taken in een workflow worden geplaatst op resources die de uitvoeringstijd minimaliseren. In [47] wordt aangetoond dat zo’n PSO algoritme sneller is dan een GA, en [64] toont aan dat PSO een betere plaatsing bekomt dan GA. Tevens toont [54] aan dat PSO in staat is om meer dan de helft van de best gekende oplossingen van andere algoritmen te verbeteren. In [42] wordt een algoritme voorgesteld dat een oplossing berekent voor het APP. Het algoritme in dit werk houdt rekening met verschillende netwerkparameters, waarbij hun aandacht specifiek gericht is naar een hybride cloud-omgeving toe. In zo’n hybride cloud ligt de bottleneck van de probleemstelling in het private netwerkgedeelte, alsook in de communicatielink die de connectie verzorgt naar de publieke cloud. De topologie van deze publieke cloud dient op deze manier dus niet gekend te zijn in de probleemstelling. De auteurs gaan er tevens vanuit dat de applicaties die uitgevoerd worden in deze hybride cloud bestaan uit een workflow van communicerende services. Het verschil ten opzichte van een traditionele APP aanpak ligt hierbij dat er wordt verondersteld dat de services al geplaatst zijn in de cloud, en er enkel nog een geschikte workflow gevonden moet worden. In zo’n workflow worden de services zodanig gecombineerd met elkaar dat ze samen een bepaalde functionaliteit verwezenlijken. Er wordt vervolgens bepaald hoeveel capaciteit er voor elke gevraagde workflow kan voorzien worden, waarbij gebruik gemaakt wordt van het Maximum Concurrent Flow Problem beschreven in [49]. Dit werk toont ook aan dat een degelijke plaatsing kan berekend worden in minder dan 100 seconden, wat het algoritme geschikt maakt om uitgevoerd te worden in een cloud-omgeving. In dit werk wordt ook aangetoond dat het abstraheren van het onderliggende netwerk de uitvoeringstijd met 30% kan verlagen, en dit zonder de kwaliteit van de plaatsing noemenswaardig te be¨ınvloeden.

2.3. VARIABILITY MODELING

2.3 2.3.1

19

Variability Modeling Algemeen

Variabiliteit speelt een belangrijke rol bij het ontwikkelen en beheren van applicaties. De mate van variabiliteit bepaalt immers op zijn beurt ook de complexiteit van deze applicaties. Gebruikers kiezen namelijk niet altijd voor eenzelfde functionaliteit bij een applicatie, of hebben verschillende eisen inzake performantie. Sommige gebruikers zijn bijvoorbeeld bereid om in te boeten aan functionaliteit door te kiezen voor een gratis versie van een applicatie, anderen verkiezen dan weer een hoge performantie en zijn daartoe bereid een prijs te betalen. Ongeacht de functionaliteit willen gebruikers vaak ook hun applicaties personaliseren, bijvoorbeeld door de grafische gebruikersomgeving ervan aan te passen. Vaak wordt er gewerkt met een soort geplande variabiliteit, wat gebruikers ervan weerhoudt om volledige vrijheid te hebben inzake hun applicaties. Ongelimiteerde flexibiliteit is namelijk vrij complex en ligt niet voor de hand. Een applicatie moet dan immers zodanig geprogrammeerd worden om aan de volledige set van eisen te kunnen voldoen van elke mogelijke gebruiker. Vaak wordt er dan ook een compromis gemaakt door het aanbieden van ‘genoeg’ variabiliteit, waarbij een gebruiker de applicatie in beperkte mate kan personaliseren [37].

2.3.2

Service-Oriented Architecture (SOA) binnen Variability Modeling

Een Service-Oriented Architecture (SOA) [28] is een architectuurmodel die toelaat om software op te bouwen uit bestaande bouwblokken. Een SOA is dus een ontwerpstijl die zeer geschikt is voor het ontwerpen en realiseren van nieuwe applicaties, aangezien het mogelijk wordt om deze applicaties te creëren op basis van bestaande services. Deze service bouwblokken implementeren eenvoudige functionaliteiten die makkelijk kunnen toegevoegd worden bij het ontwerp van complexe applicaties. Het grote voordeel ten opzichte van monolithische applicaties is dat er veel functionaliteiten kunnen worden hergebruikt tussen verschillende ontwerpen. Met behulp van een SOA kunnen bedrijven zich ook focussen op het implementeren van die bouwblokken waarin zij gespecialiseerd zijn, en andere service functionaliteiten simpelweg aankopen of uitbesteden aan derden. Het is binnen deze architectuur ook mogelijk om applicaties op een goedkope en flexibele manier aan te passen. Individuele onderdelen van een applicatie kunnen immers door gebruikers geruild worden voor hun eigen implementatie ervan, of simpelweg worden weggelaten [37].

20


Applicaties die ontwerpen zijn op basis van deze architectuur kunnen opgesplitst worden in drie grote groepen [11, 35, 36]: • Enkele instantie: Alle gebruikers van een bepaalde applicatie gebruiken eenzelfde instantie hiervan. Hierdoor is de applicatie dus niet aanpasbaar door gebruikers ervan. • Enkele configureerbare instantie: Alle gebruikers van een bepaalde applicatie gebruiken eenzelfde instantie hiervan, doch deze instantie is configureerbaar op gebruikersbasis. De instantie wordt dan gedurende runtime aangepast op basis van configuratie files, of aan de hand van bepaalde instellingen. Dit maakt het mogelijk om variabiliteit toe te voegen aan applicaties op een relatief eenvoudige manier. • Meerdere instanties: Elke gebruiker zal een andere instantie van de applicatie gebruiken. Dit zorgt voor de meeste flexibiliteit wanneer er gebruikers zijn die verschillende eisen hebben, doch vergt ook afzonderlijke codering om aan al deze eisen te voldoen.

2.3.3

Software Product Line Engineering (SPLE)

Voor het bouwen van configureerbare applicaties worden vaak concepten uit Software Product Line Engineering (SPLE) [45] toegepast. Bij deze aanpak wordt de software gemodelleerd als een collectie van verscheidene features. Features zijn bouwblokken van services die beschikken over logische relaties met betrekking tot elkaar. Elke feature zorgt voor een bepaalde functionaliteit, waarbij er logische relaties kunnen ontstaan zoals verplicht, optioneel, alternatief, of. De relaties die bouwblokken kunnen hebben met betrekking tot elkaar worden voorgesteld in figuur 2.3.

verplicht optioneel alternatief of

Figuur 2.3: Voorstelling van een mogelijk feature model.

verplicht optioneel

verplicht optioneel

2.3. VARIABILITY MODELING alternatief of

21

alternatief of

Elke service voert op zijn beurt een individueel onderdeel van de applicatie uit. Door het selecteren en deselecteren van de gepaste features kunnen verschillende varianten van de software bekomenverplicht worden. optioneelDit wordt voorgesteld in figuur 2.4. alternatief of

(a) Applicatie 1

(b) Applicatie 2

(c) Applicatie 3

Figuur 2.4: Feature matrices: voorstelling van mogelijke applicaties. Met behulp van SPLE kan een grote hoeveelheid aan gepersonaliseerde applicaties op een eenvoudige manier gemaakt worden, die elk uitgevoerd kunnen worden in een cloud omgeving. Het nadeel van deze manier van werken is dat er een unieke applicatie moet worden gemaakt voor elke feature combinatie. Dit maakt het vrijwel onmogelijk om in een cloud omgeving aan multitenancy te doen [41]. Bij multitenancy zal één enkele instantie van een applicatie die uitgevoerd wordt op een server, verscheidene eindgebruikers (Engels: tenants) kunnen bedienen. Dit zorgt ervoor dat de schaalbaarheid van applicaties toeneemt, en maakt dat de kost van zo’n applicatie per gebruiker sterk afneemt. SPLE laat echter wel toe om elke feature te gebruiken in meerdere applicaties. Een applicatie wordt dan gerealiseerd door een workflow op te stellen tussen de verscheidene features waaruit deze bestaat. Men bekomt aldus een variant van het APP, het die in [41] wordt omschreven als het Feature Placement Problem (FPP). Om deze reden zijn verschillende hedendaagse plaatsingsalgoritmen in cloud omgevingen, die geen rekening houden met relaties tussen services, niet geschikt om dit soort problemen aan te pakken. In [34] wordt beschreven hoe een workflow kan opgesteld worden aan de hand van informatie van gebruikers inzake hun gewenste variabiliteit. Deze werkwijze laat toe om dankzij een geschikt feature model automatisch scripts te genereren die applicaties kunnen opstarten in een gepersonaliseerde configuratie. Na deze stap is alle gebruikersvariabiliteit echter gebonden in de applicatie, en kan deze nog moeilijk aangepast worden op een later moment.

22

2.3.4


Complexiteit bij APP

De mate van variabiliteit die wordt aangeboden binnen een applicatie zal grotendeels de complexiteit ervan bepalen. Immers, indien er geen variabiliteit wordt toegestaan zal eenzelfde instantie van deze applicatie volstaan om verschillende gebruikers te bedienen. Deze instantie kan op één enkele server uitgevoerd worden, waardoor deze server een groot aantal gebruikers kan bedienen. Echter, hoe groter het aanbod aan services dat kan gebruikt worden om een applicatie uit op te bouwen, hoe meer service-instanties er moeten aanwezig zijn binnen het netwerk van een provider. Dit kan ervoor zorgen dat bepaalde nodes niet over alle services beschikken om de functionaliteit van één applicatie te verwezenlijken, waardoor de instanties van deze services moeten verspreid worden op nodes doorheen het netwerk. Onder deze omstandigheden ontstaat er automatisch een situatie waarbij verschillende nodes met elkaar moeten communiceren. Dit heeft uiteraard zijn impact op de netwerkinfrastructuur van een cloud provider. In zo’n situatie moet er immers rekening worden gehouden met de eindige bandbreedte van communicatielinks tussen nodes. Tevens dient er door het netwerk bijgehouden te worden waar de verschillende service-instanties worden uitgevoerd die deel uitmaken van eenzelfde applicatie. Het aanbieden van variabiliteit binnen een applicatie heeft dus zijn impact op het reserveren van de resources waarop deze applicatie uitgevoerd wordt. Men kan bijvoorbeeld opteren om applicaties te plaatsen op enkel die resources die beschikken over alle service-instanties van een bepaalde applicatie [55, 6]. Indien een bepaalde node echter niet beschikt over één van de services waaruit deze applicatie is opgebouwd, is deze node automatisch niet meer geschikt om de betreffende applicatie in zijn geheel uit te voeren. Een andere aanpak is om een workflow op te stellen die de gevraagde services van een applicatie verbindt met elkaar, waarbij een connectie opgezet wordt tussen de verschillende nodes waarop de services worden uitgevoerd [60, 30]. De manier waarop de services met elkaar communiceren zal dus ook een invloed hebben op de grootte van de workflow die opgesteld dient te worden. Men ziet gemakkelijk in dat de complexiteit van het algoritme dat een oplossing berekent voor het APP toeneemt met de mate van variabiliteit die wordt aangeboden aan gebruikers. Hierdoor zal het algoritme dat gebruikt wordt om een plaatsing te berekenen dus ook langer moeten zoeken naar een geschikte oplossing. De aanpak in deze thesis gaat er vanuit dat er geen logische relaties bestaan tussen de verschillende services van eenzelfde applicatie. Wanneer dit wel het geval is spreken we van features, en herleidt het probleem zich tot het eerder vermelde FPP [41].

2.4. RESOURCE BEHEER IN DE CLOUD

2.4

23

Resource beheer in de cloud

Wegens de hoeveelheid resources (servers, databases) die een cloud provider ter beschikking heeft in zijn netwerk, is het beheren van deze resources een complex gegeven. Zulke resources hebben vaak verschillende CPU- en geheugencapaciteiten, en kunnen niet allemaal dezelfde service-instanties uitvoeren [42]. Vaak liggen ze ook geografisch verspreid, en zijn ze met elkaar verbonden via communicatielinks met een eindige bandbreedte en een zekere tijdsvertraging [7]. Resource beheer in de cloud komt erop neer dat er een managementsysteem bestaat die automatisch de aanvragen van gebruikers zal behandelen, en hiervoor een zeker aantal resources vrijmaakt [4]. Deze resources dienen op een eerlijke manier verdeeld te worden onder alle gebruikers, en het volledige systeem moet robuust en bestendig zijn tegen fouten in het netwerk. Tevens moet het systeem zich op een efficiënte manier kunnen aanpassen aan variërende omstandigheden [60] zoals de belasting in het netwerk, het aantal gebruikers die aanvragen indient, of het aantal nodes waarop deze worden uitgevoerd. In wat volgt wordt er kort opgesomd hoe het beheer van deze resources verloopt, en hoe dit op een efficiënte manier kan gebeuren.

2.4.1

Architectuur

Er bestaan drie grote architecturen die een provider toelaten om zijn resources gestructureerd te beheren. Deze vormen van resource-management zijn gecentraliseerd, hiërarchisch en gedistribueerd. In figuur 2.5 kan men een grafische voorstelling terugvinden van deze modellen.

(a) Gecentraliseerd

(b) Hiërarchisch

(c) Gedistribueerd

Figuur 2.5: Management architecturen. Ze worden gebruikt bij het vertalen van de aanvragen van gebruikers naar wat er fysisch dient te gebeuren in het netwerk van een provider. Hieronder volgt een kort overzicht van deze modellen:

24


Gecentraliseerd Een gecentraliseerd beheer van resources is een gegeven dat vrij goed gekend is in de informatica. Denken we bijvoorbeeld aan het master-slave systeem, waarbij een centrale node (de master) een directe impact heeft op de werking van de individuele componenten die hij beheert (de slaven). Al deze slaven zijn enkel afhankelijk van de centrale node wat betreft informatie over hun huidige en toekomstige werking. Ze wisselen echter onderling geen enkele vorm van informatie uit, en luisteren enkel maar naar wat de master hen opdraagt. Enkele gecentraliseerde algoritmen bij resource management werden al eerder voorgesteld in [27], [24], [53] en [9]. Deze algoritmen zijn gebaseerd op informatie omtrent alle nodes die ze beheren, wat ertoe leidt dat ze een vrij goede performantie vertonen in kleinere datacenters, doch zeer slecht schalen naar grotere datacenters of clouds toe. De hoeveelheid informatie die naar de master gestuurd moet worden zodat deze een plaatsing kan berekenen, wordt simpelweg te groot indien het aantal resources in het netwerk toeneemt.

Hi¨ erarchisch Het concept van een hiërarchisch beheer vloeit voort uit dat van een gecentraliseerd beheer. In een hiërarchisch systeem is de macht gedecentraliseerd op een hiërarchische manier, zodat er een aantal intermediaire machtshebbers zijn tussen de allesoverheersende master en de slaven onderaan de structuur. De intermediaire machtshebbers controleren direct de slaven onder hen, doch zijn ook zelf de slaaf van de master boven hen. Op deze manier heeft de uiteindelijke master een controle over het volledige systeem, doch zonder zelf veel te moeten weten over de verschillende deelaspecten ervan. Dit systeem staat ook gekend als gedecentraliseerd of gelaagd. Hiërarchische modellen werden eerder al theoretisch omschreven in [18], en praktisch toegepast in [40] en [32]. Hierin werd aangetoond dat een hiërarchisch georganiseerd systeem zeer goed informatie kan uitwisselen tussen de verschillende nodes in een netwerk, en dit tegen een relatief lage kost inzake communicatie. Tegelijkertijd zijn ze perfect schaalbaar wanneer het aantal aanvragen, applicaties of resources in het netwerk wijzigt. De verscheidene servers in een netwerk worden daartoe hiërarchisch in een boomstructuur opgedeeld in management- en executie-servers, die respectievelijk instaan voor het beheren en het uitvoeren van applicaties.


25

Gedistribueerd Een gedistribueerd systeem heeft, in tegenstelling tot een gecentraliseerd en een hiërarchisch systeem, geen absolute heerser. Dit maakt dat gedistribueerde systemen vrij autonoom kunnen werken, in die zin dat hun werking onafhankelijk is van de bevelen van een master. De verschillende nodes in dit systeem behoren tot een groot netwerk waarin gelijkheid en onafhankelijkheid centraal staan. Binnen een gedistribueerd systeem zullen verschillende buren met elkaar communiceren en samenwerken om een bepaalde opdracht uit te voeren. Het grote voordeel van dit systeem is dat het bijzonder robuust is, aangezien er in dit netwerk geen (kwetsbare) masters zijn die de verschillende nodes controleren. Een voorbeeld van zo’n gedistribueerd systeem kan men terugvinden in [60], [2] en [3]. Hierin wordt telkens een algoritme voorgesteld waarbij elke node een database bijhoudt met daarin management informatie over de toestand van zichzelf en enkele buren. Vervolgens wordt deze informatie selectief doorgegeven naar een aantal buren van deze node. Dit leidt ertoe dat elke node beschikt over genoeg informatie om individueel te kunnen functioneren, zorgt ervoor dat geen enkele node een globaal beeld heeft omtrent de toestand van het netwerk.

2.4.2

Schaalbaarheid

Bij het beheren van resources in de cloud is het zeer belangrijk dat het algoritme dat hiervoor instaat zeer schaalbaar is, dit met het oog op het steeds toenemend aantal resources dat er zich in de cloud bevinden [38]. Bij vele algoritmen die hiervoor instaan is de schaalbaarheid immers een probleem, met name dat de uitvoertijd van het algoritme sterk toeneemt wanneer het aantal te beheren resources verhoogt. Bij het gebruik van een ILP is het zelfs zo dat er tevens een grote spreiding is wat betreft de uitvoertijd en performantie van het algoritme, waarbij het bekomen van een oplossing voor het APP soms uren kan duren [41, 62]. Omdat de toestand van resources in de cloud en de eisen van gebruikers voortdurend kunnen veranderen, is het zeer gewenst om een algoritme te hebben dat snel en dynamisch een oplossing voor het APP kan bekomen. Wanneer dit te lang duurt is de huidige toestand omtrent de bezetting van alle resources immers niet meer relevant. Echter, dit is een gegeven waarop sommige algoritmen zich baseren bij een nieuwe toekenning van resources. Men wil bijvoorbeeld het aantal verplaatsingen van service-instanties tussen twee iteraties beperkt houden, omdat deze worden beschouwd als een kostbare verspilling van tijd en resources [50].

26


Omwille van deze redenen vormt een gecentraliseerde aanpak bij het beheer van resources een probleem, omdat er teveel nodes zijn waar de master rekening mee dient te houden. Dit maakt het moeilijk voor een algoritme om tot een globaal optimum te komen. Verder moet er ook informatie over alle individuele nodes naar deze master gestuurd worden, wat zorgt voor een overvloed aan informatie bij deze node. De hoeveelheid informatie die doorgestuurd wordt kan echter gereduceerd worden, doch vaak gaat dit ten koste van de accuraatheid van de uiteindelijke toekenning van resources doorheen het netwerk. Ook is de master in het systeem op zich vrij kwetsbaar, wat een bijkomend nadeel is van deze aanpak. Als deze node immers faalt kunnen er geen resources meer gereserveerd worden, en zou er moeten gegrepen worden naar protocollen die een nieuwe master zoeken onder alle nog functionerende resources [12]. Een hiërarchische aanpak is in vele opzichten meer schaalbaar. Wanneer er ouder/kind relaties worden toegepast in het netwerk, kunnen de resources zodanig gekozen worden dat er een logische boomstructuur ontstaat. De onderste laag in deze boom zal effectief instaan voor het beheer van de resources, terwijl de bovenste laag als het ware het volledige netwerk beheert. Deze manier van werken zorgt ervoor dat er veel minder informatie dient uitgewisseld te worden tussen de verschillende nodes. Wanneer twee nodes met elkaar wensen te communiceren dient er enkel informatie naar de ouder of het kind gestuurd te worden, wat zorgt voor minder overhead in het netwerk. Op elke laag van deze logische boom kan men de informatie van de kinderen nog eens groeperen en filteren, alvorens deze verder door te sturen naar de laag erboven. Dit zorgt ook voor een reductie van de overhead in het netwerk [18]. Een hiërarchische structuur zorgt ervoor dat de nodes hogerop een veel breder maar minder gedetailleerd beeld hebben van het netwerk, wat beslissingen op dit niveau veel meer schaalbaar maakt. De lagere niveaus beschikken dan weer over gedetailleerdere informatie die hen toelaat om snel en efficiënt te reageren, doch met het nadeel dat hun impact beperkt blijft tot een klein gebied.

2.4.3

Dynamische plaatsing

Het reserveren van de geschikte resources om applicatie- of service-instanties op uit te voeren is een dynamisch proces. Aanvragen van gebruikers variëren immers in de tijd, en aldus zal ook het beheren en toekennen van instanties aan deze resources op een dynamische manier moeten gebeuren. Dit houdt in dat er bij nieuwe aanvragen van gebruikers, of bij het beëindigen van bepaalde taken in de cloud, rekening gehouden moet worden met de huidige toestand en bezetting van alle resources.


27

Wanneer bij nieuwe aanvragen van gebruikers de werklast in de cloud bijvoorbeeld laag is, kan het gebeuren dat de huidige bezetting van servers volstaat om aan deze aanvragen te voldoen. Het omgekeerde kan natuurlijk ook, namelijk wanneer de huidige werklast zodanig hoog is dat er extra resources moeten gereserveerd worden in de cloud. In figuur 2.6 wordt getoond hoe de toekenning van service-instanties op nodes kan variëren in de tijd. s1

s2

s3

s4

s5

s1

s2

s3

s4

s5

s1

n1

n1

n1

n2

n2

n2

n3

n3

n3

n4

n4

n4

n5

n5

n5

t = t0

t = t1

s2

s3

s4

s5

t = t2

t

Figuur 2.6: Dynamische plaatsing van services op nodes doorheen de tijd. In beide gevallen zal er dus eerst gekeken worden naar de huidige werklast in de cloud vooraleer er een beslissing wordt genomen over hoe de cloud zich moet aanpassen aan de nieuwe aanvragen. Wanneer de werklast in de cloud laag is kan het bijgevolg gebeuren dat er applicatie- of serviceinstanties worden verschoven naar een kleinere poel van resources. Hierbij wordt het teveel dat er aan resources was gewoon afgebroken, of in een verlaagde energietoestand (idle mode) geplaatst [19]. Als dit gebeurt houdt dit in dat er processen die nog actief runnen moeten worden afgebroken en verplaatst. In zo’n situatie dient er afgewogen te worden hoe deze extra kost inzake communicatie en verhoogde runtime zich verhoudt ten opzichte van het uitschakelen of in idle mode plaatsen van resources. Ook wanneer er extra resources dienen gereserveerd te worden kan het zijn dat er een betere plaatsing kan bekomen worden als men huidige processen afbreekt en verplaatst. Men zou simpelweg de extra resources die nodig zijn om aan een nieuwe aanvraag te voldoen kunnen toekennen aan de gebruiker van deze nieuwe aanvraag, doch deze manier van werken is vrij inefficiënt [9].

Hoofdstuk 3

Probleemstelling 3.1

Inleiding

In dit hoofdstuk zal een formele beschrijving gegeven worden van het Application Placement Problem (APP). Dit probleem kan als volgt omschreven worden: gegeven een bepaalde set van applicaties en nodes, zoek uit welke applicaties op welke nodes moeten uitgevoerd worden om zoveel mogelijk aan de vraag van eindgebruikers te kunnen voldoen. In vele werken worden deze applicaties beschouwd als gehele monolithische entiteiten, waardoor het uitvoeren van zo’n applicatie gebeurt op één enkele node. In dit werk wordt er echter uitgegaan van de veronderstelling dat de applicaties die aangevraagd worden bestaan uit een combinatie van communicerende services. Dit architectuurmodel wordt vaak toegepast binnen een Service Oriented Architecture (SOA, zie ook sectie 2.3.2). Uitgaande van deze veronderstelling mag de impact van het onderliggende netwerk niet geabstraheerd worden bij het bepalen van een plaatsing van de applicaties. Het is immers mogelijk dat de verscheidene services waaruit zo’n applicatie opgebouwd is fysisch worden uitgevoerd op verschillende nodes in het netwerk. In figuur 3.1 wordt een grafische voorstelling weergegeven van het APP. Per applicatie wordt een buffer bijgehouden van het aantal aanvragen (Engels: requests r) voor deze applicatie. Vervolgens wordt per aanvraag r een plaatsing berekend, waarbij wordt bepaald op welke node n de verschillende services s behorende tot deze applicatie moeten geplaatst worden. Wanneer men de som neemt over alle aanvragen, kan men een plaatsingsmatrix per applicatie opstellen. Indien men dan weer sommeert over alle applicaties verkrijgt men de uiteindelijke plaatsingsmatrix, die bepaalt hoeveel instanties er van elke service s moeten geplaatst worden op elke node n.

29

30

HOOFDSTUK 3. PROBLEEMSTELLING

Requestbuffer:

r = r1

r1 r2 r3 r4

s1 s2 s3 s4 s5 n1

Applicatie1

r = r2 1

n2

1

n3 n5 r1 r2 r3 r4

1

s1 s2 s3 s4 s5 n2 n3

1

n3

1

n5 r1 r2 r3 r4

n4 n5

s1 s2 s3 s4 s5 n1 n2 n3 n4 n5

1 1 1

1 1 1

n3 n4 n5

1

n3

1

n4

1 1

n5

2

n2

1

n3

2 2

n5

1 1 1

s1 s2 s3 s4 s5 n1

n4 n5

n2

1

n3

1

n3

1

n4

1 1

n5

s1 n1

Uiteindelijke plaatsing van het aantal services op elke node:

1

s1 s2 s3 s4 s5

n1 n2

1 1 1

n4

1

1 1

1

s1 s2 s3 s4 s5

1 1

2

2 2 1

n1

s1 s2 s3 s4 s5 n2

1

n4 n5

n1

1

n3

1

n2

1

s1 s2 s3 s4 s5 n2

1

s1 s2 s3 s4 s5 n1

n2

1

n1

1

n4

Applicatie3

n5

1

s1 s2 s3 s4 s5 n1

n2 n4

n1

Applicatie2

s1 s2 s3 s4 s5 n1 n3

n4

Plaatsing per applicatie:

r = r3

n2 n3 n4 n5

1 1 2

1 2 1 1 2 1 1 2

s2

s3

s4

s5

1 2 2 3 3 4 1 1 1 1 4 3 4 2 1 1 1

Figuur 3.1: Een grafische voorstelling van het Application Placement Problem. Er dienen verschillende randvoorwaarden in acht te worden genomen wanneer een plaatsing van service-instanties in het netwerk wordt berekend. Deze randvoorwaarden worden onder andere ge¨ıntroduceerd door de gebruikte apparatuur waarop deze services worden uitgevoerd, die een beperkte CPU- en geheugencapaciteit hebben. Tevens is het vaak niet mogelijk om elke instantie overal uit te voeren, daar er soms specifieke hard- of software nodig is voor het uitvoeren van een instantie, of wegens veiligheidsredenen. Daarnaast is er ook nog het onderliggende netwerk van een cloud provider, dat instaat voor de communicatie tussen alle services. De verschillende input variabelen met betrekking tot dit probleem worden hieronder beschreven, alsmede alle optimalisatiecriteria en randvoorwaarden waaraan het APP onderhevig is. Een overzicht van de gebruikte symbolen kan gevonden worden in tabellen 3.1 en 3.2.

3.1. INLEIDING

31

Input variabelen Symbool

Beschrijving

N

De set met alle nodes, waarop services kunnen uitgevoerd worden

E

De set met alle communicatielinks, die de nodes verbinden met elkaar

A

De set met alle applicaties, die bestaan uit communicerende services

Ra

De set met alle aanvragen voor applicatie a

S

De set met alle services, waaruit de applicaties opgebouwd zijn

Da

Het totaal aantal aanvragen voor applicatie a

Ωn

De CPU-capaciteit van node n (in GHz)

Γn

De geheugencapaciteit van node n (in GB)

ωs

De CPU-vereiste van service s (in GHz)

γs

De geheugenvereiste van service s (in GB)

I

De instantiematrix, die aangeeft welke services deel uitmaken van welke applicatie. Ia,s = 1 betekent dat een instantie van service s nodig is om applicatie a uit te kunnen voeren, Ia,s = 0 betekent dat dit niet nodig is

R

De relatiematrix, die aangeeft welke services uitgevoerd kunnen worden op welke node. Rs,n = 1 betekent dat service s uitgevoerd kan worden op node n, Rs,n = 0 betekent dat dit niet mogelijk is

C

De communicatiematrix, waarbij Cs1 ,s2 aangeeft hoeveel bandbreedte (in Mbit/s) er nodig is om de communicatie tussen de services s1 en s2 te kunnen realiseren

B

De bandbreedtematrix, waarbij Bn1 ,n2 aangeeft hoeveel bandbreedte (in Mbit/s) er beschikbaar is op elke communicatielink (dus tussen elk paar nodes n1 en n2 )

H

De hopcountmatrix, waarbij Hn1 ,n2 aangeeft hoeveel tussenliggende apparatuur (routers, nodes) er minstens aanwezig is tussen elk paar nodes n1 en n2 Tabel 3.1: Gebruikte input variabelen bij het APP

32


Beslissingsvariabelen, manipuleerbaar tijdens het APP Symbool G

Beschrijving De accepteringsmatrix, waarbij Ga,r = 1 aangeeft dat de r-de aanvraag voor applicatie a geaccepteerd kon worden, en Ga,r = 0 indien dit niet mogelijk was

P

a,r De plaatsingsarray, waarbij Ps,n = 1 aangeeft dat een instantie van service s wordt a,r uitgevoerd op node n en behoort tot de r-de aanvraag van applicatie a, en Ps,n =0

aangeeft dat dit niet zo is U

De uitvoeringsmatrix, waarbij Us,n = 1 aangeeft dat een instantie van service s wordt uitgevoerd op node n, en Us,n = 0 indien dit niet zo is

~n U

~ n = 1 aangeeft dat node n actief wordt gebruikt, De uitvoeringsvector, waarbij U ~ n = 0 indien dit niet zo is dus voor het uitvoeren van minstens één service, en U

F

De flowarray, waarbij Fsa,r 1 ,s2 (n1 , n2 ) aangeeft hoeveel bandbreedte (in Mbit/s) de communicatie tussen de services s1 en s2 gebruikt, behorend tot de r-de aanvraag van applicatie a, indien deze respectievelijk worden uitgevoerd op nodes n1 en n2

zw

Percentage communicatie-voldoening die elke workflow w krijgt toegekend van zijn totale eis inzake communicatie Tabel 3.2: Gebruikte beslissingsvariabelen, manipuleerbaar tijdens het APP

3.2

Netwerk-bewuste plaatsing van service workflows

In wat volgt worden de verschillende optimalisatiecriteria en randvoorwaarden besproken voor een netwerk-bewuste plaatsing van de applicaties die aangevraagd worden door eindgebruikers. Deze criteria zijn achtereenvolgens: 1. Maximaliseren van het aantal geaccepteerde aanvragen, waarbij de benodigde CPU-capaciteit van elk applicatie als gewichtsfactor wordt toegevoegd bij dit optimalisatiecriterium. 2. Maximaliseren van de communicatie-voldoening van elke workflow, waarbij zoveel mogelijk aan de communicatie-eis van elke workflow wordt voldaan. 3. Minimaliseren van het aantal gebruikte nodes bij de plaatsing. 4. Minimaliseren van het aantal verplaatsingen van service-instanties tussen twee iteraties. 5. Maximaliseren van de service workflow efficiëntie, waarbij de hop count tussen nodes als kostmetriek wordt genomen om communicerende services zo dicht mogelijk bij elkaar te plaatsen.

3.2. NETWERK-BEWUSTE PLAATSING VAN SERVICE WORKFLOWS

33

Belangrijk om te weten is dat elk optimalisatiecriterium apart wordt geoptimaliseerd in bovenstaande volgorde. Elk optimalisatiecriterium zal dan ook als randvoorwaarde optreden in een volgend optimalisatiecriterium, en zich daar manifesteren als onder- of bovengrens tijdens deze optimalisatie. Indien bijvoorbeeld het aantal geaccepteerde aanvragen wordt gemaximaliseerd in de eerste stap om een plaatsing te berekenen, mag dit aantal nooit kleiner worden tijdens een volgende stap. Elke maximalisatie is dus een ondergrens in de volgende stap, en elke minimalisatie een bovengrens in de volgende stap. Op deze manier zal elke volgende stap in het totale optimalisatieprobleem zorgen voor extra randvoorwaarden, waardoor de totale ruimte van oplossingen vaak drastisch verkleind wordt. Dit zorgt er echter niet altijd voor dat ook de benodigde tijd kleiner wordt voor elk criterium te optimaliseren, aangezien de complexiteit van elk criterium het aantal benodigde berekeningen en randvoorwaarden sterk zal be¨ınvloeden. De methode om alle criteria apart te optimaliseren is verschillend van een aanpak waarbij alle criteria samen worden geoptimaliseerd. Deze laatste aanpak is vaak sneller aangezien er maar één optimalisatie moet uitgevoerd worden, aangezien alle criteria zich samen voordoen als één supercriterium. Zo’n aanpak kan echter resulteren in optimalisatiecriteria die sterk uiteenlopend vervuld zijn. Het kan bijvoorbeeld gebeuren dat het aantal gebruikte nodes bij een plaatsing zeer hoog is, maar het aantal verplaatsingen tussen twee iteraties zeer laag. Een mogelijke oplossing hiervoor is om te werken met prioriteiten voor de verschillende optimalisatiecriteria, waarbij deze vermenigvuldigd worden met een bepaalde factor naargelang hun belangrijkheid. Hiervoor dient men echter te werken met een gemeenschappelijke basis, waarbij het resultaat van elk optimalisatiecriterium genormeerd kan worden tussen 0 en 1. Vaak is het echter zeer moeilijk om zo’n gemeenschappelijke basis te vinden voor alle criteria, dit vanwege het ontbreken van een gepaste schaal om ze te normaliseren. Bij het evalueren van het aantal geaccepteerde aanvragen kan er bijvoorbeeld gekeken worden naar het totaal aantal aanvragen, waarna dit criterium eenvoudig kan genormaliseerd worden tussen 0 en 1. Echter, bij het evalueren van het gebruikte nodes bij deze plaatsing is zo’n normalisatie veel moeilijker. Er bestaan in dit geval echter wel twee uiterste grenzen, namelijk geen en alle servers gebruiken in het netwerk. Beiden zijn echter situaties die afhankelijk zijn het aantal binnengekomen aanvragen, waardoor zo’n normalisatie zinloos is. Om deze situaties te vermijden, en het eenvoudiger te maken om criteria te prioriteren, is er gekozen voor een aanpak waarbij alle criteria apart worden geoptimaliseerd.

34

3.2.1


Maximaliseren van het aantal geaccepteerde aanvragen

Optimalisatieprobleem Gegeven een set van beschikbare applicaties A die door eindgebruikers aangevraagd kunnen worden, en een set Ra met daarin alle aanvragen voor elke applicatie a. Een discrete inputvariabele Da geeft daarbij het totaal aantal aanvragen weer voor applicatie a. Een accepteringsmatrix G wordt tijdens de berekening van een plaatsing gebruikt om aan te duiden welke van de aanvragen r ∈ Ra geaccepteerd kon worden. Hierbij geeft de booleaanse beslissingsvariabele Ga,r = 1 aan dat de r-de aanvraag voor applicatie a wel geplaatst kon worden, en Ga,r = 0 indien dit niet mogelijk was. Zo’n beslissingsvariabele is steeds manipuleerbaar gedurende een iteratie van het APP en kan verscheidene waarden aannemen tijdens het optimalisatieproces. Met de uitvoering van elke applicatie a gaat steeds de uitvoering van een aantal communicerende services gepaard. Beschouwen we daartoe een set van beschikbare services S. Elke service s ∈ S heeft een bepaalde CPU-vereiste ωs (in GHz) en een zekere geheugenvereiste γs (in GB) om correct uitgevoerd te kunnen worden. Een instantiematrix I zal aanduiden of de functionaliteit van service s al dan niet nodig is om applicatie a uit te kunnen voeren. De booleaanse variabele Ia,s = 1 zal hierbij aangeven dat er een instantie van service s nodig is om applicatie a uit te kunnen voeren. Een waarde Ia,s = 0 betekent dan weer dat dit niet nodig is. Onder deze omstandigheden kan het eerste optimalisatieprobleem, het maximaliseren van het aantal geaccepteerde aanvragen, als volgt worden voorgesteld: ! max

X X a∈A r∈Ra

Ga,r ×

X

Ia,s × ωs

(3.1)

s∈S

Als gewichtsfactor bij dit optimalisatieprobleem zal bij elke aanvraag voor een applicatie de benodigde CPU-capaciteit van deze applicatie worden genomen. Bovenstaand optimalisatieprobleem zal dus ook die aanvragen aanvaarden die zorgen voor de grootste toekenning van CPU-capaciteit doorheen het netwerk. Om tot deze waarde te komen wordt er gesommeerd over alle aanvragen r ∈ Ra van elke applicatie a ∈ A. Bij elke van die aanvragen wordt de booleaanse beslissingsvariabele Ga,r , die aangeeft of deze aanvraag wordt aanvaard, vermenigvuldigd met de benodigde CPU-capaciteit om die applicatie uit te kunnen voeren. De benodigde CPU-capaciteit per applicatie wordt bekomen door de som te nemen van de CPU-vereisten van de verschillende services waaruit deze applicatie opgebouwd is.


35

Randvoorwaarden Het optimalisatieprobleem in 3.1 is onderhevig aan verschillende randvoorwaarden, waardoor er eerst enkele extra variabelen nodig zijn om deze te beschrijven. Beschouwen we daartoe een set van nodes N . Met elke node n ∈ N gaat een CPU-capaciteit Ωn (in GHz) en een geheugencapaciteit Γn (in GB) gepaard. Verder definiëren we ook nog een relatiematrix R, die aangeeft welke services uitgevoerd kunnen worden op welke node. Hierbij geeft de booleaanse variabele Rs,n = 1 aan dat service s wel kan uitgevoerd worden op node n, en Rs,n = 0 indien dit niet mogelijk is. Enkele redenen hiervoor kunnen gevonden worden in het feit dat er soms specifieke randapparatuur nodig is om een bepaalde service uit te voeren, of omwille van een bedrijfspolicy die stelt dat gevoelige software of data niet op eender welke node mag uitgevoerd worden. Ook is er het feit dat er (soms gelicentieerde) software nodig is om een bepaalde service uit te voeren, en dat deze software maar op een beperkte set van nodes ge¨ınstalleerd is. Vervolgens definiëren we ook de meerdimensionale array P , die de uiteindelijke plaatsingsarray a,r = 1 aan dat service s wordt voorstelt. Hierbij geeft de booleaanse beslissingsvariabele Ps,n a,r uitgevoerd op node n en behoort tot de r-de aanvraag van applicatie a. Een waarde Ps,n =0

geeft dan weer aan dat dit niet zo is. Om een gegeven applicatie a uit te kunnen voeren moet echter elk van zijn services s waaruit deze applicatie opgebouwd is, ook worden uitgevoerd in het netwerk. Dit betekent in wiskundige vorm dat: ∀a ∈ A, r ∈ Ra , s ∈ S, n ∈ N ∀a ∈ A, r ∈ Ra , s ∈ S

a,r Ps,n ≤ Ga,r X a,r Ps,n ≤1

(3.2) (3.3)

n∈N

∀a ∈ A, r ∈ Ra

Ga,r ×

X s∈S

Ia,s =

XX

a,r Ps,n

(3.4)

s∈S n∈N

Ga,r ∈ {0, 1}

(3.5)

a,r Ps,n ∈ {0, 1}

(3.6)

Formule 3.2 geeft aan dat ten alle tijde elke waarde van de plaatsingsarray P kleiner of gelijk aan moet zijn aan die van de accepteringsmatrix G. Indien een aanvraag r voor applicatie a niet kan voldaan worden, is het duidelijk dat geen enkele van zijn services kan geplaatst worden in het netwerk. Formule 3.3 geeft aan dat elke service s behorend tot aanvraag r voor applicatie a op maximaal één server kan uitgevoerd worden. Formule 3.3 stelt dat alle services s van een applicatie a moeten uitgevoerd worden in het netwerk, om te kunnen stellen dat deze bepaalde applicatie ook daadwerkelijk geplaatst is.

36


Tegelijkertijd moet ook de beperkte CPU- en geheugencapaciteit van elke node n ten allen tijde gerespecteerd worden wanneer er services op uitgevoerd worden. Om te kunnen voldoen aan deze twee voorwaarden introduceren we eerst de uitvoeringsmatrix U . Hierbij zal de booleaanse beslissingsvariabele Us,n = 1 aangeven dat een instantie van service s wordt uitgevoerd op node n, en geeft Us,n = 0 aan dat dit niet zo is. Dit leidt tot de volgende twee randvoorwaarden: ∀n ∈ N :

X X X

a,r Ps,n × ωs ≤ Ω n

(3.7)

a∈A r∈Ra s∈S

∀n ∈ N :

X

Us,n × γs ≤ Γn

(3.8)

s∈S

Us,n ∈ {0, 1}

(3.9)

Formule 3.7 geeft aan dat de som van de CPU-vereisten van alle services s die uitgevoerd worden op een bepaalde node n kleiner moet zijn dan de beschikbare CPU-capaciteit van deze node. Formule 3.8 geeft aan dat de som van de geheugenvereisten van alle services s die uitgevoerd worden op een bepaalde node n kleiner moet zijn dan de beschikbare CPU-capaciteit van deze node. De reden waarom in deze laatste formule met de uitvoeringsmatrix U wordt gewerkt en niet terug met de plaatsingsarray P , is omdat de geheugenkost van een service op een bepaalde node n onafhankelijk is van de hoeveelheid instanties die er van deze service worden op uitgevoerd. Dit komt omdat het uitvoeren van een image van die service een vaste geheugenkost zal opeisen van de node waarop deze uitgevoerd wordt. De geheugenkost is dan ook onafhankelijk van de hoeveelheid CPU-cycles die nodig is om deze service te verrichten. De service blijft deze vaste hoeveelheid geheugen opeisen voor de verdere duur dat ze ge¨ınstantieerd is. Er wordt hierbij dus aangenomen dat de geheugenkost belastingsonafhankelijk is, en dit in tegenstelling tot de CPU-kost. Deze neemt immers wel toe met het aantal instanties van een service die op een node worden geplaatst. Om deze reden is het ook voordeliger om meerdere services van een bepaald type te plaatsen op een node waar al minstens één zulke service aanwezig op is. Om het verband vast te leggen tussen de uitvoeringsmatrix U en de plaatsingsarray P worden volgende randvoorwaarden toegevoegd aan de probleemstelling: ! ∀s ∈ S, n ∈ N :

X X

a,r Ps,n ≤ Us,n ×

a∈A r∈Ra

∀s ∈ S, n ∈ N :

Us,n ≤ Rs,n

X

Da × Ia,s

(3.10)

a∈A

(3.11)

Het linkerlid van de ongelijkheid in formule 3.10 geeft weer hoeveel instanties van service s er uitgevoerd worden op node n. In het rechterlid is Us,n een booleaanse variabele, die aanduidt


37

of er minstens één instantie van service s uitgevoerd wordt op node n. De vermenigvuldiging P van a∈A Da × Ia,s geeft weer hoeveel services er maximaal worden aangevraagd van type s. Het is dan ook duidelijk dat het linkerlid van deze ongelijkheid nooit groter kan worden dan het rechterlid. Doordat het objectief van de optimalisatie erin bestaat om zoveel mogelijk applicaties te plaatsen in het netwerk, wordt de waarde van Us,n automatisch gedwongen op één waar nodig. Formule 3.11 geeft aan dat er nooit instanties van een service s kunnen geplaatst worden op een node n die deze service-instantie niet ondersteunt. Naast deze randvoorwaarden is er ook nog een bijkomende voorwaarde die stelt dat elke workflow in het netwerk, dus elke communicatie tussen twee services, minstens voor 80% voldaan moet worden. Dit kan wiskundig uitgedrukt worden als volgt: ∀a ∈ A, r ∈ Ra , s1 , s2 ∈ S, n ∈ N :

zsa,r × Ga,r = 0.80 1 ,s2

(3.12)

De bijkomende voorwaarden bij deze gelijkheid worden behandeld in de volgende sectie.

3.2.2

Maximaliseren van de communicatie-voldoening van elke workflow

Optimalisatieprobleem In het netwerk wordt er tussen elk paar communicerende services s1 en s2 die behoren tot eenzelfde aanvraag r voor een bepaalde applicatie a een workflow opgesteld. Wegens de eindige hoeveelheid bandbreedte die maar beschikbaar is op elke communicatielink in het netwerk kan er vaak niet gegarandeerd worden dat de volledige bandbreedte die nodig is voor deze communicatie kan gereserveerd worden. Men werkt dan ook met variabelen die ervoor zorgen dat een bepaald deel van de communicatie tussen deze services verwezenlijkt wordt [41]. Het APP wordt hier dus uitgebreid door elke communicatielink e ∈ E in het netwerk nauwkeurig te modelleren, en tevens te definiëren in welke mate de verschillende services communiceren met elkaar. Hiertoe wordt eerst de bandbreedtematrix B bepaald, waarbij de continue variabele Bn1 ,n2 aangeeft hoeveel bandbreedte (in Mbit/s) er beschikbaar is op elke communicatielink e (dus tussen elk paar nodes n1 en n2 ). Daarna wordt ook een communicatiematrix C gedefinieerd, waarbij de continue variabele Cs1 ,s2 aangeeft hoeveel bandbreedte (in Mbit/s) er nodig is om de communicatie tussen de services s1 en s2 te kunnen realiseren. De service s1 wordt gezien als de bron (source) van de workflow, terwijl de service s2 de bestemming (sink ) van deze workflow voorstelt. De flow die langs elke communicatielink passeert kan men terugvinden uit de flowar-

38


ray F , waarbij de continue beslissingsvariabele Fsa,r 1 ,s2 (n1 , n2 ) aangeeft hoeveel bandbreedte de communicatie tussen de services s1 en s2 gebruikt, behorend tot de r-de aanvraag van applicatie a, indien deze services respectievelijk worden uitgevoerd op de nodes n1 en n2 . Het objectief van deze optimalisatie is om een workflow te vinden tussen elk paar communicerende services s1 en s2 , die zorgt voor een maximaal percentage zw (= zsa,r 1 ,s2 ) van de vereiste bandbreedte voor deze communicatie [41]. Het tweede optimalisatieobjectief, het maximaliseren van de communicatie-voldoening voor elke workflow, kan dus als volgt worden voorgesteld: max

X X

X

zsa,r 1 ,s2

(3.13)

a∈A r∈Ar s1 ,s2 ∈S

Randvoorwaarden Deze optimalisatie is onderhevig aan twee randvoorwaarden, namelijk de flow conservation voorwaarde (formule 3.15) en de eindige bandbreedte voorwaarde (formule 3.24). Eerst definiëren we de flow conservation voorwaarde, die stelt dat er geen flow kan ontstaan of geconsumeerd worden door nodes die geen source of sink zijn van de betreffende workflow: ∀a ∈ A, r ∈ Ra , s1 , s2 ∈ S, n ∈ N : X X a,r Fsa,r (n) = F (m, n) − Fsa,r (n, m) s1 ,s2 1 ,s2 1 ,s2 (m,n)∈E

    −zsa,r 1 ,s2 × Cs1 ,s2    Fsa,r (n) = +zsa,r 1 ,s2 1 ,s2 × Cs1 ,s2      0

(3.14)

(n,m)∈E

als n de source is van s1 als n de sink is van s2

(3.15)

indien anders

Formule 3.15 kan ook geschreven worden als volgt: Fsa,r (n) = zsa,r × Psa,r − Psa,r × Cs1 ,s2 1 ,s2 1 ,s2 2 ,n 1 ,n

(3.16)

Formule 3.15 introduceert een nieuwe continue beslissingsvariabele Fsa,r 1 ,s2 (n) die kan bekomen worden uit de flowarray F . Deze beslissingsvariabele stelt de netto flow voor van elke workflow op elke node n. De waarde van deze variabele wordt bepaald door de som van de uitgaande flow af te trekken van de som van de inkomende flow op elke node. Voor elke node n die geen source of sink is van een workflow moet dit resultaat nul zijn, aangezien er geen flow kan verloren gaan op zulke nodes. Voor nodes die de source zijn van een workflow zal er enkel een uitgaande


39

flow zijn, waardoor de totale flow in deze node negatief is. Voor nodes die de sink zijn van een workflow zal er enkel een inkomende flow zijn, waardoor de totale flow in deze node positief is. a,r Bij dit objectief wordt de vermenigvuldiging gemaakt van de beslissingsvariabelen zsa,r 1 ,s2 en Ps1 ,n , a,r alsmede zsa,r 1 ,s2 en Ps2 ,n . Hierdoor kan er op het eerste zicht niet meer gesproken worden van li-

neair programmeren, aangezien het probleem ogenschijnlijk kwadratisch is geworden. Echter, a,r aangezien Psa,r 1 ,n en Ps2 ,n booleaanse beslissingsvariabelen zijn kan de vermenigvuldiging ervan

met zsa,r 1 ,s2 (een continue variabele) geschreven worden aan de hand van enkele bijkomende lineaire vergelijkingen. Hiertoe worden twee bijkomende continue beslissingsvariabele xa,r s1 ,s2 ,n en ysa,r 1 ,s2 ,n gedefinieerd, die gebruikt worden om de vermenigvuldiging te realiseren tussen de eera,r a,r der vernoemde variabelen. Hierbij zal uiteindelijk xa,r s1 ,s2 ,n = zs1 ,s2 × Ps1 ,n voorstellen, en zal a,r a,r ysa,r 1 ,s2 ,n = zs1 ,s2 × Ps2 ,n voorstellen. a,r xa,r s1 ,s2 ,n ≤ Ps1 ,n

(3.17)

a,r xa,r s1 ,s2 ,n ≤ zs1 ,s2

(3.18)

a,r a,r xa,r s1 ,s2 ,n ≥ zs1 ,s2 + (Ps1 ,n − 1)

(3.19)

ysa,r ≤ Psa,r 1 ,s2 ,n 2 ,n

(3.20)

ysa,r ≤ zsa,r 1 ,s2 ,n 1 ,s2

(3.21)

ysa,r ≥ zsa,r + (Psa,r − 1) 1 ,s2 ,n 1 ,s2 2 ,n

(3.22)

a,r a,r Indien Psa,r 1 ,n = 0 is, dan wordt xs1 ,s2 ,n via 3.17 ook gedwongen op 0. De waarde van zs1 ,s2 moet

dan volgens 3.18 en 3.19 liggen tussen respectievelijk 0 en 1. Indien Psa,r 1 ,n = 1 is, dan moet a,r a,r a,r xa,r s1 ,s2 ,n ≤ 1 worden via 3.17. Formule 3.18 stelt dat xs1 ,s2 ,n ≤ zs1 ,s2 , en 3.19 stelt dat xs1 ,s2 ,n ≥ a,r a,r zsa,r 1 ,s2 . De enige mogelijke waarde voor xs1 ,s2 ,n is de gelijkheid ervan aan zs1 ,s2 , waardoor aldus

de gewenste vermenigvuldiging tussen beide beslissingsvoorwaarden is gerealiseerd. Een analoge a,r redenering gaat op voor Psa,r 2 ,n en ys1 ,s2 ,n .

Een bijkomende voorwaarde, die zoals eerder aangehaald tijdens het vorige optimalisatiecriterium ook al geldig was, is dat een applicatie maar als geplaatst mag worden beschouwd indien er minstens 80% van zijn communicatie-eis is verwezenlijkt voor elk van zijn workflows. ∀a ∈ A, r ∈ Ra , s1 , s2 ∈ S :

Ga,r ≤ zsa,r + 0.2 1 ,s2

(3.23)

Daar waar in formule 3.12 nog werd geëist dat elke workflow voor exact 80% moest worden voldaan, zal er nu worden geprobeerd om deze communicatie-voldoening te maximaliseren. Formule 3.23 impliceert dat zsa,r 1 ,s2 ≥ 0.8 moet zijn indien de r-de aanvraag voor applicatie a wordt

40


geaccepteerd. Dit criterium zorgt ervoor dat er geen aanvragen worden geaccepteerd wiens communicatie-eis voor minder dan 80% kan worden voldaan. Naast bovenstaande randvoorwaarden moet er ten allen tijden voldaan worden aan de eindige bandbreedte voorwaarde van elke communicatielink: ∀n1 , n2 ∈ N :

P

a∈A

P

r∈Ra

P

s1 ,s2 ∈S

Fsa,r 1 ,s2 (n1 , n2 ) ≤ Bn1 ,n2

(3.24)

Formule 3.24 geeft weer dat de som van alle workflows die passeren over elke communicatielink, niet de beschikbare bandbreedte van deze communicatielink mag overschrijden.

3.2.3

Minimaliseren van het aantal gebruikte nodes bij de plaatsing

Optimalisatieprobleem Een volgend objectief dat geoptimaliseerd wordt is het aantal gebruikte nodes om een plaatsing te realiseren. Hoe minder nodes er immers gebruikt worden om alle aanvragen te behandelen, hoe meer nodes er in de idle-toestand kunnen geplaatst worden. Dit zorgt ervoor dat er meer energie kan bespaard worden, wat voor een cloud provider met grote hoeveelheden nodes van zeer groot belang is. Hiervoor wordt er een bijkomende booleaanse beslissingsvariabele Un1D gedefinieerd, waarbij Un1D = 1 aangeeft dat node n gebruikt wordt om een plaatsing te realiseren, en Un1D = 0 indien dit niet zo is. Deze variabele manifesteert zich als volgt bij dit derde optimalisatieobjectief, zijnde het minimaliseren van het aantal gebruikte nodes bij de plaatsing: min

X

Un1D

(3.25)

n∈N

In dit optimalisatieprobleem wordt geprobeerd om het aantal gebruikte nodes bij een plaatsing te minimaliseren. Daartoe wordt de som genomen over alle nodes van de variabele Un1D .

Randvoorwaarden Deze beslissingsvariabele is tevens onderhevig aan de volgende randvoorwaarden: ∀n ∈ N :

X

Us,n ≤ Un1D × |S|

(3.26)

s∈S

Un1D ∈ {0, 1}

(3.27)

Formule 3.26 geeft aan dat ten alle tijde de vermenigvuldiging van Un1D met het aantal mogelijke services groter moet zijn dan de som van het aantal services op elke node. In combinatie met


41

het optimalisatieobjectief waarbij geprobeerd wordt om Un1D zo klein mogelijk te houden zorgt dit ervoor dat indien Un1D = 0 is, er geen enkele service kan uitgevoerd worden op node n.

3.2.4

Minimaliseren van het aantal verplaatsingen tussen twee iteraties

Optimalisatieprobleem Een volgend objectief is het minimaliseren van het aantal verplaatsingen tussen twee opeenvolgende iteraties van het APP [24, 27, 53]. Hierbij stelt U i de uitvoeringsmatrix voor gedurende de i-de iteratie van het APP, en was U i−1 de uiteindelijke uitvoeringsmatrix tijdens de vorige (de i = 1 aangeven i − 1-de) iteratie van het APP. Hierbij zal de booleaanse beslissingsvariabele Us,n

dat een instantie van service s wordt uitgevoerd op node n gedurende de i-de iteratie van het i APP, en geeft Us,n = 0 aan dat dit niet zo is. Het verschil tussen U i en U i−1 ligt in het feit

dat U i een beslissingsvariabele is wiens waarde manipuleerbaar is gedurende de i-de iteratie van het APP, en U i−1 een vaste waarde heeft gedurende deze iteratie. Onder deze omstandigheden kan het vierde optimalisatieobjectief, het minimaliseren van het aantal verplaatsingen van service-instanties tussen twee iteraties, als volgt worden voorgesteld: min

XX

i i−1 |Us,n − Us,n |

(3.28)

s∈S n∈N

Dit optimalisatiecriterium zorgt ervoor dat er zo weinig mogelijk verplaatsingen zijn van serviceinstanties tussen twee opeenvolgende iteraties van het APP, aangezien zulke verplaatsingen gezien worden als een kostbare verspilling van tijd en resources. Omdat een absolute waarde onmogelijk is om als dusdanig te definiëren bij een ILP is een bijkomende tussenstap nodig, waarvoor we een bijkomende beslissingsvoorwaarde diff is,n definiëren als volgt: i−1 ∀Us,n =0:

i−1 i diff is,n = Us,n + Us,n

(3.29)

i−1 ∀Us,n =1:

i−1 i diff is,n = Us,n − Us,n

(3.30)

Het optimalisatieobjectief herleidt zich dan tot: min

XX

diff is,n

(3.31)

s∈S n∈N

Volgende waarheidstabel toont aan dat deze tussenstap uiteindelijk leidt tot het realiseren van i−1 en U i elkaar zouden opheffen: een absolute waarde, zonder het risico dat beide variabelen Us,n s,n

42


i−1 Us,n

i Us,n

diff is,n

0

0

0

0

1

1

1

0

1

1

1

0

Tabel 3.3: Realiseren van een absolute waarde in een optimalisatieprobleem

3.2.5

Maximaliseren van de service workflow effici¨ entie

Optimalisatieprobleem Een laatste objectief is het maximaliseren van de service workflow efficiëntie, die hier op een eenvoudigere wijze geformuleerd is als het minimaliseren van de netwerk inefficiëntie. Dit aspect van het netwerk gedeelte wordt ook omschreven als het Minimum-Cost Flow Problem (MCFP). De opdracht van het MCFP is om de goedkoopst mogelijke weg doorheen het netwerk te zoeken om een bepaalde hoeveelheid flow te versturen van een bepaalde bron naar een zekere bestemming. Daartoe wordt eerst de hopcountmatrix H bepaald, waarbij de discrete variabele Hn1 ,n2 aangeeft hoeveel tussenliggende apparatuur (zoals nodes zelf, routers, switches, bridges) er minstens aanwezig is op het kortste pad tussen elk paar nodes n1 en n2 . De hop count tussen twee nodes geeft op deze manier de hoeveelheid apparatuur weer die een hoeveelheid data moet passeren wanneer deze vloeit van bron naar bestemming. Elke vorm van apparatuur wordt daarbij gezien als één hop, waardoor de totale hop count een eenvoudige maatstaf is voor de afstand die deze data dient af te leggen. Het doel van deze optimalisatie is een algemenere maatstaf te introduceren die aangeeft hoe efficiënt (of inefficiënt) het verkeer in het netwerk wordt gerouteerd. Deze nieuwe maatstaf wordt bekomen uit de vermenigvuldiging van de hoeveelheid workflow (in Mbit/s) tussen elk paar nodes, samen met de hop count tussen deze nodes. Beide factoren worden op deze manier gecombineerd met elkaar, wat al eerder besproken werd in [32]. Daar wordt er echter gewerkt met een statische waarde voor de communicatie tussen twee services, waarbij er verder geen rekening wordt gehouden met de mate waarin aan deze eis kan worden voldaan. In deze thesis wordt dit aspect verder verfijnd, door gebruik te maken van de flowarray F . In deze array wordt immers inherent de variabele zw gebruikt die aangeeft in hoeverre aan elke communicatie-eis is voldaan. Onder deze omstandigheden kan het vijfde optimalisatieobjectief, het maximaliseren


43

van de service workflow efficiëntie (minimaliseren van de netwerk inefficiëntie), als volgt worden voorgesteld:  min

X

 X X

X

 n1 ,n2 ∈N

Fsa,r (n1 , n2 ) × Hn1 ,n2 1 ,s2

(3.32)

a∈A r∈Ra s1 ,s2 ∈S

Dit optimalisatiecriterium zal ervoor zorgen dat de grootste hoeveelheid workflow (in Mbit/s) zoveel mogelijk plaatsvindt tussen die nodes met een lage hop count. Het criterium probeert de plaatsing van communicerende services op bepaalde nodes zoveel mogelijk te beperken tot dat deel van het netwerk waar de hop count tussen deze nodes laag is. Services die maar in een beperkte mate met elkaar communiceren mogen volgens dit criterium dan ook iets verder van elkaar uitgevoerd worden. Deze zorgen immers maar voor een relatief kleine bijdrage in het optimalisatieprobleem ten opzichte van services die veel intenser met elkaar communiceren. Om deze reden wordt er ook gewerkt met de vermenigvuldiging tussen beide parameters, aangezien ze maar een uitspraak kunnen doen omtrent de service workflow efficiëntie indien ze samen worden geëvalueerd. Een alternatief voor deze hopcountmatrix is het gebruik van een latencymatrix. De variabelen in zo’n latencymatrix zullen aangeven hoeveel tijd (in milliseconden) een IP pakket nodig heeft om van een bepaalde bron naar een zekere bestemming getransporteerd te worden. In tegenstelling tot de hop count is de latency een nuttigere maatstaf bij het bepalen van een optimaal netwerkpad, aangezien de hop count geen rekening houdt met de belasting van elke communicatielink, de betrouwbaarheid ervan of de latency. Echter, informatie verzamelen over de waarde van de latency tussen elk paar nodes is een complexer proces dan wanneer men de hop count ertussen zou bepalen. De waarde van de latency is tevens een proces dat vrij variabel is doorheen de tijd, waardoor men periodiek metingen hieromtrent zou moeten uitvoeren. Indien dit niet wordt gedaan zal de relevantie ervan in het optimalisatiecriterium grotendeels verloren gaan. Tevens zal de latency zelf vaak afhankelijk zijn van de hoeveelheid communicatie over de verschillende communicatielinks, waardoor deze latency zelf een beslissingsvariabele wordt. Omwille van deze redenen is ervoor gekozen om met de hop count te werken als kost-metriek tussen elk paar nodes. Het dient echter opgemerkt te worden dat in formule 3.32 deze hop count makkelijk vervangen kan worden door een statische latencymatrix.

Hoofdstuk 4

Architectuur 4.1

Inleiding

In dit hoofdstuk wordt een architectuur besproken die het mogelijk maakt om op een hiërarchische wijze een oplossing te berekenen voor het APP. Hierbij worden de verschillende bouwblokken besproken die nodig zijn om een plaatsing te berekenen van welke service-instanties op welke resources moeten uitgevoerd worden, opdat het systeem de aanvragen van gebruikers op een correcte manier kan behandelen. Hiervoor is onder andere kennis nodig van het aantal aanvragen voor elke applicatie, de services waaruit zo’n applicatie opgebouwd is, de service-instanties die momenteel op de verschillende nodes aanwezig zijn, en vele andere zaken.

4.2

Architecturale vereisten

De volgende vereisten zijn van belang bij het ontwerpen van een goede architectuur van het systeem dat in deze thesis wordt beschouwd: • Performantie: Het algoritme dat instaat voor het oplossen van het APP, alsmede de architectuur die het algoritme daarbij ondersteunt, moet op een relatief snelle manier een oplossing kunnen berekenen. Dit is een vereiste die van groot belang is, om een systeem te bekomen dat bruikbaar is in het netwerk van een cloud provider. Indien het berekenen van zo’n plaatsing teveel tijd kost, zal een gebruiker te lang moeten wachten alvorens hij controle krijgt over de applicaties die hij heeft aangevraagd.

45

46

HOOFDSTUK 4. ARCHITECTUUR

• Kwaliteit van het resultaat: Naast het op een snelle manier kunnen bekomen van een oplossing, moet deze oplossing liefst ook zoveel mogelijk voldoen aan de vereisten van de gebruikers. Dit houdt in dat de CPU- en geheugenvereisten van de applicaties die aangevraagd worden, zoveel mogelijk moeten voldaan worden. De services waaruit zo’n applicatie bestaat dienen zich best ook zo dicht mogelijk bij elkaar te bevinden in het netwerk, zodat de responstijd naar de gebruikers toe niet al te hoog oploopt. Tevens zal er moeten gekeken worden naar de beschikbare bandbreedte van alle communicatielinks in het netwerk, zodat de communicatievereisten van de services deze links in het netwerk niet verzadigen. • Schaalbaarheid: De performantie en kwaliteit waarmee een oplossing voor het APP wordt aangeboden dient ook schaalbaar te zijn. Indien de hoeveelheid aanvragen, applicaties, services of nodes in de cloud toeneemt, dient het APP nog steeds een kwalitatieve plaatsing te kunnen berekenen in een aanvaardbare tijd. De keuze van het algoritme die deze plaatsing berekent zal hier ongetwijfeld een cruciale rol in spelen. • Betrouwbaarheid: De mogelijkheid om een oplossing te kunnen berekenen voor het APP dient niet af te hangen van één enkele beherende server. Indien deze node immers zou falen betekent dit dat het volledige systeem onbruikbaar wordt, aangezien er geen plaatsingen van applicaties of resources meer kunnen bekomen worden. Een degelijk ontworpen netwerkarchitectuur kan vrij goed omgaan met dit soort problemen, bijvoorbeeld door te steunen op protocollen zoals leader election [12]. Hierbij wordt een gepaste server gezocht onder alle nog functionerende nodes, die dan wordt gepromoveerd tot nieuwe beherende server. • Aanpasbaarheid: De architectuur dient tevens op een eenvoudige manier aanpasbaar te zijn, en moet kunnen werken onder verschillende externe omstandigheden. Aangezien er een grote hoeveelheid algoritmen bestaat die het APP kunnen oplossen, is het niet onmogelijk dat een cloud provider na verloop van tijd wil overstappen op een ander, hopelijk beter, algoritme. Daarnaast is het ook mogelijk dat verschillende parameters die gebruikt worden in zo’n algoritme zich kunnen aanpassen aan bepaalde externe factoren. Hierbij denken we bijvoorbeeld aan de hoeveelheid aanvragen voor applicaties, het aantal service-instanties, de hoeveelheid nodes in het netwerk, en dergelijke.

4.3. VOORGESTELDE SYSTEEMARCHITECTUUR

4.3 4.3.1

47

Voorgestelde systeemarchitectuur Hi¨ erarchische boomstructuur binnen het netwerk

De verschillende servers binnen het netwerk van een cloud provider worden in deze thesis op een hiërarchische manier opgesplitst in beherende- en uitvoerende servers (management- en execution-servers). Dit proces gebeurt volgens een ouder-kind relatie, waardoor alle servers in het netwerk kunnen voorgesteld worden in een hiërarchische boomstructuur. Een voorbeeld van het resulterende logische netwerk wordt ge¨ıllustreerd in figuur 4.1.

Execution Server

Management Server

Execution Server

Execution Server

...

Execution Server

Management Server

...

Execution Server Execution Server Management Server

Management Server Execution Server

Execution Server

Management Server

Execution Server

...

Execution Server

Figuur 4.1: Hiërarchische logische boomstructuur van het netwerk. Een beherend netwerk dat hiërarchisch is opgesteld wordt ook besproken in [18] en [40]. De kinderen van zo’n beherende server kunnen terug beherende servers zijn, of wanneer men zich in de onderste laag van de boomstructuur bevindt, zijn deze kinderen de uitvoerende servers. Enkel deze onderste laag van servers in de structuur (de uitvoerende servers) zullen effectief instanties van applicaties of services uitvoeren. Alle andere servers in het netwerk zijn verantwoordelijk voor het beheren van deze uitvoerende servers, of voor het beheer van andere beherende servers.

48


Deze manier van werken heeft zijn invloed op het algoritme dat het APP oplost. Indien men op een gecentraliseerde manier te werk gaat, zal er telkens één beherende server zijn die alle aanvragen behandelt. Bij het berekenen van een plaatsing voor deze aanvragen zal telkens het volledige netwerk van de cloud provider moeten beschouwd worden. Indien men echter hiërarchische te werk gaat, kan er eerst een beherende server gekozen worden om alle aanvragen te behandelen, wiens kinderen momenteel weinig service-instanties uitvoeren. Alle aanvragen die niet konden geplaatst worden door deze beherende server, worden dan simpelweg doorgegeven naar een andere beherende server. Deze server kan zich bevinden op hetzelfde logische niveau in de hiërarchische structuur, of kan zich hogerop bevinden in deze structuur. Door deze aanpak te hanteren is er op elk moment maar een beperkte kijk nodig op het netwerk. Dit zorgt ervoor dat een oplossing voor het APP veel sneller kan bekomen worden, en meer schaalbaar is dan een gecentraliseerde aanpak. Een nadeel van deze aanpak is dat er veel communicatie moet gebeuren tussen de verscheidene beherende servers in het netwerk om een kwalitatieve hiërarchische boomstructuur te kunnen aanhouden. Tevens zal er, indien er een grote hoeveelheid aanvragen voor applicaties binnenkomen, op een bepaald punt eventueel toch moeten overgeschakeld worden naar de beherende server bovenaan de structuur. In deze situatie is er dus toch een volledige kijk op het netwerk nodig, waardoor men hier toch een gecentraliseerde aanpak hanteert. Echter, op dit moment zijn al een aantal uitvoerende servers zodanig belast met het uitvoeren van applicatie- en service-instanties, dat ze in principe niet meer hoeven beschouwd te worden door de centrale beherende server.

4.3.2

Schematische voorstelling van het volledige systeem

In figuur 4.2 wordt een architectuur voorgesteld die het mogelijk maakt om op een hiërarchische manier het APP op te lossen. De verschillende bouwblokken die voorkomen in deze architectuur worden beschreven in sectie 4.3.3. Het dient opgemerkt te worden dat alle bouwblokken die met blauw aangeduid werden, de enige zijn die ook effectief ge¨ımplementeerd werden in deze thesis. Vanwege het feit dat er in dit werk uitsluitend simulaties worden gebruikt om de ge¨ımplementeerde algoritmen te evalueren, werden alle andere bouwblokken beschouwd als een soort black box, of zelfs volledig geabstraheerd in de probleemstelling. Indien deze architectuur ook effectief dient toegepast worden in een cloud omgeving, moeten deze bouwblokken uiteraard wel ge¨ımplementeerd worden.


49

«component» Cloud Service Manager

«component» Management Server

«component» Execution Server

«component» Server Manager



«component» Hierarchical Cluster Selector

Management Interface

«component» Service Image Repository «component» Application Control Map

«component» Hierarchy Controller

Service Interface

«component» Hierarchy Controller

«component» Cloud Environment

«component» Cloud Environment

«component» Application Control Map

«component» Node Sensor «component» Node Effector

«component» Placement Controller

Request Interface

«component» Services

«component» Placement Algorithm

«component» Application Request Router

«component» Node Controller Web Interface

Client

Client

Management Interface

«component» Management Server ...

Service Interface

«component» Execution Server ...

Service Interface

«component» Execution Server ...

Figuur 4.2: Schematische voorstelling van de systeemarchitectuur.

4.3.3

Benodigde bouwblokken

In deze sectie worden de verschillende bouwblokken besproken die voorkomen in de architectuur zoals weergegeven in figuur 4.2.

Server Manager De Server Manager is een component die op elke server moet aanwezig zijn, zodat er dynamisch in het netwerk kan bepaald worden of deze server dienst doet als beherende- of als uitvoerende server. Dit komt de schaalbaarheid ten goede, onder meer doordat het volledige netwerk via deze component dynamisch kan schalen en zich kan herorganiseren wanneer daar nood aan is. Denken we bijvoorbeeld aan het falen van een beherende server, waarna een uitvoerende server gepromoveerd wordt om dienst te doen als nieuwe beherende server. Andersom is ook mogelijk, indien er bijvoorbeeld een teveel is aan beherende servers, waarna er een wordt gedegradeerd tot uitvoerende server. Om deze functionaliteit te verwezenlijken zal de Server Manager onder andere een Hierarchy Controller implementeren, dewelke later wordt uitgelegd. De Server Manager is tevens ook verantwoordelijk voor de communicatie tussen de verschillende servers in het netwerk, alsmede voor het groeperen en selectief doorgeven van informatie naar boven toe in de boomstructuur. Door het verzamelen en selectief filteren van deze informatie kan de overhead binnen een netwerk sterk gereduceerd worden [18]. Zo kunnen servers hogerop

50


in de structuur met beperktere parameters, doch een globaler beeld, de werklast verdelen binnen het netwerk. Indien de hoeveelheid informatie niet zou gefilterd en selectief doorgegeven worden, ontstaan er bottlenecks hogerop in de structuur.

Hierarchy Controller Deze component is een onderdeel van de Server Manager, en is dus tevens aanwezig op elke server in het netwerk. De Hierarchy Controller zal onder andere informatie verzamelen en bijhouden omtrent de performantie (de werklast meer bepaald) van de kinderen die deze node beheert. Deze kinderen kunnen uitvoerende servers zijn, of andere controllers die uitgevoerd worden op beherende servers lager in de hiërarchie [40]. Informatie omtrent de werklast kan bekomen worden door te kijken naar de output van de Placement Controller (die het APP oplost), of simpelweg door de informatie op te vragen van de child nodes. Deze informatie wordt dan doorgeven naar beherende servers hogerop in de boomstructuur, om beslissingen op een hoger niveau in deze structuur mogelijk te maken. Naast deze informatie wordt ook het aantal servers meegegeven die deze node beheert. Op deze manier kan er vanaf deze server, of ergens hogerop in de structuur, een reorganisatie gebeuren van de boomstructuur. Dit wordt ook voorgesteld in figuur 4.3. Indien verscheidene child nodes van een beherende server worden uitgeschakeld omdat er een teveel is aan werkkracht in het systeem, kan het voordeliger zijn om deze beherende server en zijn kinderen samen te voegen onder de autoriteit van een andere beherende server.

Figuur 4.3: Oplossen van de overbezetting van een beherende server.

Application Request Router Aanvragen van gebruikers of resource brokers, die kunnen handelen als tussenpersoon voor de eindgebruikers, worden verzameld door de Application Request Router. Deze component zal de totale hoeveelheid aanvragen, of eventueel een deel daarvan, doorsturen naar de Hierarchical


51

Cluster Selector. Deze zal vervolgens een beherende server selecteren op basis van zijn huidige bezettingsgraad, om de binnengekomen aanvragen verder te behandelen. De Application Request Router kan ook gebruikt worden om bij te houden hoeveel aanvragen er gedurende een zekere tijdsperiode zijn binnengekomen voor een bepaalde applicatie. Hij kan ook gebruikt worden om eventueel statistieken te verzamelen wat betreft de populariteit van de verschillende applicaties. Deze informatie kan vervolgens gebruikt worden om op de verscheidene nodes in het netwerk meer instanties te plaatsen van services, dewelke behoren tot een populaire applicatie. Op deze manier kan er dynamisch ingespeeld worden op de vraag van eindgebruikers, om zo in de toekomst makkelijker aan hun aanvraag te kunnen voldoen. Technologieën die inspelen op dit bepaalde aspect liggen echter buiten het bereik van deze thesis.

Hierarchical Cluster Selector De Hierarchical Cluster Selector zal onder de beschikbare beherende servers in het netwerk, een server selecteren die zal instaan voor de behandeling van de binnengekomen aanvragen. Voor het selecteren van zo’n geschikte server zal er gekeken worden naar de werklast van alle kinderen van elke beherende server. Hierbij zullen clusters met een lage werklast eerst gekozen worden, omdat die de grootste kans hebben om de binnengekomen aanvragen (zij het deels) te kunnen behandelen. Het overschot aan aanvragen wordt dan op een hiërarchische wijze doorgegeven naar hogerop toe in de boomstructuur, zoals ook wordt voorgesteld in figuur 4.4. Overschot aanvragen

Beherende servers

Overschot aanvragen

…

…

…

Uitvoerende servers

Figuur 4.4: Doorgeven van het overschot aan aanvragen door beherende servers.

52


Door op deze manier te werken zal de root node in de hiërarchie geen bottleneck worden voor het delegeren van de binnengekomen aanvragen. Deze root node zal dan enkel aangesproken worden indien vele van zijn kinderen de plaatsing niet kunnen behandelen. Het globale beeld op het netwerk van deze node kan dan gebruikt worden om een geschikte oplossing voor het APP te berekenen. De informatie omtrent de werklast van de verscheidene nodes wordt op een hiërarchische wijze bijgehouden doorheen het systeem met behulp van een Hierarchy Controller, en zal selectief doorgegeven worden doorheen de structuur.

Node Controller De Node Controller zal van elke child-node in het bezit van een beherende server bepaalde gegevens opvragen, met de voorwaarde dat diens kinderen uitvoerende servers zijn. Er wordt onder andere verzameld welke service-instanties elke node kan uitvoeren, en welke services er momenteel worden uitgevoerd. Tevens wordt er verzameld hoeveel CPU- en geheugencapaciteit deze node heeft, alsmede zijn vrije capaciteit op dat vlak. Elke beherende server geeft ook een matrix weer met daarin de hop count tussen elk paar nodes die deze server in zijn beheer heeft.

Node Sensor De Node Sensor zal lokaal gegevens verzamelen over een bepaalde node, en deze informatie doorsturen via de Server Manager. Er wordt doorgegeven welke service-instanties deze node kan uitvoeren, en welke services er op dit moment worden uitgevoerd. Tevens wordt er verzameld hoeveel CPU- en geheugencapaciteit deze node heeft, plus zijn vrije capaciteit op dat vlak.

Placement Controller De Placement Controller wordt uitgevoerd door een beherende server, en bevat het algoritme om een oplossing voor het APP te berekenen. Deze component zal als output een matrix opstellen, die voor elk van de nodes die deze server beheert uiteindelijk zal bepalen hoeveel instanties er van elke service moeten op uitgevoerd worden. Deze output bedraagt het aantal instanties die er van elke service moeten worden afgebroken of opgezet, gebaseerd ten opzichte van de huidige configuratie. Deze informatie wordt via de Server Manager doorgegeven naar elke node wiens configuratie conflicteert met deze output. Informatie omtrent de huidige bezetting van nodes kan bekomen worden via de Node Controller, en een nieuwe configuratie wordt vervolgens beheerd door de Node Effector, dewelke in een volgend puntje wordt besproken.


53

Node Effector De Node Effector zal op basis van de commando’s van de Placement Controller op de huidige node bepaalde instanties starten en/of stoppen, omdat diens huidige configuratie conflicteert met de vooropgestelde configuratie om de nieuwe plaatsing te kunnen doorvoeren.

Application Control Map De Application Control Map zal van applicatie die aangevraagd kan worden door gebruikers bijhouden welke service-instanties hiermee geassocieerd zijn. Tevens bevat deze component informatie omtrent de hoeveelheid CPU- en geheugencapaciteit die elke services vereist. Indien men niet zou werken met deze component moet elke node lokaal kennis hebben alle applicaties, de service-instanties waaruit ze opgebouwd zijn, en de vereisten inzake CPU- en geheugencapaciteit. Door middel van een Application Control Map kan elke node echter ten allen tijde deze gegevens opvragen, zodat er geen permanente kennis meer nodig is van alle applicaties. Men kan zich tevens een scenario inbeelden waarbij elke node lokaal maar kennis heeft van de populairdere applicaties die aangevraagd worden, waarna informatie omtrent de minder populaire applicaties kan opgevraagd worden uit de Application Control Map.

Service Image Repository De Service Image Repository is een component die een database bevat met daarin images van verscheidene services, dewelke behoren tot applicaties die gebruikers kunnen aanvragen. Er wordt echter zoveel mogelijk geprobeerd om te werken met de huidige bezetting van alle nodes, zodat er zo weinig mogelijk verplaatsingen moeten gebeuren van service-instanties. In deze thesis wordt echter statisch bepaald welke services kunnen uitgevoerd worden op elke node. Elke node heeft met andere woorden dus maar een beperkt aantal services die hierop uitgevoerd kunnen worden, waardoor het vaak onwaarschijnlijk is dat één enkele node een volledige applicatie kan uitvoeren. In de meeste situaties is er dus een communicatie vereist tussen de nodes waarop verschillende services uitgevoerd worden, die allen behoren tot eenzelfde applicatie.

54

4.4


Gebruiksscenario: behandelen van nieuwe aanvragen

In deze sectie wordt het gebruiksscenario (Engels: use-case) voorgesteld voor het behandelen van nieuwe aanvragen voor applicaties door gebruikers. Dit gebruiksscenario wordt voorgesteld met behulp van een sequentiediagram in figuur 4.5.. Service Interface

Sequentiediagrammen zijn illustratieve oplossingstechnieken die behoren tot de Unified Modeling

Language (UML) [46], en die weergeven hoe een bepaalde functionaliteit kan worden gerealiseerd «component» Management Server

«component» Cloud Service Manager

door samenwerking van verscheidene componenten, objecten genaamd.«component» UML is een gestandaar«component» Server Manager

Server Manager

Service Interface

diseerde taal die gebruikt wordt voor het modelleren van verschillende types van informatie, «component» «component» Hierarchy Controller

Hierarchical Cluster Selector

door gebruik te maken van een aantal soorten diagrammen. Kenmerkend voor UML is dat de Management Interface «component» Cloud Environment

«component»

Service Image Repository modellen een grafische weergave zijn van bepaalde aspecten van een informatiesysteem. «component» Placement Controller «component» Application Control Map

«component»

Placement Algorithm Binnen een sequentiediagram worden de betrokken objecten weergegeven binnen een rechthoek, «component» en daaronder wordt de levenslijn van het object getoond. Indien het object niet actief meewerkt Node Controller Request Interface om een bepaalde functionaliteit te verwezenlijken wordt er gewoon een stippellijn getekend. Als Service Interface This is a text element to place text anywhere.

het object echter wel meewerkt wordt een rechthoek over deze lijn getekend, die aanduidt dat het «component» object actief is. Het uitwisselen van informatie tussen de verschillende«component» objecten wordt meestal Application Request Router Client

Service Interface

afgehandeld onder de vorm van een methode oproep, en wordt weergegeven in het sequentiediaWeb Interface

gram door middel van een pijl tussen de communicerende objecten. Een sequentiediagram heeft typisch een bepaalde tijdsvolgorde die de functionaliteit van een systeem duidelijk maakt. Client

Application Request Router

Aanvragen voor applicaties

Cloud Service Manager

Doorsturen van deze aanvragen

Management Server

Execution Server

Hierarchical Cluster Selector kiest strategisch Management Server

Eigenschappen applicaties halen uit Application Control Map

Vraag huidige plaatsing & capaciteiten op Doorsturen informatie

Verzamel informatie via Node Sensor Stuur huidige plaatsing & capaciteiten op

Bereken oplossing voor het APP

Geef nieuwe plaatsing door aan betrokken child nodes

Voer nieuwe plaatsing uit via Node Effector

Figuur 4.5: Gebruiksscenario: behandelen van nieuwe aanvragen voor applicaties.

4.4. GEBRUIKSSCENARIO: BEHANDELEN VAN NIEUWE AANVRAGEN

55

Het sequentiediagram in figuur 4.5 wordt hieronder kort even verklaard. De trigger om het diagram te starten is wanneer er nieuwe aanvragen binnenkomen van gebruikers voor toegang tot bepaalde applicaties. De daaropvolgende stappen in het diagram zijn dan achtereenvolgens: 1. Alle aanvragen komen binnen bij de Application Request Router. Deze component zal via de Cloud Service Manager, waarin de Hierarchical Cluster Selector wordt uitgevoerd, een geschikte beherende server selecteren om alle aanvragen verder te behandelen. 2. Diezelfde Cloud Service Manager staat ook in voor het ophalen van informatie uit de Application Control Map omtrent de aangevraagde applicaties. Dit betreft het bepalen van welke services horen tot elke aangevraagde applicatie, en de vereiste CPU- en geheugencapaciteiten van de betreffende service-instanties. 3. Vervolgens wordt al deze informatie doorgestuurd naar de gekozen beherende server, die instaat voor het berekenen van een oplossing voor het APP. 4. Deze beherende server zal eerst de huidige plaatsing en CPU- en geheugencapaciteiten van al zijn child-nodes opvragen, met de voorwaarde dat deze uitvoerende servers zijn. 5. De uitvoerende servers zullen de gewenste informatie verzamelen via hun Node Sensor, en terug doorsturen naar de beherende server. 6. Met behulp alle verzamelde informatie kan de beherende server het algoritme uitvoeren die een oplossing berekent voor het APP. 7. De oplossing hiervan, zijnde welke services moeten uitgevoerd worden op elke uitvoerende server, wordt terug doorgestuurd naar alle betrokken servers. Die servers wijzigen vervolgens hun huidige configuratie met behulp van de Node Effector, conform deze nieuwe plaatsing.

Hoofdstuk 5

Algoritmen 5.1

Inleiding

In wat volgt worden de verschillende algoritmen besproken die ontworpen werden om het APP op te lossen. In een eerste fase werd de probleemstelling uit sectie 3.2 met behulp van lineair programmeren ge¨ımplementeerd, waardoor een exacte oplossing voor het APP kan worden bekomen. Vervolgens werden twee meta-heuristieken gebruikt om oplossingen voor het APP te berekenen: zijnde Particle Swarm Optimization [25] en Genetisch Algoritmen (GA) [39]. PSO en GA zijn beiden iteratieve algoritmen die telkens werken met een verzameling van mogelijke oplossingen. In elke iteratie worden nieuwe oplossingen gegenereerd die kenmerken bezitten van de huidige oplossingenverzameling. Hoe dit concreet gebeurt bij beide algoritmen is echter verschillend, wat beide algoritmen interessant maakt om ze te vergelijken. PSO maakt gebruik van een oplossingenruimte waarbij de oplossingen worden voorgesteld als geometrische punten in een wiskundige ruimte. Om elke oplossing te verbeteren wordt bij PSO gebruikt gemaakt van vectoren waarbij de posities en snelheden van andere oplossingen in acht worden genomen. GA daarentegen maken gebruik van een populatie van oplossingen, waarin elke oplossing een bepaald individu voorstelt. Om een nieuwe populatie van individuen te creëren wordt bij het GA gebruik gemaakt van technieken ge¨ınspireerd op de natuurlijke evolutie.

57

58

5.2

HOOFDSTUK 5. ALGORITMEN

Integer Linear Programming (ILP)

Lineair programmeren (LP), ook lineair optimaliseren genoemd, is een wiskundige methode om de best mogelijke uitkomst te vinden van een gegeven model. In zo’n model wordt er altijd gewerkt met een objectieffunctie, en een lijst van randvoorwaarden waaraan voldaan moet worden. Deze randvoorwaarden worden wiskundig uitgedrukt als een aantal lineaire relaties (gelijken/of ongelijkheden), vandaar de naam ‘lineair programmeren’. Een voorbeeld van zo’n objectieffunctie kan zijn om de grootst mogelijke winst te bepalen die een bedrijf kan maken, en dit gegeven een aantal productievoorwaarden, of om de laagste kost te bepalen om een doelstelling te verwezenlijken. Een voorbeeld van een randvoorwaarde die hierbij in acht moeten worden genomen, kan zijn om maximaal het aantal grondstoffen te gebruiken dat een bedrijf in voorraad heeft. Ook mag bijvoorbeeld het benodigd aantal uren voor een gegeven hoeveelheid producten te maken, niet meer bedragen dan het aantal uren dat maar gepresteerd kan worden met de arbeiders van dit bedrijf. Formeel genomen is lineair programmeren dus een techniek om een lineaire objectieffunctie te optimaliseren, die onderhevig is aan een aantal lineaire gelijken/of ongelijkheden. Het aanvaardbare gebied van mogelijke oplossingen is een convex veelvlak, dat ontstaat door de intersectie van de verschillende randvoorwaarden. Algoritmen die steunen op lineair programmeren zullen altijd een extreem punt zoeken in dit veelvlak, dat overeenkomt met de maximale of minimale waarde van de objectieffunctie (in zoverre dit mogelijk is, wanneer er dus geen tegenstrijdige randvoorwaarden zijn bijvoorbeeld). Een ILP verschilt van een LP doordat sommige beslissingsvoorwaarden zich manifesteren als gehele getallen (Engels: integers), wat het te beschouwen probleem moeilijker maakt om op te lossen. Een LP bevindt zich namelijk in de klasse van P-problemen, daar waar een ILP zich in de klasse van NP-problemen bevindt. De oplossing van een LP kan men altijd terugvinden op een van de hoeken van het convex veelvlak, dat wordt gevormd door de intersectie van de verschillende randvoorwaarden. Dit is echter niet het geval bij een ILP, waar de optimale oplossing zich immers kan bevinden binnen dit convex veelvlak. Meer uitleg over P versus NP kan gevonden worden in sectie 2.2.2. Een LP programma kan opgelost worden met behulp van het Simplex algoritme [13], doch dit algoritme is niet meer geschikt voor een ILP mee op te lossen. Een techniek die dit wel kan is bijvoorbeeld het ‘Branch and Bound’ algoritme [29].

5.3. PARTICLE SWARM OPTIMIZATION (PSO)

5.2.1

59

ILP APP algoritme

Een manier om een oplossing te berekenen voor het APP werd in deze thesis onder andere ge¨ımplementeerd onder de vorm van lineair programmeren. De verschillende objectieffuncties en randvoorwaarden kan men uitgebreid terugvinden in sectie 3.2. Kort samengevat werden vijf criteria sequentieel geoptimaliseerd, waarbij de optimale oplossing voor de objectieffunctie bij elk criterium zich manifesteerde als een bijkomende randvoorwaarde in een volgend optimalisatiecriterium. Deze vijf criteria waren achtereenvolgens: 1. Maximaliseren van het aantal geaccepteerde aanvragen. 2. Maximaliseren van de communicatie-voldoening voor elke workflow. 3. Minimaliseren van het aantal gebruikte nodes bij de plaatsing. 4. Minimaliseren van het aantal verplaatsingen tussen twee iteraties. 5. Maximaliseren van de service workflow efficiëntie. Hoe deze criteria werden geformuleerd als een stelsel van objectieffuncties en lineaire gelijken/of ongelijkheden, kan men zoals eerder aangehaald terugvinden in sectie 3.2.

5.2.2

Implementatie

Bovenstaande optimalisatiecriteria werden allen geformuleerd in de programmeertaal Java met behulp van de CPLEX-bibliotheek [23]. CPLEX is een software pakket dat gebruikt kan worden voor optimalisatie doeleinden, en gebruik maakt van een modellering laag genaamd Concert. Daardoor is CPLEX geschikt om gebruikt te worden door verschillende programmeertalen, zoals C++, C#, Java en Python. Het is mogelijk om met behulp van CPLEX exacte oplossingen uit te rekenen voor LP en ILP problemen, doordat CPLEX inwendig zowel het Simplex algoritme als het ‘Branch and Bound’ algoritme kan gebruiken.

5.3

Particle Swarm Optimization (PSO)

Particle Swarm Optimization (PSO) [25] is een meta-heuristiek die ge¨ınspireerd is op het collectief gedrag van een groep vogels of een school vissen. Het valt daarom onder de noemer van heuristieken die gebaseerd zijn op zwermintelligentie. Een groot aantal vogels of vissen bewegen

60


zich altijd synchroon in groep, kunnen plotseling veranderen van richting maar hergroeperen zich altijd terug zonder problemen. Elk individu steunt op de ervaring van zichzelf en die van anderen in de zwerm. Een andere meta-heuristiek die gebruik maakt van zwermintelligentie is Ant Colony Optimization (ACO) [14], gebaseerd op het gedrag van mieren die een pad zoeken tussen hun kolonie en een bron van voedsel.

5.3.1

PSO algemeen

Een eenvoudig PSO algoritme wordt voorgesteld in algoritme 1. De corresponderende uitleg kan men onder het algoritme terugvinden. 1

genereer een populatie P van deeltjes

2

for elk deeltje p ∈ P do

3

initialiseer dit deeltje

4

end

5

for een gegeven aantal iteraties && stopcriteria is niet van toepassing do

6


7

evalueer de kwaliteit van het huidig deeltje a.d.h.v. een gegeven objectieffunctie

8

indien van toepassing, update de globale en/of lokale beste positie

9

bereken een nieuwe snelheidsvector voor het huidig deeltje bereken een nieuwe positie voor het huidig deeltje, a.d.h.v. de vorige positie van

10

het deeltje en de nieuwe snelheidsvector 11 12

end end Algoritme 1: Een eenvoudig PSO algoritme.

PSO is een meta-heuristiek die een probleem optimaliseert door in elke iteratie een nieuwe populatie van oplossingen te genereren, die eigenschappen bezitten van de oplossingen in de huidige polulatie. Deze kandidaat-oplossingen worden binnen PSO de deeltjes (particles) genoemd, en worden door wiskundige formules gedwongen om rond te bewegen in de mogelijke oplossingenruimte. De beweging van elk deeltje gebeurt aan de hand van zijn huidige positie en de snelheidsvector van dit deeltje. Gedurende elke iteratie wordt de snelheidsvector van elk deeltje aangepast aan de hand van de kwaliteit van dit deeltje, waardoor elk deeltje een nieuwe positie zal innemen binnen de oplossingenruimte.


61

Om de kwaliteit van zo’n oplossing te evalueren, wordt er gesteund op een vooraf bepaalde objectieffunctie. Elk deeltje houdt zijn eigen beste positie bij die hij tijdens de verschillende iteraties al is tegengekomen, en de volledige zwerm heeft ook kennis van de tot hiertoe globale beste positie. Het berekenen van een nieuwe snelheidsvector voor elk deeltje gebeurt aan de hand van de lokale beste positie van het betreffende deeltje, en de tot hiertoe globale beste positie van de volledige zwerm. Zo zal elk deeltje zijn lokale oplossingenruimte verkennen, en toch aandacht besteden aan het bewegen naar de tot hiertoe globale beste positie.

5.3.2

PSO APP algoritme

Voorstelling van de deeltjes Bij het PSO algoritme zal elk deeltje een kandidaat-oplossing vertegenwoordigen van het APP. Zo’n oplossing bestaat uit een 3-dimensionale array van elementen, waarin men achtereenvolgens de volgende dimensies terug kan vinden. Deze werden ook al aangehaald in sectie 3.1. 1. Nummer van de applicatie (welke soort applicatie). 2. Nummer van de aanvraag voor deze applicatie. 3. Nummer van de services behorende tot deze applicatie. De waarde op elk punt van deze 3-dimensionale array is het node-nummer waar de betreffende service wordt op uitgevoerd, behorende tot een aanvraag voor een applicatie. Beschouwen we ter illustratie een applicatie die bestaat uit een aantal communicerende services, en een zekere aanvraag voor deze applicatie. Binnen deze meerdimensionale array kan men een vector terugvinden waarin alle mogelijke services vertegenwoordigd zijn voor de aanvraag van deze applicatie, zoals weergegeven in figuur 5.1.

Applicatie a, aanvraag nr. r

s0

s1

s2

s3

s4

s5

s6

2

4

0

-1

2

0

7

Service nr. 1 wordt uitgevoerd op node nr. 4

Services nr. 3 en 6 worden niet uitgevoerd

Figuur 5.1: PSO: Voorstelling van een deeltje.

62


Op elke positie in deze vector van services vindt men een discrete waarde terug, die het nummer van de node zal aangeven waarop deze service uitgevoerd wordt. Indien een bepaalde service niet behoort tot deze applicatie, dan mag de waarde elk getal zijn dat geen geldig nummer is van een node. Concreet betekent dit dat als er bijvoorbeeld 5 nodes zijn, de geldige waarden van node-nummers {0, 1, 2, 3, 4} zijn. Om aan te duiden dat een service niet wordt uitgevoerd op een node, kan het bijhorende node-nummer bijvoorbeeld -1 of 7 zijn.

Initialisatie van de zwerm In algoritme 2 wordt beschreven hoe de initialisatie van de zwerm van deeltjes gebeurt. Hierbij zal elk deeltje een mogelijke oplossing voorstellen voor het APP. 1

genereer een zwerm P van deeltjes

2


3 4

for elke applicatie a ∈ A, elke aanvraag r ∈ Ra en elke service s ∈ S do if service s ∈ / Sa then initialiseer positie xa,r p,s ← (−1)

5 6

else

7

blijfVerderZoeken ← waar

8

while blijfVerderZoeken do initialiseer positie xa,r p,s ← willekeurig geheel getal ∈ [0, #nodes − 1]

9

if gekozen node is geschikt om service s uit te voeren then

10

blijfVerderZoeken ← onwaar

11 12

end

13

if gegeven aantal keer geprobeerd te initialiseren then

14

initialiseer positie xa,r p,s ← (−1)

15

blijfVerderZoeken ← onwaar end

16

end

17 18 19 20

end end end Algoritme 2: Pseudocode van het PSO APP algoritme: initialiseren van de zwerm.


63

In regel 10 wordt er gecontroleerd of de gekozen node effectief ook geschikt is om service s uit te voeren. Het kan immers gebeuren dat het plaatsen van service s op deze node ervoor zorgt dat de eindige CPU- en/of geheugencapaciteit van deze node overschreden wordt. Ook is het mogelijk dat de gekozen node niet beschikt over een instantie van de betreffende service. In beide gevallen is de gekozen oplossing dus niet geschikt om toegepast te worden in werkelijkheid, waardoor er verder moet gezocht worden naar een geschikte node voor deze service. In regel 13 wordt een stopcriterium ingevoerd om het zoeken tijdelijk af te breken. Indien er geen gepaste node kan gevonden worden voor de betreffende service, dan wordt deze service niet uitgevoerd in de resulterende plaatsing. In de huidige implementatie wordt er afgebroken na 50 keer geprobeerd te hebben om een geschikte node te vinden, wat empirisch bepaald werd.

Netwerk-bewuste plaatsing: het Minimum-Cost Flow Problem In sectie 3.2.5 werd kort al even verwezen naar het Minimum-Cost Flow Problem (MCFP). De opdracht van het MCFP is om de goedkoopst mogelijke weg doorheen het netwerk te zoeken om een hoeveelheid flow te versturen van een bron naar een bestemming. Hierbij zal de kost k per hoeveelheid flow die gestuurd wordt over elke communicatielink een rol spelen, alsmede de eindige capaciteit c van deze link. Indien men beide parameters heeft, kan men een oplossing berekenen voor het MCFP met behulp van gekende algoritmen. Hierbij zal men, indien mogelijk, zoveel mogelijk van de aangevraagde hoeveelheid flow proberen te versturen van de bron naar de bestemming, en dit op de goedkoopst mogelijke manier. In figuur 5.2 wordt een voorbeeld gegeven van het MCFP, gevolgd door een korte uitleg van hoe een oplossing kan bekomen worden.

i

ki,j / ci,j

j

bron: 0 bestemming: 5 flowvereist = 3 flowvoldaan = 3 kosttotaal

= 19

flow1 = 2 kost1 = flow1 x (3 + 1 + 2) = 12 3/4

1

1/3

3

2/2

0 2/3

5 2

3/5

4

2/1

flow2 = 1 kost2 = flow2 x (2 + 3 + 2) = 7

Figuur 5.2: Het Minimum-Cost Flow Problem (MCFP).

64


Deze oplossingsmethode uit figuur 5.2 staat gekend als het Successive Shortest Path (SSP) algoritme [16], en gebeurt als volgt. In het betreffende voorbeeld dienen er 3 eenheden flow verstuurd te worden van bron node0 naar bestemming node5 . Eerst zal het pad bovenaan worden gekozen, omdat dit het kortste pad is inzake kosten. De som van de kosten per eenheid flow dat men kan sturen is immers 6 (zijnde 3 + 1 + 2), dit in tegenstelling tot het pad onderaan waar de kost 7 is (zijnde 2 + 3 + 2). Op het bovenste pad kan men echter maar 2 eenheden flow sturen, aangezien de capaciteit van de link van node3 naar node5 maar 2 is en deze een bottleneck vormt. Vervolgens zoekt men het volgende kortste pad inzake kosten, zijnde het pad onderaan met kost 7 per eenheid flow, en verstuurt men daar de resterende hoeveelheid flow. In totaal is er voldaan aan de vereiste flow van 3 hoeveelheden, en dit op de goedkoopste manier. Bij het APP volgen we een analoge formulering van het MCFP. Hierbij zal elk paar services s1 en s2 behorende tot een aanvraag voor een applicatie een gegeven communicatie-eis hebben, waardoor er een workflow w ontstaat tussen deze services. De mate waarin beide services communiceren met elkaar wordt opgelegd door de communicatiematrix C, waarbij de continue variabele Cs1 ,s2 aangeeft hoeveel bandbreedte (in Mbit/s) er nodig is om de communicatie tussen deze services te realiseren. De kost inzake communicatie tussen twee nodes wordt bepaald door de hopcountmatrix H, waarbij de discrete variabele Hn1 ,n2 aangeeft hoeveel tussenliggende apparatuur (routers, nodes) er minstens aanwezig is tussen elk paar nodes n1 en n2 . Elke workflow w krijgt een individueel percentage zw toegekend van zijn totale eis inzake communicatie, dat aldus aangeeft hoeveel procent van de totale eis er kon worden voldaan. Indien dit percentage lager is dan 80%, dan zal de aanvraag voor deze applicatie worden verworpen. Initieel worden alle aanvragen overlopen en wordt er op deze manier een communicatie van 80% gegarandeerd voor elke workflow. In een finale versie, als het maximale aantal aanvragen dat kan geplaatst worden bepaald is, wordt de communicatie-voldoening van elke workflow verhoogd tot zover de bandbreedtes van de communicatielinks in het netwerk dit toelaten. Een manier om het MCFP op te lossen is door gebruik te maken van lineair programmeren, zoals ook werd gedaan in sectie 3.2.5. Bij de implementatie van het PSO- en GA-algoritme werd er echter gebruik gemaakt van het SSP algoritme. Identieke oplossingen kunnen ook gevonden worden door te steunen op andere algoritmen uit de literatuur, zoals er onder andere zijn: cost scaling, cycle canceling of minimum mean cycle canceling [21]. De keuze om gebruik te maken van het SSP algoritme was omdat de auteur de meeste logica zag in dit algoritme.


65

Het SSP algoritme wordt beschreven in algoritme 3. Beschouwen we daartoe eerst een graaf G met een bepaalde bron s en een zekere bestemming t. Elke tak e in deze graaf heeft een eindige capaciteit ce , en een zekere kost ke met elke hoeveelheid flow die over deze tak wordt gestuurd. De flow die van s naar t gestuurd dient te worden over het netwerk noemen we d, en is niets anders dan de communicatie van twee services die tot dezelfde aanvraag voor een zekere applicatie behoren. 1

initialiseer totaleKost ← 0

2

initialiseer teRealiserenF low ← d

3

initialiseer f lowLimiet ← 0.2 × d

4

while graaf G bevat een pad van s naar t && teRealiserenF low > f lowLimiet do

5

zoek het kortste pad (op basis van kosten) van s naar t m.b.v. Dijkstra

6

tempF low ← maximale flow dat je over dit pad kan sturen

7

tempF low ← min(tempF low, teRealiserenF low − f lowLimiet)

8

for elke tak e in de graaf G die behoort tot dit kortste pad do ce ← ce − tempF low

9

totaleKost ← totaleKost + tempF low × ke

10 11

end

12

teRealiserenF low ← teRealiserenF low − tempF low

13

end

14

gerealiseerdeFlow = (d - teRealiserenFlow)

15

if (gerealiseerdeFlow / d) geq 0.8 then

16 17

sla de nieuwe capaciteitsmatrix tijdelijk op else

18

negeer de capaciteitsmatrix uit de vorige While-lus

19

de aanvraag voor deze applicatie kan niet worden voldaan

20

end Algoritme 3: Pseudocode van het SSP algoritme - initieel.

Het algoritme werkt dus al volgt: initieel zoekt men het goedkoopste pad van de bron s naar de bestemming t, in zoverre dit nog nodig is om de communicatie-voldoening van 80% te kunnen garanderen. Vervolgens zal men alle capaciteiten in het netwerk aanpassen die deel uitmaken van het gevonden pad, aangezien er een zekere hoeveelheid flow over gestuurd is. Na deze operatie wordt er terug verder gezocht naar een goedkoopste pad, en dit tot zolang het nodig is om de

66


80% eis te kunnen garanderen. Indien alle workflows van een zekere applicatie kunnen geplaatst worden, wordt de capaciteitsmatrix echt definitief gemaakt. Indien minstens één ervan niet de communicatie-voldoening 80% kan garanderen, wordt de capaciteitsmatrix ook niet aangepast. In een finaal stadium zal het algoritme een tweede keer uitgevoerd worden. Dit gebeurt wanneer er bepaald is hoeveel aanvragen voor applicaties er kunnen aanvaard worden, na het garanderen van 80% voldoening voor elke workflow. In deze finale versie van het algoritme wordt er geprobeerd om alle bestaande workflow-voldoeningen te verhogen, in zoverre er daartoe bandbreedte beschikbaar is in het netwerk. De enige parameters die aangepast moeten worden in algoritme 3 is om teRealiserenF low te initialiseren op 0.2 × d, en om f lowLimiet in te stellen op 0. Het SSP algoritme werd ge¨ımplementeerd met behulp van de JGraphT bibliotheek [1] in Java. Deze bibliotheek werd gebruikt in stap 5 in algoritme 3 om het kortste pad te berekenen tussen twee punten in een netwerk.

Evaluatie van de kwaliteit van elke deeltje Aan elk deeltje in de zwerm wordt een zekere kwaliteit toegekend, die algemeen beschouwd de mate voorstelt waarmee aan een gegeven objectieffunctie is voldaan. Bij het APP zal dit een combinatie zijn van hoeveel aanvragen er konden geplaatst worden, hoeveel servers er daarbij gebruikt werden, en dergelijke. Het toekennen van kwaliteiten aan deeltjes dient te gebeuren zodat de volledige zwerm kan worden voortgestuwd door deeltjes met een hoge kwaliteit. Indien bepaalde deeltjes echter een oplossing voorstellen die een of meerdere randvoorwaarden schenden, dan kunnen zulke deeltjes niet meer als representatief worden beschouwd om het gedrag van de zwerm te be¨ınvloeden. In zo’n gevallen kan men ervoor kiezen om een straffunctie te introduceren die zal inwerken op de objectieffunctie, of om de kwaliteit van zulke deeltjes gelijk te stellen aan nul. Het voordeel van een aanpak met een straffunctie is dat ontoelaatbare gebieden in de oplossingenruimte in eerste instantie toch nog mogen ingenomen worden. Dit in de hoop dat er uiteindelijk toch een gebied wordt gevonden met toelaatbare oplossingen met hogere kwaliteit. De randvoorwaarden die kunnen worden geschonden bij het APP zijn de volgende, en kwamen ook al aan bod kwamen in sectie 3.1. • Er worden meer aanvragen behandeld dan er binnengekomen zijn. • Er wordt meer CPU-capaciteit toegekend dan er aangevraagd werd.


67

• De geheugen- of CPU-capaciteit van een node wordt overschreden. • De bandbreedte van een communicatielink wordt overschreden. • Er worden services geplaatst op een node, die deze service niet ondersteunt. • Er worden services geplaatst op een node, die niet tot een applicatie behoren. Het dient echter opgemerkt te worden dat het niet altijd evident is om een goede straffunctie te kiezen. Er kan bijvoorbeeld een situatie ontstaan waarbij een oplossing die wel randvoorwaarden schendt, toch nog een hogere kwaliteit heeft dan een oplossing die geen randvoorwaarden schendt. Om deze reden is er gekozen om in dit werk de kwaliteit van deeltjes die een of meerdere randvoorwaarden (zoals hierboven beschreven) hebben geschonden, op nul te stellen. Concreet genomen is de objectieffunctie die wordt toegepast de volgende: obj = (CV F )2 × RV F aantalGebruikteN odes × 1− |N | + 1 aantalV erschillen × 1− |N | × |S| + 1

(5.1)

In deze objectieffunctie worden de volgende parameters gebruikt: Gebruikte parameters bij de PSO objectieffunctie Symbool RV F

Beschrijving De verhouding tussen het aantal voldane (geplaatste) aanvragen voor applicaties, en het totaal aantal aanvragen voor applicaties

CV F

De verhouding tussen de totale CPU-capaciteit van de voldane (geplaatste) aanvragen, en de totale benodigde CPU-capaciteit voor alle aanvragen te kunnen plaatsen

aantalGebruikteN odes |N |

Het totaal aantal nodes gebruikt bij een plaatsing Het aantal beschikbare nodes in het netwerk

aantalV erschillen

Het totaal aantal verschillen tussen de nieuwe toekenning van services op nodes, en de huidige toekenning van services op nodes

|S|

Het aantal services waaruit elke applicatie opgebouwd kan zijn Tabel 5.1: Gebruikte parameters bij de PSO objectieffunctie.

De objectieffunctie in formule 5.1 is empirisch bepaald, doordat metingen hebben aangetoond dat deze goede resultaten opleverde. De reden waarom de CV F tot de 2de macht wordt verheven,

68


is omdat de CV F een belangrijkere factor is dan de RV F . Bij cloud providers zoals Google App Engine worden gebruikers immers afgerekend op het aantal CPU-cycles dat ze gebruiken. Omwille van deze reden wordt er in de probleemstelling die in dit werk wordt gehanteerd, gekozen om die aanvragen voor applicaties te aanvaarden die zorgen voor de grootste toekenning van CPU-capaciteit doorheen het netwerk. De toevoeging van +1 in de noemer van beide breuken in formule 5.1 is omdat beide termen in theorie 1 kunnen worden, waarna de volledige objectieffunctie 0 zou worden. Immers, het is mogelijk dat het maximaal aantal beschikbare servers in het netwerk ook daadwerkelijk gebruikt wordt om alle aanvragen te plaatsen. Eveneens kunnen tussen twee opeenvolgende iteraties van het PSO algoritme een maximaal aantal verplaatsingen van instanties zich voordoen, zijnde |N | × |S|. De kans dat dit gebeurt is echter bijzonder klein, gegeven het feit dat we in dit werk ervan uitgaan dat niet elke server elke service-instantie kan uitvoeren.

Aanpassing van de positie van de deeltjes Om het gedrag van een groep vogels of een school vissen te simuleren, worden de posities van de deeltjes in de zwerm iteratief aangepast gedurende de tijd dat het PSO zoekt naar geschikte oplossingen. Gedurende elke iteratie wordt de snelheidsvector van elk deeltje, die zijn volgende positie binnen de oplossingenruimte zal bepalen, aangepast aan de hand van de kwaliteit van dit deeltje. Elk deeltje houdt daartoe zijn persoonlijk beste positie pbest bij die hij tijdens de verschillende iteraties al is tegengekomen, en de volledige zwerm heeft ook kennis van de tot hiertoe globale beste positie gbest. Een variant van deze aanpak kan ontstaan doordat elk deeltje enkel de beste positie in een logische buurt (bepaald aan de hand van de grootte van de zwerm) van deeltjes gaat onthouden. Wanneer men dan de globale versie beschouwt, is deze implementatie niets anders dan een speciaal geval van de lokale versie. Hierbij wordt de best mogelijke positie van een deeltje gezocht in de volledige zwerm van deeltjes. Gedurende elke iteratie zal elk deeltje p ∈ P zijn snelheidsvector vp aanpassen. Hierbij wordt er rekening gehouden met diens huidige snelheidsvector, de persoonlijk beste positie pbest die het deeltje al is tegengekomen, en de globale beste positie gbest die de volledige zwerm al is tegengekomen. Het bepalen van een nieuwe snelheidsvector vp voor elk deeltje p ∈ P, in elke dimensie d (applicatie, aanvraag, service), gebeurt als volgt: vp,d ← vp,d +

c1 × rnd1 (pbestd − xp,d ) + c2 × rnd2 (gbestd − xp,d ) c1 + c2

(5.2)


69

In formule 5.2 zijn de factoren rnd1 en rnd2 twee willekeurige reële getallen die uniform gekozen worden uit het interval {0, 1}, om enige willekeurigheid in de resulterende oplossingen te steken. Dit zorgt ervoor dat er niet steeds dezelfde posities worden bezocht in de mogelijke oplossingenruimte. De factoren c1 en c2 zijn twee gewichtsfactoren die kunnen aangestuurd worden om het zoeken naar nieuwe oplossingen te stuwen in een bepaalde richting. Indien de coëfficiënt c1 groter wordt gekozen dan c2 , dan zullen nieuwe oplossingen eerder gezocht worden rond de persoonlijk beste positie pbest die het deeltje al is tegengekomen. In het omgekeerde geval, waarbij c1 kleiner wordt gekozen dan c2 , zal er eerder gezocht worden naar nieuwe oplossingen rond de globale beste positie gbest die de zwerm al is tegengekomen. Indien er te lage waarden voor deze parameters worden gekozen, dan zullen nieuwe oplossingen altijd gevonden worden in de buurt van de huidige oplossing. Indien er echter te grote waarden worden gekozen voor deze parameters, dan kunnen deeltjes zich makkelijker naar (of zelfs over) optimale oplossingen bewegen [25]. Empirisch bepaald werden de factoren c1 en c2 ingesteld op respectievelijk 2 en 1. Tevens wordt de langere term in formule 5.2 gedeeld door de som van de factoren c1 en c2 . Dit gebeurt om enige controle te hebben over de grootste sprong die een snelheidsvector vp in dimensie d kan maken. Immers, indien rnd1 en rnd2 beiden 1 zouden worden is de grootste term die nog kan overblijven gelijk aan #nodes − 1. Deze treedt op wanneer xp,d gelijk wordt aan 0, en pbestd = gbestd = #nodes − 1. Deze term wordt vervolgens opgesteld bij de oude waarde van vp,d , waardoor een maximale snelheid van #nodes − 1 is bekomen. Op basis van deze nieuwe snelheidsvector vp kan daarna voor elk deeltje een nieuwe positie xp bepaald worden. Deze nieuwe positie stelt wederom een mogelijke oplossing voor van het APP in de oplossingenruimte. Het bepalen van een nieuwe positie xp voor elk deeltje p ∈ P, in elke dimensie d, gebeurt als volgt: xp,d ← xp,d + vp,d

(5.3)

PSO in pseudocode In algoritme 4 wordt het PSO algoritme beschreven. De output van dit algoritme is de 3dimensionale array gbest, die voor elke aanvraag van elke applicatie de toekenning van serviceinstanties op nodes weergeeft.

70


1

genereer een zwerm P van deeltjes

2

initialiseer kwaliteit globale best Qgbest ← 0

3


4

initialiseer kwaliteit lokale best Qpbest ← 0

5

initialiseer positie in elke dimensie xp,d ← willekeurig geheel getal ∈ [0, #nodes − 1]

6

initialiseer snelheidsvector in elke dimensie vp,d ← willekeurig getal ∈ [0, 1]

7

end

8

optimaliseerLoopAPP:

9

initialiseer aantalKeerGeenV erbetering ← 0

10 11

for een gegeven aantal iteraties && stopcriteria is niet van toepassing do for elk deeltje p ∈ P do

12

evalueer de kwaliteit Qp a.d.h.v. een gegeven objectieffunctie

13

if Qp > Qpbest then

14

positie lokale best pbest ← xp

15

kwaliteit lokale best Qpbest ← Qp

16

end

17

if Qp > Qgbest then

18

aantalKeerGeenV erbetering ← 0

19

positie globale best gbest ← xp

20

kwaliteit globale best Qgbest ← Qp else

21 22

aantalKeerGeenV erbetering + +

23

if aantalKeerGeenV erbetering > 2 × |P| then break optimaliseerLoopAPP

24

end

25 26

end

27

update de snelheid vpnieuw op basis van vpoud , pbest en gbest

28

update de positie xnieuw op basis van xoud en vpnieuw p p

29 30

end end Algoritme 4: Pseudocode van het PSO APP algoritme.

5.4. GENETISCHE ALGORITMEN (GA)

5.4

71

Genetische Algoritmen (GA)

Een genetisch algoritme (GA) [39] is een meta-heuristiek om oplossingen te zoeken in een oplossingenruimte door het proces van natuurlijke evolutie na te bootsen. Genetische algoritmen worden vaak gebruikt om oplossingen te genereren voor optimalisatie- en zoekproblemen, en behoren tot de grotere klasse van evolutionaire algoritmen (EA). Zulke algoritmen genereren oplossingen door te steunen op technieken ge¨ınspireerd op natuurlijke evolutie zoals selectie, kruising en mutatie. Andere methoden binnen evolutionaire algoritmen kunnen gevonden worden onder de vorm van genetisch programmeren, evolutionair programmeren of genexpressie programmeren [61].

5.4.1

GA algemeen

Binnen genetische algoritmen wordt, net zoals bij het PSO algoritme, iteratief gewerkt met een verzameling van mogelijke oplossingen. Het GA maakt gebruik van een populatie van oplossingen, waarin elke oplossing een bepaald individu voorstelt. Om een nieuwe populatie van individuen te creëren wordt zoals eerder aangehaald, gebruik gemaakt van technieken ge¨ınspireerd op de natuurlijke evolutie. Een eenvoudig genetisch algoritme wordt voorgesteld in algoritme 5. 1

genereer een populatie P van individuen

2

for elk individu p ∈ P do

3

initialiseer dit individu

4

end

5


6

for elk individu p ∈ P do evalueer de kwaliteit van het individu a.d.h.v. een gegeven objectieffunctie

7 8

end

9

voer selectie uit (kies een nieuwe populatie van individuen)

10

voer kruising uit (maak nieuwe individuen op basis van de bestaande)

11

voer mutatie uit (pas de bestaande individuen aan)

12

end Algoritme 5: Een eenvoudig GA.

72

5.4.2


GA APP algoritme

Voorstelling van de individuen en initialisatie van de populatie Binnen het APP zal elk individu in de populatie een oplossing voorstellen om zoveel mogelijk die aanvragen voor applicaties te aanvaarden die het meest CPU-capaciteit vereisen in het netwerk. Elk individu heeft wederom een aantal eigenschappen, die binnen de genetica chromosomen worden genoemd. De eigenschappen van zo’n individu binnen het APP is de bepaling van op welke node welke service-instantie wordt geplaatst, en dit voor een specifieke aanvraag van een zekere applicatie. Gedurende elke iteratie dat het algoritme zoekt naar oplossingen voor het APP, maakt elk individu kans om aangepast te worden door middel van technieken zoals selectie, kruising of mutatie, dewelke later worden besproken. Het is bij genetische algoritmen vaak gebruikelijk om de individuen als binaire woorden voor te stellen. Dit betekent dat elke oplossing wordt voorgesteld als een combinatie van nullen en enen. Echter, codeertechnieken die bijvoorbeeld gebruik maken van gehele getallen zijn ook mogelijk [58]. De voorstelling van de individuen bij het genetisch algoritme is dezelfde als die bij het PSO algoritme. Een voorbeeld van zo’n voorstelling en de corresponderende verklaring daarbij kan gevonden worden in sectie 5.3.2. Het initialiseren van de populatie van individuen is ook dezelfde als die bij het PSO algoritme, wat kan teruggevonden worden in algoritme 2. Het dient opgemerkt te worden dat elk individu binnen het GA op dezelfde manier wordt voorgesteld en ge¨ınitialiseerd als bij het PSO algoritme, doch dat een individu binnen het GA een andere rol vertolkt dan een deeltje bij PSO. Het PSO algoritme maakt gebruik van een oplossingenruimte waarbij de oplossingen worden voorgesteld als geometrische punten in een wiskundige ruimte. Genetische algoritmen daarentegen werken met een populatie van individuen, waarbij een nieuwe populatie van individuen wordt gecreëerd door gebruik te maken van technieken ge¨ınspireerd op de natuurlijke evolutie.

Evaluatie van de kwaliteit van elke individu Wegens het feit dat de voorstelling van elk individu bij het GA gelijk is aan die bij het PSO algoritme, kan men ook dezelfde objectieffunctie gebruiken om de kwaliteit van elk individu te evalueren. De objectieffunctie, en hoe deze wordt opgesteld, kan men terugvinden in sectie 5.3.2. In diezelfde sectie wordt ook uitgelegd hoe de kwaliteit van de individuen in de populatie wordt bepaald.


73

Aanpassing van de eigenschappen van de individuen Individuen in de populatie zullen doorheen de verschillende iteraties van het genetisch algoritme steeds aangepast worden, doordat het algoritme het proces van natuurlijke evolutie nabootst. Dit gebeurt door te steunen op technieken zoals selectie, kruising en mutatie. In wat volgt worden deze verschillende technieken besproken, en wordt er uitgelegd hoe elke individu in de populatie het proces van evolutie zal meemaken. Selectie: Selectie is het proces dat bepaalt hoe er in elke iteratie een nieuwe populatie van individuen wordt gekozen. Hierbij worden de individuen van deze nieuwe populatie selectief gekozen op basis van de kwaliteit van de individuen in de huidige populatie. De gekozen individuen kunnen later gebruikt worden voor kruising of mutatie op toe te passen. In deze thesis is gebruik gemaakt van fitness-proportionate-selection [22], dewelke als volgt kan worden ge¨ımplementeerd: 1. Eerst zal men de kwaliteit evalueren van elk individu in de huidige populatie, en zal men deze waarden normaliseren. Normaliseren betekent dat de waarde van de kwaliteit van elk individu wordt gedeeld door de som van alle kwaliteiten, zodat de som van de uiteindelijke kwaliteiten gelijk aan één wordt. 2. Daarna zal men de populatie sorteren op basis van de kwaliteit van alle individuen, en dit van hoog naar laag. 3. Vervolgens berekent men de geaccumuleerde kwaliteit van alle individuen. De nieuwe kwaliteit van elk individu wordt gelijk aan de som van de kwaliteit van alle voorgaande individuen, plus de kwaliteit van dit individu. De geaccumuleerde kwaliteit van het laatste individu wordt op deze manier dus gelijk aan één. 4. Hierna genereert men een willekeurig getal g tussen de waarden 0 en 1. 5. Daarna selecteert men het eerste individu wiens geaccumuleerde kwaliteit hoger is dan g. Het selecteren van individuen volgens deze methode wordt ook soms roulette-selection genoemd, en is belangrijk om een goede basis van individuen te vormen waarop er later kruising of mutatie kan gebeuren. Het is ook dit proces dat ervoor zorgt dat de populatie altijd een bepaalde grootte zal aanhouden. Immers, zoals later aangetoond zal worden, gaan operaties zoals kruising ervoor zorgen dat de grootte van de populatie toeneemt. Meestal is de grootte van de populatie echter een parameter die vooraf meegegeven wordt, waardoor er individuen volgens deze methode worden gekozen tot zolang de populatie de grootte van deze parameter aanneemt. Het dient

74


ook opgemerkt te worden dat er bij het selecteren van individuen volgens deze methode enige voorkeur wordt gegeven aan die individuen met een hoge kwaliteit. Echter, er kunnen nog altijd individuen worden gekozen die een vrij lage kwaliteit bezitten. Dit is een belangrijk gegeven aangezien zulke individuen wegens latere operaties erop, mogelijk er nog altijd toe kunnen leiden dat er een zeer geschikte eindoplossing wordt gevonden. Kruising: Bij genetische algoritmen is kruising een operator die gebruikt wordt om de individuen afzonderlijk aan te passen. Het steunt op technieken die gebruikt worden in de natuurlijke voortplanting en de biologische kruising. Bij kruising worden er altijd twee ‘ouder’-oplossingen gekozen volgens het bovenvermelde proces van selectie, waaruit er vervolgens twee ‘kind’-oplossingen zullen voorkomen die deel kunnen uitmaken van een volgende generatie. Het proces van kruising kan op verschillende manieren ge¨ımplementeerd worden. In deze thesis is er gekozen om één-punt kruising te gebruiken. Met de voorstelling van de individuen die we in dit werk hanteren, kunnen we deze één-punt kruising operator voorstellen zoals in figuur 5.3.

Applicatie a, aanvraag nr. r ouder-deeltje nr. 1

Applicatie a, aanvraag nr. r ouder-deeltje nr. 2

s0

s1

s2

s3

s4

s5

s6

2

4

0

-1

2

0

7

s0

s1

s2

s3

s4

s5

s6

-1

5

0

2

3

0

5

Kruisingspunt Applicatie a, aanvraag nr. r kind-deeltje nr. 1

Applicatie a, aanvraag nr. r kind-deeltje nr. 2

s0

s1

s2

s3

s4

s5

s6

2

4

0

2

3

0

5

s0

s1

s2

s3

s4

s5

s6

-1

5

0

-1

2

0

7

Figuur 5.3: GA: Voorstelling van de één-punt kruising.

s0

s1

s2

s3

Het genereren van twee zulke ‘kind’-oplossingen kan als volgt worden ge¨ımplementeerd: voor de mutatie

2

4

0

-1

1. Kies twee ‘ouder’-individuen volgens het bovenvermelde proces van selectie.

s0

s1

s2

s3

2

-1

0

-1



2. Kies een willekeurig punt van waar de kruising van beide ouders zal gebeuren. na de mutatie

3. Beide individuen zullen vanaf dit punt de oplossing van het andere individu overnemen.


75

Het aantal nieuwe individuen dat gegenereerd wordt door middel van kruising wordt vooraf bepaald door een instelbare parameter, de kruisingsparameter genaamd. Deze parameter wordt in deze thesis ingesteld op 80%, wat empirisch bepaald is door middel van verscheidene metingen. Dit betekent dat 80% van de ingestelde grootte van de populatie aan individuen (ook een instelbare parameter) moet worden bijgemaakt door middel van kruising. Andere vormen van kruising zijn twee-punts kruising, waarbij de oplossingen tussen de kruisingspunten worden gewisseld, of uniforme kruising, waarbij elk element van een individu kans maakt om het overeenkomstige element in het andere individu over te nemen. In deze thesis is er gekozen om één-punt kruising te gebruiken, aangezien deze een relatief simpele operator is ten opzichte van meer-punts kruising. Het dient echter opgemerkt te worden dat andere vormen van kruising niet ge¨ımplementeerd werden. Mutatie: Mutatie is een genetische operator die ervoor zorgt dat er genoeg genetische diversiteit ontstaat tussen twee opeenvolgende generaties van individuen. Het is een proces dat analoog is met de

s0

s1

s2

s3

s4

s5

s6

licatie a, aanvraag nr. r biologische mutatie, waarbij elk individu zich afzonderlijk kan aanpassen en evolueren. Bij het 2 4 0 -1 2 0 7 er-deeltje nr. 1 toepassen van mutatie kan elk individu zich minimaal aanpassen, of ook net heel veel waardoor

svolledig s2 sander s4 individu s5 s6 ontstaat. Mutatie laat het genetisch algoritme toe om volledig er seen 0 1 3

licatie a, aanvraag nr. r -1 5oplossingen 0 2 te 3 genereren, 0 5 nieuwe in plaats van telkens oplossingen te combineren om tot een er-deeltje nr. 2

resultaat te komen (zoals bij kruising gebeurt). Het toepassen van mutatie op elk element van

Kruisingspunt

een individu gebeurt met een vooraf ingestelde probabiliteit, de mutatieparameter genaamd.

s0

s1

s2

s3

s4

s5

s6

Deze parameter dient een lage waarde toegekend te worden, omdat het algoritme anders uit zal

licatie a, aanvraag nr. r 2 4 0 2 3 0 5 -deeltje nr. 1 draaien op een willekeurige zoektocht naar oplossingen. In deze thesis is er 10% gekozen voor de

s0 s1 s2 s3 wat s4 empirisch s5 s6 mutatieparameter, bepaald werd door verscheidene metingen. Dit betekent dat

licatie a, aanvraag nr. r elk-1element 5 0van-1een 2individu 0 7 uit de huidige populatie met een probabiliteit van 10% gekozen d-deeltje nr. 2

kan worden om te muteren. Met de voorstelling van individuen die we in dit werk hanteren kan de mutatie van een individu gebeuren zoals voorgesteld in figuur 5.4.

s0

s1

s2

s3

s4

s5

s6

Applicatie a, aanvraag nr. r voor de mutatie

2

4

0

-1

2

0

7

Applicatie a, aanvraag nr. r na de mutatie

2

-1

0

-1

2

0

3

Figuur 5.4: GA: Voorstelling van de mutatie van een individu.

76


Bij de nieuwe gemuteerde oplossing van de plaatsing van aanvraag nummer r voor applicatie a zal service s1 nu niet meer geplaatst worden (het node-nummer is immers -1 geworden), en zal service s6 nu wel geplaatst worden op node 3. Het proces van mutatie kan dan als volgt worden ge¨ımplementeerd: 1. Overloop elk individu in de huidige populatie. 2. Overloop elk mogelijk element (applicatie, aanvraag, service) van dit individu. 3. Indien de betreffende service behoort tot de aangevraagde applicatie, beschouw dit element voor mutatie op toe te passen. 4. Daartoe wordt vervolgens een willekeurig continu getal g gegenereerd ∈ [0, 1]. 5. Indien g < mutatieparameter, kies een nieuwe node voor dit element ∈ [0, #nodes − 1].


77

GA in pseudocode In algoritme 6 wordt het genetisch algoritme beschreven dat in deze thesis wordt gebruikt. De output van dit algoritme is de 3-dimensionale array gbest, die voor elke aanvraag van elke applicatie de toekenning van service-instanties op nodes weergeeft. 1

genereer een populatie P van individuen

2

initialiseer kwaliteit globale best Qgbest ← 0

3

for elk individu p ∈ P do

4

initialiseer individu in elke dimensie xp,d ← willekeurig geheel getal ∈ [0, #nodes − 1]

5

end

6

optimaliseerLoopAPP:

7

initialiseer aantalKeerGeenV erbetering ← 0

8


9

for elk individu p ∈ P 0 do

10

evalueer de kwaliteit Qp a.d.h.v. een gegeven objectieffunctie

11

if Qp > Qgbest then

12

aantalKeerGeenV erbetering ← 0

13

individu globale best gbest ← xp

14

kwaliteit globale best Qgbest ← Qp else

15 16

aantalKeerGeenV erbetering + +

17

if aantalKeerGeenV erbetering > 2 × |P| then break optimaliseerLoopAPP

18

end

19 20

end

21

voer selectie uit (kies een nieuwe populatie P uit P 0 , reduceer dus ook |P 0 | tot |P|)

22

maak de tijdelijke populatie P 0 ← P

23

voer één-punt kruising uit en voeg alle kinderen toe aan P 0

24

voer mutatie uit in P 0

25 26

end end Algoritme 6: Pseudocode van het GA APP algoritme.

Hoofdstuk 6

Evaluatie 6.1

Inleiding

In dit hoofdstuk worden de resultaten vergeleken tussen de verschillende ge¨ımplementeerde algoritmen. In eerste instantie wordt een kleine testopstelling beschouwd, waarin het ILP algoritme wordt vergeleken met de ontworpen PSO- en GA-algoritmen. Omdat het APP beschouwd in dit werk NP-hard is [55, 48], zorgt dit ervoor dat het vinden van een exacte oplossing zeer tijdsintensief is en amper schaalbaar wat betreft het aantal aanvragen, applicaties en resources. De uitvoeringstijd van het ILP algoritme zal daardoor exponentieel toenemen met de grootte van de testopstelling, waardoor deze oplossingsmethode niet meer bruikbaar is voor realistische doeleinden. Bij het beschouwen van een grotere testopstelling zal daarom enkel nog een vergelijking worden gemaakt tussen de ontworpen PSO- en GA-algoritmen. Alle metingen in dit werk werden uitgevoerd met behulp van de STEVIN Supercomputer Infrastructuur aan de Universiteit Gent, gefinancierd door de Universiteit Gent, het Vlaams Supercomputer Centrum (VSC), de Herculesstichting en de Vlaamse Overheid - afdeling EWI.

6.2 6.2.1

Vergelijkende studie tussen ILP, PSO en GA Testopstelling

De volgende algemene parameters werden gebruikt bij de vergelijkende studie tussen het ILP algoritme met de ontworpen PSO- en GA-algoritmen:

79

80

HOOFDSTUK 6. EVALUATIE

• Aantal iteraties: 100 In principe werden er 103 metingen uitgevoerd, doch werden de eerste 3 metingen genegeerd wegens het opstarten van bepaalde bibliotheken (meer bepaald CPLEX en JGraphT). • Aantal applicaties: 3 • Aantal services waaruit applicaties opgebouwd zijn: 4 • Kans dat een service behoort tot een applicatie: 60% (uniforme distributie) • CPU-vereiste van een service: willekeurig element ∈ {0.50, 0.60, 0.70, 0.80, 0.90, 1.00} GHz Het kiezen van een willekeurig element uit deze verzameling, en tevens ook alle andere die hieronder worden beschouwd, werd altijd volgens een uniforme distributie gedaan. • Geheugenvereiste van een service: willekeurig element ∈ {0.50, 0.70, 0.90, 1.10, 1.30, 1.50} GB • Aantal management-servers die elke management-server beheert op de bovenste lagen: 2 • Aantal executie-servers die elke management-server beheert op de onderste laag: 2 Resulterend aantal executie-servers in het netwerk: 2 × 2 × 2 = 8, zie ook figuur 6.1 • CPU-capaciteit van een executie-server: willekeurig element ∈ {9, 12, 15, 18, 21} GHz • Geheugencapaciteit van een executie-server: willekeurig element ∈ {6, 8, 10, 12, 14} GB • Communicatievereiste tussen elk paar services: willekeurig getal ∈ [0.02, 0.04] Mbit/s Hierdoor zal de communicatie-eis tussen services geen beperking vormen op de plaatsing van applicaties, waardoor een betere vergelijking kan bekomen worden tussen alle algoritmen. • Hop count tussen elk paar executie-server: willekeurig geheel getal ∈ [1, 10] • Bandbreedte tussen elk paar executie-servers: willekeurig getal ∈ [6, 14] Mbit/s overschot aanvragen

Managementservers

overschot aanvragen

…

…

…

Executieservers

Figuur 6.1: Logische voorstelling van de hiërarchische boomstructuur bij de vergelijkende studie tussen het ILP algoritme met de ontworpen PSO- en GA-algoritmen.

6.2. VERGELIJKENDE STUDIE TUSSEN ILP, PSO EN GA

81

Naast deze algemene parameters werden er nog specifiekere parameters gebruikt bij de ontworpen PSO- en GA-algoritmen. Deze parameters zijn de volgende, en werden empirisch bepaald bij de implementatie van de betreffende algoritmen. • PSO: – Maximaal aantal iteraties van het algoritme: 20 – Aantal beschouwde deeltjes gedurende elke iteratie: 10 – Lokale gewichtsfactor c1 : 2 – Globale gewichtsfactor c2 : 1 De instellingen voor beide gewichtsfactoren impliceert dat nieuwe oplossingen eerder zullen gezocht worden rond de best gekende positie van elk deeltje, in plaats van rond de globale best gekende positie van de zwerm. • GA: – Maximaal aantal iteraties van het algoritme: 20 – Aantal beschouwde individuen gedurende elke iteratie: 10 – Kruisingsparameter: 80% Deze parameter impliceert dat 80% van de ingestelde grootte van de populatie aan individuen moeten worden bijgemaakt door middel van kruising. – Mutatieparameter: 10% (uniforme distributie) Deze parameter impliceert dat elk element van een individu uit de populatie, die deel uitmaakt van een applicatie, met een probabiliteit van 10% wordt gekozen voor mutatie.

6.2.2

Bepaling van het aantal aanvragen per applicatie

Bij de vergelijkende studie tussen alle algoritmen werd een dynamische situatie beschouwd wat betreft het aantal aanvragen voor applicaties. Gedurende elke iteratie worden er nieuwe CPUen geheugencapaciteiten gekozen voor alle nodes, en wordt er een nieuwe netwerkstructuur berekend. Vervolgens wordt een variabel aantal aanvragen per applicatie beschouwd, zodanig dat een zekere bezetting van dit netwerk wordt bekomen op vlak van CPU-capaciteit. We beschouwen daartoe eerst de CPU Load Factor (CLF), die de verhouding weergeeft tussen de totale aangevraagde en beschikbare CPU-capaciteit in het netwerk. Enkele van de gebruikte symbolen kunnen ook teruggevonden worden in sectie 3.1. P P a∈A Da × s∈S Ia,s × ωs P CLF = n∈N Ωn

(6.1)

82


Bij de berekening van de CLF wordt er gesommeerd over alle applicaties a ∈ A, en wordt het totaal aantal aanvragen Da per applicatie beschouwd. Vervolgens worden ook alle services s ∈ S beschouwd die tot deze applicatie a behoren, dewelke kunnen gevonden worden uit de instantiematrix I. Een waarde Ia,s = 1 betekent dat een instantie van service s nodig is om applicatie a uit te kunnen voeren, Ia,s = 0 betekent dat dit niet nodig is. Daarna wordt ook de CPU-vereiste ωs van service s beschouwd, dewelke wordt uitgedrukt in GHz. Om de totale beschikbare CPU-capaciteit in het netwerk te vinden, wordt er gesommeerd over alle CPUcapaciteiten Ωn van alle nodes n ∈ N in het netwerk, dewelke ook worden uitgedrukt in GHz. Na het toekennen van CPU-capaciteiten Ωn aan alle nodes n ∈ N kennen we de totale beschikbare CPU-capaciteit in het netwerk. Verder kennen we ook de CPU-vereiste per applicatie, aangezien er geweten is welke services s ∈ S behoren bij elke applicatie a ∈ A, en is de CPUvereiste ωs gekend voor elk van deze services. Met behulp van deze gegevens kunnen we nu het aantal aanvragen per applicatie berekenen, om een gegeven CLF te verwezenlijken: P CLF × n∈N Ωn P Da,µ = |A| × s∈S Ia,s × ωs

(6.2)

We gebruiken bovenstaande parameter om in te stellen dat er gemiddeld Da,µ aanvragen zullen zijn voor elke applicatie a. Het genereren van het variabel aantal aanvragen Da per applicatie, per iteratie bij de vergelijking van alle algoritmen, gebeurt met behulp van een Gaussiaanse distributie. Hierbij zal het gemiddelde worden ingesteld op Da,µ , en wordt voor de standaardafwijking Da,σ = Da,µ /20 genomen. De keuze voor deze aanpak is om ervoor te zorgen dat er een vrij sterke controle is wat betreft de CLF. Deze parameter zal namelijk zijn invloed hebben op metrieken zoals de plaatsing van CPU-capaciteit, het aantal voldane aanvragen, het aantal gebruikte nodes in het netwerk en dergelijke.

6.2.3

Plaatsing van CPU-capaciteit

Een eerste metriek die wordt bekeken is hoeveel CPU-capaciteit er wordt gebruikt bij het behandelen van aanvragen voor applicaties. Bij cloud providers zoals Google App Engine worden gebruikers immers afgerekend op het aantal CPU-cycles dat ze verbruiken. Omwille van deze reden wordt er bij de probleemstelling in dit werk gekozen om die aanvragen voor applicaties te aanvaarden, die zorgen voor de grootste toekenning van CPU-capaciteit doorheen het netwerk. De eerste metriek die daarom wordt bekeken is de ‘CPU Voldane Factor’ (CVF).


Deze metriek wordt wiskundig voorgesteld in vergelijking 6.3. P P P a∈A r∈Ra ×Ga,r × s∈S Ia,s × ωs P P P CV F = a∈A r∈Ra × s∈S Ia,s × ωs

83

(6.3)

De CLF factor geeft de verhouding weer van de toegekende CPU-capaciteit bij het plaatsen van applicaties, ten opzichte van de aangevraagde CPU-capaciteit. De beslissingsvariabele Ga,r geeft weer of aanvraag r voor applicatie a al dan niet wordt geplaatst in het netwerk. Wanneer we deze factor vergelijken ten opzichte van de CLF van het systeem verwachten we dat de plaatsing van applicaties voor lage waarden van de CLF nagenoeg geen probleem mag vormen. In een eerste vergelijking is er gekozen om de hoeveelheid communicatie tussen services laag te houden ten opzichte van de bandbreedte in het netwerk, opdat deze factor de plaatsing niet zou hinderen. In een latere fase wordt deze factor echter terug bij de probleemstelling betrokken voor een uitgebreidere vergelijking tussen de algoritmen. Naarmate de waarden van de CLF toenemen zullen er meer en meer executie-servers nodig zijn om alle aanvragen te kunnen behandelen. Wegens het feit dat niet elke server alle services kan plaatsen, zal er intenser moeten gezocht worden naar een geschikte plaatsing voor alle aanvragen. Aangezien het ILP algoritme in staat is om een exacte oplossing voor het APP te genereren, verwachten we dat de resulterende CVF groter is dan bij het PSO- of het GA-algoritme. Echter, een CVF die gelijk is aan 1 bij hoge CLF waarden zal nagenoeg onhaalbaar zijn. Vanwege het feit dat services niet overal kunnen uitgevoerd worden, zou dit impliceren dat elk server exact tot aan zijn maximale CPU-capaciteit benut wordt. Dit betekent dat op elke server de som inzake alle CPU-vereisten van services exact gelijk is aan de CPU-capaciteit van deze server, wat nagenoeg onhaalbaar is. Indien er dan ook minstens één service is van een applicatie die niet geplaatst kan worden in het netwerk, wordt de aanvraag voor deze applicatie verworpen, en worden tevens alle andere services behorende tot deze applicatie ook niet geplaatst. Het dient hierbij opgemerkt te worden dat hoe kleiner de verhouding is van de CPU-vereisten van services tot de CPU-capaciteit van een executie-server, hoe eenvoudiger het is om deze server maximaal te benutten. Dit impliceert dat de som van alle CPU-vereisten van de services die op zo’n server uitgevoerd worden, dichter zal aanleunen bij de CPU-capaciteit van deze server. Dit komt vanwege het feit dat er op zo’n server meer combinaties kunnen gemaakt worden van services met een kleine CPU-vereiste, dan van services met een grote CPU-vereiste.

84


De waarde van de CVF in functie van de CLF, bij een eerste verlijking tussen het ILP-algoritme en de ontworpen PSO- en GA-algoritmen, wordt voorgesteld in figuur 6.2 en tabel 6.1. 1.2

ILP PSO GA

Factor van geplaatste CPU

1 0.8 0.6 0.4 0.2 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.2: CPU voldane factor (CVF) in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

1,00

0,99

1,00

0,99

0,99

0,98

0,97

0,94

0,90

0,86

σ

0,00

0,07

0,00

0,07

0,03

0,06

0,08

0,14

0,15

0,14

µ

1,00

0,99

1,00

0,99

0,99

0,97

0,95

0,91

0,85

0,80

σ

0,00

0,07

0,02

0,06

0,06

0,08

0,12

0,15

0,16

0,15

µ

1,00

0,99

1,00

0,99

0,99

0,97

0,95

0,91

0,84

0,79

σ

0,00

0,07

0,02

0,06

0,06

0,08

0,11

0,15

0,16

0,15

ILP

PSO

GA Tabel 6.1: CPU Voldane Factor (CVF) in functie van de CLF. We merken inderdaad dat de plaatsing voor lage waarden van de CLF geen probleem is voor de ILP, en ook niet voor de ontworpen PSO- en GA-algoritmen. Naarmate de waarden van de CLF toenemen presteert de ILP beter dan beide algoritmen, doch het verschil blijft relatief beperkt. Naast het gemiddelde voor de CVF, zijn ook de standaardafwijkingen tussen het PSOen GA-algoritme nagenoeg identiek. Hierdoor kunnen we stellen dat beide algoritmen even goed presteren als we kijken naar deze eerste metriek. Er kan tevens gesteld worden dat bij een CLF van 1, waarbij er evenveel CPU wordt aangevraagd door applicaties als er beschikbaar is in het systeem, zowel het PSO- en GA-algoritme maar 8% slechter presteren dan de ILP.


6.2.4

85

Plaatsing van aanvragen

Een tweede metriek die wordt bekeken is hoeveel aanvragen voor applicaties er effectief geplaatst werden in het netwerk. We introduceren hiertoe de ‘Request Voldane Factor’ (RVF), die de verhouding weergeeft tussen het aantal aanvragen voor applicaties die effectief geplaatst werden, en het totaal aantal aanvragen. Deze metriek wordt voorgesteld in figuur 6.3 en tabel 6.2.

Factor van geplaatste aanvragen

1.2

ILP PSO GA

1 0.8 0.6 0.4 0.2 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.3: Request Voldane Factor (RVF) in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

1,00

1,00

1,00

0,99

0,99

0,98

0,97

0,94

0,89

0,85

σ

0,00

0,04

0,00

0,06

0,05

0,06

0,09

0,14

0,16

0,16

µ

1,00

0,99

1,00

0,99

0,99

0,98

0,95

0,91

0,85

0,80

σ

0,00

0,05

0,01

0,05

0,04

0,07

0,10

0,16

0,16

0,16

µ

1,00

0,99

1,00

0,99

0,99

0,98

0,95

0,91

0,85

0,80

σ

0,00

0,05

0,01

0,05

0,05

0,07

0,10

0,16

0,16

0,16

ILP

PSO

GA Tabel 6.2: Request voldane factor (RVF) in functie van de CLF. We merken dat de resultaten voor deze factor nagenoeg hetzelfde zijn als voor de CVF. Bij de ILP is de RVF kleiner dan de CVF, wat verwacht werd. Echter, bij de ontworpen PSO- en GAalgoritmen stellen we een lichte verhoging van de RVF ten opzichte van de CVF vast, doch het verschil tussen beiden blijft beperkt. Mogelijk dienen de objectieffuncties van beide algoritmen aangepast te worden om de impact van de CVF zwaarder te laten doorwegen dan de RVF.

86


Wanneer een cloud provider deze metriek belangrijker acht dan de CVF, kan men de CVF-term weggelaten uit de huidige objectieffunctie in sectie 5.3.2. Op deze manier wordt er dus enkel nog aandacht besteed aan de RVF. Een nieuwe objectieffunctie is dan bijvoorbeeld: aantalGebruikteN odes aantalV erschillen obj = RV F × 1 − × 1− |N | + 1 |N | × |S| + 1

6.2.5

(6.4)

Aantal gebruikte nodes

Een volgende metriek die wordt beschouwd is hoeveel executie-servers er nodig waren om alle geplaatste aanvragen te behandelen. De verwachting hier is dat zowel het PSO- als het GAalgoritme meer executie-servers nodig zullen hebben dan de ILP om eenzelfde hoeveelheid aanvragen te behandelen. Bij de ILP zal immers het absolute minimum aan servers worden gezocht om alle aangevraagde applicaties te plaatsen. We verwachten daarom ook bij de ILP dat dit aantal lineair toeneemt met de CLF. Hoe meer aanvragen er binnenkomen, hoe meer executieservers er namelijk zullen nodig zijn om deze te plaatsen. Bij de andere ontworpen algoritmen wordt er niet gezocht naar zo’n minimum, en is deze voorwaarde minder streng. Het aantal gebruikte nodes in functie van de CLF kan men terugvinden in figuur 6.4 en tabel 6.3. 8

ILP PSO GA


7 6 5 4 3 2 1 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.4: Aantal gebruikte nodes in functie van de CLF. We merken inderdaad bij de ILP dat het aantal gebruikte nodes om alle geaccepteerde aanvragen voor applicaties te plaatsen, veel kleiner is dan bij de andere algoritmen. Zoals verwacht neemt dit aantal ook lineair toe met de CLF.


CLF

87

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

1,75

2,30

3,18

3,94

4,47

5,26

5,76

6,53

6,79

7,09

σ

0,73

0,56

0,79

0,76

0,68

0,70

0,88

0,88

1,26

1,22

µ

2,91

3,79

4,70

6,03

6,25

7,12

7,22

7,42

7,38

7,35

σ

1,05

1,67

1,57

1,61

1,69

1,17

1,12

1,01

1,02

1,27

µ

2,94

3,84

4,81

6,08

6,38

7,16

7,16

7,48

7,40

7,33

σ

1,04

1,78

1,58

1,59

1,61

1,24

1,19

0,94

0,98

1,29

ILP

PSO

GA Tabel 6.3: Aantal gebruikte nodes in functie van de CLF. Bij de ontworpen PSO- en GA-algoritmen wordt al sneller een grotere portie van het netwerk gebruikt om alle geaccepteerde applicaties te plaatsen. Onderling merken we weinig verschil tussen beide algoritmen, doch het dient opgemerkt te worden dat het PSO-algoritme iets minder nodes zal gebruiken dan het GA-algoritme. Initieel merken we ook een steiler verloop bij beide algoritmen ten opzichte van het ILP algoritme. Vanaf een CLF van 0.80 echter wordt er grofweg altijd eenzelfde aantal nodes gebruikt om de aanvragen te behandelen. Het punt waarop dit gebeurt is tevens het punt waarop de CVF en RVF afnemen bij een stijgende CLF, wanneer er dus proportioneel minder aanvragen konden geplaatst worden van de totale vraag ernaar.

6.2.6

Aantal verplaatsingen tussen twee iteraties

Een ander objectief dat wordt bekeken is het aantal verplaatsingen van service-instanties tussen twee iteraties. Verplaatsingen van zulke instanties worden immers aangezien als een kostbare verspilling van tijd en resources, men moet ze immers op de ene plaats in het netwerk afbreken om op een andere plaats terug op te starten. Dit maakt ook dat ze in de praktijk de communicatiekost doen toenemen in het netwerk [50]. Het aantal verplaatsingen van service-instanties tussen twee iteraties, in functie van de CLF, wordt voorgesteld in figuur 6.5 en tabel 6.4. Uit figuur 6.5 merken we dat bij een lage CLF het aantal verplaatsingen bij het ILP algoritme hoger is dan bij de ontworpen PSO- en GA-algoritmen. Dit is begrijpelijk, aangezien de ILP minder nodes zal gebruiken dan de andere algoritmen voor eenzelfde hoeveelheid aanvragen te behandelen. Dit maakt dat er ook meer verplaatsingen moeten gebeuren van service-instanties om dit aantal gebruikte nodes zo laag te kunnen houden.

88


12

ILP PSO GA

Aantal plaatsing verschillen

10 8 6 4 2 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.5: Aantal verplaatsingen in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

3,60

3,84

4,90

5,38

5,62

6,10

7,15

7,39

7,77

8,35

σ

1,11

1,53

1,84

2,03

2,07

1,99

2,36

2,38

2,44

2,35

µ

2,70

3,97

5,88

8,04

9,14

9,79

10,51

9,71

10,63

10,03

σ

2,08

2,69

3,11

3,81

3,15

3,25

3,13

3,46

3,93

4,04

µ

2,24

3,10

4,78

6,64

7,79

7,79

8,97

7,45

9,08

8,70

σ

2,44

2,74

3,26

4,01

4,02

3,75

3,84

4,41

4,81

4,55

ILP

PSO

GA Tabel 6.4: Aantal verplaatsingen in functie van de CLF. We merken ook duidelijk dat bij het GA-algoritme er steeds minder verplaatsingen gebeuren dan bij het PSO-algoritme. Verder is er voor het PSO- en GA-algoritme een soort constante te merken inzake het aantal verplaatsingen vanaf een CLF van 0.70, wat ongeveer het punt is waarop er bij deze algoritmen eenzelfde aantal nodes wordt gebruikt in het netwerk.

6.2.7

Totale netwerkkost

De netwerkkost die in dit werk wordt beschouwd, werd al eerder gedefinieerd in sectie 3.2.5. Het idee achter deze metriek is dat we services die met elkaar communiceren, zo dicht mogelijk bij elkaar willen plaatsen in het netwerk. De afstand die hierbij wordt beschouwd is de hop count, die aangeeft hoeveel tussenliggende apparatuur (zoals nodes zelf, routers, switches, bridges) er


89

minstens aanwezig zijn op het kortste pad tussen elk paar nodes. Als gewichtsfactor bij de hop count tussen twee paar nodes nemen we de communicatie (in MBit/s) tussen de services die op beide nodes worden uitgevoerd. Zo zal er eerder geprobeerd worden om services dicht bij elkaar te plaatsen die veel communiceren met elkaar, dan services die dat weinig doen. De waarde van deze netwerkkost wordt in functie van de CLF voorgesteld in figuur 6.6 en tabel 6.5. 10

ILP PSO GA

Totale netwerkkost

8

6

4

2

0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.6: Totale netwerkkost in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

0,23

0,47

0,89

1,17

1,41

1,69

1,86

2,11

2,49

2,45

σ

0,23

0,38

0,58

0,73

0,85

0,91

1,11

1,08

1,34

1,28

µ

0,99

1,99

3,75

5,10

5,82

6,92

7,60

9,12

9,56

9,53

σ

0,83

1,45

2,21

3,02

3,66

3,58

4,59

4,96

5,26

5,29

µ

0,97

2,04

3,63

4,92

5,73

6,99

7,60

8,99

9,13

9,30

σ

0,81

1,53

2,14

2,93

3,56

3,60

4,63

4,92

5,32

5,16

ILP

PSO

GA Tabel 6.5: Totale netwerkkost in functie van de CLF. We merken duidelijk dat de netwerkkost bij de ILP veel kleiner is dan deze bij het PSO- of het GA-algoritme. Dit kan verklaard worden door het feit dat de ILP de nodes kiest waarop services uitgevoerd worden, zodanig dat de netwerkkost minimaal blijft. Bij het PSO- en het GA-algoritme zal men eerder vertrekken vanaf de nodes waarop services uitgevoerd worden, en daarna pas een minimaal pad berekenen inzake deze netwerkkost. Tevens zal er bij de ILP ook geprobeerd worden om services die met elkaar communiceren op eenzelfde node uit te voeren,

90


aangezien de hop count dan 0 is, en aldus ook de kost. Bij het PSO- en het GA-algoritme is hier minder aandacht aan besteed. Verder is er ook maar een klein verschil te merken tussen het PSO- en GA-algoritme, waarbij het GA-algoritme iets beter doet dan het PSO-algoritme.

6.2.8

Benodigde verwerkingstijd

Een laatste metriek die we beschouwen is de benodigde verwerkingstijd van alle algoritmen. Zoals eerder aangehaald in sectie 2.2.2 bevindt het ILP zich in de klasse van NP-problemen. Dit maakt dat het vinden van een exacte oplossing zeer tijdsintensief is en amper schaalbaar, wat maakt dat het toepassen van deze techniek amper bruikbaar is in de praktijk. Immers, als het aantal aanvragen, applicaties, services en/of resources toeneemt, zal de benodigde tijd om een oplossing te berekenen voor het APP exponentieel toenemen. Een ILP is daarom enkel nuttig als maatstaf ten opzichte van andere algoritmen. De benodigde verwerkingstijd (logaritmisch, in seconden) voor alle algoritmen wordt voorgesteld in figuur 6.7 en tabel 6.6.

Verwerkingstijd (s, log)

ILP PSO GA 10

1

0.1 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.7: Verwerkingstijd (logaritmisch, in seconden) in functie van de CLF. We bemerken duidelijk dat de benodigde verwerkingstijd voor het ILP algoritme exponentieel toeneemt wanneer de CLF stijgt, dus wanneer het aantal aanvragen voor applicaties toeneemt. Daar waar het ILP nog een oplossing kon berekenen in minder dan een seconde voor een CLF lager dan 0.20, doet dit algoritme er nu gemiddeld al een halve minuut over voor een CLF van 1. Hierbij is tevens een bijzonder grote standaardafwijking op te merken. Gegeven de kleine testopstelling die we hanteren bij deze eerste evaluatie kunnen we dus stellen dat deze


CLF

91

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

0,36

0,65

1,10

1,73

2,79

4,03

5,55

6,55

20,31

30,00

σ

0,16

0,32

0,52

0,73

2,47

3,04

3,59

4,62

96,07

104,46

µ

0,07

0,10

0,13

0,15

0,18

0,20

0,21

0,24

0,24

0,26

σ

0,03

0,04

0,04

0,04

0,03

0,03

0,04

0,05

0,05

0,06

µ

0,07

0,10

0,12

0,16

0,18

0,20

0,21

0,24

0,25

0,26

σ

0,03

0,04

0,04

0,04

0,03

0,04

0,04

0,04

0,05

0,04

ILP

PSO

GA Tabel 6.6: Verwerkingstijd (in seconden) voor alle algoritmen in functie van de CLF. oplossingstechniek niet bruikbaar is voor praktische doeleinden. Het PSO- en GA-algoritme daarentegen vertonen een minder steile curve voor het berekenen van een oplossing voor het APP. Vanaf een CLF van 0.80 is er bijvoorbeeld nog amper een toename in benodigde verwerkingstijd. Indien we ook kijken naar de standaardafwijking kunnen we stellen dat het verschil in verwerkingstijd voor beide algoritmen verwaarloosbaar klein is.

92


6.3 6.3.1

Vergelijkende studie tussen PSO en GA Testopstelling

De volgende algemene parameters werden gebruikt bij de vergelijkende studie op grote schaal tussen het PSO-algoritme en het GA-algoritme: • Aantal iteraties: 100 • Aantal applicaties: 10 • Aantal services waaruit applicaties opgebouwd zijn: 13 • Kans dat een service behoort tot een applicatie: 40% (uniforme distributie) • CPU-vereiste van een service: willekeurig element ∈ {0.50, 0.60, 0.70, 0.80, 0.90, 1.00} GHz • Geheugenvereiste van een service: willekeurig element ∈ {0.50, 0.70, 0.90, 1.10, 1.30, 1.50} GB • Aantal management-servers die elke management-server beheert op de bovenste lagen: 4 • Aantal executie-servers die elke management-server beheert op de onderste laag: 10 Resulterend aantal executie-servers in het netwerk: 4 × 4 × 10 = 160 • CPU-capaciteit van een executie-server: willekeurig element ∈ {9, 12, 15, 18, 21} GHz • Geheugencapaciteit van een executie-server: willekeurig element ∈ {6, 8, 10, 12, 14} GB • Communicatievereiste tussen elk paar services: Gaussiaans (µ = 2.5 en σ = 0.20) Mbit/s Hierdoor zal de communicatie-eis tussen services op een gegeven moment wel een beperking vormen op de plaatsing van applicaties in het netwerk, zoals later ook aangetoond zal worden. • Hop count tussen elk paar executie-server: Gaussiaans (µ = 7 en σ = 2) hops • Bandbreedte tussen elk paar executie-servers: met een uniforme kans van 5% wordt een communicatielink voorzien tussen elk paar executie-servers, waarbij de capaciteit van deze link Gaussiaans verdeeld is met µ = 20 Mbit/s en σ = 1 Mbit/s

6.3.2

Beperkte bandbreedte in het netwerk

Zoals eerder vermeld tijdens de probleemstelling in sectie 3.2.2 mag een workflow, dus de communicatie tussen twee services, maar als geplaatst beschouwd worden in het netwerk indien er aan minstens 80% van zijn eis inzake communicatie kan voldaan worden. Indien een van de workflows behorende tot een applicatie dus niet voor minstens 80% kan geplaatst worden, wordt de aanvraag voor deze applicatie verworpen. Initieel wordt er dus ook maar voor 80% voldaan aan elke workflow. In een later stadium, als bepaald is hoeveel aanvragen er konden behandeld

6.3. VERGELIJKENDE STUDIE TUSSEN PSO EN GA

93

worden, zal elke workflow terug overlopen worden. Hierbij wordt vervolgens geprobeerd om de communicatie-voldoening van deze workflow te verhogen, voor zover het netwerk dit toelaat. We kunnen tevens een ruwe schatting maken vanaf welke CLF de bandbreedte een beperking begint te vormen op de plaatsing van applicaties. We weten immers dat er 13 mogelijke services zijn waaruit een applicatie kan opgebouwd worden, en dat elke service 40% kans heeft om deel uit te maken van elke applicatie. Tevens zal elk paar services met elkaar communiceren, gegeven dat beide services deel uitmaken van een applicatie. Deze communicatie-eis bedraagt gemiddeld 2.5 Mbit/s, doch hoeft initieel maar voor 80% voldaan te worden. De minimale trafiek veroorzaakt door elke applicatie bedraagt dus: traf iekapp =

13 × (13 − 1) × (0.40)2 × 2.5 Mbit/s × 0.80 2

= 24.96 Mbit/s

(6.5)

Het totaal aantal nodes in het netwerk bedraagt 160, zijnde 4×4×10. Met een uniforme kans van 5% wordt een communicatielink gelegd tussen elk paar nodes in het netwerk. De bandbreedte van deze link is Gaussiaans verdeeld met µ = 20 Mbit/s en σ = 1 Mbit/s. Aldus kunnen we de totale bandbreedte die beschikbaar is in het netwerk als volgt berekenen: bandwidthnetwerk =

160 × (160 − 1) × 0.05 × 20 Mbit/s 2

= 12720 Mbit/s Het aantal aanvragen dat ruwweg aanvaard kan worden is dus

(6.6) bandwidthnetwerk traf iekapp

∼ = 510. Verder

weten we ook dat gemiddeld elke executie-server over een CPU-capaciteit van 15 GHz beschikt. Elke applicatie zal dan weer een totale CPU-vereiste van 13×0.40×0.75 GHz = 3.9 GHz hebben. Met behulp van deze cijfers kunnen we dus de CLF berekenen vanaf wanneer de bandbreedte in het netwerk een beperking begint te vormen op de plaatsing van applicaties: CLFprobleem =

510 × 13 × 0.40 × 0.75 GHz 4 × 4 × 10 × 15 GHz

∼ = 0.83

(6.7)

We verwachten dus ongeveer dat vanaf een CLF van 0.80 de uiteindelijke communicatie-voldoening van elke workflow niet ver boven de 80% zal uitstijgen. Gemiddeld genomen zal deze echter nog altijd boven de 80% komen, gegeven volgende redenering. Initieel wordt elke communicatie-eis van een workflow voor 80% gegarandeerd in het netwerk. Indien er niet meer aan deze eis kan worden voldaan, zal de betreffende applicatie niet geplaatst worden in het netwerk. Dit betekent

94


dat alle workflows van die applicatie, die wel voor 80% konden worden voldaan, ook niet meer zullen geplaatst worden. In deze situatie komt er dus terug bandbreedte vrij in het netwerk, die eventueel kan gebruikt worden om een andere applicatie te plaatsen. In een later stadium, wanneer bepaald is hoeveel aanvragen voor applicaties er konden aanvaard worden, zal voor elke workflow overlopen worden in hoeverre men zijn communicatie-voldoening kan verhogen. De bandbreedte die nog resteert in het netwerk zal hiervoor gebruikt worden, waardoor sommige workflows toch nog boven hun 80% communicatie-voldoening zullen uitstijgen. De gemiddelde workflow-voldoening in het netwerk wordt voorgesteld in figuur 6.8 en tabel 6.7. 1

PSO GA

0.98 Workflow voldoening

0.96 0.94 0.92 0.9 0.88 0.86 0.84 0.82 0.8 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.8: Workflow voldoening in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

0,986

0,991

0,986

0,957

0,913

0,867

0,856

0,842

0,837

0,835

σ

0,010

0,005

0,008

0,035

0,044

0,031

0,030

0,014

0,012

0,009

µ

0,986

0,990

0,988

0,964

0,919

0,871

0,858

0,843

0,837

0,835

σ

0,016

0,012

0,007

0,029

0,044

0,032

0,033

0,014

0,012

0,009

PSO

GA Tabel 6.7: Workflow voldoening in functie van de CLF. Uit figuur 6.8 kunnen we stellen dat vanaf een CLF van 0.30 tot 0.70 de communicatie-voldoening van elke workflow sterk afneemt. Vanaf een CLF van 0.80 merken we inderdaad dat deze communicatie-voldoening begint te stagneren, en deze niet ver meer boven de 80% uitkomt. Tevens kunnen we opmerken dat het PSO-algoritme steeds minder aan de communicatie-eis van


95

elke workflow zal voldoen dan het GA-algoritme. Dit valt mogelijk te verklaren doordat het PSO-algoritme meer aanvragen kan behandelen, waardoor het netwerk dus sterker belast wordt dan bij het GA-algoritme. Echter, voor zeer lage en zeer hoge CLF waarden kunnen we stellen dat er weinig verschil te bemerken valt tussen beide algoritmen.

6.3.3

Plaatsing van CPU-capaciteit

In figuur 6.9 en tabel 6.8 wordt de CVF getoond in functie van de CLF. Tot en met een CLF van 0.60 merken we dat het PSO-algoritme beter presteert dan het GA-algoritme, zoals ook enigszins voorspeld werd door te kijken naar de workflow-voldoening in het netwerk. Vanaf deze CLF-waarde zijn de resultaten echter nagenoeg hetzelfde voor beide algoritmen. Tevens vertoont het GA-algoritme een grote standaardafwijking op de CVF bij een CLF van 0.10 en 0.20, iets waar het PSO-algoritme duidelijk geen last mee had. 1.2

PSO GA

Factor van geplaatste CPU

1 0.8 0.6 0.4 0.2 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.9: CPU voldane factor (CVF) in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

0,99

0,99

1,00

0,98

0,93

0,83

0,77

0,70

0,60

0,56

σ

0,02

0,02

0,01

0,03

0,07

0,09

0,11

0,10

0,11

0,10

µ

0,98

0,99

0,99

0,96

0,91

0,83

0,77

0,70

0,60

0,56

σ

0,11

0,08

0,01

0,04

0,06

0,09

0,11

0,10

0,11

0,10

PSO

GA Tabel 6.8: CPU Voldane Factor (CVF) in functie van de CLF.

96


6.3.4

Plaatsing van aanvragen

Wanneer we kijken naar de resultaten van de RVF in figuur 6.10 en tabel 6.9, dan merken we terug dat de RVF altijd groter is dan de CVF. Dezelfde conclusie diende zich aan bij de kleine testopstelling, waarin beide algoritmen werden vergeleken met de ILP. De objectieffunctie in beide algoritmen, die gehanteerd werd voor de kwaliteit van oplossingen te bepalen, dient dus verder aangepast te worden. Immers, bij een CLF van 1 kan gemiddeld nog 60% van de aanvragen voor applicaties geplaatst worden in het netwerk, doch zorgt dit maar voor een CPUbenutting van 56%. Dit betekent dus dat er voorrang gegeven wordt aan applicaties die weinig CPU-capaciteit nodig hebben, wat tegen de verwachtingen is. Een mogelijke oplossing hiervoor is om de impact van de CVF in de objectieffunctie uit sectie 5.3.2 nog groter te maken dan die van de RVF, zoals eerder ook al werd aangehaald.

Factor van geplaatste aanvragen

1.2

PSO GA

1 0.8 0.6 0.4 0.2 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.10: Request Voldane Factor (RVF) in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

0,99

1,00

1,00

0,98

0,94

0,86

0,79

0,74

0,64

0,60

σ

0,02

0,01

0,01

0,03

0,06

0,09

0,12

0,11

0,13

0,13

µ

0,98

0,99

0,99

0,97

0,93

0,85

0,79

0,74

0,64

0,60

σ

0,09

0,07

0,01

0,03

0,06

0,09

0,12

0,11

0,13

0,13

PSO

GA Tabel 6.9: Request voldane factor (RVF) in functie van de CLF.


6.3.5

97


Wanneer we in figuur 6.11 en tabel 6.10 kijken naar het aantal nodes dat gebruikt wordt om alle aanvragen te behandelen, dan merken we iets bijzonders op. Vanaf een CLF vanaf 0.30 zal immers bijna het volledige netwerk, zijnde 160 executie-servers, gebruikt worden om alle aanvragen te behandelen. Echter, grofweg zouden er bij een CLF van 0.30 maar 0.30 × 160 = 48 servers nodig moeten zijn om deze aanvragen te plaatsen. Dit betekent dat beide algoritmen vrij slecht presteren om het aantal nodes die gebruikt worden bij een plaatsing te minimaliseren. 170

PSO GA


160

150

140

130

120 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.11: Aantal gebruikte nodes in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

125,55 152,35 157,43 159,26 159,72 159,86 159,78 159,85 159,77 159,85

σ

9,47

µ

126,62 152,99 158,47 159,40 159,78 159,89 159,86 159,90 159,85 159,89

σ

15,68

PSO 3,77

2,96

1,04

0,62

0,38

0,58

0,39

0,51

0,39

GA 12,64

1,39

0,77

0,46

0,31

0,38

0,33

0,36

0,31

Tabel 6.10: Aantal gebruikte nodes in functie van de CLF. Wanneer we de resultaten voor een kleine testopstelling in figuur 6.4 en tabel 6.3 beschouwen, kon er opgemerkt worden dat het aantal gebruikte nodes bij een plaatsing mee schaalt met de waarde van de CLF. Echter, bij deze grotere opstelling zal al vrij snel het volledige netwerk gebruikt worden om alle aanvragen te behandelen. Vanaf een CLF van 0.40 treedt er immers nagenoeg geen verschil meer op in het aantal gebruikte nodes om een plaatsing te behandelen.

98


Een mogelijke oplossing voor dit probleem is om de initialisatie van de zwerm bij het PSOalgoritme en de populatie bij het GA-algoritme anders aan te pakken. In plaats van willekeurig een node te kiezen waarop elke service van een applicatie wordt uitgevoerd, zou er voorrang gegeven kunnen worden aan nodes die eerder al gebruikt werden. De allereerste service die wordt behandeld zal dan willekeurig een node kiezen, doch gelijkaardige services zullen in de toekomst wel eerder deze node kiezen dan een andere. Omdat we met een populatie van oplossingen werken, zal de initialisatie voor de verschillende deeltjes en individuen telkens gebruik maken van andere nodes. Deze aanpak zal dus vermoedelijk resulteren in een gevarieerd aantal oplossingen, die telkens zuiniger omspringen met het aantal gebruikte nodes om een plaatsing te behandelen.

6.3.6

Aantal verplaatsingen tussen twee iteraties

In figuur 6.12 en tabel 6.11 wordt het aantal verplaatsingen van service-instanties tussen twee iteraties voorgesteld. Voor grote CLF-waarden merken we duidelijk op dat er bij het GAalgoritme telkens minder verplaatsingen gebeuren dan bij het PSO-algoritme, iets wat ook al werd aangetoond bij de kleinere testopstelling in sectie 6.2.6. 900

PSO GA

Aantal plaatsing verschillen

800 700 600 500 400 300 200 100 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.12: Aantal verplaatsingen in functie van de CLF. Verder merken we ook een stagnatie inzake het aantal verplaatsingen vanaf een CLF van 0.60. Dit valt mogelijk te verklaren doordat er vanaf dit punt steeds maar een bepaald aantal aanvragen meer kan behandeld worden. Aangezien dit aantal hetzelfde blijft, is dit mogelijk een verklaring voor het feit dat het aantal verplaatsingen ook hetzelfde blijft.


CLF

99

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

249,6

449,6

588,5

696,1

760,5

788,7

800,1

804,9

790,1

784,6

σ

23,7

35,2

46,4

39,6

38,7

40,7

42,8

47,5

46,2

56,2

µ

275,3

470,3

585,2

664,6

704,3

724,4

722,5

726,7

713,1

695,7

σ

42,1

43,7

37,5

42,1

47,0

54,9

45,3

60,7

53,4

53,2

PSO

GA Tabel 6.11: Aantal verplaatsingen in functie van de CLF.

6.3.7

Totale netwerkkost

Wanneer we kijken naar de totale netwerkkost in figuur 6.13 en tabel 6.12, dan merken we op dat deze stagneert vanaf een CLF van 0.60. Dit valt mogelijk te wijten aan het feit dat het netwerk vanaf dit moment verzadigd begint te worden, wat ook al aangetoond werd in sectie 6.3.2. 180

PSO GA

Totale netwerkkost (x 1000)

160 140 120 100 80 60 40 20 0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.13: Totale netwerkkost (x 1000) in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

29,90

60,19

91,84

127,44 145,42 153,22 153,36 155,65 154,41 153,73

σ

4,54

9,45

18,18

19,68

µ

29,84

60,01

90,87

125,52 144,31 152,96 153,27 155,39 154,35 153,96

σ

5,56

10,60

17,18

18,75

PSO 12,81

6,50

8,35

5,88

7,43

7,52

GA 12,92

6,37

8,24

5,82

Tabel 6.12: Totale netwerkkost (x 1000) in functie van de CLF.

7,48

7,41

100


Wanneer we ook kijken naar het aantal verplaatsingen van service-instanties in sectie 6.3.6, merken we ook dat deze metriek ongeveer hetzelfde blijft vanaf een CLF van 0.60. Mogelijk zal er vanaf dit punt steeds eenzelfde aantal aanvragen voor applicaties nog aanvaard worden, aangezien het netwerk weinig meer aankan. Dit verklaart dan ook het feit dat de netwerkkost amper nog verandert vanaf dit punt.

6.3.8

Benodigde verwerkingstijd

Wanneer we tenslotte nog kijken naar de benodigde verwerkingstijd voor beide algoritmen in figuur 6.14 en tabel 6.13, dan merken we dat we met deze relatief kleine testopstelling al vrij snel 2 minuten nodig hebben om een plaatsing te berekenen voor alle aanvragen. Bij het PSOalgoritme merken we trouwens een piek in de benodigde verwerkingstijd voor een CLF van 0.40 tot 0.70, waarvoor niet direct een verklaring is gevonden. 200

PSO GA

Verwerkingstijd (s)

150

100

50

0 0.10

0.20

0.30

0.40

0.50

0.60

0.70

0.80

0.90

1.00


Figuur 6.14: Verwerkingstijd (in seconden) in functie van de CLF. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

22,20

49,14

81,80

144,51 171,48 155,47 136,26 117,76 119,56 112,82

σ

6,91

15,32

26,56

68,98

79,30

66,09

µ

26,27

53,46

59,56

80,61

94,24

104,04 104,27 111,03 108,56 103,53

σ

11,95

21,90

12,50

12,24

13,63

14,26

PSO 60,00

24,81

28,14

16,57

GA 12,76

13,91

15,08

Tabel 6.13: Verwerkingstijd (in seconden) in functie van de CLF.

13,98


101

Beschouwen we tot slot tabel 6.14, waar de benodigde verwerkingstijd is voorgesteld voor eenzelfde testopstelling zonder communicatie tussen services. Hierbij merken we dat de benodigde verwerkingstijden voor beide algoritmen significant kleiner worden wanneer we abstractie maken van deze communicatie. Het is dus duidelijk dat dit netwerkaspect zorgt voor de grote verwerkingstijd van beide algoritmen. Mogelijk is op dat vlak nog enige verbetering te bekomen indien we niet meer gebruik maken van de JGraphT bibliotheek, maar zelf een algoritme implementeren die het kortste pad kan berekenen in een netwerk. CLF

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

µ

0,37

0,50

0,76

0,96

1,17

1,38

1,62

2,01

2,23

2,64

σ

0,18

0,42

0,25

0,28

0,24

0,22

0,36

0,49

0,55

0,65

µ

0,34

0,34

0,57

0,68

0,80

0,88

1,01

1,41

1,50

1,67

σ

0,15

0,18

0,19

0,14

0,20

0,18

0,22

0,46

0,45

0,50

PSO

GA Tabel 6.14: Verwerkingstijd (in seconden) in functie van de CLF - zonder communicatie.

Hoofdstuk 7

Conclusie 7.1

Inleiding

In deze masterproef werd het Application Placement Problem onderzocht, dat een oplossing dient te bieden van welke service-instanties dienen uitgevoerd te worden op welke nodes. Er werd hierbij speciale aandacht besteed aan de netwerkinfrastructuur van een cloud provider, en de impact van een Service Oriented Architecture. Hierdoor worden de applicaties beschouwd als een combinatie van een aantal communicerende services, waardoor het netwerkaspect in de probleemstelling niet mag verwaarloosd worden. In eerste instantie werd een literatuurstudie uitgevoerd omtrent welke oplossingsmethoden er momenteel gebruikt worden om dit probleem op te lossen. Vervolgens werd zelf een architectuur voorgesteld die op een hiërarchische manier een oplossing voor dit probleem kan bieden. Hiervoor werden twee algoritmen ontworpen, gebaseerd op de meta-heuristieken Particle Swarm Optimization en Genetische Algoritmen. Tevens werd een wiskundig model opgesteld om exacte oplossingen te kunnen verkrijgen. Dit model werd vervolgens ge¨ımplementeerd met behulp van Integer Linear Programming, om de performantie van beide algoritmen in te kunnen schatten.

7.2

Resultaten

Wanneer we een kleine testopstelling beschouwen zonder strenge communicatie-eisen, en vervolgens kijken naar de CLF- en de RVF-waarden, dan merken we dat beide ontworpen PSO- en GA-algoritmen vrij gelijkaardig presteren. Het PSO-algoritme zal daarbij iets minder executie-

103

104

HOOFDSTUK 7. CONCLUSIE

servers gebruiken dan het GA-algoritme, doch het verschil is verwaarloosbaar. Wanneer we echter het aantal verplaatsingen van service-instanties op nodes beschouwen, merken we dat het PSO-algoritme beduidend meer verplaatsingen doorvoert dan het GA-algoritme. De beschouwde netwerkkost in dit werk is ook iets hoger bij het PSO-algoritme dan bij het GA-algoritme, doch het verschil is terug nagenoeg verwaarloosbaar. Bij het beschouwen van een grotere testopstelling met bandbreedte-limitaties die de plaatsing van applicaties zullen hinderen, valt het onmiddellijk op dat beide ontworpen algoritmen vrij snel het volledige netwerk gebruiken om alle service-instanties te plaatsen. Daarbij zal het PSO-algoritme echter minder aan de communicatie-eis van elke service workflow voldoen, maar waardoor er uiteindelijk meer aanvragen voor applicaties kunnen behandeld worden. Wanneer alle communicatielinks in het netwerk echter verzadigd beginnen geraken, presteren beide algoritmen nagenoeg even goed.

7.3 7.3.1

Verder onderzoek Hi¨ erarchische boomstructuur

In dit werk werd er aangenomen dat het overschot van de aanvragen die niet geplaatst konden worden door een bepaalde management-server, doorgegeven werd naar de management-server hogerop in de hiërarchische boomstructuur. Dit zorgt ervoor dat indien er maar een kleine overschot meer overbleef, direct een veel groter deel van het netwerk beschouwd werd voor de plaatsing uit te voeren. Verder onderzoek kan gevoerd worden naar de schaalbaarheid van de aanpak in dit werk. Een aanpak waarbij het overschot aan aanvragen doorgegeven wordt naar een andere management-server op hetzelfde niveau, zou eventueel betere resultaten kunnen opleveren. Enkel indien geen enkele management-server op deze laag nog de aanvragen kan plaatsen, zou het overschot doorgegeven worden naar hogerop in de structuur.

7.3.2

Ontworpen algoritmen

Een van de zaken waar aandacht aan besteed dient te worden bij de ontworpen algoritmen is het aantal gebruikte nodes bij een plaatsing kleiner te houden. Dit kan eventueel gebeuren door de initialisatie van de zwerm bij het PSO-algoritme en de populatie bij het GA-algoritme anders aan te pakken. In plaats van willekeurig een node te kiezen waarop elke service van een applicatie wordt uitgevoerd, zou er voorrang gegeven kunnen worden aan nodes die eerder al gebruikt

7.3. VERDER ONDERZOEK

105

werden. De allereerste service die wordt behandeld zal dan willekeurig een node kiezen, doch gelijkaardige services zullen in de toekomst wel eerder deze node kiezen dan een andere. Omdat we met een populatie van oplossingen werken, zal de initialisatie voor de verschillende deeltjes en individuen telkens gebruik maken van andere nodes. Deze aanpak zal dus vermoedelijk resulteren in een gevarieerd aantal oplossingen, die telkens zuiniger omspringen met het aantal gebruikte nodes om een plaatsing te behandelen. Een ander onderwerp waar verder onderzoek kan naar gebeuren is de ontworpen algoritmen onderleggen aan een intense parameter sweep. Algemene instellingen bij beide algoritmen, zoals de grootte van de oplossingenverzameling, het aantal iteraties dat uitgevoerd wordt en het stopcriteria kunnen nog eens nader bekeken worden. Bij het ontworpen PSO-algoritme kan men ook de impact van verschillende gewichtsfactoren op het eindresultaat nagaan. Bij het GA-algoritme kan men dan weer de instellingen van de selectie, kruising en mutatie evalueren. Men kan ook andere algoritmen implementeren voor het APP dat beschouwd werd in dit werk op te lossen. Daarbij kan men in dezelfde logische buurt van algoritmen blijven, en zich focussen op diegene die werken met een zwerm of populatie aan oplossingen. Echter, men kan ook een volledig ander soort algoritme gebruiken om de performantie ten opzichte van beide ontworpen algoritmen na te gaan.

Bibliografie [1] JGraphT - a free Java Graph Library. Accessed online in June 2013 at http://jgrapht. sourceforge.net/. [2] C. Adam, G. Pacifici, M. Spreitzer, R. Stadler, and C. Tang. A Decentralized Application Placement Controller for Web Applications. Technical report, IBM, RC23980, 2006. Accessed online in August 2012 at http://www.ee.kth.se/php/modules/publications/ reports/2006/TRITA-EE_2006_029.pdf. [3] C. Adam and R. Stadler. Service Middleware for Self-Managing Large-Scale Systems. IEEE Transactions on Network and Service Management (TNSM), 4(3):50–64, 2007. doi: 10.1109/TNSM.2007.021103. [4] N. Agoulmine, S. Balasubramaniam, D. Botvitch, J. Strassner, E. Lehtihet, and W. Donnelly. Challenges for Autonomic Network Management. In Proceedings of the 1st IEEE International Workshop on Modeling Autonomic Communications Environments (MACE). IEEE Computer Society, 2006. [5] M. Armbrust, A. Fox, R. Griffith, A. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia. of Cloud Computing.

Above the Clouds: A Berkeley View

Technical report, University of California at Berkeley, 2009.

Accessed online in August 2012 at http://berkeleyclouds.blogspot.com/2009/02/ above-clouds-released.html. [6] D. Breitgand and A. Epstein. SLA-aware Placement of Multi-Virtual Machine Elastic Services in Compute Clouds. In Proceedings of the 12th IFIP/IEEE International Symposium on Integrated Network Management (IM), pages 161–168. IEEE Computer Society, 2011. doi: 10.1109/INM.2011.5990687.

107

108

BIBLIOGRAFIE

[7] R. Buyya, D. Abramson, and J. Giddy. Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid. In Proceedings of the 4th IEEE International Conference on High Performance Computing in the AsiaPacific Region (HPCN), volume 1, pages 283–289. IEEE Computer Society, 2000. doi: 10.1109/HPC.2000.846563. [8] R. Buyya, C. S. Yeo, S. Venugopal, J. Broberg, and I. Brandic.

Cloud Compu-

ting and Emerging IT Platforms: Vision, Hype, and Reality for Delivering Computing as the 5th Utility.

Future Generation Computer Systems, 25(6):599–616, 2009.

doi:

10.1016/j.future.2008.12.001. [9] D. Carrera, M. Steinder, I. Whalley, J. Torres, and E. Ayguade. Utility-based Placement of Dynamic Web Applications with Fairness Goals. In Proceedings of the 11th IFIP/IEEE Network Operations and Management Symposium (NOMS), pages 9–16. IEEE Computer Society, 2008. doi: 10.1109/NOMS.2008.4575111. [10] D. Cheng. PaaS-onomics: A CIO’s Guide to Using Platform-as-a-Service to Lower Costs of Application Initiatives While Improving the Business Value of IT. Technical report, LongJump, 2008.

Accessed online in September 2012 at http://www.longjump.com/

downloads/whitepapers/WP-PaaS.pdf. [11] F. Chong and G. Carraro. Architecture Strategies for Catching the Long Tail. MSDN Library, Microsoft Corporation, pages 9–10, 2006. Accessed online in October 2012 at http://msdn.microsoft.com/en-us/library/aa479069.aspx. [12] O. Dagdeviren and K. Erciyes. A Hierarchical Leader Election Protocol for Mobile Ad hoc Networks. In Proceedings of the 8th International Conference on Computational Science (ICCS), pages 509–518. Springer-Verlag, 2008. doi: 10.1007/978-3-540-69384-0 56. [13] G. B. Dantzig and M. N. Thapa. Linear Programming 1: Introduction. Springer-Verlag, 1997. [14] M. Dorigo and G. Di Caro. The Ant Colony Optimization Meta-Heuristic. In New Ideas in Optimization, pages 11–32. McGraw-Hill, 1999. [15] J. Edmonds. Matroids and the greedy algorithm. In Mathematical Programming, volume 1, pages 127–136. Springer-Verlag, 1971. doi: 10.1007/BF01584082, issn: 0025-5610.

BIBLIOGRAFIE

109

[16] J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. ACM, 19(2):248–264, 1972. doi: 10.1145/321694.321699. [17] J. Famaey, W. De Cock, T. Wauters, F. De Turck, B. Dhoedt, and P. Demeester. A LatencyAware Algorithm for Dynamic Service Placement in Large-Scale Overlays. In Proceedings of the 11th IFIP/IEEE International Symposium on Integrated Network Management (IM), pages 414–421. IEEE Computer Society, 2009. doi: 10.1109/INM.2009.5188843. [18] J. Famaey, S. Latré, J. Strassner, and F. De Turck. A Hierarchical Approach to Autonomic Network Management. In Proceedings of the 12th IFIP/IEEE Network Operations and Management Symposium (NOMS), pages 225–232. IEEE Computer Society, 2010. doi: 10.1109/NOMSW.2010.5486571. [19] J. Famaey, T. Wauters, F. De Turck, B. Dhoedt, and P. Demeester. Dynamic Overlay Node Activation Algorithms for Large-Scale Service Deployments. In Proceedings of the 19th IFIP/IEEE International Workshop on Distributed Systems: Operations and Management (DSOM), pages 14–27. Springer-Verlag, 2008. doi: 10.1007/978-3-540-87353-2 2. [20] J. Famaey, T. Wauters, F. De Turck, B. Dhoedt, and P. Demeester. Towards Efficient Service Placement and Server Selection for Large-Scale Deployments. In Proceedings of the 4th Advanced International Conference on Telecommunications (AICT), pages 13–18. IEEE Computer Society, 2008. doi: 10.1109/AICT.2008.46. [21] A. V. Goldberg and R. E. Tarjan. Finding Minimum-Cost Circulations by Canceling Negative Cycles. ACM, 36(4):873–886, 1989. doi: 10.1145/76359.76368. [22] D. E. Goldberg and K. Deb. A Comparative Analysis of Selection Schemes Used in Genetic Algorithms. In Foundations of Genetic Algorithms, pages 69–93. Morgan Kaufmann, 1991. doi: 10.1.1.101.9494. [23] IBM. ILOG CPLEX Optimization Studio, 1988. Accessed online in May 2013 at http: //www-03.ibm.com/software/products/us/en/ibmilogcpleoptistud/. [24] A. Karve, T. Kimbrel, G. Pacifici, M. Spreitzer, M. Steinder, M. Sviridenko, and A. Tantawi. Dynamic Placement for Clustered Web Applications. In Proceedings of the 15th International Conference on World Wide Web (WWW), pages 595–604. ACM, 2006. doi: 10.1145/1135777.1135865.

110

BIBLIOGRAFIE

[25] J. Kennedy and R. Eberhart. Particle Swarm Optimization. In Proceedings of the 4th IEEE International Conference on Neural Networks (ICNN), volume 4, pages 1942–1948. IEEE Computer Society, 1995. doi: 10.1109/ICNN.1995.488968. [26] J.O. Kephart and R. Das. Achieving Self-Management via Utility Functions. IEEE Transactions on Internet Computing, 11(1):40–48, 2007. doi: 10.1109/MIC.2007.2. [27] T. Kimbrel, M. Steinder, M. Sviridenko, and A. Tantawi. Dynamic Application Placement Under Service and Memory Constraints. In Proceedings on the 4th International Workshop on Experimental and Efficient Algorithms (WEA), pages 391–402. Springer-Verlag, 2005. doi: 10.1007/11427186 34. [28] D. Krafzig, K. Banke, and D. Slama. Enterprise SOA: Service-Oriented Architecture Best Practices. Prentice Hall, 2004. isbn: 0-13146-575-9. [29] A. H. Land and A. G. Doig. An Automatic Method for Solving Discrete Programming Problems. Econometrica, 28(3):497–520, 1960. [30] Y. Li, F. Chen, X. Sun, M. Zhou, W. Jiao, D. Cao, and H. Mei. Self-Adaptive Resource Management for Large-Scale Shared Clusters. Computer Science and Technology, 25(5):945– 957, 2010. doi: 10.1007/s11390-010-1075-6. [31] Z. Li and P. Mohapatra. QRON: QoS-Aware Routing in Overlay Networks. IEEE Journal on Selected Areas in Communications (J-SAC), 22(1):29–40, 2004. doi: 10.1109/JSAC.2003. 818782. [32] C. Low. Decentralised Application Placement. Future Generation Computer Systems, 21(2):281–290, 2005. doi: 10.1016/j.future.2003.10.003. [33] P. Mell and T. Grance. The NIST Definition of Cloud Computing. Technical report, National Institute of Standards and Technology (NIST), Information Technology Laboratory, 2011. Accessed online in October 2012 at http://csrc.nist.gov/publications/ nistpubs/800-145/SP800-145.pdf. [34] A. Metzger, P. Heymans, K. Pohl, P.-Y. Schobbens, and G. Saval. Disambiguating the Documentation of Variability in Software Product Lines: A Separation of Concerns, Formalization and Automated Analysis. In Proceedings of the 15th IEEE International Con-

BIBLIOGRAFIE

111

ference on Requirements Engineering (RE), pages 243–253. IEEE Computer Society, 2007. doi: 10.1109/RE.2007.61. [35] R. Mietzner and F. Leymann. Generation of BPEL Customization Processes for SaaS Applications from Variability Descriptors. In Proceedings of the 2008 IEEE International Conference on Services Computing (SCC), volume 2, pages 359–366. IEEE Computer Society, 2008. doi: 10.1109/SCC.2008.85. [36] R. Mietzner and F. Leymann. Towards Provisioning the Cloud: On the Usage of MultiGranularity Flows and Services to Realize a Unified Provisioning Infrastructure for SaaS Applications. In Proceedings of the 2008 IEEE International Congress on Services - Part I, pages 3–10. IEEE Computer Society, 2008. doi: 10.1109/SERVICES-1.2008.36. [37] R. Mietzner, A. Metzger, F. Leymann, and K. Pohl. Variability Modeling to Support Customization and Deployment of Multi-Tenant-Aware Software as a Service Applications. In Proceedings of the 2009 ICSE Workshop on Principles of Engineering Service Oriented Systems (PESOS), pages 18–25. IEEE Computer Society, 2009. doi: 10.1109/PESOS.2009.5068815. [38] R. Miller. Data Center Knowledge: A Look Inside Amazon’s Data Centers, 2011. Accessed online in October 2012 at http://www.datacenterknowledge.com/archives/2011/06/ 09/a-look-inside-amazons-data-centers. [39] M. Mitchell. An Introduction to Genetic Algorithms. MIT Press, 1998. isbn: 0262631857. [40] H. Moens, J. Famaey, S. Latré, B. Dhoedt, and F. De Turck. Design and Evaluation of a Hierarchical Application Placement Algorithm in Large Scale Clouds. In Proceedings of the 12th IFIP/IEEE International Symposium on Integrated Network Management (IM), pages 137–144. IEEE Computer Society, 2011. doi: 10.1109/INM.2011.5990684. [41] H. Moens, E. Truyen, S. Walraven, W. Joosen, B. Dhoedt, and F. De Turck. Feature Placement Algorithms for High-Variability Applications in Cloud Environments. In Proceedings of the 2012 IFIP/IEEE Network Operations and Management Symposium (NOMS), pages 17–24. IEEE Computer Society, 2012. doi: 10.1109/NOMS.2012.6211878. [42] H. Moens, E. Truyen, S. Walraven, W. Joosen, B. Dhoedt, and F. De Turck. Network-Aware Impact Determination Algorithms for Service Workflow Deployment in Hybrid Clouds.

112

BIBLIOGRAFIE

In Proceedings of the 8th International Conference on Network and Service Management (CNSM). IEEE Computer Society, 2012. [43] R. Moreno-Vozmediano, R.S. Montero, and I.M. Llorente. Elastic Management of Clusterbased Services in the Cloud. In Proceedings of the 1st Workshop on Automated Control for Datacenters and Clouds (ACDC), pages 19–24. ACM, 2009. doi: 10.1145/1555271.1555277. [44] S. Pandey, W. Linlin, S.M. Guru, and R. Buyya. A Particle Swarm Optimization-Based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments. In Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications (AINA), pages 400–407. IEEE Computer Society, 2010. doi: 10.1109/AINA.2010.31. [45] K. Pohl, G. B¨ ockle, and F. van der Linden. Software Product Line Engineering: Foundations, Principles and Techniques. Springer-Verlag, 2005. isbn: 3-540-24372-0. [46] J. Rumbaugh, I. Jacobson, and G. Booch, editors. The Unified Modeling Language Reference Manual. Addison-Wesley Professional, 1999. isbn: 0-201-30998-X. [47] A. Salman, I. Ahmad, and S. Al-Madani. Particle Swarm Optimization for Task Assignment Problem. Microprocessors and Microsystems, 26(8):363–371, 2002. doi: 10.1016/S01419331(02)00053-4. [48] H. Shachnai and T. Tamir. On Two Class-Constrained Versions of the Multiple Knapsack Problem. Algorithmica, 29(3):442–467, 2001. doi: 10.1007/s004530010057. [49] F. Shahrokhi and D. W. Matula.

The Maximum Concurrent Flow Problem.

ACM,

37(2):318–334, 1990. doi: 10.1145/77600.77620. [50] B. Sotomayor, R.S. Montero, I.M. Llorente, and I. Foster. Capacity Leasing in Cloud Systems using the OpenNebula Engine. In Proceedings of the 1st International Workshop on Cloud Computing and its Applications (CCA). ACM, 2008. [51] B. Sotomayor, R.S. Montero, I.M. Llorente, and I. Foster. Virtual Infrastructure Management in Private and Hybrid Clouds. IEEE Internet Computing, 13(5):14–22, 2009. doi: 10.1109/MIC.2009.119. [52] W. Sun, X. Zhang, C. J. Guo, P. Sun, and H. Su. Software as a Service: Configuration and Customization Perspectives. In Proceedings of the 2008 IEEE International Congress on

BIBLIOGRAFIE

113

Services - Part II, pages 18–25. IEEE Computer Society, 2008. doi: 10.1109/SERVICES2.2008.29. [53] C. Tang, M. Steinder, M. Spreitzer, and G. Pacifici. A Scalable Application Placement Controller for Enterprise Data Centers. In Proceedings of the 16th International Conference on World Wide Web (WWW), pages 331–340. ACM, 2007. doi: 10.1145/1242572.1242618. [54] M. F. Tasgetiren, Y. Liang, M. Sevkli, and G. Gencyilmaz. A Particle Swarm Optimization Algorithm for Makespan and Total Flowtime Minimization in Permutation Flowshop Sequencing Problem. European Journal of Operational Research, 177(3):1930–1947, 2007. doi: 10.1016/j.ejor.2005.12.024. [55] B. Urgaonkar, A.L. Rosenberg, and P.J. Shenoy. Application Placement on a Cluster of Servers. In Proceedings of the 17th IASTED International Conference of Parallel and Distributed Computing Systems (PDCS). IASTED, 2004. doi: 10.1142/S012905410700511X. [56] W. Vogels. A Head in the Cloud: The Power of Infrastructure as a Service. In Proceedings of the 1st International Workshop on Cloud Computing and its Applications (CCA). ACM, 2008. [57] W.E. Walsh, G. Tesauro, J.O. Kephart, and R. Das. Utility Functions in Autonomic Systems. In Proceedings of the 1st International Conference on Autonomic Computing (ICAC), pages 70–77. IEEE Computer Society, 2004. doi: 10.1109/ICAC.2004.1301349. [58] D. Whitley. A Genetic Algorithm Tutorial. Statistics and Computing, 4(2):65–85, 1994. doi: 10.1007/bf00175354. [59] L. A. Wolsey and G. L. Nemhauser. Integer and Combinatorial Optimization. WileyInterscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, 1999. isbn: 0-47135-943-2. [60] F. Wuhib, R. Stadler, and M. Spreitzer. Cloud Environments.

Gossip-based Resource Management for

In Proceedings of the 6th International Conference on Network

and Service Management (CNSM), pages 1–8. IEEE Computer Society, 2010.

doi:

10.1109/CNSM.2010.5691347. [61] X. Yao, Y. Liu, and G. Lin. Evolutionary Programming Made Faster. IEEE Transactions on Evolutionary Computation (TEVC), 3:82–102, 1999.

114

BIBLIOGRAFIE

[62] P.-Y. Yin, S.-S. Yu, P.-P. Wang, and Y.-T. Wang. A Hybrid Particle Swarm Optimization Algorithm for Optimal Task Assignment in Distributed Systems. Computer Standards and Interfaces, 28(4):441–450, 2006. doi: 10.1016/j.csi.2005.03.005. [63] J. Yu, R. Buyya, and K. Ramamohanarao. Workflow Scheduling Algorithms for Grid Computing. In Metaheuristics for Scheduling in Distributed Computing Environments, volume 146 of Studies in Computational Intelligence, pages 173–214. Springer-Verlag, 2008. doi: 10.1007/978-3-540-69277-5 7, isbn: 978-3-540-69260-7. [64] L. Zhang, Y. Chen, R. Sun, S. Jing, and B. Yang. A Task Scheduling Algorithm Based on PSO for Grid Computing. International Journal of Computational Intelligence Research, 4:37–43, 2008. doi: 10.5019/j.ijcir.2008.123.

Lijst van figuren 2.1

Een grafische weergave van cloud computing. . . . . . . . . . . . . . . . . . . . .

6

2.2

Tijdscomplexiteit van polynomiale tijd versus exponentiële tijd. . . . . . . . . . .

12

2.3

Voorstelling van een mogelijk feature model. . . . . . . . . . . . . . . . . . . . . .

20

2.4

Feature matrices: voorstelling van mogelijke applicaties. . . . . . . . . . . . . . .

21

2.5

Management architecturen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.6

Dynamische plaatsing van services op nodes doorheen de tijd. . . . . . . . . . . .

27

3.1

Een grafische voorstelling van het Application Placement Problem. . . . . . . . .

30

4.1

Hiërarchische logische boomstructuur van het netwerk. . . . . . . . . . . . . . . .

47

4.2

Schematische voorstelling van de systeemarchitectuur. . . . . . . . . . . . . . . .

49

4.3

Oplossen van de overbezetting van een beherende server. . . . . . . . . . . . . . .

50

4.4

Doorgeven van het overschot aan aanvragen door beherende servers. . . . . . . .

51

4.5

Gebruiksscenario: behandelen van nieuwe aanvragen voor applicaties. . . . . . .

54

5.1

PSO: Voorstelling van een deeltje. . . . . . . . . . . . . . . . . . . . . . . . . . .

61

5.2

Het Minimum-Cost Flow Problem (MCFP). . . . . . . . . . . . . . . . . . . . . .

63

5.3

GA: Voorstelling van de één-punt kruising.

. . . . . . . . . . . . . . . . . . . . .

74

5.4

GA: Voorstelling van de mutatie van een individu. . . . . . . . . . . . . . . . . .

75

6.1

Logische voorstelling van de hiërarchische boomstructuur bij de vergelijkende studie tussen het ILP algoritme met de ontworpen PSO- en GA-algoritmen. . . . . .

80

6.2

CPU voldane factor (CVF) in functie van de CLF. . . . . . . . . . . . . . . . . .

84

6.3

Request Voldane Factor (RVF) in functie van de CLF. . . . . . . . . . . . . . . .

85

6.4

Aantal gebruikte nodes in functie van de CLF. . . . . . . . . . . . . . . . . . . .

86

6.5

Aantal verplaatsingen in functie van de CLF. . . . . . . . . . . . . . . . . . . . .

88

115

116

LIJST VAN FIGUREN

6.6

Totale netwerkkost in functie van de CLF. . . . . . . . . . . . . . . . . . . . . . .

89

6.7

Verwerkingstijd (logaritmisch, in seconden) in functie van de CLF. . . . . . . . .

90

6.8

Workflow voldoening in functie van de CLF. . . . . . . . . . . . . . . . . . . . . .

94

6.9

CPU voldane factor (CVF) in functie van de CLF. . . . . . . . . . . . . . . . . .

95

6.10 Request Voldane Factor (RVF) in functie van de CLF. . . . . . . . . . . . . . . .

96

6.11 Aantal gebruikte nodes in functie van de CLF. . . . . . . . . . . . . . . . . . . .

97

6.12 Aantal verplaatsingen in functie van de CLF. . . . . . . . . . . . . . . . . . . . .

98

6.13 Totale netwerkkost (x 1000) in functie van de CLF. . . . . . . . . . . . . . . . . .

99

6.14 Verwerkingstijd (in seconden) in functie van de CLF. . . . . . . . . . . . . . . . . 100

Lijst van tabellen 3.1

Gebruikte input variabelen bij het APP . . . . . . . . . . . . . . . . . . . . . . .

31

3.2

Gebruikte beslissingsvariabelen, manipuleerbaar tijdens het APP . . . . . . . . .

32

3.3

Realiseren van een absolute waarde in een optimalisatieprobleem . . . . . . . . .

42

5.1

Gebruikte parameters bij de PSO objectieffunctie. . . . . . . . . . . . . . . . . .

67

6.1

CPU Voldane Factor (CVF) in functie van de CLF. . . . . . . . . . . . . . . . . .

84

6.2

Request voldane factor (RVF) in functie van de CLF.

. . . . . . . . . . . . . . .

85

6.3

Aantal gebruikte nodes in functie van de CLF. . . . . . . . . . . . . . . . . . . .

87

6.4

Aantal verplaatsingen in functie van de CLF. . . . . . . . . . . . . . . . . . . . .

88

6.5

Totale netwerkkost in functie van de CLF. . . . . . . . . . . . . . . . . . . . . . .

89

6.6

Verwerkingstijd (in seconden) voor alle algoritmen in functie van de CLF. . . . .

91

6.7

Workflow voldoening in functie van de CLF. . . . . . . . . . . . . . . . . . . . . .

94

6.8

CPU Voldane Factor (CVF) in functie van de CLF. . . . . . . . . . . . . . . . . .

95

6.9

Request voldane factor (RVF) in functie van de CLF.

. . . . . . . . . . . . . . .

96

6.10 Aantal gebruikte nodes in functie van de CLF. . . . . . . . . . . . . . . . . . . .

97

6.11 Aantal verplaatsingen in functie van de CLF. . . . . . . . . . . . . . . . . . . . .

99

6.12 Totale netwerkkost (x 1000) in functie van de CLF. . . . . . . . . . . . . . . . . .

99

6.13 Verwerkingstijd (in seconden) in functie van de CLF. . . . . . . . . . . . . . . . . 100 6.14 Verwerkingstijd (in seconden) in functie van de CLF - zonder communicatie. . . . 101

117

Lijst van algoritmen 1

Een eenvoudig PSO algoritme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

2

Pseudocode van het PSO APP algoritme: initialiseren van de zwerm. . . . . . . .

62

3

Pseudocode van het SSP algoritme - initieel. . . . . . . . . . . . . . . . . . . . . .

65

4

Pseudocode van het PSO APP algoritme. . . . . . . . . . . . . . . . . . . . . . . .

70

5

Een eenvoudig GA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

6

Pseudocode van het GA APP algoritme. . . . . . . . . . . . . . . . . . . . . . . .

77

119

plaatsing van service workflows in clouds

Recommend Documents