MCIT 553 Project 1
MCIT Online 553 Project 1 Code Documentation Link State and Distance Vector Routing
In this assignment, you will implement two routing protocols: link state and distance vector routing. 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.
Copyright By PowCoder代写 加微信 powcoder
An important goal of this project is to provide you the opportunity to read and understand a sizable
piece of software and extend it. Hence, we have deliberately not included all the details about the ns-3 code, particularly on specific APIs.
Please be aware that no amount of documentation can replace actual reading and running of the code itself. So rather than spend hours digesting this document without looking at the code, make sure you treat this document as a reference guide while you run the simulator and step through the control flow of various interacting software modules. To get into the habit of working as a team, we encourage you to spend a day or two to get your entire group together to try to understand the code as a team, and help each other out.
1 Getting Started
The TAs developed a version of ns-3.33 release for this assignment. Instead of downloading from the ns3 website, please download the file from course web page.
1.1 VM and ns-3 Download
We will provide a Docker environment for the class and a link to download the ns-3 starter code tar ball.
1.2 Git Repositories
We will be setting up a git repo for you in the CIS 553 Github account. Do not set up your own git repo outside of our assigned repositories. We will post a Google form for you to enter your group information necessarily for creating your repositories.
2 Code Structure and Compilation
For the purpose of this project, we have isolated all the code that you need to make/learn within the contrib/upenn-cis553 folder. All the other files for the purpose of testing are stored under scratch/re- sults, scratch/scenarios and scratch/topologies folder.
One of the important things to learn from this project is learning how to read and understand APIs within the code, before filling in the actual implementation. We will not provide details of APIs here.
Understanding these APIs is part of your project. To help you understand each function, we have added some comments (function headers).
Files to modify ls-routing-protocol.cc
This file contains all the event handles that you need to implement for handling incoming/outgoing route messages.
– For each incoming message, you need to implement the logic to handle the message, update local routing tables, and send out outgoing messages.
– Periodic/triggered link-state updates should be transmitted and handled within this class.
– Once the routing table is computed, handlers for forwarding messages should be imple- mented here, i.e. given an incoming message, forward the message along the computed next hop to the destination.
ls-message.cc
This file implements all the packet formats used in the above file. To implement your link-state protocol, feel free to extend this file to add new packet formats, for instance, “hello” packets for neighbor discovery, and “lsa” for link-state advertisements.
dv-routing-protocol.cc
Similar to ls-routing-protocol.cc
dv-message.cc
Similar to ls-message.cc
Files that are provided upenn-cis553/test-app
This folder contains the autograder and test code.
– test-app.cc
This is an example application that we have provided to test your link-state or distance vector implementation. This application periodically generates a small packet to be transmitted from any source to any destination nodes.
Feel free to modify test-app.cc to include your tests. While debugging your code, it is advisable to modify our test-app.cc to do something simpler, for instance, sending just one message from a fixed source to destination.
upenn-cis553/common
This folder contains all logging wrappers and test essentials. You should not modify the files inside this folder
scratch/topologies
This folder contains the input network to the ns-3 simulation.
scratch/scenarios
This folder contains the step-by-step scenario file that you can customize to start/stop a network, bring up/down links, output network state, etc.
• scratch/results
This folder contains the sample output for DUMP NEIGHBORS, DUMP ROUTES.
• scratch/simulator-main.cc
This contains the main driver program for your simulation. It takes as input the topology and scenario file, and executes the scenario. In the process, commands from the scenario file are sent to ls-routing-protocol.cc and dv-routing-protocol.cc, for instance, to generate a table dump, etc. Basically, our simulator-main handles basic commands related to link/node topology changes, and redirect routing-related commands to other modules. For instance, routing related commands are sent to ls-routing-protocol.cc and dv-routing-protocol.cc, while test-case specific commands are sent to test-app.cc.This file also generates optional outputs traces for animation.
DO NOT MODIFY simulator-main.cc.
Note: upenn-cis553/keys and upenn-cis553/penn-search are used in project 2, you should be able to finish project 1 without modifying them.
2.3 Compilation
To compile the code, first ssh to the docker environment. We use ”waf”, which is a python-based build tool to build our project. In order to use it, first make it executable.
$ chmod +x waf
Then run the configure command. You only need to run it once, unless you changed the wscript and thus need to update the configure.
$ ./waf configure
Then, compile the code using the following command, it will generate a simulator-main executable at ./build/scratch. It takes quite some time for the first time, and will be faster later.
If you want to add new helper source files, for instance, creating your own classes for route entries, neighbor entries, etc. Whenever you add a new file, you need to modify the wscript file (most likely to be contrib/upenn-cis553/wscript) within the subdirectory where your new file resides. Failure to do this means that the new file may be excluded from the build.
For faster compilation, use “./waf –j 4” to enable parallel compilation. Please do not be greedy and increase 4 to a larger number, since that will slow down the virtual machine and may not speed up your compilation by much!
2.4 Running and interacting with the simulator
The compiled binaries are located in the build directory. Now that you have successfully compiled your code, you can run the simulator by going to the main ns-3 directory, and run the command below:
Note: waf is one of the build tools that have good source file management, however, you can also run the code as a normal c++ project if you like. Remember to set environment variable first (you only need to do it once every time you open a terminal session):
$ ./waf –run “simulator-main –routing=
$ export LD LIBRARY PATH=./build/lib/
And then run:
You can choose either way of running your project, and the same rule applies to the following commands.
To test the implementation, you can add –result-check argument. But you don’t need it until you have finished your implementation.
For example, if you want to test LS algorithm with the 10 nodes topology:
To understand the commands above, run
$ ./waf –run “simulator-main –help”
3 NS-3 Architecture
For most part, you do not need to read any additional files beyond those in upenn-cis553. However for debugging purposes, it is important to understand the interactions of your code with other parts of ns-3. We provide a high-level overview here.
$ ./build/scratch/simulator-main –routing=
$ ./waf –run “simulator-main –routing=
$ ./waf –run “simulator-main –routing=LS –scenario=scratch/scenarios/10-ls.sce –inet- topo=scratch/topologies/10.topo –result-check=scratch/results/10-ls.output”
The figure shows layers 2-5 from the perspective of a single ns-3 node. At the link layer, each node has multiple IP addresses and interfaces/device. At the IP stack (layer 3), IP packets are forwarded as follows:
• RouteInput() receives a message from one of the devices. Your implementation has to determine the next hop to be taken for this message and forward the message to the appropriate device or the local host (if the destination is itself).
• RouteOutput() takes messages that originated from the local node, and then performs a similar next-hop forwarding or to the local host (if the destination is itself).
To understand how RouteInput() and RouteOutput() used, consult the OLSR code in src/olsr. You do not need to implement multicast for this project.
Note that all control messages used in link-state and distance-vector are sent via UDP protocol in layer 5 to immediate neighbors. This is counter-intuitive at first, since these protocols are implemented in layer 3, while UDP is a layer 4 service. However, this is a common practice to utilize the UDP protocol to bootstrap the protocol itself, where UDP is initially used for communicating with direct neighbors within the same subnet for exchanging control messages. However, once your routing protocol works, you should be able to write an application that uses UDP sockets to send packets to a destination node that is multiple hops away.
4 Input Topology
Your ns-3 simulation has to take in an initial input point-to-point topology. To see an example topology, refer to scratch/topologies.
Here is an example 10 node topology:
10 9 055 185 250 325 420 568 658 780 882 948
0 1 1973 0 2 4253 0 3 5341 0 5 4066 0 6 2702 0 9 4393 1 8 1033 2 7 10589 3 4 1126
This is based on a standard topology format used in network simulations. The topology has 10 nodes and 9 edges as initialized in the first line. The first 10 lines list each node and two attributes (X and Y coordinates). The next 9 are edges connecting nodes A to B with a edge weight. In our project, all edge
weights are set to 1, so you can ignore the edge attribute too (as a fun exercise after the project is done, you can consider using this edge attribute to do shortest path by aggregate link costs rather than by hop count).
The figure shows an example of point-to-point topology. Each node has a set of neighbors, one for each of its interfaces/device. The figure above contains also subnets and masks, which you need not worry about for this project. However, we included them in case you are interested to learn more.
In the topology file, we refer to nodes by node numbers, e.g. 0,1,2. . . However, once the topology is initialized, our simulator-main assigns to each node multiple IP addresses. The reason why each node requires multiple IP addresses is that it participates in multiple subnets (which you need not worry about). Our simulator-main will select one of the IP addresses as the unique identifier of the node. This identifier is what the node should advertise to its neighbors for computing routes. For instance, consider a node 0 that has IP addresses IP0,1, IP0,2, and IP0,3. In this case, IP0,1 is selected as the unique identifier. We have also provided APIs that will map from the logical node number to the corresponding unique IP address (and vice versa). However, we have included this discussion here for your own understanding should you be curious to learn how addressing works in a pt-to-pt network.
5 Scenario File
After the simulator has started the network, the scenario file is used to generate network events, such as link failures, node additions/failures, sending messages, dump commands to display network state, etc.
We have provided an example scenario file at scratch/scenarios/test.sce. This scenario file contains most of the commands indicated below. Your goal is to read this scenario file and understand what it is doing. For your own testing purposes, you probably should write your own (simpler) scenarios initially, and feel free to add your own commands (for example, commands to dump link-state updates and network statistics).
Most of the common commands have the following format:
Our simulator-main.cc will direct the command based on the module name to the appropriate code that implements the command handles. (ls-routing-protocol.cc, dv-routing-protocol.cc, or test-app.cc).
For instance, the command “1 LS VERBOSE TRAFFIC ON” will result in node 1 turning on all the traffic traces for the link-state protocol. “* LS VERBOSE TRAFFIC ON” will turn on the link-state traces for all nodes.
• VERBOSE
TRAFFIC ERROR DEBUG STATUS OUTPUT ALL
Use this when data is sent/received
Use this when error messages are to be printed Use this to print debug logs
Use this to print status messages
Use this to write output to a file
Use this to switch all traces at once
Note: ERROR and STATUS verbose is ON by default. For example, to switch on TRAFFIC traces for node 1:
1 LS VERBOSE TRAFFIC ON
• PING
Note that for LS and DV modules, PING can only be sent to immediate neighbors. We have added
this functionality as an example for students to implement their neighbor discovery for MS 1.
On the other hand, the APP module PING is multi-hop, which means the PING message ought to be forwarded to the destination node using the routing tables computed by LS or DV.
For example, Node 1 sends PING request to node 2 with a message: “hi!”:
1 LS PING 2 hi!
You may also use “*” wildcard with APP module:
1 APP PING * “hello!”
Node 1 sends PING to all the nodes in the topology.
• NODELINKS
NODELINKS DOWN 1
• LINK
LINK DOWN 1 8
LINK
LINK DOWN 6
TIME
TIME Display the current simulator time QUIT Quit Simulator
Commands to Implement
Note that the commands you need to implement for our actual demo are as follows:
DUMP ROUTES DUMP NEIGHBORS
Print out routing table Print out neighbors
1 LS/DV DUMP ROUTES
1 LS/DV DUMP NEIGHBORS
5.2 Interactive Scenario Mode
In addition to using the scenario file, you can also enter the scenario commands interactively via the keyboard. While the simulation is running, there is a command prompt that you can use to enter the commands described above.
6 Auto-checker Mode
At some point before your actual demonstration, we will be providing you with a sample topology/s- cenario and a result-check file. The auto-checker mode can be invoked by providing the given topol- ogy/scenario files, together with the result-check file by using the option “–result-check=
Please note that having your implementation match our result-check file is the bare minimum that you should aim to achieve. We recommend that you make sure your implementation clears the auto- checker before submitting on the Gradescope auto-grader. We are providing you this file so that you can be sure that your implementation is on track.
7 Basic Guidelines 7.1 Link-state Routing
Link State routing protocols hold at least 2 distinctive tables: a neighbor table, and an actual routing table. Link state routing operation follows four simple steps; each link state enabled router must perform the following:
1. Neighbor discovery Your node continuously probes the network at a low rate to discover its immediate neighbors in the network topology.
There are many design choices / implementations, here we list one of the possible implementa- tions, you are not required to use this implementation. Feel free to use other methods.
Suggested implementation: Write three methods: ”ProcessHelloReq, ProcessHelloRsp and BroadcastPacket”
(a) ProcessHelloReq
Once received a ”hello” message, neighboring nodes respond with a “hello reply” message with their IP addresses.
(b) ProcessHelloRsp
Once received a ”hello reply” message, and the destination address is own address, then process the message:
• If it is a new neighbor, add to ”m neighbors” table.
• If the neighbor exists, update ”m neighbors” table, since the timestamp changed, also
the link cost might be changed as well (for extra credit)
(c) BroadcastPacket
It can be called in ProcessHelloReq, periodic broadcast “hello” message on all outgoing interfaces to neighboring nodes to inform them of the node’s presence. The TTL of the broadcast message has to be set to 1, to avoid flooding the message to entire network.
Some basic guidelines:
• You may add additional packet types for “hello” message and ”hello reply” message. The ”hello” and ”hello reply” message should mirror the ping/pong message code.
• Neighbors disappear as well as appear (as specified in the scenario file or via the interactive command line). For debugging, you may want to print out the current list of neighbors so you can see who they are, perhaps only printing when there is a change.
• You will need to use timers to implement continuous, low-rate background activity. Be very careful with automated mechanisms, especially when using flooding and broadcast! They should operate on the timescale of at least tens of seconds (tens of thousands of milliseconds in the API calls!).
• Add the following command to your node: ”DUMP NEIGHBORS” to dump a list of all of the neighbors to which your node believes it is currently connected. Each neighbor entry should include
2. Flooding To tell all nodes about all neighbors.
It is recommended to add another message type for link state packet.
Your flooding protocol should not result in infinite packet loops or unnecessary duplicate packets (i.e. a node should not forward a link-state packet it has seen previously, or if it has seen a more recent one). A key design choice is whether to send out a LinkState packet periodically or immediately after the neighbor list changes. A key design criterion is t
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com