Phase 9 - Implement Multi-Client

What to do

1) Implement multiple clients connect to server.

There are several ways to implement a server serving multiple client concurrently. Two common approaches are to use fork() and select()

The fork() approach

http://www.tutorialspoint.com/unix_sockets/socket_server_example.htm

The select() approach

http://www.binarytides.com/blog/handle-multiple-socket-connections-with-fd_set-and-select-on-linux/

I ended up using the fork() approach, which is really easy. The basic idea is whenever the server accepts a client connection, it creates a new process to deal with this connection. Thus different clients can perform its own operation without affecting each other. As soon as the clients exits, the corresponding process terminates itself.

Goal

Modify the server program so that it could handle multiple clients at the same time. Run client program on different machines and connects to the same server.

Related Topic: How to exit client program and server program safely

When the server receives the exit command from client, it need to make sure that client receives the ACK frame before it exit. But how would the server know the client has received the ACK frame? Does the client need to send another frame to server to notify its receipt of the command it sent? There is actually a very simple way to do this. We know that client would keep re-sending frames until it receives the ACK frames. So after receiving the last frame, if for a certain period of time (which must be longer than the retransmission timer interval), the server does not receive any more frame from client, it knows the client has received the ACK frame, and it can exit safely.

One way to implement this is when the Application Layer of server identifies the exit command from client, it sends a control packet to the Datalink Layer. Upon receiving that control packet, Datalink Layer notifies Timer Process to start an extra timer called Exit Timer, whose interval should be reasonably longer than the retransmission timer interval. After that, whenever a frame is received at server, the Exit Timer gets restarted. When the Exit Timer times out, server can shut itself down safely. (There is still one possibility that for some reason after sending the exit command, the client hangs up for a period that's longer than the interval of Exit Timer, then the server would shut itself down before client receives any ACK. We do not consider this scenaria).

Phase 8 - Making Sure A File Is Completely Transmitted Before Entering Another Command

In this phase, we are going to deal with an issue we didn't pay much attention before. That is when an command is finished, say a file is finished uploading to the server, a "Please type in command here:" message is displayed in the console and user is allowed to enter their commands. The message is displayed right after the Application send the last packet to the Datalink Layer. Is it safe to do this? When error rate is zero or extremely low, probably yes. But when the error rate is high, like 70% as we set in our code for now, it's not safe at all. The reason is, take window size 8 for an example, that the frame which are sent before the last frame is very likely to be still in the buffer and not acknowledged yet, and it may take a long time for all of them to be acknowledged. It's even more unsafe if the next command is to exit the program, because the client program may be shut down before a file is transmitted completely. So we need to come up with an mechanism that when the receiver sends the last few packets of a file from its Datalink Layer to Application Layer, it would notify the sender by adding extra information in its last ACK frame. It's not that tricky to fulfill this goal, what you need to do is to get hint from the buffer usage at receiver, the time at which the last frame is arrived, among other information you can gain at the Datalink Layer. When the sender receives such ACK frame, it knows the file has been transmitted completely, and can safely go for the next command.

Goal of Phase 8
Modify the code so that before an user can enter another command, the file that needs to transmitted in the current command is completely transmitted.

Related Topic: Things you should know when using select()

Be really careful with your code when you use select function. Select() function is frequently used in multiprocessing programming and network programming to coordinate different processes. Very likely, the select function appears in infinite loop to catch any incoming messages. The regular order to use select function is

1) zero out the object of type fd_set

2) bind the file descriptor you want to monitor with the fd_set object 

3) find out the largest file descriptor

4) set up the timeval structure to specify how long this select function will be used if it's not NULL

The following code shows how the select monitors the reading end of a pipe. 

//initialize variables
fd_set input;
int max_fd;
int n; 
struct timeval timeout;
 
while(1)
{
 //set up time interval, 1 second
 timeout.tv_sec  = 1;
 timeout.tv_usec = 0; 
 //set up select function
 FD_ZERO(&input);
 FD_SET(fd_pipe_in[0], &input);
 max_fd=fd_pipe_in[0]+1;
 n=select(max_fd, &input, NULL, NULL, &timeout);
 if(n<0)
 perror("select() failed");
 // if nothing happens in this period
 else if(n==0)
 {
  //...
 }
 // if something is on the reading end of the pipe
 else
 {
  if(FD_ISSET(fd_pipe_in[0], &input))
   { 
    //......
   } 
 }
} 

