CS 60 Computer Networks


Simple Reliable Transport (SRT) - Implementing Go-Back-N and Checksum

In this lab, you will implement the data transfer protocol for the Simple Reliable Transport (SRT). SRT uses a “sliding window” protocol for efficient data transfer between the client and server (unidirectional reliable byte stream). The data transfer protocol will be able to recover from SRT packet (SRT header and DATA segment) loss and reception of packets with bit errors. We have already dealt with the loss of control packets in Lab4 where SYN, SYNACK, FIN, and FINACK can be lost but the protocol recovers.

In this lab, DATA and DATAACK packets can be lost and the data transfer is designed to recover. In addition, packets may be received in error (be corrupt due to errors on the link). To detect this we will implement a checksum that will be included in the SRT header of all transmitted packets. On reception of packets (be it the client or server) the checksum will be recomputed and packets will be silently dropped if a bit error is detected. So in this lab we will implement Go-Back-N (GBN) and a checksum mechanism. This makes our SRT transport robust to packet loss and packet corruption which happen on the Internet.

At the end of this lab you will have really good sense for how protocols such as TCP establish connections between hosts and how the internal mechanisms resolve issue such as lost or corrupt signaling packets (e.g., SYN is lost).

Before you read another line of this programming assignment please read or re-read the lecture notes on SRT Data Transfer

Submitting assignment: Submit via svn as usual.

Please make sure that the lab5 directory contains a simple text file, named README, describing anything “unusual” about how your solutions should be located, executed, and considered; and a Makefile to build the source.

In the case of the stress test you will send a plain text file - send_this_text.txt - between the client and server. At the server you will save this file as receivedtext.txt. Please do a “diff” on those files since we will when we run your transport to confirm that all the bytes are received reliably in-order.

Your lab5 should have the following structure and files.

[atc@dhcp-212-223 lab4] ls *

Makefile ReadMe

app_simple_client.c app_stress_client.c send_this_text.txt srt_client.c srt_client.h

constants.h seg.c seg.h

app_simple_server.c app_stress_server.c receivedtext.txt srt_server.c srt_server.h

OK, let’s get going


Source and header files - please read them

OK, now you have read the design notes, look at these important files - browse them for now, we will be back.

Note, all the files listed below plus other files (e.g., makefile, README, etc.) needed for this lab can be found in this tarball file: lab5handout.tar.gz . Save this and work from this tarball for your assignment.

We provide two sets of application client and server files: (1) simple application client and server and (2) stress test application client and server. The simple case will send short text buffers between the client and server application. The stress test case send a plain text file between the client and server; this last app. will test out your transport in a more comprehensive manner.

Note, that you do not have to write any application client or server code in this assignment. This allows you to focus on the implementation of the go-back-n and checksum processing for the SRT client and server side code. The basic idea is to first get your code running with the simple code set and if that works move to running the stress test against your code base. You should extend your srt_client.c and srt_server.c that you wrote for lab4. The basic skeleton code for srt_client.c and srt_server.c is given below.

Simple client and server code:



Stress test client and server code:



For the stress test you will need two put the following plain text file in the same directory as your app˙stress˙client


Client side data structures and prototypes needed to implement the client side SRT protocol



Server side data structures and prototypes needed to implement the server side SRT protocol



SNP APIs - header file. SRT header and segment data structure, SNP prototypes.




Adding the Data Transfer Code to your existing Code Base

The idea of this lab is to build on what you have already coded. You should start with your existing code set and add Data Transfer to that. Note, you do not have to start from ground zero.

Please familiarize yourself with the following in the SRT data transfer design ; with focus on:

+Send buffer data structure and life cycle

+Receive buffer data structure and life cycle

+Go-Back-N Finite State Machine

