CSE 310 – Computer Networks

Summer, 2021

Programming Assignment 02 – Implementing a Reliable Transport Protocol

Re-Assigned: Thursday, 07/08/2021

Due: Sunday, 07/25/2021, at 11:59 PM

For the second programming assignment you will be implementing a simple reliable transport protocol. The protocol will be unidirectional. Host A will be sending segments, and Host B will be receiving and acknowledging those segments, but Host B will not be sending any application data of its own. Host A is the sender, Host B is the receiver.

1. First, read section 3.4.1 – "Building a Reliable Data Transfer Protocol" of Kurose and Ross, Computer Networking: A Top-Down Approach. You will be implementing the Alternating Bit protocol, which they call rdt3.0.

2. Read the directions, descriptions, and suggestions in the attached assignment description from the textbook authors carefully.

3. Examine the files prog2.c and prog2.py carefully. All of your code will be added to one of these files to fill in the function stubs. That is how you will implement rdt3.0 as a part of this network simulation program.

4. You must implement the following functions in prog2.py or prog2.c, please read their descriptions in the assignment description carefully.

a. A_init

b. A_output

c. A_input

d. A_timerinterrupt

e. B_init

f. B_input

5. Do not implement either B_output or B_timerinterrupt. Those functions are only required for a bi-directional version of the protocol. Please ignore these two function stubs.

6. Your implementation should include some output to STDOUT describing events that occur and protocol actions that are taken during the simulation. For example, message arrival, packet arrival, timer interrupt, or data corruption detection, etc. should all be reported to STDOUT. In addition, describe the actions your functions take in response. For example, building a packet, sending a packet, retransmitting a message, restarting the timer, etc. Part of your submission will be a trace of your program—we need output for the trace.

7. Try running the simulation program first – to see what it looks like before you start adding your own code.

8. Submit your source code, which should consist of a single file—your modified prog2.py or prog2.c

9. Submit a README that briefly explains your strategy for implementing each of the functions required for rdt3.0.

10. Submit a trace of your completed program running to the point where about 10 messages have been sent and correctly acknowledged. Use the following settings: loss probability of 0.1, corruption probability of 0.3, and a trace level of 2. You can use screenshots, or you can redirect the output to a file. You might want to annotate your trace to indicate where interesting things happened (e.g., recovery from packet loss or packet corruption).

Submission Instructions:

1. Please submit all files in a compressed directory as a zip file.

2. Please name your submission file: CSE310_PA02_LastName_FirstName.zip

3. This is an individual programming assignment. Any collaboration on coding will be considered a violation of academic honesty.

Programming Assignment 2: Implementing a Reliable Transport Protocol

Overview

In this laboratory programming assignment, you will be writing the sending and receiving transport-level code for implementing a simple reliable data transfer protocol. There are two versions of this lab, the Alternating-Bit-Protocol version and the Go-Back-N version. We are using the Alternating-Bit-Protocol Version only. This lab should be fun since your implementation will differ very little from what would be required in a real-world situation.

Since you probably don't have standalone machines (with an OS that you 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. (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/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 (positively or negatively) 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. The overall structure of the environment is shown in Figure Lab.3-1 (structure of the emulated environment):

The unit of data passed between the upper layers and your protocols is a message, which is declared as:

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 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:

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.

● 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.

The Alternating-Bit-Protocol Version of this lab.

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 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 should put your procedures in a file called prog2.c. You will need the initial version of this file, containing the emulation routines we have writen for you, and the stubs for your procedures. You can obtain this program from http://gaia.cs.umass.edu/kurose/transport/prog2.c.

This lab can be completed on any machine supporting C. It makes no use of UNIX features. (You can simply copy the prog2.c file to whatever machine and OS you choose).

Helpful Hints and the like

● 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. Our past experience is that random number generators can vary widely from one machine to another. You may need to modify the random number generation code in the emulator we have suplied you. Our emulation routines have a test to see if the random number generator on your machine will work with our code. If you get an error message:

It is likely that random number generation on your machine is different from what this emulator expects. Please take a look at the routine jimsrand() in the emulator code. Sorry.

then you'll know you'll need to look at how random numbers are generated in the routine jimsrand(); see the comments in that routine.

Q&A

When we've taught this lab in our introductory neworking course, students have posed versious questions. If you are interested in looking at the questions we've received (and answers), check out http://gaia.cs.umass.edu/kurose/transport/programming_assignment_QA.htm

Here, FYI, are the most recent Q&A's for this lab assignment:

● You write a very clean, portable program! I only made a few changes to compile it on Windows NT using Microsoft Developer Studio. I have not started the assignment yet. I thought you might be interested in what changes I made as an initial step.

1. include stdlib.h

2. add function prototypes at the top of the file for init, generate_next_arrival, and insertevent.

3. declared functions that don't return anything as void.

4. cast a bunch of constants to float.

5. removed a couple of unreferenced local variables.