Phase 7 - Implement Sliding WIndow (Part 3)

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)

Validation

It'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.

Client Output

Please type in command here: UP#image.jpeg#

-> 1 frame: DATA (Error)

<- 1 frame: NAK

-> 2 frame: DATA (Retransmission)

<- 2 frame: ACK

<- 3 frame: DATA

-> 3 frame: ACK

Start uploading...

-> 4 frame: DATA (Error)

<- 4 frame: NAK

-> 5 frame: DATA (Retransmission)

<- 5 frame: ACK

-> 6 frame: DATA (Error)

<- 6 frame: NAK

-> 7 frame: DATA (Retransmission)

<- 7 frame: ACK

-> 8 frame: DATA (Error)

<- 8 frame: NAK

-> 9 frame: DATA (Retransmission)

<- 9 frame: ACK

-> 10 frame: DATA (Error)

<- 10 frame: NAK

-> 11 frame: DATA (Retransmission)

<- 11 frame: ACK

<- 12 frame: DATA

-> 12 frame: ACK

You've uploaded the file

Server Output

<- 1 frame: DATA (BAD)

-> 1 frame: NAK

<- 2 frame: DATA (GOOD)

-> 2 frame: ACK

-> 3 frame: DATA 

<- 3 frame: ACK

<- 4 frame: DATA (BAD)

-> 4 frame: NAK

<- 5 frame: DATA (GOOD)

<- 5 frame: ACK

<- 6 frame: DATA (BAD)

-> 6 frame: NAK

<- 7 frame: DATA (GOOD)

-> 7 frame: ACK

<- 8 frame: DATA (BAD)

-> 8 frame: NAK

<- 9 frame: DATA (GOOD)

-> 9 frame: ACK

<- 10 frame: DATA (BAD)

-> 10 frame: NAK

<- 11 frame: DATA (GOOD)

-> 11 frame: ACK

-> 12 frame: DATA

<- 12 frame: ACK

========================================= 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 milisecond

Timer Interval = 50 milisecond

ACKTimer Interval = 1 milisecond

Output of client

1. Please type in command here: UP#image.jpeg#
2. -> 1 frame: DATA (BAD)
3. <- 1 frame: NAK
4. -> 2 frame: DATA (Retransmission) (BAD)
5. Timeout 1
6. -> 3 frame: DATA (Retransmission) (BAD)
7. Timeout 2
8. -> 4 frame: DATA (Retransmission) (GOOD)
9. <- 2 frame: ACK
10. <- 3 frame: DATA
11. -> 5 frame: ACK
12. Start uploading...
13. -> 6 frame: DATA (GOOD)
14. <- 4 frame: ACK
15. -> 7 frame: DATA (GOOD)
16. <- 5 frame: ACK
17. -> 8 frame: DATA (GOOD)
18. <- 6 frame: ACK
19. -> 9 frame: DATA (BAD)
20. <- 7 frame: NAK
21. -> 10 frame: DATA (Retransmission) (BAD)
22. Timeout 3
23. -> 11 frame: DATA (Retransmission) (GOOD)
24. <- 8 frame: ACK
25. <- 9 frame: DATA
26. -> 12 frame: ACK
27. You've uploadeded the file

Output of server

1. 
   
2. <- 1 frame: DATA - BAD
3. -> 1 frame: NAK
4. <- 2 frame: DATA - BAD
5. 
   
6. <- 3 frame: DATA - BAD
7. 
   
8. <- 4 frame: DATA - GOOD
9. -> 2 frame: ACK
10. -> 3 frame: DATA
11. <- 5 frame: ACK
12. 
    
13. <- 6 frame: DATA - GOOD
14. -> 4 frame: ACK
15. <- 7 frame: DATA - GOOD
16. -> 5 frame: ACK
17. <- 8 frame: DATA - GOOD
18. -> 6 frame: ACK
19. <- 9 frame: DATA - BAD
20. -> 7 frame: NAK
21. <- 10 frame: DATA - BAD
22. 
    
23. <- 11 frame: DATA - GOOD
24. -> 8 frame: ACK
25. -> 9 frame: DATA
26. <- 12 frame: ACK

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 below

Client ERRORRATE = 60%

Server ERRORRATE = 0%

Tick = 0.1 milisecond

