Computer Network 5 | Distance Vector Implementation

1. Project Documentation

The current project is similar to the last one we ran.

run_topo.py

The simple driver that triggers the simulation and write the logs.

  • open_log: function defined in helpers package used to load a file for logging purpose

  • Topology: define a class of Topology which contains a collection of Nodes

  • topo.run_topo(): triggers the simulation

  • finish_log: function defined in helpers to end the logging

SimpleTopo.txt, SimpleNegativeCycleTopo.txt, BadTopo.txt, SingleLoopTopo.txt, ComplexTopo.txt

The topology files containing the map information. Note that BadTopo.txt is a topology that defined with node A link to an nonexistent node z. It should give an error message.

Neighbor

A simple class defined in Node.py with a neighbor node and a path cost.

  • name: neighbor node name

  • weight: the path cost

Node

Node is a class defined in Node.py used to store the node information.

  • name: node/router name

  • incoming_links: list of Neighbor objects of incoming node name and cost

  • outgoing_links: list of Neighbor objects of outgoing node name and cost

  • neighbor_names: list of incoming link node names

  • topology: a backlink to the Topology object and it should not be used in the implementation

  • messages: list of messages defined by user

  • A.send_msg(msg, B): send the message msg to the node B from A

  • B.queue_msg(msg): called when other nodes sends message msg to B. It contains a simple attend function that will add the message to a list.

Note that DistanceVector class is based on this class.

Topology

A class defined by Topology.py used to store the topology map.

  • topodict: a dictionary with each node as the field mapping to its incoming_links and outgoing_links. It contains DistanceVector objects.

  • nodes: a list version of topodict

helpers.py

A helper package that contains several useful functions.

  • open_log(filename): function called in run_topo.py to open a log file filename. Variables logfile and current_logs are set to zeros. It also initialize the current_logs as an empty dictionary.

  • finish_log(): close the global logfile variable

  • add_entry(switch, logstring): add switch: logstring entry to current_logs

  • finish_round(): This is the function called in Topology.py and it is used to write all the entries in the current_logs to the logfile with a alphabet order of field names. It will seperate each round with string "-----\n" and clear the current_logs

2. Assistant File

Makefile

This file can be used to simplify the testing process.

#Makefile

clean:
	rm -rf ./*.log

run: clean
	./run.sh SimpleTopo 2>/dev/null | grep -i 'invalid\|complete'
	./run.sh SimpleNegativeCycleTopo 2>/dev/null | grep -i 'invalid\|complete'
	./run.sh BadTopo 2>/dev/null | grep -i 'invalid\|complete'
	./run.sh SingleLoopTopo 2>/dev/null | grep -i 'invalid\|complete'
	./run.sh ComplexTopo 2>/dev/null | grep -i 'invalid\|complete'
	rm -rf __pycache__

3. Message Class

We should define a Message class or other data types but it should have the following information.

  • name: source node to forward from

  • distVector: the distance vector of the source node

4. DistanceVector Class

DistanceVector is a given class based on class Node and it should add a mapping variable called distVector which keeps track of the distance vector information. it should be initialized with itself as the field and 0 cost as a value.

5. send_initial_messages Function

send_initial_messages is relatively simple. It is used to send the initial message to all the incoming links (say, neighboring routers) at the beginning. Node.send_msg(Message, str) function should be called and the implementation of this message queue is a FIFO data structure.

Note that when passing the distVector in Message, make sure it is copyed with its current value so a future change won’t effect its value.

6. log_distances Function

log_distances is used to output the current distVector in a easy-reading way. For example, it should have the pattern like A:A0,B1,C2 based on {A: 0, B: 1, C: 2} and its implementation should be very easy.

7. process_BF Function

process_BF is actually a impletation of Bellman-Ford algorithm and it must accomplish the two tasks,

  1. Process queued messages

  2. Send neighbors sendMessage distance

The second task is like send_initial_messages with the new message so let’s consider the first task. This is a pseudocode for implementing this task,

Loop through all messages:
    Loop through all nodes in message.distVector:
    
        Skip current node
        
        Calculate the cost from x -> s
        - Cost(x, v)
        - Dv(s)
        - dist* = Cost(x, v) + Dv(s)
        
        1 For new nodes in distVector
        1-1 if node is a neighbor
            update with Cost(x, s)
        1-2 if node is not a neighbor
            update with dist*
        
        2 For existing nodes in distVector
        2-1 if Cost(x, v) or Dv(s) is smaller than -99, then dist* will be -99 no matter the other value
        2-2 if Cost(x, v) + Dv(s) < -99, then dist* will be -99
        2-3 if Cost(x, v) + Dv(s) > -99 but smaller than Dv(s), should also update