[네트워크] #12 RDT (신뢰성 있는 데이터 전송), RDT 오토마톤 표현, 파이프라인 전송

목차

1. 신뢰성 있는 데이터 전송 원칙
2. RDT에 대한 유한 상태 머신(오토마톤) 표현
3. 파이프라인 방식의 고신뢰도 전송 프로토콜

---

1. 신뢰성 있는 데이터 전송 원칙

a. Provided service

1. 수신자가 메시지를 만들어 세그먼트 단위로 쪼갬
2. 신뢰성 있는 채널로 데이터를 전송 TCP 서비스가 Reliable 한 서비스를 만들어 줌

 

하지만 현실은 다름, 호스트가 떨어진 원격지에 있기 때문에 전송 계층을 통해 바로 데이터를 전송할 수 없음→ 네트워크 계층을 거처야 함

네트워크 계층은 신뢰할 수 없음

무수히 많은 라우터에 오류가 있을 수도 있고 해커들도 존재

현실적으로 TCP의 신뢰성 있는 서비스는 b와 같은 형태로 이루어짐

 

b. Service Implementation

1. 애플리케이션은 전송 계층의 TCP 서비스가 제공하는 rdt_send() api를 호출함
2. 응용 계층에서 생성한 메시지가 세그먼트로 쪼개져서 전송 계층으로 전달됨 이 세그먼트를 다른 호스트로 보내려면 네트워크 패킷을 만들어서 보내야 함
3. 네트워크 채널을 이용하여 데이터를 보냄 → udt_send() 사용 (rdt 요청을 받았어도 네트워크를 통해 데이터를 보낼 때에는 어쩔 수 없이 udt로 데이터를 보내야 함)
4. 세그먼트가 패킷이 되어 네트워크를 지나감
5. rdt_rcv()를 통하여 패킷을 수신함
6. 패킷을 받는 쪽의 전송 계층에서 에러를 체크함 에러가 있다면 재전송 요청을 보냄
7. deliver_data를 사용하여 세그먼트를 메시지로 합쳐서 응용 계층으로 전송함

 

unreliable 한 채널을 통해 reliable 한 데이터를 보낼 수 있는 것(b)이 TCP 프로토콜의 기본 개념

---

2. RDT에 대한 유한 상태 머신(오토마톤) 표현

유한 상태 기계(유한 오토마톤, 복수형: 오토마타)

state: 동그라미로 표현 / e/a: 위쪽의 event, 아래쪽의 action

컴퓨터 프로그램과 전자 논리 회로를 설계하는 데이 쓰이는 수학적 모델

간단히 ‘상태 기계’라고 함

state: 주어진 시간의 상태

event: 다른 상태로 변화하는 계기

action: 사건에 의해 상태가 변하는 것

 

rdt1.0: a Perfectly Reliable Channel

a.

state: 응용 계층에서 오는 데이터 대기 중

event: rdt_send() 데이터 도착(함수 호출)

action: make_pkt() 패킷 생성, udt_send() 패킷 전송

 

b.

state: 네트워크 계층에서 오는 데이터 대기 중

event: rdt_rcv() 패킷 도착(함수 호출)

action: extract() 압축 풀기, deliver() 응용 계층으로 데이터 전달

 

rdt2.0: a Channel with Bit Channel

비트 에러의 가능성이 있는 상황

ARQ(Automatic Repeat reQuest) 프로토콜

데이터를 잘 받았으면 ACK(acknowledgement)

에러가 있으면 NCK(negative acknowledgement)

 

송신자가 ACK 또는 NAK 대기 상태일 때 상위 계층에서 더 많은 데이터를 얻을 수 없음 → rdt2.0을 중지 및 대기 프로토콜

 

패킷이 에러가 있는지 없는지에 따라 ACK 또는 NCK를 보냄

 

rdt2.0에서는 rdt1.0과 다르게 송신자가 데이터에 checksum을 넣어 전송하여 수신자가 에러를 체크할 수 있음

rdt2.0의 문제점 - ACK 또는 NCK 패킷이 에러 날 수 있음

 

rdt2.1

sender / receiver

rdt2.0에서 ACK, NCK에 시퀀스 넘버를 추가함

수신자가 ACK를 보냈지만 패킷이 누락되어서 송신자가 수신자에게 패킷을 다시 보낼 수 있으므로 중복 패킷에 대한 처리가 추가됨

 

rdt2.2: a NAK-free protocol

sender / receiver

 

rdt3.0: channels whit errors and loss

기본 채널에서도 패킷(데이터, ACK)가 손실될 수 있음

송신자가 ACK에 대해 ‘합리적인’시간을 기다림

시간 내에 ACK가 수신되지 않으면 재전송 (b), (c), (d)

만약 시간 이후에 ACK가 수신되면, 해당 ACK에 대해 처리 + 시간이 초과되어 재전송된 패킷에 대한 ACK는 무시 (d)

---

3. 파이프라인 방식의 고신뢰도 전송 프로토콜

프로토콜 rdt3.0은 기능적으로 정확

But, 성능이 안좋음

이 문제는 대기 중지(stop-and-wait) 방식에서 발생

rdt3.0의 성능

\(D_{trans} = L/R\)

\(U_{sender}\): 활용률

\[U_{sender}={\frac {L/R} {RTT+L/R}}\]

 

파이프라인: 동시에 여러 작업을 수행

시퀀스 번호의 범위를 늘림

송신자 및 수신자에서 버퍼링 발생

\(U_{sender}\)(활용률)이 약 3배 좋아짐

 

Go-back-N

window는 파이프라인 크기

시퀀스는 누적 ack만 전송(loss가 해결될 때까지 시퀀스 증가 x)

ack가 오지 않은 가장 최근 패킷에 대해 시간 체크

시퀀스가 N인 패킷에 loss가 발생하면 N 패킷까지 되돌아가 작업을 수행

 

Selective repeat

수신자는 각각의 패킷에 대해 개별 ack를 보냄

송신자는 ack가 오지 않은 패킷에 대해 타이머를 유지

타이머가 만료되면 해당 패킷만 재전송

송신자, 수신자 모두 완료되지 않은 시퀀스에 대해 base 가짐

 

 

Selection repeat의 딜레마

b와 같은 상황에서 수신자가 시퀀스 0인 데이터(이전에 받았던 잘못된 데이터)를 받게 되는 문제가 생길 수 있음