Timer Interval = 50 milisecond

ACKTimer Interval = 1 milisecond

Client Output

1. Please type in command here: UP#image.jpeg#
2. -> 1 frame: DATA (BAD)
3. Start Timer
4. Stop ACK Timer
5. <- 1 frame: NAK (GOOD) (BETWEEN)
6. 
   
7. -> 2 frame: DATA (Retransmission) (BAD)
8. Start Timer
9. Stop ACK Timer
10. Timeout 1
11. -> 3 frame: DATA (Retransmission) (GOOD)
12. Start Timer
13. Stop ACK Timer
14. <- 2 frame: DATA (GOOD) (EXPECTED)
15. Start ACK Timer
16. Start uploading...
17. Ack timeout 1
18. -> 4 frame: ACK (GOOD)
19. Stop ACK Timer
20. Timeout 2
21. -> 5 frame: DATA (Retransmission) (BAD)
22. Start Timer
23. Stop ACK Timer
24. <- 3 frame: NAK (GOOD) (NOT BETWEEN)
25. Timeout 3
26. -> 6 frame: DATA (Retransmission) (GOOD)
27. Start Timer
28. Stop ACK Timer
29. <- 4 frame: ACK (GOOD)
30. Stop Timer
31. -> 7 frame: DATA (GOOD)
32. Start Timer
33. Stop ACK Timer
34. <- 5 frame: ACK (GOOD)
35. Stop Timer
36. -> 8 frame: DATA (GOOD)
37. Start Timer
38. Stop ACK Timer
39. <- 6 frame: ACK (GOOD)
40. Stop Timer
41. -> 9 frame: DATA (BAD)
42. Start Timer
43. Stop ACK Timer
44. <- 7 frame: NAK (GOOD) (BETWEEN)
45. 
    
46. -> 10 frame: DATA (Retransmission) (BAD)
47. Start Timer
48. Stop ACK Timer
49. Timeout 4
50. -> 11 frame: DATA (Retransmission) (GOOD)
51. Start Timer
52. Stop ACK Timer
53. <- 8 frame: ACK (GOOD)
54. Stop Timer
55. -> 12 frame: DATA (GOOD)
56. Start Timer
57. Stop ACK Timer
58. <- 9 frame: DATA (GOOD) (EXPECTED)
59. Start ACK Timer
60. You've uploadeded the file
61. Ack timeout 2
62. -> 13 frame: ACK (BAD)
63. Stop ACK Timer
64. Timeout 5
65. -> 14 frame: DATA (Retransmission) (GOOD)
66. Start Timer
67. Stop ACK Timer
68. <- 10 frame: NAK (GOOD) (NOT BETWEEN)
69. Timeout 6
70. -> 15 frame: DATA (Retransmission) (GOOD)
71. Start Timer
72. Stop ACK Timer
73. <- 11 frame: ACK (GOOD)
74. Stop Timer
75. 
    
76. <- 12 frame: DATA (GOOD) (NOT EXPECTED)
77. 
    
78. 
    
79. -> 16 frame: NAK (GOOD)
80. Stop ACK Timer
81. <- 13 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
82. Start ACK Timer
83. Ack timeout 3
84. -> 17 frame: ACK (BAD)
85. Stop ACK Timer
86. <- 14 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
87. Start ACK Timer
88. Ack timeout 4
89. -> 18 frame: ACK (GOOD)
90. Stop ACK Timer
91. Please type in command here:

Server Output

1. -bash-3.2$ ./Phase_4_Server
2. <- 1 frame: DATA (BAD)
3. 
   
4. 
   
5. -> 1 frame: NAK (GOOD)
6. Stop ACK Timer
7. <- 2 frame: DATA (BAD)
8. 
   
9. 
   
10. 
    
11. <- 3 frame: DATA (GOOD) (EXPECTED)
12. Start ACK Timer
13. 
    
14. -> 2 frame: DATA (GOOD)
15. Start Timer
16. Stop ACK Timer
17. 
    
18. <- 4 frame: ACK (GOOD)
19. Stop Timer
20. 
    
21. <- 5 frame: DATA (BAD)
22. 
    
23. 
    
