Statistics
| Branch: | Revision:

iof-tools / mrai_setter / mrai_setter.py @ 7476b400

History | View | Annotate | Download (11.5 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**(maxi-fl[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(maxi-fl[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*(2-cent[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*(2-cent[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']) == i:
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 customer-provider loops
288
                explored.add(i)
289

    
290
    fl = FabrikantLeveler(G)
291
    return fl.levels(adv_node)
292

    
293

    
294
def strategyfy(G, strategy, adv_node):
295
    if not adv_node:
296
        adv_node = list(G.nodes)[-1]
297
    G.nodes[adv_node]['destinations'] = "10.0.0.0/24"
298

    
299
    if strategy in strategies:
300
        eval("apply_" + strategy + "_strategy")(G, adv_node)
301
    else:
302
        raise ValueError(f"Strategy \"{strategy}\" not available")
303

    
304

    
305
def adapt_to_mean(G, expected_mean):
306
    mean = 0.0
307
    n_elements = 0
308
    for e in G.edges(data=True):
309
        if e[2]['mrai1'] != 0.0:
310
            mean += e[2]['mrai1']
311
            n_elements += 1
312
        if e[2]['mrai2'] != 0.0:
313
            mean += e[2]['mrai2']
314
            n_elements += 1
315
    mean /= n_elements
316

    
317
    multiplier = round(float(expected_mean) / mean, 2)
318
    for e in G.edges(data=True):
319
        e[2]['mrai1'] = round(e[2]['mrai1'] * multiplier, 2)
320
        e[2]['mrai2'] = round(e[2]['mrai2'] * multiplier, 2)
321

    
322

    
323
if __name__ == "__main__":
324
    if len(sys.argv) in list(range(5, 7)):
325
        filename = sys.argv[1]
326
        strategy = sys.argv[2]
327
        outDir = sys.argv[3]
328
        mean_mrai = sys.argv[4]
329

    
330
        adv_node = None
331
        if len(sys.argv) == 6:
332
            adv_node = sys.argv[5]
333

    
334
        G = nx.read_graphml(filename)
335
        strategyfy(G, strategy, adv_node)
336
        if float(mean_mrai) > 0:
337
            adapt_to_mean(G, mean_mrai)
338

    
339
        filePath = f"{strategy}_{filename}"
340
        if outDir is not None:
341
            if not os.path.exists(outDir):
342
                os.makedirs(outDir)
343
            i = 0
344
            filePath = outDir + "/" + str(i) + "_" + f"{strategy}_{filename}"
345
            while os.path.isfile(filePath):
346
                i += 1
347
                filePath = outDir + "/" + str(i) + "_" + f"{strategy}_{filename}"
348
        else:
349
            i = 0
350
            filePath = str(i) + "_" + f"{strategy}_{filename}"
351
            while os.path.isfile(filePath):
352
                i += 1
353
                filePath = str(i) + "_" + f"{strategy}_{filename}"
354

    
355
        nx.write_graphml(G, filePath)
356
        # print(f"Created file {strategy}_{filename} for strategy {strategy}")
357
    else:
358
        usage(sys.argv[0])