Project #4: Reliable Communication over an Unreliable Network

Project #4: Reliable Communication over
an Unreliable Network
CS 352 Internet Technology

Instructions
Please read these instructions carefully before you begin.
1. You must work on this project in teams of 2.
2. You are free to discuss the project on Piazza or through other means with your peers and the
instructors. You may refer to the course materials, textbook, and resources on the Internet for
a deeper understanding of the topics. However, you cannot lift solutions from other students
or from the web including GitHub, Stack Overflow, or other resources. Do not post this
project to question-answering services like Chegg. All written and programmed solutions
must be your team’s original work. We run sophisticated software to detect plagiarism and
carefully monitor student answers. If you are in doubt, please ask us.
3. You cannot post your solutions to this project on your personal GitHub page or on other web
services hosting class materials.
4. For each question in the project report, please be clear and concise. Vague and rambling
answers will receive zero credit.
5. For the report question on collaboration, please include anyone you discussed the project
with, and also any resources you consulted to learn how to solve this project, including
URLs of pages visited on the Internet. Please be specific about the aspect of the project that
you got help with. You must be thorough and as complete as possible here. It is mandatory
to answer this question.
6. We encourage you to start early and get the bulk of the work for this project done the week(s)
before it is due, rather than keeping it until the submission date.
7. If you have any questions or clarifications on the project, please post them on Piazza or
contact the course staff. We are here to help.
1
Overview
In project 4, you will implement a reliable sender using an unreliable UDP socket. There are two
programs provided in the project 4 archive: sender.py and receiver.py. You will only modify
sender.py. The sender.py program is a UDP sender that must implement the techniques of
reliable delivery that we discussed during lecture to upload a file to the receiver. Specifically, you
will implement reliability based on stop and wait and cumulative-ACK-based selective repeat. The
receiver.py program is a UDP receiver that is attempting to download a file transmitted by
the sender over a lossy channel that may drop packets, ACKs, or both. We will test reliability by
checking that the receiver’s version of the file matches exactly with the sender’s version of the file
(there are a few samples provided in the project archive for your testing and reference). Unlike the
prior projects, this project uses python3.
Step 1: Let’s take it for a spin!
The sender and the receiver are equipped with command line flags to customize their operation.
$ python3 sender.py --help
usage: sender.py [-h] [--port PORT] [--infile INFILE] [--winsize WINSIZE]
optional arguments:
-h, --help show this help message and exit
--port PORT receiver port to connect to (default 50007)
--infile INFILE name of input file (default test-input.txt)
--winsize WINSIZE Window size to use in pipelined reliability
You can specify which file you wish to upload through the --infile flag, the localhost port to
which the file must be uploaded (i.e., where the receiver is listening), and other flags. By default,
the file test-input.txt will be uploaded to localhost port 50007.
The receiver is more complex, with command line flags to control the packet and ACK losses
that are simulated in the communication.
$ python3 receiver.py --help
usage: receiver.py [-h]
[--pktloss {noloss,everyn,alteveryn,iid}]
[--ackloss {noloss,everyn,alteveryn,iid}] [--pktlossN PKTLOSSN]
[--acklossN ACKLOSSN] [--ooo_enabled]
[--port PORT] [--outfile OUTFILE]
optional arguments:
-h, --help show this help message and exit
--pktloss {noloss,everyn,alteveryn,iid}
Emulated loss behavior on packets (default
every n packets)
2
--ackloss {noloss,everyn,alteveryn,iid}
Emulated loss behavior on ACKs (default noloss)
--pktlossN PKTLOSSN n for pkt loss behaviors (only if loss specified)
--acklossN ACKLOSSN n for ack loss behaviors (only if loss specified)
--ooo_enabled enable out of order data buffering (default false)
--port PORT receiver local port to bind to (default 50007)
--outfile OUTFILE name of output file (default test-output.txt)
By default, the channel between the sender and receiver drops every 3rd packet that is transmitted to it (i.e., --pktloss everyn --pktlossN 3) but does not drop ACKs (i.e., --ackloss
noloss). By default, the receiver writes its downloaded output into the file test-output.txt.
Step 1.1: Test without any drops
To test the file upload/download without any packet drop, run the following commands on separate
terminals:
python3 receiver.py --pktloss noloss
and
python3 sender.py
By doing this, we are configuring the receiver to not drop any data (packets or ACKs); instructing sender.py to simply push the bytes in the input file test-input.txt through the UDP
socket to the receiver, and the receiver to write the downloaded outputs into test-output.txt.
You will see many helpful prints on both the sender and the receiver. At the sender:
[S] Transmitting file test-input.txt
[S]: Sender socket created
Transmitted Seq: 5 ACK: 2345367 Len: 2 Msg: 88
Transmitted Seq: 7 ACK: 2345367 Len: 8 Msg: msg 1
Transmitted Seq: 15 ACK: 2345367 Len: 8 Msg: msg 2
Transmitted Seq: 23 ACK: 2345367 Len: 8 Msg: msg 3
Transmitted Seq: 31 ACK: 2345367 Len: 8 Msg: msg 4
Transmitted Seq: 39 ACK: 2345367 Len: 8 Msg: msg 5
Transmitted Seq: 47 ACK: 2345367 Len: 8 Msg: msg 6
Transmitted Seq: 55 ACK: 2345367 Len: 8 Msg: msg 7
Transmitted Seq: 63 ACK: 2345367 Len: 8 Msg: msg 8
Transmitted Seq: 71 ACK: 2345367 Len: 8 Msg: msg 9
Transmitted Seq: 79 ACK: 2345367 Len: 8 Msg: msg 10
Transmitted Seq: 87 ACK: 2345367 Len: 8 Msg: msg 11
[S] Sender finished all transmissions.
3
The input file is broken up into packets each of which contains 8 bytes. Each message is transmitted with an application layer protocol format that includes a sequence number, ACK number,
message length, and the actual application bytes. At the receiver, you will see:
[R]: Receiver socket created
Received Seq: 5 ACK: 2345367 Len: 2 Msg: 88
Transmitted Seq: 235347 ACK: 7 Len: 0 Msg:
Received Seq: 7 ACK: 2345367 Len: 8 Msg: msg 1
Transmitted Seq: 235347 ACK: 15 Len: 0 Msg:
Received Seq: 15 ACK: 2345367 Len: 8 Msg: msg 2
Transmitted Seq: 235347 ACK: 23 Len: 0 Msg:
Received Seq: 23 ACK: 2345367 Len: 8 Msg: msg 3
Transmitted Seq: 235347 ACK: 31 Len: 0 Msg:
Received Seq: 31 ACK: 2345367 Len: 8 Msg: msg 4
Transmitted Seq: 235347 ACK: 39 Len: 0 Msg:
Received Seq: 39 ACK: 2345367 Len: 8 Msg: msg 5
Transmitted Seq: 235347 ACK: 47 Len: 0 Msg:
Received Seq: 47 ACK: 2345367 Len: 8 Msg: msg 6
Transmitted Seq: 235347 ACK: 55 Len: 0 Msg:
Received Seq: 55 ACK: 2345367 Len: 8 Msg: msg 7
Transmitted Seq: 235347 ACK: 63 Len: 0 Msg:
Received Seq: 63 ACK: 2345367 Len: 8 Msg: msg 8
Transmitted Seq: 235347 ACK: 71 Len: 0 Msg:
Received Seq: 71 ACK: 2345367 Len: 8 Msg: msg 9
Transmitted Seq: 235347 ACK: 79 Len: 0 Msg:
Received Seq: 79 ACK: 2345367 Len: 8 Msg: msg 10
Transmitted Seq: 235347 ACK: 87 Len: 0 Msg:
Received Seq: 87 ACK: 2345367 Len: 8 Msg: msg 11
[R] Writing results into test-output.txt
[R] Receiver finished downloading file data.
You can check that the file was received intact by comparing the input and output files. In this
project, we can use the diff command to do this. Run
diff test-output.txt test-input.txt
If you see a blank output, that means the files are exactly the same. The transmission was fully
correct!
Step 1.2: Test with packet loss
Unfortunately, real networks can experience loss of packet data, and UDP sockets don’t provide a
reliable interface over lossy networks. Let’s try our file upload/download over a lossy network. On
separate terminals, run
4
python3 receiver.py
and
python3 sender.py
By default (i.e., with no options to receiver.py), the communication channel deterministically drops every 3rd packet that is transmitted by the sender. The sender.py program happily
thinks it has sent all the data correctly. However, there are mistakes in the downloaded file. The
content corresponding to messages 1, 4, 7, and 10 are only in the input, but not in the output!
$ diff test-output.txt test-input.txt
0a1
> msg 1
2a4
> msg 4
4a7
> msg 7
6a10
> msg 10
You will see from the receiver.py output that the receiver indeed detects these losses
through the gaps in the sequence numbers. Specifically, there are messages that say “fresh data
creating seq space hole”, corresponding to data received after dropped sequence numbers:
[R]: Receiver socket created
Received Seq: 5 ACK: 2345367 Len: 2 Msg: 88
Transmitted Seq: 235347 ACK: 7 Len: 0 Msg:
Received Seq: 15 ACK: 2345367 Len: 8 Msg: msg 2
[R] Fresh data creating seq space hole
Transmitted Seq: 235347 ACK: 23 Len: 0 Msg:
Received Seq: 23 ACK: 2345367 Len: 8 Msg: msg 3
Transmitted Seq: 235347 ACK: 31 Len: 0 Msg:
Received Seq: 39 ACK: 2345367 Len: 8 Msg: msg 5
[R] Fresh data creating seq space hole
Transmitted Seq: 235347 ACK: 47 Len: 0 Msg:
Received Seq: 47 ACK: 2345367 Len: 8 Msg: msg 6
Transmitted Seq: 235347 ACK: 55 Len: 0 Msg:
Received Seq: 63 ACK: 2345367 Len: 8 Msg: msg 8
[R] Fresh data creating seq space hole
Transmitted Seq: 235347 ACK: 71 Len: 0 Msg:
Received Seq: 71 ACK: 2345367 Len: 8 Msg: msg 9
Transmitted Seq: 235347 ACK: 79 Len: 0 Msg:
Received Seq: 87 ACK: 2345367 Len: 8 Msg: msg 11
5
[R] Fresh data creating seq space hole
[R] Writing results into test-output.txt
[R] Receiver finished downloading file data.
Step 1.3: Understand different modes of loss
You can experiment with many different kinds of loss behaviors for this unreliable network channel. You can configure the loss behavior through command line flags at the receiver. Here is a
description of these flags you can supply to receiver.py.
• --pktloss everyn --pktlossN N: The network is configured to deterministically drop
every Nth packet transmitted to the receiver, starting from packet number N - 1. Similar loss
behavior can be effected on ACKs by using the flag --ackloss everyn --acklossN N.
• --pktloss alteveryn --pktlossN N: For every N packets transmitted by the sender,
the network deterministically drops packets N-3 and N-1. This creates not just one hole, but
two holes in the sequence space. Similar loss behavior can be effected on ACKs by using
the flag --ackloss alteveryn --acklossN N.
• --pktloss iid --pktlossN N: The network drops each packet probabilistically with
an independent identical probability (I.I.D) of 1/N. Similar loss behavior can be effected on
ACKs by using the flag --ackloss iid --acklossN N.
• --pktloss noloss ensures that no packets are dropped. The flag --ackloss noloss
ensures that no ACKs are dropped. This is helpful to debug your program.
Packet loss and ACK loss are orthogonal behaviors that be configured independently. For
example, you could ask that every 5th data packet is dropped and every 8th and 10th ACK is
dropped. This is achieved by invoking the receiver script with the flags --pktloss everyn
--pktlossN 5 --ackloss alteveryn --acklossN 10.
Your task in this project is to design a sender that is reliable against all of these modes of packet
and ACK loss. You will achieve this by implementing a stop-and-wait reliable sender. Then, you
will also improve the file download time by implementing a pipelined reliable sender.
Step 2: Understand sender.py
It is worthwhile to spend a little time understanding the code in sender.py. Here are some of the
salient pieces:
Message class Msg. Objects of this class represent our own custom protocol message at the
application layer. The message contains a sequence number (for data packets), an ACK number
(for ACKs), a payload length (corresponds to the length of application data in the message), and
finally the actual application content. These fields are separated by the pipe (‘|‘) character if
you inspect the packet. The Msg class has helper methods to construct application “packets” with
specific sequence number, ACK, and application-layer messages, and also to construct a Msg object
out of a message that is received on the wire.
6
Helper methods. There are several helper functions to initialize a socket, read an entire file and
chunk this data into packets for transmission, and to parse command line arguments.
The reliable sending function send reliable. This is where you’ll be spending all your
time working on this project. This function has two internal helper methods transmit one()
and transmit entire window from() which are useful to transmit one and multiple packets
respectively.
When you’re implementing stop-and-wait reliability, you’ll only need to use transmit one().
Pay particular attention to how this function calls sendto() on the socket, rather than send()
that we’re used to in TCP. This is a key difference between TCP and UDP; UDP senders (usually)
state who the intended recipient of each message is because they are connectionless and intended
for one-off packet transfers. A similar socket call for receiving data, recvfrom(), returns both
the content of the data as well as the sender who sent it, unlike recv() which only returns the
first.
When you implement pipelined reliability, you will call transmit entire window from(x)
to transmit all data with sequence numbers starting at x. For example, x could be the “left” edge of
the window (win left edge) which is the first unACKed sequence number in order. The value
x could also be somewhere further into the window ahead of win left edge. The function will
transmit all data up to the “right” edge of the window, i.e., the latest sequence number that is
allowed to be transmitted by the sender given where the window is.
The window size is configured through the --winsize flag and defaults to a value of 20 bytes.
You only need to use the window size when you implement and test pipelined reliability.
At the end of this function comes the most interesting part of the function’s logic where you
will make all of your changes. This region of code is marked by a TODO in the code. You won’t
need to change any other parts of this program. In the starter code, there is a while loop that
transmits one packet each time, running until the left edge of the window exceeds the last valid
sequence number of the data, i.e., until win left edge >= INIT SEQNO + content len. If
you think about what this code is doing, this sender isn’t a reliable sender at all; the sender merely
transmits the packets one by one without checking whether they were actually delivered to the
receiver!
Constants. The initial sequence number of a stream in our protocol can be any arbitrary value.
The starter code for sender.py uses the value INIT SEQNO = 5. The size of the application
payload in each packet is set in the variable CHUNK SIZE, which is 8 bytes. The retransmission
timeout is set to a constant RTO = 500 ms. Please do not change these constants.
The main thread. The code block under if name == ’’ main ’’ shows the main thread
of execution of the sender. The command line arguments are parsed into the Python dictionary
args. The rest of this block simply constitutes calls to various functions including send reliable().
The flow of logic here should be straightforward to understand.
7
Step 3: Stop-and-wait reliability
As discussed in lecture, stop and wait reliability requires a sender to (1) wait for an ACK before
transmitting the next piece of data, (2) if ACKs don’t return within a timeout (RTO), retransmit
the data, (3) distinguish different pieces of data using sequence numbers. The existing starter code
already simplifies your life quite a bit: receiver.py already sends ACKs, and transmit one()
already sends data with the appropriate sequence numbers to help the receiver disambiguate fresh
transmissions from retransmissions.
Step 3.1: How to implement stop-and-wait
Your main task in this step reduces to waiting for an ACK of a transmitted packet, and either (i)
transmitting the next piece of data if an ACK is successfully received, or (ii) retransmit the old
packet if no ACK was received before a timeout (use the variable RTO for the timeout).
You have already implemented receivers that time out waiting for data in project 2. You can
use similar mechanisms here. We recommend using the select() call. If you have readable data
from this call, you can use the socket recvfrom() method to obtain readable data. Here is some
example code you could use to parse the data that you’ve read from recvfrom():
# r is a readable socket
data_from_receiver, receiver_addr = r.recvfrom(100)
ack_msg = Msg.deserialize(data_from_receiver)
print("Received {}".format(str(ack_msg)))
You can obtain the acknowledgment number on the received ACK (really, the only useful information in the ACK) by reading ack msg.ack. Like TCP, the sender and receiver in this project
use byte-based sequence and ACK numbers. Further, like TCP, the ACK number returned by
receiver.py is the next expected sequence number.
Once you receive an ACK, you can advance the left edge of the window win left edge to
the acknowledgment number in the ACK. Check if this window edge has advanced past the last
sequence number you need to transmit, and terminate your sender appropriately. Otherwise, loop
to transmit the next message using transmit one().
Step 3.2: Test your code
Use all the lossy scenarios described in step 1.3 above and transmit files test-input.txt,
medium-input.txt, and long-input.txt. The difference between the uploaded and downloaded versions of the file (as checked with the diff command) should be empty. We recommend
checking with the following cases:
1. no packet loss, no ACK loss
2. packet loss everyn with N = 3, no ACK loss
3. packet loss everyn with N = 10, no ACK loss
4. no packet loss, ACK loss everyn with N = 3
8
5. no packet loss, ACK loss everyn with N = 10
6. packet loss alteveryn with N = 8, no ACK loss
7. no packet loss, ACK loss alteveryn with N = 8
8. packet loss iid with N = 5, no ACK loss
9. no packet loss, ACK loss iid with N = 5
10. packet loss everyn with N = 3, ACK loss alteveryn with N = 4
11. start the sender first, give a few seconds, then start the receiver (with any of the loss behaviors
mentioned above)
In all of the cases above, a correct sender will:
1. eventually finish execution by making progress through the sequence numbers corresponding
to the application message. File upload must take just a few seconds for test-input.txt.
Other files may take a bit longer, but the sequence numbers being transmitted (as printed)
must clearly advance over time.
2. return an empty diff between the uploaded and downloaded files for all loss behaviors
mentioned above. and all input (upload) files provided in the project archive.
If all of this is working as intended, freeze your code by copying sender.py into a separate
file, stopandwait.py. You will submit stopandwait.py in addition to the final version of
sender.py after step 4 (described below).
Step 4: Pipelined reliability
If you’ve made it this far, you’ve already built a reliable sender out of an unreliable network! Your
task in this step is to make this sender more efficient while still being reliable. Further, you will
implement selective repeat through cumulative acknowledgments.
The first step to implement pipelining with selective repeat is to ask the receiver to buffer outof-order data so that the sender does not need to resend all data after a packet loss. The receiver-side
functionality needed for this is already available: just invoke the receiver in the following way (you
may include any additional flags you need for the intended loss behaviors):
python3 receiver.py --ooo_enabled
Proceed to implement the pipelined sender with the following additional steps.
(Step 4.1) Transmit a window of packets first. When transmission begins, use the function
transmit entire window from() to send a burst of packets starting from the current left edge
of the window, win left edge.
(Step 4.2) Preliminaries It helps to initialize and maintain a variable last acked that tracks
the highest cumulative ACK number received so far. (Recall that you can retrieve the ACK number
from an ACK through the .ack member of a Msg object.)
It also helps to separately initialize and maintain the first sequence number that must transmitted by the sender after a number of transmissions. Let’s call this value first to tx. After each
transmission of application data, you may use the value returned by the functions transmit one()
or transmit entire window from() to set first to tx.
9
Finally, it is useful determine what the final cumulative ACK from the receiver (i.e., after successful reception of all data) must indicate on its acknowledgment number field. The final ack
is just INIT SEQNO + content len. We will use final ack to determine when to terminate
the sender.
Next, enhance your stop-and-wait implementation with these additional checks whenever you
have ACKs after a recvfrom() call.
(Step 4.3) If the ACK acknowledges fresh data, slide the window forward. The slide
must reflect changes to the variables corresponding to the left window edge (win left edge), the
right window edge (win right edge), and the cumulative ACK number (last acked).
(Step 4.4) Is there more data to transmit? If the window has slid forward, the sender now
becomes free to transmit more data, assuming that the right edge of the window hasn’t gone
beyond the set of available sequence numbers to transmit (bounded by final ack). Call the
transmit entire window from() function supplied with the first sequence number that must
be transmitted, first to tx.
(Step 4.5) If there is no more fresh data, have all required ACKs been received? This
can be determined by checking whether last acked is the same as final ack. At this point, we
can terminate all transmission and reception.
If there is either more fresh data to transmit, or not all ACKs have been received, the sender
should wait for ACKs (same as it did with stop-and-wait) to help slide its window forward for the
subsequent transmissions or finish receiving all ACKs.
(Step 4.6) Handling timeouts. Ensure that you only transmit one() after a timeout, since
we are using selective repeat, and the receiver is buffering out-of-order data to reduce unnecessary
transmissions.
In a true pipelined reliable sender, there is a distinct timeout for each sequence number in flight.
However, the select() call implements a timeout on the entire socket. The distinction between
a timeout per socket and a timeout per sequence number did not matter in stop-and-wait, because
all sequence numbers in flight will either be ACKed together or none of those sequence numbers
will be ACKed at all. However, with pipelined reliability, if you use a select() call as you did
in step 3.1, a single lost packet may not trigger a retransmission timeout on the socket if the sender
is continuing to receive any data at all (usually duplicate ACKs) on the socket.
In this project, we will keep things simple and just implement a single RTO on the socket rather
than one RTO per sequence number. So, you can keep the select() implementation from step
3.1.
(Step 4.7) Test your code. Your code should continue to run correctly with all the test cases in
step 3.2. In addition, you can test multiple window sizes. We suggest testing with three values,
the default (20 bytes), one medium (200 bytes), and one large (2000 bytes). You can change the
sender’s window size using the --winsize flag. A correct pipelined sender should indeed run
faster than the corresponding stop-and-wait sender.
10
What you must submit
For your project submission on Canvas, please turn in stopandwait.py (unmodified after step 3),
sender.py (after step 4), and your project report report.pdf. You cannot change the command
line arguments for the programs relative to the starter code. The questions for the report are listed
below. We will be running your code on the ilab machines with the default Python 3 version on
those machines. Please compress the files into a single Zip archive before uploading to Canvas.
Only one team member must submit. We will not accept modified versions of receiver.py; your
senders must work with the unmodified receiver script.
Testing your programs. We have already described how we will test your programs in steps 3.2
and 4.7 above.
Project report. Please answer the following questions for your project report.
1. Team details: Clearly state the names and netids of your team members (there are 2 of you).
2. Collaboration: Who did you collaborate with on this project? What resources and references did you consult? Please also specify on what aspect of the project you collaborated or
consulted.
3. Is there any portion of your code that does not work as required in the description above?
Please explain.
4. Did you encounter any difficulties? If so, explain.
5. Describe two technical observations or facts you learned while working on this project.
Please answer in specific and precise terms. Your observations could relate to topics including reliable data delivery in general, your implementation of it in this project, reliable
delivery in TCP, using UDP sockets, or other topics that are relevant to your software and
implementation in this project. Please ensure your responses are clear, specific, and technical.
Contact the course staff on Piazza if you have any questions.
11