24. -> 3 frame: NAK (GOOD)
25. Stop ACK Timer
26. <- 6 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
27. Start ACK Timer
28. Ack timeout 1
29. -> 4 frame: ACK (GOOD)
30. Stop ACK Timer
31. <- 7 frame: DATA (GOOD) (EXPECTED)
32. Start ACK Timer
33. Ack timeout 2
34. -> 5 frame: ACK (GOOD)
35. Stop ACK Timer
36. <- 8 frame: DATA (GOOD) (EXPECTED)
37. Start ACK Timer
38. Ack timeout 3
39. -> 6 frame: ACK (GOOD)
40. Stop ACK Timer
41. <- 9 frame: DATA (BAD)
42. 
    
43. 
    
44. -> 7 frame: NAK (GOOD)
45. Stop ACK Timer
46. <- 10 frame: DATA (BAD)
47. 
    
48. 
    
49. 
    
50. <- 11 frame: DATA (GOOD) (EXPECTED)
51. Start ACK Timer
52. Ack timeout 4
53. -> 8 frame: ACK (GOOD)
54. Stop ACK Timer
55. <- 12 frame: DATA (GOOD) (EXPECTED)
56. Start ACK Timer
57. 
    
58. -> 9 frame: DATA (GOOD)
59. Start Timer
60. Stop ACK Timer
61. 
    
62. <- 13 frame: ACK (BAD)
63. 
    
64. 
    
65. <- 14 frame: DATA (GOOD) (NOT EXPECTED)
66. 
    
67. 
    
68. -> 10 frame: NAK (GOOD)
69. Stop ACK Timer
70. <- 15 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
71. Start ACK Timer
72. Ack timeout 5
73. -> 11 frame: ACK (GOOD)
74. Stop ACK Timer
75. Timeout 1
76. -> 12 frame: DATA (Retransmission) (GOOD)
77. Start Timer
78. Stop ACK Timer
79. <- 16 frame: NAK (GOOD) (NOT BETWEEN)
80. Timeout 2
81. -> 13 frame: DATA (Retransmission) (GOOD)
82. Start Timer
83. Stop ACK Timer
84. <- 17 frame: ACK (BAD)
85. Timeout 3
86. -> 14 frame: DATA (Retransmission) (GOOD)
87. Start Timer
88. Stop ACK Timer
89. <- 18 frame: ACK (GOOD)
90. Stop Timer

The following textbox shows the output of transmitting image.jpeg from Client to Server using the configuration below

Client ERRORRATE = 30%

Server ERRORRATE = 30%

Tick = 0.1 milisecond

Timer Interval = 50 milisecond

ACKTimer Interval = 1 milisecond

Client Output

1. Please type in command here: UP#image.jpeg#
2. -> 1 frame: DATA (GOOD)
3. Start Timer
4. Stop ACK Timer
5. <- 1 frame: DATA (GOOD) (EXPECTED)
6. Start ACK Timer
7. Start uploading...
8. Ack timeout 1
9. -> 2 frame: ACK (BAD)
10. Stop ACK Timer
11. Timeout 1
12. -> 3 frame: DATA (Retransmission) (BAD)
13. Start Timer
14. Stop ACK Timer
15. <- 2 frame: NAK (GOOD) (NOT BETWEEN)
16. Timeout 2
17. -> 4 frame: DATA (Retransmission) (GOOD)
18. Start Timer
19. Stop ACK Timer
20. <- 3 frame: ACK (GOOD)
21. Stop Timer
22. -> 5 frame: DATA (GOOD)
23. Start Timer
24. Stop ACK Timer
25. <- 4 frame: ACK (BAD)
26. Timeout 3
27. -> 6 frame: DATA (Retransmission) (GOOD)
28. Start Timer
29. Stop ACK Timer
30. <- 5 frame: NAK (GOOD) (NOT BETWEEN)
31. 
    
32. 
    
33. <- 6 frame: DATA (GOOD) (NOT EXPECTED)
34. 
    
35. 
    
36. -> 7 frame: NAK (GOOD)
37. Stop ACK Timer
38. Timeout 4
39. -> 8 frame: DATA (Retransmission) (GOOD)
40. Start Timer
41. Stop ACK Timer
42. <- 7 frame: ACK (GOOD)
43. Stop Timer
44. -> 9 frame: DATA (BAD)
45. Start Timer
46. Stop ACK Timer
47. Timeout 5
48. -> 10 frame: DATA (Retransmission) (GOOD)
49. Start Timer
50. Stop ACK Timer
51. <- 8 frame: ACK (BAD)
52. Timeout 6
53. -> 11 frame: DATA (Retransmission) (BAD)
54. Start Timer
55. Stop ACK Timer
56. <- 9 frame: NAK (GOOD) (NOT BETWEEN)
57. Timeout 7
58. -> 12 frame: DATA (Retransmission) (GOOD)
59. Start Timer
60. Stop ACK Timer
61. <- 10 frame: ACK (BAD)
62. 
    
