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.
74 :param assign_st: Select source and target nodes on the graph.
77 NOTE: Only point-to-point like network topologies are supported for now.
78 (Wireless and Ethernet networks were several nodes share the same
79 edge (hyperedge) can not be modeled for the moment).
82 self._topology = kwargs.get("topology")
83 self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC)
86 if kwargs.get("node_count"):
87 node_count = kwargs["node_count"]
88 branches = kwargs.get("branches")
90 self._topology = self.generate_topology(self.topo_type,
91 node_count, branches = branches)
93 self._topology = networkx.Graph()
95 if kwargs.get("assign_ips"):
96 network = kwargs.get("network", "10.0.0.0")
97 prefix = kwargs.get("prefix", 8)
98 version = kwargs.get("version", 4)
100 self.assign_p2p_ips(network = network, prefix = prefix,
103 if kwargs.get("assign_st"):
104 self.select_target_zero()
105 self.select_random_leaf_source()
109 return self._topology
113 return self._topo_type
117 return self.topology.order()
120 return self.topology.nodes()
123 return self.topology.edges()
125 def generate_topology(self, topo_type, node_count, branches = None):
126 if topo_type == TopologyType.LADDER:
127 total_nodes = node_count/2
128 graph = networkx.ladder_graph(total_nodes)
130 elif topo_type == TopologyType.LINEAR:
131 graph = networkx.path_graph(node_count)
133 elif topo_type == TopologyType.MESH:
134 graph = networkx.complete_graph(node_count)
136 elif topo_type == TopologyType.TREE:
137 h = math.log(node_count + 1)/math.log(2) - 1
138 graph = networkx.balanced_tree(2, h)
140 elif topo_type == TopologyType.STAR:
141 graph = networkx.Graph()
144 nodesinbranch = (node_count - 1)/ BRANCHES
147 for i in xrange(BRANCHES):
149 for n in xrange(1, nodesinbranch + 1):
151 graph.add_edge(prev, c)
155 # node ids are int, make them str
157 g.add_nodes_from(map(lambda nid: str(nid), graph.nodes()))
158 g.add_edges_from(map(lambda t: (str(t[0]), str(t[1])),
163 def add_node(self, nid):
166 if nid not in self.topology:
167 self.topology.add_node(nid)
169 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 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 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 = ipaddr.IPv4Network(netblock)
256 net = ipaddr.IPv6Network(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 = sub_itr.next()
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 """ Marks the node 0 as target
322 def select_random_leaf_source(self):
323 """ Marks a random leaf node as source.
326 # The ladder is a special case because is not symmetric.
327 if self.topo_type == TopologyType.LADDER:
328 total_nodes = self.order/2
329 leaf1 = str(total_nodes)
330 leaf2 = str(total_nodes - 1)
331 leaves = [leaf1, leaf2]
332 source = leaves.pop(random.randint(0, len(leaves) - 1))
334 # options must not be already sources or targets
335 options = [ k for k,v in self.topology.degree().iteritems() \
336 if v == 1 and not self.topology.node[k].get("source") \
337 and not self.topology.node[k].get("target")]
339 source = options.pop(random.randint(0, len(options) - 1))
341 self.set_source(source)