컴퓨터 네트워크 3장- 신뢰적인 데이터 전송의 원리

3.4 신뢰적인 데이터 전송의 원리

일반적인 신뢰적인 데이터 전송 문제를 다룬다.

신뢰적인 데이터 전송을 구현하는 문제가 트랜스포트 계층뿐만 아니라 링크계층과 애플리케이션 계층에서도 발생할 수 있기 때문에.

• 신뢰적인 채널에서는 전송된 데이터가 손상되거나 손실되지 않으며,
• 모든 데이터는 전송된 순서 그대로 전달된다.

- >TCP가 인터넷 애플리케이션에게 제공하는 서비스 모델

 

• 데이터 전송 프로토콜의 송신 측은 rdt_send() 호출로 위쪽으로부터 호출될 것이며, 수신 측에서는 상위 계층으로 전달될 데이터를 넘길 것이다.
  • rdt : 신뢰적인 데이터 전송(reliable data transfer) 프로토콜을 나타낸다.
  • _send : rdt의 송신 측이 호출되고 있음을 나타낸다.
• 수신 측에서 rdt_rcv()는 패킷이 채널의 수신 측으로부터 도착했을 때 호출된다.
• rdt 프로토콜이 상위 계층에 데이터를 전달하려고 할 때 deliver_data()를 호출한다.

 

단방향 데이터 전송(unidirectional data tranfer)의 경우인 송신 측으로부터 수신 측까지의 데이터 전송만을 고려한다.

양방향(전이중) 데이터 전송(bidirectional data transfer)의 설명은 상당히 복잡하다.

 

단방향 데이터 전송만 생각하더라도 프로토콜의 송신 측과 수신 측이 양방향으로 패킷을 전달할 필요가 있다.

즉, rdt의 송신 측과 수신 측은 전송 데이터를 포함하는 패킷을 교환하는 것 외에 제어 패킷을 양쪽으로 전송해야 한다.

• rdt의 송신 측과 수신 측 모두 udt_send()를 호출함으로써 다른 쪽에 패킷을 전송한다.
  • udt : 비신뢰적인 데이터 전송(unreliable data transfer)을 나타냄

 

 

3.4.1 신뢰적인 데이터 전송 프로토콜의 구축

 

• 전이를 일으키는 이벤트는 변화를 표기하는 가로선 위에 나타난다.
• 이벤트가 발생했을 때 취해지는 액션은 가로선 아래에 나타낸다
• 이벤트 발생 시 어떠한 행동도 취해지지 않거나, 어떠한 이벤트 발생 없이 행동이 취해질 때 동작이나 이벤트가 없음을 표시하기 위해 각각 가로선 아래나 위에 기호 𝚲를 사용한다.

 

 

완벽하게 신뢰적인 채널상에서의 신뢰적인 데이터 전송: rdt1.0

하위 채널이 완전히 신뢰적인 가장 간단한 경우.

rdt1.0 송수신자에 대해  

유한상태 머신(finite-state machine, FSM)에 대한 정의

 

 

rdt1.0에서 송신자와 수신자는 각각의 FSM은 하나의 상태만을 가지므로, 전이는 필연적으로 그 상태로부터 자신으로 되돌아온다.

 

송신자

1. rdt_send(data) 이벤트에 의해 상위 계층으로부터 데이터를 받아들이고 데이터를 포함한 패킷을 생성한다. (make_pkt(data))
2. 패킷을 채널로 송신한다.

수신자

1. rdt는 rdt_rcv(packet) 이벤트에 의해 하위의 채널로부터 패킷을 수신한다.  이 이벤트는 하위 계층 프로토콜로부터의 프로시저 호출(rdt_rcv())에 의해 발생한다.
2. 패킷으로부터 데이터를 추출하고 (extract(packet, data))
3. 데이터를 상위 계층으로 전달한다. (deliver_data(data))

 

 

여기서는 데이터 단위와 패킷의 차이점이 없으며, 모든 패킷 흐름은 송신자로부터 수신자까지다.