63. 
    
64. <- 11 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
65. Start ACK Timer
66. Ack timeout 2
67. -> 13 frame: ACK (BAD)
68. Stop ACK Timer
69. Timeout 8
70. -> 14 frame: DATA (Retransmission) (BAD)
71. Start Timer
72. Stop ACK Timer
73. Timeout 9
74. -> 15 frame: DATA (Retransmission) (GOOD)
75. Start Timer
76. Stop ACK Timer
77. <- 12 frame: ACK (GOOD)
78. Stop Timer
79. -> 16 frame: DATA (GOOD)
80. Start Timer
81. Stop ACK Timer
82. <- 13 frame: ACK (GOOD)
83. Stop Timer
84. -> 17 frame: DATA (GOOD)
85. Start Timer
86. Stop ACK Timer
87. <- 14 frame: ACK (BAD)
88. Timeout 10
89. -> 18 frame: DATA (Retransmission) (GOOD)
90. Start Timer
91. Stop ACK Timer
92. <- 15 frame: NAK (BAD)
93. Timeout 11
94. -> 19 frame: DATA (Retransmission) (BAD)
95. Start Timer
96. Stop ACK Timer
97. <- 16 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
98. Start ACK Timer
99. Ack timeout 3
100. -> 20 frame: ACK (GOOD)
101. Stop ACK Timer
102. <- 17 frame: DATA (GOOD) (EXPECTED)
103. Start ACK Timer
104. You've uploadeded the file
105. Ack timeout 4
106. -> 21 frame: ACK (GOOD)
107. Stop ACK Timer
108. Timeout 12
109. -> 22 frame: DATA (Retransmission) (GOOD)
110. Start Timer
111. Stop ACK Timer
112. <- 18 frame: ACK (GOOD)
113. Stop Timer
114. Please type in command here:

Server Output

1. -bash-3.2$ ./Phase_4_Server
2. <- 1 frame: DATA (GOOD) (EXPECTED)
3. Start ACK Timer
4. 
   
5. -> 1 frame: DATA (GOOD)
6. Start Timer
7. Stop ACK Timer
8. <- 2 frame: ACK (BAD)
9. 
   
10. 
    
11. 
    
12. <- 3 frame: DATA (BAD)
13. 
    
14. 
    
15. -> 2 frame: NAK (GOOD)
16. Stop ACK Timer
17. <- 4 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
18. Start ACK Timer
19. Ack timeout 1
20. -> 3 frame: ACK (GOOD)
21. Stop ACK Timer
22. <- 5 frame: DATA (GOOD) (EXPECTED)
23. Start ACK Timer
24. Ack timeout 2
25. -> 4 frame: ACK (BAD)
26. Stop ACK Timer
27. <- 6 frame: DATA (GOOD) (NOT EXPECTED)
28. 
    
29. 
    
30. -> 5 frame: NAK (GOOD)
31. Stop ACK Timer
32. Timeout 1
33. -> 6 frame: DATA (Retransmission) (GOOD)
34. Start Timer
35. Stop ACK Timer
36. <- 7 frame: NAK (GOOD) (NOT BETWEEN)
37. 
    
38. 
    
39. <- 8 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
40. Start ACK Timer
41. Ack timeout 3
42. -> 7 frame: ACK (GOOD)
43. Stop ACK Timer
44. <- 9 frame: DATA (BAD)
45. 
    
46. 
    
47. 
    
48. <- 10 frame: DATA (GOOD) (EXPECTED)
49. Start ACK Timer
50. Ack timeout 4
51. -> 8 frame: ACK (BAD)
52. Stop ACK Timer
53. <- 11 frame: DATA (BAD)
54. 
    
55. 
    
