Statistics
| Branch: | Revision:

iof-tools / chain_gadget.py @ 62798f6e

History | View | Annotate | Download (10.7 KB)

1
import networkx as nx
2

    
3
ATTR_NODE_TYPE = "type"
4
ATTR_NODE_DESTINATIONS = "destinations"
5
ATTR_EDGE_TYPE = "type"
6
ATTR_EDGE_CUSTOMER = "customer"
7
ATTR_EDGE_TERMINATION1 = "termination1"
8
ATTR_EDGE_TERMINATION2 = "termination2"
9
ATTR_EDGE_MRAI1 = "mrai1"
10
ATTR_EDGE_MRAI2 = "mrai2"
11
ATTR_EDGE_WEIGHT = "fabrikant_weight"
12
ATTR_TIMER = "mrai"
13
DEFAULT_MRAI_TIMER = 30.0
14
VALID_NODE_TYPES = ["T", "M", "CP", "C"]
15
VALID_EDGE_TYPES = ["transit", "peer"]
16

    
17

    
18
def gen_ring_with_outer(n_inner_ring, ring_index, timer, weight=False):
19
    """
20
    Generates a single ring for a chain gadget topology with the outer
21
    nodes. For more details on the parameters, see the gen_chain_gadget method.
22
    :param n_inner_ring: number of inner nodes in the ring
23
    :param ring_index: index of the ring within the topology. The ring with
24
    the highest index is the one that is connected to the destination node.
25
    This index is used to properly assign the ids to the node, so that the
26
    ring can simply be added to the complete topology graph.
27
    :param timer: the MRAI timer to be assigned to nodes in this ring
28
    :param weight: add edge weight as in the Fabrikant paper
29
    :return: a networkx topology representing the ring with index
30
    "ring_index" to be added to the complete chain topology
31
    """
32
    g = nx.Graph()
33
    total_nodes = n_inner_ring * 2 + 3
34
    id_delta = (total_nodes - 1) * ring_index
35
    # connect the inner part of the ring
36
    for i in range(0, total_nodes-2, 2):
37
        g.add_edge(i+2+id_delta, i+id_delta)
38
        attrs = {
39
            (i+2+id_delta, i+id_delta): {
40
                ATTR_EDGE_CUSTOMER: str(i+id_delta),
41
                ATTR_EDGE_TERMINATION1: str(i+id_delta),
42
                ATTR_EDGE_TERMINATION2: str(i+2+id_delta),
43
                ATTR_EDGE_MRAI1: timer,
44
                ATTR_EDGE_MRAI2: timer
45
            }
46
        }
47
        nx.set_edge_attributes(g, attrs)
48
    # connect the outer part of the ring
49
    for i in range(0, total_nodes-1):
50
        g.add_edge(i+1+id_delta, i+id_delta)
51
        attrs = {
52
            (i+1+id_delta, i+id_delta): {
53
                ATTR_EDGE_CUSTOMER: str(i+id_delta),
54
                ATTR_EDGE_TERMINATION1: str(i+id_delta),
55
                ATTR_EDGE_TERMINATION2: str(i+1+id_delta),
56
                ATTR_EDGE_MRAI1: timer,
57
                ATTR_EDGE_MRAI2: timer
58
            }
59
        }
60
        nx.set_edge_attributes(g, attrs)
61
    # connect the first node of the ring with all the inner nodes
62
    for i in range(2, total_nodes, 2):
63
        g.add_edge(i+id_delta, 0+id_delta)
64
        attrs = {
65
            (i+id_delta, 0+id_delta): {
66
                ATTR_EDGE_CUSTOMER: str(0+id_delta),
67
                ATTR_EDGE_TERMINATION1: str(i+id_delta),
68
                ATTR_EDGE_TERMINATION2: str(0+id_delta),
69
                ATTR_EDGE_MRAI1: timer,
70
                ATTR_EDGE_MRAI2: timer
71
            }
72
        }
73
        nx.set_edge_attributes(g, attrs)
74
    if weight:
75
        for i in range(0, total_nodes, 2):
