Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Generates graphs resembling the Internet Autonomous System network"""
3import networkx as nx
4from networkx.utils import py_random_state
6__all__ = ["random_internet_as_graph"]
9def uniform_int_from_avg(a, m, seed):
10 """Pick a random integer with uniform probability.
12 Returns a random integer uniformly taken from a distribution with
13 minimum value 'a' and average value 'm', X~U(a,b), E[X]=m, X in N where
14 b = 2*m - a.
16 Notes
17 -----
18 p = (b-floor(b))/2
19 X = X1 + X2; X1~U(a,floor(b)), X2~B(p)
20 E[X] = E[X1] + E[X2] = (floor(b)+a)/2 + (b-floor(b))/2 = (b+a)/2 = m
21 """
23 from math import floor
25 assert m >= a
26 b = 2 * m - a
27 p = (b - floor(b)) / 2
28 X1 = round(seed.random() * (floor(b) - a) + a)
29 if seed.random() < p:
30 X2 = 1
31 else:
32 X2 = 0
33 return X1 + X2
36@py_random_state("seed")
37def choose_pref_attach(degs, seed):
38 """Pick a random value, with a probability given by its weight.
40 Returns a random choice among degs keys, each of which has a
41 probability proportional to the corresponding dictionary value.
43 Parameters
44 ----------
45 degs: dictionary
46 It contains the possible values (keys) and the corresponding
47 probabilities (values)
48 seed: random state
50 Returns
51 -------
52 v: object
53 A key of degs or None if degs is empty
54 """
56 if len(degs) == 0:
57 return None
58 s = sum(degs.values())
59 if s == 0:
60 return seed.choice(list(degs.keys()))
61 v = seed.random() * s
63 nodes = list(degs.keys())
64 i = 0
65 acc = degs[nodes[i]]
66 while v > acc:
67 i += 1
68 acc += degs[nodes[i]]
69 return nodes[i]
72class AS_graph_generator:
73 """Generates random internet AS graphs."""
75 @py_random_state("seed")
76 def __init__(self, n, seed):
77 """Initializes variables. Immediate numbers are taken from [1].
79 Parameters
80 ----------
81 n: integer
82 Number of graph nodes
83 seed: random state
84 Indicator of random number generation state.
85 See :ref:`Randomness<randomness>`.
87 Returns
88 -------
89 GG: AS_graph_generator object
91 References
92 ----------
93 [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
94 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
95 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
96 """
98 self.seed = seed
99 self.n_t = min(n, round(self.seed.random() * 2 + 4)) # num of T nodes
100 self.n_m = round(0.15 * n) # number of M nodes
101 self.n_cp = round(0.05 * n) # number of CP nodes
102 self.n_c = max(0, n - self.n_t - self.n_m - self.n_cp) # number of C nodes
104 self.d_m = 2 + (2.5 * n) / 10000 # average multihoming degree for M nodes
105 self.d_cp = 2 + (1.5 * n) / 10000 # avg multihoming degree for CP nodes
106 self.d_c = 1 + (5 * n) / 100000 # average multihoming degree for C nodes
108 self.p_m_m = 1 + (2 * n) / 10000 # avg num of peer edges between M and M
109 self.p_cp_m = 0.2 + (2 * n) / 10000 # avg num of peer edges between CP, M
110 self.p_cp_cp = 0.05 + (2 * n) / 100000 # avg num of peer edges btwn CP, CP
112 self.t_m = 0.375 # probability M's provider is T
113 self.t_cp = 0.375 # probability CP's provider is T
114 self.t_c = 0.125 # probability C's provider is T
116 def t_graph(self):
117 """Generates the core mesh network of tier one nodes of a AS graph.
119 Returns
120 -------
121 G: Networkx Graph
122 Core network
123 """
125 self.G = nx.Graph()
126 for i in range(self.n_t):
127 self.G.add_node(i, type="T")
128 for r in self.regions:
129 self.regions[r].add(i)
130 for j in self.G.nodes():
131 if i != j:
132 self.add_edge(i, j, "peer")
133 self.customers[i] = set()
134 self.providers[i] = set()
135 return self.G
137 def add_edge(self, i, j, kind):
138 if kind == "transit":
139 customer = str(i)
140 else:
141 customer = "none"
142 self.G.add_edge(i, j, type=kind, customer=customer)
144 def choose_peer_pref_attach(self, node_list):
145 """Pick a node with a probability weighted by its peer degree.
147 Pick a node from node_list with preferential attachment
148 computed only on their peer degree
149 """
151 d = {}
152 for n in node_list:
153 d[n] = self.G.nodes[n]["peers"]
154 return choose_pref_attach(d, self.seed)
156 def choose_node_pref_attach(self, node_list):
157 """Pick a node with a probability weighted by its degree.
159 Pick a node from node_list with preferential attachment
160 computed on their degree
161 """
163 degs = dict(self.G.degree(node_list))
164 return choose_pref_attach(degs, self.seed)
166 def add_customer(self, i, j):
167 """Keep the dictionaries 'customers' and 'providers' consistent."""
169 self.customers[j].add(i)
170 self.providers[i].add(j)
171 for z in self.providers[j]:
172 self.customers[z].add(i)
173 self.providers[i].add(z)
175 def add_node(self, i, kind, reg2prob, avg_deg, t_edge_prob):
176 """Add a node and its customer transit edges to the graph.
178 Parameters
179 ----------
180 i: object
181 Identifier of the new node
182 kind: string
183 Type of the new node. Options are: 'M' for middle node, 'CP' for
184 content provider and 'C' for customer.
185 reg2prob: float
186 Probability the new node can be in two different regions.
187 avg_deg: float
188 Average number of transit nodes of which node i is customer.
189 t_edge_prob: float
190 Probability node i establish a customer transit edge with a tier
191 one (T) node
193 Returns
194 -------
195 i: object
196 Identifier of the new node
197 """
199 regs = 1 # regions in which node resides
200 if self.seed.random() < reg2prob: # node is in two regions
201 regs = 2
202 node_options = set()
204 self.G.add_node(i, type=kind, peers=0)
205 self.customers[i] = set()
206 self.providers[i] = set()
207 self.nodes[kind].add(i)
208 for r in self.seed.sample(list(self.regions), regs):
209 node_options = node_options.union(self.regions[r])
210 self.regions[r].add(i)
212 edge_num = uniform_int_from_avg(1, avg_deg, self.seed)
214 t_options = node_options.intersection(self.nodes["T"])
215 m_options = node_options.intersection(self.nodes["M"])
216 if i in m_options:
217 m_options.remove(i)
218 d = 0
219 while d < edge_num and (len(t_options) > 0 or len(m_options) > 0):
220 if len(m_options) == 0 or (
221 len(t_options) > 0 and self.seed.random() < t_edge_prob
222 ): # add edge to a T node
223 j = self.choose_node_pref_attach(t_options)
224 t_options.remove(j)
225 else:
226 j = self.choose_node_pref_attach(m_options)
227 m_options.remove(j)
228 self.add_edge(i, j, "transit")
229 self.add_customer(i, j)
230 d += 1
232 return i
234 def add_m_peering_link(self, m, to_kind):
235 """Add a peering link between two middle tier (M) nodes.
237 Target node j is drawn considering a preferential attachment based on
238 other M node peering degree.
240 Parameters
241 ----------
242 m: object
243 Node identifier
244 to_kind: string
245 type for target node j (must be always M)
247 Returns
248 -------
249 success: boolean
250 """
252 # candidates are of type 'M' and are not customers of m
253 node_options = self.nodes["M"].difference(self.customers[m])
254 # candidates are not providers of m
255 node_options = node_options.difference(self.providers[m])
256 # remove self
257 if m in node_options:
258 node_options.remove(m)
260 # remove candidates we are already connected to
261 for j in self.G.neighbors(m):
262 if j in node_options:
263 node_options.remove(j)
265 if len(node_options) > 0:
266 j = self.choose_peer_pref_attach(node_options)
267 self.add_edge(m, j, "peer")
268 self.G.nodes[m]["peers"] += 1
269 self.G.nodes[j]["peers"] += 1
270 return True
271 else:
272 return False
274 def add_cp_peering_link(self, cp, to_kind):
275 """Add a peering link to a content provider (CP) node.
277 Target node j can be CP or M and it is drawn uniformly among the nodes
278 belonging to the same region as cp.
280 Parameters
281 ----------
282 cp: object
283 Node identifier
284 to_kind: string
285 type for target node j (must be M or CP)
287 Returns
288 -------
289 success: boolean
290 """
292 node_options = set()
293 for r in self.regions: # options include nodes in the same region(s)
294 if cp in self.regions[r]:
295 node_options = node_options.union(self.regions[r])
297 # options are restricted to the indicated kind ('M' or 'CP')
298 node_options = self.nodes[to_kind].intersection(node_options)
300 # remove self
301 if cp in node_options:
302 node_options.remove(cp)
304 # remove nodes that are cp's providers
305 node_options = node_options.difference(self.providers[cp])
307 # remove nodes we are already connected to
308 for j in self.G.neighbors(cp):
309 if j in node_options:
310 node_options.remove(j)
312 if len(node_options) > 0:
313 j = self.seed.sample(list(node_options), 1)[0]
314 self.add_edge(cp, j, "peer")
315 self.G.nodes[cp]["peers"] += 1
316 self.G.nodes[j]["peers"] += 1
317 return True
318 else:
319 return False
321 def graph_regions(self, rn):
322 """Initializes AS network regions.
324 Parameters
325 ----------
326 rn: integer
327 Number of regions
328 """
330 self.regions = {}
331 for i in range(rn):
332 self.regions["REG" + str(i)] = set()
334 def add_peering_links(self, from_kind, to_kind):
335 """Utility function to add peering links among node groups."""
336 peer_link_method = None
337 if from_kind == "M":
338 peer_link_method = self.add_m_peering_link
339 m = self.p_m_m
340 if from_kind == "CP":
341 peer_link_method = self.add_cp_peering_link
342 if to_kind == "M":
343 m = self.p_cp_m
344 else:
345 m = self.p_cp_cp
347 for i in self.nodes[from_kind]:
348 num = uniform_int_from_avg(0, m, self.seed)
349 for _ in range(num):
350 peer_link_method(i, to_kind)
352 def generate(self):
353 """Generates a random AS network graph as described in [1].
355 Returns
356 -------
357 G: Graph object
359 Notes
360 -----
361 The process steps are the following: first we create the core network
362 of tier one nodes, then we add the middle tier (M), the content
363 provider (CP) and the customer (C) nodes along with their transit edges
364 (link i,j means i is customer of j). Finally we add peering links
365 between M nodes, between M and CP nodes and between CP node couples.
366 For a detailed description of the algorithm, please refer to [1].
368 References
369 ----------
370 [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
371 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
372 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
373 """
375 self.graph_regions(5)
376 self.customers = {}
377 self.providers = {}
378 self.nodes = {"T": set(), "M": set(), "CP": set(), "C": set()}
380 self.t_graph()
381 self.nodes["T"] = set(self.G.nodes())
383 i = len(self.nodes["T"])
384 for _ in range(self.n_m):
385 self.nodes["M"].add(self.add_node(i, "M", 0.2, self.d_m, self.t_m))
386 i += 1
387 for _ in range(self.n_cp):
388 self.nodes["CP"].add(self.add_node(i, "CP", 0.05, self.d_cp, self.t_cp))
389 i += 1
390 for _ in range(self.n_c):
391 self.nodes["C"].add(self.add_node(i, "C", 0, self.d_c, self.t_c))
392 i += 1
394 self.add_peering_links("M", "M")
395 self.add_peering_links("CP", "M")
396 self.add_peering_links("CP", "CP")
398 return self.G
401@py_random_state(1)
402@nx._dispatchable(graphs=None, returns_graph=True)
403def random_internet_as_graph(n, seed=None):
404 """Generates a random undirected graph resembling the Internet AS network
406 Parameters
407 ----------
408 n: integer in [1000, 10000]
409 Number of graph nodes
410 seed : integer, random_state, or None (default)
411 Indicator of random number generation state.
412 See :ref:`Randomness<randomness>`.
414 Returns
415 -------
416 G: Networkx Graph object
417 A randomly generated undirected graph
419 Notes
420 -----
421 This algorithm returns an undirected graph resembling the Internet
422 Autonomous System (AS) network, it uses the approach by Elmokashfi et al.
423 [1]_ and it grants the properties described in the related paper [1]_.
425 Each node models an autonomous system, with an attribute 'type' specifying
426 its kind; tier-1 (T), mid-level (M), customer (C) or content-provider (CP).
427 Each edge models an ADV communication link (hence, bidirectional) with
428 attributes:
430 - type: transit|peer, the kind of commercial agreement between nodes;
431 - customer: <node id>, the identifier of the node acting as customer
432 ('none' if type is peer).
434 References
435 ----------
436 .. [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
437 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
438 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
439 """
441 GG = AS_graph_generator(n, seed)
442 G = GG.generate()
443 return G