56. -> 9 frame: NAK (GOOD)
57. Stop ACK Timer
58. <- 12 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
59. Start ACK Timer
60. Ack timeout 5
61. -> 10 frame: ACK (BAD)
62. Stop ACK Timer
63. Timeout 2
64. -> 11 frame: DATA (Retransmission) (GOOD)
65. Start Timer
66. Stop ACK Timer
67. <- 13 frame: ACK (BAD)
68. 
    
69. 
    
70. <- 14 frame: DATA (BAD)
71. 
    
72. 
    
73. 
    
74. <- 15 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
75. Start ACK Timer
76. Ack timeout 6
77. -> 12 frame: ACK (GOOD)
78. Stop ACK Timer
79. <- 16 frame: DATA (GOOD) (EXPECTED)
80. Start ACK Timer
81. Ack timeout 7
82. -> 13 frame: ACK (GOOD)
83. Stop ACK Timer
84. <- 17 frame: DATA (GOOD) (EXPECTED)
85. Start ACK Timer
86. Ack timeout 8
87. -> 14 frame: ACK (BAD)
88. Stop ACK Timer
89. <- 18 frame: DATA (GOOD) (NOT EXPECTED)
90. 
    
91. 
    
92. -> 15 frame: NAK (BAD)
93. Stop ACK Timer
94. <- 19 frame: DATA (BAD)
95. Timeout 3
96. 
    
97. -> 16 frame: DATA (Retransmission) (GOOD)
98. Start Timer
99. Stop ACK Timer
100. <- 20 frame: ACK (GOOD)
101. Stop Timer
102. -> 17 frame: DATA (GOOD)
103. Start Timer
104. Stop ACK Timer
105. 
     
106. <- 21 frame: ACK (GOOD)
107. Stop Timer
108. 
     
109. <- 22 frame: DATA (GOOD) (NOT EXPECTED) (NAK EXISTS)
110. Start ACK Timer
111. Ack timeout 9
112. -> 18 frame: ACK (GOOD)
113. Stop ACK Timer

=========================================== 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 find 

if(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.

Phase 6 - Implement Sliding Windows (Part 2)

What to do

1) Implement Sliding windows - Part 2

• In Phase 1, I've mentioned that when using named pipe, basic flow control is achieved. At this point of the project, you need to replace named pipe with normal pipe, and use select() to listen to the reading end of the pipes (select() does not work on named pipes). There were four named pipes, which are pipeAPPtoDLL and pipeDLLtoAPP at both client and server. We will keep the name of the named pipes and replace them with normal pipes. After the replacement, the totally number of pipes will still be four. That's because pipes are unidirectional. (On some systems (but not Linux), pipes are bidirectional: data can be transmitted in both directions between the pipe ends. According to POSIX.1-2001, pipes only need to be unidirectional. Portable applications should avoid reliance on bidirectional pipe semantics. Find the code snippet select_on_pipe.c in my google drive folder)

Structure Graph

Phase 6 Goal

Based on the code of phase 5, replace the four named pipes between Datalink Layer and Application Layer at both client and server with normal pipes. Then implement the function select() on the reading end of each pipe. The use of select() guarantees that the receiving process will read the packet from the sending process only when the pipe is ready for reading, thus keeping the receiving process from reading undesired number of bytes. 

Phase 5 - Implement Sliding Window (Part 1)

What to do

1) Implement Sliding Windows - Part 1

• For the various sliding windows protocol, we decide to implement Selective Repeat. (Check Help_Sess3_B05.pdf, the textbook and Data_Link_Layer_S12.pdf for pseudo code)
• In order for the Selective Repeat to work, we need to use the function select(). select() allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible) http://linux.die.net/man/2/select. In our case, we need select() to listen to the pipes between Datalink Layer and Application Layer, and the socket between client and server. In phase 5, let's use select() on both client and server side to listen to the reading end of the socket. We will use select() to listen to the pipes between Datalink Layer and Application Layer in the next phase. (Attached is the code snippet select_on_socket.c in my google drive folder)

Phase 5 Goal

Based on the code of phase 4, implement the function select() on both client and server end to listen to the reading end of the socket. The use of select() guarantees that the receiver will read the frame from the socket only if the socket is ready for reading, thus keeping the receiver from reading undesired number of bytes. 

Phase 4 - Randomly Insert Single Bit Error

What to do

Fulfill the requirement "randomly insert a single bit error into the frame checksum field before a frame is sent"

How to flip a random bit of a 32-bit checksum. (Need help? Please check bitTwiddle.pdf )

