[컴퓨터 네트워크] - Transport layer_Principles of reliable data transfer(1): rdt

 지난 글에서는 Transport layer 프로토콜 중 하나인 UDP에 대해서 알아보았다. UDP의 특징 중에, unreliable, 즉, 신뢰성 있는 데이터 전송을 보장하지 못한다는 단점이 있었다. 

 그렇지만, UDP와 달리 TCP는 reliable data trasfer이라는 특징이 있다. 즉, 신뢰성 있는 데이터 전송을 보장하는데, 이 TCP에 대해서 알아보기 전에 그 전에 TCP를 위한 사전지식이라고 생각하고, TCP에 적용된 원칙들에 대해서 알아보려고 한다.

---

1. Abstraction of reliable of data transfer

 처음에는, 단순히 신뢰성 있는 데이터 전송을 어떻게 구현해야될까에 대한 추상화부터 알아보려고 한다. 다음 그림을 보면 이 추상화라는 개념에 있어서 신뢰성 있는 데이터 전송은 쉽게 이해할 수 있을 것이다.

 

 즉, 위 그림을 보면 다음과 같은 과정임을 알 수 있다.

1. application 계층에서 전달받은 데이터를 transport계층에서 프로토콜을 이용해 신뢰성 보장하는 segment를 만들어서
2. network계층으로 전달해 unreliable channel을 통해 receiver에 도착한 뒤
3. receiver의 transport 계층에서도 전송된 데이터를 받아 오류, 손실, 순서 문제를 해결한 뒤, 완전한 데이터로 재조립해서
4. application layer에 데이터를 전달한다

 

 이 때, 고려해야 될 점은, sender와 receiver는 서로의 상태를 알 수 없다는 점이다. 즉, sender는 receiver가 데이터를 잘 받은 상태인지, 못받은 상태인지 모르고, receiver는 sender가 데이터를 전송했는지 안했는지 모르는 상태인 것이다. 즉 다음과 같이 커튼이 쳐져 있는 상태인 것으로 표현할 수 있다.

---

2. rdt(Reliable data transfer protocol) interfaces

 위와 같은 상태 문제를 뚫고 신뢰성 보장 데이터 전송 프로토콜 방법이 rdt이다. rdt는 1.0, 2.0, 2.1, 2.2, 3.0 등 여러 버전이 존재하는데 먼저, 간단히 rdt가 어떤 식의 protocol인지 정리하고, 알아보도록 하겠다. 기본 개념은 다음 그림과 같다.

 

 먼저, sender 쪽을 확인해 보자.

1. 상위 application layer에서 rdt_send()를 호출한다.
2. 데이터를 transport layer로 전달한다.
3. transport layer는 udt_send()를 통해 header를 붙인 segment를 network 계층으로 보낸다. udt는 unreliable data transfer.
4. 중간에 unrelibale channel을 통해 receiver로 전달된다.
5. receiver는 rdt_rcv()를 통해 segment를 받는다.
6. 신뢰성이 보장된 데이터를 deliver_data()를 통해 application layer로 보낸다.

이런 개념을 가지고 rdt는 undirectional data transfer(방향이 존재하지 않는 데이터 전송=단방향 데이터 전송)과 FSM(finite state machines)으로 sender와 receiver측에 구현됐다. FSM은 다음과 같다.

 

 FSM에 대해 위 그림을 이용해 설명해보자면, 먼저, 상태들이 존재한다.

 

 상태들은 원 안에 표현하며, 상태가 바뀌면 화살표로 표시해준다. 

 

 그리고 그 화살표 위에, bar를 놓고, bar 위쪽에는 상태 변화를 일으키는 event, bar 아래쪽에는 그 event에서 일어나는 상태 변화를 적는다.

---

3. rdt 2.0(Stop and Wait)

 수업시간에 rdt 1.0에 대해 다룰 시간이 없어서 rdt 2.0부터 진도를 나가기 시작했다. rdt 2.0에 대해서 알아보기 전에 간단하게 ACK과 NAK에 대해서 설명하면 다음과 같다.

• ACK: 잘 받았다.
• NAK: 메세지가 비정상적이다.(훼손됐다.)

 이제, 본격적으로 rdt 2.0의 FSM을 알아보자.

 

rdt 2.0 sender FSM

 

 먼저, sender 측의 FSM부터 살펴볼 예정이다. 위 그림을 설명하면 다음과 같다.

