CIS 432/532 Introduction to Computer Networks
Fall 2002

Program #2: Implementing a Reliable Transport Protocol
Due November 12th, 2:00 PM, online and in class

Overview

You will implement two simple, reliable data transport protocols: Stop-And-Wait and Go-Back-N. Your implementation will differ very little from what would be required in a real-world situation.

Since you probably don't want to modify your own Operating System, 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. (Indeed, the software interfaces described in this programming assignment are much more realistic that the infinite loop senders and receivers that many texts describe.) Stopping and starting of timers is also simulated, allowing you to simulate timer interrupts for your transport protocol.

Procedures

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 (positively or negatively) receipt of data. Your will implement a set of procedures described below. These procedures will be called by (and will call) procedures that are part of a network simulator. The overall structure of the environment is shown below:

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 routines (i.e., those you are to complete) are in the file, prog2.c, described later. Your sending entity will 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): 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): 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): 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): 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.
   
• stoptimer(calling_entity): calling_entity is either 0 (for stopping the A-side timer) or 1 (for stopping the B side timer).
   
• tolayer3(calling_entity,packet): 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): 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. The network simulator (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 corruption 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 network simulator (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 used to debug the simulator. A tracing value of 2 may be helpful to you in debugging your code. You should keep in mind that real implementers 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.

Stop-And-Wait

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 (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 use both ACK and NACK messages.

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.

You must put your procedures in a file called stopandwait.c. You will need the initial version of this file, containing the simulation routines we have written for you, and the stubs for your procedures. You can obtain the program from /cs/classes/cis432/program2.

Make sure you read the "helpful hints" given later in this assignment.

Go-Back-N

You are to write the procedures A_output(), A_input(), A_timerinterrupt(), A_init(), B_input(), and B_init() which together will implement a Go-Back-N unidirectional transfer of data from the A-side to the B-side, with a window size of 8. Your protocol should use both ACK and NACK messages. Consult the alternating-bit-protocol version of this lab above for information about how to use the network simulator.

We would STRONGLY recommend that you first implement Stop-and-Wait, and then extend your code to implement Go-Back-N. Regardless, you must copy stopandwait.c to a new file called gobackn.c and put your Go-Back-N procedures in this new file.

Some new considerations for your Go-Back-N code (which do not apply to the Stop-and-Wait protocol) are:

• A_output(message): message is a structure of type msg, containing data to be sent to the B-side.
  
  Your A_output() routine will now sometimes be called when there are outstanding, unacknowledged messages in the medium - implying that you will have to buffer multiple messages in your sender. Also, you'll also need buffering in your sender because of the nature of Go-Back-N: sometimes your sender will be called but it won't be able to send the new message because the new message falls outside of the window.
  
  Rather than have you worry about buffering an arbitrary number of messages, it will be OK for you to have some finite, maximum number of buffers available at your sender (say for 50 messages) and have your sender simply abort (give up and exit) should all 50 buffers be in use at one point (Note: using the values given below, this should never happen!) In the ``real-world,'' of course, one would have to come up with a more elegant solution to the finite buffer problem!
   
• A_timerinterrupt() This routine will be called when A's timer expires (thus generating a timer interrupt). Remember that you've only got one timer, and may have many outstanding, unacknowledged packets in the medium, so you'll have to think a bit about how to use this single timer.

BiDirectional Transfer

Graduate students must also implement bidirectional transfer of messages. For undergraduates, they will receive extra credit for implementing this. In this case, entities A and B operate as both a sender and receiver. You may also piggyback acknowledgments on data packets (or you can choose not to do so). To get the simulator to deliver messages from layer 5 to your B_output() routine, you will need to change the declared value of BIDIRECTIONAL from 0 to 1.

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 suggest using 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 simtime that you can access from within your code to help you out with your diagnostics messages, for managing a timer interrupt list, and anything else you want.
   
• 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.
   
• For debugging, you should set the tracing level to 2 and use printf() or gdb as appropriate.
   
• Be sure to pass a float value to the timer routines, rather than an integer. The timer will probably not work correctly if you pass it an integer value.
   
• You do not have to implement a three-way handshake. Instead, hard-code an initial sequence number into your sender and receiver.
   
• You will need some way to indicate that a packet is a NACK (as opposed to an ACK). One good way is to use negative numbers for NACKs.
   
• Be careful when printing out a string (character pointer) -- if it is not null-terminated, you may crash your program.

Turning in the Assignment

You must submit all your source code online. Do not submit any object code. Use the submission instructions for this program, which are available in the Schedule section of the class web page.

You must also print out and fill in the survey for this program. The survey is also available in the Schedule section of the class web page. Turn this in to my office on the due date (or put it under my door).

You must also include a printout showing some sample output from your program. The procedures you write should print out a message whenever an event occurs at your sender or receiver (a message/packet arrival, or a timer interrupt) as well as any action taken in response.

For Stop-and-Wait, your sample output should be for a run up to the point (approximately) when 10 messages have been ACK'ed correctly at the receiver, using a loss probability of 0.1, a corruption probability of 0.3, and a trace level of 2. Annotate your printout with a colored pen showing how your protocol correctly recovers from packet loss and corruption. You will be graded based on how well your sample output illustrates the correct operation of your protocol.

For Go-Back-N, your sample output should be for a run that is long enough so that at least 20 messages are successfully transferred from sender to receiver (i.e., the sender receives ACKs for these messages), using a loss probability of 0.2, a corruption probability of 0.2, a trace level of 2, and a mean time between arrivals of 10. Annotate parts of your printout with a colored pen showing how your protocol correctly recovers from packet loss and corruption.

Grading

You will be graded based on how well your protocols handle corruption and packet loss, as well as how they conform to the definition of Stop-and-Wait and Go-Back-N. One of the primary sources of information for this grading will be your sample output. Be sure your annotation of the output is clear and illustrates the correct operation of your protocol.

If you wish to receive partial credit for a program that does not operate correctly, you must print out clear and concise information when the program is run. I will use this information to determine how much of your program works and therefore how much partial credit you will receive. The more helpful and clear your output is, the better your chances. You should apply this same standard to how you document your code.

Any program that does not compile or that crashes while running will receive a 0.