X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=src%2Fnepi%2Futil%2Fnetgraph.py;h=49a194bd85b603aa7725a978a83d04aaa2b91174;hb=6285ca51026efb69642eea9dfc7c480e722d84a9;hp=c3ba81440280b37e473ba8d3c6dc5c510983979f;hpb=bac63fdc5983e2ade1902f711c1e7899d82ca4ae;p=nepi.git diff --git a/src/nepi/util/netgraph.py b/src/nepi/util/netgraph.py index c3ba8144..49a194bd 100644 --- a/src/nepi/util/netgraph.py +++ b/src/nepi/util/netgraph.py @@ -3,9 +3,8 @@ # Copyright (C) 2013 INRIA # # This program is free software: you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation, either version 3 of the License, or -# (at your option) any later version. +# it under the terms of the GNU General Public License version 2 as +# published by the Free Software Foundation; # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -19,6 +18,7 @@ import ipaddr import networkx +import math import random class TopologyType: @@ -39,12 +39,12 @@ class NetGraph(object): """ - def __init__(self, *args, **kwargs): + def __init__(self, **kwargs): """ A graph can be generated using a specified pattern (LADDER, MESH, TREE, etc), or provided as an argument. - :param graph: Undirected graph to use as internal representation - :type graph: networkx.Graph + :param topology: Undirected graph to use as internal representation + :type topology: networkx.Graph :param topo_type: One of TopologyType.{LINEAR,LADDER,MESH,TREE,STAR} used to automatically generate the topology graph. @@ -69,43 +69,55 @@ class NetGraph(object): :param version: IP version for IP address assignment. :type version: int - :param assign_st: Select source and target nodes on the graph. :type assign_st: bool + :param sources_targets: dictionary with the list of sources (key = + "sources") and list of targets (key = "targets") if defined, ignore + assign_st + :type sources_targets: dictionary of lists + + :param leaf_source: if True, random sources will be selected only + from leaf nodes. + :type leaf_source: bool + NOTE: Only point-to-point like network topologies are supported for now. (Wireless and Ethernet networks were several nodes share the same edge (hyperedge) can not be modeled for the moment). """ - self._graph = kwargs.get("graph") - self._topo_type = TopologyType.ADHOC + self._topology = kwargs.get("topology") + self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC) - if not self._graph and kwargs.get("topo_type") and \ - kwargs.get("node_count"): - topo_type = kwargs["topo_type"] - node_count = kwargs["node_count"] - branches = kwargs.get("branches") + if not self.topology: + if kwargs.get("node_count"): + node_count = kwargs["node_count"] + branches = kwargs.get("branches") - self._topo_type = topo_type - self._graph = self.generate_grap(topo_type, node_count, - branches = branches) + self._topology = self.generate_topology(self.topo_type, + node_count, branches = branches) + else: + self._topology = networkx.Graph() if kwargs.get("assign_ips"): network = kwargs.get("network", "10.0.0.0") prefix = kwargs.get("prefix", 8) version = kwargs.get("version", 4) - self.assign_p2p_ips(self, network = network, prefix = prefix, + self.assign_p2p_ips(network = network, prefix = prefix, version = version) - if kwargs.get("assign_st"): + sources_targets = kwargs.get("sources_targets") + if sources_targets: + [self.set_source(n) for n in sources_targets["sources"]] + [self.set_target(n) for n in sources_targets["targets"]] + elif kwargs.get("assign_st"): self.select_target_zero() - self.select_random_leaf_source() + self.select_random_source(is_leaf = kwargs.get("leaf_source")) @property - def graph(self): - return self._graph + def topology(self): + return self._topology @property def topo_type(self): @@ -113,32 +125,30 @@ class NetGraph(object): @property def order(self): - return self.graph.order() + return self.topology.order() - @property def nodes(self): - return self.graph.nodes() + return self.topology.nodes() - @property def edges(self): - return self.graph.edges() + return self.topology.edges() - def generate_graph(self, topo_type, node_count, branches = None): - if topo_type == LADDER: + def generate_topology(self, topo_type, node_count, branches = None): + if topo_type == TopologyType.LADDER: total_nodes = node_count/2 graph = networkx.ladder_graph(total_nodes) - elif topo_type == LINEAR: + elif topo_type == TopologyType.LINEAR: graph = networkx.path_graph(node_count) - elif topo_type == MESH: + elif topo_type == TopologyType.MESH: graph = networkx.complete_graph(node_count) - elif topo_type == TREE: + elif topo_type == TopologyType.TREE: h = math.log(node_count + 1)/math.log(2) - 1 graph = networkx.balanced_tree(2, h) - elif topo_type == STAR: + elif topo_type == TopologyType.STAR: graph = networkx.Graph() graph.add_node(0) @@ -153,35 +163,71 @@ class NetGraph(object): prev = c c += 1 - # node ids are int, make them str - g = networkx.Graph() - g.add_nodes_from(map(lambda nid: NODES[str(nid)], - graph.nodes())) - g.add_edges_from(map(lambda t: (NODES[str(t[0])], NODES[str(t[1])]), - graph.edges())) - - return g + return graph def add_node(self, nid): - nid = str(nid) - - if nid not in self.graph: - self.graph.add_node(nid) + if nid not in self.topology: + self.topology.add_node(nid) def add_edge(self, nid1, nid2): - nid1 = str(nid1) - nid2 = str(nid2) - self.add_node(nid1) self.add_node( nid2) - if nid1 not in self.graph[nid2]: - self.graph.add_edge(nid2, nid1) - - # The weight of the edge is the delay of the link - self.graph.edge[nid1][nid2]["weight"] = None - # confidence interval of the mean RTT - self.graph.edge[nid1][nid2]["weight_ci"] = None + if nid1 not in self.topology[nid2]: + self.topology.add_edge(nid2, nid1) + + def annotate_node_ip(self, nid, ip): + if "ips" not in self.topology.node[nid]: + self.topology.node[nid]["ips"] = list() + + self.topology.node[nid]["ips"].append(ip) + + def node_ip_annotations(self, nid): + return self.topology.node[nid].get("ips", []) + + def annotate_node(self, nid, name, value): + if not isinstance(value, str) and not isinstance(value, int) and \ + not isinstance(value, float) and not isinstance(value, bool): + raise RuntimeError("Non-serializable annotation") + + self.topology.node[nid][name] = value + + def node_annotation(self, nid, name): + return self.topology.node[nid].get(name) + + def node_annotations(self, nid): + return self.topology.node[nid].keys() + + def del_node_annotation(self, nid, name): + del self.topology.node[nid][name] + + def annotate_edge(self, nid1, nid2, name, value): + if not isinstance(value, str) and not isinstance(value, int) and \ + not isinstance(value, float) and not isinstance(value, bool): + raise RuntimeError("Non-serializable annotation") + + self.topology.edge[nid1][nid2][name] = value + + def annotate_edge_net(self, nid1, nid2, ip1, ip2, mask, network, + prefixlen): + self.topology.edge[nid1][nid2]["net"] = dict() + self.topology.edge[nid1][nid2]["net"][nid1] = ip1 + self.topology.edge[nid1][nid2]["net"][nid2] = ip2 + self.topology.edge[nid1][nid2]["net"]["mask"] = mask + self.topology.edge[nid1][nid2]["net"]["network"] = network + self.topology.edge[nid1][nid2]["net"]["prefix"] = prefixlen + + def edge_net_annotation(self, nid1, nid2): + return self.topology.edge[nid1][nid2].get("net", dict()) + + def edge_annotation(self, nid1, nid2, name): + return self.topology.edge[nid1][nid2].get(name) + + def edge_annotations(self, nid1, nid2): + return self.topology.edge[nid1][nid2].keys() + + def del_edge_annotation(self, nid1, nid2, name): + del self.topology.edge[nid1][nid2][name] def assign_p2p_ips(self, network = "10.0.0.0", prefix = 8, version = 4): """ Assign IP addresses to each end of each edge of the network graph, @@ -198,23 +244,28 @@ class NetGraph(object): :type version: int """ - if len(networkx.connected_components(self.graph)) > 1: + if networkx.number_connected_components(self.topology) > 1: raise RuntimeError("Disconnected graph!!") # Assign IP addresses to host netblock = "%s/%d" % (network, prefix) if version == 4: net = ipaddr.IPv4Network(netblock) - new_prefix = 31 + new_prefix = 30 elif version == 6: net = ipaddr.IPv6Network(netblock) - new_prefix = 31 + new_prefix = 30 else: - raise RuntimeError, "Invalid IP version %d" % version + raise RuntimeError("Invalid IP version %d" % version) + + ## Clear all previusly assigned IPs + for nid in self.topology.nodes(): + self.topology.node[nid]["ips"] = list() + ## Generate and assign new IPs sub_itr = net.iter_subnets(new_prefix = new_prefix) - - for nid1, nid2 in self.graph.edges(): + + for nid1, nid2 in self.topology.edges(): #### Compute subnets for each link # get a subnet of base_add with prefix /30 @@ -230,56 +281,62 @@ class NetGraph(object): ip1 = addr1.exploded ip2 = addr2.exploded - self.graph.edge[nid1][nid2]["net"] = dict() - self.graph.edge[nid1][nid2]["net"][nid1] = ip1 - self.graph.edge[nid1][nid2]["net"][nid2] = ip2 - self.graph.edge[nid1][nid2]["net"]["mask"] = mask - self.graph.edge[nid1][nid2]["net"]["network"] = mask - self.graph.edge[nid1][nid2]["net"]["prefix"] = prefixlen + self.annotate_edge_net(nid1, nid2, ip1, ip2, mask, network, + prefixlen) + + self.annotate_node_ip(nid1, ip1) + self.annotate_node_ip(nid2, ip2) def get_p2p_info(self, nid1, nid2): - net = self.graph.edge[nid1][nid2]["net"] + net = self.topology.edge[nid1][nid2]["net"] return ( net[nid1], net[nid2], net["mask"], net["network"], net["prefixlen"] ) def set_source(self, nid): - graph.node[nid]["source"] = True + self.topology.node[nid]["source"] = True + + def is_source(self, nid): + return self.topology.node[nid].get("source") def set_target(self, nid): - graph.node[nid]["target"] = True + self.topology.node[nid]["target"] = True + + def is_target(self, nid): + return self.topology.node[nid].get("target") def targets(self): """ Returns the nodes that are targets """ - return [nid for nid in self.graph.nodes() \ - if self.graph.node[nid].get("target")] + return [nid for nid in self.topology.nodes() \ + if self.topology.node[nid].get("target")] def sources(self): """ Returns the nodes that are sources """ - return [nid for nid in self.graph.nodes() \ - if self.graph.node[nid].get("sources")] + return [nid for nid in self.topology.nodes() \ + if self.topology.node[nid].get("source")] def select_target_zero(self): - """ Marks the node 0 as target + """ Mark the node 0 as target """ - self.set_target("0") + nid = 0 if 0 in self.topology.nodes() else "0" + self.set_target(nid) - def select_random_leaf_source(self): - """ Marks a random leaf node as source. + def select_random_source(self, **kwargs): + """ Mark a random node as source. """ # The ladder is a special case because is not symmetric. if self.topo_type == TopologyType.LADDER: total_nodes = self.order/2 - leaf1 = str(total_nodes - 1) - leaf2 = str(nodes - 1) + leaf1 = total_nodes + leaf2 = total_nodes - 1 leaves = [leaf1, leaf2] source = leaves.pop(random.randint(0, len(leaves) - 1)) else: # options must not be already sources or targets - options = [ k for k,v in graph.degree().iteritems() \ - if v == 1 and not graph.node[k].get("source") \ - and not graph.node[k].get("target")] - + options = [ k for k,v in self.topology.degree().iteritems() \ + if (not kwargs.get("is_leaf") or v == 1) \ + and not self.topology.node[k].get("source") \ + and not self.topology.node[k].get("target")] source = options.pop(random.randint(0, len(options) - 1)) self.set_source(source)