ndn/apps/calculate_routing.py

# -*- 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