ndn/apps: add global routing helper
Change-Id: Id2bfb035424e2214d3dad1d00da95a0715c716c9
diff --git a/ndn/apps/calculate_routing.py b/ndn/apps/calculate_routing.py
new file mode 100644
index 0000000..ce1966f
--- /dev/null
+++ b/ndn/apps/calculate_routing.py
@@ -0,0 +1,264 @@
+# -*- Mode:python; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+#!/usr/bin/env python
+#
+# Copyright (C) 2015-2019, The University of Memphis
+#
+# This file is part of Mini-NDN.
+# See AUTHORS.md for a complete list of Mini-NDN authors and contributors.
+#
+# Mini-NDN is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# Mini-NDN is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with Mini-NDN, e.g., in COPYING.md file.
+# If not, see <http://www.gnu.org/licenses/>.
+
+'''
+This module will compute link state, hyperbolic and geohyperbolic
+routes and their costs from the given Mini-NDN topology
+'''
+
+import heapq
+import math
+from collections import defaultdict
+from math import sin, cos, sinh, cosh, acos, acosh
+import json
+import operator
+
+from mininet.log import info, debug, error
+
+UNKNOWN_DISTANCE = -1
+HYPERBOLIC_COST_ADJUSTMENT_FACTOR = 1000
+
+class CalculateRoutes():
+ """
+ Creates a route calculation object, which is used to compute routes from a node to
+ every other nodes in a given topology topology using hyperbolic or geohyperbolic
+ routing algorithm
+
+ :param NetObject netObj: Mininet net object
+ :param RoutingType routingType: (optional) Routing algorithm, link-state or hr etc
+ """
+ def __init__(self, netObj, routingType):
+ self.adjacenctMatrix = defaultdict(dict)
+ self.nodeDict = defaultdict(dict)
+ self.routingType = routingType
+ for host in netObj.hosts:
+ radius = float(host.params['params']['radius'])
+ angles = [float(x) for x in host.params['params']['angle'].split(',')]
+ self.nodeDict[host.name][radius] = angles
+
+ for link in netObj.topo.links_conf:
+ linkDelay = int(link.linkDict['delay'].replace("ms", ""))
+ self.adjacenctMatrix[link.h1][link.h2] = linkDelay
+ self.adjacenctMatrix[link.h2][link.h1] = linkDelay
+
+ def getNestedDictionary(self):
+ return defaultdict(self.getNestedDictionary)
+
+ def getRoutes(self, nFaces):
+ resultMatrix = self.getNestedDictionary()
+ routes = defaultdict(list)
+
+ if self.routingType == "link-state":
+ if nFaces == 1:
+ resultMatrix = self.computeDijkastra() # only best routes.
+ else:
+ resultMatrix = self.computeDijkastraAll() # all possible routes
+ elif self.routingType == "hr":
+ # Note: For hyperbolic, only way to find the best routes is by computing all possible
+ # routes and getting the best one.
+ resultMatrix = self.computeHyperbolic()
+ else:
+ info("Routing type not supported\n")
+ return []
+
+ for node in resultMatrix:
+ for destinationNode in resultMatrix[node]:
+ # Sort node - destination via neighbor based on their cost
+ tempDict = resultMatrix[node][destinationNode]
+ shortedTempDict = sorted(tempDict.items(), key=operator.itemgetter(1))
+ # nFaces option gets n-best faces based on shortest distance, default is all
+ if nFaces == 0:
+ for item in shortedTempDict:
+ viaNeighbor = item[0]
+ cost = item[1]
+ routes[node].append([destinationNode, str(cost), viaNeighbor])
+ else:
+ for index, item in enumerate(shortedTempDict):
+ if index >= nFaces:
+ break
+ viaNeighbor = item[0]
+ cost = item[1]
+ routes[node].append([destinationNode, str(cost), viaNeighbor])
+
+ debug("-routes----", routes)
+ return routes
+
+ def getNodeNames(self):
+ return [k for k in self.nodeDict]
+
+ def computeHyperbolic(self):
+ paths = self.getNestedDictionary()
+ nodeNames = self.getNodeNames()
+ for node in self.nodeDict:
+ neighbors = [k for k in self.adjacenctMatrix[node]]
+ for viaNeighbor in neighbors:
+ others = list(set(nodeNames) - set(viaNeighbor) - set(node))
+ paths[node][viaNeighbor][viaNeighbor] = 0
+ # Compute distance from neighbors to no-neighbors
+ for destinationNode in others:
+ hyperbolicDistance = getHyperbolicDistance(self.nodeDict[viaNeighbor],
+ self.nodeDict[destinationNode])
+ hyperbolicCost = int(HYPERBOLIC_COST_ADJUSTMENT_FACTOR \
+ * round(hyperbolicDistance, 6))
+ paths[node][destinationNode][viaNeighbor] = hyperbolicCost
+
+ debug("Shortest Distance Matrix: {}".format(json.dumps(paths)))
+ return paths
+
+ def computeDijkastra(self):
+ """
+ Dijkstra computation: Compute all the shortest paths from nodes to the destinations.
+ And fills the distance matrix with the corresponding source to destination cost
+ """
+ distanceMatrix = self.getNestedDictionary()
+ nodeNames = self.getNodeNames()
+ for node in nodeNames:
+ others = list(set(nodeNames) - set(node))
+ for destinationNode in others:
+ cost, path = dijkstra(self.adjacenctMatrix, node, destinationNode)
+ viaNeighbor = path[1]
+ distanceMatrix[node][destinationNode][viaNeighbor] = cost
+
+ debug("Shortest Distance Matrix: {}".format(json.dumps(distanceMatrix)))
+ return distanceMatrix
+
+ def computeDijkastraAll(self):
+ """
+ Multi-path Dijkastra computation: Compute all the shortest paths from nodes to the
+ destinations via all of its neighbors individually. And fills the distanceMatrixViaNeighbor
+ with a corresponding source to its destination cost
+
+ Important: distanceMatrixViaNeighbor represents the shortest distance from a source to a
+ destination via specific neighbors
+ """
+ distanceMatrixViaNeighbor = self.getNestedDictionary()
+ nodeNames = self.getNodeNames()
+ for node in nodeNames:
+ neighbors = [k for k in self.adjacenctMatrix[node]]
+ for viaNeighbor in neighbors:
+ directCost = self.adjacenctMatrix[node][viaNeighbor]
+ distanceMatrixViaNeighbor[node][viaNeighbor][viaNeighbor] = directCost
+ others = list(set(nodeNames) - set(viaNeighbor) - set(node))
+ for destinationNode in others:
+ nodeNeighborCost = self.adjacenctMatrix[node][viaNeighbor]
+ # path variable is not used for now
+ cost, path = dijkstra(self.adjacenctMatrix, viaNeighbor, destinationNode, node)
+ if cost != 0 and path != None:
+ totalCost = cost + nodeNeighborCost
+ distanceMatrixViaNeighbor[node][destinationNode][viaNeighbor] = totalCost
+
+ debug("Shortest Distance Matrix: {}".format(json.dumps(distanceMatrixViaNeighbor)))
+ return distanceMatrixViaNeighbor
+
+def dijkstra(graph, start, end, ignoredNode = None):
+ """
+ Compute shortest path and cost from a given source to a destination
+ using Dijkstra algorithm
+
+ :param Graph graph: given network topology/graph
+ :param Start start: source node in a given network graph/topology
+ :end End end: destination node in a given network graph/topology
+ :param Node ignoredNode: node to ignore computing shortest path from
+ """
+ queue = [(0, start, [])]
+ seen = set()
+ while True:
+ (cost, v, path) = heapq.heappop(queue)
+ if v not in seen:
+ path = path + [v]
+ seen.add(v)
+ if v == end:
+ debug("Distance from {} to {} is {}".format(start, end, cost))
+ return cost, path
+ for (_next, c) in graph[v].iteritems():
+ if _next != ignoredNode: # Ignore path going via ignoreNode
+ heapq.heappush(queue, (cost + c, _next, path))
+
+ if not queue: # return if no path exist from source - destination except via ignoreNode
+ debug("Distance from {} to {} is {}".format(start, end, cost))
+ return cost, None
+
+def calculateAngularDistance(angleVectorI, angleVectorJ):
+ """
+ For hyperbolic/geohyperbolic routing algorithm, this function computes angular distance between
+ two nodes. A node can have two or more than two angular coordinates.
+
+ :param AngleVectorI angleVectorI: list of angular coordinate of a give node I
+ :param AngleVectorJ angleVectorJ: list of angular coordinate of a give node J
+
+ ref: https://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates
+
+ """
+ innerProduct = 0.0
+ if len(angleVectorI) != len(angleVectorJ):
+ error("Angle vector sizes do not match")
+ return UNKNOWN_DISTANCE
+
+ # Calculate x0 of the vectors
+ x0i = cos(angleVectorI[0])
+ x0j = cos(angleVectorJ[0])
+
+ # Calculate xn of the vectors
+ xni = sin(angleVectorI[len(angleVectorI) - 1])
+ xnj = sin(angleVectorJ[len(angleVectorJ) - 1])
+
+ # Do the aggregation of the (n-1) coordinates (if there is more than one angle)
+ # i.e contraction of all (n-1)-dimensional angular coordinates to one variable
+ for k in range(0, len(angleVectorI)-1):
+ xni *= sin(angleVectorI[k])
+ xnj *= sin(angleVectorJ[k])
+
+ innerProduct += (x0i * x0j) + (xni * xnj)
+
+ if (len(angleVectorI) > 1):
+ for m in range(1, len(angleVectorI)):
+ # Calculate euclidean coordinates given the angles and assuming R_sphere = 1
+ xmi = cos(angleVectorI[m])
+ xmj = cos(angleVectorJ[m])
+ for l in range (0, m):
+ xmi *= sin(angleVectorI[l])
+ xmj *= sin(angleVectorJ[l])
+
+ innerProduct += xmi * xmj
+
+ # ArcCos of the inner product gives the angular distance
+ # between two points on a d-dimensional sphere
+ angularDist = acos(innerProduct)
+ debug("Angular distance from {} to {} is {}".format(angleVectorI, angleVectorJ, angularDist))
+ return angularDist
+
+def getHyperbolicDistance(sourceNode, destNode):
+ """
+ Return hyperbolic or geohyperbolic distance between two nodes. The distance is computed
+ on the basis of following algorithm/mathematics
+ ref: https://en.wikipedia.org/wiki/Hyperbolic_geometry
+ """
+ r1 = [key for key in sourceNode][0]
+ r2 = [key for key in destNode][0]
+
+ zeta = 1.0
+ dtheta = calculateAngularDistance(sourceNode[r1], destNode[r2])
+ hyperbolicDistance = (1./zeta) * acosh(cosh(zeta * r1) * cosh(zeta * r2) -\
+ sinh(zeta * r1) * sinh(zeta * r2) * cos(dtheta))
+
+ debug("Distance from {} to {} is {}".format(sourceNode, destNode, hyperbolicDistance))
+ return hyperbolicDistance
\ No newline at end of file
diff --git a/ndn/apps/ndn_global_routing_helper.py b/ndn/apps/ndn_global_routing_helper.py
new file mode 100644
index 0000000..b05d697
--- /dev/null
+++ b/ndn/apps/ndn_global_routing_helper.py
@@ -0,0 +1,127 @@
+ # -*- Mode:python; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+#
+# Copyright (C) 2015-2019, The University of Memphis
+#
+# This file is part of Mini-NDN.
+# See AUTHORS.md for a complete list of Mini-NDN authors and contributors.
+#
+# Mini-NDN is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# Mini-NDN is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with Mini-NDN, e.g., in COPYING.md file.
+# If not, see <http://www.gnu.org/licenses/>.
+
+# IMPORTANT! This feature is in highly experimental phase and may go several changes
+# in future
+
+from mininet.log import info
+from ndn.apps.nfdc import Nfdc as nfdc
+from collections import defaultdict
+from ndn.apps.calculate_routing import CalculateRoutes
+from mininet.log import warn
+
+class GlobalRoutingHelper():
+ """
+ This module is a helper class which helps to create face and register routes
+ to NFD from a given node to all of its neighbors.
+
+ :param NetObject netObject: Mininet net object
+ :param FaceType faceType: UDP, Ethernet etc.
+ :param Routing routingType: (optional) Routing algorithm, link-state or hr etc
+
+ """
+ def __init__(self, netObject, faceType=nfdc.PROTOCOL_UDP, routingType="link-state"):
+ self.net = netObject
+ self.faceType = faceType
+ self.routingType = routingType
+ self.routes = []
+ self.namePrefixes = {host_name.name: [] for host_name in self.net.hosts}
+ self.routeObject = CalculateRoutes(self.net, self.routingType)
+
+ def globalRoutingHelperHandler(self):
+ for host in self.net.hosts:
+ neighborIPs = self.getNeighbor(host)
+ self.createFaces(host, neighborIPs)
+ self.routeAdd(host, neighborIPs)
+
+ info('Processed all the routes to NFD\n')
+
+ def addOrigin(self, nodes, prefix):
+ """
+ Add prefix/s as origin on node/s
+
+ :param Prefix prefix: Prefix that is originated by node/s (as producer) for this prefix
+ :param Nodes nodes: List of nodes from net object
+ """
+ for node in nodes:
+ self.namePrefixes[node.name] = prefix
+
+ def calculateNPossibleRoutes(self, nFaces=0):
+ """
+ By default, calculates all possible routes i.e. routes via all the faces of a node.
+ pass nFaces if want to compute routes via n number of faces. e.g. 2. For larger topology
+ the computation might take huge amount of time.
+
+ :param int nFaces: (optional) number of faces to consider while computing routes. Default
+ i.e. nFaces = 0 will compute all possible routes
+
+ """
+ self.routes = self.routeObject.getRoutes(nFaces)
+ if self.routes:
+ self.globalRoutingHelperHandler()
+ else:
+ warn("Route computation failed\n")
+
+ def calculateRoutes(self):
+ # Calculate shortest path for every node
+ calculateNPossibleRoutes(self, nFaces=1)
+
+ def createFaces(self, node, neighborIPs):
+ for ip in neighborIPs.values():
+ nfdc.createFace(node, ip, self.faceType)
+
+ def routeAdd(self, node, neighborIPs):
+ """
+ Add route from a node to its neighbors for each prefix/s advertised by destination node
+
+ :param Node node: source node (Mininet net.host)
+ :param IP neighborIPs: IP addresses of neighbors
+ """
+ neighbors = self.routes[node.name]
+ for route in neighbors:
+ destination = route[0]
+ cost = int(route[1])
+ nextHop = route[2]
+ defaultPrefix = "/ndn/{}-site/{}".format(destination, destination)
+ prefixes = [defaultPrefix] + self.namePrefixes[destination]
+ for prefix in prefixes:
+ # Register routes to all the available destination name prefix/s
+ nfdc.registerRoute(node, prefix, neighborIPs[nextHop], \
+ nfdc.PROTOCOL_UDP, cost=cost)
+ @staticmethod
+ def getNeighbor(node):
+ # Nodes to IP mapping
+ neighborIPs = defaultdict()
+ for intf in node.intfList():
+ link = intf.link
+ if link:
+ node1, node2 = link.intf1.node, link.intf2.node
+
+ if node1 == node:
+ other = node2
+ ip = other.IP(str(link.intf2))
+ else:
+ other = node1
+ ip = other.IP(str(link.intf1))
+
+ # Used later to create faces
+ neighborIPs[other.name] = ip
+ return neighborIPs
\ No newline at end of file
diff --git a/ndn/apps/nfdc.py b/ndn/apps/nfdc.py
index e5ed6cc..e772a42 100644
--- a/ndn/apps/nfdc.py
+++ b/ndn/apps/nfdc.py
@@ -22,7 +22,9 @@
# If not, see <http://www.gnu.org/licenses/>.
import time
-from mininet.log import setLogLevel, output, info, debug
+from mininet.log import debug
+
+SLEEP_TIME = 0.2
class Nfdc:
STRATEGY_ASF = "asf"
@@ -48,13 +50,13 @@
)
debug(node.cmd(cmd))
- time.sleep(0.5)
+ time.sleep(SLEEP_TIME)
@staticmethod
def unregisterRoute(node, namePrefix, remoteNodeAddress, origin=255):
cmd = "nfdc route remove {} {} {}".format(namePrefix, remoteNodeAddress, origin)
debug(node.cmd(cmd))
- time.sleep(0.5)
+ time.sleep(SLEEP_TIME)
@staticmethod
def createFace(node, remoteNodeAddress, protocol="udp", isPermanent=False):
@@ -64,20 +66,20 @@
"permanent" if isPermanent else "persistent"
))
debug(node.cmd(cmd))
- time.sleep(0.5)
+ time.sleep(SLEEP_TIME)
@staticmethod
def destroyFace(node, remoteNodeAddress, protocol="udp"):
debug(node.cmd("nfdc face destroy {}://{}".format(protocol, remoteNodeAddress)))
- time.sleep(0.5)
+ time.sleep(SLEEP_TIME)
@staticmethod
def setStrategy(node, namePrefix, strategy):
cmd = "nfdc strategy set {} ndn:/localhost/nfd/strategy/{}".format(namePrefix, strategy)
debug(node.cmd(cmd))
- time.sleep(0.5)
+ time.sleep(SLEEP_TIME)
@staticmethod
def unsetStrategy(node, namePrefix):
debug(node.cmd("nfdc strategy unset {}".format(namePrefix)))
- time.sleep(0.5)
\ No newline at end of file
+ time.sleep(SLEEP_TIME)
\ No newline at end of file
diff --git a/ndn/experiments/static_routing_experiment.py b/ndn/experiments/static_routing_experiment.py
new file mode 100644
index 0000000..e40fbf9
--- /dev/null
+++ b/ndn/experiments/static_routing_experiment.py
@@ -0,0 +1,73 @@
+# -*- Mode:python; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+#
+# Copyright (C) 2015-2019, The University of Memphis,
+# Arizona Board of Regents,
+# Regents of the University of California.
+#
+# This file is part of Mini-NDN.
+# See AUTHORS.md for a complete list of Mini-NDN authors and contributors.
+#
+# Mini-NDN is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# Mini-NDN is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with Mini-NDN, e.g., in COPYING.md file.
+# If not, see <http://www.gnu.org/licenses/>.
+
+from ndn.experiments.experiment import Experiment
+from ndn.apps.ndn_global_routing_helper import GlobalRoutingHelper
+
+from mininet.log import info
+
+class RoutingHelperExp(Experiment):
+
+ def __init__(self, args):
+ Experiment.__init__(self, args)
+
+ def start(self):
+ """
+ Compute and add routes to NFD
+ """
+ info('Adding static routes to NFD\n')
+ grh = GlobalRoutingHelper(self.net, self.options.faceType, self.options.routingType)
+ # For all host, pass self.net.hosts or a list, [self.net['a'], ..] or [self.net.hosts[0],.]
+ grh.addOrigin([self.net['a']], ["/abc"])
+ grh.calculateNPossibleRoutes()
+
+ '''
+ Experiment run with default topology, test cases won't work with other topologies
+ # With calculateNPossibleRoutes,
+ 10 # routing = hr, N = All, from A, 3 routes needs to added to NFD.
+ A +++++++ B # A - B -- cost 10
+ + + # A - C -- cost 10
+ 10 + + 10 # A - D -- cost 20
+ + + # Same goes for B being a source.
+ C D #
+
+ prefix "/abc" is advertise from node A, it should be reachable from all other nodes.
+
+ '''
+ if self.options.routingType == "link-state":
+ # This test only for link-state. Similar test can be done for hyperbolic routing.
+ routesFromA = self.net['a'].cmd("nfdc route | grep -v '/localhost/nfd'")
+ if '/ndn/b-site/b' not in routesFromA or \
+ '/ndn/c-site/c' not in routesFromA or \
+ '/ndn/d-site/d' not in routesFromA:
+ info("Route addition failed\n")
+ exit(-1)
+
+ routesToPrefix = self.net['b'].cmd("nfdc fib | grep '/abc'")
+ if '/abc' not in routesToPrefix:
+ info("Missing route to advertised prefix, Route addition failed\n")
+ exit(-1)
+
+ info('Route addition to NFD completed\n')
+
+Experiment.register("centralize-routing", RoutingHelperExp)
\ No newline at end of file