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
  74             :param assign_st: Select source and target nodes on the graph.
  75             :type assign_st: bool
  76
  77         NOTE: Only point-to-point like network topologies are supported for now.
  78                 (Wireless and Ethernet networks were several nodes share the same
  79                 edge (hyperedge) can not be modeled for the moment).
  80
  81         """
  82         self._topology = kwargs.get("topology")
  83         self._topo_type = kwargs.get("topo_type", TopologyType.ADHOC)
  84
  85         if not self.topology:
  86             if kwargs.get("node_count"):
  87                 node_count = kwargs["node_count"]
  88                 branches = kwargs.get("branches")
  89
  90                 self._topology = self.generate_topology(self.topo_type,
  91                         node_count, branches = branches)
  92             else:
  93                 self._topology = networkx.Graph()
  94
  95         if kwargs.get("assign_ips"):
  96             network = kwargs.get("network", "10.0.0.0")
  97             prefix = kwargs.get("prefix", 8)
  98             version = kwargs.get("version", 4)
  99
 100             self.assign_p2p_ips(network = network, prefix = prefix,
 101                     version = version)
 102
 103         if kwargs.get("assign_st"):
 104             self.select_target_zero()
 105             self.select_random_leaf_source()
 106
 107     @property
 108     def topology(self):
 109         return self._topology
 110
 111     @property
 112     def topo_type(self):
 113         return self._topo_type
 114
 115     @property
 116     def order(self):
 117         return self.topology.order()
 118
 119     def nodes(self):
 120         return self.topology.nodes()
 121
 122     def edges(self):
 123         return self.topology.edges()
 124
 125     def generate_topology(self, topo_type, node_count, branches = None):
 126         if topo_type == TopologyType.LADDER:
 127             total_nodes = node_count/2
 128             graph = networkx.ladder_graph(total_nodes)
 129
 130         elif topo_type == TopologyType.LINEAR:
 131             graph = networkx.path_graph(node_count)
 132
 133         elif topo_type == TopologyType.MESH:
 134             graph = networkx.complete_graph(node_count)
 135
 136         elif topo_type == TopologyType.TREE:
 137             h = math.log(node_count + 1)/math.log(2) - 1
 138             graph = networkx.balanced_tree(2, h)
 139
 140         elif topo_type == TopologyType.STAR:
 141             graph = networkx.Graph()
 142             graph.add_node(0)
 143
 144             nodesinbranch = (node_count - 1)/ BRANCHES
 145             c = 1
 146
 147             for i in xrange(BRANCHES):
 148                 prev = 0
 149                 for n in xrange(1, nodesinbranch + 1):
 150                     graph.add_node(c)
 151                     graph.add_edge(prev, c)
 152                     prev = c
 153                     c += 1
 154
 155         # node ids are int, make them str
 156         g = networkx.Graph()
 157         g.add_nodes_from(map(lambda nid: str(nid), graph.nodes()))
 158         g.add_edges_from(map(lambda t: (str(t[0]), str(t[1])),
 159             graph.edges()))
 160
 161         return g
 162
 163     def add_node(self, nid):
 164         nid = str(nid)
 165
 166         if nid not in self.topology:
 167             self.topology.add_node(nid)
 168
 169     def add_edge(self, nid1, nid2):
 170         nid1 = str(nid1)
 171         nid2 = str(nid2)
 172
 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         """ Marks the node 0 as target
 319         """
 320         self.set_target("0")
 321
 322     def select_random_leaf_source(self):
 323         """  Marks a random leaf node as source.
 324         """
 325
 326         # The ladder is a special case because is not symmetric.
 327         if self.topo_type == TopologyType.LADDER:
 328             total_nodes = self.order/2
 329             leaf1 = str(total_nodes)
 330             leaf2 = str(total_nodes - 1)
 331             leaves = [leaf1, leaf2]
 332             source = leaves.pop(random.randint(0, len(leaves) - 1))
 333         else:
 334             # options must not be already sources or targets
 335             options = [ k for k,v in self.topology.degree().iteritems() \
 336                     if v == 1 and not self.topology.node[k].get("source") \
 337                         and not self.topology.node[k].get("target")]
 338
 339             source = options.pop(random.randint(0, len(options) - 1))
 340
 341         self.set_source(source)
 342