Resource Mapping Optimization for Distributed Cloud Services - PhD Thesis Defense

Resource Mapping Optimization for Distributed Cloud Services
Resource Mapping Optimization
for Distributed Cloud Services
PhD Thesis Defense
Atakan Aral
Thesis Advisor: Asst. Prof. Dr. Tolga Ovatman
Istanbul Technical University – Department of Computer Engineering
November 3, 2016

Introduction
Motivation
Outline
1 Introduction
Motivation
Preliminary Information
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
3 Replication Management
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Introduction
Motivation
Motivation

Introduction
Motivation
Motivation
Scientiﬁc computing
Internet of Things
Finance services
Health care systems
e-Learning
(Mobile) image processing, VR
Social networking
On-demand or live video streaming
Online gaming
. . .
Real time, distributed, data- and computation-intensive cloud services
need low latency and low-cost communication.

Introduction
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Introduction
Cloud Computing
Deﬁnition
Applications and services that run on a distributed network using virtualized
resources and accessed by common Internet protocols and networking standards.
Broad network access: Platform-independent, via standard methods
Measured service: Pay-per-use, e.g. amount of storage/processing power,
number of transactions, bandwidth etc.
On-demand self-service: No need to contact provider to provision resources
Rapid elasticity: Automatic scale up/out, illusion of inﬁnite resources
Resource pooling: Abstraction, virtualization, multi-tenancy

Introduction
Cloud Computing – Service Models

Introduction
Cloud Computing – Deployment Models

Introduction
Inter-Cloud
Deﬁnition
A cloud model that allows on-demand reassignment of resources and transfer of
workload through an interworking of cloud systems of different cloud providers.
Depending on the initiator of the Inter-Cloud endeavour:
Cloud Federation: A voluntary collaboration between a group of cloud
providers to exchange their resources
Multi-Cloud: An uninformed combination of multiple clouds by a service
provider to host the components of the service

