transport 계층의 가장 중요한 오류 복구에 대해서 다룰 예정
Stop and wait ARQ
오류 복구 개념
정보 전송 단위
- datagram : IP, UDP
- segment : TCP+) 일부는 링크 계층에서 오류 복구를 하는 경우가 있지만, 대부분은 TCP에서 이루어진다. 따라서 이 정리에서는 전송 단위를 segment와 TCP를 기반으로 둘 것임.
TCP 세그먼트 구조 (TCP 설명 나중에 할 예정)
segment error
- 세그먼트 훼손 : 훼손된 segment 도착(checksum으로 확인)
- 세그먼트 손실 : segment 미도착 (중간 통신장치의 buffer overflow)
segment 수신 확인
- segment 정상 수신 -> 수신 확인(ACK) segment 회신
- 훼손 segment 수신 -> 폐기 -> 미수신
- segment 미수신 -> 인지 불가 (중간에 훼손된 것인지, 안 보낸 것인지 인지 불가)
ACK(acknowleegement)
- 수신자가 data segment의 정상 수신을 확인하기 위하여, 송신자에게 보내는 특수한 segment
segment 미수신 확인
- segment 전송 후, timer 개시
- timer 종료 시까지, ACK 미도착하면, 정상적으로 도착하지 않았다고 생각
timer 설정
- RTT(Round Trip Time)와 연계된 함수
- RTT : segment 보내고, ack를 받기까지의 시간
정리하면, 송신자가 segment를 보내는 동시에 timer를 설정하고, 해당 timer가 종료될 때까지 ack가 오지 않으면, 재전송을 하겠다.
오류 segment 복구 절차
- segment 전송, timer 시작
- segment timer 종료할 때까지 ACK 미도착
- segment 재전성하고, tiemr 재시작
Stop and Wait ARQ (Automatic Repeat Request)
: 오류 복구의 하나의 알고리즘!
ARQ
- Automatic Repeat Request : 내가 ack segment를 정해진 시간 내로 받지 못하면, 다시 requset segment를 보내주겠다. (그런데 stop and wait 방식으로 진행하겠다.)
송신자
- segment 송신 후, 복제본을 buffer에 유지
- 재전송 timer 시작
- timer 종료 전, ACK 수신하면, 복제본 폐기/timer 종료
수신자
- 정상 segment 수신 시, ACK 회신
문제점
- ACK segment에 오류 발생 시, 중복 전송
- 수신자 중복 segment 구분 불가
수신자에게 동일한 segment가 올 경우, 2번의 동일한 segment요청이 온 것인지, 처음에 error가 나서 이전에 온 것과 동일한 segment요청이 온 것인지 알 수 있는 방법이 없다. -> 이를 해결하고자, SN을 추가로 보내주게 되었다.
Stop and Wait ARQ with SN(Sequence Number)
SN(Sequence Number) : 순서번호
- 각 segment에 대한 순서 번호 : 동일 종류 segment간 구분 가능
- 송신 SN : 현재 송신 segment 번호
- ACK SN : 다음 송신 segment 번호 (송신SN +1)
송신 SN과 ACK SN
Q) 여기서 그러면, 순서 번호는 몇 bit가 되어야 하는가? 송신측에서 무제한적으로 segment를 보내면, bit가 무제한으로 커지지 않는가?
A) SN 범위: [0, 1] (1 bit)
사진처럼.. 정상적으로 왔다면, 같은 segment가 송신되었을 대, 동일한 SN가 반환될 건데, 다른 SN이 오면, 중복해서 온 것임을 알 수 있다.
(segment:0 -> ACK:1 -> segment:1 -> ACK:0 -> segment:0 -> ACK:1 -> .. ::이렇게 되는게 정상)
(segment:0 -> ACK:1 -> segment:0 -> ACK:1 -> .. :: 이건 손실된 거!)
문제점 : 낮은 링크 사용 효율성
- ACK가 도착할 때까지 전송 대기
- 대기 시간 동안 link 미사용 -> link 사용률 저하
쉬지 않고 보내면 20000 bit.
그런데 stop and wait 쓰면 1000 bit. ::> 비효율!
Go-Back-N ARQ
pipelining
- 개념 : ACK가 회신되기 전, RTT 동안 링크에 M개의 segment를 전송
- 장점 : linkn 효율 제고 (stop-and-wait보다 M배 높은 효율)
- stop-and-wait는 하나씩 와리가리, Go-Back-N은 한번에 여러개 보내서 와리가리, Selective_Repeat은 여러개 보내서, 에러난 것만 선택해서 와리가리
요구사항
- 최대 pipelining segment 수 M(송신 윈도우) 보다 큰 순서번호(SN) 사용
- SN 필드 m bit: 2^m > M (m과 M의 관계는 오류 복구 유형에 따라 결정)
- 순서번호: [0, 2^m - 1], mod 2^m)
SN 0에 대해 ACK가 왔으니, 다음 SN을 보내는 거!
오류복구 유형
- Go-Back-N ARQ
- Selective-Repeat ARQ
Go-back-N 작동 원리
: N으로 돌아가서 재전송 하겠다.
- 오류 segment부터 이후의 모든 segment를 재전송
송신자 동작 절차
- ACK가 회신 되는 RTT 동안 링크에 최대 M(송신 윈도우)개의 segment를 전송하고, buffer에 유지
- ACK 수신하면, 해당 segment를 버퍼에서 제거하고, 송신 가능 순서번호 범위를 1씩 이동 (송신 윈도우 sliding)
- segment 재전송 timer가 종료될 때까지 ACK가 수신되지 않으면, 해당 segment로부터 송신 윈도우의 모든 segment 재전송
- sliding : slide타는 것처럼 한개씩 차례차례 넘어가는 것을 의미함.
송신 윈도우(send window)
- 송신 가능 순서번호 범위
- 송신 후, 버퍼에 유지되어야 할 segment 범위
송신자 버퍼 관리
S size : 송신 슬라이딩 윈도우 크기 (send sliding window size)
- ACK 없이 송신 가능한 최대 segment 수
- S size = 2^m - 1 (m은 순서번호 필드 크기(bit수) )
S f : ACK가 수신되지 않은 첫번째 segment의 순서 번호
- ACK가 수신될 때마다 Sf = (Sf + 1) mod 2^m
S n : 다음 송신 segment의 순서 번호
- segment를 송신할 대마다 Sn = (Sn + 1) mod 2^m
송신 버퍼
[Sf, Sn -1] segment를 재전송하기 위해 buffer에 유지
수신자 동작 절차
- 다음 순서번호 Rn의 segment를 정상적으로 수신하면, ACK(Rn+1) 회신
- 다음 순서번호 Rn이 아닌 다른 segment가 올 경우, 모든 segment 폐기 -> 누적 수신확인(Accumulative ACK)
수신자 버퍼 관리
- Rn : 다음에 수신할 segment 순서번호
- segment가 수신될 때마다 Rn = (Rn + 1) mod 2^m
- 수신 윈도우 크기 : 1
- 수신자 buffer size : 1
순서번호는 2^m - 1 이하여야 한다!
장점
- stop-and-wait 대비 고효율성
- 간단한 수신자 버퍼 관리 (다음 segment 수신용 버퍼)
단점
- 오류 segment 이후 도착한 정상 segment 재전송
-> 불필요한 재전송 회수 증가
-> link 효율 저하
::> 이를 해결하고자, selective_repeat ARQ 등장
Selective_Repeat ARQ
: 오류(손실)가 일어난 segment만 선택적으로 재전송 하겠다.
요구사항
- 최대 파이프라이닝 segment 수: M(송신 윈도우) 보다 큰 순서번호 사용
- SN 필드 m bit: 2^m > M (m과 M의 관계는 오류 복구 유형에 따라 결정)
- 순서번호: [0, 2^m -1], mod 2^m
오류 복구 유형
: Go-back-N ARQ
: Selective-Repeat ARQ
Selective_Repeat 작동 원리
개념 : 오류 segment만 재전송
송신자
- ACK가 회신되는RTT동안 링크에 최대로 송신 윈도우 크기인 S size개의 segment를 전송
- 누적 ACK 수신하면, 송신 윈도우를 누적 ack 수만큼 이동
- 비누적 ACK 수신하면, 해당 segment의 ACK 수신 사실 기록
- segment 재전송 timer가 종료될 때까지 ACK가 수신되지 않으면, 해당 segment만 재전송
송신 윈도우
- 송신 가능 순서 번호 범위
- 송신 후, 버퍼에 유지되어야 할 segment 범위
누적 ACK
- 송신 윈도우 내에서 누적적으로 순서 번호가 맞는 ACK
비누적 ACK
- 송신 윈도우 내에서 누적적으로 순서 번호가 맞지 않는 ACK
ex)
0123 seq가 왔고, ack로 01234 보냈어 :: 누적ACK
이후 5678 seq 왔는데, 678이라는 ack가 왔어. :: 비누적ACK (이전 것에서 연결되는 5가 빠지고 왔기 때문에.. 그 중도의 값이 누락되어 오는 것을 비누적 ACK라고 한다.)
수신자 동작 절차
- 송신 윈도우와 동일한 크기의 수신 윈도우 R size 유지
- 누적 정상 segment를 수신하면, ACK를 회신하고, 누적 정상 segment 수만큼 수신 윈도우 이동
- 비누적 정상 segment를 수신하면, ACK를 회신하고, 해당 segment buffer에 유지
수신 윈도우: R size
- 수신 가능한 segment 범위
- 송신 window size와 동일
수신자의 buffer 관리
- 비누적 정상 segment를 수신 buffer에 유지
- 다음 수신 가능 segment : 수신 buffer에 유지되고 있지 않은 수신 윈도우 내의 모든 segment
수신 윈도우 크기
: 8
- 수신된 비누적 정상 segment : 4,7,9
Q)여기서 왜 R size가 2^m -1 이 아니라 2^(m-1)이 되었는가?
그니까, 누적이면, sliding하고, 비누적 오면, buffer 유지시켰다가, 그 비누적 중에 손실되었던 놈 채워지는 순간 sliding 해버리는 게 selectvie_repeat ARQ라는 거잖아?
SN 필드 크기가 m bit일 때, 송신 윈도우 크기 : S size
S size의 최대 크기 = 2^(m-1)
그러니까, 2^(m-1)+1이 SN이면, 수신측에서 3번 제대로 보냈는데, receiver쪽에서 ack가 하나도 안 날아온 경우,, sender는 제대로 보냈구나~ 라고 착각하게 된다고.. 왜? 처음 보낸 segment와 동일한 걸 보내주게 되기 때문에..!
