Homework is attached in this

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

Instructor: Dr. Shengquan Wang

Due Time: 6PM, 12/05/2015

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:

A B 7 1 B

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:

A B 7 1 B

A C 6 3 B

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.

3

5 Submission

You are going to report the following things:

(a) Describe in details how you implemented the DV.

(b) Write a detailed report with the screenshots of the testing results for the two scenarios: without Poison Reverse and with Poison Reverse. Each screenshot should include your username and the current time, which show that you did it by yourself.

(c) Specify the contribution made by each member if you work as a group.

The report should be written in a “.docx”, “.doc”, or “.pdf” format. All source codes should be well formatted with good comments. Submit the report and the source code files to Project P4 on Canvas separately. Any .zip or .tar format is not permitted.

4