어떻게 데이터 전송에 신뢰성을 추가하는가?

전송 과정

1. rdt_send()

• 수신기 상위 계층에 전달할 데이터 전달

2. udt_send()

• rdt에 의해 호출된다.

• 신뢰할 수 없는 채널을 통해 패킷을 전송한다.

3. rdt_rcv()

• 패킷이 채널의 rcv-side에 도착하면 호출된다.

4. deliver_data()

• rdt에 의해 호출된다.

• 데이터를 상위 계층에 전달한다.

---

rdt 만들기

유한 상태 기계를 통해서 rdt를 만들어보자!

유한 상태 기계(FSM)이란?

유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, 복수형: 유한 오토마타 finite automata)는 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델이다.

관련 용어

• 현재 상태(Current State): 임의의 주어진 시간의 상태
• 전이(Transition): 기계가 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화하는 현상

FSM 작동 구조

rdt1.0: 완벽히 신뢰할 수 있는 채널

송신측

수신측

완벽히 신뢰할 수 있는 채널?

• 비트 에러가 없다
• 패킷의 손실또한 없다

하지만 현실에서 이렇게 완벽히 신뢰할 수 있는 채널을 짜는 것은 힘들다.

rdt2.0: 비트 에러가 있는 채널

기본 채널은 패킷 속의 비트에 에러가 발생할 수 있다.

rdt2.0에서는 비트 에러를 찾기 위해 체크섬(checksum)을 사용한다!

어떻게 에러를 회복할 수 있을까?

• acknowledgements (ACKs): 수신자가 송신자에게 패킷을 잘 수신했다고 알려준다.

• negative acknowledgements (NAKs): 수신자가 송신자에게 패킷에 에러가 있다고 알려준다.

송신측

송신자가 Wait-for-ACK-or-NAK 상태에 있을 때, 상위 계층에서 더 많은 데이터를 가져올 수 없다.

따라서, rdt2.0을 Stop-and-Wait 프로토콜이라고 한다.

수신측

하지만 rdt2.0에도 치명적인 오류가 존재한다!
데이터 흐름에 문제가 생겨 ACK나 NAK 패킷이 손상(corrupt)될 수 있다.

ACK/NAK가 손상된다면?

• 송신자는 수신자에게 무슨 일이 발생했는 지 알 수 없다.

• 송신자는 같은 패킷을 재전송 할 가능성이 생긴다! --> 중복

중복을 다루는 방법

• 송신자가 ACK/NAK 패킷이 손상된다면 현재의 패킷을 재전송한다
• 송신자가 각 패킷에 sequence 숫자를 추가한다
• 수신자가 중복되는 패킷은 버린다.

rdt2.1: 중복 패킷 제어 채널

송신측

수신측

rdt2.2: NAK가 없는 프로토콜

• rdt2.1과 성능은 동일하지만, ACks만을 사용한다.

• NAK 대신, 수신자는 지난 패킷을 제대로 수신했다는 의미로 ACK를 보낸다.

  단, 수신자는 ACK 패킷에 seq #를 첨부한다.

• 보낸 사람의 ACK가 중복되면 NAK와 동일한 작업이 수행됩니다.

송신측

송신자가 ACK 0을 기다릴 때, ACK 1이 온다면 패킷을 재전송한다.
ACK 1을 기다릴때도 마찬가지이다.

수신측

rdt3.0: 에러와 손실이 있는 채널

손실이 없을 때

패킷 손실

ACK 손실

timeout이 일찍 되거나 ACK가 지연됐을 때

송신측

수신측

---

파이프라이닝

rdt3.0은 기능적으로 옳은 프로토콜이지만, 성능이 최악이다.

stop-and-wait 방법으로 패킷을 전송하기 때문!!!

rdt3.0의 성능 분석

1 Gbps link, RTT 30msec, 8000bit packet이라고 가정하자.

• 1Gbps 링크를 통한 33kB/초 처리량
• 네트워크 프로토콜이 물리적 자원의 사용을 제한하고 있다!

파이프라이닝된 데이터 전송 프로토콜

파이프라이닝: 송신자는 패킷의 다중 전송을 허락한다.

