routing-helper: fix route computation bug
Route computation for link-state had a bug, neighbor's list
contained the host itself and so the computation was erroneous,
and ultimately crashing.
Change-Id: I461476eef83b73b64ae943f6f08bf576e3719b94
diff --git a/install.sh b/install.sh
index fb92104..0fbb689 100755
--- a/install.sh
+++ b/install.sh
@@ -213,6 +213,7 @@
sudo cp topologies/minindn.ucla.conf "$install_dir"
sudo cp topologies/minindn.testbed.conf "$install_dir"
sudo cp topologies/current-testbed.conf "$install_dir"
+ sudo cp topologies/geo_hyperbolic_test.conf "$install_dir"
sudo python setup.py develop
}
diff --git a/minindn/helpers/ndn_routing_helper.py b/minindn/helpers/ndn_routing_helper.py
index 0fb4b33..94eec0d 100644
--- a/minindn/helpers/ndn_routing_helper.py
+++ b/minindn/helpers/ndn_routing_helper.py
@@ -1,6 +1,6 @@
- # -*- Mode:python; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+# -*- Mode:python; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
#
-# Copyright (C) 2015-2019, The University of Memphis
+# Copyright (C) 2015-2020, The University of Memphis
#
# This file is part of Mini-NDN.
# See AUTHORS.md for a complete list of Mini-NDN authors and contributors.
@@ -27,6 +27,7 @@
routes and their costs from the given Mini-NDN topology
'''
+import sys
import heapq
from math import sin, cos, sinh, cosh, acos, acosh
import json
@@ -124,7 +125,6 @@
"""
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) -\
@@ -146,17 +146,19 @@
self.adjacenctMatrix = defaultdict(dict)
self.nodeDict = defaultdict(dict)
self.routingType = routingType
+ self.isHrConfigValid = True
for host in netObj.hosts:
if 'radius' in host.params['params']:
radius = float(host.params['params']['radius'])
else:
+ self.isHrConfigValid = False
radius = 0.0
- if 'angles' in host.params['params']:
+ if 'angle' in host.params['params']:
angles = [float(x) for x in host.params['params']['angle'].split(',')]
else:
- angles = 0.0
+ self.isHrConfigValid = False
+ angles = [0.0]
self.nodeDict[host.name][radius] = angles
-
for link in netObj.topo.links(withInfo=True):
linkDelay = int(link[2]['delay'].replace("ms", ""))
self.adjacenctMatrix[link[0]][link[1]] = linkDelay
@@ -175,12 +177,14 @@
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 []
+ if self.isHrConfigValid == True:
+ # 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:
+ warn('Hyperbolic coordinates in topology file are either missing or misconfigured.\n')
+ warn('Check that each node has one radius value and one or two angle value(s).\n')
+ return None
for node in resultMatrix:
for destinationNode in resultMatrix[node]:
@@ -213,7 +217,7 @@
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))
+ others = [x for x in nodeNames if x not in [viaNeighbor, node]]
paths[node][viaNeighbor][viaNeighbor] = 0
# Compute distance from neighbors to no-neighbors
for destinationNode in others:
@@ -222,7 +226,6 @@
hyperbolicCost = int(HYPERBOLIC_COST_ADJUSTMENT_FACTOR \
* round(hyperbolicDistance, 6))
paths[node][destinationNode][viaNeighbor] = hyperbolicCost
-
debug("Shortest Distance Matrix: {}".format(json.dumps(paths)))
return paths
@@ -234,7 +237,7 @@
distanceMatrix = self.getNestedDictionary()
nodeNames = self.getNodeNames()
for node in nodeNames:
- others = list(set(nodeNames) - set(node))
+ others = [x for x in nodeNames if x not in [node]]
for destinationNode in others:
cost, path = dijkstra(self.adjacenctMatrix, node, destinationNode)
viaNeighbor = path[1]
@@ -259,7 +262,7 @@
for viaNeighbor in neighbors:
directCost = self.adjacenctMatrix[node][viaNeighbor]
distanceMatrixViaNeighbor[node][viaNeighbor][viaNeighbor] = directCost
- others = list(set(nodeNames) - set(viaNeighbor) - set(node))
+ others = [x for x in nodeNames if x not in [viaNeighbor, node]]
for destinationNode in others:
nodeNeighborCost = self.adjacenctMatrix[node][viaNeighbor]
# path variable is not used for now
@@ -290,6 +293,7 @@
self.routeObject = _CalculateRoutes(self.net, self.routingType)
def globalRoutingHelperHandler(self):
+ info('Creating faces and adding routes to FIB\n')
for host in self.net.hosts:
neighborIPs = self.getNeighbor(host)
self.createFaces(host, neighborIPs)
@@ -320,10 +324,13 @@
"""
self.routes = self.routeObject.getRoutes(nFaces)
- if self.routes:
+ if self.routes is not None:
+ info('Route computation completed\n')
self.globalRoutingHelperHandler()
else:
- warn("Route computation failed\n")
+ warn('Route computation failed\n')
+ self.net.stop()
+ sys.exit(1)
def calculateRoutes(self):
# Calculate shortest path for every node
diff --git a/topologies/geo_hyperbolic_test.conf b/topologies/geo_hyperbolic_test.conf
new file mode 100644
index 0000000..a0857e5
--- /dev/null
+++ b/topologies/geo_hyperbolic_test.conf
@@ -0,0 +1,13 @@
+[nodes]
+kisti: _ radius=10.3702985908827 angle=0.716433223334,0.0545806345001
+uum: _ radius=1.6094379124341003 angle=1.67926190756,1.86479930822
+remap: _ radius=6.530877627725885 angle=0.895062959887,6.12377862701
+ntnu: _ radius=1.791759469228055 angle=0.947897043404,2.43808027724
+tongji: _ radius=1.791759469228055 angle=1.17730242215,1.99086740715
+[links]
+kisti:remap delay=20ms
+uum:tongji delay=15ms
+remap:uum delay=13ms
+ntnu:kisti delay=10ms
+tongji:ntnu delay=10ms
+uum:ntnu delay=20ms
\ No newline at end of file