2 # NEPI, a framework to manage network experiments
3 # Copyright (C) 2013 INRIA
5 # This program is free software: you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License version 2 as
7 # published by the Free Software Foundation;
9 # This program is distributed in the hope that it will be useful,
10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 # GNU General Public License for more details.
14 # You should have received a copy of the GNU General Public License
15 # along with this program. If not, see <http://www.gnu.org/licenses/>.
17 # Author: Alina Quereilhac <alina.quereilhac@inria.fr>
23 from six import next, PY2, PY3
39 ## - AQ: Add support for hypergraphs (to be able to add hyper edges to
40 ## model CSMA or wireless networks)
42 class NetGraph(object):
43 """ NetGraph represents a network topology.
44 Network graphs are internally using the networkx library.
48 def __init__(self, **kwargs):
49 """ A graph can be generated using a specified pattern
50 (LADDER, MESH, TREE, etc), or provided as an argument.
52 :param topology: Undirected graph to use as internal representation
53 :type topology: networkx.Graph
55 :param topo_type: One of TopologyType.{LINEAR,LADDER,MESH,TREE,STAR}
56 used to automatically generate the topology graph.
57 :type topo_type: TopologyType
59 :param node_count: Number of nodes in the topology to be generated.
62 :param branches: Number of branches (arms) for the STAR topology.
66 :param assign_ips: Automatically assign IP addresses to each node.
67 :type assign_ips: bool
69 :param network: Base network segment for IP address assignment.
72 :param prefix: Base network prefix for IP address assignment.
75 :param version: IP version for IP address assignment.
78 :param assign_st: Select source and target nodes on the graph.
81 :param sources_targets: dictionary with the list of sources (key =
82 "sources") and list of targets (key = "targets") if defined, ignore
84 :type sources_targets: dictionary of lists
86 :param leaf_source: if True, random sources will be selected only
88 :type leaf_source: bool
90 NOTE: Only point-to-point like network topologies are supported for now.
91 (Wireless and Ethernet networks were several nodes share the same
92 edge (hyperedge) can not be modeled for the moment).
95 self._topology = kwargs.get("topology")
96 self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC)
99 if kwargs.get("node_count"):
100 node_count = kwargs["node_count"]
101 branches = kwargs.get("branches")
103 self._topology = self.generate_topology(self.topo_type,
104 node_count, branches = branches)
106 self._topology = networkx.Graph()
108 if kwargs.get("assign_ips"):
109 network = kwargs.get("network", "10.0.0.0")
110 prefix = kwargs.get("prefix", 8)
111 version = kwargs.get("version", 4)
113 self.assign_p2p_ips(network = network, prefix = prefix,
116 sources_targets = kwargs.get("sources_targets")
118 [self.set_source(n) for n in sources_targets["sources"]]
119 [self.set_target(n) for n in sources_targets["targets"]]
120 elif kwargs.get("assign_st"):
121 self.select_target_zero()
122 self.select_random_source(is_leaf = kwargs.get("leaf_source"))
126 return self._topology
130 return self._topo_type
134 return self.topology.order()
137 return self.topology.nodes()
140 return self.topology.edges()
142 def generate_topology(self, topo_type, node_count, branches = None):
143 if topo_type == TopologyType.LADDER:
144 total_nodes = node_count/2
145 graph = networkx.ladder_graph(total_nodes)
147 elif topo_type == TopologyType.LINEAR:
148 graph = networkx.path_graph(node_count)
150 elif topo_type == TopologyType.MESH:
151 graph = networkx.complete_graph(node_count)
153 elif topo_type == TopologyType.TREE:
154 h = math.log(node_count + 1)/math.log(2) - 1
155 graph = networkx.balanced_tree(2, h)
157 elif topo_type == TopologyType.STAR:
158 graph = networkx.Graph()
161 nodesinbranch = (node_count - 1)/ BRANCHES
164 for i in range(BRANCHES):
166 for n in range(1, nodesinbranch + 1):
168 graph.add_edge(prev, c)
174 def add_node(self, nid):
175 if nid not in self.topology:
176 self.topology.add_node(nid)
178 def add_edge(self, nid1, nid2):
182 if nid1 not in self.topology[nid2]:
183 self.topology.add_edge(nid2, nid1)
185 def annotate_node_ip(self, nid, ip):
186 if "ips" not in self.topology.node[nid]:
187 self.topology.node[nid]["ips"] = list()
189 self.topology.node[nid]["ips"].append(ip)
191 def node_ip_annotations(self, nid):
192 return self.topology.node[nid].get("ips", [])
194 def annotate_node(self, nid, name, value):
195 if not isinstance(value, str) and not isinstance(value, int) and \
196 not isinstance(value, float) and not isinstance(value, bool):
197 raise RuntimeError("Non-serializable annotation")
199 self.topology.node[nid][name] = value
201 def node_annotation(self, nid, name):
202 return self.topology.node[nid].get(name)
204 def node_annotations(self, nid):
205 retcod = self.topology.node[nid].keys()
206 if PY3: retcod = list(retcod)
209 def del_node_annotation(self, nid, name):
210 del self.topology.node[nid][name]
212 def annotate_edge(self, nid1, nid2, name, value):
213 if not isinstance(value, str) and not isinstance(value, int) and \
214 not isinstance(value, float) and not isinstance(value, bool):
215 raise RuntimeError("Non-serializable annotation")
217 self.topology.edge[nid1][nid2][name] = value
219 def annotate_edge_net(self, nid1, nid2, ip1, ip2, mask, network,
221 self.topology.edge[nid1][nid2]["net"] = dict()
222 self.topology.edge[nid1][nid2]["net"][nid1] = ip1
223 self.topology.edge[nid1][nid2]["net"][nid2] = ip2
224 self.topology.edge[nid1][nid2]["net"]["mask"] = mask
225 self.topology.edge[nid1][nid2]["net"]["network"] = network
226 self.topology.edge[nid1][nid2]["net"]["prefix"] = prefixlen
228 def edge_net_annotation(self, nid1, nid2):
229 return self.topology.edge[nid1][nid2].get("net", dict())
231 def edge_annotation(self, nid1, nid2, name):
232 return self.topology.edge[nid1][nid2].get(name)
234 def edge_annotations(self, nid1, nid2):
235 retcod = self.topology.edge[nid1][nid2].keys()
236 if PY3: retcod = list(retcod)
239 def del_edge_annotation(self, nid1, nid2, name):
240 del self.topology.edge[nid1][nid2][name]
242 def assign_p2p_ips(self, network = "10.0.0.0", prefix = 8, version = 4):
243 """ Assign IP addresses to each end of each edge of the network graph,
244 computing all the point to point subnets and addresses in the network
247 :param network: Base network address used for subnetting.
250 :param prefix: Prefix for the base network address used for subnetting.
253 :param version: IP version (either 4 or 6).
257 if networkx.number_connected_components(self.topology) > 1:
258 raise RuntimeError("Disconnected graph!!")
260 # Assign IP addresses to host
261 netblock = "%s/%d" % (network, prefix)
263 net = ipaddr.IPv4Network(netblock) if PY2 else ipaddress.ip_network(netblock)
266 net = ipaddr.IPv6Network(netblock) if PY2 else ipaddress.ip_network(netblock)
269 raise RuntimeError("Invalid IP version %d" % version)
271 ## Clear all previusly assigned IPs
272 for nid in self.topology.nodes():
273 self.topology.node[nid]["ips"] = list()
275 ## Generate and assign new IPs
276 sub_itr = net.iter_subnets(new_prefix = new_prefix)
278 for nid1, nid2 in self.topology.edges():
279 #### Compute subnets for each link
281 # get a subnet of base_add with prefix /30
282 subnet = next(sub_itr)
283 mask = subnet.netmask.exploded
284 network = subnet.network.exploded
285 prefixlen = subnet.prefixlen
287 # get host addresses in that subnet
288 i = subnet.iterhosts()
294 self.annotate_edge_net(nid1, nid2, ip1, ip2, mask, network,
297 self.annotate_node_ip(nid1, ip1)
298 self.annotate_node_ip(nid2, ip2)
300 def get_p2p_info(self, nid1, nid2):
301 net = self.topology.edge[nid1][nid2]["net"]
302 return ( net[nid1], net[nid2], net["mask"], net["network"],
305 def set_source(self, nid):
306 self.topology.node[nid]["source"] = True
308 def is_source(self, nid):
309 return self.topology.node[nid].get("source")
311 def set_target(self, nid):
312 self.topology.node[nid]["target"] = True
314 def is_target(self, nid):
315 return self.topology.node[nid].get("target")
318 """ Returns the nodes that are targets """
319 return [nid for nid in self.topology.nodes() \
320 if self.topology.node[nid].get("target")]
323 """ Returns the nodes that are sources """
324 return [nid for nid in self.topology.nodes() \
325 if self.topology.node[nid].get("source")]
327 def select_target_zero(self):
328 """ Mark the node 0 as target
330 nid = 0 if 0 in self.topology.nodes() else "0"
333 def select_random_source(self, **kwargs):
334 """ Mark a random node as source.
337 # The ladder is a special case because is not symmetric.
338 if self.topo_type == TopologyType.LADDER:
339 total_nodes = self.order/2
341 leaf2 = total_nodes - 1
342 leaves = [leaf1, leaf2]
343 source = leaves.pop(random.randint(0, len(leaves) - 1))
345 # options must not be already sources or targets
346 options = [ k for k,v in self.topology.degree().items() \
347 if (not kwargs.get("is_leaf") or v == 1) \
348 and not self.topology.node[k].get("source") \
349 and not self.topology.node[k].get("target")]
350 source = options.pop(random.randint(0, len(options) - 1))
352 self.set_source(source)