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>
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.
73 :param assign_st: Select source and target nodes on the graph.
76 NOTE: Only point-to-point like network topologies are supported for now.
77 (Wireless and Ethernet networks were several nodes share the same
78 edge (hyperedge) can not be modeled for the moment).
81 self._topology = kwargs.get("topology")
82 self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC)
85 if kwargs.get("node_count"):
86 node_count = kwargs["node_count"]
87 branches = kwargs.get("branches")
89 self._topology = self.generate_topology(self.topo_type,
90 node_count, branches = branches)
92 self._topology = networkx.Graph()
94 if kwargs.get("assign_ips"):
95 network = kwargs.get("network", "10.0.0.0")
96 prefix = kwargs.get("prefix", 8)
97 version = kwargs.get("version", 4)
99 self.assign_p2p_ips(network = network, prefix = prefix,
102 if kwargs.get("assign_st"):
103 self.select_target_zero()
104 self.select_random_leaf_source()
108 return self._topology
112 return self._topo_type
116 return self.topology.order()
119 return self.topology.nodes()
122 return self.topology.edges()
124 def generate_topology(self, topo_type, node_count, branches = None):
125 if topo_type == TopologyType.LADDER:
126 total_nodes = node_count/2
127 graph = networkx.ladder_graph(total_nodes)
129 elif topo_type == TopologyType.LINEAR:
130 graph = networkx.path_graph(node_count)
132 elif topo_type == TopologyType.MESH:
133 graph = networkx.complete_graph(node_count)
135 elif topo_type == TopologyType.TREE:
136 h = math.log(node_count + 1)/math.log(2) - 1
137 graph = networkx.balanced_tree(2, h)
139 elif topo_type == TopologyType.STAR:
140 graph = networkx.Graph()
143 nodesinbranch = (node_count - 1)/ BRANCHES
146 for i in xrange(BRANCHES):
148 for n in xrange(1, nodesinbranch + 1):
150 graph.add_edge(prev, c)
154 # node ids are int, make them str
156 g.add_nodes_from(map(lambda nid: str(nid), graph.nodes()))
157 g.add_edges_from(map(lambda t: (str(t[0]), str(t[1])),
162 def add_node(self, nid):
165 if nid not in self.topology:
166 self.topology.add_node(nid)
168 def add_edge(self, nid1, nid2):
175 if nid1 not in self.topology[nid2]:
176 self.topology.add_edge(nid2, nid1)
178 def annotate_node_ip(self, nid, ip):
179 if "ips" not in self.topology.node[nid]:
180 self.topology.node[nid]["ips"] = list()
182 self.topology.node[nid]["ips"].append(ip)
184 def node_ip_annotations(self, nid):
185 return self.topology.node[nid].get("ips", [])
187 def annotate_node(self, nid, name, value):
188 if not isinstance(value, str) and not isinstance(value, int) and \
189 not isinstance(value, float) and not isinstance(value, bool):
190 raise RuntimeError, "Non-serializable annotation"
192 self.topology.node[nid][name] = value
194 def node_annotation(self, nid, name):
195 return self.topology.node[nid].get(name)
197 def node_annotations(self, nid):
198 return self.topology.node[nid].keys()
200 def del_node_annotation(self, nid, name):
201 del self.topology.node[nid][name]
203 def annotate_edge(self, nid1, nid2, name, value):
204 if not isinstance(value, str) and not isinstance(value, int) and \
205 not isinstance(value, float) and not isinstance(value, bool):
206 raise RuntimeError, "Non-serializable annotation"
208 self.topology.edge[nid1][nid2][name] = value
210 def annotate_edge_net(self, nid1, nid2, ip1, ip2, mask, network,
212 self.topology.edge[nid1][nid2]["net"] = dict()
213 self.topology.edge[nid1][nid2]["net"][nid1] = ip1
214 self.topology.edge[nid1][nid2]["net"][nid2] = ip2
215 self.topology.edge[nid1][nid2]["net"]["mask"] = mask
216 self.topology.edge[nid1][nid2]["net"]["network"] = network
217 self.topology.edge[nid1][nid2]["net"]["prefix"] = prefixlen
219 def edge_net_annotation(self, nid1, nid2):
220 return self.topology.edge[nid1][nid2].get("net", dict())
222 def edge_annotation(self, nid1, nid2, name):
223 return self.topology.edge[nid1][nid2].get(name)
225 def edge_annotations(self, nid1, nid2):
226 return self.topology.edge[nid1][nid2].keys()
228 def del_edge_annotation(self, nid1, nid2, name):
229 del self.topology.edge[nid1][nid2][name]
231 def assign_p2p_ips(self, network = "10.0.0.0", prefix = 8, version = 4):
232 """ Assign IP addresses to each end of each edge of the network graph,
233 computing all the point to point subnets and addresses in the network
236 :param network: Base network address used for subnetting.
239 :param prefix: Prefix for the base network address used for subnetting.
242 :param version: IP version (either 4 or 6).
246 if networkx.number_connected_components(self.topology) > 1:
247 raise RuntimeError("Disconnected graph!!")
249 # Assign IP addresses to host
250 netblock = "%s/%d" % (network, prefix)
252 net = ipaddr.IPv4Network(netblock)
255 net = ipaddr.IPv6Network(netblock)
258 raise RuntimeError, "Invalid IP version %d" % version
260 ## Clear all previusly assigned IPs
261 for nid in self.topology.nodes():
262 self.topology.node[nid]["ips"] = list()
264 ## Generate and assign new IPs
265 sub_itr = net.iter_subnets(new_prefix = new_prefix)
267 for nid1, nid2 in self.topology.edges():
268 #### Compute subnets for each link
270 # get a subnet of base_add with prefix /30
271 subnet = sub_itr.next()
272 mask = subnet.netmask.exploded
273 network = subnet.network.exploded
274 prefixlen = subnet.prefixlen
276 # get host addresses in that subnet
277 i = subnet.iterhosts()
283 self.annotate_edge_net(nid1, nid2, ip1, ip2, mask, network,
286 self.annotate_node_ip(nid1, ip1)
287 self.annotate_node_ip(nid2, ip2)
289 def get_p2p_info(self, nid1, nid2):
290 net = self.topology.edge[nid1][nid2]["net"]
291 return ( net[nid1], net[nid2], net["mask"], net["network"],
294 def set_source(self, nid):
295 self.topology.node[nid]["source"] = True
297 def is_source(self, nid):
298 return self.topology.node[nid].get("source")
300 def set_target(self, nid):
301 self.topology.node[nid]["target"] = True
303 def is_target(self, nid):
304 return self.topology.node[nid].get("target")
307 """ Returns the nodes that are targets """
308 return [nid for nid in self.topology.nodes() \
309 if self.topology.node[nid].get("target")]
312 """ Returns the nodes that are sources """
313 return [nid for nid in self.topology.nodes() \
314 if self.topology.node[nid].get("source")]
316 def select_target_zero(self):
317 """ Marks the node 0 as target
321 def select_random_leaf_source(self):
322 """ Marks a random leaf node as source.
325 # The ladder is a special case because is not symmetric.
326 if self.topo_type == TopologyType.LADDER:
327 total_nodes = self.order/2
328 leaf1 = str(total_nodes - 1)
329 leaf2 = str(nodes - 1)
330 leaves = [leaf1, leaf2]
331 source = leaves.pop(random.randint(0, len(leaves) - 1))
333 # options must not be already sources or targets
334 options = [ k for k,v in self.topology.degree().iteritems() \
335 if v == 1 and not self.topology.node[k].get("source") \
336 and not self.topology.node[k].get("target")]
338 source = options.pop(random.randint(0, len(options) - 1))
340 self.set_source(source)