Statistics
| Branch: | Revision:

iof-tools / 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**(maxi-fl[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(maxi-fl[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*(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']) == 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 customer-provider 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])