Douglas E. Comer

Computer Science Department
Purdue University
West Lafayette, IN 47907

webmaster: W. David Laverell

Companion Topics

Home

Book Information

Purpose of Site

Getting Started

Students

Faculty

"What's New"

"Coming Attractions"

"C Pointers"

Acknowledgements

Chapter 8 continues 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. Compatibility is quite an issue on this assignment. My first solution used the ualarm function followed by a loop with the recv function. If the timer goes off, recv returns a negative number of bytes, and errno will be set to EINTR. Unfortunately, ualarm is not a standard feature of Linux so my solution worked only on Solaris. I put the problem aside to work on other things and came across the function setitimer. After varyifying that Linux offers this function, I quickly produced a second Solaris solution. I then discovered that this function simply does not work the same way on Linux, in fact, it didn't work at all. I tried it on Mandrake 8.1, Red Hat 7.3, and SuSE 8.1 and it failed consistently. In desperation I turned to an old friend, the select function and was able to produce a portable solution.

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 W. David Laverell of the Computer Science Department at Calvin College. For assistance or corrections, please contact him at lave@calvin.edu.