1. 먼저, application layer로부터 rdt_send()를 기다리는 상태(왼쪽)에서 시작한다.
2. 왼쪽에서 오른쪽으로 상태 이전이 일어나는 조건은 그림의 맨 상단의 bar로 표현돼있다.
3. rdt_send(data)가 일어나면, snkpkt을 make_pkt(data,checksum)과 udt_send(sndpkt)이 일어난다.                                    즉, packet을 data와 checksum을 가지고 만들고, udt_send(sndpkt)를 통해 packet을 다음 계층으로 보낸다.
4. 그 후, 상태는 ACK나 NAK을 기다리는 상태로 바뀐다.
5. 이 때, sender측에서 rdt_rcv(rcvpkt)&&isNAK(rcvpkt)이라면, udt_send(sndpkt)이 일어난다.                                              즉, 패킷을 받았는데(기대하고 있는 패킷은 ACK이나 NAK), 그 패킷이 NAK이라면, 전에 전송했던 패킷을 다시 보낸다.
6. 그리고, 만약, rdt_rcv(rcvpkt) && isACK(rcvpkt)라면, 아무일도 일어나지 않고 rdt_send()를 기다리는 상태로 바뀐다.

rdt 2.0 receiver FSM

그렇다면, receiver측은 어떨까? 위그림을 설명하면 다음과 같다.

1. 처음 상태는 하위계층(=network layer)에서 rdt_rcv()를 기다리고 있는 상태이다.
2. rdt_rct(rcvpkt)&&notcorrupt(rcvpkt)라면, extract(rcvpkt,data), deliver_data(data), udt_send(ACK)가 차례대로 일어난다. 즉, 패킷을 받고, 정상적인(방해받지 않은) 패킷이라면, 패킷으로부터 데이터를 분리하고 그 데이터를 application layer에 전달하고, sender에게 ACK pakcet을 불러온 뒤, 다시 처음 상태로 돌아간다.
3. 만약, 비정상적인(방해받은) 패킷을 받았다면, NAK패킷을 보내고 다시 처음 상태로 돌아간다.

 

 이런 rdt 2.0에도 치명적인 결점이 존재한다. rdt 2.0은 packet을 만들어 전송한 뒤, ACK와 NAK를 통해 서로의 상태를 알 수 있다. 그렇지만, 이 ACK와 NAK가 손상됐다면? receiver는 packet이 손상된 채로 와서 NAK을 보낸 상태지만, sender는 receiver의 상태를 ACK를 통해 잘 받았다고 생각한 상황을 생각해보자. sender는 ACK을 받아 패킷을 재전송하지 않을 것이다. 

 

 또, sender는 packet을 보내놓고, ACK이나 NAK이 오기 전에, 다른 패킷을 보낼 수 없다. 대역폭이 큰 상황이라면 큰 낭비인 것이다.

 

 이러한 방법에 대한 해결책으로, sender는 패킷에 sequence number 즉, 번호를 추가했다. receiver는 동일한 sequence number를 받았다면 중복 패킷을 폐기한다. 이를 적용한 방식이 rdt 2.1이다.

---

4. rdt 2.1

 rdt 2.1에서는 위에서 설명했듯이 packet에 sequence number, 순서를 부여한 것이다. rdt 2.1의 FSM에 대해 알아보자.

rdt 2.1 sender FSM

 

 먼저 sender 쪽의 FSM이다. 위 그림을 설명하면 다음과 같다.

1. 맨 처음, rdt_send()를 기다리는 상태인 것은 rdt 2.0과 동일하다.
2. 이 때, rdt_send()가 호출 되면, 패킷을 만드는데, 이 때, 패킷에 0번을 포함시켜 만들고, 이 패킷을 보낸다.
3. 그 뒤, 0번에 대한 ACK와 NAK를 기다리는 상태가 된다. 이 때, 패킷이 도착했는데, 훼손돼서 도착했거나 NAK 패킷을 받았다면, 패킷을 재전송한다.
4. 만약, 정상적으로 ACK를 훼손되지 않고 받았다면, 아무 일도 일어나지 않고, 1 패킷에 대한 rdt_send를 기다린다.
5. 1에 대한 패킷 전송은 0과 같고, 이를 0,1,0,1 반복해서 번호를 붙여 전송한다.

rdt 2.1 receiver FSM

 

그렇다면 receiver는 어떨까?