1. 완전히 신뢰적인 채널에서는 오류가 생길 수 없으므로 수신 측이 송신 측에게 어떤 피드백(feedback)도 제공할 필요가 없다.
2. 수신자는 송신자가 데이터를 송신하자마자 데이터를 수신할 수 있다고 가정하였다. 따라서 수신자가 송신자에게 천천히 보내라는 것을 요청할 필요가 없다.

 

 

---

 

 

 

비트 오류가 있는 채널상에서의 신뢰적인 데이터 전송: rdt2.0

하위 채널의 더 실질 모델은 패킷 안의 비트들이 하위 채널에서 손상되는 모델이다.

비트 오류-> 패킷이 전송 또는 전파, 버퍼링 될때 네트워크의 물리적 구성요소에서 일반적으로 발생

 

 

비트 오류를 처리하기 위해 기본적으로 다음과 같은 세 가지 부가 프로토콜 기능이 ARQ 프로토콜에 요구

 

오류 검출

비트 오류가 발생했을 때 수신자가 검출할 수 있는 기능이 필요하다. → checksum

이러한 기술은 수신자가 패킷 비트 오류를 검출하고 복구할 수 있게 해준다.

 

수신자 피드백

송신자가 수신자의 상태를 알기 위한 유일한 방법은 수신자가 송신자에게 피드백을 제공하는 것이다.

수신자의 상태 : 패킷이 정확하게 수신되었는지 아닌지 등

 

rdt2.0 프로토콜에서은 수신자로부터 송신자 쪽으로 ACK와 NAK 패킷들을 전송할 것이다.

• 긍정 확인 응답(ACK)
• 부정 확인 응답(NAK)

-> 이러한 패킷은 단지 한 비트 길이면 된다. (0 또는 1)

 

재전송

수신자에서 오류를 가지고 수신된 패킷은 송신자에 의해 재전송(retransmit)된다.

 

 

rdt2.0에 대한 FSM

 

 

송신자

1. 왼쪽 상태에서 송신 측 프로토콜은 상위 계층으로부터 데이터가 전달되기를 기다린다. rdt_sent(data) 이벤트가 발생하면  송신자는 패킷 체크섬과 함께 전송될 데이터를 포함하는 패킷(sndpkt)을 생성하고 udt_send(sndpkt) 동작을 통해 전송한다.
2. 오른쪽 상태에서 송신자 프로토콜은 수신자로부터의 ACK 또는 NAK 패킷을 기다린다.
   1. 만약 ACK 패킷이 수신된다면 (rdt_rcv(rcvpkt) && isACK(rcvpkt))
      • 가장 최근에 전송된 패킷이 정확하게 수신되었음을 의미한다.
      • 따라서 프로토콜은 상위 계층으로부터 데이터를 기다리는 상태로 돌아간다.
   2. 만약 NAK가 수신된다면
      1. 프로토콜은 마지막 패킷을 재전송한다.
      2. 재전송된 데이터 패킷에 대한 응답으로 수신자에 의해 응답하는 ACK 또는 NAK를 기다린다
   rdt2.0과 같은 프로토콜은 전송 후 대기(stop-and-wait) 프로토콜이다.

 송신자가 ACK 또는 NAK를 기다리는 상태에 있을 때, 상위 계층으로부터 더 이상의 데이터를 전달받을 수 없다.

rdt_send() 이벤트는 발생할 수 없으며, 이는 오직 송신자가 ACK를 수신하고 이 상태를 떠난 후에 발생할 것이다.

 

따라서 송신자는 수신자가 현재의 패킷을 정확하게 수신했음을 확신하기 전까지 새로운 데이터를 전달하지 않는다.

수신자

단일 상태를 갖는다.

패킷이 도착했을 때, 수신자는 수신된 패킷이 손상되었는지 아닌지에 따라 ACK 또는 NAK로 응답한다.

 

 

rdt2.0의 결함

