Programming Assignment 2 (P2): Reliable Datagram Protocol (RDP) Solution

1    Introduction

    7 So far, you have implemented a Simple Web Server following the Hyper Text Transfer Protocol

    8 (HTTP) in the first programming assignment (P1).  Good job!  But very soon you have found

    9 that the simple web server is not always working reliably, due to the fact that it just relies on the

    10 unreliable User Datagram Protocol (UDP). For example, if the HTTP request or response messages

    11 are larger than what a normal UDP packet can accommodate, multiple UDP packets have to be

    12 sent over the network. These packets may get lost, duplicated, reordered or corrupted along the

    13 way, and neither the sender nor the receiver has the capability to recover them. In addition, a fast

    14 sender can send packets much faster than how much the receiver can handle and may potentially

    15 overflow the receiver’s buffer and cause packet loss, even if the packets have arrived at the receiver.

    16 Further, the sender should be able to indicate to the receiver the end of the request or response

    17 messages, so the receiver does not need to wait any further for more packets.

    18 Therefore, you need to add some flow control and error control capabilities, as well as the start

    19 and finish indicators, to UDP, leading to a “new” protocol that we call CSC361 “Reliable Datagram
    20 Protocol” or RDP 1. In this programming assignment, you will complete the design of the CSC361

    21 RDP protocol and implement it using the datagram (DGRAM) socket Application Programming

    22 Interface (API) with UDP. The goal is to transfer a text file from a sender to a receiver through

    23 the Linksys router in ECS360 that emulates various network impairments such as packet loss,

    24 duplication, reordering and corruption in a real network.

    25 In this assignment, only the assignment requirements and basic design are provided, and you

    26 have the freedom to create your own detailed design and implement it. Be creative, but you should

    27 be able to justify your own design choices.


    28 2  Schedule

    29 In order to help you finish the assignment on time successfully, the schedule of this assignment has

    30 been synchronized with both the lectures and the lab and tutorial modules. There are five tutorial

    31 modules arranged in the weekly lab sessions during the course of this assignment, and it is very

    32 important that you follow the schedule very closely for your assignment.


1BTW, Google has a similar but of course more sophisticated approach called QUIC ;-)




1

Date
Lab Lecture and Tutorial Tasks
Milestones





Feb 20/21/22/23
P2 Spec, RDP header, Connection Mgmt (CM)
RDP header done



Feb 27/28/Mar 1/2
Flow Control (FC) and Error Control (EC)
CM done, FC half-way



Mar 6/7/8/9
network impairments and NAT
FC done, first due; EC half-way



Mar 13/14/15/16
feedback, debug and test
CM, FC and EC all done



Mar 20/21/22/23
demo
all done and tested; second due




33    3    Requirements

34

35

36


37

38

39


40

41

42

3.1    Reliable Datagram Protocol (RDP)

    1. RDP should be able to transfer a file of any size from a sender to a receiver, through a router.

    2. The received file should be identical to the sent file in content.

        ◦ Hint: how do you know two files are identical in content? You can compare them bit-to-bit for sure. But for a quick check, you can use md5sum to know that two files of the same size are actually different.

    3. Maximal RDP packet size (including RDP packet header and data payload): 1,024 bytes.

    4. RDP packet header has a similar design as HTTP request or response header fields in ASCII string coding. The minimal set of the supported RDP packet header fields are:

RDP header field

Possible value
Meaning




















































Magic:



magic












CSC361
CSC361 RDP protocol









































Type:

type













DAT
Data packet











































ACK
Acknowledgment packet

























SYN
Synchronization packet

























FIN
Finish packet

























RST
Reset packet



















Sequence:




seqno








e.g., 0
byte sequence number































Acknowledgment:

ackno



e.g., 900
byte acknowledgment number




















Payload:


length



e.g., 900
RDP payload length in bytes



















Window:



size



e.g., 10240
RDP window size in bytes














(an empty line)


the end of the RDP header





























43

44

45

46

47

48

49

50


    • Magic:  CSC361: indicating the RDP protocol used in the CSC 361 Lab at UVic.

    • Type:   type : identifying the type of the packet, i.e.,

– DAT: Data packet, sent by the sender and carries data payload (i.e., Payload is greater than zero for the same packet).

– ACK: Acknowledgment packet, sent by the receiver to acknowledge the reception of DAT, SYN or FIN packets.

– SYN: Synchronization packet, sent by the sender to initiate the data transfer.

– FIN: Finish packet, sent by the sender to finish the data transfer.




2

51

– RST: Reset packet, sent by either the sender or the receiver to terminate the current
52

data transfer due to unrecoverable errors.
53

– You may be able to define more types of packets in your extended design.
54
• Sequence or Acknowledgment: integer, byte sequence or acknowledgment number (i.e.,
55

x+1 represents the byte immediately after the byte represented by x in the data stream).
56

