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 as published by
7 # the Free Software Foundation, either version 3 of the License, or
8 # (at your option) any later version.
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU General Public License for more details.
15 # You should have received a copy of the GNU General Public License
16 # along with this program. If not, see <http://www.gnu.org/licenses/>.
18 # Author: Alina Quereilhac <alina.quereilhac@inria.fr>
34 ## - AQ: Add support for hypergraphs (to be able to add hyper edges to
35 ## model CSMA or wireless networks)
37 class NetGraph(object):
38 """ NetGraph represents a network topology.
39 Network graphs are internally using the networkx library.
43 def __init__(self, **kwargs):
44 """ A graph can be generated using a specified pattern
45 (LADDER, MESH, TREE, etc), or provided as an argument.
47 :param topology: Undirected graph to use as internal representation
48 :type topology: networkx.Graph
50 :param topo_type: One of TopologyType.{LINEAR,LADDER,MESH,TREE,STAR}
51 used to automatically generate the topology graph.
52 :type topo_type: TopologyType
54 :param node_count: Number of nodes in the topology to be generated.
57 :param branches: Number of branches (arms) for the STAR topology.
61 :param assign_ips: Automatically assign IP addresses to each node.
62 :type assign_ips: bool
64 :param network: Base network segment for IP address assignment.
67 :param prefix: Base network prefix for IP address assignment.
70 :param version: IP version for IP address assignment.
73 :param assign_st: Select source and target nodes on the graph.
76 :param sources_targets: dictionary with the list of sources (key =
77 "sources") and list of targets (key = "targets") if defined, ignore
79 :type sources_targets: dictionary of lists
81 :param leaf_source: if True, random sources will be selected only
83 :type leaf_source: bool
85 NOTE: Only point-to-point like network topologies are supported for now.
86 (Wireless and Ethernet networks were several nodes share the same
87 edge (hyperedge) can not be modeled for the moment).
90 self._topology = kwargs.get("topology")
91 self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC)
94 if kwargs.get("node_count"):
95 node_count = kwargs["node_count"]
96 branches = kwargs.get("branches")
98 self._topology = self.generate_topology(self.topo_type,
99 node_count, branches = branches)
101 self._topology = networkx.Graph()
103 if kwargs.get("assign_ips"):
104 network = kwargs.get("network", "10.0.0.0")
105 prefix = kwargs.get("prefix", 8)
106 version = kwargs.get("version", 4)
108 self.assign_p2p_ips(network = network, prefix = prefix,
111 sources_targets = kwargs.get("sources_targets")
113 [self.set_source(n) for n in sources_targets["sources"]]
114 [self.set_target(n) for n in sources_targets["targets"]]
115 elif kwargs.get("assign_st"):
116 self.select_target_zero()
117 self.select_random_source(is_leaf = kwargs.get("leaf_source"))
121 return self._topology
125 return self._topo_type
129 return self.topology.order()
132 return self.topology.nodes()
135 return self.topology.edges()
137 def generate_topology(self, topo_type, node_count, branches = None):
138 if topo_type == TopologyType.LADDER:
139 total_nodes = node_count/2
140 graph = networkx.ladder_graph(total_nodes)
142 elif topo_type == TopologyType.LINEAR:
143 graph = networkx.path_graph(node_count)
145 elif topo_type == TopologyType.MESH:
146 graph = networkx.complete_graph(node_count)
148 elif topo_type == TopologyType.TREE:
149 h = math.log(node_count + 1)/math.log(2) - 1
150 graph = networkx.balanced_tree(2, h)
152 elif topo_type == TopologyType.STAR:
153 graph = networkx.Graph()
156 nodesinbranch = (node_count - 1)/ BRANCHES
159 for i in xrange(BRANCHES):
161 for n in xrange(1, nodesinbranch + 1):
163 graph.add_edge(prev, c)
169 def add_node(self, nid):
170 if nid not in self.topology:
171 self.topology.add_node(nid)
173 def add_edge(self, nid1, nid2):
177 if nid1 not in self.topology[nid2]:
178 self.topology.add_edge(nid2, nid1)
180 def annotate_node_ip(self, nid, ip):
181 if "ips" not in self.topology.node[nid]:
182 self.topology.node[nid]["ips"] = list()
184 self.topology.node[nid]["ips"].append(ip)
186 def node_ip_annotations(self, nid):
187 return self.topology.node[nid].get("ips", [])
189 def annotate_node(self, nid, name, value):
190 if not isinstance(value, str) and not isinstance(value, int) and \
191 not isinstance(value, float) and not isinstance(value, bool):
192 raise RuntimeError, "Non-serializable annotation"
194 self.topology.node[nid][name] = value
196 def node_annotation(self, nid, name):
197 return self.topology.node[nid].get(name)
199 def node_annotations(self, nid):
200 return self.topology.node[nid].keys()
202 def del_node_annotation(self, nid, name):
203 del self.topology.node[nid][name]
205 def annotate_edge(self, nid1, nid2, name, value):
206 if not isinstance(value, str) and not isinstance(value, int) and \
207 not isinstance(value, float) and not isinstance(value, bool):
208 raise RuntimeError, "Non-serializable annotation"
210 self.topology.edge[nid1][nid2][name] = value
212 def annotate_edge_net(self, nid1, nid2, ip1, ip2, mask, network,
214 self.topology.edge[nid1][nid2]["net"] = dict()
215 self.topology.edge[nid1][nid2]["net"][nid1] = ip1
216 self.topology.edge[nid1][nid2]["net"][nid2] = ip2
217 self.topology.edge[nid1][nid2]["net"]["mask"] = mask
218 self.topology.edge[nid1][nid2]["net"]["network"] = network
219 self.topology.edge[nid1][nid2]["net"]["prefix"] = prefixlen
221 def edge_net_annotation(self, nid1, nid2):
222 return self.topology.edge[nid1][nid2].get("net", dict())
224 def edge_annotation(self, nid1, nid2, name):
225 return self.topology.edge[nid1][nid2].get(name)
227 def edge_annotations(self, nid1, nid2):
228 return self.topology.edge[nid1][nid2].keys()
230 def del_edge_annotation(self, nid1, nid2, name):
231 del self.topology.edge[nid1][nid2][name]
233 def assign_p2p_ips(self, network = "10.0.0.0", prefix = 8, version = 4):
234 """ Assign IP addresses to each end of each edge of the network graph,
235 computing all the point to point subnets and addresses in the network
238 :param network: Base network address used for subnetting.
241 :param prefix: Prefix for the base network address used for subnetting.
244 :param version: IP version (either 4 or 6).
248 if networkx.number_connected_components(self.topology) > 1:
249 raise RuntimeError("Disconnected graph!!")
251 # Assign IP addresses to host
252 netblock = "%s/%d" % (network, prefix)
254 net = ipaddr.IPv4Network(netblock)
257 net = ipaddr.IPv6Network(netblock)
260 raise RuntimeError, "Invalid IP version %d" % version
262 ## Clear all previusly assigned IPs
263 for nid in self.topology.nodes():
264 self.topology.node[nid]["ips"] = list()
266 ## Generate and assign new IPs
267 sub_itr = net.iter_subnets(new_prefix = new_prefix)
269 for nid1, nid2 in self.topology.edges():
270 #### Compute subnets for each link
272 # get a subnet of base_add with prefix /30
273 subnet = sub_itr.next()
274 mask = subnet.netmask.exploded
275 network = subnet.network.exploded
276 prefixlen = subnet.prefixlen
278 # get host addresses in that subnet
279 i = subnet.iterhosts()
285 self.annotate_edge_net(nid1, nid2, ip1, ip2, mask, network,
288 self.annotate_node_ip(nid1, ip1)
289 self.annotate_node_ip(nid2, ip2)
291 def get_p2p_info(self, nid1, nid2):
292 net = self.topology.edge[nid1][nid2]["net"]
293 return ( net[nid1], net[nid2], net["mask"], net["network"],
296 def set_source(self, nid):
297 self.topology.node[nid]["source"] = True
299 def is_source(self, nid):
300 return self.topology.node[nid].get("source")
302 def set_target(self, nid):
303 self.topology.node[nid]["target"] = True
305 def is_target(self, nid):
306 return self.topology.node[nid].get("target")
309 """ Returns the nodes that are targets """
310 return [nid for nid in self.topology.nodes() \
311 if self.topology.node[nid].get("target")]
314 """ Returns the nodes that are sources """
315 return [nid for nid in self.topology.nodes() \
316 if self.topology.node[nid].get("source")]
318 def select_target_zero(self):
319 """ Mark the node 0 as target
321 nid = 0 if 0 in self.topology.nodes() else "0"
324 def select_random_source(self, **kwargs):
325 """ Mark a random node as source.
328 # The ladder is a special case because is not symmetric.
329 if self.topo_type == TopologyType.LADDER:
330 total_nodes = self.order/2
332 leaf2 = total_nodes - 1
333 leaves = [leaf1, leaf2]
334 source = leaves.pop(random.randint(0, len(leaves) - 1))
336 # options must not be already sources or targets
337 options = [ k for k,v in self.topology.degree().iteritems() \
338 if (not kwargs.get("is_leaf") or v == 1) \
339 and not self.topology.node[k].get("source") \
340 and not self.topology.node[k].get("target")]
341 source = options.pop(random.randint(0, len(options) - 1))
343 self.set_source(source)