Distance Vector Routing

Assigned: Wednesday, May 4, 2016

Due: Friday, May 13, 2016 at 10:30pm

Collaboration: Work with your assigned partner for this lab. You may use your classmates and their code as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted.

Groups

  • Bazil and David Ch.
  • Sarah and Jerry
  • Reilly and Alex
  • Uzo and Marcel
  • Otabek and Daniel
  • Aleksandar and Hamza
  • David Ca. and Michael
  • Mari and Albert
  • Moses and Shaun
  • Kumar and Evan
  • Dave and Helen
  • Nick and Fengyuan

Overview

In this lab, you will be writing a distributed set of procedures that implement a distributed asynchronous distance vector routing for the network shown in the figure below.

Network topology and link costs for this lab.

For the basic part of the assignment, you are to write the following routines which will “execute” asynchronously within the emulated environment that we have written for this assignment.

For node 0, you will write the routines:

rtinit0()
This routine will be called once at the beginning of the emulation. rtinit0() has no arguments. It should initialize the distance table in node 0 to reflect the direct costs of 1, 3, and 7 to nodes 1, 2, and 3, respectively. In Figure 1, all links are bi-directional and the costs in both directions are identical. After initializing the distance table, and any other data structures needed by your node 0 routines, it should then send its directly-connected neighbors (in this case, 1, 2 and 3) the cost of it minimum cost paths to all other network nodes. This minimum cost information is sent to neighboring nodes in a routing packet by calling the routine tolayer2(), as described below. The format of the routing packet is also described below.

rtupdate0(struct rtpkt* packet)
This routine will be called when node 0 receives a routing packet that was sent to it by one if its directly connected neighbors. The parameter packet is a pointer to the packet that was received.

The rtupdate0() function is the heart of the distance vector algorithm. The values it receives in a routing packet from some other node i contain i’s current shortest path costs to all other network nodes. rtupdate0() uses these received values to update its own distance table (as specified by the distance vector algorithm). If its own minimum cost to another node changes as a result of the update, node 0 informs its directly connected neighbors of this change in minimum cost by sending them a routing packet. Recall that in the distance vector algorithm, only directly connected nodes will exchange routing packets. Thus nodes 1 and 2 will communicate with each other, but nodes 1 and 3 will not communicate with each other.

The distance table inside each node is the principal data structure used by the distance vector algorithm. We declare the distance table as a 4-by-4 array of ints, where entry [i,j] in the distance table in node 0 is node 0’s currently computed cost to node i via direct neighbor j. If 0 is not directly connected to j, you can ignore this entry. We will use the convention that the integer value 9999 is “infinity”, i.e.,

#define INFINITY 9999

The figure below provides a conceptual view of the relationship of the procedures inside node 0.

Relationship between procedures inside node 0.

Similar routines are defined for nodes 1, 2 and 3. Thus, you will write at least 8 procedures in all: rtinit0(), rtinit1(), rtinit2(), rtinit3(), rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3().

Software Interfaces

The procedures described above are the ones that you will write. We have written the following routines that can be called by your routines:

tolayer2(struct rtpkt pkt2send)
where rtpkt is the following structure, which is already declared for you:

extern struct rtpkt {
  int sourceid; /* id of node sending this pkt, 0, 1, 2, or 3 */
  int destid; /* id of router to which pkt being sent (must be an immediate neighbor) */
  int mincost[4]; /* min cost to node 0 ... 3 */
};

The procedure tolayer2() is defined in the file dvr.c. Note that tolayer2() is passed a structure, not a pointer to a structure.

printdt(int from, struct distance_table* dtptr)
This procedure will pretty print the distance table for node number from. It is passed a pointer to a structure of type distance_table.

The Simulated Network Environment

Your procedures rtinit0(), rtinit1(), rtinit2(), rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() send routing packets (whose format is described above) into the medium. The medium will deliver packets in-order, and without loss to the specified destination. Only directly-connected nodes can communicate. The delay between is sender and receiver is variable (and unknown).