여기선 ACK 또는 NAK 패킷이 손상될 수 있다는 가능성을 고려하지 않았다.

만약 ACK 또는 NAK가 손상되었다면, 송신자는 수신자가 전송된 데이터의 마지막 부분을 올바르게 수신했는지를 알 방법이 없다.

 

1. 최소한의 오류 검출을 위해서는 ACK와 NAK 패킷에 대한 체크섬 비트를 추가할 필요가 있다.

이 방식은 패킷이 손상될 수 있으나 손실되지는 않는 채널의 경우에는 즉각적으로 문제를 해결할 수 있다.

 

 

2. 송신자가 왜곡된 ACK 또는 NAK 패킷을 수신할 때 현재 데이터 패킷을 단순히 다시 송신한다.

그러나 이 방식은 송신자에게 수신자 간의 채널로 중복 패킷(duplicate packet)을 전송한다.

• 송신자 입장에서는 마지막으로 전송된 ACK 또는 NAK가 송신자에게 정확하게 수신됐는지를 알 수 없다.
• 수신자 입장에서는 도착하는 패킷이 새로운 데이터를 포함하고 있는 것인지 아니면 재전송인지를 사전에 알 수 없다.

 

해결방법

데이터 패킷에 새로운 필드를 추가하고 이 필드 안에 순서 번호(sequence number)를 삽입하는 방식으로 데이터 패킷에 송신자가 번호를 붙인다.

수신자는 수신된 패킷이 재전송인지를 결정할 때는 이 순서 번호만 확인하면 된다.

 

 

---

 

 

 

 

 

rdt2.0의 수정 버전: rdt2.1

 

rdt2.1은 rdt2.0보다 두 배 많은 상태를 가지고 있다. 이는 아래의 2가지를 반영해야 하기 때문이다.

1. 프로토콜 상태가 현재 (송신자에 의해) 전송되고 있는지에 대한 반영
2. 수신자가 기다리고 있는 패킷이 순서 번호 0 또는 1을 가져야 하는지에 대한 반영 (Yes or No 이니까 2개면 됨)

 

프로토콜 rdt2.1은 수신자로부터 송신자까지의 긍정 확인응답과 부정 확인응답을 모두 포함한다.

• 순서가 바뀐 패킷이 수신되면, 수신자는 이미 전에 수신한 패킷에 대한 긍정 확인응답을 전송한다.
• 손상된 패킷이 수신되면, 수신자는 부정 확인응답을 전송한다.

NAK를 송신하는 것 대신에,
가장 최근에 정확하게 수신된 패킷에 대해 ACK를 송신함으로써 NAK를 송신한 것과 같은 효과를 얻을 수 있다.

 

즉, 같은 패킷에 대해 2개의 ACK를 수신(즉, 중복(duplicate) ACK를 수신)한 송신자는
수신자가 두 번 ACK 한 패킷의 다음 패킷을 정확하게 수신하지 못했다는 것을 알게 된다. (NAK의 의미와 동일)

 

송신자

수신자

 

 

 

 

---

 

 

비트 오류를 갖는 채널을 위한 NAK 없는 신뢰적인 데이터 전송 프로토콜 : rdt2.2

1. rdt 2.1:

1. • rdt 2.1은 기본적인 stop-and-wait 프로토콜을 기반
   • 데이터를 전송하기 위해 송신 측은 데이터를 보내고, 수신 측은 ACK(긍정적인 확인)을 받은 후에만 다음 데이터를 전송
   • 에러 제어 기능이 있지만, 송신 측이 데이터와 ACK를 재전송하여 에러를 처리
   • 재전송이 발생할 경우, 데이터 전송이 중지되고 송신 측은 재전송을 기다리며 타이머를 사용하여 시간을 측정
