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