Summer 2021 – CSEE W4119 Computer Networks
Programming Assignment 2 – Network Protocols Emulation
Prof. Gil Zussman
due: 06/20/2021, 23:59pm
1 Introduction
In this assignment, you will emulate the operation of a link layer and network layer protocol in a small computer
network. The program you write should behave like a single node in the network. You will start several nodes
(instances of your program) so that they can send packets to each other as if there are links between them. Running
as an independent node, your program should implement a simple version of Selective Repeat (Link Layer) and the
Distance-Vector Routing Algorithm (Network Layer), in order to provide reliable packetized data transmission and
efficient routing.
Each section of the assignment will walk you through a different portion on the way to this end goal. Section
2 will have you implement the Selective Repeat (SR) protocol and Section 3 will have you implement a Distance
Vector (DV) routing algorithm. By the time you get to Section 4, which is to combine these two algorithms, you
should have the vast majority of the hard work done and can focus on these two algorithms working in tandem.
The assignment is split into these sections not only to make it easier, but also to give you the most opportunity for
partial credit. Accomplishing only Sections 2 and 3 will get you 80 of the 100 points available. Please follow the
instructions step by step, and submit the programs for whichever sections you attempt.
This assignment is meant to be done on your own; please do not collaborate with others as this is cheating.
Please start early, and read the entire assignment! Also ensure that your code works on the Google Cloud VM!
Good luck, and have fun!
2 Selective Repeat Protocol (40pt)
2.1 Description
This section involves two nodes, a sender and a receiver. The sender sends packets to the receiver through the UDP
protocol. You have to implement the SR protocol on top of UDP on both nodes to guarantee that all packets can be
successfully delivered in the correct order to the higher layers. To emulate an unreliable channel, the receiver or the
sender will drop an incoming data packet or an ACK, respectively, with a certain probability.
If there are any doubts about how the SR protocol should operate, please consult the course material and this
SR simulator webpage. This section should effectively operate exactly as this website shows.
2.2 Protocol
• Packet
For simplicity, one packet contains a single ASCII character, which means that the data in each packet should
have the max length of only 1 byte. This section involves two kinds of packets, data packets and ACK packets.
Your own packet header (not the UDP header) is needed to maintain the order of data packets. There will be
no requirements on the format of these headers, so you should come up with your own design. For example,
1
https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/selective-repeat-protocol/index.html
https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/selective-repeat-protocol/index.html
you can add a 32-bit sequence number ahead of the data you want to send. (See Figure 1).
Figure 1: SR Packet Header Example
The ACK packet is similar to the data packet except that it only has the header and does not have any data.
Please note that you must implement a mechanism for understanding what the last packet is. This could
be done for example in two ways: augmenting the packet header to store some extra information or by
transmitting a specific data value that signifies end of data.
• Buffers
Each node should have a sending buffer or receiving buffer, depending on its current mode of operation
(sender or receiver). On the sender’s side, all data packets (not ACK) should be put into the buffer before
sending, and removed from the buffer once the corresponding ACK is received. The sending buffer should
be long enough to avoid the conflict of packet numbers given the window size below. If the buffer is full, the
sending function simply waits until more space is available.
On the receiver’s side, the buffer is used to permit out-of-order packet delivery within the receiver’s window,
in line with the SR protocol.
• Window
The sender window moves along the sending buffer. If you implement the buffer as an array, the window
should wrap around to the beginning of the array after reaching the end. All packets in the window should be
sent out immediately. The size for the window will be passed in as an argument when starting your program.
The receiver window can be implemented identically, or differently as long as the receiver is able to buffer
out-of-order packets and ACK duplicate packets, even if they are outside of the receiver window. The size of
the receiver window will be the same as the sender window.
• Timers
You must maintain a timeout timer for each packet in SR, which starts after the packet is sent. The timeout
for the timer should be 500ms and after a timeout, the packet should be resent.
2.3 Emulation
You should create a program that emulates an SR node using the specifications above. Two SR nodes will be running
to send packets to each other over the UDP protocol. To emulate an unreliable channel, the receiver will deliberately
drop data packets (as if the packets are lost and not received) and the sender will deliberately drop ACKs before
actually handling them. There are two ways to control the drop of the packets – deterministic and probabilistic. The
deterministic way is to drop every nth packet, and the probabilistic way is to drop packets randomly with probability
p (for sanity check, probability of 0 here means no packets are lost, and probability of 1 means all packets are lost).
Which method will be used and the value of n or p will be passed in when starting the program.
Figure 2: Packet Loss Example
2
2.4 Command Syntax
• Starting Programs
The SR node should be started with the following command:
$ ./srnode
The user should only specify either -d or -p. The square bracket and the vertical line means to choose between
the two options.
-d means the SR node will drop packets (data or ACK) in a deterministic way (for every n packets), and -p
means the SR node will drop packets with a probability of p.
To make it clear, ”srnode” is the name of the program. The arguments should be passed in at the launch of
the program, not after the program has started to run. The square brackets with a bar in the middle indicate
an ”either or” command line option.
• Sending Messages
After the SR node has started, node> is prompted for commands. There is only one command allowed:
node> send
message is a character string which the sender will send to the 2.5 Status Messages [ [ [ Receiver side: [ [ [ [ [ Note that 2.6 Loss Rate Calculation [Summary] <# dropped>/<# total> packets dropped, loss rate = To test the loss rate emulation, set up a sender and receiver node where: • No ACKS fail (sender drop rate = 0) • Packets dropped probabilistically (receiver drops with probability p) • 1000 packets are sent (message of 1000 characters) • Receiver & sender window size is 5 At the end of the transmission, the receiver’s summary message should present a loss ratio near the input probability 3 2.7 Cases Normal packet sending with no loss (8pt) 2.8 Example node> send abcdefghi [1353035731.011] packet0 a sent [1353035731.012] packet1 b sent [1353035731.013] packet2 c sent [1353035731.015] ACK0 received, window starts at 1 [1353035731.015] packet3 d sent [1353035731.016] ACK1 received, window starts at 2 [1353035731.016] packet4 e sent [1353035731.019] ACK3 received, window starts at 2 [1353035731.106] ACK4 received, window starts at 2 [1353035731.511] packet2 timeout, resending [1353035731.515] ACK2 received, window starts at 5 [1353035731.515] packet5 f sent [1353035731.516] packet6 g sent [1353035731.517] packet7 h sent [1353035731.519] ACK5 dropped [1353035731.520] ACK6 received, window starts at 5 [1353035731.521] ACK7 received, window starts at 5 [1353035732.015] packet5 timeout, resending [1353035732.019] ACK5 received, window starts at 8 [1353035732.019] packet8 i sent [1353035732.023] ACK8 received, window starts at 9 [Summary] 1/10 ACKs dropped, loss rate = 0.100 Receiver side: [1353035731.013] packet0 a received [1353035731.013] ACK0 sent, window starts at 1 [1353035731.014] packet1 b received [1353035731.014] ACK1 sent, window starts at 2 [1353035731.015] packet2 c dropped [1353035731.017] packet3 d received out of order, buffered [1353035731.017] ACK3 sent, window starts at 2 [1353035731.018] packet4 e received out of order, buffered [1353035731.018] ACK4 sent, window starts at 2 [1353035731.513] packet2 c received [1353035731.513] ACK2 sent, window starts at 5 [1353035731.517] packet5 f received 4 [1353035731.517] ACK5 sent, window starts at 6 [1353035731.518] packet6 g received [1353035731.518] ACK6 sent, window starts at 7 [1353035731.519] packet7 h received [1353035731.519] ACK7 sent, window starts at 8 [1353035732.017] duplicate packet5 f received, discarded [1353035732.017] ACK5 sent, window starts at 8 [1353035732.021] packet8 i received [1353035732.021] ACK8 sent, window starts at 9 [1353035732.021] Message received: abcdefghi [Summary] 1/11 packets dropped, loss rate = 0.091 3 Distance-Vector Routing Algorithm (40pt) 3.1 Description 3.2 Network Model 3.3 Protocol 3.4 Routing Information Exchange 1. Upon the activation of the program, each node should construct the initial routing table from command line 2. Once the link and distance information for all the nodes are specified, the routing table information will be 5 3. Using the Bellman-Ford algorithm, each node will keep updating its routing table as long as neighboring 4. If there is any change in the routing table, a node should send the updated information to its neighbors. Due to the nature of the UDP protocol, packets may be lost or delivered out of order to the application. Thus you 3.5 Command Syntax dvnode Program name. It is between 0-1 and represents the probability of a packet being dropped on that link. last Indication of the last node information of the network. The program should understand this arg as ctrl+C (exit) Use ctrl+C to exit the program. 3.6 Status Messages 1. Routing message sent: 2. Routing message received: 3. Routing table (every time after a message is received, and for the initial routing table): – ( – ( – ( – ( 3.7 Cases Distance Vector Routing tables and their updates should follow DV algorithms (20pt) 6 3.8 Example Figure 3: Network Configuration Example The command to start a program is: 7 From the command line prompts type: $ ./dvnode 2222 1111 .1 3333 .2 4444 .8 $ ./dvnode 3333 1111 .5 2222 .2 4444 .5 $ ./dvnode 4444 2222 .8 3333 .5 last As soon as the command for node 4444 is entered the following process should kick in. 1. Node 4444 sends its routing information to node 2222 and 3333. 2. Node 2222 and 3333 update their routing tables according to the routing information sent from node 4444. 3. Node 1111 should update its routing table according to the message received either from node 2222 or 3333 4. Each node will update its routing table according to the messages received from its neighbors. However, it 5. The process converges as each node has the most updated routing table which includes the shortest distances Once the algorithm converges, there should be no more status messages. The last status message from the nodes [1353035852.173] Node 1111 Routing Table – (.1) -> Node 2222 – (.3) -> Node 3333; Next hop -> Node 2222 – (.8) -> Node 4444; Next hop -> Node 2222 [1353035852.192] Node 2222 Routing Table … [1353035852.239] Node 3333 Routing Table … [1353035852.287] Node 4444 Routing Table – (.5) -> Node 3333 – (.7) -> Node 2222; Next hop -> Node 3333 … 4 Combination (20pt) 4.1 Description 8 4.2 Loss Rate Calculation • Window size is always 5. • The data packet will only be dropped in a probabilitic way. • ACK will never be dropped. • Timeout is still 500ms. The loss rate of each link is calculated by the following equation: Link cost = { , otherwise A counter is needed for every link to get those numbers. 4.3 Probe Packets 4.4 Routing Information Exchange • The distances in the routing table should be rounded to the second demical place, • The updates of routing table should only be sent out 1) for every 5 seconds (if there is any change in the • The updates should be sent to all neighboring nodes, including all probe senders and receivers. • The probe receivers will only get the calculated distance of the corresponding links through the updates sent 4.5 Command Syntax 9 cnnode Again, the program name. If you are using a different sending port number, you have to add the listening port number send The current node will be the probe sender for the following neighbors. last The optional argument. Indication of the last node information of the network. Upon the input of the ctrl+C (exit) Use ctrl+C to exit the program. 4.6 Example Figure 4: Network Configuration Example $ ./cnnode 1111 receive send 2222 3333 (receiving list is empty) $ ./cnnode 3333 receive 1111 .5 2222 .2 send 4444 $ ./cnnode 4444 receive 2222 .8 3333 .5 send last (sending list is empty) When node 4444 is started, it will send DV update (initially all with loss rate of 0) to both node 2222 and node 4.7 Status Messages 10 [ For example: 4.8 Cases Counter The number of packets should be counted at the sender side (5pt) 5 Program Structure • single thread operation – The process should listen to the port, receive an incoming packet, parse the packet • multi-threading – The main thread within a process is always listening to its port. Once a UDP packet arrives The program structure is left for you to design and implement, but make sure you test it thoroughly. 6 Submission Instructions If using Java, use sudo apt-get install default-jdk to install the Java JDK. Please do not use Java 8. If using Python, the Google Cloud Ubuntu 16.04 LTS images already have Python 2.7 as well as Python 3.5 in- Make sure that your program compiles and runs on a Google Cloud Ubuntu 16.04 LTS instance before • README: The file contains the project documentation, program features, usage scenarios, brief explanation of • Makefile: This file is used to build your application. If you have written the programs in C (Unix), the output 11 dvnode.class, cnnode.class. You do not need a Makefile if you used Python, but please name your files • Your source code. • test.txt: This file should contain some output samples on several test cases. This would help others to The submission should be made via Courseworks. Zip all the deliverables mentioned above, and name the zip file In the grading of your work, we will take the following points into account. • The documentation clearly describes your work and the test result. • The source code is complied properly by using the Makefile and generate appropriate output files. • The programs run properly, including 1) take appropriate commands and arguments, 2) handle different • The programs follow the command line formats exactly, and that the deliverables are presented in the format Happy Coding and Good luck!! � 12 Introduction Distance-Vector Routing Algorithm (40pt) Combination (20pt) Program Structure
The following messages should be displayed on each node for the situations that have been described above:
Sender side:
[
[
At the end of the transmission, have both the sender and receiver print out the ratio of total packet failures to total
packets received, to see how it relates to the failure rate specified on the command line:
p.
Your program should deal with the following cases:
An ACK is lost Timer times out and packet resent (5pt)
An ACK is received out of order ACK accepted and window not moved (5pt)
A packet is dropped Timer times out and packet resent (5pt)
Duplicate packet received Correct ACK is sent (5pt)
A packet is received out of order Buffered and ACK sent (5pt)
Print received message Correct message sent, in-order (2pt)
Loss rate calculation Probabilistic loss rate test converges to input probability (5pt)
Sender side:
$ ./srnode 1111 2222 3 -p 0.1
$ ./srnode 2222 1111 3 -p 0.1
The objective of this portion of the assignment is to implement a simplified version of a routing protocol in a static
network. You are required to write a program which builds its routing table based on the distances (i.e., edge
weights) to other nodes in the network. The Bellman-Ford algorithm should be used to build and update the routing
tables. The UDP protocol should be used to exchange the routing table information among the nodes in the network.
You may assume that that all the nodes (instances of your program) run on the same machine and they all have
the same IP address. Each node can be identified uniquely by a (UDP listening) port number, which is specified
by the user. The port numbers must be > 1024. The maximum number of nodes to support is 16. The links
among the nodes in the network and the distances (non-negative integer) between two directly connected nodes are
specified by the user upon the activation of the program and stay static throughout the session. No need to support
dynamic link/node status changes. The link distance is the same for either direction (e.g. Between node A and B,
DistanceA→B = DistanceB→A.)
For this assignment, we will use the UDP protocol to exchange the routing information among the nodes. Each
node will send its most recent routing table by building a UDP packet. The destination port is the listening port of
the node to which the packet is being sent. The source port is an arbitrary UDP port the node is using to send the
packet. The data field of a packet should include 1) the sending node UDP listening port number (to identify the
sending node to its neighbor) and 2) the most recent routing table.
You are free to design the format and structure of the routing table kept locally by each node and exchanged among
neighboring nodes.
info, and keep it locally.
exchanged among network neighbors. Each node should send its routing table information to its neighbors at
least once. (See the command syntax section for more detail on how the process starts). This is the base case
before there are any table updates.
nodes send their updated routing tables information.
may consider to add some kind of time stamp or sequence information to each packet (i.e. each routing table), so
that each node can update its own routing table accordingly. Note that if the process is implemented properly, the
routing information exchange should converge (stop) as soon as all nodes in the network obtain the routing tables
with the shortest paths information.
The program name should be dvnode. For each node in the network, the command syntax is:
$ dvnode
For this section of the assignment you do not have to implement dropping of packets.
Keep listing the pair of
optional (hence represented in brackets above). Upon the input of the command with this
argument, the routing message exchanges among the nodes should kick in.
The followinh status messages should be displayed at least for the following events. The example of the messages
are also shown below.
[
[
[
Your program should deal with the following cases:
DV Updates DV updates should be sent out to all neighbors once the routing table is changed (10pt)
Convergence Routing tables should eventually converge and all output should cease (10pt)
The example below illustrates the command inputs, routing message exchanges and the computation of the routing
table at each node, given the network configuration described in Figure 3.
C $ ./dvnode
Java $ java dvnode
Python $ python dvnode.py
$ ./dvnode 1111 2222 .1 3333 .5
Since both node 2222 and 3333 have not sent their routing information to anyone, node 2222 sends its routing
information to node 1111, 3333 and 4444. Node 3333 will send its routing information to node 1111, 2222 and
4444.
whichever came first. Node 1111 will send its updated routing information to node 2222 and 3333. (At this
point, all nodes have sent their routing information to their neighbors at least once.)
will send messages only if its routing table is updated.
to all the nodes in the network and the next hop on the shortest path to each node.
will be something like (note: each node will print its own table):
As an ultimate goal for this assignment, both SR and DV protocols should be implemented and take effect in the
emulated network. The SR protocol can create reliable links, and the DV algorithms should determine the shortest
paths over these SR links. For this assignment, it is only required to generate the correct routing table for each node
using the two protocols. The distance of each link will be the packet loss rate on that link calculated by the SR
protocol.
This is the incorporation of section 2.6, so it should not be additional work. To simplify the problem, we put some
more specifications on the SR protocol:
0, (initial value) if no probe packets have been sent
Total number of dropped packets
Total number of sent packets
To obtain the loss rate quickly, probe packets (data packets with any data) should be sent ”continuously” (in one
direction) on all links. You should implement a sending interval. Because each link has two nodes, the user has to
specify which node is the probe sender, and which node is the probe receiver. Also, the sender should only start to
send probe packets when all nodes in the network have become ready. As described in Section 3, there will be a
last node with the word ”last” in the arguments. Once that node is started, the DV update messages should be sent
to all that last node’s neighbors, triggering the neighbors to send out DV messages as well. Therefore, the first time
a node receives a DV update message, it should know that the network has become ready, and it can start sending
probe packets.
The requirements for routing information exchange are similar to those in Section 3, except when the routing
updates should be sent out to neighbors. The loss rate calculated for each link will keep changing rapidly, but you
should not send updates to the network in the same frequency, as those packets would flood the entire network.
For this assignment, we have the following requirements:
rounded distances based on the newly calculated loss rate), or 2) when a DV update is received from a
neighbor that changes the local routing table.
by the probe senders.
Your program in this section should be named ”cnnode” and should be started with the following command:
cnnode
receive The current node will be the probe receiver for the following neighbors.
to your own packet header.
Keep listing the pair of
Keep listing the pair of
command with this argument, the routing message exchanges among the nodes should
kick in.
For example, to start the network shown in Figure 4: The user should use the following commands:
$ ./cnnode 2222 receive 1111 .1 send 3333 4444
3333.
After receiving the DV updates, node 2222 and 3333 should both update their routing table, send out the changes,
and start sending probe packets. Node 2222 will send DV update to node 1111, 3333, and 4444, and start sending
probe packets to 3333 and 4444. Node 3333 will send DV update to node 1111, 2222, and 4444, and start sending
probe packets to only 4444.
When node 1111 receives the DV update from either node 2222 or node 3333, it should update its own routing
table, send the DV update to node 2222 and 3333, and also start sending probe packets to node 2222 and 3333.
After that, there will be no more DV updates as no routing tables will be changed. All nodes have started to count
and calculate the loss rate of each link. 5 seconds later, the DV updates will be sent out again and all routing tables
will be updated. Note: Routing tables are ignorant of the loss rates input on the command line. The information
enters the tables via the ongoing loss rate calculations.
The status messages should contain those in Section 3.
Also, the packet loss rate for each link should be displayed every 1 second with the following format:
[1353035952.259] Link to 2222: 10 packets sent, 5 packets lost, loss rate .50
Your program should deal with the following cases:
Loss Rate The loss rate calculated at the sender should vary at first but eventually converge (5pt)
Distance Vector The routing tables should be updated periodically following the DV algorithm (5pt)
DV algorithm The routing tables should vary at first but eventually converge to the result of Section 3 (5pt)
The program should run an independent process per node. Within one process, there are two ways to operate:
data, and take actions (to update the local routing table and send out packets to its neighbors, or to check the
sequence number and send back an ACK). Once all the actions are completed, the process goes back to port
listening mode. The downsize of this approach is that normally there is a limited size input queue associated
with each UDP port. This implies that while the process is busy taking above actions, incoming packets may
be queued up and some of them may be lost. If you select this approach you have to verify that the routing
tables still converge.
to the port, a sub-thread is created to parse the message and take actions. By doing this, the main thread is
always listening to the port so that you will not miss any incoming packet. (Obviously there are many ways
to assign tasks to different sub-threads though.)
Please use C, Java, or Python for developing the emulation programs. You should develop on Ubuntu 16.04 LTS,
which is available on the Google Cloud platform.
Before you begin programming, install the required packages for your choice of the languages above. Before pro-
ceeding, be sure to run sudo apt-get update.
If using C, use this command in the terminal to download gcc: sudo apt-get install build-essential
stalled. If using Python 2, clearly state so in the README. Otherwise, it will be assumed that Python 3 is used.
you submit the package. Your final submission package should include the following deliverables:
algorithms or data structures used, and the description of any additional features/functions you implemented.
This should be a text file. You will lose points if you submit a PDF, .rtf, or any other format.
file names should be srnode, dvnode, and cnnode. If you used Java, the file names should be srnode.class,
srnode.py, dvnode.py, and cnnode.py.
understand how your programs work in each test scenario. It is optional to include this, as part of your README
document.
as
containing all deliverables. Upload the file in the Courseworks, under Assignments -> Programming Assignment 2.
It is highly recommended after submitting to download your submission, unzip it, and test it on Ubuntu 16.04 again!
situations and support required functions, and 3) display necessary status messages.
specified by the assignment.
Selective Repeat Protocol (40pt)
Description
Protocol
Emulation
Command Syntax
Status Messages
Loss Rate Calculation
Cases
Example
Description
Network Model
Protocol
Routing Information Exchange
Command Syntax
Status Messages
Cases
Example
Description
Loss Rate Calculation
Probe Packets
Routing Information Exchange
Command Syntax
Example
Status Messages
Cases
Submission Instructions