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