X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=src%2Fnepi%2Futil%2Fnetgraph.py;h=c04f94df08396a100c9700f083dbfc79e41cbe13;hb=baf0ec72915b1290a0be284aab90b6ebdf057115;hp=c3ba81440280b37e473ba8d3c6dc5c510983979f;hpb=bac63fdc5983e2ade1902f711c1e7899d82ca4ae;p=nepi.git diff --git a/src/nepi/util/netgraph.py b/src/nepi/util/netgraph.py index c3ba8144..c04f94df 100644 --- a/src/nepi/util/netgraph.py +++ b/src/nepi/util/netgraph.py @@ -19,6 +19,7 @@ import ipaddr import networkx +import math import random class TopologyType: @@ -39,12 +40,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. @@ -78,25 +79,25 @@ class NetGraph(object): 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"): @@ -104,8 +105,8 @@ class NetGraph(object): self.select_random_leaf_source() @property - def graph(self): - return self._graph + def topology(self): + return self._topology @property def topo_type(self): @@ -113,32 +114,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) @@ -155,9 +154,8 @@ class NetGraph(object): # 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])]), + g.add_nodes_from(map(lambda nid: str(nid), graph.nodes())) + g.add_edges_from(map(lambda t: (str(t[0]), str(t[1])), graph.edges())) return g @@ -165,8 +163,8 @@ class NetGraph(object): 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) @@ -175,13 +173,61 @@ class NetGraph(object): 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 + + ## 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,33 +281,38 @@ 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 @@ -270,15 +326,15 @@ class NetGraph(object): # 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 = str(total_nodes) + leaf2 = str(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 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))