Project 2: Simple Window-Based Reliable Data Transfer

Project 2: Simple Window-Based Reliable Data Transfer

1 Overview
The purpose of this project is to implement a basic version of reliable data transfer protocol, including
connection management. You will design a new customized reliable data transfer protocol, akin to TCP but
using UDP in C/C++ programming language. This project will deepen your understanding on how TCP
protocol works and specifically how it handles packet losses.
You will implement this protocol in context of server and client applications, where client transmits a file
as soon as the connection is established.The following functions should be realized:
• TCP connection management, including connection setup and tear-down.
• Large file transmission with pipelining.
• Loss recovery with Go-Back-N (GBN) or Selective Repeat (SR). If you implement SR, you can get up
to 10% bonus. Implementation with GBN will not get the bonus.
We made several simplifications to the real TCP protocol, especially:
• You do not need to implement checksum computation and/or verification;
• You can assume there are no corruption, no reordering, and no duplication of the packets in transmit;
The only unreliability you will work on is packet loss;
• You do not need to estimate RTT, nor to update RTO using RTT estimation or using Karn’s algorithm
to double it; You will use a fixed retransmission timer value;
• You do not need to handle parallel connections; all connections are assumed sequential.
• You do not need to realize congestion control in your project.
We require you implement code in a Linux environment so we can test it with simulated packet loss.
All implementations need to be written in C/C++ using BSD sockets. You are not allowed to use any
third-party libraries (like Boost.Asio or similar) other than the standard libraries provided by C/C++. You
are allowed to use some high-level abstractions, including C++11 extensions, for parts that are not directly
related to networking, such as string parsing and multi-threading.
2 Instructions
The project contains two parts: a server and a client.
• The server opens UDP socket and implements incoming connection management from clients. For each
of the connection, the server saves all the received data from the client in a file.
• The client opens UDP socket, implements outgoing connection management, and connects to the server.
Once connection is established, it sends the content of a file to the server.
Both client and server must implement reliable data transfer using unreliable UDP transport, including
data sequencing, cumulative acknowledgments.
1
UCLA CS 118 Project 2, Spring 2020
2.1 Basic Protocol Specification
2.1.1 Header Format
• You have to design your own protocol header for this project. It is up to you what information you
want to include in the header to achieve the functionalities required, but you need to at least include
a Sequence Number field, an Acknowledgment Number field, and ACK , SYN , and FIN flags.
• The header length needs to be exactly 12 bytes, while if your design does not use up all 12 bytes, pad
zeros to make it so.
2.1.2 Requirements
• The maximum UDP packet size is 524 bytes including a header ( 512 bytes for the payload). You
should not construct a UDP packet smaller than 524 bytes while the client has more data to send.
• The maximum Sequence Number should be 25600 and be reset to 0 whenever it reaches the maximum value.
• Packet retransmission should be triggered when no data was acknowledged for more than RTO = 0.5 seconds .
It is a fixed retransmission timeout, so you do not need to maintain and update this timer using Karn’s
algorithm, nor to estimate RTT and update it.
• If the ACK flag is false, Acknowledgment Number should be set to 0 .
• SYN and FIN packets must not carry any payload. But these packets should take logically 1 byte
of the data stream (same as in TCP, see examples).
2.2 Server Application Specification
2.2.1 Application Name and Argument
The server application MUST be compiled into a binary called server , accepting one command-line argument:
$ ./server <PORT
The argument hPORTi is the port number on which server will “listen” on connections (expects UDP
packets to be received). You can assume that the specified port is always correct. The server must accept
connections coming from any network interface. For example, the command below should start the server
listening on port 5000 .
$ ./server 5000
2.2.2 Requirements
• The server must open a UDP socket on the specified port number.
• When server is running, it should be able to accept multiple clients’ connection requests. It is guaranteed that a new client only initiates connection after the previous client closes its connection. In
other words, connections from clients are initiated sequentially, so you do not need to handle parallel
connections.
• The server must save all files transmitted over the established connection and name them following
the order of each established connection at current directory, as hCONNECTION ORDERi.file . For
example, 1.file , 2.file , etc. for the file received in the first connection, in the second connection, and
so on.
• The server should be able to accept and save files, where each file’s size could be up to 10 MB .
2
UCLA CS 118 Project 2, Spring 2020
2.3 Client Application Specification
2.3.1 Application Name and Argument
The client application MUST be compiled into a binary called client , accepting three command-line arguments:
$ ./client <HOSTNAME-OR-IP <PORT <FILENAME
Their meanings are:
• hHOSTNAME-OR-IPi : hostname or IP address of the server to connect (send UDP datagrams).
• hPORTi : port number of the server to connect (send UDP datagrams).
• hFILENAMEi : name of the file to transfer to the server after the connection is established.
For example, the command below should result in connection to a server on the same machine listening
on port 5000 and transfer content of testfile :
$ ./client localhost 5000 testfile
You can assume that the specified inputs are always correct.
2.3.2 Requirements
• The client must open a UDP socket and initiate 3-way handshake to the specified hostname/IP and
port.
– Send UDP packet with SYN flag set, Sequence Number initialized using a random number not
exceeding MaxSeqNum = 25600 , and Acknowledgment Number set to 0 .
– Expect response from server with SYN and ACK flags set.
– Send UDP packet with ACK flag including the first of the specified file. If the file is larger than
512 bytes, this packet should has exactly 512 bytes in the data field.
• Client should send file in pipeling scheme with a fixed window size 5120 (10 packets in a window) if
packets are not retransmissions. For retransmissions, the client only need to send packet sent but not
acked in the window
• After file is successfully transferred (all bytes acknowledged), the client should gracefully terminate the
connection following these steps:
– Send UDP packet with FIN flag set.
– Expect a packet with ACK flag and another packet FIN flag.
– Respond to each incoming FIN with an ACK packet; drop any other non- FIN packet.
– After receive the FIN packet, wait for 2 seconds to close connection and terminate.
• Client should support transfer of files that are up to 10 MB .
3
UCLA CS 118 Project 2, Spring 2020
2.4 Example
See below for an example illustration of two clients establishing connections and transmitting files to
the server.
Client1 Server
(A 500-byte file to send)
| |
| seq=12345, ack=0, SYN |
| ------------------------------------- |
| seq=221, ack=12346, SYN, ACK |
| <------------------------------------- |
| |
| seq=12346, ack=222, ACK |
| ------------------------------------- |
| (if include 500-byte payload) |
| seq=222, ack=12846, ACK |
| <------------------------------------- |
| |
| |
| FIN procedures to close connection |
| <------------------------------------ |
| (saves file 1.file) |
| |
close |
connection | Client2
(A 1000-byte file to send)
| |
| seq=5345, ack=0, SYN |
| <---------------------------------- |
| seq=4321, ack=5346, SYN, ACK |
| ---------------------------------- |
| |
| seq=5346, ack=4322, ACK |
| <---------------------------------- |
| (if includes 512-byte payload) |
| |
| seq=5858, ack=0 |
| <---------------------------------- |
| (if includes 488-byte payload) |
| |
| seq=4322, ack=5858, ACK |
| ---------------------------------- |
| |
| seq=4322, ack=6346, ACK |
| ---------------------------------- |
| |
| |
| FIN procedures to close connection|
| <--------------------------------- |
| (saves file 2.file) |
| |
close
connection
4
UCLA CS 118 Project 2, Spring 2020
See below diagram for illustration for FIN procedures during connection teardown.
Client Server
(A 10000-byte file to send)
| |
... ...
| (10000 bytes transferred) |
| |
| seq=22346, ack=0, FIN |
| ------------------------------------- |
| (no payload in FIN) |
| |
| seq=4322, ack=22347, ACK |
| <------------------------------------- |
| |
| |
| seq=4322, ack=0, FIN |
+-- | <------------------------------------- |
2 | | seq=22347, ack=4323, ACK |
s | | ------------------------------------- |
e | | |
c | ... (if ACK is lost) ...
o | | |
n | | seq=4322, ack=0, FIN |
d | | <------------------------------------- |
s | | seq=22347, ack=4323, ACK |
| | ------------------------------------- |
w | | |
a | ... close
i | | connection
t | |
| |
+-- |
close
connection
2.5 Error Handling: Loss
2.5.1 Loss emulation for testing
We will test your reliable transport protocol in unreliable conditions. However, we will only test under the
packet loss. You can safely assume there are no corruption, no reordering, and no duplication of the packets
in transmit.
Although using UDP does not ensure reliability of data transfer, the actual rate of packet loss or corruption in LAN may be too low to test your applications. Therefore, we are going to emulate packet loss
by using the tc command in Linux. Note that you need to have root permission to run tc command,
and it has to be applied on the proper network interface. There are two requirements for the network loss
emulation using tc :
• The file transmission should be completed successfully, unless the packet loss rate is set to 100%.
• The timer on both the client and the server should work correctly to retransmit the lost packet(s).
The following commands are listed here for your reference to adjust parameters of the emulation. More examples can be found in http://www.linuxfoundation.org/collaborate/workgroups/networking/netem.
5
UCLA CS 118 Project 2, Spring 2020
1. To check the current parameters for a given network interface (e.g. lo0 for localhost; The interface
name of localhost may differ on your laptop, you can figure it out by command ifconfig ):
tc qdisc show dev lo0
2. If network emulation has not yet been setup or have been deleted, you can add a configuration called
root it to a given interface, with 10% loss without delay emulation for example:
tc qdisc add dev lo0 root netem loss 10%
3. To delete the network emulation:
tc qdisc del dev lo0 root
2.5.2 Requirements
• Select Go-Back-N scheme OR Selective Repeat scheme for loss recovery. You’ll get bonus up to 10%
for implementing Selective Repeat.
• Generally, Go-Back-N scheme keeps ONE timer for the least recent unacknowledged packet and retransmits all unacknowledged packets upon timeout. RTO=0.5 seconds . Duplicate ACKs should not
trigger retransmission. Procedures at the sender are as follows (see pseudo code in section 3.33 of
textbook):
– After the sender sends out a packet, the timer is started if not running.
– After the sender receives a new ACK (not duplicate), the timer is restarted if there is any
unacknowledged packet.
– Upon timeout, the sender transmits all unacknowledged packets in the window; The timer is
started for the same packet again.
Procedures at the receiver are as follows:
– Upon receiving a packet, send back a cumulative ACK with the sequence number of the next
in-order byte expected from the sender. For example, the receiver has got bytes 0 - 511 and 1024
- 1535; The next in-order byte is 512. So when the segment of byte 1536 - 2047 arrives next, the
receiver will acknowledge this packet with ACK number 512.
– Any out-of-order packet and duplicate packet (which has been received before) is directly discarded.
• For Selective Repeat scheme:
– The sender keeps a timer for each unacknowledged packet. Retransmission of a certain packet is
triggered only when the corresponding timer is expired.
– The receiver acknowledges every packet with ACK number = sequence number of the last byte
of that packet+1. The ACK is not cumulative. For example, when the packet of bytes 0 - 511 is
received, the receiver will send back ACK with number 512.
2.6 Common Printout Format Requirements
The following output MUST be written to standard output ( std::cout in C++ or stdout in C) in the
EXACT format defined. If any other information needs to be shown for your own debugging, it MUST be
written to standard error ( std::cerr ) or commented out before your submission.
• Packet received:
RECV hSeqNumi hAckNumi [SYN] [FIN] [ACK]
• Packet sent:
SEND hSeqNumi hAckNumi [SYN] [FIN] [ACK] [DUP-ACK]
6
UCLA CS 118 Project 2, Spring 2020
• Packet retransmition:
RESEND hSeqNumi [SYN] [FIN] [ACK]
• Timeout:
TIMEOUT hSeqNumi
Note the convention:
• When a packet is being retransmitted, the client should print RESEND instead of SEND. Notice that
a server will never print RESEND because duplicate ACK transmission is not retransmission.
• Use one white space between any two pieces of information in the output line.
• hyyi means that value of yy variable should appear on the output (in decimal). Undefined value
should be 0. For example, in the first SYN packet in TCP three-way handshake, the AckNum should
be 0.
• [xx] means that xx string is optional. However, if the packet belongs to one or more of the following
cases you cannot omit the corresponding printout:
– Acknowledgment packet: [ACK]
– Duplicate ACK packet: [DUP-ACK] . When [DUP-ACK] shows up, [ACK] must not show up
at the same time.
– If SYN flag is set: [SYN]
– If FIN flag is set: [FIN]
Please make sure the printout of your client and server matches the format. You will get no credit if the
format is not followed exactly and our parsing script cannot automatically parse it. The parsing script will
be released to you at the end of the 8th week for you to check the format.
2.6.1 Sample Output
Please check following example of the client. This example shows the TCP three-way handshake and the
transmission of the first 10 packets of the file.
SEND 12345 0 SYN
RECV 4321 12346 SYN ACK
SEND 12346 4322 ACK
SEND 12858 0
SEND 13370 0
SEND 13882 0
SEND 14394 0
SEND 14906 0
SEND 15418 0
SEND 15930 0
SEND 16442 0
SEND 16954 0
...
Another client side output sample is GBN retransmission after timeout due to packet loss with sequence
number 12858.
...
RECV 4322 12858 ACK
SEND 17466 0
7
UCLA CS 118 Project 2, Spring 2020
TIMEOUT 12858
RESEND 12858 0
RESEND 13370 0
RESEND 13882 0
RESEND 14394 0
RESEND 14906 0
RESEND 15418 0
RESEND 15930 0
RESEND 16442 0
RESEND 16954 0
RESEND 17466 0
...
3 Hints
The best way to approach this project is in incremental steps. Do not try to implement all of the functionality
at once.
• First, assume there is no packet loss, implement the header fields and connection control functions
(initialization with 3-way handshake and termination). Just have the client initiate the connection
with 3-way handshake, send a small file (200 Bytes) as a packet, and the server respond with an ACK,
and then the server use FIN procedure to close the connection.
• Second, introduce a large file transmission and pipe-lining. This means you must divide the file into
multiple packets and transmit the packets based on the specified window size.
• Third, introduce packet loss. Now you have to add a timer for last sent packet (Go-Back-N) or several
timers for each unacked packets (Selective repeat). If a timer times out, the corresponding (lost) packet
should be retransmitted for the successful file transmission.
The credit of your project is distributed among the required functions. If you only finish part of the
requirements, we still give you partial credit. So please do the project incrementally.
4 Submission and Demo
4.1 Submission
This project is due June 5th, 2019 at 23:59 PT. Late submission is allowed by Sunday, June 7th (20%
deduction on Saturday, 40% deduction on Sunday). Put all your files into a directory, compress the directory
and generate a UID.tar.gz where UID is your UCLA ID. Your submission should include the following files:
• Your source codes (e.g. server.c, client.c). The code of the server and the client can be several files.
• A Makefile. The TAs will only type make to compile your code.
• A README file which will contain following information
– Your name, email, and UCLA ID
– The high level design of your server and client (one paragraph)
– The problems you ran into and how you solved the problems (up to three paragraphs)
– List of any additional libraries used Acknowledgement of any online tutorials or code example
(except class website) you have been using.
8
UCLA CS 118 Project 2, Spring 2020
4.2 Demo Requirements
1. Sign up for demo: TA will distribute the demo sign-up sheet in Week 8.
2. Testing files and scripts: TA will release testing files and scripts after the due data. So as the details
of demo. You need to download the testing files and scripts and learn how to run it before the demo.
3. Demo day:
• TAs will ask you to demo the function step-by-step on an up-to-date Linux system.
• You will use make to compile your programs, run your programs to deliver a test file from the
client side to the server side. Your program should print out operations according to the defined
format, and you should also be able to explain the delivery process. You will be asked to run test
scripts. TAs may ask you to use different values for tc command to test your program. TAs will
ask you to compare the received files with the sent ones using the Linux program diff.
• After the demo, TAs may ask you a few questions and you need to answer them. All question will
be related to your project implementation. Q&A and slides are counted towards the total credit
of this project.
9