Experiment 8.4

Chapter 8 peaks with Experiment 8.4 in which you are to implement a sliding window protocol. If you find this task daunting, may I suggest a first, small step. Include the sequence numbers, and have your server send a starting sequence number with its acknowledgement of the datagram with the name of the file. This lets the client know which datagram it is supposed to receive next. Have the client reject any datagram with a sequence number other than the one it is expecting. This corresponds to a window of 1 datagram.

Debugging can be very difficult. If you did the last Optional Extension in Experiment 8.1, you can extend your logging facility to include sequence number information. Or you can simply have your client display two vital pieces of information: the sequence number it is expecting and the sequence number in the datagram it has received. What you do not want is for your system not to work and give you no information as to why it does not work. Set a very high timeout value in your select statements for debugging purposes.

When you read about the sliding window protocol in textbooks, you get the impression that you set a timer for each datagram transmitted. In fact, the protocol is often implemented with a single timer. You can set the timer using the ualarm function followed by a loop in which you call the recv function. If the timer goes off, will return a negative number of bytes, and errno will be set to EINTR. There is a major difference between Linux and Solaris at this point. You set a function to be your alarm handler using the signal function, but in Linux you only have to do this once. In Solaris, you must do this repeatedly so your handler should call signal before returning. If you are not aware of this, you will have a very difficult time debugging your code because your program will terminate the second time the timer goes off. (Fortunately for me, my colleague, Joel Adams, had run into this problem in the Operating Systems course and knew from my description of the problem exactly what was wrong.)

Here is a sketch of the algorithm assuming a window size of 8 datagrams:

  1. Set up an array of datagrams. The size of the array will be the window size, 8. Each entry in this array should have, at a minimum, a time stamp and a flag indicating its status.
  2. Send 8 datagrams recording the time for each and setting a timer for the first one only.
  3. Repeatedly attempt to receive the number of acknowledgments that corresponds to the number of outstanding datagrams. Whenever one is received, change the flag in the appropriate place from SENT to ACKED. You can only slide the window if the oldest datagram has been acknowledged. My advice is to think this through carefully with a simple example in mind. Suppose you send datagrams 0 through 7. Suppose acknowledgements come in for 3, 0, 4, 2, 7, 5, 6, 1 in that order. When you get number 0, you can slide the window and when you get number 1. In the other cases you can only change the flag.
  4. Whenever the oldest datagram has been acknowledged, you need to set a timer for what is now the oldest unacknowledged datagram.
  5. If your receive loop times out, you have to do two things. One is easy, and one is hard. Obviously, you need to resend datagrams which are still in the SENT state. That is simple to do. However, they need new time stamps, and you need to restart your timer. It turns out that there is a reasonably easy way to do this, but it takes some thinking.
  6. It would seem that figuring out the circumstances in which your server should terminate ought to be easy. Not quite. This too takes some thinking. (Are we seeing a common theme here?) For testing use a high value for the jitter parameters and for the drop parameter and/or the corrupt parameters. It is extremely satisfying to see a reliable file transfer take place under these conditions.
    This site is maintained by by W. David Laverell of the Computer Science Department at Calvin College.
    For assistance or corrections, please contact him at lave@calvin.edu.