ioftools / mrai_setter / mrai_setter.py @ 62798f6e
History  View  Annotate  Download (12.6 KB)
1 
#!/usr/bin/env python3


2 
# Author: Luca Baldesi 2019

3  
4 
import sys 
5 
import networkx as nx 
6 
import functools 
7 
import random 
8 
import os 
9  
10 
import milaniBGPLoad as mice 
11  
12  
13 
strategies = [] 
14 
default_mrai = 30.0

15 
percentage_constant = 20

16  
17  
18 
def usage(name): 
19 
print("Usage:")

20 
print(f"\t{name} <graphml_file> <strategy> [<advertising_node>]")

21 
print("\nAvailable strategies:")

22 
pp = "\t"

23 
pp += ", ".join(strategies)

24 
print(pp) 
25  
26  
27 
def bgp_strategy(func): 
28 
""" Wrapper for strategy definition; it adds strategy name to the strategy list.

29 
Strategy name *must not* include an underscore and the function *must* be

30 
called "apply_<strategyname>_strategy".

31 
"""

32 
strategies.append(func.__qualname__.split('_')[1]) 
33 
@functools.wraps(func)

34 
def wrapper(*args, **kwargs): 
35 
return func(*args, **kwargs)

36 
return wrapper

37  
38  
39 
@bgp_strategy

40 
def apply_30secs_strategy(G, adv_node): 
41 
""" set all mrai timers to 30 """

42 
for e in G.edges: 
43 
i, j = e 
44 
G.edges[e]['termination1'] = i

45 
G.edges[e]['termination2'] = j

46 
G.edges[e]['mrai1'] = default_mrai

47 
G.edges[e]['mrai2'] = default_mrai

48  
49  
50 
@bgp_strategy

51 
def apply_none_strategy(G, adv_node): 
52 
""" set all mrai timers to 0 """

53 
for e in G.edges: 
54 
i, j = e 
55 
G.edges[e]['termination1'] = i

56 
G.edges[e]['termination2'] = j

57 
G.edges[e]['mrai1'] = 0.0 
58 
G.edges[e]['mrai2'] = 0.0 
59  
60  
61 
@bgp_strategy

62 
def apply_fabrikant_strategy(G, adv_node): 
63 
""" set mrai timers according to the Fabrikant gadget paper """

64 
fl = fabrikant_levels(G, adv_node) 
65 
print(fl) 
66 
for i in G.nodes: 
67 
if i in fl: 
68 
set_node_mrai(G, i, default_mrai/(2**fl[i]))

69 
else:

70 
set_node_mrai(G, i, default_mrai) 
71  
72  
73 
@bgp_strategy

74 
def apply_constantfabrikant_strategy(G, adv_node): 
75 
""" set mrai timers according to the Fabrikant gadget paper but with a constant decrease"""

76 
fl = fabrikant_levels(G, adv_node) 
77 
for i in G.nodes: 
78 
if i in fl: 
79 
mrai = 30

80 
for level in range(fl[i]): 
81 
mrai = mrai  ((mrai*percentage_constant)/100)

82 
set_node_mrai(G, i, mrai) 
83 
else:

84 
set_node_mrai(G, i, default_mrai) 
85  
86  
87 
@bgp_strategy

88 
def apply_inversefabrikant_strategy(G, adv_node): 
89 
""" set mrai timers according to the Fabrikant gadget paper

90 
but in reverse order """

91 
fl = fabrikant_levels(G, adv_node) 
92 
maxi = max(fl.values())

93 
for i in G.nodes: 
94 
if i in fl: 
95 
set_node_mrai(G, i, default_mrai/(2**(maxifl[i])))

96 
else:

97 
set_node_mrai(G, i, default_mrai) 
98  
99  
100 
@bgp_strategy

101 
def apply_constantinversefabrikant_strategy(G, adv_node): 
102 
""" set mrai timers according to the Fabrikant gadget paper

103 
but in reverse order and with a constant increment"""

104 
fl = fabrikant_levels(G, adv_node) 
105 
maxi = max(fl.values())

