Project 4 - Implement Distance Vector based Routing Algorithm (due 11:59pm 11/21/06. Extended to 11:59pm 12/01/06)

Overview

This project intends to give you a hand-on experience on how routing tables are generated and updated using distance vector based routing algorithms. You are given the following network topology of four nodes and the associated cost of each link.

Project Description

Network: Assume all links in the network are bi-directional and the costs in both directions are identical. The network topology information should be saved in a configuration file network.conf in the format of a 4x4 matrix. The cost between nodes without direct connection is set to 999.
Simulation Environment: Instead of running the routing algorithm on four different computers, the four nodes are simulated using four processes running on the same computer. Each process creates a socket to listen to incoming packets (server) and another socket to send out packets (client). The nodes are identified by the port number to which the server-side socket is binded. You can define four constants to represent the nodes:
Message Exchange: You need to write four programs: node0.c, node1.c, node2.c, node3.c. They need to run at the same time as four processes (well, strictly speaking, they are started sequentially). The four processes should have similar flow. A typical flow of node0 is described as follows:
- Read in the configuration file (the 4x4 matrix) and derive its neighbors based on the link cost.
- Send message to let neighbors know "I'm here.". The information of alive neighbors are saved in a binary array (linkstatus) where 0 means no direct connection and 1 means with direct connection. After node0 derives its neighbors from the configuration matrix, it sends HELLO message to its neighbors to inform its existence. The format of the HELLO message is as follows:
  
  HELLO NODE0
  where NODE0 is the port number used to identify node0. Upon receiving the HELLO message from other nodes, node0 keeps this information in a table (Suggest to use an array of three elements to save the connection information to its neighbors). Note that since the four nodes are not brought up at EXACTLY the same time, there might be a situation that even though node0 and node1 are supposed to be directly connected, since node1 comes up after node0, the HELLO message sent to node1 by node0 is missed by node1. Therefore, the HELLO message should be periodically sent out to inform your neighbor of the link situation.
- Initialize the distance table and send it to its neighbors. The distance table is sent through a RTPKT message. The format is defined as follows:
  
  RTPKT source dest minimum-cost
  
  Note that the distance table is sent row by row.
- Upon receiving distance table from its neighbors, update the distance table. If the minimum cost has changed, it sends RTPKT message to neighbors.
Summary of Data Structure and Interface
- network: a two-dimensional integer array which stores the link cost as a 4x4 matrix.
- neighbor: a one-dimensional integer array (only stores binary information) which stores the status of its neighbors. The array should be maintained by a pointer and declared dynamically since different nodes have different number of neighbors.
- dv: a two-dimensional integer array which stores the distance table as a 4x4 matrix.
- HELLO: a struct that specifies the HELLO message.
- RTPKT: a struct that specifies the RTPKT message.
Bonus (30 pts)

Deliverables and Grading Policy

Basic Assignment (100 pts.): Implement DV algorithm and exchange the routing table between neighbors until the routing table converges at each node. You need to implement all the messages specified above.
- (40 pts.) Basic understanding of the problem and the DV algorithm. Report is well organized including
  - (1) title page
  - (3) abstract (<=300 words)
  - (6) introduction (background related to this project. For example, you should introduce routing and especially DV routing, socket programming, connection-oriented vs. connectionless service, etc.)
  - (20) technical approach (how you design the code, flow of the program, data structures used, e.g., how you represent configuration file, DV table, how you exchange HELO, why need to exchange HELO, how you exchange DV table, how you use the DV to update your current table, etc.),
  - (5) experimental result (outputs from the code)
  - (3) discussion (what's done, what needs to be done, problems in current implementation, lessons learned, etc.)
  - (2) Appendix (code printout using "enscript") (the points are for the programming style. e.g., good comments, indenting, etc.)
- (60 pts.) Coding
  - (10) Read configuration file, derive neighbor, and use HELLO message to inform the existence.
  - (25) Correctness of socket programming, usage of select and fork
  - (25) Correctness of the final distance table as well as the intermediate table
- Bonus (30 pts.):
  - (5) Create a scenario such that the link between nodes 2 and 3 is done after running the code for 3 minutes. Suggest to look into "signal"
  - (10) Instead of sending the HELO package only at the initial setup stage, you need to periodically send HELO message (e.g., once every 30 sec.). This way, a broken link will be detected if no HELO message has been received in the past 30 seconds.
  - (15) The change of topology is propagated to neighbors and the DV table is changed to another stable state.