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
NB// only coding part
You'll get a 16.0KB .ZIP file.