해당 글은 한양대학교 이석복 교수님의 과목 "컴퓨터 네트워크"를 공부하고 작성한 글입니다. 해당 강의를 직접 수강하시려면 다음 링크를 참고해주세요.
컴퓨터네트워크
인터넷을 동작시키는 컴퓨터네트워크 프로토폴을 학습한다.
www.kocw.net
파이프라인 프로토콜(Pipelined protocol)
(1) 필요한 이유
기존의 RDT 3.0은 메시지를 하나의 링크를 따라 보낸다.
이 경우 하나의 패킷이 도착하고 ACK가 돌아올 때까지, 해당 소켓은 아무런 메시지를 보낼 수가 없다.
여기서 하나의 패킷이 전송되고 ACK가 돌아올 때까지의 시간을 RTT(Round Trip Time, 왕복시간)라 한다.
RTT(Round Trip Time, 왕복 시간): 패킷망(인터넷) 상에서 상대측 호스트까지 패킷이 왕복하는데 걸리는 시간
→ 즉, 패킷 왕복 시간
기존의 상황에서는 RTT동안 아무것도 보낼 수 없다.
따라서 네트워크 활용률(Utilization)이 낮을 수밖에 없다.
ACK가 돌아올 때까지 하나밖에 못 보내서 활용률이 낮은 것이 아닐까?
패킷을 하나가 아니라 세 개씩 보낸다면 활용률도 세 배가 된다.
더 많이 보낼수록, 네트워크의 활용률도 높아진다.
그렇다면 어떻게 하면 더 많은 메시지를 동시에 보낼 수 있을까?
방법은 메시지 패킷도 동시에 보내고 ACK 패킷도 동시에 받는 것이다.
(2) 성능 개선: 파이프라인 프로토콜(Pipelined protocols)
한 번에 많은 메시지를 보내고 한 번에 응답을 받는 것이 당연히 더 효율적이다.
신뢰성 있는 파이프라인 프로토콜을 구축하기 위한 방법에는 대표적으로 두 가지가 있다.
- Go-Back-N
- Selective repeat
실제 TCP에서는 이 두 개 기법을 적절히 섞은 방법을 사용한다.
TCP의 파이프라인 프로토콜을 보기 이전에, 위 두 방법을 먼저 살펴보자.
1) Go-Back-N
Go-Back-N은 윈도우(Window)라고 해서 한 번에 전송할 범위를 지정해준다.
- 윈도우 크기(window size): 한 번에 얼마나 많은 패킷을 보낼 수 있는지를 가리킨다.
만약 윈도우 크기가 3이면 ACK가 돌아올 때까지 3개까지의 메시지를 동시에 보낼 수 있는 것이다.
동시에 여러 패킷을 전송하므로 피드백 메시지 방식도 달라진다.
- ACK(n): receiver가 n번 패킷까지 제대로 받았음을 알리는 피드백 → "cumulative ACK"
예를 들어 이제 ACK 11은 11번 패킷을 받았다는 뜻이 아니라, 이전 패킷부터 시퀀스 넘버(sequence number)가 11번인 패킷까지 모두 정상적으로 받았음을 의미한다.
0번 패킷부터 11번 패킷까지 전송을 성공했다는 뜻이다.
지금까지 누적(cumulative)된 패킷 모두에 대해 피드백을 보내는 것이다.
그런데 이렇게 변경하면 문제가 발생한다.
어느 패킷까지 전송되었는지 알 수 없는 것이다.
0, 1, 2, 3, 4, 5번 패킷을 보내는데 3번 패킷이 유실되었다고 하자.
그러면 피드백 메시지는 ACK 0, ACK 1, ACK 2까지 전송되고 나서 3번 패킷이 유실되었으므로 다음 피드백은 ACK 2, ACK 2, ACK 2이 돌아오게 된다.
3번 패킷이 유실된 것이 확실한데, 4번, 5번 패킷도 유실된 것인지 아닌지 알 수 없다.
따라서 유실되어 timeout이 발생할 시 재전송할 패킷이 불분명하다. 따라서 모두 재전송해주게 된다.
- timeout(n): n번 패킷이 유실되었을 경우, N번 패킷부터 윈도우 내에서 그다음에 있는 패킷을 모두 재전송한다.
쉽게 말하면, 3번 패킷이 유실되면 4번, 5번 패킷도 재전송하는 셈이다.
예시
위 그림에서는 윈도우 사이즈가 4로 정해져 있다.
0번 패킷부터 3번 패킷까지 순차적으로 전송한다.
sender가 3번 패킷까지 전송하고 나면 잠시 전송을 정지한다.
Go-Back-N은 ACK 메시지가 들어오게 되면 윈도우를 옮기게 된다.
따라서 1번 패킷까지는 정상적으로 패킷이 전송되어 sender는 ACK 0, ACK 1을 받고 윈도우가 재설정된다.
그에 따라 4번, 5번 패킷이 전송된다.
그러나 2번 패킷이 유실되어 ACK 2는 전송되지 않는다.
2번 이후로 3, 4, 5번 패킷이 전송되지만, 2번 패킷을 받지 못했으므로 3, 4, 5번 패킷도 버려지게 된다.
중간에 2번 패킷이 비어 있어서 순서대로 전송되지 않았기 때문이다.
2번 패킷이 유실되면서 ACK 2가 오지 않아 timeout이 발생한다.
이때, 윈도우 내에서 2번 패킷보다 뒤에 있는 것은 3, 4, 5번 패킷이므로 2, 3, 4, 5번 패킷을 재전송하게 된다.
3, 4, 5번 패킷은 정상 전송되었으므로, 재전송된 복제(duplicate) 패킷은 버려진다.
Go-Back-N 정리
Go-Back-N을 정리하면 다음과 같다.
- timeout시 윈도우 내의 모든 패킷을 재전송한다.
- timeout이 발생하면, 윈도우 사이즈(window size)가 N일 때 전송할 대상도 N만큼 다시 돌아오게 된다.
- 윈도우에 들어 있는 데이터는 버퍼(buffer)에 저장하고 있어야 한다.
- 윈도우 밖(0, 1): ACK가 왔으므로 전송이 완료됨 → 버퍼에 저장하지 않음
- 윈도우 내(2, 3, 4, 5): ACK가 오지 않아 제대로 전송되었는지 알 수 없다. → 버퍼에 저장해야 한다.
Go-Back-N의 문제점
Go-Back-N의 문제점은 정상 전송된 패킷이 버려지고 재전송된다는 점이다.
실제로는 윈도우 사이즈가 4 정도로 작지 않다.
원래라면 실패할 경우 그 패킷만 재전송하면 된다.
그러나 Go-Back-N에 따르면 한 패킷만 전송에 실패해도 윈도우 내에 있는 모든 패킷을 재전송해야 한다.
이 문제를 개선한 방법이 바로 Selective Repeat이다.
2) Selective Repeat
Selective Repeat는 패킷이 유실되어 재전송할 때 선별적으로 패킷을 재전송한다.
Go-Back-N처럼 ACK를 누적(cumulative) 방식으로 보내게 되면 어디까지 패킷이 전송되었는지 알 수 없다.
따라서 Selective Repeat에서는 패킷을 받을 때마다 각각 ACK를 전송시켜준다.
예를 들어 7번 패킷을 받으면 ACK 7을 보내는데, 여기서 ACK 7은 7번까지 모두 받았다는 것이 아니라 7번 패킷을 받았다는 뜻이다.
ACK 7을 받게 되면 7번 패킷을 윈도우에서 해제해준다.
그러나 패킷이 순서대로 정렬되어야 하므로 패킷이 유실되었을 때, 그 패킷이 도착할 때까지 다음 순서의 패킷을 임시로 저장해 줄 필요가 있다.
따라서 2번 패킷을 받지 못하고 3, 4번 패킷을 받았을 때 이를 recv 버퍼에 저장해주게 된다.
예시
위 그림이 바로 2번 패킷이 유실된 상황이다.
똑같이 윈도우 사이즈가 4인 상황이다.
2번 패킷이 유실된 이후 receiver는 3, 4, 5번 패킷을 받게 된다.
순서대로 저장하기 위해 2번 패킷이 도착할 때까지 3, 4, 5번 패킷은 버퍼에 저장(buffered)해둔다.
sender는 timeout이 발생하면 2번 패킷만을 재전송한다.
이때 receiver가 2번 패킷을 받게 되면 2번 패킷과 더불어 버퍼의 내용(3, 4, 5번 패킷)도 함께 저장해준다.
이렇게 해서 0, 1, 2, 3, 4, 5번 패킷이 순서대로 정렬되게 된다.
특이한 점은 이미 전송되어 ACK가 돌아온 패킷은 sender가 윈도우에서 해제한다는 점이다.
ACK 5까지 오고 나면 2번 패킷을 제외한 0, 1, 3, 4, 5번 패킷은 윈도우에서 해제되고, sender는 유실된 패킷인 2번 패킷만을 버퍼에 저장하고 있다.
이렇게 하면 쓸모없이 같은 패킷을 두 번 전송할 필요가 없다.
3) 딜레마
그러나 Go-Back-N, Selective repeat과 같은 파이프라인 프로토콜에는 문제점이 있다.
바로 시퀀스 번호(Seq #)가 무한하지 않다는 점이다.
시퀀스 번호를 전달하기 위해서는 세그먼트 헤더에 정보를 넣어야 하는데, 더 큰 수를 지원하려면 더 많은 비트가 필요해져서 헤더 또한 길이가 길어지게 된다.
그래서 적당한 값으로 설정해야 한다.
대략 window size가 N이라면 시퀀스 번호는 N*2 정도가 필요하다.
4) TCP에서
Selective repeat에도 단점은 있다.
- 윈도우 내의 모든 패킷마다 타이머를 설정해야 한다.
- 실제로는 몇백 개 이상의 패킷을 전송하고 저장하게 된다.
그로 인해 패킷마다 타이머를 설정하는 것이 어렵다.
따라서 TCP에서는 약간 변화를 준다.
- 윈도우 내에서 대표 timeout 타이머를 설정한다.
- cumulative 기법을 사용함
다음 포스팅에서는 실제로 TCP에서 어떤 기법을 사용하는지 알아보자.
출처
RTT
RTO, Retransmission Timeout, 재전송 타임아웃, Karn Algorithm, 카른 알고리즘, Karn 알고리즘, 지수 RTO 후퇴
www.ktword.co.kr
'컴퓨터과학 > 네트워크' 카테고리의 다른 글
| 3-5. 전송(Transport) 계층: TCP 2 (0) | 2021.10.28 |
|---|---|
| 3-4. 전송(Transport) 계층: TCP (2) | 2021.10.17 |
| 3-2. 전송(Transport) 계층: 신뢰성 있는 데이터 전송(RDT) (0) | 2021.10.10 |
| 3-1. 전송(Transport) 계층: 다중화(Multiplexing)/역다중화(Demultiplexing) (0) | 2021.10.10 |
| 2. 소켓 프로그래밍 (0) | 2021.10.06 |
댓글