GDN programming assignment

Designing and implementing a communication protocol that is a basic ingredient for many other protocols.

Overview

In this assignment, each group of 2 students will design, implement, test and describe the sending and receiving code for a sliding window data link protocol: the Go Back N version. This lab should be fun since your implementation will differ very little from what would be required in a real-world situation.

Since we don't have standalone machines, with an OS that we can modify, your code will have to 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.

You can download the simulator here.

The routines you will write

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 have been written to emulate a network environment. The overall structure of the environment is shown in structure of the emulated environment. Note that this gives the uni-directional case, in this assignment we use the bi-directional case (#define BIDIRECTIONAL 1 in the code). Both A and B sides are then sending and receiving messages.

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 simulator program, simprog.c,, described later. Your sending entities will thus receive data in 20-byte chunks from a higher layer (called layer5); your receiving entities should deliver 20-byte chunks of correctly received data in the correct order to layer5 of the receiving side.

The unit of data passed between your routines and the lower layer (called layer3 here) is the packet, which is declared as:

struct pkt {
   int seqnum;
   int acknum;
   int checksum;
   struct msg mes;
    };

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(B)_output(struct msg mes), where mes contains data to be sent to the B(A)-side. This routine will be called whenever the upper layer at the sending side A(B) 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(B)_input(struct pkt packet). This routine will be called whenever a packet sent from the B(A)-side (i.e., as a result of a tolayer3() being done by a B(A)-side procedure) arrives at the A(B)-side. packet is the (possibly corrupted) packet sent from the B(A)-side.
• A(B)_timerinterrupt(int tnum) . This routine will be called when A(B)'s timer number tnum expires (thus generating a timer interrupt). You'll probably want to use this routine to control the retransmission of packets and the piggybacking of ACK's. See starttimer() and stoptimer() below for how the timer is started and stopped.
• A(B)_init() .These routines will be called once, before any of your other A(B)-side routines are called. It can be used to do any required initialization.
• A(B)_finish(). These routines will be called when the main program is finished, you could use them to printout debug or statistics information.

Note that a global variable used by the A side routines may not be used by the B side routines (and vice versa), since in real live they run on different machines. To make live easy, you may use it for debugging (use the DEBUG define).

Software Interfaces

The following emulator routines can be called by your routines:

• void starttimer(int calling_entity, int tnum, float increment), where calling_entity is either 0 (for starting the A-side timer) or 1 (for starting the B side timer), tnum is the number of the timer and increment indicates 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. There can be any number of timers. To give you an idea of the appropriate increment value to use: a packet sent to layer takes an average of 20 time units to arrive at the other side when there are no other messages in the medium.
• void stoptimer(int calling_entity, int tnum), where calling_entity is either 0 or 1, and tnum is the number of the timer.
• void tolayer3(int calling_entity, struct pkt packet). Calling this routine will cause the packet to be sent into the network, destined for the other entity.
• void tolayer5(int calling_entity, struct msg message). Calling this routine will cause data to be passed up to layer 5 of the calling entity.
• void onofflayer5(int calling_entity, int onoff), turns layer5 of the calling entity on (1) or off(0). Initially they are off.
• double gettime(), returns the (simulation) time, which you could use in this assigment for debugging.

The simulated network environment

A call to procedure tolayer3() sends packets into the medium (i.e., is send out to the other side). 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 type in values regarding the simulated network environment, unless you give them on the command line:

• Number of messages to simulate. They will be evenly divided over both sides.
• 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.
• Average time between messages from sender's layer5. You can set this value to any non-zero, positive value.
• Tracing. Setting a tracing value of 3, 4 or 5 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. 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!

The simulator can be compiled on any machine supporting C, it does not use special UNIX or Windows features. A problem could be the random number generator rand() and the largest integer mmm, used in the simrand() function. A simple check is performed on the returned random values and an error message is printed when this fails. In that case you have to change simrand() so that it works on your machine. When you handin your assigment, put the original simrand() back.

The Go Back N version.

You should implement a sliding window protocol using Go Back N. Your protocol should use both ACK and NACK messages. You can use the #define's as given in simprog.c, in that way you can use static declarations for buffers (e.g struct pkt window[2][NRBUFS] ) instead of having to use dynamic allocations. Test you routines for various values of these #define's and of the loss and corruption probabilities (e.g. 0.0, 0.1, 0.95). Put your procedures in a file called proggbn.c.

For the case "proggbn 10000 0.1 0.1 8.0 0", with NRBUFS set to 8 and TO_ACK set to 20.0, you should determine the "best" setting of the timeout value (TO_PKT) for packets. Consider both the transfer rate (messages per timeunit) and the loading of the network (packets per message).

You should handin your proggbn.c program, a design document describing your design and implementation, and a document describing how you have determined the time-out value.

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).
• Shared variables. 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. Note, however, that if a global variable is used by the A (B) side, that variable should NOT be accessed by the B (A) side, since in real life, communicating entities connected only by a communication channel can not share global variables.
• 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 4 or 5 and put LOTS of printf's in your code while your debugging your procedures, put this under the DEBUG define. You may printout global variables from the other side and use gettime() to check the timeing. Leave the debug code in.
• Message contents. The 20 char messages have internally a sequence number, which is used by the simulator to check the order of delivery. An error message is given if a message is delivered out of order. You can use simprpacket() and simprcont() to printout packet and message information for your debugging.
• ACK and NACK. You could use the seqnum and acknum fields in struct pkt to encode the type of packet:
  • seqnum < 0 : no data, only ack or nack
  • acknum = 0: no ack with this packet
  • acknum < 0: nack: seqnum = -(acknum+1) was not received, previous ones are
  • acknum > 0: ack: seqnum = (acknum+1) was received, previous ones also

Handin

The handin requirements are described already above, they contain the programs, design and implementation descriptions and the timing measurements and evaluations.

Send it in by email as an attachment in a compressed format.

Success,
Theo