You will need to add new events and actions to your existing state machine implementation according to the material discussed on Lecture 13 on SRT Data Transfer. Most code changes are associated with the CONNECTED state of the full FSMs described in SRT design. If you were to look at the CONNECTED state in the original design document and then look at the Go-Back-N FSMs for the client and server in SRT data transfer. So again most of the action is in the CONNECTED state on the client and server side.

New SRT Functions to Implement

For Lab5 you need to implement two new SRT interfaces: srt_client_send() and srt_svr_recv(). Here are the prototypes for these new parts of the SRT API. You can change them according to your own design if you want.

srt_client_send(int sockfd, void* data, unsigned int length)

Here is the str_client_send() prototype definition:

int srt_client_send(int sockfd, void* data, unsigned int length);

// Send data to an srt server. This function should use the socket ID
// to find the TCP entry. Then it should create segBufs using the given
// data and append them to send buffer linked list. If the send buffer
// was empty before insertion, a thread called sendbuf_timer should
// be started to poll the send buffer every SENDBUF_POLLING_INTERVAL
// time to check if a timeout event should occur. If the function
// completes successfully, it returns 1. Otherwise, it returns -1.

srt_server_recv(int sockfd, void* buf, unsigned int length)

Here is the str_server_recv() prototype definition:

int srt_server_recv(int sockfd, void* buf, unsigned int length);

// Receive data from an srt client. Recall this is a unidirectional
// transport where DATA flows from the client to the server.
// Signaling/control messages such as SYN, SYNACK, etc. flow in both
// directions. This function keeps polling the receive buffer every
// RECVBUF_POLLING_INTERVAL until the requested data is available,
// it then stores the data and return 1. If the function
// fails, return -1

Besides implementing these two new functions you also need to modify other SRT APIs implemented as part of Lab4 to make data transfer work correctly. For example, in srt_svr_sock() you need to add code to dynamically create the receive buffer and mutex for receive buffer. So you need to think about your design and determine what other changes need to be made to make data transfer work. Clearl,y you need a sender side buffer to, for example.

Segment Checksum

You need to implement a checksum. Lab4 uses seglost() to determine if a segment is lost or not and then drop the segment silently if it is deemed lost. In this lab, we extend seglost() to create segment errors by flipping a random bit in the segment. You have to implement the checksum creation function checksum() and the checksum checking function checkchecksum() to detect if any bit errors have occurred.

Here is the prototype for seglost() and its implementation from seg.h. You can copy the seglost implementation directly to your seg.c file.

Note, don’t cut and paste seglost from these notes but cut and paste it from this file - or save this file. seg.h

seglost(seg_t* segPtr)

// This function is called after a segment is received
// a segment has PKT_LOSS_RATE probability to be lost or
// has invalid checksum with PKT_LOSS_RATE/2 probability,
// the segment is lost, this function returns 1
// if the segment is not lost, return 0
// Even if the segment is not lost, the segment has PKT_LOSS_RATE/2
// probability to have invalid checksum
// To introduce invalid checksum, we flip  a random bit
// in the segment  int seglost(seg_t* segPtr);
// source code for seglost
// put this in seg.c

