forked from GinnyJI/VM-Placement-Simulator
-
Notifications
You must be signed in to change notification settings - Fork 0
/
EAGLE_MOD.py
218 lines (186 loc) · 8.3 KB
/
EAGLE_MOD.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
# Written by Ginny
from Placement import Placement
import time
from math import sqrt
import sys
class Point:
def __init__(self, x_init, y_init):
self.x = x_init
self.y = y_init
def shift(self, x, y):
self.x += x
self.y += y
def __repr__(self):
return "".join(["Point(", str(self.x), ",", str(self.y), ")"])
def distance(a, b):
return sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2)
def getKey(task):
return task.arrival_time
class EAGLE_MOD(Placement):
# Mem_Abv_Ratio = 0
r0 = 0.1 # Satisfaction factor
R0 = 0.8 # Balance Factor
O1 = Point(1 - R0, R0) # center of quarter circle
O2 = Point(R0, 1 - R0)
def __init__(self):
super(EAGLE_MOD, self).__init__()
self.requestLatency = []
def is_in_SD(self, S): # return true if point is in safety domain
if distance(S, self.O1) <= self.R0 and distance(S, self.O2) <= self.R0:
return True
elif S.x <= (1 - self.R0) and S.y <= (1 - self.R0):
return True
elif S.x >= self.R0 and S.y >= self.R0:
return True
else:
return False
def is_in_AD(self, S): # return true if point is in acceptance domain
E = Point(1, 1)
if distance(S, E) <= self.r0:
return True
else:
return False
def find_best_PM(self, task):
R_max = 0 # store maximum utilization ratio
best_PM_in_AD = None
PM_found_in_AD = False
D_min = sys.maxint # store minimum variance distance
best_PM_in_SD = None
PM_found_in_SD = False
for m in self.cluster:
if m.beingUtilized is True:
if m.availMem >= task.mem and m.availCPU >= task.cpu:
post_mem_ratio = 1 - (m.availMem - task.mem) / m.mem
post_CPU_ratio = 1 - (m.availCPU - task.cpu) / m.CPU
pus = Point(post_mem_ratio, post_CPU_ratio) # posterior usage state
if self.is_in_AD(pus):
R = ((1 - m.availMem / m.mem) + (1 - m.availCPU / m.CPU)) * 0.5 # avarage utilization ratio
if R > R_max:
best_PM_in_AD = m
R_max = R
PM_found_in_AD = True
elif self.is_in_SD(pus): # if m is in AD, no need to check SD
res_util_mean = (post_mem_ratio + post_CPU_ratio) * 0.5
D = distance(pus, Point(res_util_mean, res_util_mean))
if D < D_min:
best_PM_in_SD = m
D_min = D
PM_found_in_SD = True
if PM_found_in_AD:
return best_PM_in_AD
elif PM_found_in_SD:
return best_PM_in_SD
else: # return an unused machine
for m in self.cluster:
if m.beingUtilized is False:
if m.availMem >= task.mem and m.availCPU >= task.cpu:
return m
return None
def find_best_PM_blw_ratio(self, task):
R_max = 0 # store maximum utilization ratio
best_PM_in_AD = None
PM_found_in_AD = False
D_min = sys.maxint # store minimum variance distance
best_PM_in_SD = None
PM_found_in_SD = False
Distance = sys.maxint # store minimum variance distance in empty PMs
best_PM_empty = None
for m in self.cluster:
if m.availMem - self.Mem_Abv_Ratio >= task.mem and m.availCPU - self.CPU_Abv_Ratio >= task.cpu:
m_mem = m.mem - self.Mem_Abv_Ratio
m_cpu = m.CPU - self.CPU_Abv_Ratio
m_avail_mem = m.availMem - self.Mem_Abv_Ratio
m_avail_cpu = m.availCPU - self.CPU_Abv_Ratio
post_mem_ratio = 1 - (m_avail_mem - task.mem) / m_mem
post_CPU_ratio = 1 - (m_avail_cpu - task.cpu) / m_cpu
pus = Point(post_mem_ratio, post_CPU_ratio) # posterior usage state
if m.beingUtilized is True:
if self.is_in_AD(pus):
R = ((1 - m_avail_mem / m_mem) + (1 - m_avail_cpu / m_cpu)) * 0.5 # avarage utilization ratio
if R > R_max:
best_PM_in_AD = m
R_max = R
PM_found_in_AD = True
elif self.is_in_SD(pus): # if m is in AD, no need to check SD
res_util_mean = (post_mem_ratio + post_CPU_ratio) * 0.5
D = distance(pus, Point(res_util_mean, res_util_mean))
if D < D_min:
best_PM_in_SD = m
D_min = D
PM_found_in_SD = True
else:
res_util_mean = (post_mem_ratio + post_CPU_ratio) * 0.5
Dis = distance(pus, Point(res_util_mean, res_util_mean))
if Dis < Distance:
best_PM_empty = m
Distance = Dis
if PM_found_in_AD:
return best_PM_in_AD
elif PM_found_in_SD:
return best_PM_in_SD
else: # return an unused machine
return best_PM_empty
def VMplacement(self):
self.clearResults() # clear results directory
start_time = time.time()
print start_time
current_time = 0
unplaced_tasks = self.tasks[:]
backlogged_tasks = []
firstFailureAlready = False
machine_empty = False
enough_resource = True
self.update_ratio()
# Fetch VM requests
while unplaced_tasks:
machine_empty = self.updateMachines(current_time)
enough_resource = True
task_end_time = 0 # store the latest task coming time
while unplaced_tasks:
if unplaced_tasks[0].arrival_time > task_end_time:
task_end_time = unplaced_tasks[0].arrival_time
if unplaced_tasks[0].arrival_time <= current_time:
backlogged_tasks.append(unplaced_tasks.pop(0))
else:
break
if backlogged_tasks:
for task in backlogged_tasks:
# PM = self.find_best_PM_blw_ratio(task)
# if PM is not None:
# self.place_task(task, PM, current_time)
# continue
PM = self.find_best_PM(task)
if PM is not None:
self.place_task(task, PM, current_time)
else:
if current_time % 10 == 0 or (len(unplaced_tasks) == 0):
self.getResults(current_time)
current_time += 1
continue
for task in backlogged_tasks:
if task.hostMachine == None:
unplaced_tasks.append(task)
enough_resource = False
backlogged_tasks = []
if not enough_resource:
print "EAGLE MOD: not enough resource for all tasks, time", current_time
unplaced_tasks.sort(key=getKey, reverse=False)
if not firstFailureAlready:
self.getFirstFailureResult() # First Failure Utilization Check
firstFailureAlready = True
if current_time % 1 == 0 or (len(unplaced_tasks) == 0):
self.getResults(current_time)
current_time += 1
# if enough_resource and not unplaced_tasks: #VM placement finished
# if not enough_resource:
if current_time > task_end_time: # heavy workload case VM placement finished
end_time = time.time()
print end_time
self.getTimeResult(float(end_time - start_time))
break
self.getResourceFragmentation()
self.getFailureNum()
def getResults(self, current_round):
super(EAGLE_MOD, self).getResults(current_round)
def __str__(self):
return "EAGLE MOD"