106 
for i in G.nodes: 
107 
if i in fl: 
108 
mrai = 30

109 
for level in range(maxifl[i]): 
110 
mrai = mrai  ((mrai * percentage_constant) / 100)

111 
set_node_mrai(G, i, mrai) 
112 
else:

113 
set_node_mrai(G, i, default_mrai) 
114  
115 
@bgp_strategy

116 
def apply_simpleheuristic_strategy(G, adv_node): 
117 
""" set mrai timers so that they slightly increase as updates get

118 
farther and farther from the advertising node """

119 
start_mrai = 0

120 
inc_mrai = 0.5

121 
mrai = {} 
122  
123 
visited_nodes = set()

124 
mrai[adv_node] = start_mrai 
125 
set_node_mrai(G, adv_node, mrai[adv_node]) 
126 
fifo = set()

127 
for j in nx.neighbors(G, adv_node): 
128 
fifo.add((adv_node, j)) 
129  
130 
while len(fifo) > 0: 
131 
i, j = fifo.pop() 
132 
if j not in visited_nodes: 
133 
mrai[j] = mrai[i] + inc_mrai 
134 
set_node_mrai(G, j, mrai[j]) 
135 
visited_nodes.add(j) 
136  
137 
e = G.edges[(i,j)] 
138 
if str(e['customer']) == i: 
139 
for z in nx.neighbors(G, j): 
140 
if z != i and z not in visited_nodes: 
141 
fifo.add((j, z)) 
142 
else:

143 
for z in nx.neighbors(G, j): 
144 
if str(G.edges[(j, z)]['customer']) == z and z not in visited_nodes: 
145 
fifo.add((j, z)) 
146  
147  
148 
@bgp_strategy

149 
def apply_uniformdistrmrai_strategy(G, adv_node): 
150 
""" set mrai chosing the mrai from a uniform distribution between a max and a min value """

151 
max_value = default_mrai 
152 
min_value = (default_mrai*percentage_constant)/100

153 
for e in G.edges: 
154 
i, j = e 
155 
G.edges[e]['termination1'] = i

156 
G.edges[e]['termination2'] = j

157 
G.edges[e]['mrai1'] = round(random.uniform(min_value, max_value), 2) 
158 
G.edges[e]['mrai2'] = round(random.uniform(min_value, max_value), 2) 
159  
160 
@bgp_strategy

161 
def apply_milanicent_strategy(G, adv_node): 
162 
""" set mrai timers so accordingly to Milani centrality (MiCe).

163 
Graph is split in three logic parts. """

164 
T = default_mrai # max mrai in seconds

165 
cent = mice.mice_centrality(G, normalized=True)

166 
visited_nodes = set()

167 
set_node_mrai(G, adv_node, T*cent[adv_node]/2)

168 
fifo = set()

169 
for j in nx.neighbors(G, adv_node): 
170 
fifo.add((adv_node, j)) 
171  
172 
while len(fifo) > 0: 
173 
i, j = fifo.pop() 
174 
if j not in visited_nodes: 
175 
e = G.edges[(i,j)] 
176 
if str(e['customer']) == j: # we are in phase 3 
177 
set_node_mrai(G, j, T*cent[j]/2)

178 
elif G.nodes[j]['type'] == 'T': # we are in phase 2 
179 
set_node_mrai(G, j, T/2)

180 
else: # we are in phase 3 
181 
set_node_mrai(G, j, T*(2cent[j])/2) 
182 
visited_nodes.add(j) 
183  
184 
if str(e['customer']) == i: 
185 
for z in nx.neighbors(G, j): 
186 
if z != i and z not in visited_nodes: 
187 
fifo.add((j, z)) 
188 
else:

189 
for z in nx.neighbors(G, j): 
190 
if str(G.edges[(j, z)]['customer']) == z and z not in visited_nodes: 
191 
fifo.add((j, z)) 
192  
193  
194 
@bgp_strategy

