Description

Updates to the assignment, including any corrections and clarifications, will be posted on the subject website. Please make sure that you check the subject website regularly for updates.

1. Change Log

2. Goal and Learning Objectives

In this assignment, your task is to implement the distance vector routing protocol. You will design a program that will be run at each router in the specified network. At each router, the input to your program is a set of directly attached links and their costs. Note that, the program at each router does not know the entire network topology. Your routing program at each router should report the cost and next hop for the shortest paths to all other routers in the network. Your program must be able to elegantly handle the failure of neighbouring nodes. You must also implement poisoned reverse to solve the count-to-infinity problem.

2.1 Learning Objectives

On completing this assignment, you will gain sufficient expertise in the following skills:
• Designing a routing protocol
• Distance vector algorithm
• UDP socket programming
• Routing optimisations

3. Assignment Specifications

3.1 Implementation Details

In this assignment, you will implement distance routing protocol.

The program will accept the following command line arguments:
• NODE_ID, the ID for this node (i.e. router). This argument must be a single uppercase alphabet (e.g.: A, B, etc.).
• NODE_PORT, the port number on which this node will send and receive packets from its neighbours.
• CONFIG.TXT, this file will contain the costs to the neighbouring nodes. It will also contain the port number on which each neighbour is waiting for routing packets. An example of this file is provided below.
• POISONED REVERSE FLAG (-p), this is an optional argument, which is used to turn on/off Poisoned reverse. This means that your program should accept either 3 or 4 arguments. If the – p flag is present in the argument list then poisoned reverse should be employed in the routing protocol. If this flag is absent then only basic distance vector should be used.

Since we can’t let you play with real routers, the routing programs for all the nodes in the simulated network will run on a single desktop machine. However, each instance of the routing protocol (corresponding to each node in the network) will be listening on a different port number. If your routing software runs well on a single desktop machine, it should also work on real network routers.

The file naming convention is explained later in the spec. For now, assume that the routing protocol is implemented in a file called Dvr.java (or Dvr.c or Dvr.py). The naming convention to be followed is explained later in the specification.

Assume that the routing protocol is being instantiated for a node A, with two neighbouring nodes B and C, and Poisoned reverse is off. A simple example of how the routing program would be executed (assuming it is a Java program) follows:

java Dvr A 2000 config.txt

where the config.txt would be as follows:
2
B 5 2001
C 7 2002

Important: Each node is only aware of the costs to its direct neighbours. The nodes do not have global knowledge (i.e. information about the entire network topology).

To run your program with Poisoned reverse on, the following command should be used:

java Dvr A 2000 config.txt -p

Of course, consistency must be maintained across all nodes, i.e. Poisoned reverse should be either enabled or disabled globally.

Note: The rest of this discussion will outline the specification for the basic distance vector protocol without Poisoned reverse. A separate section later will discuss Poisoned reverse.

Instead of implementing the exact distance vector routing protocol described in the textbook, you will implement a slight variation of the protocol. In this protocol, each node sends out the routing information (i.e. the distance vectors) to its neighbours at a certain frequency (once every 5 seconds), no matter if there have been any changes since the last announcement. This strategy improves the robustness of the protocol. For instance, a lost message will be automatically recovered by later messages.

As specified in the distance vector protocols, your routing program at each node will exchange the distance vectors with directly connected neighbors. Real routing protocols use UDP for such exchanges. Hence, you MUST use UDP for exchanging routing information amongst the nodes. If you use TCP, a significant penalty will be assessed.

On receiving distance vectors from its neighbours, each node should re-compute its own distance vector. The format of the distance vectors exchanged between the neighbours should be similar to that discussed in the text (and the lecture notes). You are free to choose an appropriate format for these messages.

Termination can be a tricky part of your implementation. Real routing programs run forever without termination, but your program must print out the routing table at some point in order to successfully complete the assignment. The key is to find out when the distance vectors have stabilised. You can be assured that when we test your program, we will start the routing program on all participating nodes simultaneously using scripts and that the topology of the network will be stable during the test (except for the cases when we are testing for node failures and Poisoned reverse, as explained later). Your program should be able to determine when the routing distance vector has stabilized; following which it should print the output to terminal. Don’t make us wait for more than three minutes!

Each node should print the final output to the terminal as shown in the following example (this is for node A in some arbitrary example):

