- Error를 검출한 이후에, what should the receiver do?
ARQ
Stop-and-Wait
- ACK(Acknowledgement) frame
만약 frame이 성공적으로 수신되었다면, 수신자는 발신자에게 ACK frame을 보낸다. - 발신자가 ACK frame을 받았다면, 보낸 frame이 수신자에게 성공적으로 도착했음을 의미한다.
Error case
- 만약 frame이 수신자에게 못가면, 수신자는 아무것도 못받고, ACK도 못보내준다.
- 만약 frame이 수신자에게 성공적으로 갔는데 ACK이 발신자에게 못가면.
Sender 입장에서 이 두 case는 똑같다.
Sender's action
- After sending a frame, wait for T seconds. (timeout period)
- 이 시간 안에 ACK가 오면, send the next frame
- 이 시간 안에 ACK가 안오면, retransmit(재전송) the frame
Timeout period
- 제대로 frame 받아서 ACK 잘 보내줬는데, T가 너무 짧아서 sender가 재전송하면 그건 너무 억울하다.
- 그래서 timeout period가 적당히 길어야 한다.
- Timeout should be based on RTT(Round-Trip Time)
-
RTT : Duration of time between the sender starts sending a frame and finishes receiving an ACK
= transmission time of frame (frame size / capacity)
+ propagation time of frame (거리 / 속도)
+ transmission time of ACK
+ propagation time of ACK
+ processing time at sender and receiver -
Typical time out period T = RTT + margin
Receiver's perspective
- frame이 도착했다
- 조금 이따, 다른 frame이 도착했다.
- 이게 next frame일까?
- 아니면 재전송된 같은 frame일까?
Normal case
S : frame 보낸다
R : frame 받고, ACK 보낸다
S : ACK 받고, 다음 frame 보낸다
R : frame 받는다
- 이러면, next frame이다.
Retransmission case 1 : frame is lost
S : frame 보낸다
R : (frame 못받았어)
S : timeout called, frame 재전송한다
R : frame 받고, ACK 보낸다
S : ACK 받고, 다음 frame 보낸다
R : frame 받는다
- 이러면, next frame이다
Retransmission case 2 : ACK is lost
S : frame 보낸다
R : frame 받고, ACK 보낸다
S : ACK 못받고, timeout called, frame 재전송한다
R : frame 받고, ACK 보낸다
- 이러면, retransimtted frame이다
Retransmission case 3 : ACK is arrived after timeout
S : frame 보낸다
R : frame 받고, ACK 보낸다
S : timeout called, frame 재전송한다
S : 이제서야 ACK 받고 next frame 보낸다
R : frame 받고, ACK 보낸다
R : frame 받고, ACK 보낸다
- 이러면, retransmitted frame이다. (지금 두번째 받는 frame 얘기중이야)
결론적으로, 이게 next인지 retransmitted인지 알 수가 없다!!
Solution
- frame에 sequence number를 붙인다.
- each frame마다 sequence nubmer가 커진다.
- ACK도 sequence number가 있는데, 이건 "next expected frame"을 의미한다.
- receiverrk frame(0)을 받으면, ACK(1)을 보낸다
"다음으로 1 줘"
- stop and wait ARQ 에서 sequence number는 [0, 1]이다
frame(0) -> frame(1) -> frame(0) -> frame(1) -> ...
Retransmission case 1 : frame is lost
S : frame(0) 보냄(-> lost)
R : 못받아
S : timeout, retransmits frame(0)
R : frame(0) 받고, ACK(1) 보내
S : ACK(1) 받아
- No problem
Retransmission case 2 : ACK is lost
S : frame(0) 보냄
R : frame(0) 받고, ACK(1) 보내(-> lost)
S : timeout, retransmits frame(0)
R : frame(0) 받고, ACK(1) 보내
S : ACK(1) 받아
- Problem solved
Retransmission case 3 : ACK is arrived after timeout
S : frame(0) 보냄
R : frame(0) 받고, ACK(1) 보내
S : timeout, retransmits frame(0)
S : 이제서야 ACK(1) 받고, frame(1) 보내
R : frame(0) 받고, ACK(1) 보내. 이미 frame(0)가 있기 때문에 frame(0) 하나 버려
R : frame(1) 받고, ACK(0) 보내
S : ACK(1) 받고, ACK(1) 버려. 이미 아까 늦게 ACK(1) 받은거 있어
S : ACK(0) 받고, frame(0) 보내
- Problem solved
Performance
-
전송률이 그렇게 좋진 않다.
Q. Suppose a system uses stop-and-wait ARQ. The link bandwidth is 1Mbps, and RTT is fixed at 20ms. Assuming no error and infinite timeout, what is the throughput? Suppose frame size is 1000 bits
A. 20ms에 1frame(1000 bits) 전송
-> 1s에 50,000 bits 전송
-> 50,000 bps
bandwidth와의 비율을 계산하면 1/20. -
Resource Waste
frame을 보낸 후, sender는 ACK가 올 때까지 계속 기다려야 한다.
Go-Back-N
- 겨우 frame 하나 보내려고 ACK을 기다리는 건 시간 낭비다
- Send multiple frames in order to fill up the pipe
- 특정 frame에 오류가 생기면, disregard all frames sent after the lost frame, and restart from there
Send Window
- Sender can only send frames inside the window
- ACK를 받으면, window slides to the right
Receive Window
- Receiver can only receive frames inside receive window
- frame 하나.
- ACK을 보내면, window slides to the right
Sequence Number Range
- range가 너무 넓으면, sequence number를 표현하기 위해 너무 많은 bits가 필요하다.
- If sequence number range is [0, ..., N-1], then log2N bits are needed
- 그렇다고 너무 좁으면, receiver가 new frame과 retransmitted frame을 구분하기 어려워진다.
- 일단, send window size가 N이면, sequence number range는 N보다는 커야 한다!
- 반대로, sequence number uses m bits, the send window size must be less than 2m
Normal case
- 중간에 ACK2가 버려지긴 했지만, 그 이후에 ACK3를 받고 Sender는 frame 2까지 정상적으로 받았음을 확인할 수 있다.
Timeout case
Problem
- timeout이 발생하면, 맨 처음으로 돌아가서 다시 하나씩 다 보내야 한다.
1번 하나 못 보냈는데, 2345를 다 버리는 상황이 된다. - 이건 receive window size가 1이기 때문이다.
Selective repeat
- Go-back-N의 문제점을 보완하여, receive window size를 N으로 한다.
- Typically, send window size = receive window size
- 즉, receiver 입장에서, (현재 window range가 [3,... 10]이라 하자)
3을 못받았더라도 4, 7, 9가 들어오면 accept한다. - 그러다 다시 3을 받으면, receiver는 ACK(5)를 전송한다. 다음 받아야 하는 frame을 알려줘야 하기 때문이다.
- send window size와 동일하게,
If sequence number uses m bits, both send window and receive window should be less than or equal to 2m-1
NAK mechanism
- NAK : Negative acknowledgement
- receiver가 NAK(1)을 보낸다는 건, it means that a subsequent frame was received without frame(1)
- NAK이 없으면, sender는 timeout까지 기다려야 한다.
- 일단 frame별로 timer를 사용한다
- receiver window의 맨 처음 frame이 들어올 때만 ACK을 보내주고,
앞에 빵꾸가 하나 생긴 상태로 뒤의 frame이 들어오면 NAK을 보내준다.
- 위 그림에서 frame 1을 못 받은 채로 frame2를 받으니까 일단 저장은 하고 NAK(1)을 보내준다.
-
그 다음 frame3을 받았을 때는 NAK(1)을 또 보내진 않는다. do nothing
NAK을 계속 보내면 좋긴 한데, 좀 과하다.
NAK을 맨 처음 한 번만 보내면 좋긴 한데, 여기서 오류 생기면 timer 끝날 때까지 기다려야 한다.
어쨌든 우리는 후자의 방법을 선택한다 -
결국 frame1을 받았으면 ACK(4)를 보내줌으로써 앞에 1, 2, 3을 모두 받았다는 걸 알려준다
-
When does the receiver send ACK?
: When a frame is recevied, and receiver has all the previous frames
