Program #3 - Reliable Data Transport
In this program, you will put into practice the basic building blocks of reliable data transport: acknowledgements, checksums and timeouts.
Overview.
You will be writing the sending and receiving transport-level code for implementing a simple reliable data transfer protocol.
You will be using the alternating-bit-protocol (rdt3.0 from Chapter 3).
In this program, you will practice what we've learned about reliable data transport by implementing a simulated stop-and-wait sender and receiver.
This lab should be fun since your implementation will differ very little from what would be required in a real-world situation.
Your code will execute in a simulated hardware/software environment.
However, the programming interface provided to your routines, i.e. the code that would call your entities from above and from below is very close to what is done in an actual UNIX environment.
Stopping/starting of timers are also simulated, and timer interrupts will cause your timer handling routine to be activated.
The routines you will write.
The procedures you will write are for the sending entity (A) and the receiving entity (B).
Only unidirectional transfer of data (from A to B) is required.
Of course, the B side will have to send packets to A to acknowledge receipt of data.
Your routines are to be implemented in the form of the procedures described below.
These procedures will be called by (and will call) procedures that I have written which emulate a network environment.
Here is the overall structure of the environment:
The unit of data passed between the upper layers and your protocols is a message, which is declared as:
struct msg
{
char data[20];
};
This declaration, and all other data structure and emulator routines, as well as stub functions (which you need to complete) are in the C++ source file, rdt.cpp.
It is a command-line program, so you can use the operating system and development environment of your choice.
But I will be compiling it with g++ on katie and testing it there as well.
Your sending entity will thus receive data in 20-byte chunks from layer5.
Your receiving entity should deliver 20-byte chunks of correctly received data to layer5 at the receiving side.
The unit of data passed between your routines and the network layer is the packet, which is declared as:
struct pkt {
int seqnum;
int acknum;
int checksum;
char payload[20];
};
Your routines will fill in the payload field from the message data passed down from layer5.
The other packet fields will be used by your protocols to insure reliable delivery, as we've seen in class.
The routines you will write are detailed below.
As noted above, such procedures in real-life would be part of the operating system, and would be called by other procedures in the operating system.
- A_output(message), where message is a structure of type
msg, containing data to be sent to the B-side. This routine will be
called whenever the upper layer at the sending side (A) has a message to send.
It is the job of your protocol to insure that the data in such a message is
delivered in-order, and correctly, to the receiving side upper layer.
- A_input(packet), where packet is a structure of type
pkt. This routine will be called whenever a packet sent from the
B-side (i.e. as a result of a tolayer3() being done by a B-side
procedure) arrives at the A-side. packet is the (possibly corrupted)
packet sent from the B-side.
- A_timerinterrupt() This routine will be called when A's timer
expires (thus generating a timer interrupt). You'll probably want to use this
routine to control the retransmission of packets. See starttimer()
and stoptimer() below for how the timer is started and stopped.
- A_init() This routine will be called once, before any of your other
A-side routines are called. It can be used to do any required initialization.
- B_input(packet),where packet is a structure of type
pkt. This routine will be called whenever a packet sent from the
A-side (i.e. as a result of a tolayer3() being done by a A-side
procedure) arrives at the B-side. packet is the (possibly corrupted)
packet sent from the A-side.
- B_init() This routine will be called once, before any of your other
B-side routines are called. It can be used to do any required initialization.
Software Interfaces.
The procedures described above are the ones that you will write. I have
written the following routines which can be called by your routines:
- starttimer(calling_entity,increment), where calling_entity
is either 0 (for starting the A-side timer) or 1 (for starting the B side
timer), and increment is a float value indicating the amount
of time that will pass before the timer interrupts. A's timer should only be
started (or stopped) by A-side routines, and similarly for the B-side timer.
To give you an idea of the appropriate increment value to use: a packet sent
into the network takes an average of 5 time units to arrive at the other side
when there are no other messages in the medium.
I used a timeout value of 15.0 in my sample runs.
- stoptimer(calling_entity), where calling_entity is either
0 (for stopping the A-side timer) or 1 (for stopping the B side timer).
- tolayer3(calling_entity,packet), where calling_entity is
either 0 (for the A-side send) or 1 (for the B side send), and packet
is a structure of type pkt. Calling this routine will cause the
packet to be sent into the network, destined for the other entity.
- tolayer5(calling_entity,message), where calling_entity is
either 0 (for A-side delivery to layer 5) or 1 (for B-side delivery to layer
5), and message is a structure of type msg. With
unidirectional data transfer, you would only be calling this with
calling_entity equal to 1 (delivery to the B-side). Calling this
routine will cause data to be passed up to layer 5.
The simulated network environment.
A call to procedure tolayer3() sends packets into the medium (i.e.
into the network layer). Your procedures A_input() and
B_input() are called when a packet is to be delivered from the medium
to your protocol layer.
The medium is capable of corrupting and losing packets. It will not reorder
packets. When you compile your procedures and my procedures together and run the
resulting program, you will be asked to specify values regarding the simulated
network environment:
- Number of messages to simulate. My emulator (and your routines)
will stop as soon as this number of messages have been passed down from layer
5, regardless of whether or not all of the messages have been correctly
delivered. Thus, you need not worry about undelivered or unACK'ed
messages still in your sender when the emulator stops. Note that if you set
this value to 1, your program will terminate immediately, before the message
is delivered to the other side. Thus, this value should always be greater than
1.
- Loss. You are asked to specify a packet loss probability. A value
of 0.1 would mean that one in ten packets (on average) are lost.
- Corruption. You are asked to specify a packet loss probability. A
value of 0.2 would mean that one in five packets (on average) are corrupted.
Note that the contents of payload, sequence, ack, or checksum fields can be
corrupted. Your checksum should thus include the data, sequence, and ack
fields.
- Tracing. Setting a tracing value of 1 or 2 will print out useful
information about what is going on inside the emulation (e.g., what's
happening to packets and timers). A tracing value of 0 will turn this off. A
tracing value greater than 2 will display all sorts of odd messages that are
for my own emulator-debugging purposes. A tracing value of 2 may be helpful to
you in debugging your code. You should keep in mind that real
implementors do not have underlying networks that provide such nice
information about what is going to happen to their packets!
- Average time between messages from sender's layer5. You can set
this value to any non-zero, positive value. Note that the smaller the value
you choose, the faster packets will be be arriving to your sender.
Alternating-Bit-Protocol.
You are to write the procedures,
A_output(),A_input(),A_timerinterrupt(),A_init(),B_input(), and
B_init() which together will implement a stop-and-wait (i.e. the
alternating bit protocol, which we referred to as rdt3.0 in the text)
unidirectional transfer of data from the A-side to the B-side. Your protocol
should only use positive acknowledgements with the receiver sending an ACK of
the last good packet if a corrupted or out-of-sequence packet is received.
You should choose a very large value for the average time between messages
from sender's layer5, so that your sender is never called while it still has an
outstanding, unacknowledged message it is trying to send to the receiver. I'd
suggest you choose a value of 1000. You should also perform a check in your
sender to make sure that when A_output() is called, there is no message
currently in transit. If there is, you can simply ignore (drop) the data being
passed to the A_output() routine.
Helpful Hints.
- Checksumming. You can use whatever approach for checksumming you
want. Remember that the sequence number and ack field can also be corrupted.
We would suggest a TCP-like checksum, which consists of the sum of the
(integer) sequence and ack field values, added to a character-by-character sum
of the payload field of the packet (i.e. treat each character as if it were
an 8 bit integer and just add them together).
- Note that any shared "state" among your routines needs to be in the form
of global variables. Note also that any information that your procedures need
to save from one invocation to the next must also be a global (or static)
variable. For example, your routines will need to keep a copy of a packet for
possible retransmission. It would probably be a good idea for such a data
structure to be a global variable in your code. Note, however, that if one of
your global variables is used by your sender side, that variable should
NOT be accessed by the receiving side entity, since in real life,
communicating entities connected only by a communication channel can not share
global variables.
- There is a float global variable called time that you can access
from within your code to help you out with your diagnostics msgs.
- START SIMPLE. Set the probabilities of loss and corruption to zero
and test out your routines. Better yet, design and implement your procedures
for the case of no loss and no corruption, and get them working first. Then
handle the case of one of these probabilities being non-zero, and then finally
both being non-zero.
- Debugging. We'd recommend that you set the tracing level to 2 and
put LOTS of printf's in your code while your debugging your procedures.
- Random Numbers. The emulator generates packet loss and errors using
a random number generator with a fixed seed. It may however generate different
random numbers on different machines. Our sample runs were on katie.
Example runs.
Below are some input and output files.
Your output can of course differ in some ways (e.g. you may have choosen a different way to compute checksums).
In our solution, we used a flag value of 255 when the acknowledgement or sequence number was unused.
We used 15.0 as the timeout value.
rdt < 10_noerr_trace2.txt > 10_noerr_trace2.out
rdt < 10_noerr_trace3.txt > 10_noerr_trace3.out
rdt < 10_corrupt_trace2.txt > 10_corrupt_trace2.out
rdt < 10_corrupt_trace3.txt > 10_corrupt_trace3.out
rdt < 10_trace2.txt > 10_trace2.out
rdt < 10_trace3.txt > 10_trace3.out
Submission.
Submit your program rdt.cpp via Moodle.
Be sure each submitted source file has the required header with your name, username, and a description of the program.
If you worked as a pair, submit only one copy of the source code with both your names on it.
Programs should use descriptive variable names and appropriate levels of commenting (explain at a high-level the goal of different sections of code).
Page last updated: September 11, 2013