76
            attrs = {
77
                (i+id_delta, 0+id_delta): {
78
                    ATTR_EDGE_WEIGHT: i//2
79
                },
80
                (i + id_delta, i + 1 + id_delta): {
81
                    ATTR_EDGE_WEIGHT: 0
82
                },
83
                (i + id_delta, i + 2 + id_delta): {
84
                    ATTR_EDGE_WEIGHT: 1
85
                }
86
            }
87
            nx.set_edge_attributes(g, attrs)
88
    return g
89

    
90

    
91
def gen_ring_without_outer(n_inner_ring, ring_index, timer, weight=False):
92
    """
93
    Generates a single ring for a chain gadget topology without the outer
94
    nodes. For more details on the parameters, see the gen_chain_gadget method.
95
    :param n_inner_ring: number of inner nodes in the ring
96
    :param ring_index: index of the ring within the topology. The ring with
97
    the highest index is the one that is connected to the destination node.
98
    This index is used to properly assign the ids to the node, so that the
99
    ring can simply be added to the complete topology graph.
100
    :param timer: the MRAI timer to be assigned to nodes in this ring
101
    :param weight: add edge weight as in the Fabrikant paper
102
    :return: a networkx topology representing the ring with index
103
    "ring_index" to be added to the complete chain topology
104
    """
105
    g = nx.Graph()
106
    total_nodes = n_inner_ring + 2
107
    id_delta = (total_nodes - 1) * ring_index
108
    # connect the inner part of the ring
109
    for i in range(total_nodes-1):
110
        g.add_edge(i+1+id_delta, i+id_delta)
111
        attrs = {
112
            (i+1+id_delta, i+id_delta): {
113
                ATTR_EDGE_CUSTOMER: str(i+id_delta),
114
                ATTR_EDGE_TERMINATION1: str(i+id_delta),
115
                ATTR_EDGE_TERMINATION2: str(i+1+id_delta),
116
                ATTR_EDGE_MRAI1: timer,
117
                ATTR_EDGE_MRAI2: timer
118
            }
119
        }
120
        nx.set_edge_attributes(g, attrs)
121
    # connect the first node of the ring with all the inner nodes
122
    for i in range(2, total_nodes, 1):
123
        g.add_edge(i+id_delta, 0+id_delta)
124
        attrs = {
125
            (i+id_delta, 0+id_delta): {
126
                ATTR_EDGE_CUSTOMER: str(0+id_delta),
127
                ATTR_EDGE_TERMINATION1: str(i+id_delta),
128
                ATTR_EDGE_TERMINATION2: str(0+id_delta),
129
                ATTR_EDGE_MRAI1: timer,
130
                ATTR_EDGE_MRAI2: timer
131
            }
132
        }
133
        nx.set_edge_attributes(g, attrs)
134
    if weight:
135
        for i in range(1, total_nodes, 1):
136
            attrs = {
137
                (i+id_delta, 0+id_delta): {
138
                    ATTR_EDGE_WEIGHT: i-1
139
                }
140
            }
141
            nx.set_edge_attributes(g, attrs)
142

    
143
    return g
144

    
145

    
146
def gen_ring(n_inner_ring, ring_index, add_outer, timer, weight=False):
147
    """
148
    Generates a single ring for a chain gadget topology. For more details on
149
    the parameters, see the gen_chain_gadget method.
150
    :param n_inner_ring: number of inner nodes in the ring
151
    :param ring_index: index of the ring within the topology. The ring with
152
    the highest index is the one that is connected to the destination node.
153
    This index is used to properly assign the ids to the node, so that the
154
    ring can simply be added to the complete topology graph.
155
    :param add_outer: if set to true, adds the outer nodes as well
156
    :param timer: the MRAI timer to be set to all nodes in the ring
157
    :param weight: add edge weight as in the Fabrikant paper
158
    :return: a networkx topology representing the ring with index
159
    "ring_index" to be added to the complete chain topology
160
    """
161
    if add_outer:
162
        g = gen_ring_with_outer(n_inner_ring, ring_index, timer, weight)
163
    else:
164
        g = gen_ring_without_outer(n_inner_ring, ring_index, timer, weight)
165
    return g
166

    
167

    
168
def gen_chain_gadget(n_rings, n_inner, add_outer, node_type, edge_type="transit",
169
                     set_timer=False, min_mrai=None, weight=False):
