본 내용은 Computer Networking: A Top-down Approach 를 읽고 공부한 내용입니다.
TCP/UDP에 이어 이번에는 RDT(reliable data transfer)에 대해 알아보자! 과정이 조금 복잡할 수 있다
목차
1. rdt의 원리
2. rdt 1.0: 오류 없는 채널에서의 신뢰적인 데이터 전송
1) 송신/수신 방법 - event, action
3. rdt 2.0: 비트 오류가 있는 채널상에서의 신뢰적 데이터 전송
1) 송신/수신 방법 - ACK, NAK
2) rdt 2.0의 치명적 결점
3) rdt 2.1: sequence number로 구분하여 전송
4) rdt 2.2: sequence number로 구분하여 전송+a NAK-free protocol
4. rdt 3.0: 비트 오류가 있는 손실 채널상에서의 신뢰적 데이터 전송
1) 송신/수신 방법 - timer
2) rdt 3.0의 performance와 한계
5. GBN
1) 송신/수신 방법 - 슬라이딩 윈도우
6. SR
1) 송신/수신 방법 - 슬라이딩 윈도우+버퍼
2) SR의 딜레마
1. rdt의 원리
신뢰적인 데이터 전송을 위해서는 아래와 같은 프레임워크(서비스 모델)로 구현되어야 한다.
맨 왼쪽 그림과 같이 랜선으로 end-to-end 연결을 한다면 이 서비스는 매우 신뢰적이라고 할 수 있겠지만, 현실은 그렇지 못하다. 따라서 여러 rdt 방법을 사용하여 극복한다.
그럼 어떻게 reliability를 제공할 수 있을까? 일단 비트가 깨지는 상황이 생길 수 있다. 이를 위해 checksum을 이용해 에러가 났다/괜찮다 정도는 체크해줄 수 있다. 또한 ACK+timer/NAK를 이용해서 정보가(패킷이) 유실되었는지를 확인할 수 있다. 또한 순서가 어긋나서 도착하지 않는지 중복된 순서가 오지는 않았는지 확인해야 할 것이다.
아래의 다양한 명령어 이름(call, call back)에 대해 조금 알아두자!
_send(): rdt의 송신측이 호출되고 있다는 의미이다.
rdt_rcv() : 패킷이 채널의 수신 측으로부터 도착했을 때 호출된다.
deliver_data(): rdt 프로토콜이 상위 계층에 데이터를 전달하려고 할 때 호출된다.
udt_send(): rdt의 송신/수신 측 모두 다른 쪽에 패킷을 전송할 때 호출한다.
2. rdt 1.0 : 오류 없는 채널에서의 신뢰적인 데이터 전송
2.1 송신/수신 방법 - event, action
이 프로토콜은 하위의 채널이 완전히 신뢰적인 경우를 가정한다. 즉, 위에서 확인했던 bit error도 packet loss도 없다.
아래 그림에서 ---(작대기) 위에 있는 건 event, 아래에 있는 건 action을 의미한다.
ex. 알람이 울려서(event) -> 일어난다(action)
송신(sender)측에서는 계속해서 상위(주로 애플리케이션) 계층으로부터의 호출을 기다린다. 그러다가 상위 계층으로부터 data를 rdt_send로 받게 되면, data 패킷을 만들어 udt방식 send로 보내게 된다.
수신(receiver)측에서도 하위 계층으로부터의 호출을 기다린다. 이후 하위 채널로부터 프로시저 호출로(rdt_rcv) 패킷을 받으면, 패킷으로부터 데이터를 떼어내어(extract) 상위 계층에 적절히 전달한다.
3. rdt 2.0 : 비트 오류가 있는 채널상에서의 신뢰적 데이터 전송
3.1 송신/수신 방법 - ACK, NAK
이번에는 비트 오류가 생길 수 있는 상황이다. 그러면 "뭐라고? 다시 보내. OK" 등의 의사소통이 필요할 것이다.
따라서 이 과정에서는 ACK, NAK, retransmission 등을 사용한다.
아래 그림을 보며 상황을 파악하자!
- sender(송신자) 측에서는 데이터와 checksum(오류 검출을 위함) 필드로 packet을 만들어 udt로 보낸다. isACK(rcvpkt) 에서 볼 수 있듯, ACK를 제대로 받은 상황이다. 이럴 경우 sender(송신)측에서는 아무 액션도 취하지 않는다. (Λ = no action ) 한편 isNAK(rcvpkt) 나크를 받았다면, 재전송한다.
- receiver(수신자) 측에서는 에러(corrupt)가 났으면 NAK, 안 났으면 ACK를 보낸다.
3.2 rdt 2.0의 치명적 결점
현실적으로 생각해보면 이 ACK, NAK도 하나의 전달방식이다. 이도 깨질 수 있다.
따라서 ACK와 NAK가 corrupted 되었을 때에는 sender는 receiver에게 어떤 일이 일어난 건지 알 수 없다. 또한 이런 상황에서 데이터가 이미 잘 갔는데 ACK 자체가 깨져서 재전송을 할 경우 중복 오류가 생길 수 있다. 이 일을 극복하기 위해 현재것, 이전 것을 sequence number로 구분하여 전송하는데 이 때 송신자/수신자 양쪽의 싱크를 맞추기 위해서 stop and wait(보내고 난 후 저쪽에서 반응이 오기 전까지 기다린다)를 하게 된다.
그럼 이 sequence number로 구분하여 전송하는 rdt 2.1의 여러 경우를 살펴보자.
3.3 rdt 2.1: sequence number로 구분하여 전송
에러가 없을 경우
sender는 패킷을 보내고, 0번 ACK가 오기를 기다린다. 그리고 receiver는 0번 ACK를 보낸다.
sender는 이 ACK를 받은 후에야 1번과 관련한 패킷을 보내고 또 1번 ACK가 오기를 기다린다. receiver는 이번에도 1번 ACK를 보낸다.
이 0과 1을 활용하여 뱅글뱅글 돌게 된다. (단 두개의 sequence number!)
위 과정에서 이번에는 0번이 깨져서 receiver 받을 때 1. ACK가 깨져서 오거나 2. NAK가 왔다. 따라서 sender 또한 corrupted된 신호가 왔다. 이럴 때에는 sender 쪽에서 Retransmission(재전송)한다.
이번에는 receiver가 받는 건 잘 받아서 ACK를 날렸는데 해당 ACK가 sender쪽으로 가면서 1.ACK가 깨져서 가거나 2. NAK가 갔다. 따라서 재전송하였는데 이 때에는 duplication이 발생한다. 그러면 "아냐, 나 잘 받았어" 하고 ACK를 다시 보낸다.
근데 이걸 또 깨졌다고 하면, 재전송이 2번 일어난다고 보면 된다.
이 rdt 2.1은 sequence number가 사실상 0과 1 뿐이다. 이는 stop and wait 방법을 채택하기 때문에 가능하다. 하지만 생각해보면 가장 마지막 패킷의 경우에는 이 0과 1에서 혼동이 와서 전송이 제대로 이루어지지 않을 수 있다.
3.4 rdt 2.2: sequence number로 구분하여 전송+a NAK-free protocol
이번에는 NAK를 쓰지 않는다. 그냥 ACK만 사용하여 ACK(1) -- 그 전 꺼까지는 잘 받았어요. ACK(0) -- 방금 거까지 잘 받았어요 로 상황을 확인할 수 있다.
4. rdt 3.0 : 비트 오류가 있는 손실 채널상에서의 신뢰적 데이터 전송
4.1 송신/수신 방법 - timer
데이터가 아예 유실이 생기는 경우 송신자로부터 어떠한 응답이 오지 않을 수 있다. 이 때에는 위에서 본 ACK, sequence num이 아닌 timer 등의 수단으로 극복한다.
수신 측은 2.2와 동일하다.
반면 송신 측은 계속 원하는 답이 오지 않으면 무한루프를 돌리다가 time out 시켜버린다.
그런데 이 때 time out에도 문제가 발생할 수 있다. 이는 두 개의 상황 premature timeout / delayed ACK 로 나뉜다.
아래 그림에서, 왼쪽을 보자. 초록색 ack1을 못 받아서 timeout이 난 상황이라 다시 pkt1에 대한 요청을 보냈다. 근데 timeout 전에 와야했을 ack1이 와버렸다. 이 순간부터 전부 duplicated가 생기게 된다.
이를 위해 왼쪽 그림의 노란색 부분을 도입하였다. 만약 ack0을 기다리고 있는 도중 ack1이 오면 일단 아무것도 하지 않는 것이다. 이 이후의 duplicated를 방지하기 위해서!
이번에는 오른쪽을 보자. 우리가 나중 응답을 받기 전에 rcv_pkt을 기다리는 도중 이미 ack1이 왔다. 이 때도 그냥 아무것도 하지 않는다. 사실 당연하다!
4.2 rdt 3.0 Performance와 한계
실제로 패킷을 모두 전송하는 데 필요한 시간은 8 마이크로초이고, 실제 사용한 시간은 30 마이크로초에 육박한다. 따라서 네트워크의 효율/사용률은 0.00027이다. 사용하는 실질적인 시간은 아래 파란색에 해당하고, 나머지 시간은 대부분 놀고 있다. 받을 때까지 아무것도 안 하고 낭비하는 시간이 많음을 알 수 있다.
이를 해결하기 위해서는 굳이 하나씩 확인하기 전에 쭉 받으면 될 거다. 근데 이런 경우 한 번 오류가 나면 앞에 오류났던 것부터 또 쭉 다시 받아와야 한다. 이것이 바로 pipeline 방식으로 아래에서 확인할 Go Back N과 selective repeat에 해당한다.
5. GBN
5.1 송신/수신 방법 - 슬라이딩 윈도우
슬라이딩 윈도우 알고리즘+timer를 활용한다.
이 알고리즘을 활용해 아래에서 sender와 receiver끼리 통신하며 위에 있던 노란색은 초록색으로 바꾸고, 파란색은 하나 늘려 윈도우를 한 칸씩 오른쪽으로 움직이게 된다. 그 과정이 아래에 적혀 있다.
에러가 나올 때에는 송신측에서는 아무것도 하지 않고, 수신측에서는 여기까지 밖에 못 받았어라는 ACK를 보낸다. (ex. 6번 패킷을 받아야 하는데 7,8,9가 올 때)
6. SR
6.1 송신/수신 방법 - 슬라이딩 윈도우+버퍼
GBN과 SR의 가장 큰 차이는 buffering이다. SR에는 송신 쪽에서 buffering을 사용한다. 즉, 이 슬라이딩 윈도우가 수신 쪽에도 존재한다!
수신자 입장에서 색깔은 다음을 의미한다.
자주색 : 수신자가 기대한 패킷이 아닌데(out of order, 이빨 빠짐) 일단 저장하고 ack를 보낸 상태
회색 : 아직 못 받음
파란색 : 더 저장 가능한 공간
6.2 SR의 딜레마
sequence number의 재사용 문제 때문에 딜레마가 생길 수 있다.
이로 인해 SR에서 sequence number 는 window size의 두 배보다 커야 한다.
반면 GBN은 어차피 슬라이딩 윈도우를 한 개만 쓰므로 window size 이상만 되어도 상관 없다.
'CS > 네트워크' 카테고리의 다른 글
| [네트워크] Network Layer : 데이터 평면 (0) | 2023.06.13 |
|---|---|
| [네트워크] 혼잡 제어 (0) | 2023.04.23 |
| [네트워크] UDP와 TCP (2) | 2023.04.22 |
| [네트워크] 애플리케이션 계층-4 (0) | 2023.04.21 |
| [네트워크] 애플리케이션 계층-3 (2) | 2023.04.17 |
