Source

cs655 / routing / python / routing / protocols / pathvector.py

# pathvector.py - node which uses the path vector routing protocol
#
# CS655 routing assignment
# Jeffrey Finkelstein
# November 2011
"""Provides the node class for the path vector protocol."""
import copy
import itertools
import logging

from ..datacontainers import Packet
from .bases import INFINITY
from .bases import Node

STAR = None
"""Represents a null head of a path."""

_logger = logging.getLogger(__name__)
"""The logger for this module."""


class Logger(object):
    """Wrapper for the `logging` module's normal logger which prepends the
    simulation time before logging the requested message.

    """

    def __init__(self, scheduler, logger):
        """Stores the scheduler, which maintains the simulation time, and the
        logger to use to log messages.

        """
        self.scheduler = scheduler
        self.logger = logger

    def debug(self, message):
        """Logs `message` with the current simulation time."""
        time = self.scheduler.timefunc()
        self.logger.debug('{:.3f}: {}'.format(time, message))

logger = None
"""This is the instance of the `Logger` class (defined in this module) which
wraps the Python built-in `logging` logger to provide the simulation time.

HACK: this is a global so we can keep existing code without changing calls to
`logger.debug`.

"""


class PathVectorNode(Node):
    """Uses a mixed distance vector/path vector strategy implemented with the
    modified distributed Bellman-Ford algorithm to determine the shortest path
    to other nodes in the graph.

    """

    def __init__(self, *args, **kw):
        """Initializes the routing table and distance matrix for this node."""
        super().__init__(*args, **kw)
        # HACK logger is global to allow wrapping logger.debug
        global logger
        logger = Logger(self.scheduler, _logger)
        # key is destination (j), value is triple (preferred neighbor (P_ij),
        # shortest distance (RDIST_i_ofj), HEAD_i_ofj)
        self.routing_table = dict([(d, (STAR, INFINITY, STAR))
                                   for d in range(self.total_nodes)])
        self.d_i = self.link_costs
        # first dimension is destination, second is "via", entry is pair
        # (distance from i to j via k (D_ij_k), head of that path (h_ij_k))
        self.D_i = [dict((n, (INFINITY, STAR)) for n in self.neighbors())
                    for m in range(self.total_nodes)]
        for k, d_ik in self.d_i.items():
            self.routing_table[k] = (k, d_ik, self.node_id)
        self.routing_table[self.node_id] = (STAR, 0, STAR)
        for n in self.neighbors():
            self.D_i[n][n] = self.d_i[n]

    def from_layer2(self, packet):
        """Updates the distance matrix with the new distances specified in the
        packet, updates the routing table if necessary due to changes in the
        distance matrix, and sends any changes to the neighbors of this node.

        """
        logger.debug('from_layer2(): packet {}'.format(packet))
        i, k = packet.dest, packet.source
        assert self.node_id == i
        # V_ki is a list of triples
        V_ki = packet.mincosts
        self.log_routing_table()
        self.log_distances()
        # copy the new costs from neighbor j into column k
        for (j, D_kj, h_kofj) in (x for x in V_ki if x[0] != i):
            logger.debug('  copying cost from neighbor {} via {}: ({}, {})'.format(j, k, D_kj, h_kofj))
            if j == k:
                h_kofj = self.node_id
            self.D_i[j][k] = (D_kj + self.d_i[k], h_kofj)
        self.log_routing_table()
        self.log_distances()
        self.update_and_send(k)

    def initialize(self, all_nodes):
        """Provides this node with a mapping from node ID integer to `Node`
        instance for all nodes in the graph in which this node lives, and
        sends the initial distance vectors to the neighbors of this node.

        `all_nodes` is a dictionary mapping ID numbers to `Node`
        instances. The length of `all_nodes` must equal `total_nodes` as
        specified in the constructor for this class.

        """
        logger.debug('initialize(): node {}'.format(self.node_id))
        self.nodes = all_nodes.copy()
        mycosts = copy.deepcopy(self.routing_table_to_vector())
        for neighbor in self.neighbors():
            logger.debug('initialize():   sending to neighbor {}'.format(neighbor))
            packet = Packet(self.node_id, neighbor, mycosts)
            self.to_layer2(packet)

    def in_path(self, neighbor, dest):
        h = self.routing_table[dest][2]
        if h == node:
            return False
        if h == neighbor:
            return True
        return self.in_path(neighbor, self.routing_table[h][2])

    def is_minimum_of_row(self, c, b):
        minimum_of_row = min(D_ic_b for D_ic_b, h_ic_b in self.D_i[c].values())
        return minimum_of_row == self.D_i[c][b][0]

    def link_down(self, link_id):
        self.set_column_to_inf(k)
        self.update_and_send(k)

    def link_up(self, link_id, cost):
        i, k = self.node_id, link_id
        d_ik = cost
        V_ki = [(k, d_ik, i)]
        packet = Packet(k, i, V_ki)
        self.from_layer2(packet)
        V_ik = self.routing_table
        packet = Packet(i, k, V_ik)
        self.to_layer2(packet)

    def link_changed(self, link_id, new_cost):
        self.link_down(link_id)
        self.link_up(link_id, new_cost)

    def log_distances(self):
        """Logs the current distance matrix at the `DEBUG` level."""
        logger.debug('  Distance table for node {}:'.format(self.node_id))
        for dest, row in enumerate(self.D_i):
            logger.debug('  {}: {}'.format(dest, row))

    def log_routing_table(self):
        """Logs the current routing table at the `DEBUG` level."""
        logger.debug('  Routing table for node {}:'.format(self.node_id))
        for key, row in self.routing_table.items():
            logger.debug('  {}: {}'.format(key, row))

    def minimum_distance_neighbor_in_row(self, j):
        logger.debug("minimum distance neighbors in row: ")
        result = min(self.D_i[j].items(), key=lambda e: e[1][0])[0]
        logger.debug('  {}'.format(result))
        return result

    def routing_table_must_change(self, k):
        #if there exist (j,b) such that D_ij_b < D_ij or k==P_ij:
        for (j, b) in itertools.product(range(self.total_nodes),
                                        range(len(self.neighbors()))):
            if (self.D_i[j][b][0] < self.routing_table[j][1]
                or k == self.routing_table[j][0]):
                return True
        return False

    def routing_table_to_vector(self):
        return [(j, RDIST_i_ofj, HEAD_i_ofj) for j, (P_ij, RDIST_i_ofj,
                                                     HEAD_i_ofj)
                in self.routing_table.items()]

    def rt_update(self):
        dest_determined = dict([(d, False) for d in range(self.total_nodes)])
        distance_determined = dict([(d, dict([(n, False)
                                              for n in self.neighbors()]))
                                    for d in range(self.total_nodes)])
        # TODO should this be `for j in filter(lambda x: x, dest_determined)`?
        for j in dest_determined:
            logger.debug("rt_update(): j {}".format(j))
            if dest_determined[j]:
                continue
            if not any(distance_determined[j]):
                dest_determined[j] = False
                continue
            TV = []
            b = self.minimum_distance_neighbor_in_row(j)
            self.log_distances()
            self.log_routing_table()
            logger.debug('rt_update():   b {}'.format(b))
            #c = h_ij_b
            c = self.D_i[j][b][1]
            TV.append(c)
            logger.debug('rt_update():   c {}'.format(c))
            logger.debug('rt_update():   TV {}'.format(TV))
            while (self.is_minimum_of_row(c, b)
                   and self.D_i[c][b][1] != self.node_id
                   and not dest_determined[self.D_i[c][b][1]]):
                self.log_routing_table()
                self.log_distances()
                logger.debug('c {}'.format(c))
                c = self.D_i[c][b][1]
                TV.append(c)
            if (not dest_determined[self.D_i[c][b][1]]
                or not self.is_minimum_of_row(c, b)):
                for n in TV:
                    dest_determined[n] = False
            else:
                for n in TV:
                    dest_determined[n] = True
                    RDIST_i_j, HEAD_i_j = self.D_i[j][b]
                    P_ij = b
                    self.routing_table[j] = (P_ij, RDIST_i_j, HEAD_i_j)
        # copy routing table to V_i done in from_layer2

    def set_column_to_inf(self, k):
        for v in range(self.total_nodes):
            self.D_i[v][k] = (INFINITY, STAR)

    def update_and_send(self, k):
        logger.debug('update_and_send()')
        V_i = None
        V_ib = dict([(b, []) for b in self.neighbors()])
        if self.routing_table_must_change(k):
            self.rt_update()
            V_i = self.routing_table()
        else:
            V_i = None
        if V_i is not None:
            for b in self.neighbors():
                for t in V_i:
                    j, rdist_iofj, head_iofj = t
                    if self.in_path(b, j):
                        V_ib[b].append((j, INFINITY, STAR))
                    else:
                        V_ib[b].append(t)
                send_pkt = Packet(self.node_id, b, V_ib[b])
                self.to_layer2(send_pkt)