195 
def apply_milanicent2_strategy(G, adv_node): 
196 
""" set mrai timers so accordingly to Milani centrality (MiCe).

197 
Graph is split in three logic parts. """

198 
T = default_mrai # max mrai in seconds

199 
cent = mice.mice_centrality(G, normalized=False)

200 
ss = max(cent.values())

201 
cent = {i: v/ss for i,v in cent.items()} 
202  
203 
visited_nodes = set()

204 
set_node_mrai(G, adv_node, T*cent[adv_node]/2)

205 
fifo = set()

206 
for j in nx.neighbors(G, adv_node): 
207 
fifo.add((adv_node, j)) 
208  
209 
while len(fifo) > 0: 
210 
i, j = fifo.pop() 
211 
if j not in visited_nodes: 
212 
e = G.edges[(i,j)] 
213 
if str(e['customer']) == j: # we are in phase 3 
214 
set_node_mrai(G, j, T*cent[j]/2)

215 
elif G.nodes[j]['type'] == 'T': # we are in phase 2 
216 
set_node_mrai(G, j, T/2)

217 
else: # we are in phase 3 
218 
set_node_mrai(G, j, T*(2cent[j])/2) 
219 
visited_nodes.add(j) 
220  
221 
if str(e['customer']) == i: 
222 
for z in nx.neighbors(G, j): 
223 
if z != i and z not in visited_nodes: 
224 
fifo.add((j, z)) 
225 
else:

226 
for z in nx.neighbors(G, j): 
227 
if str(G.edges[(j, z)]['customer']) == z and z not in visited_nodes: 
228 
fifo.add((j, z)) 
229  
230  
231 
def set_node_mrai(G, node, mrai): 
232 
for j in nx.neighbors(G, node): 
233 
e = G.edges[(node, j)] 
234 
if 'termination1' in e: 
235 
if e['termination1'] == node: 
236 
e['mrai1'] = float(mrai) 
237 
else:

238 
e['mrai2'] = float(mrai) 
239 
else:

240 
e['termination1'] = node

241 
e['mrai1'] = float(mrai) 
242 
e['termination2'] = j

243  
244 
"""for node in self.graph.nodes(data=True):

245 
self.G.add_node(node[0])

246 

247 
for edge in self.graph.edges(data=True):

248 
e1 = str(edge[2]["customer"])

249 
if e1 == str(edge[2]["termination1"]):

250 
e2 = str(edge[2]["termination2"])

251 
else:

252 
e2 = str(edge[2]["termination1"])

253 
if 'fabrikant_weight' in edge[2]:

254 
self.G.add_edge(e1, e2, customer=edge[2]['customer'], termination2=edge[2]['termination2'],

255 
fabrikant_weight=edge[2]['fabrikant_weight'], termination1=edge[2]['termination1'],

256 
mrai1=edge[2]['mrai1'], mrai2=edge[2]['mrai2'], type=edge[2]['type'])

257 
else:

258 
self.G.add_edge(e1, e2, customer=edge[2]['customer'], termination2=edge[2]['termination2'],

259 
termination1=edge[2]['termination1'], mrai1=edge[2]['mrai1'], mrai2=edge[2]['mrai2'],

260 
type=edge[2]['type'])"""

261  
262  
263 
def fabrikant_levels(G, adv_node): 
264 
class FabrikantLeveler(object): 
265 
def __init__(self, G): 
266 
self.G = G

267 
self.level = {}

268 
self.sub_nodes = {}

269  
270 
def levels(self, adv_node): 
271 
self.set_distances_from(adv_node)

272 
self.trim_sub_nodes()

273 
return self.level 
274  
275 
def trim_sub_nodes(self): 
276 
for i in sorted(self.sub_nodes.keys(), key=lambda x: self.sub_nodes[x]): 
277 
for j in nx.neighbors(G, i): 
278 
if j in self.sub_nodes[i]: 
279 
for z in self.sub_nodes[i].difference(self.sub_nodes[j]): 
280 
if z != j:

281 
# print(f"subnode {z} of {i} had level {self.level[z]}")

