COSD Lab 1 - Reliable Data Transport Protocol Solution

Assignment overview:
In this assignment, you will be implementing the sending and receiving side of a reliable data transport (RDT) protocol. Your protocol should achieve error-free, loss- free, and in-order data delivery on top of a link medium that can lose, reorder, and corrupt packets. Your implementation can follow any variation of the sliding window protocol, e.g., Go-Back-N, Selective Repeat, or the TCP rdt protocol. Since we don't have machines with OS that we can modify, your implementation will run in a simulated environment. This simulated environment is carefully constructed to follow the behavior of real systems. This also means that your program should be written in the same programming language as the simulator -- C/C++.

The unit of data passed between the upper layer and the RDT layer is the message, which is declared as:
struct message { int size; char *data;
};
1
2
3
4 message.size indicates the size of message.data measured in bytes. The reliable
data transport protocol requires the data in the receiving node being delivered in order. It does not, however, require the preservation of message boundaries. The unit of data passed between the RDT layer and the lower layer is the packet, which is declared as:
#define RDT_PKTSIZE 128 struct packet {
char data[RDT_PKTSIZE];
};
1
2
3
4
The routines you need to implement :
The routines you need to implement are detailed below. Such routines in real-life would be part of the operating system.
 void Sender_Init(); - sender initialization, called once at the very beginning. This routine is here to help you. Leave it blank if you don't need it.
 Sender_Final(); - sender finalization, called once at the very end. This routine is here to help you. Leave it blank if you don't need it.
 void Sender_FromUpperLayer(struct message*); - called when a message is passed from the upper layer at the sender.
 void Sender_FromLowerLayer(struct packet*); - called when a packet is passed from the lower layer at the sender.
 void Sender_Timeout(); - called when the timer expires at the sender.
 void Receiver_Init(); - receiver initialization, called once at the very beginning. This routine is here to help you. Leave it blank if you don't need it.
 void Receiver_Final(); - receiver finalization, called once at the very end. This routine is here to help you. Leave it blank if you don't need it.
 void Receiver_FromLowerLayer(struct packet *pkt); - called when a packet is passed from the lower layer at the receiver.
The routines you can call (implemented by the simulated environment):
The routines you can call (implemented by the simulated environment) are detailed below. Such routines in real-life would also be part of the operating system.
 void Sender_StartTimer(double timeout); - start the sender timer with a specified timeout (in seconds). This timer is canceled when Sender_StopTimer() is called or a new Sender_StartTimer() is called before the current timer expires.
Sender_Timeout() will be called when the timer expires.
 void Sender_StopTimer(); - stop the sender timer.
 bool Sender_isTimerSet(); - check whether the sender timer is being set, return true if the timer is set, return false otherwise.
 void Sender_ToLowerLayer(struct packet*); - pass a packet to the lower layer at the sender for delivery.
 void Receiver_ToLowerLayer(struct packet*); - pass a packet to the lower layer at the receiver for delivery.
 void Receiver_ToUpperLayer(struct message*); - deliver a message to the upper layer at the receiver.
The simulated network environment:
The overall structure of the environment is shown in the above figure. There is one and only one timer available at the sender. The underlying link medium can lose, reorder, and corrupt packets. The default one-way latency for this link is 100ms when the link does not reorder the packets. After you compile your code and my code together and run the resulting program, you will be asked to specify the following parameters for the simulation environment.
 sim_time - total simulation time, the simulation will end at this time (in seconds).
 mean_msg_arrivalint - average intervals between consecutive messages passed from the upper layer at the sender (in seconds). The actual interval varies between zero and twice the average.
 mean_msg_size - average size of messages (in bytes). The actual size varies between one and twice the average.
 outoforder_rate - the probability that a packet is not delivered with the normal latency - 100ms. A value of 0.1 means that one in ten packets are not delivered with the normal latency. When this occurs, the latency varies between zero and 200ms.
 loss_rate - packet loss probability: a value of 0.1 means that one in ten packets are lost on average.
 corrupt_rate - packet corruption probability: a value of 0.1 means that one in ten packets (excluding those lost) are corrupted on average. Note that any part of a packet can be corrupted.
 tracing_level - levels of trace printouts (higher level always prints out more information): a tracing level of 0 turns off all traces, a tracing level of 1 turns on regular traces, a tracing level of 2 prints out the delivered message. Most likely you want to use level 1 for debugging and use level 0 for final testing.
