MP2: Remote File Transfer README -------------------------------------------------------------------------------- Part 1: Implementation Log --Message Formats There are 5 types of messages (or packets). The first byte in all the packets indicates the packet type. Type 1: Send Request [from client to server] This packet includes only the filename. It has two fields - the packet type (1 byte) and the filename (256 bytes atmost). Since the send request is received using recvfrom rather than mp2_recvfrom, it does not suffer any errors. Format: byte 0: Packet type (0x00) bytes 1 to 256 atmost: File name terminated by \0. Type 2: Acknowledgement for a valid send request [from server to client] This packet mainly has the file length in bytes and the length of data packets transmitted later which has to be less than 256 bytes (the server calls mp2_get_mss to determine the recommended packet size). Format: byte 0: Packet type (0x07) bytes 1 to 4: File length byte 5: Length of the data packet bytes 6 to 10: 2D parity (over rows and columns) Type 3: Error messages [from server to client] This packet will contain error numbers corresponding to errors that might take place like "file does not exist" or "bad request message received". So, it has three fields - the packet type (1 byte), the error number (1 byte) and 2-D parity bits. Again, 2-D parity is used instead of CRC-8 because the beginning of a transaction uses 2-D parity and then we switch to CRC-8 if corruption is below a threshold. Format: byte 0: Packet type (0x38) byte 1: Error code bytes 2 to 6: 2D parity (over rows and columns) Type 4: Data packet [from server to client] The following fields are used: packet type (1 byte), the sequence number of the send window (2 bytes), the data and then the CRC-8 remainder or the 2-D parity bits (whichever is used). The client knows the length of the packet because the acknowledgement to the send request (packet type 2) contains the length of the data packet. The size of the data within this packet depends on whether 2-D parity error correction or CRC-8 error detection is being used. If 2-D parity is used, then the actual data is less, if CRC-8 is used, the actual data is more. The packet type will be used to determine if 2-D parity or CRC-8 is being used. Type 5: Acknowledgement of data packet [from client to server] The following fields are present: packet type (1 byte), sequence number of packet being acknowledged and the CRC-8 polynomial or the 2-D parity bits. The packet type will be used to determine if 2-D parity or CRC-8 is being used. We use the following message types: Packet Packet type field (1 byte) in binary ---------------------------------------------------------------------------------- Send Request 00000000 Acknowledgement for valid send request 00000111 Error messages 00111000 Data packet with CRC-8 00111111 Data packet with 2-D parity 01001001 Acknowledgement packet with CRC-8 01010010 Acknowledgement packet with 2-D parity 10100100 The minimum distance of the above packet type field is 3. Hence, if a single bit error occurs, we can correct it. This is important because if the packet type is in error and the above packet types are not used, then the receiver may read the incorrect number of bytes, hence screwing up the framing. Since only single bit errors occur on the network, distance 3 will suffice for correction. --Sliding Window Data Structures: The following is an excerpt from our program: /* Sender window data structure */ typedef struct _SenderWindow { unsigned char *packet[SWS]; int packetSize[SWS]; unsigned int LAR; unsigned int LFS; struct timeval sentTime[SWS]; unsigned char acked[SWS]; unsigned char sent[SWS]; unsigned char resent[SWS]; } senderWindowRec, *senderWindowPtr; /* Receiver window data structure */ typedef struct _ReceiverWindow { unsigned char *packet[RWS]; int packetSize[RWS]; unsigned int NFE; unsigned char received[RWS]; } receiverWindowRec, *receiverWindowPtr; The fields are self explanatory. --Calculation of 2D parity: To calculate the parity bits, we've used a table in which we place 4 bytes per row. Hence if there are L data bytes, there will be ceil(L/4) rows. There's 1 row parity bit for each row, 4 parity bytes for columns and an additional 1 bit of parity for the right hand bottom corner. So, the number of parity bytes required is: 4 + ceil((L + 1)/4) Using this formula, we calculate the total number of parity bytes required given the data bytes and vice-versa. -------------------------------------------------------------------------------- Part 2: Experimental Results After much experimentation, we used the following parameters in our sliding window: --Window sizes: SWS = RWS = 200 MaxSeqNum = (SWS + RWS) = 400 Therefore, the sequence numbers are from 0 to 399. We used a 16-bit sequence number space to allow for flexibility. The maximum re-order was found to be about 10, so there was no question of wrap-arounds in the window. --Switching from 2D parity to CRC: We start off transmitting all data frames and acks using 2 D parity. Error messages and file length frames are always transmitted using 2D parity. If the network does not corrupt too many packets, then we switch to CRC. We switch when the percentage of error-free packets is greater than 80% (but only if the number of frames transmitted is greater than 50). --Timeout value calculation: We found the following RTT's for the different adversaries: No adversary 38 ms Adv #2 28 ms Adv #3 12 ms Adv #4 21 ms Adv #5 176 ms These round trip times include the transmission time of the data packet, the transmission time of the ack, the propagation delays in either direction and the processing time involved in the sliding window. Since these RTT's vary so much, it was required to dynamically adapt the timeout values for the different adversaries. We calculated the average RTT's for the first 200 or so packets and then assigned 3 times of the average RTT to timeout. Initially timeout was set to 150 ms. --Terminating the server if the last ack is lost If the client has received all the data packets and dispatched all the acks, it terminates. But the acks may be lost and hence the server goes into an infinite loop, waiting for acks. To avoid this condition, we keep track of the time at which the last ack arrived. If the time elapsed from the last ack is greater than 10s, then we terminate the server. Instead of checking for this every time through the loop (which decreases performance), we check this every 200th time through the loop. --PERFORMANCE We checked our performance compared to the benchmark solutions when the machines were busy. Hence we got the following results (averaged over 3 runs almost at the same time and running on the same machines): ADVERSARY TIME FOR OUR CODE TIME FOR BENCHMARK CODE ------------------------------------------------------------------------------- No adversary 5.70 s 6.32 s Adversary 2 8.01 s 6.81 s Adversary 3 33.44 s 11.85 s Adversary 4 19.90 s 9.53 s Adversary 5 72.00 s 31.47 s ------------------------------------------------------------------------------- --Properties of adversaries: (Referred to post by David Warden on the newsgroup named "Adversary specifications") No Adversary: No loss, reorder or error takes place. Adversary 2: No loss or reorders occur. However approximarely 88% of the packets suffer 1 bit errors. Adversary 3: About 10% of the frames get lost, 9% are in error (1 bit). Adversary 4: Approximately 25% of the messages were lost, frames get delayed and the maximum reorder is that of 7 packets. Adversary 5: 70% of the packets get lost, 1.55% are in error and delays of upto 190 ms are inserted. --Handling loss of packets: The sliding window protocol makes sure that every packet is acked. So if pkts are lost, the ack is not received and timeouts occur, so the packet is retransmitted. We had to be very careful in setting the timeout value. The procedure is described above. --Handling bit errors in packets: We use 2D parity to correct errors and CRC to detect errors. Since we're assured that only single bit errors, 2D is adequate to correct bit errors. If CRC detects a bit error, the client drops the packet and hence the server does not receive the ack. Therefore, it retransmits the packet. It continues doing this till the packet is received without any error. For adversaries 1, 3, 4 and 5, it was adequate to use CRC rather than 2D parity because the % of errors is small. So we dynamically switched to CRC for adv 1, 3, 4 and 5. But for adv 2, we don't switch because the % of errors is very high. --Handling re-orders: If the packet received is in the receiver window but not the first one in the receiver window, it is buffered but not written to the file. Since the maximum re-order is over 7 sequence numbers and the receiver window size is 200, re-orders do not cause any problems. --Handling delays: As can be seen by the table of RTT's for the different adversaries, the delays are quite variable. So again, the timeout has to be adjusted such that packets that are delayed do not time out, but the server does not have to wait too long before it can retransmit once it has sent all the packets in its sender window atleast once.