int seglost(seg_t* segPtr) {

  int random = rand()%100;

  //if this segment is corrupted

  if(random<PKT_LOSS_RATE*100) {
    //50% probability of losing a segment
    if(rand()%2==0) {
        printf("seg lost!!!\n");
        return 1;
    } else { //50% chance of having invalid checksum
        //get data length
        int len = sizeof(srt_hdr_t)+segPtr->header.length;

        //get a random bit that will be flipped
        int errorbit = rand()%(len*8);

        //flip the bit
        char* temp = (char*)segPtr;
        temp = temp + errorbit/8;
        *temp = *temp^(1<<(errorbit%8));
        return 0;
  return 0;

You should implement two new functions checksum() and checkchecksum() in seg.c.

checksum(seg_t* segment)

In what follows, we describe the SRT checksum which is the same as the TCP/UDP checksum. Following that we detail the checksum() prototype.

The checksum() algorithm: first clear the checksum field in segment to 0. Denote the data from which the checksum is calculated as D. D = segment header + segment data. If size of D (in bytes) is an odd number, append a byte with all bits set as 0 to D. (Note, we do not mean add a byte to what is to be transfered. But add a byte so the computation is on 16 bit boundaries). Then checksum() divides D into 16-bits-long values and adds all these 16-bits-long values using 1s complement addition. Then sum of these 16-bits-long values is flipped and returned to the calling code For signaling messages (e.g., SYN) there is a header and no data. Therefore, the checksum is computed on the header. Note that the value of the checksum field in the header is always 0 before the checksum computation is done.

Note, that on return from checksum the returned checksum value is written to the checksum field in the header.

Here is the checksum() prototype definition:

unsigned short checksum(seg_t* segment);

// Calculate the checksum over a segment.
// The checksum is calculated over both the header and data in
// the segment. You should first make the checksum field in the
// segment to 0, then if the data contained in segment has
// odd number of octets, add one 0 octet at the end.
// Then calculate the checksum using the Internet checksum
// calculation method from your text book (one’s complement)
// return the checksum value.
// The returned value is written to the header checksum.

checkchecksum(seg_t* segment)

In what follows, we describe the SRT checksum which is the same as the TCP/UDP checksum. Following that we detail the checksum() prototype.

The checkchecksum() algorithm: Denote the data from which the checksum is calculated as D. D = segment header + segment data. If size of D (in bytes) is an odd number, append a byte with all bits set as 0 to D. checkchecksum() divides D into 16-bits-long values, and adds all these 16-bits-long values using 1s complement to get the sum. Note, the sum of D includes the computed checkcum put in the packet header by the sender. If resulting sum is 0xFFFF (hexadecimal) (where all 16 bits are set) then a valid checksum has been computed for this packet. This indicates that there has been no single bit error. Rather than checking 0xFFFF the checkchecksum() flips the bits of sum and check the flipped sum against 0. The checkchecksum() function flips the sum of these 16-bits-long value and returns 1 if the result is 0. Otherwise, return -1.

Here is the checkchecksum() prototype definitions:

int checkchecksum(seg_t* segment);

// check the checksum value in the segment
// if the checksum is valid, return 1
// If the checksum is invalid, return -1

To use the checksum you need to modify your previous implementation of snp_sendseg() and snp_recvseg().

In snp_sendseg() function, before sending a segment, use checksum() to compute the checksum for the segment and put checksum into the segment’s checksum field. Take a look at the SRT segment header to see the field the checksum is written into.

In snp_recvseg() function, after receiving a segment and after calling seglost() we should compute the checksum for the packet that is received calling checkchecksum(). If we compute there is a corrupt packet we silently drop it else we carry on and process the packet. Note that errors can occurs in control (SYN, FIN, etc.) and DATA packets. In the case of DATA segments the checksum must be computed over the SRT header and DATA segment - that is, compute the checksum for the complete SRT packet. In the case of control packets (e.g., SYN) there is no data segment so the checksum is computed on the header only.

Note, students find the checksum hard to code. Here is what I can do. If you code the checksum yourself you get an extra credit. If you do not want to do that the c code for the checksum and other languages can be found in the following RFC - you can use that code with citation if you wish:

Computing the Internet Checksum

This is also a very helpful link:

Additive Checksums

Why is this a first for undergrads?

Once you have completed Lab5 you will have completed what are essentially the core protocol components of a transport protocol. You will be able to support multiple connections in parallel. Those connections will support reliable in-order byte streams. Your protocol will support loss of packets and reception of corrupt packets. Essentially, your protocol and FSM is not widely different from TCP.

This is the first time I have seem this done where undergrads have implemented a transport that runs over the Internet - this is no stinking simulator or emulator - this is real thing and I think it is very cool that you have completed this. And, quite novel. Tell people when you interview - yes, I have implemented a transport, and wait for the reaction!