• 시퀀스 넘버는 반드시 증가해야 한다.

• 보낸 사람 및/또는 받는 사람 버퍼링

파이프라이닝은 utilization을 증가시킨다!

파이프라인 프로토콜의 두 가지 종류

• go-Back-N
• 선택적 반복(selective repeat)

go-back-N

• 송신자는 파이프라인 안에 N개의 unacked 패킷을 가질 수 있다.

• 수신자는 오직 누적 ack만 보낸다(차이가 있으면 ack 패킷을 보내지 않는다)

• 송신자는 unacked 패킷에 대해 타이머를 가지고 있다.

  타이머가 만기되면, unacked 패킷을 재전송한다.

go-back-N: 송신자 윈도우

• 패킷 헤더 안에 k-bit의 seq #을 가지고 있다.

• 최대 N개의 "윈도우"이며, 연속적으로 unacked 패킷이 허용된다.
  

위 그림에 대한 이해.

• ACK(n)의 의미: n 숫자 이하의 패킷들은 모두 ACK까지 완료된 상태이다.
• timeout(n): 윈도우에 있는 n 숫자 이상의 패킷들을 모두 다시 재전송한다.
• 윈도우는 총 N개의 패킷을 관리한다.
• base부터 nextseqnum 전까지는 ack를 기다리고 있다.
• 어플리케이션에서는 data를 6번(회색 패킷의 개수) 보낼 수 있다.

go-Back-N의 예제

선택적인 반복

• 수신자는 모든 받은 패킷에 대해 개별적으로 ack를 보낸다.

• 송신자는 ack를 받지 못한 패킷만 재전송한다.

  각 unACKed 패킷에 대해 타이머가 존재한다.

• 송신자의 window는 연속된 N개의 seq #를 가지고 있다.

  보냈거나, unACKed 된 패킷의 seq #를 제한한다.

선택적인 반복: 송신자, 수신자 윈도우

송신자

다음에 사용 가능한 seq 번호가 window에 있으면 pkt를 보낸다.

timeout(n): 패킷 n을 다시 보내고, 타이머를 다시 시작한다.

ACK(n)을 받았을 때 (윈도우 안에 있을 때)

• 패킷 n을 받은 것으로 표시한다.
• n이 ACK되지 않은 패킷 중 가장 작은 패킷이면 창 베이스를 다음 ACK되지 않은 시퀀스 #로 이동합니다.

수신자

패킷 n이 윈도우 안에 있을 때[rcvbase, rcvbase+N-1]

• ACK(n)을 보낸다.
• n이 순서와 다르다면? 버퍼에 넣는다.
• n이 순서와 같다면? (버퍼된 순서대로 패킷도 전달), 아직 receive 되지 않은 다음 패킷으로 윈도우를 옮긴다.

패킷 n이 윈도우 이전 패킷부터 윈도우 크기만큼일 때[rcvbase-N, rcvbase-1]

• ACK(n)을 보낸다.

그 이외의 경우

• 무시한다.

선택적인 반복의 예제

선택적인 반복의 딜레마

• seq #'s: 0, 1, 2, 3

• 윈도우 크기 = 3

위의 문제를 피하기 위해서는 seq # 크기는 윈도우의 크기의 2배 이상은 되야한다.

---

신뢰성 있는 전송의 요약

• 체크섬(Checksum): 전송된 패킷의 비트 에러를 체크하기 위해 사용.

• 타이머(Timer): 만약 패킷(또는 해당 ACK)이 채널 내에서 손실되었을 가능성이 있기에, 패킷 시간 초과(timeout)/재전송에 사용됩니다.

• 시퀀스 번호(Sequence number): 송신자에서 수신자로 흐르는 데이터 패킷의 순차적 번호 부여에 사용

• 인정(Acknowledgement): 수신자가 송신자에게 패킷을 잘 받았음을 알리기 위해 사용

• 부정 인정(Negative Acknowledgement): 수신자가 송신자에게 패킷을 못 받았음을 알리기 위해 사용

• 윈도우(Window)와 파이프라이닝(pipelining): 송신자는 지정된 범위 내에 있는 시퀀스 번호의 패킷만 전송하도록 제한될 수 있다.