• Convert the CRC into a 4-byte character array 
• Randomly choose a byte of that character array and then choose a bit of that byte 
• Generate the mask for that byte
• Xor the chosen byte with the mask

Useful Resources
Bitwise operators in C, a tutorial.
http://www.cprogramming.com/tutorial/bitwise_operators.html
Generate an random integer within range in C.
http://stackoverflow.com/questions/822323/how-to-generate-a-random-number-in-c

code snippet

#include 
#include 

srand(time(NULL)); //only need to be called once for each thread
int r = rand()%range; //returns a integer between 0 and range-1, inclusive

The most efficient way to implement an integer based power function pow(int, int) (Proved correct)
http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int !!!

Convert a 4-byte char array into a 32-bit int !!!
code snippet

unsigned int CharArrToUnsignedInt(char * charArr)
{
    unsigned int i = *(int *)charArr;
}

Related Topic: The most important lesson learned in Phase 3

The client/server programs began to malfunction after I added CRC into the frame. After  transmission, the file on server side is not of the same size as the one on client side. Initially  I thought it is caused by the CRC calculation function and the related functions. I modified  some of them, but it still doesn't work. Then I started to look at the server side, and added  some code into the server program. Somehow the programs worked again. The only thing  I've added is a printf function. This is a problem that has confused me for a long time, i.e.  would the printf function affect the execution of the code besides printing out its parameters  on the standard output. The answer is yes if you are doing multiple-threaded or network  programming, because the printf function you added would cause a delay to the execution  of other part of the program.  (Check out this http://www.velocityreviews.com/forums/t665299-off-topic-strange-behaviou r-adding-printf-change-the-prograexecution.html) That's why after adding the CRC part, the program malfunctions -  the calculation of the CRC delays the sending of the frames from sender to receiver. Thus for some callings of the function recv, it does not receive the entire frame (or receive nothing). After I adding some code into the server side, the additional code caused some delays on the server side, making the server slow down its reading from the socket.  How to know if the server (or the receiving end) always read the entire frame?  Add these code after the recv function.  //Receive frame from client ssize_t numBytesRcvd = recv(clntSocket, &fmRecv, FSIZE, 0); if(numBytesRcvd<0) perror("recv() failed"); if(numBytesRcvd!=FSIZE) perror("Receivd unexpected number of bytes"); (FSIZE is the size of a frame)  Note our code does not guarantee that for each calling of function recv, the receiver would  receive an entire frame (the use of function select() introduced in Phase 4 will solve  this problem), but it will tell you when the receiver does not.

Phase 3 - Implement Cyclic Redundancy Check

What to do

1) Use Cyclic Redundancy Check (CRC) as error detection strategy. We use the CRC code provided by Michael Barr in the link below:

http://cprogramminglanguage.net/c-structure.aspx !!!

• Note the CRC in our frame is calculated based on the first seven members of a frame. Because six of them are not char-type, we need to first convert them into six 4-byte char arraies. For how to convert a 32-bit integer into 4-byte char array, please check the link below. (Note that enum is actually integer-type.) http://stackoverflow.com/questions/3784263/converting-an-int-into-a-4-byte-char-array-c. !!!

Phase 3 Goal

Based on the code of phase 2, add additional functionality. Before sending frame to server, the sender calculates CRC, and upon the receiver receives the frame, it calculates the CRC and compare it with the CRC in the receiving frame. If they don't match, print the event (in this phase, we don't insert any error). 

Useful resources

How to define enumeration in C?

http://msdn.microsoft.com/en-us/library/whbyts4t(v=vs.80).aspx

enum in C.

http://crasseux.com/books/ctutorial/enum.html

typedef in C.

http://www.cprogramming.com/tutorial/typedef.html and

http://publications.gbdirect.co.uk/c_book/chapter8/typedef.html

Implement Cyclic Redundancy Check in C 

http://prabhakargouda.hubpages.com/hub/Cyclic-redundancy-check-implementation-using-C and 

http://www.sourcecode4u.com/categories/computer-networks/37-crc-in-c and

Understanding CRC

http://www34.brinkster.com/dizzyk/math-crc.asp !!!

What is C-preprocessor (Wiki)

http://en.wikipedia.org/wiki/C_preprocessor

The C Preprocessor

http://www.cs.cf.ac.uk/Dave/C/node14.html