Project #1 A Simulator for Distance Vector Routing

This project would take a good amount of work and time, so please start early. You would not be able to nish if you start few days before the due date. Late submissions would incur a penalty of 20% per day for up to 2 days, and then they will not be accepted. Leave the last few days for documentation, further testing and formatting the results. Please read the description below carefully, understand the requirements and the expected outcomes. Please remember that it is an act of plagiarism to submit someone else’s work as part of your own. Please email me, if you have questions. This project is to be done individually.

An Overview

In this project, you are asked to simulate Distance Vector routing for a given network. The main goal of this project is to study the impact of di erent factors on the convergence times to optimal routes. You will be provided with multiple les that represent di erent network topologies. Your simulator would need build routing tables and then forward data packets until they reach their destinations based on the routing tables built.

The Network Topology Files

Each network topology le consists of a number of rows, each row represents a single edge in the network. There are three entries per row. The rst entry is the node ID at one end, the second is the node ID at the other end, and the third entry is the cost of the link between the nodes which will be used in computing optimal routes. For example, a row with these values: 2 12 23 means that there is a link between node 2 and node 12 and that link has a cost 23. Here are three topologies to use:

Toplogy1.txt (5 nodes, 7 edges) Toplogy2.txt (10 nodes, 20 edges) Toplogy3.txt (30 nodes, 60 edges)

Initially, every node is only aware of its immediate neighbors (and thus would not have a complete picture of the topology). To build routing tables, nodes will proceed in \Rounds". At the beginning of every round, each node will prepare a DV packet that it would send to its immediate neighbors. DV packets include the source node and the list of nodes-costs pairs for what this node knows about the network. In every round, a pair of nodes that are connected will exchange their DV packets and update their tables.

The above topologies were generated using BRITE. The grader may test/grade your code on di erent topologies than the ones provided above, so make sure nothing is hard-coded (even the number of nodes!). Your simulator should take as a line argument, which topology le to use along with the duration to run your simulation (e.g., how many rounds needs to be simulated).

Distance Vector

Recall that in a distance vector-based routing algorithm, each node would tell its neighbors, what it knows about the whole network. As nodes exchange information with their neighbors in every round, they update their routing tables if better routes are discovered. Each node would maintain a routing table that consists of < destination; cost; nexthop >. The DV packet each node sends is simply the destination and cost pairs (no need to send the next hop).

When a node receives a data packet, it consults its routing table and forwards the packet to the next hop, which would do the same until the packet reaches the destination.


Page 2 of 3
CS4310 (Mina Guirguis ): Project #1


What to Turn in

A short design document stating the overall design decisions made and data structures used. The source code.

The\results document that includes the full routing table for each node (for the above 3 topology les) after convergence.

Please provide a single command line to compile your program and another single command line to test your code and make sure to provide a working example of the command line. You can assume that the topology le will be in the same directory as your simulator.

The TA must be able to compile and run the simulator on the CS Linux Servers. You need to upload a single zipped le to Canvas.

In the Results document, answer the following questions (for each topology):

        1. How many rounds did it take each network to converge?

        2. What is the ID of the last node to converge in each network?

        3. How many DV messages were sent in total until each network converged?

After convergence, have your simulator route the following data packets using the routing tables created, showing the path used from source to destination.

        1. For the  rst topology: node 0 receives a data packet destined to node 3.

        2. For the second topology:node 0 receives a data packet destined to node 7.

        3. For the third topology: node 0 receives a data packet destined to node 23.

































Page 3 of 3