6. set mmm to RAND_MAX in function jimsrand.

7. exit takes an argument under windows (i.e. exit(0) instead of exit())

8. removed redefinitions of malloc (it is already declared in stdlib.h.)

I'm impressed. You must have put a lot of time into this. I included the whole modified file in case you wanted to take a look.

Well, thanks. Here is the modified code (modification to the code I handed out) that this student turned in. I have not tried that code myself.

● The gcc compiler complains about the use of exit() in your code.

Change exit() to exit(0) if this is a problem.

● The compiler complains about the use of the time variable in your code.

Some compilers will do this. You can change the name of my emulator's time variable to simtime or something like that.

● My timer doesn't work. Sometimes it times out immediately after I set it (without waiting), other times, it does not time out at the right time. What's up?

My timer code is OK (hundreds of students have used it). The most common timer problem I've seen is that students call my timer routine and pass it an integer time value (wrong), instead of a float (as specified).

● You say that we can access you time variable for diagnostics, but it seems that accessing it in managaing our timer interrupt list would also be useful. Can we use time for this purpose?

Yes.

● The jimsrand() function is not returning the right values on the edlab machines

To make jimsrand() work on the edlab Alphas, the variable mmm should be set to RAND_MAX (it may be necessary to include stdlib.h to get this constant).

● Why is there a timer on the B side?

This is there in case you want to implement bi-directional data transfer, in which case you would want a timer for the B->A data path.

● How concerned does our code need to be with synchronizing the sequence numbers between A and B sides? Does our B side code assume that Connection Establishment ( three-way handshake) has already taken place, establishing the first packet sequence number ? In other words can we just assume that the first packet should always have a certain sequence number? Can we pick that number arbitrarily?

You can assume that the three way handshake has already taken place. You can hard-code an initial sequence number into your sender and receiver.

● You instruct us to use both ACK and NAK messages. How would we signify a NAK event given the pkt struct you defined?

A hack would be to use negative numbers for NAKs. I probably should have included an explicit ACK/NAK bit in the packet definition.

● In a bidirectional implementation, how would the sender indicate that a packet includes only an ACK and not an ACK plus data (when there's no data available on which to piggyback the ACK)?

The would be no need to use the sequence number (or you could set it to a default value like -1) if there is no data in the packet.

● When I submitted my assignment I could not get a proper output because the program core dumped..... I could not figure out why I was getting a segmentation fault so ....

Offhand I'm not sure whether this applies to your code, but it seems most of the problems with seg. faults on this lab stemmed from programs that printed out char *'s without ensuring those pointed to null- terminated strings. (For example, the messages -- packet payloads -- supplied by the network emulator were not null-terminated) This is a classic difficulty that trips up many programmers who've recently moved to C from a more safe langauge.

Figure 3.15 rdt3.0 sender

diagram; note that a receive time for a packet is necessarily later than the send time for a packet as a result of transmission and propagation delays. In Figures 3.16(b)–(d), the send-side brackets indicate the times at which a timer is set and later times out. Several of the more subtle aspects of this protocol are explored in the exercises at the end of this chapter. Because packet sequence numbers alternate between 0 and 1, protocol rdt3.0 is sometimes known as the alternating-bit protocol.

We have now assembled the key elements of a data transfer protocol. Checksums, sequence numbers, timers, and positive and negative acknowledgment packets each play a crucial and necessary role in the operation of the protocol. We now have a working reliable data transfer protocol!

Figure 3.14 rdt2.2 receiver

is initiated. The approach thus adopted in practice is for the sender to judiciously choose a time value such that packet loss is likely, although not guaranteed, to have happened. If an ACK is not received within this time, the packet is retransmitted. Note that if a packet experiences a particularly large delay, the sender may retransmit the packet even though neither the data packet nor its ACK have been lost. This introduces the possibility of duplicate data packets in the sender-to-receiver channel. Happily, protocol rdt2.2 already has enough functionality (that is, sequence numbers) to handle the case of duplicate packets.

From the sender’s viewpoint, retransmission is a panacea. The sender does not know whether a data packet was lost, an ACK was lost, or if the packet or ACK was simply overly delayed. In all cases, the action is the same: retransmit. Implementing a time-based retransmission mechanism requires a countdown timer that can interrupt the sender after a given amount of time has expired. The sender will thus need to be able to (1) start the timer each time a packet (either a first-time packet or a retransmission) is sent, (2) respond to a timer interrupt (taking appropriate actions), and (3) stop the timer.

Figure 3.15 shows the sender FSM for rdt3.0 , a protocol that reliably transfers data over a channel that can corrupt or lose packets; in the homework problems, you’ll be asked to provide the receiver FSM for rdt3.0 . Figure 3.16 shows how the protocol operates with no lost or delayed packets and how it handles lost data packets. In Figure 3.16, time moves forward from the top of the diagram toward the bottom of the