2. rdt 2.2:
   • rdt 2.2는 rdt 2.1에서 개선된 버전으로, 성능을 향상시키기 위한 추가적인 기능을 제공
   • rdt 2.2는 윈도우 기반의 프로토콜을 사용하여 연속적으로 여러 데이터 패킷을 전송. 즉, 여러 패킷이 네트워크를 통해 동시에 전송될 수 있음
   • 또한, rdt 2.2는 선택적인 음수적인 확인(Negative Acknowledgement)을 통해 송신 측에 에러를 신속하게 보고하여 재전송을 최소화.
   • ACK와 NACK를 사용하여 수신 측은 수신한 데이터를 확인하고, 필요한 경우 송신 측에 재전송을 요청할 수 있음
   • rdt 2.2는 stop-and-wait 방식보다 효율적인 데이터 전송을 가능

rtd2.2는 rdt2.1과 다르게,

1. 수신자가 반드시 ACK 메시지에 의해 확인 응답되는 패킷의 순서 번호를 포함해야 한다.
   • 이는 수신자 FSM의 make_pkt()에 ACK, 0 또는 ACK, 1인 인수를 넣어서 수행한다.
2. 송신자는 수신된 ACK 메시지에 의해 확인응답된 패킷의 순서 번호를 반드시 검사해야만 한다.
   • 이는송신자 FSM의 isACK()에 0 또는 1인 인수를 넣어서 수행한다

 

 

 

 

 

---

 

 

 

 

비트 오류와 손실 있는 채널상에서의 신뢰적인 데이터 전송: rdt3.0

비트의 손상 이외에도 하위채널이 패킷을 손실하는 경우도 생각.

다음과 같은 두 가지 부가 내용을 프로토콜이 다루어야 한다.

1. 어떻게 패킷 손실을 검출할 것인가?
2. 패킷 손실이 발생했을 때 어떤 행동을 할 것인가?

 

송신자에게 손실된 패킷의 검출과 회복 책임을 부여한다.

 

송신자가 데이터 패킷을 전송하고, 패킷 또는 수신자의 패킷에 대한 ACK를 손실했다고 가정하자.

어느 경우에서나 송신자에게는 수신자로부터 어떠한 응답도 없다.

 

즉, 송신자는 데이터 패킷이 손실되었는지, ACK가 손실되었는지, 패킷 또는 ACK가 단순히 지나치게 지연된 것인지를 알지 못한다.

만약 송신자가 패킷을 잃어버렸다고 확신할 정도로 충분한 시간을 기다릴 수만 있다면, 데이터 패킷은 간단하게 재전송될 수 있다.

 

그러나 

 

송신자가 어떤 패킷을 손실했다는 것을 확신하기 위해 얼마나 오랫동안 기다려야 할까?

 

적어도 송신자와 수신자 사이의 왕복 시간 지연(중간 라우터에서의 버퍼링을 포함) + 수신 측에서 패킷을 처리하는 데 필요한 시간은 기다려야 한다.

 

패킷 손실이 일어났을 만한 그런 시간을 선택하여, 만일 ACK가 이 시간 안에 수신되지 않는다면 패킷은 재전송된다.

이것은 송신자 대 수신자 채널에서 중복 데이터 패킷(duplicate data packet)의 가능성을 포함하나,
프로토콜 rdt2.2에서처럼 패킷의 순서 번호를 통하여 처리가 가능하다.

 

시간 기반의 재전송 메커니즘을 구현하기 위해서는 주어진 시간이 지난 후에 송신자를 인터럽트(중단)할 수 있는 카운트다운 타이머(countdown timer)가 필요하다.

 

 

그러므로 송신자는 다음처럼 동작해야 한다.

1. 매 패킷(첫 번째 또는 재전송 패킷)이 송신된 시간에 타이머를 시작한다.
2. 타이머 인터럽트에 반응한다. (즉, 적당한 행동을 취함)
3. 타이머를 멈춘다.

 

 

 

 

 

 

 

 

 

 

 

 

