$29
Project 2: Simple Window-Based Reliable Data Transfer Solution
• 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 speci cally how it handles packet losses.
You will implement this protocol in context of server and client applications, where client transmits a le as soon as the connection is established.The following functions should be realized:
TCP connection management, including connection setup and tear-down. Large le 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 simpli cations to the real TCP protocol, especially:
You do not need to implement checksum computation and/or veri cation;
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 xed 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.
• 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 le.
The client opens UDP socket, implements outgoing connection management, and connects to the server. Once connection is established, it sends the content of a le 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 Speci cation
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 eld, an Acknowledgment Number eld, and ACK , SYN , and FIN ags.
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 maxi-mum value.
Packet retransmission should be triggered when no data was acknowledged for more than RTO = 0.5 seconds . It is a xed 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 ag 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 Speci cation
2.2.1 Application Name and Argument
The server application MUST be compiled into a binary called server , accepting one command-line argu-ment:
$ ./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 speci ed 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 speci ed port number.
When server is running, it should be able to accept multiple clients’ connection requests. It is guar-anteed 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 les transmitted over the established connection and name them following the order of each established connection at current directory, as hCONNECTION ORDERi. le . For example, 1. le , 2. le , etc. for the le received in the rst connection, in the second connection, and so on.
The server should be able to accept and save les, where each le’s size could be up to 10 MB .
2
UCLA CS 118 Project 2, Spring 2020
2.3 Client Application Speci cation
2.3.1 Application Name and Argument
The client application MUST be compiled into a binary called client , accepting three command-line argu-ments:
$ ./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 le 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 test le :
$ ./client localhost 5000 testfile
You can assume that the speci ed inputs are always correct.
2.3.2 Requirements
The client must open a UDP socket and initiate 3-way handshake to the speci ed hostname/IP and port.
{ Send UDP packet with SYN ag 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 ags set.
{ Send UDP packet with ACK ag including the rst of the speci ed le. If the le is larger than 512 bytes, this packet should has exactly 512 bytes in the data eld.
Client should send le in pipeling scheme with a xed 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 le is successfully transferred (all bytes acknowledged), the client should gracefully terminate the connection following these steps:
{ Send UDP packet with FIN ag set.
{ Expect a packet with ACK ag and another packet FIN ag.
{ 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 les 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 les 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 cor-ruption 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 le 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 ex-amples 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 di er on your laptop, you can gure it out by command ifcon g ):
tc qdisc show dev lo0
2. If network emulation has not yet been setup or have been deleted, you can add a con guration 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 re-transmits 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 dis-carded.
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 de ned. 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). Unde ned value should be 0. For example, in the rst 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 ag is set: [SYN]
{ If FIN ag 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 rst 10 packets of the le.
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
...
• 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 elds 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 le (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 le transmission and pipe-lining. This means you must divide the le into multiple packets and transmit the packets based on the speci ed 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 le transmission.
The credit of your project is distributed among the required functions. If you only nish part of the requirements, we still give you partial credit. So please do the project incrementally.
• 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 les into a directory, compress the directory and generate a UID.tar.gz where UID is your UCLA ID. Your submission should include the following les:
Your source codes (e.g. server.c, client.c). The code of the server and the client can be several les. A Make le. The TAs will only type make to compile your code.
A README le 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 les and scripts: TA will release testing les and scripts after the due data. So as the details of demo. You need to download the testing les 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 le from the client side to the server side. Your program should print out operations according to the de ned 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 di erent values for tc command to test your program. TAs will ask you to compare the received les with the sent ones using the Linux program di .
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
