Programming Assignment 2
Programming Assignment 2
Networks Protocol Emulation
Selective Repeat over UDP and Distance Vector Routing
DUE: June 20, 11:59pm EST
Overview
Emulate a link layer and a network layer protocol
2 Independent Sections
Selective Repeat (SR) (link layer)
Distance Vector Protocol (network layer)
Will combine the 2 sections such that both algorithms work in tandem
Selective Repeat
Implement the Selective Repeat (SR) protocol on top of UDP to guarantee that all packets can be successfully delivered to the higher layers in the correct order
To emulate an unreliable channel, the receiver and the sender need to drop an incoming data packet or an ACK, respectively.
Do this deterministically (every M packets) or with a certain probability P
One program called “srnode”
Two node instances: sender and receiver
Both node processes will be on the same machine but different port numbers
Data packet: 1 character
Loss emulation: probabilistic or deterministic
Selective Repeat: Details
Selective Repeat: Setup
Two nodes, sender and receiver
Selective Repeat: Loss Rate Calculation
After transmission, sender and receiver each report:
Loss rate = # packets dropped / total # packets
A test: In probabilistic mode, actual loss rate should converge to command line drop probability p
In other words, if you send a large number of packets (~1000), the # of dropped packets should be close to 1000*p
Distance Vector Protocol
Objective: Implement a simplified version of a routing protocol in a static network.
Use the Bellman-Ford algorithm to build and update the routing tables
UDP should be used to exchange the routing table information among the nodes
We assume that that all the nodes run on the same machine and they all have the same IP address
Each node can be identified uniquely by a UDP port number, which is specified by the user
Keeping track of Routing Table
Upon the activation of the program, each node should construct the initial routing table and keep it locally
The node with the “last” keyword will send out its routing table first
Using Bellman-Ford, each node will keep updating its routing table as long as neighbouring nodes send their updated routing tables information
If there is any change in the routing table, a node should send the updated information to its neighbours.
NOTE: Each node should send its routing table information to its neighbours at least once.
Initializing Network Topology
=
Status Messages!
Please be sure to follow the status messages specified
Please note all the specifications in this section
Max Nodes = 16
Links and distances (costs) specified at start and stay static throughout test
Distance is same in both directions
Use UDP (if you did PA1 then you already know how!)
Combination
SR part + DV routing part to emulate a computer network with dynamic link state
Goal is to integrate code you’ve already written.
Dynamic Links
Use code from SR section
Probe packets instead of char messages
Loss rate calc: simplified
Only probabilistic packet drop
ACKs never dropped
Window size == 5
Probe packets
Probe packets sent continuously, loss rate updated
Each link connects two nodes, specify sender node and receiver node
Probe packets sent in one direction
Senders will only get link loss rate when receiver sends over Routing Table update
$ ./cnnode 1111 receive send 2222 3333 (receiving list is empty)
$ ./cnnode 2222 receive 1111 .1 send 3333 4444
$ ./cnnode 3333 receive 1111 .5 2222 .2 send 4444
$ ./cnnode 4444 receive 2222 .8 3333 .5 send last (sending list is empty)
Simple Example
Simple Example
Testing
We will be running your code on Google Cloud Machines using Ubuntu 18.04 LTS
Please run and test your code in this environment
Use the same instance as PA1 or re-create one on Google Cloud
Java, Python, and C allowed (same rules as PA1)
Some Tips
Start early (due date: June 20, 2021 by midnight)
Make sure a step works before going on to the next one
Please match the command line argument format
Please follow submission instructions relevant for your choice of programming language
Write clean, friendly, commented and well-structured code (so that we can give you as much partial credit as possible)
Some Tips
Remember that the Selective Repeat and Distance Vector Routing sections are independent of each other until you integrate them together
If you are stuck:
Check over for common errors (incorrect port #, loops ending before they should, etc.)
Threads can be difficult to debug. Avoid race conditions and deadlocks
Come to office hours
Questions on Piazza (any questions with source code must be only to Instructors)
Don’t get frustrated
Have a walk, eat some nice food, sleep on an idea, etc…
Have fun!