Shortest path to node B: the next hop is D and the cost is 10
Shortest path to node C: the next hop is B and the cost is 11.5

The routing protocol running on each node should continue to execute forever, exchanging distance vectors with its neighbours periodically (every 5 seconds). To kill an instance of the routing protocol, the user should type CTRL-C at the respective terminal.

3.2 An Example

Let us consider an example with the network topology as shown in the figure overleaf:

shortest path to node B: the next hop is B and the cost is 2.0 shortest path to node C: the next hop is D and the cost is 3.0 shortest path to node D: the next hop is D and the cost is 1.0 shortest path to node E: the next hop is D and the cost is 2.0 shortest path to node F: the next hop is D and the cost is 4.0

Note: It is not necessary that the nodes are listed alphabetically as in the example output above.

Before you submit, you should ensure that your program provides a similar output for the above topology. Of course, you should not make any assumptions of the topology while coding. We will use a set of different network topologies for marking.

3.3 Handling Node Failures

Once a node detects that its neighbour has failed, it should recalculate its distance vector and exclude this neighbour from the vector computations. Further, the node need not compute the shortest path to this failed node. The newly computed distance vector should then be passed on to its other neighbours. Eventually, via the propagation of distance vectors, other nodes in the network will become aware that the failed node is unreachable and it will be excluded from all routing tables.

While marking your assignment, we will only fail a few nodes, such that a reasonable topology is still maintained. Further, care will be taken to ensure that the network does not get partitioned. However, note that the nodes do not have to fail simultaneously.

When we test the node failure feature, we will first start all nodes in the test topology and let the routing protocol stabilise and print the output. Once the output is available at all nodes, the desired node(s) will be killed (by typing CTRL-C in the respective terminal windows). We will again wait for your routing to stabilise and print the new shortest paths. If any further node failures need to be simulated, the above process will be repeated, else the remaining nodes will be terminated.

3.4 Implementing Poisoned Reverse

Your objective in this part of the assignment is to prevent the count to infinity problem that is known to affect the distance vector routing protocol by implementing Poisoned Reverse. (see the lecture notes on routing or the relevant sections on the text in Chapter 5)

As discussed earlier, your program should accept an additional optional parameter (-p), which should indicate whether the poisoned reverse module, is being used. This flag is used to turn on/off the poisoned reverse module. If the last flag is present in the argument list, then poisoned reversed is to be employed. The absence of this parameter indicates that only basic distance vector should be used.

In order to test poisoned reverse, we need to be able to change the link cost of certain links in the network topology. However, our basic configuration files do not provide this feature. Hence, we will use slightly different configuration files for testing this function. The following shows an example of the modified configuration file for node A:
2
B 5 50 2001
C 7 7 2002

4. Extension: Count-to-Infinity Issues (2 bonus marks)

NOTE: The amount of work involved in attempting the extension is not proportional to the bonus marks allocated. It is primarily geared towards high achieving students who want to take up the challenge.

Even though poisoned reverse solves the count-to-infinity problem in some instances, it is not a generic fix for this problem. In other words, it will not solve all count-to-infinity problems. In this extension, your first task is to provide an example of a network where the count-to-infinity problem still occurs even if nodes employ poisoned reverse. You should provide this example in the report and clearly explain the existence of this problem.

5. Additional Notes

This is not a group assignment. You are expected to work on this individually.

How to start: Sample UDP client and server programs are available on the Week 3 lecture material page. They are a good starting point to start your development. You will also find several links to network programming resources on that page.

Error Condition: Note that all the arguments supplied to the programs will be in the appropriate format. The configuration files supplied as an argument to each node will also be consistent with the test topology. Your programs do not have to handle errors in format, etc.

Do not worry about the reliability of UDP in your assignment. It is possible for packets to be dropped, for example, but the chances of problems occurring in a local area network are fairly small. If it does happen on the rare occasion, that is fine. Further, your routing protocol is inherently robust against occasional losses since the distance vectors are exchanged every 5 seconds. If your program appears to be losing or corrupting packets on a regular basis, then there is likely a fault in your program.

6. File Naming Convention and Assignment Submission

