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