Helpful hints:
 Timer - There is only one physical timer available at the sender. In some cases you might want to keep multiple timers simultaneously. You can simulate multiple virtual timers using a single physical timer. The basic idea is that you keep a chain of virtual timers ordered in their expiration time and the physical timer will go off at the first virtual timer expiration.
 Error detection and checksumming - You will need some kind of checksumming to detect errors. The Internet checksum is a good candidate here. Remember that no checksumming can detect all errors but your checksum should have sufficient number of bits (e.g. 16 bit in Internet checksum) to make undetected errors very rare. We can not guarantee completely error-free delivery because of checksumming's limitation. But you should be convinced that this should happen very rarely with a good checksumming technique.
 Packet format - A key part of your design is the packet format. The packet will be split into a header part and a payload part. Some common header fields include payload size, sequence number, acknowledgment sequence number, and the checksum.

Source code of the simulator:

You are re co mmende d to prep are a LINUX environ ment. either virtual machine or Linux host is okay.
Handin procedure:
Testing:
 rdt_sim 1000 0.1 100 0 0 0 0 - there is no packet loss, corruption, or reordering in the underlying link medium.
 rdt_sim 1000 0.1 100 0.02 0 0 0 - there is no packet loss or corruption, but there is reordering in the underlying link medium.
 rdt_sim 1000 0.1 100 0 0.02 0 0 - there is no packet corruption or reordering, but there is packet loss in the underlying link medium.
 rdt_sim 1000 0.1 100 0 0 0.02 0 - there is no packet loss or reordering, but there is packet corruption in the underlying link medium.
 rdt_sim 1000 0.1 100 0.02 0.02 0.02 0 - there could be packet loss, corruption, or reordering in the underlying link medium.
Reference Value:
 rdt_sim 1000 0.1 100 0.15 0.15 0.15 0
#GBN
## Simulation completed at time 3206.00s with
981689 characters sent
981689 characters delivered
86390 packets passed between the sender and the receiver
## Congratulations! This session is error-free, loss-free, and in order.
#SR
## Simulation completed at time 1656.02s with
983959 characters sent
983959 characters delivered
1
2
3
4
5
6
78
9
10
11
38066 packets passed between the sender and the receiver
## Congratulations! This session is error-free, loss-free, and in order.
12
13
 rdt_sim 1000 0.1 100 0.3 0.3 0.3 0
##GBN
## Simulation completed at time 7019.09s with
1010200 characters sent
1010200 characters delivered
153855 packets passed between the sender and the receiver
## Congratulations! This session is error-free, loss-free, and in order.
#SR
## Simulation completed at time 4321.40s with
984465 characters sent
984465 characters delivered
59417 packets passed between the sender and the receiver
## Congratulations! This session is error-free, loss-free, and in order.
1
2
3
4
5
6
78
9
10
11
12
13
Grading:
 60% for correctness, including error-free, loss-free, and in-order delivery of your RDT implementation. That is to say, as long as you fulfill the correctness requirements, you will get the majority of the credits.
 20% for efficiency. There are two aspects of efficiency. The primary efficiency metric is measured by the number of packets your implementation needs to pass between the sender and receiver for each particular data transfer session. The secondary efficiency metric is the transmission throughput --- the maximum amount of data that can be successfully transmitted within a time frame. We are mostly interested in the primary efficiency metric. We bring up the secondary metric to guard against a Stop-and-Wait protocol (which does not pass too many packets to complete a data transfer session, thus has very low throughput). You can compare your efficiency with the referenced value. A reasonable implementation of either GoBack-N or Selective Repeat should get you full credits on the efficiency.
 20% for your document. You should describe your design and implementation strategies in detail. You can also describe the problem you meet and the solution you use to solve that problem.