Initial sequence number is chosen by the sender randomly.










57

– For packets such as DAT, SYN and FIN sent by the sender, it represents the sequence
58

number of the first byte of the data payload, the initial sequence number, and the
59

finish sequence number, respectively.
60

– For packets such as ACK sent by the receiver, it represents the sequence number of
61

the next byte expected at the receiver, i.e., acknowledgment number.
62
• Payload or Window: integer, byte payload length or window size (i.e., x represents X data
63

bytes).







64

– For packets such as DAT, it indicates the length of the data payload in the packet.
65

– For packets such as ACK, it represents the window size (i.e., the extra amount of
66

data can be accommodated by the receiver).
67
• You may be able to define more packet header fields in your extended design.
68
5. Packets may be dropped, duplicated, reordered and corrupted by the network and the router.
69
• Hint: you will need error control procedures, including error detection, error notification
70

and error recovery, in your design.
71
6. For performance concerns, RDP cannot use the stop-and-wait strategy.
72
• Hint: you will need some flow control procedures in your design.
73
• Hint: you do not need to implement a full set of TCP protocol mechanisms over UDP, but
74

you can use TCP to help formulate your design. Note that unlike TCP with bidirectional





75

data flows, there is only one single data flow from the sender to receiver.

76
For self-testing purposes, your RDP implementation should correctly transfer a file of minimal
77
size 1 MB through the Linksys router in the lab, and the packet error rate can go as high as 10%
78
(BTW, normally TCP suffers greatly or even fails with a 10% packet error rate).

79    3.2    RDP Sender

80    Your RDP sender should have the following command line syntax:

81    rdps sender_ip sender_port receiver_ip receiver_port sender_file_name

82    sender ip and sender port specify the IP address and UDP port number the sender will use;

83    receiver ip and receiver port specify the location of the receiver; sender file name specifies

84    the location of the file at the sender to be sent to the receiver through the router.

85    While transferring the file, your RDP sender should print to screen the log message on sending/receiving

86    each packet, i.e., not just data packets, with the following format:


3
    87 HH:MM:SS.us event_type sip:spt dip:dpt packet_type seqno/ackno length/window

    88 • HH:MM:SS.us:  represents the time instance in Hour:Minute:Second.microsecond format

    89 sending or receiving a packet, e.g., 23:59:59.999999 means 1 microsecond before midnight.

    90 • event type: represents the type of events, i.e.,


91

92

93

94

– s: send a packet for the first time

– S: resend the packet

– r: receive a packet

– R: receive the same packet again

    95 • sip:spt dip:dpt: are source/destination IP address and UDP port number of the packet.

    96 • packet type: represents the type of the packet, i.e, DAT, ACK, SYN, FIN, or RST.

    97 • seqno/ackno: sequence number or acknowledgment number.

    98 • length/window: payload length or window size.

    99 After the file transfer is finished, your RDP sender should print to screen the summary message

    100 following the example below

    101 total data bytes sent: 1165152

    102 unique data bytes sent: 1048576

    103 total data packets sent: 1166

    104 unique data packets sent: 1049

    105 SYN packets sent: 1

    106 FIN packets sent: 1

    107 RST packets sent: 0

    108 ACK packets received: 1051

    109 RST packets received: 0

    110 total time duration (second): 0.093

    111 In this example, a file of 1 MB (1,048,576 bytes) is successfully transferred, which corresponds

    112 to 1,049 unique data packets (1,048 packets of 1,000 bytes each in payload, and one packet of 576

    113 bytes). Due to packet errors, in total 1,165,152 data bytes are sent (1,164 packets of 1,000 bytes

    114 each in payload, and two packets of 576 bytes each), for a total time duration of 0.093 second from

    115 the ACK packet on the first SYN packet to the ACK packet on the last FIN packet.

    116 3.3  RDP Receiver

    117 Your RDP receiver should have the following command line syntax:

    118 rdpr receiver_ip receiver_port receiver_file_name

    119 receiver file name specifies the location at the receiver to store the received file.

    120 While receiving the file, your RDP receiver should print to screen the log message on receiving/sending

    121 each packet, i.e., not only data packets, with the following format:


SYN
SYN
SYN




ACK
ACK

DAT
DAT
timeout

resendDAT
(a)
ACK







SYN
FIN
resendDAT



RST
ACK



RST



(b)
(c)
(d)