You should use the following naming convention depending on the functionality that you have implemented:
DvrBase.c (or DvrBase.java or DvrBase.py) if you have only implemented the basic distance vector protocol without Poisoned Reverse.
DvrPr.c (or DvrPr.java or DvrPr.py) if you have implemented Poisoned Reverse on top of the basic distance vector protocol.
DvrExt.c (or DvrExt.java or DvrExt.py) if you have implemented the extension in addition to the above.

This naming convention is important since it will inform us what tests to run while marking your assignment.

You are required to submit your source code and report.pdf. You do not have to submit any topology files. The only exception is if you have attempted the enhancement, in which case you will need to provide for configuration files for a test topology. You can submit your assignment using the give command in a terminal from any CSE machine (or connecting via SSH to the CSE login servers). Make sure you are in the same directory as your code and report, and then do the following:

1. Type tar -cvf assign.tar filenames
e.g. tar -cvf assign.tar *.java report.pdf

2. When you are ready to submit, at the bash prompt type 3331

3. Next, type: give cs3331 assign2 assign.tar (You should receive a message stating the result of your submission).

DO NOT SUBMIT ANYTHING ON OPENLEARNING.

Late Submission Penalty

Late penalty will be applied as follows:
• 5 or more days late: NOT accepted

NOTE: The above penalty is applied to your final total. For example, if you submit your assignment 1 day late and your score on the assignment is 10, then your final mark will be 10 – 1 (10% penalty) = 9.

That said, we are aware that a lot of learning takes place in student conversations, and don’t wish to discourage you from taking your classmates, provided you follow the Gilligan’s Island Rule – After a joint discussion of an assignment or problem, each student should discard all written material and then go do something mind-numbing for half an hour. For example, go watch an episode of Gilligan’s Island (or Reality TV in modern terms), and then recreate the solutions. The idea of this policy is to ensure that you fully understand the solutions or ideas that the group came up with.

8. Forum Use

9. Sequence of Operation for Testing

The following shows the sequence of events that will be involved in marking your assignment. Please ensure that before you submit your code you thoroughly check that your code can execute these operations successfully.

1) First chose an arbitrary network topology (similar to the test topology above). Work out the distance tables at each node using the methodology in the textbook (or lecture notes). Create the appropriate configuration files that need to be input to the nodes. Note again that the configuration files should only contain information about the neighbours and not of the entire topology.

2) Log on to a CSE Linux machine. Open as many terminal windows as the number of nodes in your test topology. Almost simultaneously, execute the routing protocol for each node (one node in each terminal).

java DvrBase A 2000 configA.txt (for JAVA)
java DvrBase B 2001 configB.txt and so on.

3) Wait till the distance vector converges and the nodes display the output at their respective terminals.

4) Compare the displayed shortest paths to the ones obtained in step 1 above. These should be consistent.

5) If you have attempted extension 1, let all nodes continue to run. Else kill all instances of the routing protocols.

6) For testing handling of failed nodes, kill a few nodes to simulate node failures. As indicated in the specification, these should be carefully selected to avoid partitioning the network. Wait till the distance vector protocol converges and the nodes display the output at their respective terminals.

7) Terminate all nodes.

8) If Poisoned Reverse has been implemented, the “-p” flag should be used to activate Poisoned reverse at all nodes. Select an appropriate topology and choose an appropriate link for which the link cost will be increased. Work out the distance vectors manually. Remember to use the modified configuration files for the nodes. Choose a large value for the link cost variation (typical cost variation should be 40 units or more). Following the convergence of the distance vector algorithm nodes will output the routing tables at the command prompt. Next, the change in the link cost will take affect and the distance vector computations will be performed again with poisoned reverse. Wait till the output is printed to the screen.

9) Terminate all nodes by typing CTRL-C in each terminal window.

NOTE: We will ensure that your programs are tested multiple times to account for any possible UDP segment losses (the occurrence of packet loss will be very rare).

10. Marking Policy

We will test your routing protocol for at least 2 different network topologies (which will be distinct from the example provided). Marks will be deducted if necessary, depending on the extent of the errors observed in the output at each node. After the marking process, we will upload the test topologies on the website for all students to view. Comments will be provided with each individual submission if marks have been deducted indicating the error in the outputs that we observed. The distribution of the marks will be as follows:
• Correct operation of the basic distance vector protocol: 6 marks
• Correct handling node failures: 2 marks
• Correct implementation of poisoned reverse: 3.5 marks
• Report: 0.5 mark.
• Extension: 2 marks (bonus).