CIS 5530: Project 1

Link State and Distance Vector Routing

Spring 2025

Overview

In this assignment, you will implement two routing protocols:  link state and distance vector routing. Your ns-3 implementation should be able to read network topology files and calculate the routing table based on the LS and the DV algorithms.  There will be commands to bring up/down a node or a link, your code should handle the update and reflect on the output in a timely manner.  We also provide an auto-grader and test files to validate your implementation.

1 Specification

We will be using the ns-3 discrete network simulator to teach core principles of network routing protocol design and implementation.  Your assignment is to extend ns-3 to support efficient routing using link- state and distance-vector protocols.  For more information on the existing code base and some tips on how to get started, please read the separate CIS 5530: Project 1 Code Documentation.

2 Project Specifications

2.1 Milestone 1 (12%)

In this milestone 1, you will work in teams to develop basic neighbor discovery capabilities to each node. The goals of this first milestone are to become familiar with the ns-3 development environment and understand the TA’s skeleton code. Before you write any code, make sure you read in detail the code documentation, understand the API and structure of the relevant parts of the ns-3 code.

All your code should go inside the upenn_cis553 directory and you should not modify other files in the ns-3 directory. You are free to add new packet types to ls-message.cc and dv-message.cc. Feel free to structure your own code, for instance, introduce your own helper files, or have one neighbor discovery module shared by both LS and DV.

You will finish the following tasks:

1. Neighbor Discovery.

2. Output neighbor table.

Expected Output. Once you finished the above tasks, you should be able to generate the Neighbor List by calling the ‘DUMP  NEIGHBORS ’ command.  The first row of Neighbor List is the total number of the neighbors for that node. Then followed by a series of neighbor entries. Each neighbor entry should include 〈neighbor node number, neighbor IP address, interface IP address〉 . This needs to work for both LS and DV. For example, the output of command ‘1  LS  DUMP  NEIGHBORS’ for 10-ls .sce and 10 .topo should be

**************** Neighbor List ********************

NeighborNumber    NeighborAddr    InterfaceAddr

2

0                              10.0.0.1           10.0.0.2

8                              10.0.6.2           10.0.6.1

Submission for Milestone 1. In Gradescope, select the relevant GitHub repository and branch, and Gradescope will automatically pull/test the most recent version.  Only one person in the team needs to submit.  Be sure to include all other team members in the Gradescope submission (look for the add teammates feature in the top right corner).

2.2 Milestone 2 (88%)

Your assignment is to extend your node to support efficient routing by implementing two protocols: link-state and distance-vector routing. If your implementation works, you will be able to route packets hop-by-hop through the network, having packets propagate through a path, only involving nodes on the route to the destination.

2.2.1 Link-state routing

Your node must implement link-state routing to construct a routing table, and use this routing table to forward packets towards their destination.  You should read about link-state routing in the Peterson textbook and in our lecture slides. The link-state protocol generally involves four steps (See more details in the code guidelines):

1. Neighbor discovery. (Built in MS1)

2. Link-state flooding.

3. Shortest-path calculation.

4. Forwarding.

2.2.2 Distance-vector routing

The second routing protocol you have to implement is the distance-vector routing protocol, described in our lecture notes and in the Peterson’s textbook.  Your solution should address the count-to-infinity problem by bounding the distance to a maximum of 16 hops.  Note that we are not implementing the entire RIP protocol, but a simple distance vector routing protocol that consists of the following four steps (more details in the code guidelines):

1. Neighbor discovery. (Built in MS1)

2. Distance-vector exchange.

3. Route calculation.

4. Forwarding.

Expected Output: Your output should be able to pass the auto-grader test. For example, when you run the protocol over the 10 nodes topology with the command:

$ ./build/scratch/simulator-main --routing=LS \

--scenario=scratch/scenarios/10-ls.sce \

--inet-topo=scratch/topologies/10.topo \

--result-check=scratch/results/10-ls .output

If you passed, you will get this message for each of the tests.

XXX is correct

Submission for Milestone 2: As with Milestone 1, select the relevant GitHub repository and branch, and Gradescope will automatically pull/test the most recent version. You will need to submit separately for LS and DV for small and large topologies. We strongly recommend you ensure that your implementation passes the local autograder first before submitting to Gradescope. As before, make sure you include all your teammates.

3 Extra Credit (submit together with Milestone 2)

Doing extra credit is entirely optional. We offer extra-credit problems as a way of providing challenges for those students with both the time and interest to pursue certain issues in more depth.  You should only attempt the extra credits after you have completed the regular portions of the project. Do note that if your regular credit LS and DV do not work correctly, we reserve the right not to award extra credit points. Hence, we recommend that you only start working on extra credits after you have finished the original assignment.

Submit your extra credit together with Milestone 2 (same deadline).  We will provide a separate submission folder on Gradescope for this submission.  You can add your own custom command line arguments to showcase a given extra credit feature. You are free to make any changes to any part of the ns-3 code base for extra credit, but make sure to not break your original submission in case you need to go back and change anything (e.g., keep things in a separate branch of the repo).

There is no autograder for extra credit. You will need to schedule a meeting with a TA to demonstrate your extra credit. After the deadline, TAs will reach out to schedule a meeting with your group.  Here are some examples of extra credits that you can implement.  For extra credit, you are responsible for providing your own test cases:

• Delay tolerant networking (10%) Implement summary-based epidemic routing protocol. Demon- strate actual implementation in a highly disconnected wireless network where nodes are connected   to each other infrequently. You will need to read up outside of course material on this protocol.

• Incremental Dijkstra computation (5%) Given a route update, instead of recomputing Dijkstra from scratch for all entries, perform. incremental recomputation that only updates routes relevant to the shortest path. To demonstrate working implementation, you need to demonstrate that your simulation can run significantly faster for the same network size (while computing the correct routes, of course!).

• Your proposal (X%) If you have a cool extension in mind, feel free to contact the teaching staff to discuss feasibility and points awarded.