ioftools / mrai_setter / mrai_setter.py @ fb99df25
History  View  Annotate  Download (11.4 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 
for i in G.nodes: 
66 
if i in fl: 
67 
set_node_mrai(G, i, default_mrai/(2**fl[i]))

68 
else:

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

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

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

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

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

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

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

89 
but in reverse order """

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

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

95 
else:

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

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

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

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

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

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

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

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

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

117 
farther and farther from the advertising node """

118 
start_mrai = 0

119 
inc_mrai = 0.5

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

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

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

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

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

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

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

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

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

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

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

163 
T = default_mrai # max mrai in seconds

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

165  
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  
245 
def fabrikant_levels(G, adv_node): 
246 
class FabrikantLeveler(object): 
247 
def __init__(self, G): 
248 
self.G = G

249 
self.level = {}

250 
self.sub_nodes = {}

251  
252 
def levels(self, adv_node): 
253 
self.set_distances_from(adv_node)

254 
self.trim_sub_nodes()

255 
return self.level 
256  
257 
def trim_sub_nodes(self): 
258 
for i in sorted(self.sub_nodes.keys(), key=lambda x: self.sub_nodes[x]): 
259 
for j in nx.neighbors(G, i): 
260 
if j in self.sub_nodes[i]: 
261 
for z in self.sub_nodes[i].difference(self.sub_nodes[j]): 
262 
if z != j:

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

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

266  
267 
def set_distances_from(self, adv_node): 
268 
explored = set()

269 
self.level[adv_node] = 0 
270 
self.sub_nodes[adv_node] = set() 
271 
to_explore = set([adv_node])

272  
273 
while len(to_explore) > 0: 
274 
i = to_explore.pop() 
275 
for j in nx.neighbors(G, i): 
276 
e = G.edges[(i,j)] 
277 
if e['type'] == 'transit' and str(e['customer']) == j: 
278 
if j not in self.level: 
279 
self.level[j] = self.level[i] + 1 
280 
else:

281 
self.level[j] = min(self.level[j], self.level[i]+1) 
282  
283 
if j not in self.sub_nodes: 
284 
self.sub_nodes[j] = set() 
285 
self.sub_nodes[j] = self.sub_nodes[j].union(self.sub_nodes[i]) 
286 
self.sub_nodes[j].add(i)

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

288  
289 
explored.add(i) 
290  
291 
fl = FabrikantLeveler(G) 
292 
return fl.levels(adv_node)

293  
294  
295 
def strategyfy(G, strategy, adv_node): 
296 
if not adv_node: 
297 
adv_node = list(G.nodes)[1] 
298 
G.nodes[adv_node]['destinations'] = "10.0.0.0/8" 
299  
300 
if strategy in strategies: 
301 
eval("apply_" + strategy + "_strategy")(G, adv_node) 
302 
else:

303 
raise ValueError(f"Strategy \"{strategy}\" not available") 
304  
305  
306 
def adapt_to_mean(G, expected_mean): 
307 
mean = 0.0

308 
n_elements = len(G.edges)*2 
309 
for e in G.edges(data=True): 
310 
mean += e[2]['mrai1'] + e[2]['mrai2'] 
311 
mean /= n_elements 
312  
313 
multiplier = round(float(expected_mean) / mean, 2) 
314 
for e in G.edges(data=True): 
315 
e[2]['mrai1'] = round(e[2]['mrai1'] * multiplier, 2) 
316 
e[2]['mrai2'] = round(e[2]['mrai2'] * multiplier, 2) 
317  
318  
319 
if __name__ == "__main__": 
320 
if len(sys.argv) in list(range(5, 6)): 
321 
filename = sys.argv[1]

322 
strategy = sys.argv[2]

323 
outDir = sys.argv[3]

324 
mean_mrai = sys.argv[4]

325  
326 
adv_node = None

327 
if len(sys.argv) == 6: 
328 
adv_node = sys.argv[5]

329  
330 
G = nx.read_graphml(filename) 
331 
strategyfy(G, strategy, adv_node) 
332 
if float(mean_mrai) > 0: 
333 
adapt_to_mean(G, mean_mrai) 
334  
335 
filePath = f"{strategy}_{filename}"

336 
if outDir is not None: 
337 
if not os.path.exists(outDir): 
338 
os.makedirs(outDir) 
339 
i = 0

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

342 
i += 1

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

345 
i = 0

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

348 
i += 1

349 
filePath = str(i) + "_" + f"{strategy}_{filename}" 
350  
351 
nx.write_graphml(G, filePath) 
352 
# print(f"Created file {strategy}_{filename} for strategy {strategy}")

353 
else:

354 
usage(sys.argv[0])