Figure 1: RDP protocol interaction examples.



    122 HH:MM:SS.us event_type sip:spt dip:dpt packet_type seqno/ackno length/window

    123 After the file transfer is finished, your RDP receiver should print to screen the summary message

    124 with the following format

    125 total data bytes received:

    126 unique data bytes received:

    127 total data packets received:

    128 unique data packets received:

    129 SYN packets received:

    130 FIN packets received:

    131 RST packets received:

    132 ACK packets sent:

    133 RST packets sent:

    134 total time duration (second):

    135 Figure 1 shows some RDP protocol interaction examples. They are not exhaustive.

    136 For self-testing purposes, you first run your RDP receiver on the “WAN” interface (10.10.1.100)

    137 and port 8080 of your lab computer,

    138 ./rdpr 10.10.1.100 8080 received.dat

    139 and then run your RDP sender on the “LAN” interface (192.168.1.100) and port 8080 of your
    140 lab computer to send the sent.dat file.

    141 ./rdps 192.168.1.100 8080 10.10.1.100 8080 sent.dat








5
PC




rdps
rdpr
rdpr





Router
1
rdps


2


LAN  WAN

eth2  eth1  eth0
1

3







4


4


3




PC
Router    PC






2



    1. 192.168.1.100:8080 −> 10.10.1.100:8080

    2. 10.10.1.1:9876 −> 10.10.1.100:8080

    3. 10.10.1.100:8080 −> 10.10.1.1:9876

    4. 10.10.1.100:8080 −> 192.168.1.100:8080

Figure 2: Network configuration in the lab.


142    4    Network Emulation

    143 Figure 2 shows the network configuration in the lab for this assignment, where your rdps and rdpr

    144 are running on the PC and using eth0 and eth1, respectively. eth0 and eth1 are connected to the

    145 LAN and WAN port of the Linksys WRT54GL router, respectively.

    146 Figure 2 also shows the sample packets appearing on the eth0 and eth1 interface and sent/received

    147 by rdps and rdpr, respectively, for the SYN-ACK interaction. You may notice that the source IP

    148 address and port number have been changed from packet 1 to packet 2 when it travels through

    149 the router.  This is due to the Network Address Translation (NAT). However, the NAT process

    150 should be transparent to your RDP sender and receiver, and your rdpr will extract the translated
    151 IP address and port number for your rdps from the incoming packets and respond accordingly.

    152 The Linksys WRT54GL router in the lab has been specially instrumented to emulate a wide-area

    153 network with packet delay, loss, duplication, corruption and reordering. You will be given detailed

    154 instruction to set these network impairments in lab. For reference, see [1].

    155 In order for your packets to go through the router, the computer in the lab has been specially

    156 instrumented to forward packets with the “LAN” interface source IP address (192.168.1.100) and

    157 the “WAN” interface destination IP address (10.10.1.100) through the router, when you bind the
    158 socket of your rdps to source IP address (192.168.1.100).


    159 5  Submission

    160 The entire programming assignment, including the code and documentation, should be submitted

    161 electrically through http://connex.csc.uvic.ca on or before the due dates in two stages. The

    162 site will start to accept submissions one week before the due date.

    163 For P2, to help you finish smoothly and successfully, we have a two-stage submission process.

    164 Design and code with connection management (SYN-ACK and FIN-ACK interaction) and flow

    165 control (sliding window) capabilities will be due by March 10, 2017 as p2a, and the updated design

    166 with connection management and flow and error control capabilities will be due by March 24, 2017
    167 as p2b.

    168 Only the source code (including header files and Makefile) and documentation (including Readme)

    169 should be included in a single tar.gz file to be submitted. No object or binary files are included

    170 in the submission. If directory is your project directory, to create such a gzipped tarball, you can

    171 cd directory

    172 tar -zcvf p2a.tar.gz .

    173 for p2a and similarly for p2b.

    174 This packing and naming convention should be strictly followed to allow your submission to be

    175 properly located for grading.
    176 In directory, you need to include a Makefile, which compiles and builds the final binary
    177 executable (rdps and rdpr) automatically by typing

    178 make

    179 The same Makefile also removes all object and binary files when you type in

    180 make clean

    181 All assignments will be tested on n-greek.csc.uvic.ca

    182 In directory, you also need to include a Readme plain text file, which contains your student

    183 number, registered lab section and the description of your initial and final design in RDP flow and

    184 error control and code structure.

    185 The code itself should be sufficiently self-documented, which will not only help you build and

    186 maintain your code well but also assist the code demo and evaluation.

    187 IMPORTANT: All submitted work should be yours.  If you have used anything out there,

    188 even a small component in your implementation, you should credit and reference properly, and

    189 your contribution can be determined accordingly. For academic integrity policies, please see [2].


    190 6  Marking

    191 This programming assignment is worth 25% in the final grade of this course. p2a counts 5% and

    192 p2b counts 20%.  The lab instructor will also check the progress of your assignment during the

    193 weekly lab sessions.

    194 For mark posting and appeal policies, please see the official course outline at [2].


    195 References

    196 [1] http://www.linuxfoundation.org/collaborate/workgroups/networking/netem

    197 [2] https://heat.csc.uvic.ca/coview/outline/2017/Spring/CSC/361










7