1. 0패킷에 대한 rdt_rcv()를 기다리는 상태이다.
2. rdt_rcv를 받고, 방해를 받았다면, NAK에 checksum을 같이 보낸다(NAK도 훼손확인 위해!)
3. 또는 sequence 번호가 0이 아닌 1이 왔다면, 패킷을 잘 받아서 ACK를 보내지만, 추출해서 application layer로 data를 보내지 않는다.
4. 만약, 패킷이 훼손되지 않고, 번호도 잘 맞았다면, data를 패킷에서 추출해 application layer에 전송하고, ACK을 보낸다.
5. 1에 대한 경우도 위 1~4와 같다.

 rdt 2.1에 대해서 정리해보면 다음과 같다.

-Sender

• ACK,NAK에 checksum과 sequence 번호를 추가해서 훼손된 상태에 대처한다.
• stop and wait 프로토콜이기 때문에 sequence 번호는 2개로 충분하다
• state 숫자가 2배 증가한다

-Receiver

• state 숫자가 2배 증가한다.
• 패킷의 중복 체크를 해야한다.(이미 받은 패킷인지 아닌지)
• 마지막으로 보낸 ACK/NAK이 잘 도착했는지 상태를 알 수 없다.

---

5. rdt 2.2 - NAK free protocol

 rdt 2.2의 아이디어는 기능적으로는 rdt 2.1과 동일하지만, ACK만을 사용하는 것이다.

 

 그럼, NAK의 역할은 어떻게 대체할까가 그 다음에 따라오는 궁금증이다. 이는 ACK에도 똑같이 번호를 부여하는 것이다. 즉, 마지막에 잘 받은 패킷에 대한 번호를 그대로 ACK에 붙여서 sender에게 전송하는 것이다.

 

 예를 들어, 1을 마지막에 잘 받아서 ACK-1까지 sender에게 보낸 상태라고 가정해보자. sender 입장에서는 ACK-1을 잘 받았다고 가정하고, 그 후 0을 보낼 차례여서 0을 보냈는데, receiver에게서 ACK-1을 받았다면, ACK-0을 못받았기 때문에 도착하지 못했다고 판단하는 것이다.

 

 그럼 rdt 2.2의 FSM을 살펴보자.

sender rdt 2.2 FSM

 

 먼저, sender 쪽인데, 기능적으로는 rdt 2.1과 같기 때문에, 달라진 점만 설명하면 다음과 같다.

• 0을 단 패킷을 전송하고 ACK 0을 기다리는 상태에서NAK 대신에 ACK의 번호가 1번을 받았다면, 재전송하는 것이고,
• 0번 ACK를 정상적으로 받았다면 아무일도 일어나지 않고 wait for call 1 from above 상태로 가는 것이다. 

receiver rdt 2.2 FSM

receiver 쪽도 차이점만 설명하면 다음과 같다.

• sequence 번호가 1번인 패킷을 기다리는 상태에서 0번인 패킷을 기다리는 상태로 전이되는 과정에서 ACK1번, 즉 번호가 달린 ACK패킷을 전송하는 것이고,
• 반대인 경우도 마찬가지이다.

---

6. rdt 3.0

 rdt 2.2까지는 모두 중간에 방해받은 패킷에 대한 대처법으로 나온 프로토콜이지만, rdt 3.0은 이 프로토콜에, 중간에 loss된 경우를 대처하기 위한 방법까지 추가한 프로토콜이다.

 

 loss된 패킷에 대해서 어떻게 알 수 있냐는 간단하게 타이머를 설정하는 것이다. 즉, 일정 시간이 넘었는데도 ACK를 받지 못했다면, 패킷을 재전송하는 것이다. 이 때, 생길 수 있는 문제점은 다음과 같다. ACK가 설정해놓은 시간 후에 도착했지만, 패킷이 재전송되도, receiver 측에서는 sequence number로 해결 가능하다. 

 

 그럼, 이제 rdt 3.0의 FSM을 살펴보자.

rdt 3.0 sender FSM

 

 먼저, 기능적으로 타이머만 추가된 것이기 때문에 timer 쪽만 살펴보자.

1. 패킷에 sequence 번호 0번을 부텨 전송하고 이 전송되는 시점에 timer를 시작한다. 그리고 ACK 0번을 기다리는 상태로 간다.
2. 여기서 timeout이 발생하면, 이전 패킷을 재전송하고, timer를 다시 시작한다. 
3. 만약, timer가 끝나기 전에 0번 ACK가 도착했다면, timer를 멈추고, sequence번호 1번 패킷 전송 대기 상태로 돌아간다.

 