1. RDT 2.0:
   • 패킷의 손실을 감지할 수 있다.
   • 패킷의 손실이 감지되면, 수신자가 해당 패킷의 재전송을 요청할 수 있다.
   • 패킷의 순서가 변경되는 경우도 감지하고, 정확한 순서로 재조립할 수 있다.
2. RDT 2.1:
   • RDT 2.0과 유사하지만, 송신자는 모든 패킷을 일정 시간동안 재전송하지 않고, 수신자가 재전송을 요청한 패킷만 재전송한다.
   • 수신자는 재전송을 요청할 때 수신한 마지막 정상적인 패킷의 번호를 함께 전송하여 중복 재전송을 방지한다.
3. RDT 2.2:
   • RDT 2.1과 유사하지만, 패킷의 순서가 변경되는 경우에 대한 처리를 개선하여 수신자가 불연속적으로 도착한 패킷을 더 효과적으로 처리할 수 있다.
4. RDT 3.0:
   • RDT 2.x와는 달리, RDT 3.0은 흐름 제어와 혼잡 제어를 포함한 추가적인 기능을 제공한다.
   • 흐름 제어는 수신자가 송신자로부터 받을 수 있는 데이터의 양을 조절하여 수신자의 버퍼 오버플로우를 방지한다.
   • 혼잡 제어는 네트워크의 혼잡을 감지하고, 송신자가 네트워크를 너무 과도하게 사용하지 않도록 제한하는 메커니즘을 제공한다.

---

 

 

3.4.2 파이프라이닝된 신뢰적인 데이터 전송 프로토콜

 

rdt3.0의 핵심적인 성능 문제는 전송 후 대기(stop-and-wait) 프로토콜이라는 점 때문에 발생한다.

 

 

전송 후 대기 프로토콜은 형편없는 송신자 이용률(utilization, 또는 효율)을 갖는다.

 

U sender: utilization – fraction of time sender busy sending = (L/R) / RTT + (L/R)

 

 

 

 

순서 번호의 범위가 커져야 한다.

각각의 전송 중인 패킷은 유일한 순서 번호를 가져야 한다.

전송 중인 확인응답(ACK)이 안 된 패킷이 여럿 있을지도 모르기 때문이다.

 

프토로콜의 송신 측과 수신 측은 패킷 하나 이상을 버퍼링해야 한다.

최소한 ‘송신자는 전송되었으나 확인응답되지 않은 패킷’을 버퍼링해야 한다.

정확하게 수신된 패킷의 버퍼링은 수신자에게서도 필요하다.

 

필요한 순서 번호의 범위와 버퍼링 조건은 데이터 전송 프로토콜이 손실 패킷과 손상 패킷 그리고 상당히 지연된 패킷들에 대해 응답하는 방식에 달려 있다.

파이프라인 오류 회복의 두 가지 기본적인 접근 방법

1. GBN(Go-Back-N) : N부터 반복
2. SR(Selective Repeat) : 선택적 반복

 

 

 

---

 

3.4.3 GBN

GBN(Go-Back-N, N부터 반복) 프로토콜에서 송신자는 확인 응답을 기다리지 않고 여러 패킷을 전송(가능할 때)할 수 있다.

그러나 파이프라인에서 확인응답이 안 된 패킷의 최대 허용 수 N보다 크지 말아야 한다.

 

 

 

 

• 확인응답이 안 된 가장 오래된 패킷의 순서 번호를 base로 정의한다.
• 가장 작은 순서 번호를 nextseqnum(전송될 다음 패킷의 순서 번호)으로 정의한다.

 

이를 통해서 순서 번호의 범위에서 4개의 간격을 식별할 수 있다.

1. 간격 [0, base-1] : 순서 번호는 이미 전송되고 확인응답이 된 패킷
2. 간격 [base, nextseqnum-1] : 송신은 되었지만 아직 확인응답되지 않은 패킷
3. 간격 [nextseqnum, base+N-1] : 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷
4. base+N 이상
   → 파이프라인에서 확인응답이 안 된 패킷(특히, 순서 번호 base를 가진 패킷)의 확인응답이 도착할 때까지 사용될 수 없다.

 

