Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/internet_as_graphs.py: 12%
181 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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
36def choose_pref_attach(degs, seed):
37 """Pick a random value, with a probability given by its weight.
39 Returns a random choice among degs keys, each of which has a
40 probability proportional to the corresponding dictionary value.
42 Parameters
43 ----------
44 degs: dictionary
45 It contains the possible values (keys) and the corresponding
46 probabilities (values)
47 seed: random state
49 Returns
50 -------
51 v: object
52 A key of degs or None if degs is empty
53 """
55 if len(degs) == 0:
56 return None
57 s = sum(degs.values())
58 if s == 0:
59 return seed.choice(list(degs.keys()))
60 v = seed.random() * s
62 nodes = list(degs.keys())
63 i = 0
64 acc = degs[nodes[i]]
65 while v > acc:
66 i += 1
67 acc += degs[nodes[i]]
68 return nodes[i]
71class AS_graph_generator:
72 """Generates random internet AS graphs."""
74 def __init__(self, n, seed):
75 """Initializes variables. Immediate numbers are taken from [1].
77 Parameters
78 ----------
79 n: integer
80 Number of graph nodes
81 seed: random state
82 Indicator of random number generation state.
83 See :ref:`Randomness<randomness>`.
85 Returns
86 -------
87 GG: AS_graph_generator object
89 References
90 ----------
91 [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
92 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
93 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
94 """
96 self.seed = seed
97 self.n_t = min(n, round(self.seed.random() * 2 + 4)) # num of T nodes
98 self.n_m = round(0.15 * n) # number of M nodes
99 self.n_cp = round(0.05 * n) # number of CP nodes
100 self.n_c = max(0, n - self.n_t - self.n_m - self.n_cp) # number of C nodes
102 self.d_m = 2 + (2.5 * n) / 10000 # average multihoming degree for M nodes
103 self.d_cp = 2 + (1.5 * n) / 10000 # avg multihoming degree for CP nodes
104 self.d_c = 1 + (5 * n) / 100000 # average multihoming degree for C nodes
106 self.p_m_m = 1 + (2 * n) / 10000 # avg num of peer edges between M and M
107 self.p_cp_m = 0.2 + (2 * n) / 10000 # avg num of peer edges between CP, M
108 self.p_cp_cp = 0.05 + (2 * n) / 100000 # avg num of peer edges btwn CP, CP
110 self.t_m = 0.375 # probability M's provider is T
111 self.t_cp = 0.375 # probability CP's provider is T
112 self.t_c = 0.125 # probability C's provider is T
114 def t_graph(self):
115 """Generates the core mesh network of tier one nodes of a AS graph.
117 Returns
118 -------
119 G: Networkx Graph
120 Core network
121 """
123 self.G = nx.Graph()
124 for i in range(self.n_t):
125 self.G.add_node(i, type="T")
126 for r in self.regions:
127 self.regions[r].add(i)
128 for j in self.G.nodes():
129 if i != j:
130 self.add_edge(i, j, "peer")
131 self.customers[i] = set()
132 self.providers[i] = set()
133 return self.G
135 def add_edge(self, i, j, kind):
136 if kind == "transit":
137 customer = str(i)
138 else:
139 customer = "none"
140 self.G.add_edge(i, j, type=kind, customer=customer)
142 def choose_peer_pref_attach(self, node_list):
143 """Pick a node with a probability weighted by its peer degree.
145 Pick a node from node_list with preferential attachment
146 computed only on their peer degree
147 """
149 d = {}
150 for n in node_list:
151 d[n] = self.G.nodes[n]["peers"]
152 return choose_pref_attach(d, self.seed)
154 def choose_node_pref_attach(self, node_list):
155 """Pick a node with a probability weighted by its degree.
157 Pick a node from node_list with preferential attachment
158 computed on their degree
159 """
161 degs = dict(self.G.degree(node_list))
162 return choose_pref_attach(degs, self.seed)
164 def add_customer(self, i, j):
165 """Keep the dictionaries 'customers' and 'providers' consistent."""
167 self.customers[j].add(i)
168 self.providers[i].add(j)
169 for z in self.providers[j]:
170 self.customers[z].add(i)
171 self.providers[i].add(z)
173 def add_node(self, i, kind, reg2prob, avg_deg, t_edge_prob):
174 """Add a node and its customer transit edges to the graph.
176 Parameters
177 ----------
178 i: object
179 Identifier of the new node
180 kind: string
181 Type of the new node. Options are: 'M' for middle node, 'CP' for
182 content provider and 'C' for customer.
183 reg2prob: float
184 Probability the new node can be in two different regions.
185 avg_deg: float
186 Average number of transit nodes of which node i is customer.
187 t_edge_prob: float
188 Probability node i establish a customer transit edge with a tier
189 one (T) node
191 Returns
192 -------
193 i: object
194 Identifier of the new node
195 """
197 regs = 1 # regions in which node resides
198 if self.seed.random() < reg2prob: # node is in two regions
199 regs = 2
200 node_options = set()
202 self.G.add_node(i, type=kind, peers=0)
203 self.customers[i] = set()
204 self.providers[i] = set()
205 self.nodes[kind].add(i)
206 for r in self.seed.sample(list(self.regions), regs):
207 node_options = node_options.union(self.regions[r])
208 self.regions[r].add(i)
210 edge_num = uniform_int_from_avg(1, avg_deg, self.seed)
212 t_options = node_options.intersection(self.nodes["T"])
213 m_options = node_options.intersection(self.nodes["M"])
214 if i in m_options:
215 m_options.remove(i)
216 d = 0
217 while d < edge_num and (len(t_options) > 0 or len(m_options) > 0):
218 if len(m_options) == 0 or (
219 len(t_options) > 0 and self.seed.random() < t_edge_prob
220 ): # add edge to a T node
221 j = self.choose_node_pref_attach(t_options)
222 t_options.remove(j)
223 else:
224 j = self.choose_node_pref_attach(m_options)
225 m_options.remove(j)
226 self.add_edge(i, j, "transit")
227 self.add_customer(i, j)
228 d += 1
230 return i
232 def add_m_peering_link(self, m, to_kind):
233 """Add a peering link between two middle tier (M) nodes.
235 Target node j is drawn considering a preferential attachment based on
236 other M node peering degree.
238 Parameters
239 ----------
240 m: object
241 Node identifier
242 to_kind: string
243 type for target node j (must be always M)
245 Returns
246 -------
247 success: boolean
248 """
250 # candidates are of type 'M' and are not customers of m
251 node_options = self.nodes["M"].difference(self.customers[m])
252 # candidates are not providers of m
253 node_options = node_options.difference(self.providers[m])
254 # remove self
255 if m in node_options:
256 node_options.remove(m)
258 # remove candidates we are already connected to
259 for j in self.G.neighbors(m):
260 if j in node_options:
261 node_options.remove(j)
263 if len(node_options) > 0:
264 j = self.choose_peer_pref_attach(node_options)
265 self.add_edge(m, j, "peer")
266 self.G.nodes[m]["peers"] += 1
267 self.G.nodes[j]["peers"] += 1
268 return True
269 else:
270 return False
272 def add_cp_peering_link(self, cp, to_kind):
273 """Add a peering link to a content provider (CP) node.
275 Target node j can be CP or M and it is drawn uniformly among the nodes
276 belonging to the same region as cp.
278 Parameters
279 ----------
280 cp: object
281 Node identifier
282 to_kind: string
283 type for target node j (must be M or CP)
285 Returns
286 -------
287 success: boolean
288 """
290 node_options = set()
291 for r in self.regions: # options include nodes in the same region(s)
292 if cp in self.regions[r]:
293 node_options = node_options.union(self.regions[r])
295 # options are restricted to the indicated kind ('M' or 'CP')
296 node_options = self.nodes[to_kind].intersection(node_options)
298 # remove self
299 if cp in node_options:
300 node_options.remove(cp)
302 # remove nodes that are cp's providers
303 node_options = node_options.difference(self.providers[cp])
305 # remove nodes we are already connected to
306 for j in self.G.neighbors(cp):
307 if j in node_options:
308 node_options.remove(j)
310 if len(node_options) > 0:
311 j = self.seed.sample(list(node_options), 1)[0]
312 self.add_edge(cp, j, "peer")
313 self.G.nodes[cp]["peers"] += 1
314 self.G.nodes[j]["peers"] += 1
315 return True
316 else:
317 return False
319 def graph_regions(self, rn):
320 """Initializes AS network regions.
322 Parameters
323 ----------
324 rn: integer
325 Number of regions
326 """
328 self.regions = {}
329 for i in range(rn):
330 self.regions["REG" + str(i)] = set()
332 def add_peering_links(self, from_kind, to_kind):
333 """Utility function to add peering links among node groups."""
334 peer_link_method = None
335 if from_kind == "M":
336 peer_link_method = self.add_m_peering_link
337 m = self.p_m_m
338 if from_kind == "CP":
339 peer_link_method = self.add_cp_peering_link
340 if to_kind == "M":
341 m = self.p_cp_m
342 else:
343 m = self.p_cp_cp
345 for i in self.nodes[from_kind]:
346 num = uniform_int_from_avg(0, m, self.seed)
347 for _ in range(num):
348 peer_link_method(i, to_kind)
350 def generate(self):
351 """Generates a random AS network graph as described in [1].
353 Returns
354 -------
355 G: Graph object
357 Notes
358 -----
359 The process steps are the following: first we create the core network
360 of tier one nodes, then we add the middle tier (M), the content
361 provider (CP) and the customer (C) nodes along with their transit edges
362 (link i,j means i is customer of j). Finally we add peering links
363 between M nodes, between M and CP nodes and between CP node couples.
364 For a detailed description of the algorithm, please refer to [1].
366 References
367 ----------
368 [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
369 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
370 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
371 """
373 self.graph_regions(5)
374 self.customers = {}
375 self.providers = {}
376 self.nodes = {"T": set(), "M": set(), "CP": set(), "C": set()}
378 self.t_graph()
379 self.nodes["T"] = set(self.G.nodes())
381 i = len(self.nodes["T"])
382 for _ in range(self.n_m):
383 self.nodes["M"].add(self.add_node(i, "M", 0.2, self.d_m, self.t_m))
384 i += 1
385 for _ in range(self.n_cp):
386 self.nodes["CP"].add(self.add_node(i, "CP", 0.05, self.d_cp, self.t_cp))
387 i += 1
388 for _ in range(self.n_c):
389 self.nodes["C"].add(self.add_node(i, "C", 0, self.d_c, self.t_c))
390 i += 1
392 self.add_peering_links("M", "M")
393 self.add_peering_links("CP", "M")
394 self.add_peering_links("CP", "CP")
396 return self.G
399@py_random_state(1)
400@nx._dispatch(graphs=None)
401def random_internet_as_graph(n, seed=None):
402 """Generates a random undirected graph resembling the Internet AS network
404 Parameters
405 ----------
406 n: integer in [1000, 10000]
407 Number of graph nodes
408 seed : integer, random_state, or None (default)
409 Indicator of random number generation state.
410 See :ref:`Randomness<randomness>`.
412 Returns
413 -------
414 G: Networkx Graph object
415 A randomly generated undirected graph
417 Notes
418 -----
419 This algorithm returns an undirected graph resembling the Internet
420 Autonomous System (AS) network, it uses the approach by Elmokashfi et al.
421 [1]_ and it grants the properties described in the related paper [1]_.
423 Each node models an autonomous system, with an attribute 'type' specifying
424 its kind; tier-1 (T), mid-level (M), customer (C) or content-provider (CP).
425 Each edge models an ADV communication link (hence, bidirectional) with
426 attributes:
428 - type: transit|peer, the kind of commercial agreement between nodes;
429 - customer: <node id>, the identifier of the node acting as customer
430 ('none' if type is peer).
432 References
433 ----------
434 .. [1] A. Elmokashfi, A. Kvalbein and C. Dovrolis, "On the Scalability of
435 BGP: The Role of Topology Growth," in IEEE Journal on Selected Areas
436 in Communications, vol. 28, no. 8, pp. 1250-1261, October 2010.
437 """
439 GG = AS_graph_generator(n, seed)
440 G = GG.generate()
441 return G