즉, 다음과 일이 진행된다.

 

(a)같은 경우는, 시간 내에 ACK가 들어온 경우이고, (b)는 loss가 발생해, timeout이 발생하고 재전송이 일어나는 경우이다.

 

 

 (c)같은 경우도 생길 수 있다. ACK가 손실된 경우인데, 이 때는 sender쪽에 타이머가 timeout 되어, 패킷 재전송이 일어난다. Receiver 측은 중복 패킷을 받았지만, 패킷을 정상적으로 받았기 때문에, ACK를 보내고, 중복 패킷은 지운다.

 

(d)와 같은 경우도 일어날 수 있다. ACK가 도착하기 전에 timeout이 일어나는 경우인데, 이 경우는 그림을 보면서 정리해봐야겠다.

 

 ack1을 기다리는 상태에서

1. timeout이 일어나 pkt1에 대한 재전송을 했다.
2. 재전송 뒤에 ack1이 도착해서 sender 측은 잘 도착했다고 생각해 다음 차례인 pkt0을 보낸다 
3. 중복된 pkt1은 지우고,
4. ack1을 다시 보낸다.
5. 이 때, ack1은 이미 sender가 받은 상태이기 때문에 중복 패킷이므로, sender측에서도 무시한다.

---

6-1 Performance of rdt 3.0

 rdt 3.0도 마찬가지로, stop and wait 방식이다. 그렇다면 이 rdt 3.0의 성능은 얼마나 좋을까?

 

 성능의 척도로 이용되는 것이 utilization이다. 다음과 같은 예시를 생각해보자.

 

 1 Gbps의 속도를 가진 link와 15 ms의 propagation delay가 있고, 8000 bit 패킷을 보내는 상황이다. 이 때, 주어진 정보로, transmission delay를 구할 수 있다. 1 Gbps = 10^9 이므로, transmission delay는 다음과 같다.

 

 

 그리고, rdt 3.0의 전송 방법을 생각하면, 다음 그림과 같 나타낼 수 있다.

 

 위 그림과 같이, 다음 패킷을 보낼 때, ACK까지 확인을 하고 보내야 되기 때문에, 다음 패킷을 보낼 때까지, RTT가 발생하게 되고, 다음 패킷을 보낼 때까지 걸리는 시간은 RTT+L/R이다. 즉 이를 위 숫자를 대입해서 계산해보면, 0.008+30 = 30.008이다. 이 때, Utilization은 다음과 같이 구할 수 있다.

 

 실제 값을 대입해보면, 0.008/30.008 = 0.00027이 sender의 utilization임을 알 수 있다. 즉, 패킷을 0.027% 확률로 전송한다는 것이다. 그렇다면, 이렇게 효율이 안좋은 rdt 3.0을 쓰는 이유는 뭘까?

 

6-2 Pipelining 

 현재 rdt 3.0은 stop and waiting 방법을 사용하고 있다. 즉, 패킷을 보내고 ACK가 올 때까지, 다음패킷 전송을 멈추고 기다리는 상태라는 것이다. 그렇지만, 이런 방법은 위와 같이 효율성 측면에서 최악이다. 이를 해결하기 위해 rdt 3.0에 적용한 방법이 piplelining 방법이다.

 

 이 pipelining에 대해서 간단히 설명하면, ACK 패킷이 도착하지 않아도, 패킷을 전송하는 것이다. 이를 sender쪽 측면에서 in-flight상태라 부르고, 이 방식을 사용하면, multiple packet을 보낼 수 있게 된다.

 

 그렇다면, 이 방식을 적용한 rdt 3.0의 utilization을 계산해보자.

 

 pipelining을 적용하기 전과 propagation delay와 transmission delay는 똑같다고 가정하고 위 그림을 보면, sender 측 utilization은 다음과 같이 구할 수 있다.

 

 즉, 전 utilization과 비교해보면, 3배 가까이 상승했음을 볼 수 있다. 즉, 0.081%확률로 패킷을 전송할 수 있다는 것이다. 비록, 아직까지0.081%확률이지만, 동시에 보내는 패킷수가 많으면 많을수록, utilization이 올라가는 것을 확인할 수 있다.