170
    """
171
    Generates a chain gadget topology as in Fig. 3 of the Fabrikant-Rexford
172
    paper (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5935139). As
173
    the paper doesn't introduce a specific notation, we introduce one here to
174
    explain the parameters. Consider the nodes in the following configuration:
175

176
          7     5     3     1
177
             6           2
178
       8           4           0
179

180
    The chain gadget topology is composed by a set of rings, ring 1 being the
181
    set of nodes {0, 1, 2, 3, 4} and ring 2 being the set of nodes {4, 5, 6, 7,
182
    8}. Rings are connected through a single node that they share, in this
183
    specific example node 4. In the paper, the nodes of this kind are labeled
184
    with X_i. Within each ring we have two type of nodes, called inner and outer
185
    nodes. Inner nodes are the ones in the middle (in the paper, these are the
186
    Y_i nodes). The first node of each ring (i.e., nodes 0 and 4) have an edge
187
    to all the inner nodes. Outer nodes are the ones at the top (in the paper
188
    they are labeled with Z_i). Within each ring all the nodes are connected in
189
    a chain, i.e., there exist the set of edges {(i, i+1) : i = first node, ...,
190
    last node - 1}. In the paper the edge direction is the opposite of a
191
    customer-provider relationship, so if in the paper there is an edge (i, j),
192
    the topology needs to have the edge (j, i).
193
    Finally, in the paper, there is a final node labelled as "d" (
194
    destination). This IS NOT a node of the network, but a destination
195
    network exported by the left-most node in the graph (8 in this example).
196
    :param n_rings: number of rings in the topology. In the example topology
197
    described above, n_rings = 2. This number must be at least 1
198
    :param n_inner: number of inner nodes. The number of outer nodes (if the
199
    user requires to add outer nodes) is automatically derived from this number
200
    (inner nodes + 1). In the example topology described above, n_inner = 1.
201
    This number must be at least 1.
202
    :param add_outer: if set to False, the procedure will not add outer 
203
    nodes, but only inner nodes
204
    :param node_type: type of node to be assigned. Valid values are T, M, CP, C
205
    :param edge_type: type of edge to be assigned. Valid values are P and CS.
206
    CS is the default
207
    :param set_timer: if set to true, adds the MRAI timer to the set of node
208
    attributes following the indications within the paper (a timer which
209
    value decreases exponentially with the ring id)
210
    :param min_mrai: minimum MRAI value to be used
211
    :param weight: add edge weight as in the Fabrikant paper
212
    :return: a networkx graph following the chain gadget topology
213
    """
214
    if n_rings < 1:
215
        raise Exception("The number of rings must be at least 1")
216
    if n_inner < 1:
217
        raise Exception("The number of inner nodes must be at least 1")
218
    if node_type not in VALID_NODE_TYPES:
219
        raise Exception("Invalid node type '{}' specified. Please choose a "
220
                        "value in {}".format(node_type,
221
                                             ', '.join(VALID_NODE_TYPES)))
222
    if edge_type not in VALID_EDGE_TYPES:
223
        raise Exception("Invalid edge type '{}' specified. Please choose a "
224
                        "value in {}".format(edge_type,
225
                                             ', '.join(VALID_EDGE_TYPES)))
226
    mrai = DEFAULT_MRAI_TIMER
227
    if min_mrai is not None:
228
        computed_min_mrai = DEFAULT_MRAI_TIMER / 2**(n_rings-1)
229
        if computed_min_mrai < min_mrai:
230
            mrai = min_mrai * 2**(n_rings-1)
231
    g = nx.Graph()
232
    for i in range(n_rings):
233
        if set_timer:
234
            timer = mrai * pow(2, -(n_rings - i - 1))
235
        else:
236
            timer = mrai
237
        ring = gen_ring(n_inner, i, add_outer, timer, weight)
238
        g = nx.compose(g, ring)
239
    nx.set_node_attributes(g, node_type, ATTR_NODE_TYPE)
240
    nx.set_edge_attributes(g, edge_type, ATTR_EDGE_TYPE)
241
    nx.set_node_attributes(g, "", ATTR_NODE_DESTINATIONS)
242
    nx.set_node_attributes(g, {
243
        len(g.nodes)-1: {ATTR_NODE_DESTINATIONS: "100.0.0.0/24"}
244
    })
245
    return g