$29
Programming Assignment 2: Digital Music Manager & Doubly Linked Lists – Part I Solution
• Overview
The purpose of this project is to implement a basic version of reliable data transfer protocol, including connection management and congestion control. 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. We made several simpli cations to the real TCP protocol and its congestion control, 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.
All implementations will 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. We will also accept implementations written in C. You are encouraged to use a version control system (i.e. Git/SVN) to track the progress of your work.
• 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, and a basic version of congestion control.
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 will at least need a Sequence Number eld, an Acknowledgment Number eld, and ACK , SYN , and FIN ags.
1
UCLA CS 118 Project 2, Spring 2019
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 and appropriate congestion control actions 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 you have an ACK eld, Acknowledgment Number should be set to 0 if ACK is not set.
FIN should take logically 1 byte of the data stream (same as in TCP, see examples). FIN and FIN-ACK packets must not carry any payload.
You do not need to implement checksum and/or its veri cation in the header.
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). 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.
The server should gracefully process incorrect port number and exit with a non-zero error code. In addition to exiting, the server must print out on standard error ( std::cerr ) an error message that starts with ERROR: string.
Once the server receives correct port number, it will remain running forever. The only condition that it exits is upon receiving SIGQUIT / SIGTERM signal. It should exit with code 0 .
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.
2
UCLA CS 118 Project 2, Spring 2019
The server should be able to accept and save les, where each le’s size could be up to 100 MB . Handling edge cases when receiving les:
1. If the server is gracefully terminated (because of receiving SIGQUIT / SIGTERM signal) during an established client connection, write only INTERRUPT in the corresponding le. For example,
the server should create a 2. le containing only INTERRUPT string if the server was terminated while having a connection from Client2, while Client2 had transmitted some data already.
2. If the server establishes a connection but receives no data from the client after 10 seconds since the connection establishment, it should create an empty le according to the connection order (e.g. 1. le ) at current directory, and close this connection.
3. If the server establishes a connection but receives no data from the client after 10 seconds since
the last successful data packet transmit, it should save all the data received (e.g. into 1. le ) at current directory, and close this connection.
See below for an example illustration of clients establishing connections and transmit les to the server.
Client1
Server
|
|
|
seq=12345, ack=0, SYN
|
| -------------------------------------
> |
|
seq=221, ack=12346, SYN, ACK
|
| <-------------------------------------
|
|
|
|
seq=12346, ack=222, ACK
|
| -------------------------------------
> |
|
(if no payload included)
|
|
|
...
10 seconds waiting
...
|
|
| FIN procedures to close connection
|
| <------------------------------------
> |
|
(saves an empty 1.file)
|
|
|
close
|
connection
|
Client2
|
|
|
seq=5345, ack=0, SYN
|
| <----------------------------------
|
|
seq=4321, ack=5346, SYN, ACK
|
| ----------------------------------
> |
|
|
|
seq=5346, ack=4322, ACK
|
| <----------------------------------
|
|
(if includes 512-byte payload)
|
|
|
|
seq=4322, ack=5858, ACK
|
| ----------------------------------
> |
...
...
|
seq=5858, ack=0
|
| <----------------------------------
|
|
seq=4322, ack=5370, ACK
|
| ----------------------------------
> |
...
...
|
|
3
UCLA CS 118 Project 2, Spring 2019
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.txt :
$ ./client localhost 5000 test.txt
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 part of the speci ed le.
The client should gracefully process incorrect hostname and port number and exist with a non-zero exit code (you can assume that the speci ed le is always correct). In addition to exiting, the client must print out on standard error ( std::cerr ) an error message that starts with ERROR: string.
Client should support transfer of les that are up to 100 MB .
Whenever client receives no packets from server for more than 10 seconds , it should abort the con-nection (close socket and exit with non-zero code).
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 packet with ACK ag.
{ Wait for 2 seconds for incoming packet(s) with FIN ag.
{ During the wait, respond to each incoming FIN with an ACK packet; drop any other non- FIN packet.
{ Close connection and terminate with code 0 .
See below diagram for an example illustration.
4
UCLA CS 118 Project 2, Spring 2019
Client
Server
|
|
...
...
|
(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.4 Congestion Control Requirements
Client and server are required to implement TCP congestion window maintenance logic following RFC5681. The congestion control will be mostly done at the client, since the client sends data to the server. TCP Slow Start and Congestion Avoidance are mandatory to implement in this project. Fast Recovery/Fast Retransmit with 3rd-duplicate ACK loss detection is left as optional part with bonus. You may nd an electronic version of RFC5681 posted on CCLE or at https://tools.ietf.org/html/rfc5681.
2.4.1 Mandatory: Slow Start and Congestion Avoidance
You should read the Slow Start and Congestion Avoidance description speci ed in Section 3.1 of RFC5681.
We made some simpli cations to the RFC and use our own parameters, see summary below.
Initial and minimum congestion window size ( cwnd ) should be 512 . The maximum congestion window size ( cwnd ) should be 10240 .
Initial slow-start threshold ( ssthresh ) should be 5120 .
After connection is established, the client should send up to the initial cwnd = 512 bytes of data without starting the wait for acknowledgments.
After each ACK is received:
5
UCLA CS 118 Project 2, Spring 2019
(Slow Start) If cwnd < ssthresh : cwnd += 512
(Congestion Avoidance) If cwnd ssthresh : cwnd += (512 * 512) / cwnd
After timeout, set ssthresh := max (cwnd / 2, 1024) , set cwnd := 512 , and retransmit data after the last acknowledged byte. After retransmission, Slow Start is performed.
For each valid packet of the connection (except packets with only ACK ag and empty payload), the server responds with an ACK packet, which includes the next expected in-sequence byte to receive (cumulative acknowledgment).
2.4.2 Optional: Fast Retransmit/Fast Recovery (Extra Credit)
It is optional to implement TCP Tahoe (with Fast Retransmit) or TCP Reno (with Fast Retransmit/Fast Recovery). If you implement only Fast Retransmit, you can get up to 5% extra credits of this project. If you also implement Fast Retransmit/Fast Recovery, you can get up to 10% extra credits. For details of Fast Retransmit/Fast Recovery, you can refer to descriptions speci ed in Section 3.2 of RFC5681. We made some simpli cations to the RFC and use our own parameters, see summary below.
(Fast Retransmit) After receiving 3 duplicate ACKs in a row, set ssthresh := max (cwnd / 2, 1024) , set cwnd := ssthresh + 1536 , and retransmit data after the last acknowledged byte. After retransmis-sion, set cwnd := ssthresh , and enter Congestion Avoidance.
(Fast Recovery) After receiving 3 duplicate ACKs in a row, set ssthresh := max (cwnd / 2, 1024) , set cwnd := ssthresh + 1536 , and retransmit data after the last acknowledged byte. Each time an-other duplicate ACK arrives, set cwnd += 512 . Then, send a new data segment if allowed by the
value of cwnd. Upon a new (i.e., non-duplicate) ACK, set cwnd := ssthresh , and enter Congestion Avoidance.
2.5 Error Handling: Loss
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.
1. To check the current parameters for a given network interface (e.g. eth0 ): tc qdisc show dev eth0
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 eth0 root netem loss 10%
6
UCLA CS 118 Project 2, Spring 2019
3. To change current parameters to loss rate of 20% and delay 100ms: tc qdisc change dev eth0 root netem loss 20% delay 100ms
4. To delete the network emulation:
tc qdisc del dev eth0 root
2.6 Common Printout Format Requirements
The following output MUST be written to standard output ( std::cout ) in the EXACT format de ned. If any other information needs to be shown, it MUST be written to standard error ( std::cerr )
Packet received:
RECV hSeqNumi hAckNumi hcwndi hssthreshi [ACK] [SYN] [FIN]
Packet sent:
SEND hSeqNumi hAckNumi hcwndi hssthreshi [ACK] [SYN] [FIN] [DUP]
Note the convention:
[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]
{ SYN, or SYN-ACK packet: [SYN]
{ FIN, or FIN-ACK packet: [FIN]
{ Duplicate ACK packet: [DUP]
hyyi means that value of yy variable should appear on the output (in decimal). Note, since the server does not need to implement congestion control, you should print 0 0 for hcwndi hssthreshi elds.
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.
• 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. Just have the client send a packet, and the server respond with an ACK, and so on.
Second, introduce a large le transmission. This means you must divide the le into multiple packets and transmit the packets based on the current window size.
Third, introduce packet loss. Now you have to add a timer on each sent and un-ACKed packet. 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.
7
UCLA CS 118 Project 2, Spring 2019
• Due Date and Demo
4.1 Project Due
This project is due June 7th, 2019 at 23:59 PT. You will submit an electronic copy of the project on CCLE before due. See the Project Submission section for details on submission requirements. After submission, you are required to demo your program on 6/11 and 6/12 (tentative schedule).
4.2 Demo Requirements
1. Sign up for demo: TA will distribute the demo sign-up sheet in Week 8.
2. Preparing for the demo: You need to prepare at least 3 slides to present. One slide for your design and considerations, one slide for experiences you gained,and one slide for lesson learn from project and suggestions.
3. Demo day:
Demo time is 15 minutes for each group.
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. 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 will also ask you to walk through the slides. 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.
• Project Submission
NOTE: Late submission is not allowed, WITHOUT EXCEPTION.
1. Put all your les into a directory called project2 UID1 UID2 , where UIDs are your UCLA ID numbers.
Compress the directory and submit a project2 UID1 UID2.zip to CCLE course website before the deadline.
2. The project2 UID1 UID2.zip should contain the following les:
Source codes (can be multiple les);
A Make le ; TAs will only type make to compile your code, make sure your Make le works on Linux system.
README le that includes your group information. The README should contain: { Students name, and UID.
{ Brief description about how you divide the workload.
A PDF format report le (.pdf) no more than 5 pages. The report should contain:
{ Student names and UIDs at the very beginning (2 students per-group).
{ Implementation description (header format, messages, timeouts, window-based protocol etc). { Di culties that you faced and how you solved them.
3. The rst person in each group (according to the group sign-up sheet) submits the project les to CCLE.
8