전송되었지만 아직 확인응답이 안 된 패킷을 위해, 허용할 수 있는 순서 번호의 범위는 순서 번호의 범위상에서 크기가 N인 ‘윈도(window)’로 나타낸다.

 

프로토콜이 동작할 때, 이 윈도는 순서 번호 공간에서 오른쪽으로 이동(slide)된다.

• N = 윈도 크기(window size)

따라서 GBN 프로토콜은 슬라이딩 윈도 프로토콜(sliding-window protocol)이라고 부른다.

 

실제로 패킷의 순서 번호는 패킷 헤더 안의 고정된 길이 필드에 포함된다.

• 만약 k가 패킷 순서 번호 필드의 비트 수라면, 순서 번호의 범위는 [0, 2^k - 1]
• 순서 번호의 제한된 범위에서, 순서 번호를 포함하는 모든 계산은 모듈로(modulo) 2^k 연산을 이용한다.

 

GBM 프로토콜에서 수신자는 순서가 잘못된 패킷들을 버린다.

지금 패킷 n이 수신되어야 하지만, 그 사람 다음의 패킷 n+1이 먼저 도착했다고 가정하자.

수신자는 상위 계층에 데이터를 전달해야 한다.

데이터가 순서대로 전달되어야 하므로, 수신자는 패킷 n+1을 저장하고
나중에 패킷 n이 수신되고 전달된 후에 상위 계층에 이 패킷을 전달한다.

GBN 프로토콜의 성능 문제

GBN 프로토콜은 송신자가 패킷으로 파이프라인을 채우는 것을 통해 전송 후 대기 프로토콜에서의 채널 이용률 문제를 피하도록 하였다.

 

그러나 GBN 자체에는 성능 문제를 겪는 시나리오들이 존재한다.

윈도 크기와 대역폭 지연(bandwidth-delay) 곱의 결과가 모두 클 때, 많은 패킷이 파이프라인에 있을 수 있다.

 

GBN은 패킷 하나의 오류 때문에 많은 패킷을 재전송하므로, 많은 패킷을 불필요하게 재전송하는 경우가 발생한다.

채널 오류의 확률이 증가할수록 파이프라인은 불필요한 재전송 데이터로 채워진다.

 

 

---

3.4.4 SR

 수신자에서 오류(손실되거나 변조된)가 발생한 패킷을 수신했다고 의심되는 패킷만을 재전송한다.

• 이를 통해서 SR는 불필요한 재전송을 피한다.
• 필요에 따라 각각의 개별적인 재전송은 수신자가 올바르게 수신된 패킷에 대한 개별적인 확인응답을 요구할 것이다.

 

윈도 크기 N은 파이프라인에서 아직 확인응답이 안 된 패킷 수를 제한하는 데 사용된다.

그러나 GBN과는 달리, 송신자는 윈도에 있는 몇몇 패킷에 대한 ACK를 이미 수신했을 것이다.

 

 

• SR 수신자는 패킷의 순서와는 무관하게 손상 없이 수신된 패킷에 대한 확인응답을 할 것이다.
• 빠진 패킷이 존재하는 경우
  1. 순서가 바뀐 패킷은 빠진 패킷이 수신될 때까지 버퍼에 저장
     
     
  2. 빠진 패킷이 수신된 시점에서 일련의 패킷을 순서대로 상위 계층에 전달할 수 있다.
     
     

 

 

 

수신자는 송신자의 행동을 볼 수 없다.

 

모든 수신자는 채널을 통해 받고, 채널을 통해 보내는 메시지의 순서를 관찰하는데, 이는 위의 두 가지 시나리오가 똑같다.

즉, 다섯 번째 패킷의 원래 전송과 첫 번째 패킷의 재전송을 구별할 방법은 없다.

윈도 크기는 SR 프로토콜에 대한 순서 번호 공간 크기의 절반보다 작거나 같아야 한다.