Description
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 different factors on the convergence times to optimal routes. You will
be provided with multiple files that represent different 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 file consists of a number of rows, each row represents a single edge in the network.
There are three entries per row. The first 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 different
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 file 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.
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 files)
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 file 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 file 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 first 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.
