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