What to do
- Phase 5 and Phase 6 are more like the preparation for implementing selective repeat. In Phase 7, we will get into the actual mechanism of selective repeat. Because selective repeat protocol is very complicated, it is almost impossible to implement it in one step without any error, we need to divide the whole work into smaller steps, and validate the code at each step. Below is how I divide the work:
========================================= Step 1 ============================================
Make things simple
- Window size at both client and server to be 1.
- No frame loss and all the frames received are correct, thus no need to consider retransmission.
- Send ACK frame back to sender as soon as the receiver receives a frame. No need to implement timeout and ack_timeout event yet.
We've already limit the complexity, now the only tricky thing left is how to achieve the flow control between Applcation Layer and Datalink Layer, as we only want to enable application layer when nbuffered < NR_BUFS. The first idea that came to my mind is to use signaling between processes; just suspend the Application Layer whenever before a packet is going to be written to the pipe. The Application Layer resumes when it receives a signal from Datalink Layer, which is generated by calling the function enable_app_layer(). Unfortunately, this approach does not work because the signal needs to been generated after the suspension of the Application Layer, otherwise that signal will just be ignored and the application layer will be suspended forever. An alternative is to use select() to block the Application Layer at the same place where it is suspended in the previous approach. The select() monitors the pipe, when receiving a control packet, it unblock the application layer, letting application layer continue writing to the pipe. The control packet is generated and sent to the pipe when calling enable_app_layer(). At this point, the Application Layer is blocked, either waiting to send packets or waiting for incoming packets. Note that the control packet may be consumed sometimes when the Application Layer is waiting for some data packet to come. If control packet is consumed under this situation, they won't have effect on the Application Layer.
Variables
There are a bunch of variables used in selective repeat protocol. They are declared and initialized at both client and server end. Notice that, they are not used at the same time. out_buf[NR_BUFS], nbuffered, next_frame_to_send, and ack_expected are the ones used at the sender, and arrived[NR_BUFS], in_buf[NR_BUFS], frame_expected, and to_far are used at the receiver. Because client and server could act as both a sender and recevier, all these variables will be used eventually.
Structure Graph (Step 1)
ValidationIt's a good idea to test the code by using files of different sizes. Large files are more likely to break down the program, making them the better test cases. For me, I use four files to validate the correctness of the code written so far.
- image.jpeg - 457 bytes
- image.jpg - 606KB
- music.mp3 - 4.73MB
- test.rar - 123MB
========================================= Step 2 ============================================
Make things simple
- Introduce checksum error and NAK frame, but still assume there is no frame loss. Thus no need to consider timeout and ack_timeout event yet.
- Assume that we could only insert error into DATA frame at client side, i.e. no errors in ACK, NAK frame, and DATA frames sent by server.
- Follow one extra rule: frame is inserted an error the first time it is sent to the receiver, when in re-transmission, no error is inserted into that frame.
Making the above simplification, we are able to introduce NAK frame at Step 2 without using any timer. Below is the result when uploading the file image.jpeg.
========================================= Step 3 ============================================
Our task in Step 3 is to realize timer for sender. When a timer times out, the sender knows that a DATA frame it sent previously is lost, or the ACK frame to that DATA frame is lost while in transmission. In response to a timeout event, the sender retransmits the DATA frame corresponding to the timer. How to implement the timer is another piece of work in Selective Repeat protocol. First of all, the timers we are going to implement is virtual timers, which are different from the system timer each process has, and it could not be as accurate as the real timer. Thus we need to use the single timer to simulate multiple virtual timers (at this step, we only need to implement one virtual timer because for now the window size at the sender is 1). Second, how to tell the program that a timer times out is yet another problem we need to face. To solve the first problem, page 222, 223 on the textbook is a good place to find inspiration. What I ended up doing is to use array. Each entry of the array represents a timer and the number in the entry stands for the time left to this timer, with -1 meaning this timer hasn't been started yet or has been stopped. As the system clock ticks, the number in each entry (if not equal to -1) is decremented by a certain time interval, and then if the number in that entry becomes 0, a timeout signal will be sent to Datalink Layer. Another important thing I need to mention is we cannot put timers in Datalink Layer or Application Layer, we need to create another process (let's call it Timer Process), in which we "put" all of our timers. For the second problem, since we used function select() through this project, there will be no exception here. We will create two extra pipes. One pipe is for the Datalink Layer to send starting timer or stopping timer signal to Timer process, and another pipe is for Timer process to send timeout signal to Datalink Layer.
For the timer signals, we used a simple structure which contains three members, timer_NO, type and command. timer_NO is the index of the timer (entry of the array), type could be either TO (timeout) or ATO (ACK timeout), and command could be START, STOP or TIMEOUT. The structure is shown below.
struct timeout_sig{
unsigned int timer_NO;
timer_type type;
timer_command command; };
The following textbox shows the output of transmitting image.jpeg from Client to Server
Client ERRORRATE = 70%Server ERRORRATE = 0%Tick = 0.1 milisecondTimer Interval = 50 milisecondACKTimer Interval = 1 milisecond
Now we know that timer works. Is it done for step 3? No, there is one more thing you need to decide, i.e. we need to specify how long a "tick" will be and how long before a timer timesout. In my code, a "tick" is 1 milisecond and timer will timeout after 0.5 second. These are pretty large numbers if timeout event is frequent, but are fairly reasonable numbers if you just play around with the program. So decide carefully on these two numbers.
Structure Graph (Step 3)
There are still a bunch of simplification in Step 3. As we go forward, we will continuously add complexity. The simplification at Step 3 is all the ACK frame or NAK frame contain no error and will not be lost during transmission, and all the frames sent by server contain no error and will not be lost during transmission.
========================================= Step 4 ============================================
At Step 4, we are going to implement ACK timer. Because of ACK timer, the receiver does not need to send back the ACK frame corresponding to each data frame it receives. For more details about why ACK timer is used, please take a look at page 227, 228 of the textbook. In short, as long as there is some reverse traffic (data frame or NAK frame) back to the sender before the ACK timer expires, the ACK timer will be stopped and thus the ACK will be held. Here is how the textbook put it - If no reverse traffic has presented itself before this timer expires, a separate acknowledgement frame is sent.
Implementing ACK timer is much easier than the retransmission timer. First, all the hard stuff has been finished at Step 3, i.e. we just need to put the ACK timer in the same Timer Process, using the same pipes to send timeout signals and receive start/stop signals. Second, no matter how many window size you have, there is only one ACK timer. So using an integer variable to represent the ACK timer is enough, and the ACK timer works just the same as the retransmission timer. One important difference, maybe obvious enough, between retransmission timer and ACK timer is that ACK timer is used for receiver, and retransmission timer is used for sender. Also make sure the timeout associated with the auxiliary timer be appreciably shorter than the timer used for timing out data frames. This condition is required to make sure a correctly received frame is acknowledged early enough that the frame's retransmission timer does not expire and retransmit the frame.
========================================= Step 5 ============================================From Step 1 to 4, we made certain assumptions to simplify the implementation of Selective Repeat protocol. One of these assumptions is that all the ACK and NAK frame contains no error. In Step 5 we are going to make sure our program could deal with erroneous ACK and NAK frame. In fact, the receiver does not do anything upon receiving damaged ACK or NAK frame, which is fine because we have retransmission timer that will make sure the DATA frame will be retransmitted if it's not been acknowledged within certain period. Another thing I want to mention is that the receiver will respond differently to incoming frames that contain no error. For example, for a DATA frame that is not the one the receiver is expecting, whether or not a NAK frame has been sent makes a difference; if no NAK frame has been sent, the receiver will send a NAK frame to sender. While if a NAK frame has already been sent, the receiver will do nothing. The second goal of Step 5 is to make sure the server program shares exactly the same Datalink code with the client program by implementing retransmission timers and ACK timer at Server side. At this point, we have a client and server that shares the same code of Datalink Layer, yet different code of Application Layer.
The following textbox shows the output of transmitting image.jpeg from Client to Server using the configuration belowClient ERRORRATE = 60%Server ERRORRATE = 0%Tick = 0.1 milisecondTimer Interval = 50 milisecondACKTimer Interval = 1 milisecond
The following textbox shows the output of transmitting image.jpeg from Client to Server using the configuration belowClient ERRORRATE = 30%Server ERRORRATE = 30%Tick = 0.1 milisecondTimer Interval = 50 milisecondACKTimer Interval = 1 milisecond
=========================================== Step 6 ==============================================
If you've made this far, you then have a well-built error-tolerant client/server program that is based on selective repeat protocol. You can play around by specifying different combinations of error rate at client side and server side. You can also change the length of a tick, the retransmission timer interval and ACK timer interval to see what the results are.The goal we need to aim next is to increase the windows size. Implementing a sliding window of only one buffer obviously does not make full use of selective repeat protocol. At this step, let's not aim too big, making the windows size from 1 to 2 is enough.There is nothing much left to talk about extending the window size, what you need to do is to set the NR_BUFS to 2, thus the number of all the timers, buffers are doubled. There is still one tiny trivial thing you need to implement before finishing Step 6. That is to solve the problem of determining which frame caused a timeout. There is plenty of workaround for this problem. What I ended up doing is to add an array oldest_frame_seq storing the frame sequence number of the packet stored at buffer out_buf in Datalink Layer. Thus whenever a timer times out, we look up the frame sequence number stored in the same index of the array oldest_frame_seq and resend that frame to receiver. (Please refer to the last two paragraphs at page 228 in the textbook).========================================= Step 7 ============================================In Step 7, let's double the window size to make it 4. It's very easy to do it, just change NR_BUFS to 4 and add two more timers in Timer Process. However, things turned out to be not as smooth as I expected. The transmission stopped at certain point when I tried to send image.jpg to server. Looking into the log file (which I have added at Step 6), I found out that the variable nbuffered which is used to track the usage of outgoing buffer reaches 5 after certain point during transmission, which should not be allowed. This bug is caused by DLL asking APP to send packet to it too frequently. If you take a look at the end of the while loop inside DLL, you'll findif(nbuffered<NR_BUFS)enable_app_layer();is executed in each iteration, while the case app_layer_ready is not executed in each iteration. Thus nbuffered is not incremented in time to to reflect the effect of enabling application layer. The workaround is to keep a nbuffered at Application Layer, which is kept updated synced with the nbuffered at Datalink Layer. You can easily achieve this by using select() function based on the structure we've built so far.========================================= Step 8 =============================================Just in case there are any other bugs that are not exposed yet and to make sure the our code is robust enough, I added Step 8 to increase the window size to 8. Then transmit the sample files. It turned out the programs are working pretty well!!======================================== Conclusion ==========================================
Now I can finally announce that we've successfully implement Selective Repeat Protocol. It is a big piece of work, which involves socket programming, multi-process programming and massive use of select method. The essential of Multi-process programming is to let the processes be aware of the current state of each other and behaves correspondingly. Thus, socket programming is, to some extent, a kind of multi-process programming, because client and server try to notify each other the current state of themselves.
No comments:
Post a Comment