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>
33 ## - AQ: Add support for hypergraphs (to be able to add hyper edges to
34 ## model CSMA or wireless networks)
36 class NetGraph(object):
37 """ NetGraph represents a network topology.
38 Network graphs are internally using the networkx library.
42 def __init__(self, **kwargs):
43 """ A graph can be generated using a specified pattern
44 (LADDER, MESH, TREE, etc), or provided as an argument.
46 :param topology: Undirected graph to use as internal representation
47 :type topology: networkx.Graph
49 :param topo_type: One of TopologyType.{LINEAR,LADDER,MESH,TREE,STAR}
50 used to automatically generate the topology graph.
51 :type topo_type: TopologyType
53 :param node_count: Number of nodes in the topology to be generated.
56 :param branches: Number of branches (arms) for the STAR topology.
60 :param assign_ips: Automatically assign IP addresses to each node.
61 :type assign_ips: bool
63 :param network: Base network segment for IP address assignment.
66 :param prefix: Base network prefix for IP address assignment.
69 :param version: IP version for IP address assignment.
72 :param assign_st: Select source and target nodes on the graph.
75 :param sources_targets: dictionary with the list of sources (key =
76 "sources") and list of targets (key = "targets") if defined, ignore
78 :type sources_targets: dictionary of lists
80 :param leaf_source: if True, random sources will be selected only
82 :type leaf_source: bool
84 NOTE: Only point-to-point like network topologies are supported for now.
85 (Wireless and Ethernet networks were several nodes share the same
86 edge (hyperedge) can not be modeled for the moment).
89 self._topology = kwargs.get("topology")
90 self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC)
93 if kwargs.get("node_count"):
94 node_count = kwargs["node_count"]
95 branches = kwargs.get("branches")
97 self._topology = self.generate_topology(self.topo_type,
98 node_count, branches = branches)
100 self._topology = networkx.Graph()
102 if kwargs.get("assign_ips"):
103 network = kwargs.get("network", "10.0.0.0")
104 prefix = kwargs.get("prefix", 8)
105 version = kwargs.get("version", 4)
107 self.assign_p2p_ips(network = network, prefix = prefix,
110 sources_targets = kwargs.get("sources_targets")
112 [self.set_source(n) for n in sources_targets["sources"]]
113 [self.set_target(n) for n in sources_targets["targets"]]
114 elif kwargs.get("assign_st"):
115 self.select_target_zero()
116 self.select_random_source(is_leaf = kwargs.get("leaf_source"))
120 return self._topology
124 return self._topo_type
128 return self.topology.order()
131 return self.topology.nodes()
134 return self.topology.edges()
136 def generate_topology(self, topo_type, node_count, branches = None):
137 if topo_type == TopologyType.LADDER:
138 total_nodes = node_count/2
139 graph = networkx.ladder_graph(total_nodes)
141 elif topo_type == TopologyType.LINEAR:
142 graph = networkx.path_graph(node_count)
144 elif topo_type == TopologyType.MESH:
145 graph = networkx.complete_graph(node_count)
147 elif topo_type == TopologyType.TREE:
148 h = math.log(node_count + 1)/math.log(2) - 1
149 graph = networkx.balanced_tree(2, h)
151 elif topo_type == TopologyType.STAR:
152 graph = networkx.Graph()
155 nodesinbranch = (node_count - 1)/ BRANCHES
158 for i in range(BRANCHES):
160 for n in range(1, nodesinbranch + 1):
162 graph.add_edge(prev, c)
168 def add_node(self, nid):
169 if nid not in self.topology:
170 self.topology.add_node(nid)
172 def add_edge(self, nid1, nid2):
176 if nid1 not in self.topology[nid2]:
177 self.topology.add_edge(nid2, nid1)
179 def annotate_node_ip(self, nid, ip):
180 if "ips" not in self.topology.node[nid]:
181 self.topology.node[nid]["ips"] = list()
183 self.topology.node[nid]["ips"].append(ip)
185 def node_ip_annotations(self, nid):
186 return self.topology.node[nid].get("ips", [])
188 def annotate_node(self, nid, name, value):
189 if not isinstance(value, str) and not isinstance(value, int) and \
190 not isinstance(value, float) and not isinstance(value, bool):
191 raise RuntimeError("Non-serializable annotation")
193 self.topology.node[nid][name] = value
195 def node_annotation(self, nid, name):
196 return self.topology.node[nid].get(name)
198 def node_annotations(self, nid):
199 return list(self.topology.node[nid].keys())
201 def del_node_annotation(self, nid, name):
202 del self.topology.node[nid][name]
204 def annotate_edge(self, nid1, nid2, name, value):
205 if not isinstance(value, str) and not isinstance(value, int) and \
206 not isinstance(value, float) and not isinstance(value, bool):
207 raise RuntimeError("Non-serializable annotation")
209 self.topology.edge[nid1][nid2][name] = value
211 def annotate_edge_net(self, nid1, nid2, ip1, ip2, mask, network,
213 self.topology.edge[nid1][nid2]["net"] = dict()
214 self.topology.edge[nid1][nid2]["net"][nid1] = ip1
215 self.topology.edge[nid1][nid2]["net"][nid2] = ip2
216 self.topology.edge[nid1][nid2]["net"]["mask"] = mask
217 self.topology.edge[nid1][nid2]["net"]["network"] = network
218 self.topology.edge[nid1][nid2]["net"]["prefix"] = prefixlen
220 def edge_net_annotation(self, nid1, nid2):
221 return self.topology.edge[nid1][nid2].get("net", dict())
223 def edge_annotation(self, nid1, nid2, name):
224 return self.topology.edge[nid1][nid2].get(name)
226 def edge_annotations(self, nid1, nid2):
227 return list(self.topology.edge[nid1][nid2].keys())
229 def del_edge_annotation(self, nid1, nid2, name):
230 del self.topology.edge[nid1][nid2][name]
232 def assign_p2p_ips(self, network = "10.0.0.0", prefix = 8, version = 4):
233 """ Assign IP addresses to each end of each edge of the network graph,
234 computing all the point to point subnets and addresses in the network
237 :param network: Base network address used for subnetting.
240 :param prefix: Prefix for the base network address used for subnetting.
243 :param version: IP version (either 4 or 6).
247 if networkx.number_connected_components(self.topology) > 1:
248 raise RuntimeError("Disconnected graph!!")
250 # Assign IP addresses to host
251 netblock = "%s/%d" % (network, prefix)
253 net = ipaddress.ip_network(netblock)
256 net = ipaddress.ip_network(netblock)
259 raise RuntimeError("Invalid IP version %d" % version)
261 ## Clear all previusly assigned IPs
262 for nid in self.topology.nodes():
263 self.topology.node[nid]["ips"] = list()
265 ## Generate and assign new IPs
266 sub_itr = net.iter_subnets(new_prefix = new_prefix)
268 for nid1, nid2 in self.topology.edges():
269 #### Compute subnets for each link
271 # get a subnet of base_add with prefix /30
272 subnet = next(sub_itr)
273 mask = subnet.netmask.exploded
274 network = subnet.network.exploded
275 prefixlen = subnet.prefixlen
277 # get host addresses in that subnet
278 i = subnet.iterhosts()
284 self.annotate_edge_net(nid1, nid2, ip1, ip2, mask, network,
287 self.annotate_node_ip(nid1, ip1)
288 self.annotate_node_ip(nid2, ip2)
290 def get_p2p_info(self, nid1, nid2):
291 net = self.topology.edge[nid1][nid2]["net"]
292 return ( net[nid1], net[nid2], net["mask"], net["network"],
295 def set_source(self, nid):
296 self.topology.node[nid]["source"] = True
298 def is_source(self, nid):
299 return self.topology.node[nid].get("source")
301 def set_target(self, nid):
302 self.topology.node[nid]["target"] = True
304 def is_target(self, nid):
305 return self.topology.node[nid].get("target")
308 """ Returns the nodes that are targets """
309 return [nid for nid in self.topology.nodes() \
310 if self.topology.node[nid].get("target")]
313 """ Returns the nodes that are sources """
314 return [nid for nid in self.topology.nodes() \
315 if self.topology.node[nid].get("source")]
317 def select_target_zero(self):
318 """ Mark the node 0 as target
320 nid = 0 if 0 in self.topology.nodes() else "0"
323 def select_random_source(self, **kwargs):
324 """ Mark a random node as source.
327 # The ladder is a special case because is not symmetric.
328 if self.topo_type == TopologyType.LADDER:
329 total_nodes = self.order/2
331 leaf2 = total_nodes - 1
332 leaves = [leaf1, leaf2]
333 source = leaves.pop(random.randint(0, len(leaves) - 1))
335 # options must not be already sources or targets
336 options = [ k for k,v in self.topology.degree().items() \
337 if (not kwargs.get("is_leaf") or v == 1) \
338 and not self.topology.node[k].get("source") \
339 and not self.topology.node[k].get("target")]
340 source = options.pop(random.randint(0, len(options) - 1))
342 self.set_source(source)