Introduction
Edge Computing
Deﬁnition
Pushing the frontier of computing applications, data, and services away from
centralized nodes to the logical extremes of a network (e.g. mobile devices,
sensors, micro data centers, cloudlets, routers, modems, . . .
Low latency access to powerful computing resources
Cyber-foraging: Computation or data ofﬂoading from mobile devices to
servers for extending computation power, storage capacity and/or battery life.

Introduction
General Problem
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Introduction
General Problem
General Problem
Deployment on multiple clouds can beneﬁt cloud services
Allows seemingly inﬁnite scalability,
Provides better geographical coverage,
Avoids vendor lock-in and eases hybridization,
Increases fault tolerance and availability,
Allows exploiting differences in pricing schemes, . . .
Business solutions that allow basic inter-cloud deployment are already here,
e.g. Nuvla, EGI, RightScale, Equinix, . . .
However, such solutions leave cloud data center selection to user.
There is no automatic mapping between provider resources and user
requirements.

Introduction
General Problem
General Problem (continued)
Resource mapping in distributed cloud is a complex problem due to factors
such as:
Multiple objectives and perspectives (QoS, access latency, throughput,
availability, cost, proﬁt, . . . ),
Constraints (SLAs, processing capacity, network bandwidth, energy
consumption, . . . ),
Geographical distribution and nonuniform network conditions,
Heterogeneity and dynamicity of both entities (i.e. resources and requests),
The large number of the entities (especially in the case of Edge Computing),
Inter-dependencies among the components that constitute a cloud service (e.g.
Virtual Machines, Databases).

Introduction
Solution Proposal
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Introduction
Solution Proposal
Proposed Solution
Hypothesis
Employing resource mapping algorithms that consider and utilize structural
characteristics of the distributed cloud services would increase the QoS
experienced by service users in a cost-efﬁcient way.
QoS indicators are: (i) access latency to the service, (ii) access latency
between dependent components, and (iii) access latency to the data.
Cost indicators are: (i) VM provisioning cost, (ii) data storage cost, and (iii)
data transfer (bandwidth) cost.

V MnV M1 V M2
...
Service ModelEntity
Cloud based Service SaaS
Resource Mapper PaaS
Topology Mapper Replication Manager
• Replica Placement
• Replica Discovery
• Network Embedding
• Resource Allocation
DB
Cloud Infrastructure IaaS
DC1
DC2
DC4 DC5
DC3

Topology Mapping
Motivating Example
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Topology Mapping
Motivating Example
Motivating Example
A small cloud-based navigation service for public transportation
Two-tier architecture: User interface and route planning
VM 1: 8 CPU cores, 16 GB memory, 2 TB HDD storage
VM 2: 32 CPU cores, 60 GB memory, 80 GB SSD storage
500 Mbps of dedicated bandwidth between the two tiers is desired

Topology Mapping
Motivating Example
Motivating Example (continued)
First tier is replicated in two
separate DCs to improve:
Availability
Fault tolerance
Proximity
Second tier is not replicated
due to:
Economical constraints
Uncriticality to the service
But it is still deployed on a
third DC because of:
Pricing differences
Fairness

Topology Mapping
Motivating Example
Motivating Example (continued)
There are 5 (federated) cloud providers in the area.
Not all have dedicated
network connections
between them.
Heterogeneous bandwidth
capacities and latencies
Heterogeneous resource
capacities and loads
How to map user virtual machines to cloud data centers?

Topology Mapping
Problem Definition
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Definition
Solution Details
Evaluation
Motivating Examples
Problem Definition
Solution Details
Evaluation
4 Conclusion

Topology Mapping
Problem Deﬁnition
Virtual Machine Cluster Embedding
Mapping VM clusters across inter-cloud infrastructure (node & edge mapping)
Reduce inter-cloud latency
Reduce makespan
Reduce resource costs
Optimize bandwidth
utilization
Increase system throughput
Increase acceptance rate
Increase revenue
CP4
CP1
CP5
CP2
CP3
VM1 VM3VM2
CP4
CP1
CP5
CP2VM1
VM2VM3
CP3

Topology Mapping
Problem Deﬁnition
Virtual Machine Cluster Embedding (continued)
GC = VC, EC, AV
C, AE
C
GF = VF , EF , AV
F , AE
F
∀ (v ∈ VC) ∃ v ∈ VF | v → v
∀ (e ∈ EC) ∃ E ⊆ EF | e → E
Validity conditions:
1 Capacity sufﬁciency
2 Path creation
3 No cycle forming
CP4
CP1
CP5
CP2
CP3
VM1 VM3VM2
CP4
CP1
CP5
CP2VM1
VM2VM3
CP3
f = (VM1 → CP3, VM2 → CP5, VM3 → CP4)
g = D1,2 → {C1,3, C3,5}, D2,3 → {C4,5}

Topology Mapping
Solution Details
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Topology Mapping
Solution Details
Topology based Mapping (TBM) Algorithm
Map VM clusters to the subgraphs of the federation topology that are
isomorphic to their topology.
Mapping function f is injective and ∀ (e ∈ EC) ∃ (E ⊆ EF ) | e → E ∧ |E | = 1
In case of multiple alternatives, choose by average latency to the user.
Fall back to a greedy heuristic in case of failure.
Instead, map to a homeomorphic subgraph where |E | ≥ 1

Topology Mapping
Solution Details
Topology based Mapping (TBM) Algorithm (continued)

Topology Mapping
Evaluation
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Topology Mapping
Evaluation
Experimental Setup
Simulated on the RalloCloud framework which is based on CloudSim.
Federation topology is taken from the FEDERICA project and contains 14
clouds across Europe.
Virtual machine clusters are randomly generated based on population density.
Simulation period is 50 hours.

Resource Mapping Optimization for Distributed Cloud Services - PhD Thesis Defense

Topology Mapping
Evaluation
Results (1/4)

Topology Mapping
Evaluation
Results (2/4)

Topology Mapping
Evaluation
Results (3/4)

Topology Mapping
Evaluation
Results (4/4)

Replication Management
Motivating Examples
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Motivating Examples
Sport Event

Motivating Examples
Trafﬁc

Motivating Examples
Motivating Examples
Edge Computing provides low-latency access to computing resources for
mobile code offloading.
However, many services need to access data that is stored centrally due to:
Limited storage capacity of the edge entities
Economic constraints
Availability for offline analysis
Simpler maintenance and concurrency control
High latency to central storage harms QoS.
How to decide the number and location of data replicas so that the data
access latency is decreased in a cost efficient way?

Motivating Examples
Locality of Reference
The patterns that the user data accesses exhibit: Temporal Locality, Spatial
Locality, and Geographical Locality
[0,0.5)
[0.5,1)
[1,1.5)
[1.5,2)
[2,2.5)
[2.5,3)
[3,3.5)
[3.5,4)
[4,4.5)
[4.5,5)
[5,5.5)
[5.5,6)
[6,6.5)
[6.5,7)
[7,7.5)
[7.5,8)
[8,8.5)
[8.5,9)
[9,9.5)
[9.5,10)
[10,10.5)
[10.5,11)
[11,11.5)
[11.5,12)
[12,12.5)
[12.5,13)
[13,13.5)
[13.5,14)
[14,14.5)
[14.5,15)
[15,15.5)
[15.5,16)
[16,16.5)
[16.5,17)
[17,17.5)
[17.5,18)
[18,18.5)
[18.5,19)
[19,19.5)
[19.5,20)
0
2
4
6
·104
Distance (1, 000 × km)
NumberofRequestPairs
The CAIDA Anonymized Internet Traces 2015 Dataset (2.3 Billion IPv4 packets)

Problem Definition
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Definition
Solution Details
Evaluation
Motivating Examples
Problem Definition
Solution Details
Evaluation
4 Conclusion

Problem Deﬁnition
Edge Replica Placement
a
c
b d cs
1 Which data objects to replicate?
2 When to create/destroy a replica?
3 How many replicas for each object?
4 Where to store each replica?
5 How to redirect requests to the
closest replica?
In order to minimize average replica-to-client distance in a bandwidth-
and cost-effective way.

Problem Deﬁnition
Facility Location Problem
minimize :
j
fj · Yj +
i j
hi · dij · Xij
fj = unit_pricej · replica_size · epoch
hi = num_requestsi · replica_size
dij = latencyij · λ

Problem Deﬁnition
Requirements
Centralized solutions are not feasible due to the large number of entities.
The solution must be distributed with minimal input and communication.
Edge users continuously enter and leave the network topology through
connections with nonuniform latencies.
The solution must be dynamic and online.
Edge entities should be aware of the closest replica when they need a certain
data object.
A Replica Discovery technique is necessary.

Solution Details
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Solution Details
Decentralized Replica Placement (D-ReP) Algorithm
Storage nodes that host replicas act as local optimizers.
They evaluate experienced demand, storage cost as well as expected latency
improvement to carry out either:
Duplication num_requestsknh · latencynh · λ > unit_pricen · epoch
Migration (num_reqsknh − i∈N
i=n
num_reqskih) · latencynh · λ >
unit_pricen − unit_priceh · epoch
Removal i∈N num_requestskih < original_num_requestsh · α
The replicas are incrementally pushed from the central storage to the edge.
λ allows user to control the trade-off between cost- and latency-optimization.

Solution Details
Replica Discovery
Only the most relevant nodes are notiﬁed of the replica creations or removals.
Temporal locality: requesters of the source during the n most recent epochs
Geographical locality: m-hop sphere of the destination
Each active node keeps a Known Replica Locations (KRL) table.

Evaluation
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Evaluation
Experimental Setup
Simulated on the RalloCloud framework which is based on CloudSim.
The CAIDA Anonymized Internet Traces 2015 Dataset: IPv4 packets data
from February 19, 2015 between 13:00-14:00 (UTC) which contains more
than 2.3 Billion records
GeoLite2 IP geolocation database
Synthetic workloads based on uniform, exponential, normal, Chi-squared, and
Pareto distributions of request locations
Barabási–Albert scale-free network generation model: 1000 nodes, 2994
edges, and a heavy-tailed distribution of bandwidth in [10, 1024] mbps
Amazon Web Services S3 prices

Evaluation
Results (1/4)

Evaluation
Results (2/4)

Evaluation
Results (3/4)

Conclusion
Outline
1 Introduction
Motivation
General Problem
Solution Proposal
2 Topology Mapping
Motivating Example
Problem Deﬁnition
Solution Details
Evaluation
Motivating Examples
Problem Deﬁnition
Solution Details
Evaluation
4 Conclusion

Conclusion
Contribution
Topology Mapping Algorithm1 4 5
First attempt to employ subgraph isomorphism to ﬁnd a injective match between
virtual and physical cloud/grid topologies
First to explicitly evaluate network latency for the VMNE
Minimum Span Heuristic3 5
Novel heuristic algorithm to defer MIP
Decentralized Replica Placement Algorithm2 5
First completely decentralized, partial-knowledge replica placement algorithm
KRL based Discovery Technique2
Novel replica discovery technique with low overhead
RalloCloud: A simulation environment for Inter-Cloud resource mapping1
First simulator for inter-cloud systems

Conclusion
Publications
1 Aral, A., and Ovatman, T. 2016. Network-Aware Embedding of Virtual Machine Clusters onto Federated
Cloud Infrastructure. The Journal of Systems and Software, vol. 120, pp. 89-104. DOI:
10.1016/j.jss.2016.07.007
2 Aral, A., and Ovatman, T. 2017?. A Decentralized Replica Placement Algorithm for Edge Computing.
Under review in The IEEE Transactions on Parallel and Distributed Systems.
3 Aral, A., and Ovatman, T. 2014. Improving Resource Utilization in Cloud Environments using Application
Placement Heuristics. In 4th Int’l. Conf. on Cloud Comp. and Services Science (CLOSER 2014), pp.
527-534.
4 Aral, A., and Ovatman, T. 2015. Subgraph Matching for Resource Allocation in the Federated Cloud
Environment. In IEEE 8th International Conference on Cloud Computing (IEEE CLOUD 2015), pp.
1033-1036.
5 Aral, A. 2016. Network-Aware Resource Allocation in Distributed Clouds. IEEE International Conference
on Cloud Engineering (IC2E 2016), Doctoral Symposium.

Conclusion
Future Work
Standardization of cloud APIs
Real-time performance and cost guarantees
Service self-awareness
Load balancing and fairness between cloud providers
Fault tolerance and availability

Conclusion
Thank you for your time.

Literature Review
Appendices
5 Literature Review
6 RalloCloud
7 Algorithm Details
8 Intra-Cloud Mapping
9 Subgraph Matching
10 Complete Results

Literature Review
Virtual Network Embedding
Cloud Federation Embedding Entity Simultaneous NW-Aware
TBM VMs
[30] VMs
[31] VMs
[32] Serv.
[33] Tasks
[34] VMs
[35] VNs
[22] VMs
[36] VMs
[37] VNs
[25] VMs
[38] VNs

Literature Review
TBM VMs
[39] VNs
[40] VNs
[41] VMs
[42] VNs
[43] VNs
[44] VMs
[45] VNs
[46] VMs
[47] VNs
[48] Tasks
[49] VNs

Literature Review
TBM VMs
[50] VNs
[51] VMs
[52] Jobs
[53] WEs

Literature Review
[25] Tordsson, J., Montero, R.S., Moreno-Vozmediano, R. and Llorente, I.M. (2012). Cloud brokering
mechanisms for optimized placement of virtual machines across multiple providers, Future Generation
Computer Systems, 28(2), 358–367.
Exact solution with IP, cloud brokerage and uniform interface
[35] Leivadeas, A., Papagianni, C. and Papavassiliou, S. (2013). Efﬁcient resource mapping framework over
networked clouds via iterated local search-based request partitioning, IEEE Transactions on Parallel and
Distributed Systems, 24(6), 1077–1086.
Graph partitioning, IP based embedding, no latency consideration
[38] Xin, Y., Baldine, I., Mandal, A., Heermann, C., Chase, J. and Yumerefendi, A. (2011). Embedding virtual
topologies in networked clouds, Proceedings of the 6th International Conference on Future Internet
Technologies, ACM, pp.26–29.
Connected components of the VM cluster topology are merged,
isomorphic subgraph to the resulting graph is sought

Literature Review
Replica Placement (Centralized)
P D Environment Topology Objectives
[68] Web Tree Proximity
[69] CDN Unrestricted Proximity
[70] N/A Unrestricted Proximity
[71] Data Grid Tree Proximity, Cost, Load Balance
[72] N/A Tree Proximity
[73] N/A Unrestricted Proximity
[65] Cloud Unrestricted Proximity
[74] Cloud Unrestricted Bandwidth, Load Balance
[67] Cloud Unrestricted Proximity, Cost
[75] N/A Unrestricted Availability
[76] Data Grid Multi-Tier Proximity, Cost, Bandwidth
[77] CDN Unrestricted Proximity, Cost

Literature Review
Replica Placement (Centralized)
[63] Cloud Unrestricted Prox., Bandwidth, Load Balance
[78] Data Grid Multi-Tier Proximity
[64] Data Grid Unrestricted Prox., Bandwidth, Availability
[66] Cloud-CDN Unrestricted Proximity, Cost
[79] Data Grid Tree Prox., Bandwidth, Availability
[80] Data Grid Multi-Tier Proximity, Bandwidth
[81] Cloud Tree Proximity, Availability
[82] Cloud Unrestricted Bandwidth, Load Balance
[83] Cloud-CDN Unrestricted Cost, Availability
[84] Cloud (Mobile) Unrestricted Proximity, Availability

Literature Review
Replica Placement (Decentralized)
[89] Cloud-CDN Unrestricted Proximity
[90] Cloud Complete Prox., Cost, Bandwidth, Avail.
[91] Data Grid Unrestricted Prox., Cost, Bandwidth, Avail.
[92] P2P Unrestricted Cost, Bandwidth, Availability
[93] Web Unrestricted Proximity, Bandwidth
[94] N/A Multi-Tier Proximity, Bandwidth
[88] Web Unrestricted Prox., Cost, Load B., Bandwidth
[95] P2P Unrestricted Proximity, Cost
[87] Web Unrestricted Proximity, Cost
[96] Web Unrestricted Proximity, Cost
D-ReP Cloud Unrestricted Proximity, Cost, Bandwidth

Literature Review
Replica Placement
[90] Bonvin, N., Papaioannou, T.G. and Aberer, K. (2010). A self-organized, fault-tolerant and scalable replica-
tion scheme for cloud storage, Proceedings of the 1st ACM symposium on Cloud computing, pp. 205–216.
Game theoretical, replicate/migrate autonomously, each node is aware of
other replicas, prices, demand, bandwidth, . . .
[95] Shen, H. (2010). An efficient and adaptive decentralized file replication algorithm in P2P file sharing
systems, IEEE Transactions on Parallel and Distributed Systems, 21(6), 827–840.
Replicas on data access path intersections (traffic hubs), traffic analysis
[87] Pantazopoulos, P., Karaliopoulos, M. and Stavrakakis, I. (2014). Distributed placement of autonomic
internet services, IEEE Transactions on Parallel and Distributed Systems, 25(7), 1702–1712.
[96] Smaragdakis, G., Laoutaris, N., Oikonomou, K., Stavrakakis, I. and Bestavros, A. (2014). Distributed
server migration for scalable Internet service deployment, IEEE/ACM Trans. on NW, 22(3), 917–930.
Solve FLP in an r-ball, centrality, demand and FLP decisions are broadcasted

RalloCloud
Appendices
5 Literature Review
6 RalloCloud
7 Algorithm Details
9 Subgraph Matching
10 Complete Results

RalloCloud
Entity Relationship Diagram

RalloCloud
Network Modeling
Requested bandwidth between two VMs is allocated from all edges on the
shortest path between the clouds to which two VMs are deployed.
Three types of latency are considered:
Deployment Latency = M +
i∈P1
Li +
S
B
Communication Latency =
i∈P2
Li +
D
B
Data Access Latency =
i∈P3
Li +
D
B

RalloCloud
Cost Modeling
Static Pricing and Trough Filling strategies
Total Service Cost =
i∈VC j∈AV
C
resource_sizeij · unit_priceij · durationij
+
i∈EC
resource_sizei · unit_pricei · durationi
+
i
replica_sizei · unit_pricei · durationi

RalloCloud
Performance Criteria
Criteria
Temporal
Latency
Cloud-to-User Latency
Hop Count
Inter-Cloud Latency
Duration
Completion Time
Execution Time
Makespan
SLA Violations
Volumetrical
Throughput
Utilization Rate
Economical
Beneﬁt-Cost Ratio
Resource Cost
Revenue
Distributional
Distribution Rate
Load Balance
Other
Acceptance/Rejection Rate
Fairness

Algorithm Details
Appendices
5 Literature Review
6 RalloCloud
7 Algorithm Details
9 Subgraph Matching
10 Complete Results

Algorithm Details
TBM

Algorithm Details
Replica Discovery

Algorithm Details
D-ReP
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
User demand locations
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
ITERATION 1d: User demand received from c and f
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
ITERATION 1d: Cache creation decision
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
ITERATION 2f: Migration decision
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
ITERATION 2c: Duplication decision
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
ITERATION 3e: Migration decision
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
ITERATION 3a: Migration decision
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Algorithm Details
ITERATION 3c: Removal decision
a
b
c
d
f
e
a1
a2
a3
a4
e1
b3
b2
b1
e4
e2
e3
f3
d1
f1
f2
d2
c1 c2

Intra-Cloud Mapping
Appendices
5 Literature Review
6 RalloCloud
7 Algorithm Details
9 Subgraph Matching
10 Complete Results

Intra-Cloud Mapping
Virtual Machine Cluster Embedding
Allocation of PMs to VMs in a single cloud data center.
Increase resource
utilization
Increase data center
throughput
Increase acceptance rate
Increase revenue
#PMs
i=0


#VMs
j=0
A[i][j] = 1


#PMs
i=0
#Res
j=0




#VMs
k=0
A[i][k] × RR[j][k]

 ≤ AR[i][j]



Intra-Cloud Mapping
Minimum Span Heuristic
Map a VM to the PM with the maximum resource utilization evenness.
Span(p) = maxi∈[1,m] (ri) − mini∈[1,m] (ri)
Fall back to a Mixed Integer Programming (MIP) solution in case of failure.

Intra-Cloud Mapping
Pseudo Code

Intra-Cloud Mapping
Other Heuristics
SD(v) =
m
i=1
(ri − ¯r)2
CD(v) =
m
i=1
m
j=1 |ri − rj|
2
DM(v) =
n
i=1
ri − min
j∈[1,m]
rj
SK(v) =
m
i=1
ri
¯r
− 1
2

Intra-Cloud Mapping
Results (1/2)
0%
1%
2%
3%
4%
5%
6%
7%
8%
9%
10%
11%
12%
13%
14%
15%
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
3 4 5 6 7 8 9 10 11 12
ImprovementRate
NumberofAssignedApplications
VM Count
GR HR Improvement
PM
VMs
10.8% perfect
placement
12.1% more VMs
34.5% less
migrations

Intra-Cloud Mapping
Results (2/2)

Subgraph Matching
Appendices
5 Literature Review
6 RalloCloud
7 Algorithm Details
9 Subgraph Matching
10 Complete Results

Subgraph Matching
Subgraph Matching
Search space is all possible injective matchings from the set of pattern nodes
to the set of target nodes.
Systematically explore the search space:
Start from an empty matching
Extend the partial matching by matching a non matched pattern node to a non
matched target node
Backtrack if some edges are not matched
Repeat until all pattern nodes are matched (success) or all matchings are
already explored (fail).
Filters are necessary to reduce the search space by pruning branches that do
not contain solutions.

Subgraph Matching
LAD Filtering

Subgraph Matching
LAD Filtering
D1 = D3 = D5 = D6 = A, B, C, D, E, F, G
D2 = D4 = A, B, D

Complete Results
Appendices
5 Literature Review
6 RalloCloud
7 Algorithm Details
9 Subgraph Matching
10 Complete Results

Complete Results
Complete Results

Complete Results
Complete Results
[0,25)
[25,50)
[50,75)
[75,100)
[100,125)
[125,150)
[150,175)
[175,200)
[200,225)
[225,250)
[250,275)
[275,300)
[300,325)
[325,350)
[350,375)
[375,400)
[400,425)
[425,450)
[450,475)
[475,500)
[500,525)
[525,550)
[550,575)
[575,600)
[600,625)
[625,650)
[650,675)
[675,700)
[700,725)
[725,750)
[750,775)
[775,800)
[800,825)
[825,850)
[850,875)
[875,900)
[900,925)
[925,950)
[950,975)
[975,1,000)
0
500
1,000
Generated Grid Coordinates
Uniform Distribution
Exponential Distribution

Complete Results
Complete Results
[0,25)
[25,50)
[50,75)
[75,100)
[100,125)
[125,150)
[150,175)
[175,200)
[200,225)
[225,250)
[250,275)
[275,300)
[300,325)
[325,350)
[350,375)
[375,400)
[400,425)
[425,450)
[450,475)
[475,500)
[500,525)
[525,550)
[550,575)
[575,600)
[600,625)
[625,650)
[650,675)
[675,700)
[700,725)
[725,750)
[750,775)
[775,800)
[800,825)
[825,850)
[850,875)
[875,900)
[900,925)
[925,950)
[950,975)
[975,1,000)
0
1,000
2,000
Normal Distribution (σ = 50)

Complete Results
Complete Results
[0,25)
[25,50)
[50,75)
[75,100)
[100,125)
[125,150)
[150,175)
[175,200)
[200,225)
[225,250)
[250,275)
[275,300)
[300,325)
[325,350)
[350,375)
[375,400)
[400,425)
[425,450)
[450,475)
[475,500)
[500,525)
[525,550)
[550,575)
[575,600)
[600,625)
[625,650)
[650,675)
[675,700)
[700,725)
[725,750)
[750,775)
[775,800)
[800,825)
[825,850)
[850,875)
[875,900)
[900,925)
[925,950)
[950,975)
[975,1,000)
0
2,000
4,000
Chi-Squared Distribution (degree o f freedom = 1)

Complete Results
Complete Results
[0,25)
[25,50)
[50,75)
[75,100)
[100,125)
[125,150)
[150,175)
[175,200)
[200,225)
[225,250)
[250,275)
[275,300)
[300,325)
[325,350)
[350,375)
[375,400)
[400,425)
[425,450)
[450,475)
[475,500)
[500,525)
[525,550)
[550,575)
[575,600)
[600,625)
[625,650)
[650,675)
[675,700)
[700,725)
[725,750)
[750,775)
[775,800)
[800,825)
[825,850)
[850,875)
[875,900)
[900,925)
[925,950)
[950,975)
[975,1,000)
0
1,000
2,000
Pareto Distribution (scale = 1, shape = 3)

Resource Mapping Optimization for Distributed Cloud Services - PhD Thesis Defense

Recommended

More Related Content

What's hot (20)

Viewers also liked (16)

Similar to Resource Mapping Optimization for Distributed Cloud Services - PhD Thesis Defense (20)

More from AtakanAral (15)

Recently uploaded (20)

Resource Mapping Optimization for Distributed Cloud Services - PhD Thesis Defense