# 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
import ipaddr
import networkx
+import math
import random
class TopologyType:
""" 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.
: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_graph(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):
@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):
+ 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)
prev = c
c += 1
- # node ids are int, make them str
- g = networkx.Graph()
- 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
+ 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.graph.node[nid]:
- self.graph.node[nid]["ips"] = list()
-
- self.graph.node[nid]["ips"].append(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):
- self.graph.node[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.graph.node[nid].get(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.graph.node[nid][name]
+ del self.topology.node[nid][name]
def annotate_edge(self, nid1, nid2, name, value):
- self.graph.edge[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.graph.edge[nid1][nid2].get(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.graph.edge[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,
: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.graph.node():
- self.graph.node[nid]["ips"] = list()
+ 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
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):
- self.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):
- self.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("source")]
+ 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 self.graph.degree().iteritems() \
- if v == 1 and not self.graph.node[k].get("source") \
- and not self.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)
git://git.onelab.eu / nepi.git / blobdiff