nepi/util/netgraph.py

   1 #
   2 #    NEPI, a framework to manage network experiments
   3 #    Copyright (C) 2013 INRIA
   4 #
   5 #    This program is free software: you can redistribute it and/or modify
   6 #    it under the terms of the GNU General Public License version 2 as
   7 #    published by the Free Software Foundation;
   8 #
   9 #    This program is distributed in the hope that it will be useful,
  10 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 #    GNU General Public License for more details.
  13 #
  14 #    You should have received a copy of the GNU General Public License
  15 #    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16 #
  17 # Author: Alina Quereilhac <alina.quereilhac@inria.fr>
  18
  19 import networkx
  20 import math
  21 import random
  22
  23 from six import next, PY2, PY3
  24 if PY2:
  25     import ipaddr
  26 else:
  27     import ipaddress
  28
  29
  30 class TopologyType:
  31     LINEAR = "linear"
  32     LADDER = "ladder"
  33     MESH = "mesh"
  34     TREE = "tree"
  35     STAR = "star"
  36     ADHOC = "adhoc"
  37
  38 ## TODO:
  39 ##      - AQ: Add support for hypergraphs (to be able to add hyper edges to
  40 ##        model CSMA or wireless networks)
  41
  42 class NetGraph(object):
  43     """ NetGraph represents a network topology.
  44     Network graphs are internally using the networkx library.
  45
  46     """
  47
  48     def __init__(self, **kwargs):
  49         """ A graph can be generated using a specified pattern
  50         (LADDER, MESH, TREE, etc), or provided as an argument.
  51
  52             :param topology: Undirected graph to use as internal representation
  53             :type topology: networkx.Graph
  54
  55             :param topo_type: One of TopologyType.{LINEAR,LADDER,MESH,TREE,STAR}
  56             used to automatically generate the topology graph.
  57             :type topo_type: TopologyType
  58
  59             :param node_count: Number of nodes in the topology to be generated.
  60             :type node_count: int
  61
  62             :param branches: Number of branches (arms) for the STAR topology.
  63             :type branches: int
  64
  65
  66             :param assign_ips: Automatically assign IP addresses to each node.
  67             :type assign_ips: bool
  68
  69             :param network: Base network segment for IP address assignment.
  70             :type network: str
  71
  72             :param prefix: Base network prefix for IP address assignment.
  73             :type prefix: int
  74
  75             :param version: IP version for IP address assignment.
  76             :type version: int
  77
  78             :param assign_st: Select source and target nodes on the graph.
  79             :type assign_st: bool
  80
  81             :param sources_targets: dictionary with the list of sources (key =
  82             "sources") and list of targets (key = "targets") if defined, ignore
  83             assign_st
  84             :type sources_targets: dictionary of lists
  85
  86             :param leaf_source: if True, random sources will be selected only
  87             from leaf nodes.
  88             :type leaf_source: bool
  89
  90         NOTE: Only point-to-point like network topologies are supported for now.
  91                 (Wireless and Ethernet networks were several nodes share the same
  92                 edge (hyperedge) can not be modeled for the moment).
  93
  94         """
  95         self._topology = kwargs.get("topology")
  96         self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC)
  97
  98         if not self.topology:
  99             if kwargs.get("node_count"):
 100                 node_count = kwargs["node_count"]
 101                 branches = kwargs.get("branches")
 102
 103                 self._topology = self.generate_topology(self.topo_type,
 104                         node_count, branches = branches)
 105             else:
 106                 self._topology = networkx.Graph()
 107
 108         if kwargs.get("assign_ips"):
 109             network = kwargs.get("network", "10.0.0.0")
 110             prefix = kwargs.get("prefix", 8)
 111             version = kwargs.get("version", 4)
 112
 113             self.assign_p2p_ips(network = network, prefix = prefix,
 114                     version = version)
 115
 116         sources_targets = kwargs.get("sources_targets")
 117         if sources_targets:
 118             [self.set_source(n) for n in sources_targets["sources"]]
 119             [self.set_target(n) for n in sources_targets["targets"]]
 120         elif kwargs.get("assign_st"):
 121             self.select_target_zero()
 122             self.select_random_source(is_leaf = kwargs.get("leaf_source"))
 123
 124     @property
 125     def topology(self):
 126         return self._topology
 127
 128     @property
 129     def topo_type(self):
 130         return self._topo_type
 131
 132     @property
 133     def order(self):
 134         return self.topology.order()
 135
 136     def nodes(self):
 137         return self.topology.nodes()
 138
 139     def edges(self):
 140         return self.topology.edges()
 141
 142     def generate_topology(self, topo_type, node_count, branches = None):
 143         if topo_type == TopologyType.LADDER:
 144             total_nodes = node_count/2
 145             graph = networkx.ladder_graph(total_nodes)
 146
 147         elif topo_type == TopologyType.LINEAR:
 148             graph = networkx.path_graph(node_count)
 149
 150         elif topo_type == TopologyType.MESH:
 151             graph = networkx.complete_graph(node_count)
 152
 153         elif topo_type == TopologyType.TREE:
 154             h = math.log(node_count + 1)/math.log(2) - 1
 155             graph = networkx.balanced_tree(2, h)
 156
 157         elif topo_type == TopologyType.STAR:
 158             graph = networkx.Graph()
 159             graph.add_node(0)
 160
 161             nodesinbranch = (node_count - 1)/ BRANCHES
 162             c = 1
 163
 164             for i in range(BRANCHES):
 165                 prev = 0
 166                 for n in range(1, nodesinbranch + 1):
 167                     graph.add_node(c)
 168                     graph.add_edge(prev, c)
 169                     prev = c
 170                     c += 1
 171
 172         return graph
 173
 174     def add_node(self, nid):
 175         if nid not in self.topology:
 176             self.topology.add_node(nid)
 177
 178     def add_edge(self, nid1, nid2):
 179         self.add_node(nid1)
 180         self.add_node( nid2)
 181
 182         if nid1 not in self.topology[nid2]:
 183             self.topology.add_edge(nid2, nid1)
 184
 185     def annotate_node_ip(self, nid, ip):
 186         if "ips" not in self.topology.node[nid]:
 187             self.topology.node[nid]["ips"] = list()
 188
 189         self.topology.node[nid]["ips"].append(ip)
 190
 191     def node_ip_annotations(self, nid):
 192         return self.topology.node[nid].get("ips", [])
 193
 194     def annotate_node(self, nid, name, value):
 195         if not isinstance(value, str) and not isinstance(value, int) and \
 196                 not isinstance(value, float) and not isinstance(value, bool):
 197             raise RuntimeError("Non-serializable annotation")
 198
 199         self.topology.node[nid][name] = value
 200
 201     def node_annotation(self, nid, name):
 202         return self.topology.node[nid].get(name)
 203
 204     def node_annotations(self, nid):
 205         retcod = self.topology.node[nid].keys()
 206         if PY3: retcod = list(retcod)
 207         return retcod
 208
 209     def del_node_annotation(self, nid, name):
 210         del self.topology.node[nid][name]
 211
 212     def annotate_edge(self, nid1, nid2, name, value):
 213         if not isinstance(value, str) and not isinstance(value, int) and \
 214                 not isinstance(value, float) and not isinstance(value, bool):
 215             raise RuntimeError("Non-serializable annotation")
 216
 217         self.topology.edge[nid1][nid2][name] = value
 218
 219     def annotate_edge_net(self, nid1, nid2, ip1, ip2, mask, network,
 220             prefixlen):
 221         self.topology.edge[nid1][nid2]["net"] = dict()
 222         self.topology.edge[nid1][nid2]["net"][nid1] = ip1
 223         self.topology.edge[nid1][nid2]["net"][nid2] = ip2
 224         self.topology.edge[nid1][nid2]["net"]["mask"] = mask
 225         self.topology.edge[nid1][nid2]["net"]["network"] = network
 226         self.topology.edge[nid1][nid2]["net"]["prefix"] = prefixlen
 227
 228     def edge_net_annotation(self, nid1, nid2):
 229         return self.topology.edge[nid1][nid2].get("net", dict())
 230
 231     def edge_annotation(self, nid1, nid2, name):
 232         return self.topology.edge[nid1][nid2].get(name)
 233
 234     def edge_annotations(self, nid1, nid2):
 235         retcod = self.topology.edge[nid1][nid2].keys()
 236         if PY3: retcod = list(retcod)
 237         return retcod
 238
 239     def del_edge_annotation(self, nid1, nid2, name):
 240         del self.topology.edge[nid1][nid2][name]
 241
 242     def assign_p2p_ips(self, network = "10.0.0.0", prefix = 8, version = 4):
 243         """ Assign IP addresses to each end of each edge of the network graph,
 244         computing all the point to point subnets and addresses in the network
 245         representation.
 246
 247             :param network: Base network address used for subnetting.
 248             :type network: str
 249
 250             :param prefix: Prefix for the base network address used for subnetting.
 251             :type prefixt: int
 252
 253             :param version: IP version (either 4 or 6).
 254             :type version: int
 255
 256         """
 257         if networkx.number_connected_components(self.topology) > 1:
 258             raise RuntimeError("Disconnected graph!!")
 259
 260         # Assign IP addresses to host
 261         netblock = "%s/%d" % (network, prefix)
 262         if version == 4:
 263             net = ipaddr.IPv4Network(netblock) if PY2 else ipaddress.ip_network(netblock)
 264             new_prefix = 30
 265         elif version == 6:
 266             net = ipaddr.IPv6Network(netblock) if PY2 else ipaddress.ip_network(netblock)
 267             new_prefix = 30
 268         else:
 269             raise RuntimeError("Invalid IP version %d" % version)
 270
 271         ## Clear all previusly assigned IPs
 272         for nid in self.topology.nodes():
 273             self.topology.node[nid]["ips"] = list()
 274
 275         ## Generate and assign new IPs
 276         sub_itr = net.iter_subnets(new_prefix = new_prefix)
 277
 278         for nid1, nid2 in self.topology.edges():
 279             #### Compute subnets for each link
 280
 281             # get a subnet of base_add with prefix /30
 282             subnet = next(sub_itr)
 283             mask = subnet.netmask.exploded
 284             network = subnet.network.exploded
 285             prefixlen = subnet.prefixlen
 286
 287             # get host addresses in that subnet
 288             i = subnet.iterhosts()
 289             addr1 = next(i)
 290             addr2 = next(i)
 291
 292             ip1 = addr1.exploded
 293             ip2 = addr2.exploded
 294             self.annotate_edge_net(nid1, nid2, ip1, ip2, mask, network,
 295                     prefixlen)
 296
 297             self.annotate_node_ip(nid1, ip1)
 298             self.annotate_node_ip(nid2, ip2)
 299
 300     def get_p2p_info(self, nid1, nid2):
 301         net = self.topology.edge[nid1][nid2]["net"]
 302         return ( net[nid1], net[nid2], net["mask"], net["network"],
 303                 net["prefixlen"] )
 304
 305     def set_source(self, nid):
 306         self.topology.node[nid]["source"] = True
 307
 308     def is_source(self, nid):
 309         return self.topology.node[nid].get("source")
 310
 311     def set_target(self, nid):
 312         self.topology.node[nid]["target"] = True
 313
 314     def is_target(self, nid):
 315         return self.topology.node[nid].get("target")
 316
 317     def targets(self):
 318         """ Returns the nodes that are targets """
 319         return [nid for nid in self.topology.nodes() \
 320                 if self.topology.node[nid].get("target")]
 321
 322     def sources(self):
 323         """ Returns the nodes that are sources """
 324         return [nid for nid in self.topology.nodes() \
 325                 if self.topology.node[nid].get("source")]
 326
 327     def select_target_zero(self):
 328         """ Mark the node 0 as target
 329         """
 330         nid = 0 if 0 in self.topology.nodes() else "0"
 331         self.set_target(nid)
 332
 333     def select_random_source(self, **kwargs):
 334         """  Mark a random node as source.
 335         """
 336
 337         # The ladder is a special case because is not symmetric.
 338         if self.topo_type == TopologyType.LADDER:
 339             total_nodes = self.order/2
 340             leaf1 = total_nodes
 341             leaf2 = total_nodes - 1
 342             leaves = [leaf1, leaf2]
 343             source = leaves.pop(random.randint(0, len(leaves) - 1))
 344         else:
 345             # options must not be already sources or targets
 346             options = [ k for k,v in self.topology.degree().items() \
 347                     if (not kwargs.get("is_leaf") or v == 1)  \
 348                         and not self.topology.node[k].get("source") \
 349                         and not self.topology.node[k].get("target")]
 350             source = options.pop(random.randint(0, len(options) - 1))
 351
 352         self.set_source(source)
 353