Project 4 (P4): Distance Vector Routing (DV)

The purpose of this project is to learn how distributed dynamic routing protocols like distance vector
accomplish routing in practice. In this assignment, you will be asked to build a distance vector routing
protocol that implements the distributed Bellman-Ford algorithm. 1 Design
Data Each router needs to maintain three different data:
• All link cost information to all active neighbors.
• Its own distance vector. It shall display as follows:
AB 71B
A C 10 2 B
There are two entries in this distance vector. For each entry, the five columns are source router
ID, destination router ID, distance, number of hops, the router ID for the next router in routing,
respectively.
• Its neighboring routers’ distance vectors.
Events We will use the running processes to simulate routers. Processes can be run on different hosts.
Each router is assigned with a unique router ID (English letter). Two processes communicate with
another process through its UDP socket:
(1) Upon receiving any distance vector entries from any neighboring router or detecting a new neighbor
or the link cost change to a neighbor, the router will use the Bellman-Ford Equation to update its
distance vector; (2) Then for any change in its distance vector, the router will broadcast the changed distance vector
entries to its neighboring routers through a UDP socket and print out the changed entries to the
console.
UDP sockets in all routers should alway be listening (for potential messages from some neighbors).
1
Commands Here is what are expected with the multiple running routers. We use the same program
for all routers. Name it as dvrouter. For example with a Java program, run Router A in the shell as
prompt java dvrouter A 1000
where 1000 is the assigned UDP port number. Once a router A starts, it shall display as shown in the
following example:
Router A (localhost, 1000) is active. Waiting for input and output ...
where (localhost, 1000) is the pair of the hostname and the port number.
The following input commands will be supported in the console for a router (e.g., router A):
add It adds a new link to the router. For example
add B 2000 1
It will add the link between A and B (with hostname “localhost” and port number 2000) with a link
cost 1 to Router A. If the router B is alive, a message will be sent to B and it will add the link between
B and A with a link cost 1 to Router B. On Router A, it will display “The link A-B is set!” message; on
Router B, it will display “The link B-A is set!” message. Keep in mind the link cost is bidirectionally
symmetric.
change It changes an existing link to the router. For example
change B 7
It will change the link between A and B with a link cost 7 to Router A. If the router B is alive, a message
will be sent to B and it will change the link cost between B and A with a link cost 5 in Router B. On
Router A, it will display “The cost of link A-B is changed!” message; on Router B, it will display “The
cost of link B-A is changed!” message. Keep in mind the link cost is bidirectionally symmetric.
display It display the distance vector of the router. Input
display
then we have the output as
The distance vector for Router A is:
AB71B
AC63B
2 Testing
Start 4 processes (as 4 routers) in 4 different terminals (they will be run on the same host). Each router
is given a router ID. Its running process is associated with its host name and the port number. We
assume they are
Router A: (localhost, 1000)
Router B: (localhost, 2000)
Router C: (localhost, 3000)
Router D: (localhost, 4000)
2
Make sure they are active before adding any links. This 4 routers will form the following network
topology:
1 3
A ---- B --- D
\ /
6\/2
C
We assume all links are symmetric in terms of link cost in both directions.
Perform the following actions:
• Add all links to the routers using the command add;
• Display the distance vector for each router using the command display.
Once the system is stabilized, B detects a link cost of BA from 1 to 60. Perform the following actions:
• Change the link cost of B-A to 60 using the command change at Router B;
• Print out the number of messages for all nodes before the system is stabilized again;
You are required to print out to the console on any message received by each router and any change of
DV at each router.
Next, apply Poison Reverse technique in the design of the DV. Re-perform the above actions again
and show the difference after applying the Poison Reverse technique.
3 Implementation Tips
Run each router as a separate process. In each router, you can start multiple threads to handle different
communications:
• One thread for receiving input from the console;
• One thread per neighbor commutation.
4 Bonus
Each router will periodically broadcast advertisement (its distance vector) to its neighbor (e.g., every
10s). The period will restart upon each broadcasting. If a router doesn’t hear one of its neighbor’s
advertisement within a timeout interval (e.g., 30s), it will remove this neighbor and update its distance
vector and broadcast the changed entries to its neighboring routers.
You need to implement another function:
kill It kills the running router. Input
kill
then we have the output as
Router A is about to be terminated...
In your testing, kill Router D in the end and then display the DV at Router A
NB// only coding part
Powered by