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, *args, **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_grap(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 == LADDER:
 128             total_nodes = node_count/2
 129             graph = networkx.ladder_graph(total_nodes)
 130
 131         elif topo_type == LINEAR:
 132             graph = networkx.path_graph(node_count)
 133
 134         elif topo_type == MESH:
 135             graph = networkx.complete_graph(node_count)
 136
 137         elif topo_type == TREE:
 138             h = math.log(node_count + 1)/math.log(2) - 1
 139             graph = networkx.balanced_tree(2, h)
 140
 141         elif topo_type == 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: NODES[str(nid)],
 159             graph.nodes()))
 160         g.add_edges_from(map(lambda t: (NODES[str(t[0])], NODES[str(t[1])]),
 161             graph.edges()))
 162
 163         return g
 164
 165     def add_node(self, nid):
 166         nid = str(nid)
 167
 168         if nid not in self.graph:
 169             self.graph.add_node(nid)
 170
 171     def add_edge(self, nid1, nid2):
 172         nid1 = str(nid1)
 173         nid2 = str(nid2)
 174
 175         self.add_node(nid1)
 176         self.add_node( nid2)
 177
 178         if nid1 not in self.graph[nid2]:
 179             self.graph.add_edge(nid2, nid1)
 180
 181             # The weight of the edge is the delay of the link
 182             self.graph.edge[nid1][nid2]["weight"] = None
 183             # confidence interval of the mean RTT
 184             self.graph.edge[nid1][nid2]["weight_ci"] = None
 185
 186     def assign_p2p_ips(self, network = "10.0.0.0", prefix = 8, version = 4):
 187         """ Assign IP addresses to each end of each edge of the network graph,
 188         computing all the point to point subnets and addresses in the network
 189         representation.
 190
 191             :param network: Base network address used for subnetting.
 192             :type network: str
 193
 194             :param prefix: Prefix for the base network address used for subnetting.
 195             :type prefixt: int
 196
 197             :param version: IP version (either 4 or 6).
 198             :type version: int
 199
 200         """
 201         if len(networkx.connected_components(self.graph)) > 1:
 202             raise RuntimeError("Disconnected graph!!")
 203
 204         # Assign IP addresses to host
 205         netblock = "%s/%d" % (network, prefix)
 206         if version == 4:
 207             net = ipaddr.IPv4Network(netblock)
 208             new_prefix = 31
 209         elif version == 6:
 210             net = ipaddr.IPv6Network(netblock)
 211             new_prefix = 31
 212         else:
 213             raise RuntimeError, "Invalid IP version %d" % version
 214
 215         sub_itr = net.iter_subnets(new_prefix = new_prefix)
 216
 217         for nid1, nid2 in self.graph.edges():
 218             #### Compute subnets for each link
 219
 220             # get a subnet of base_add with prefix /30
 221             subnet = sub_itr.next()
 222             mask = subnet.netmask.exploded
 223             network = subnet.network.exploded
 224             prefixlen = subnet.prefixlen
 225
 226             # get host addresses in that subnet
 227             i = subnet.iterhosts()
 228             addr1 = i.next()
 229             addr2 = i.next()
 230
 231             ip1 = addr1.exploded
 232             ip2 = addr2.exploded
 233             self.graph.edge[nid1][nid2]["net"] = dict()
 234             self.graph.edge[nid1][nid2]["net"][nid1] = ip1
 235             self.graph.edge[nid1][nid2]["net"][nid2] = ip2
 236             self.graph.edge[nid1][nid2]["net"]["mask"] = mask
 237             self.graph.edge[nid1][nid2]["net"]["network"] = mask
 238             self.graph.edge[nid1][nid2]["net"]["prefix"] = prefixlen
 239
 240     def get_p2p_info(self, nid1, nid2):
 241         net = self.graph.edge[nid1][nid2]["net"]
 242         return ( net[nid1], net[nid2], net["mask"], net["network"],
 243                 net["prefixlen"] )
 244
 245     def set_source(self, nid):
 246         graph.node[nid]["source"] = True
 247
 248     def set_target(self, nid):
 249         graph.node[nid]["target"] = True
 250
 251     def targets(self):
 252         """ Returns the nodes that are targets """
 253         return [nid for nid in self.graph.nodes() \
 254                 if self.graph.node[nid].get("target")]
 255
 256     def sources(self):
 257         """ Returns the nodes that are sources """
 258         return [nid for nid in self.graph.nodes() \
 259                 if self.graph.node[nid].get("sources")]
 260
 261     def select_target_zero(self):
 262         """ Marks the node 0 as target
 263         """
 264         self.set_target("0")
 265
 266     def select_random_leaf_source(self):
 267         """  Marks a random leaf node as source.
 268         """
 269
 270         # The ladder is a special case because is not symmetric.
 271         if self.topo_type == TopologyType.LADDER:
 272             total_nodes = self.order/2
 273             leaf1 = str(total_nodes - 1)
 274             leaf2 = str(nodes - 1)
 275             leaves = [leaf1, leaf2]
 276             source = leaves.pop(random.randint(0, len(leaves) - 1))
 277         else:
 278             # options must not be already sources or targets
 279             options = [ k for k,v in graph.degree().iteritems() \
 280                     if v == 1 and not graph.node[k].get("source") \
 281                         and not graph.node[k].get("target")]
 282
 283             source = options.pop(random.randint(0, len(options) - 1))
 284
 285         self.set_source(source)
 286