When you compile your procedures and the provided procedures together and run the resulting program, you will be asked to specify only one value regarding the simulated network environment:

Tracing

Setting a tracing value of 1 or 2 will print out useful information about what is going on inside the emulation (e.g., what’s happening to packets and timers). A tracing value of 0 will turn this off. A tracing value greater than 2 will display all sorts of odd messages that are for own debugging the emulator.

A tracing value of 2 may be helpful to you in debugging your code. You should keep in mind that real implementors do not have underlying networks that provide such nice information about what is going to happen to their packets!

Assignment

Basic

You are to write the procedures rtinit0(), rtinit1(), rtinit2(), rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() which together will implement a distributed, asynchronous computation of the distance tables for the topology and costs shown in Figure 1.

You should put your procedures for nodes 0 through 3 in files node0.c, node1.c, node2.c, and node3.c. You are not allowed to declare any global variables that are visible outside of a given C file (e.g., any global variables you define in node0.c may only be accessed inside node0.c). This is to force you to abide by the coding conventions that you would have to adopt if you were really running the procedures in four distinct nodes.

Prototype versions of all files are available on MathLAN:

$ cp -R /home/curtsinger/courses/csc216/dvr your/csc216/directory/

To compile your routines, go to your copy of the dvr directory and run:

$ make

For your sample output, your procedures should print out a message whenever your rtinit0(), rtinit1(), rtinit2(), rtinit3() or rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() procedures are called, giving the time (available via the global float variable clocktime). For rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() you should print the identity of the sender of the routing packet that is being passed to your routine, whether or not the distance table is updated, the contents of the distance table (you can use the pretty-print routines), and a description of any messages sent to neighboring nodes as a result of any distance table updates. Here is an example transcript: trace.txt.

Advanced

In addition to the above, write two procedures, rtlinkhandler0(int linkid, int newcost) and rtlinkhandler1(int linkid, int newcost), which will be called when the cost of the link between 0 and 1 changes. These routines should be defined in the files node0.c and node1.c, respectively. The routines will be passed the name (id) of the neighboring node on the other side of the link whose cost has changed, and the new cost of the link. Note that when a link cost changes, these routines will have to update the distance table and may (or may not) have to send updated routing packets to neighboring nodes.

In order to complete the advanced part of the assignment, you will need to change the value of the constant LINKCHANGES (line 6 in dvr.h) to 1.

FYI, the cost of the link will change from 1 to 20 at time 10000 and then change back to 1 at time 20000. Your routines will be invoked at these times.

For your sample output, in addition to the messages for the “Basic” version of the algorithm, you should print a message with the time when the rtlinkhandler0() and rtlinkhandler1() procedures are called along with a description of any messages sent to neighboring nodes as a result of the distance table updates. Here is an example transcript: trace_linkchanges.txt.

Hints

  • At each node, I recommend you store the provided link costs from that particular node in an array to simplify calculations (via loops) in the init, update, and link handler routines.
  • At each node, I recommend you store (and update) the shortest path to other nodes from that particular node to simplify calcuations and sending distance vectors.
  • Practice good code reuse and decomposition:
    • Two or three methods need to send distance vector updates to neighbors.
    • One or two methods need to check for updates to the shortest path (new minimum cost paths).

Evaluation

Assuming the general guidelines for lab exercises are met, correctly completing the Basic assignment will earn a B, while correctly completing the Advanced assignment will earn an A.

What to turn in

  • A tar.gz archive of your entire code directory
  • A transcript of the compilation of your files
  • A transcript of your running program with a TRACE value of 2

Acknowledgements

This lab was written by Jerod Weinman, who based it heavily on Programming Assignment 6: Implementing an Algorithm by James F. Kurose and Keith W. Ross.

This course is based in part on materials from Jerod Weinman's fall 2014 offering of CSC 364.

This website was built using Jekyll, Twitter Bootstrap, and the Bootswatch Cosmo Theme.