282 
self.level[z] = min(self.level[z], self.level[i] 1) 
283 
# print(f"now it has {self.level[z]}")

284  
285 
def set_distances_from(self, adv_node): 
286 
explored = set()

287 
self.level[adv_node] = 0 
288 
self.sub_nodes[adv_node] = set() 
289 
to_explore = set([adv_node])

290  
291 
while len(to_explore) > 0: 
292 
i = to_explore.pop() 
293 
for j in nx.neighbors(G, i): 
294 
e = G.edges[(i,j)] 
295 
if e['type'] == 'transit' and str(e['customer']) == i: 
296 
if j not in self.level: 
297 
self.level[j] = self.level[i] + 1 
298 
else:

299 
self.level[j] = min(self.level[j], self.level[i]+1) 
300  
301 
if j not in self.sub_nodes: 
302 
self.sub_nodes[j] = set() 
303 
self.sub_nodes[j] = self.sub_nodes[j].union(self.sub_nodes[i]) 
304 
self.sub_nodes[j].add(i)

305 
to_explore.add(j) # there cannot be customerprovider loops

306 
explored.add(i) 
307  
308 
fl = FabrikantLeveler(G) 
309 
return fl.levels(adv_node)

310  
311  
312 
def strategyfy(G, strategy, adv_node): 
313 
if not adv_node: 
314 
adv_node = list(G.nodes)[1] 
315 
G.nodes[adv_node]['destinations'] = "10.0.0.0/24" 
316  
317 
if strategy in strategies: 
318 
eval("apply_" + strategy + "_strategy")(G, adv_node) 
319 
else:

320 
raise ValueError(f"Strategy \"{strategy}\" not available") 
321  
322  
323 
def adapt_to_mean(G, expected_mean): 
324 
mean = 0.0

325 
n_elements = 0

326 
for e in G.edges(data=True): 
327 
if e[2]['mrai1'] != 0.0: 
328 
mean += e[2]['mrai1'] 
329 
n_elements += 1

330 
if e[2]['mrai2'] != 0.0: 
331 
mean += e[2]['mrai2'] 
332 
n_elements += 1

333 
mean /= n_elements 
334  
335 
multiplier = round(float(expected_mean) / mean, 2) 
336 
for e in G.edges(data=True): 
337 
e[2]['mrai1'] = round(e[2]['mrai1'] * multiplier, 2) 
338 
e[2]['mrai2'] = round(e[2]['mrai2'] * multiplier, 2) 
339  
340  
341 
if __name__ == "__main__": 
342 
if len(sys.argv) in list(range(5, 7)): 
343 
filename = sys.argv[1]

344 
strategy = sys.argv[2]

345 
outDir = sys.argv[3]

346 
mean_mrai = sys.argv[4]

347  
348 
adv_node = None

349 
if len(sys.argv) == 6: 
350 
adv_node = sys.argv[5]

351  
352 
G = nx.read_graphml(filename) 
353 
strategyfy(G, strategy, adv_node) 
354 
if float(mean_mrai) > 0: 
355 
adapt_to_mean(G, mean_mrai) 
356  
357 
filePath = f"{strategy}_{filename}"

358 
if outDir is not None: 
359 
if not os.path.exists(outDir): 
360 
os.makedirs(outDir) 
361 
i = 0

362 
filePath = outDir + "/" + str(i) + "_" + f"{strategy}_{filename}" 
363 
while os.path.isfile(filePath):

364 
i += 1

365 
filePath = outDir + "/" + str(i) + "_" + f"{strategy}_{filename}" 
366 
else:

367 
i = 0

368 
filePath = str(i) + "_" + f"{strategy}_{filename}" 
369 
while os.path.isfile(filePath):

370 
i += 1

371 
filePath = str(i) + "_" + f"{strategy}_{filename}" 
372  
373 
nx.write_graphml(G, filePath) 
374 
# print(f"Created file {strategy}_{filename} for strategy {strategy}")

375 
else:

376 
usage(sys.argv[0])
