[컴퓨터망] - Rdt,pipeline, Go-Back-N, Selective Repeat

RDT란?

RDT(reliable data transfer)는 신뢰성 있는 데이터 전송을 위한 프로토콜입니다.

신뢰성이 있다는 뜻은 송/수신하는 데이터가 오류 없이 전송된다는 뜻입니다.

RDT는 TCP가 UDP와 구분되는 가장 큰 특징입니다.

RDT는 상위 계층에서 전송한 데이터가 손상되거나, 손실되지 않았다는 것을 보장한다는 뜻이고, 하위 계층에서 신뢰성을 보장할 수 없기에, 특정 계층에서 신뢰성을 보장한다면 그 상위 계층의 신뢰성은 모두 보장됩니다.

Transport Layer에서는 신뢰성 있는 데이터 교환을 원하지만, 그 아래의 레이어에서는 신뢰성을 보장할 수 없기에, 신뢰성 있는 통신에 문제가 생길 수 있습니다.

이때 RDT 프로토콜을 이용하면 신뢰성을 확인할 수 있습니다.

그림을 보면 알 수 있듯이 transport layer에 신뢰성 있는 통신도 어쩌면 network layer에서 unreliable channel에 강하게 의존합니다.

RDT interfaces

패킷을 송신

• 상위레이어에서 보내려는 데이터가 있을 경우 rdt_send() 시스템 콜을 호출하여 RDT 프로토콜로 전송한다.
• RDT 프로토콜에서 신뢰할 수 없는 채널인 하위 레이어로 보낼 때 udt_send()를 호출해 패킷을 전송한다.

패킷을 수신

• 하위 레이어에서 보내려는 패킷이 있을 경우 rdt_rcv() 시스템 콜을 호출하여 RDT 프로토콜로 전송한다.
• RDT 프로토콜에서 상위 레이어로 데이터를 보낼 경우 deliver_data()를 호출 해 데이터를 전송한다.

요약하면

상위레이어 -> RDT : rdt_send() 하위레이어 -> RDT : rdt_rcv()
RDT -> 하위레이어 : udt_ send() RDT-> 상위 : deliver_data()

---

송신과 수신의 상호작용하는 과정을 설명하기 위해서 FSM을 활용한다.

FSM(Finite State Machines)

유한한 상태(state)가 존재할 때, 어떠한 상태가 다른 상태로 변화할때 생기는 일을 event와 action으로 나누어 설명하는 이론이다.
event는 상태를 변화시키는 원인이고, action은 상태가 변화하면서 생기는 변화를 말한다.

---

rdt 1.0

네트워크의 모든 채널이 완벽하게 신뢰성 있다는 것이 전제이다.

즉 bit error와, packet의 loss가 없다.

송신자는 상위 계층에서 데이터를 받고, 데이터를 포함한 패킷을 생성한뒤 송신한다.

수신자는 하위 채널에서 패킷을 수신하고, 데이터를 추출한 뒤 상위 계층으로 전달한다.

아주 간단하다. 왜냐하면 네트워크의 모든 채널이 신뢰성 있다고 가정했기 때문이다.

rdt 1.0은 데이터 손상이나 손실의 우려가 없는 네트워크에서 사용할 수 있는 모델이다.

---

rdt 2.0

packe에서 비트 오류가 발생할 수 있다는 것을 가정한다.

에러를 어떻게 감지하고 처리할까?

ACKs와 NAKs를 통해 수신된 패킷이 손상되었는지 여부를 수신자가 송신자에게 반환해 준다.

이때 송신자는 수신자의 응답을 받을 때까지 기다려줘야 합니다.

이 방식을 stop and wait라고 합니다.

ACKs(acknowledgements)

• 받는 사람이 나 잘 받았어~~!!라고 송신자에게 말해줌.

NAKs(negative acknowledgements)

• 받는 사람이 나 잘 못 받았어~라고 송신자에게 말해줌.
• 패킷 에러가 났다는 뜻.
• 송신자가 NAKs를 받는다면 송신자는 다시 데이터를 재전송해야 합니다.

1. sender는 보내고 나서 ACK/NAK를 기다립니다.
2. receiver는 수신을 하고, 만약 corrupt이라면 NAK를 송신자에게 수신합니다.
3. 만약 notcorrupt라면 그때 데이터를 추출하고, delivert_data 해서 상위 레이어로 보낸 뒤, 송신 측에게 ACK를 보내줍니다.
4. 만약에 수신 측에서 ACK를 보낸다면 다음 작업을 진행하고, NAK를 보낸다면 다시 재전송해 줍니다.

하지만 이러한 RDT 2.0도 치명적인 결함이 있다.

그래서 RDT 2.1로 발전했다.

송신자는 수신자의 상태를 ACK/NAK로 판단한다.
하지만 이러한 ACK/NAK가 과연 믿을 만 한가? 오류가 발생했다면 어떻게...??

무작정 재전송하기엔 복제품이 너무나 많이 생긴다는 단점이 있다.

이러한 복제품을 을 다루기 위해서 구별법이 생겨났다.

그 구별법은 바로 sequence number를 패킷마다 부여하는 것이다.

이 sequence number를 통해서 패킷이 새로운 데이터를 전송하는 것인지 NAK를 받아 재전송하는 것인지 구분할 수 있다.

만약 NAK1이라는 데이터를 받으면, 송신자는 1번 패킷이 문제가 있다는 것을 알아챌 수 있다.

수신자 입장에서는 내가 A패킷을 잘 받았다고 송신에게 보내고(ACK), B라는 패킷을 기다리고 있는데 A가 재전송 왔다면

내가 보낸 ACK가 제대로 가지 않았으니, 다시 송신 측에게 ACK를 보내준다.

아래 그림은 송신에 동작방식이다.

총 4가지 상태가 존재한다.

1. 0번 패킷을 보내기 전 상태
2. 0번 패킷을 보내고 ACK/NAK를 기다리는 상태
3. 1번 패킷을 보내기 전 상태
4. 1번 패킷을 보내고 ACK/NAK를 기다리는 상태이다.

동작 방식은 다음과 같다.

1. 0번 패킷을 만들어서 보낸다.
   • 여기서는 seq number, data, checksum 등이 포함된 정보를 패킷에 저장한다.
2. 0번 패킷에 대한 응답을 기다린다. (ACK or NAK)
   • 여기서 만약 NAK 라면 다시 0번 패킷을 보내준다.
   • ACK라면 1번 패킷을 보낼 준비를 한다.
3. 1번 패킷에 대한 응답을 기다린다. (ACK or NAK)

수신 측은 2가지의 상태가 존재한다.

1. 0번 패킷에 대한 응답을 보내기 전 상태
2. 1번 패킷에 대한 응답을 보내기 전 상태

동작 방식은 다음과 같다.

1. 0번 패킷을 기다리는 상태에서 0번 패킷이 잘 왔다면 extract -> deliver_data -> ACK를 보냄.
   1. 1번 패킷을 기다림.
      1. 들어온 패킷이 손상되었다면 NAK를 보냄.
      2. 0번 패킷이 들어왔다면 extract(), deliver_data 작업 없이 단순 ACK를 보냄.
         1. 나 잘 받았어~ 재전송
2. 1번 패킷이 잘 왔다면 extract() -> deliver_data() -> ACK를 보냄.

RDT 2.1에서는 seq num을 0과 1만 사용한다.

이유는 RDT 2.1 프로토콜에서는 2개의 패킷만을 사용하기 때문이다.

시퀀스 넘버를 2개로 제한하는 것은 RDT 2.1의 간단한 설계와 구현을 가능하게 하고, 충분히 2개로 신뢰성이 판단되기 때문이다.

---

RDT 2.2

기존 RDT 2.1의 ACK/NAK에서 NAK를 삭제한 버전이다.

NAK를 삭제한 대신 ACK에다가 뒤에 숫자를 붙여줍니다.

이 숫자의 의미는 가장 최근에 잘 받은 패킷을 뜻합니다.

0번 패킷을 보냈는데, 만약 ACK(0)이 온다면 잘 받았다는 뜻이고, ACK(1)이 온다면 잘 못 받았다는 뜻(NAK)입니다.

• 송신 측
  • 0번 ACK를 기다리고 있을 때 만약 ACK(1)이 날아오면 0번 패킷을 재전송하는 것을 볼 숭 있다.
    • ACK(0)이 날아오면 다음 패킷을 전송할 준비를 한다.
• 수신 측
  • 1번 패킷을 받았을 때 문제가 없다면 extract()-> deliver_data() -> send 하는 것을 볼 수 있다.
  • 만약 문제가 생겼다면 다시 재전송해달라고 부탁 (ACK(0))을 보낸다.

---

RDT3.0

RDT 3.0은 데이터 전송 과정에서 다음과 같이 여러 가지 문제가 발생할 수 있다고 가정한다.

1. 전송 도중에 flip bit, 즉 데이터 손상
   1. 비트의 에러를 탐지하기 위해 체크섬을 이용한다.
2. 전송 도중에 패킷 loss
   1. 어찌어찌하다가 패킷이나 ACK가 loss 될 수 있다.
   2. 유실되는 패킷을 확인하고 처리하기 위해 ACK Seq num을 활용한다.

사람을 통해서 예를 들면

내가 A라는 질문을 친구에게 물어봤는데 내 입장에선 이 친구 놈이 잘 들은 지 못 들은 지 판단이 안 선다.

그래서 나는 이 친구 놈이 들은 지 안 들었는지를 모르니까 대답이 올 때까지 무작정 물어본다. 계속계속 답이 올 때까지..

이렇게 무작정 기다리기에는 나도 답답하고, 친구는 내가 들었는데, 왜 다음말을 안 하지..?라는 이상한 상황이 펼쳐진다.

이걸 수신과 송신으로 엮어보면,

송신 측이 보낸 패킷이 전송 중에 loss 된 상황에서, 송신 측은 내 패킷에 대한 수신 측에 응답을 기다릴 것이고,

수신 측은 패킷이 오지 않았기에, 올 때까지 가

~

빤히 있는 것이다.

이러한 애매한 상황을 방지하기 위해서 Timeout이 도입된다.

송신 측은 적절한 시간(Timeout)만큼 수신 측에 대답을 기다리는 것이다.

나도 이러는 편이다. 친구들에게 물어보고 내가 정한 시간 동안 대답이 안 오면 다시 묻는다.

물론 내가 정한 Timeout은 굉장히 짧다. 그렇기에 적절한 Timeout을 정하는 것이 아주 중요하다 ㅋㅋ

RDT 3.0 요약하자면

송신자가 데이터를 전송하고 일정 시간을 기다린다.
그 시간 내에 올바른 ACK가 오지 않는다면 재전송!

송신 측 FSM은 아래와 같다.

• 송신측
  • 0번 패킷을 보내고, start_time를 실행.
    • 만약 1번 패킷이 돌아왔다면 무시하고 재전송, start_timer 실행
    • 0번 패킷이 시간 내에 돌아왔다면 stop_time()해준다.
    • 만약 0번 패킷이 돌아와도 timeout에 걸린다면 송신 측은 재전송한다.

4가지 시나리오

loss가 없는 상황

packet loss가 발생한 상황

packet loss가 일어나고 timeout동안 수신 측에서 ack가 안 와서 다시 재전송하는 그림이다.

Ack loss가 발생한 상황

여기서는 ACK가 가는 상황에서 loss가 일어났다.

그렇기에 송신 측은 패킷 1을 다시 보냈고, 수신 측은 seq num을 확인해서 재전송된 패킷인지를 판단할 수 있다.(detect duplicate)

ACK보다 Timeout이 먼저 실행되었을 경우

인터넷 문제로 delay 되는 등 ACK가 가는 도중에 Timeout 발생

이처럼 RDT 모델은 패킷을 보내고 ACK를 기다리는 Stop-and-Wait 방식을 사용한다.

이러한 대기하는 방식 때문에 한편으로는 효율성이 낮다고 볼 수 있다.

왜냐? 보내고 그냥 기다리기 때문이다. 아무것도 하지 않는다. 다음 작업도 준비하지 않는다. 왜냐? 응답이 오지 않았기 때문이다.

저기 파란색 세로길이를 우리는 Transmission delay라고 한다.

송신자로부터 수신자까지 전송되는 데 걸리는 시간을 의미합니다.

그리고 RTT는 패킷을 전송해서 응답이 도착할 때까지 걸리는 시간이다.

Transmission delay는 보통 packet의 길이/Transmission rate이다.

송신 측에서 패킷을 보내고 ACK를 받을 때까지 소요되는 시간은 RTT + Transmission delay(L/R)이 된다.

송신이 실제로 일하는 시간은 Transmission delay이고, 소요되는 시간은 RTT + Transmission delay이므로

송신 측의 효율은 아래와 같습니다.

하지만 이러한 stop-and-wait 방식은 효율성이 좋지 못합니다.

그래서 발전한 개념이 pipeline입니다.

하나의 패킷을 보내는 것이 아닌 여러 개의 패킷을 보내고 그 패킷에 대한 응답을 기다리는 개념입니다.



그림처럼 여러 개의 패킷을 보낼 수 있습니다.

3개의 패킷을 보낼 경우 non-pipeline 방식보다 효율성이 3배 증가한 것을 알 수 있습니다.

---

GBN(Go-Back-N)

수신 측에서 순서대로 받지 못한 패킷이 있다면 그 패킷부터 다시 재전송하는 방식이다.
패킷의 시퀀스 넘버를 이용합니다.

sender/receiver Window

• 송신 측에서 현재 전송 가능한 패킷들의 범위를 나타내는 개념입니다.
• 창문의 크기(window size)는 고정되어 있으며, 패킷의 전송이 완료되면 오른쪽으로 한 칸 증가시켜 줍니다.
• send_base는 send_base가 가리키는 범위 이전까지 성공적으로 응답을 받았다는 뜻을 의미합니다.
• rcv_base는 rcv_base가 가리키는 범위 이전까지 성공적으로 받았냐는 소리입니다.(수신자 창문)
• nextseqnum은 말 그대로, 다음에 전송할 패킷의 시퀀스 번호를 나타냅니다.
• sender window와 receiver window의 사이즈는 일치한다.

cumulative ACK

해당 패킷이 올 때까지 다른 패킷들을 받아도 받지 못한 패킷의 직전 패킷에 대한 ACK를 보낸다.

즉 예를 들어서

송신 측에서 패킷 1,2,3,45를 전송했는데, 수신측에서 1,2,4,5를 받았다면, 수신측은 ACK 1,2,2,2를 보낸다.

왜냐? 3을 받지 못했기에, 3 직전 패킷인 ACK(2)를 송신측에 보낸다.

그럼 송신 측은 ACK2가 오기에 2번까지만 제대로 갔구나. 2번 다음거부터 다시 보내자!

ACK(N)을 받았다면 송신측은 N+1부터 전송을 시작하면 된다.

아래 그림은 송신 측에서 전송한 패킷 2번이 중간에 소실된 상황이다.

• sender window
  • 패킷 넘버에 대한 ack가 온다면 한 칸씩 증가한다.
  • 위 그림을 예로 들면 0번 패킷에 대한 ack가 와서 rcv 한 시점에서 윈도가 오른쪽으로 한 칸 증가한다.
  • N=4이기에, 항상 범위 4반을 유지해야 한다.
• 송신/수신
  • 송신은 계속해서 packet을 pipeling 하게 보낸다.
  • 수신 측은 받았으면 ACK를 보낸다.
  • 여기서 문제가 발생했다.
    • 패킷 2번에 대한 loss가 일어났고, 수신 측은 패킷 2번을 기다리고 있고, 송신측은 패킷 2번에 대한 응답이 없지만 계속해서 보낸다.
      • 여기서 수신 측은 나 패킷 2번 못받앗어!!! 지금 들어온 패킷들을 다 discard하고 ACK(1)을 보낸다.
      • 여기서 수신측은 계속 ACK(1)을 보내지만, 송신 측은 패킷 2번에 대한 Timeout 기간 동안 ACK(2)을 기다린다.
      • 그렇게 기다리다가 timeout이 넘어가면 패킷 2번부터 재전송을 시작한다.
      • 이때 timeout은 송신 측에서 패킷 2번 전송하고 timer를 킨 시점부터 timeout까지 시간이다.

이렇게 pk # timeout이라면 #넘버부터 재전송해 준다.

---

Selective repeat(SR)

SR방식은 수신 측에서 받은 각각의 패킷들에 대해 ACK를 보내는 방식이다.

• 수신 측은 ACK가 오는 것에 대해서 ACK를 보낸다.
  • 순서를 신경 쓰지 않는다.
    • 만약 1,2,3,4,5를 전송했을 때, 수신 측에서 1,2,3,5만 받았다면, 수신 측은 ACK(1,2,3,5)를 보낸다.
• 수신측은 ACK를 받지 못한 모든 패킷에 대해 timer를 계산합니다.
  • 만약 각각의 timer가 Timeout 될 때까지 ACK가 온다면 각각의 패킷을 재전송합니다.
• Buffer packet이 필요하다.
  • 높은 신뢰성과 데이터의 안전성을 보장함.
    • 이유 1: 순서 제어
      • SR 방식은 일부 패킷의 재전송을 요청하므로, 수신 측에서는 원래의 패킷 순서를 유지하기 위해 재전송이 요청된 패킷을 기다려야 한다. 따라서 재전송이 요청된 패킷들을 "순서"대로 재전송해야 하기에, 임시적으로 버퍼에 저장해야 한다.
    • 이유 2: 중복제거
      • 예를 들어 송신 측 -> 패킷 (1,2,3) / 수신 측에서 패킷 2의 재전송을 요청
        • 수신 측은 패킷 2의 재전송을 받게 되는데, 이 패킷은 이미 이전에 수신된 패킷 2와 중복되는 내용을 가지고 있을 수 있기에, 이를 버퍼에 저장해서, 중복된 패킷을 제거함.
    • 이유 3 : 재전송을 위한 저장
      • 송신 측에서 재전송을 요청된 패킷들을 다시 보내야 한다. 이를 위해서 재전송이 요청된 패킷들을 버퍼에 저장하고, 버퍼를 확인해 전송

SR 방식에서 sender window, receiver window이다.

시나리오 1 : Sender가 보낸 패킷 중 하나가 소실된 경우

• 0번과 1번까지는 문제가 없습니다.
• 하지만 패킷 2번에서 문제가 발생했습니다.
• 2번이 오지 않은 상태에서 패킷 3, 4, 5가 도착해서 3번 4번 5번을 버퍼에 저장합니다.
• 패킷 2에 대한 응답이 오지 않았기에 sender window는 2번에서 멈춰있습니다.
• 패킷 2에 대한 timeout 상황이므로 패킷 2를 재전송합니다.
• 수신 측은 패킷 를 받고, 버퍼에 있는 패킷(3,4,5)까지 포함해 패킷 2,3,4,5를 상위 계층으로 deliver 하고, ACK(2)를 보냅니다.
• ACK 2가 송신 측에 도착하면 send_base가 2에서 3으로 밀립니다.

SR의 딜레마

SR은 GBN에 비해 효율적으로 보입니다.

실제로 전송이 실패한 것만 재전송하기 때문이죠.

하지만 큰~~ 딜레마가 있습니다.

송신 측은 패킷에 대한 ACK가 온다면 창문을 오른쪽으로 민다.

수신 측은 패킷을 전송 받으면 창문을 오른쪽으로 민다.

수신측 창문을 계속 밀었기에, 0번 패킷에 대한 문제가 발생하지 않는다!

문제가 발생한다 왜냐!?

• 수신 측은 패킷 0,1,2를 제대로 받았기에 창문을 오른쪽으로 계속 밀어준다.
• 하지만 수신측은 패킷 0,1,2에 대한 ACK 신호가 오지 않았기에, timeout이 되고 패킷 0을 다시 보냅니다.
• 여기서 문제는 receiver window의 0이 있기 때문입니다.
• 수신 측은 송신 측의 상황을 모르기 때문에, 패킷 0이 올바른 패킷이라고 판단하기에, 패킷 0을 버퍼에 넣을 것입니다.
• 하지만 지금 들어온 패킷 0은 저번에 받았던 패킷 0과 똑같기에, 중복된 패킷을 받게 되고, 문제가 발생합니다.

여기서 해결방법은 바로 window size를 줄이는 것입니다.

더 정확하게 말하면

window size가 sequence number의 개수의 절반보다 작거나 같아야 합니다.

sequence number가 송신/수신 window size의 합보다 크거나 같아야 합니다.
만약 더 작다면 수신 측에서 위와 같이 오해할 수 있는 상황이 생깁니다.

글이 제법 기네요..

정리를 하자면

😀요약

• Transport Layer에서는 RDT는 신뢰성 있는 데이터 전송을 위한 프로토콜이다.
  • 아래 계층에서의 신뢰성을 확인할 수 있다.
• FSM은 상태변화에 따른 event(원인)와 action(변화)으로 나누어 설명하는 이론이다.
  • 송신과 수신의 상호작용하는 과정을 설명하기 위해 활용된다.
• rdt 1.0은 데이터 손상이나 손실의 우려가 없는 네트워크에서 사용할 수 있는 모델이다.
• 패킷의 오류를 감지하기 위해서 RDT 2.0에서 ACK와 NAK가 등장했다.
  • 수신자가 송신자에게 응답해 줄 때 보내주는 메시지이다.
  • ACK : 잘 받았다는 뜻 / NAK : 못 받았다는 뜻 -> 송신자가 다시 데이터를 재전송해야 함.
• ACK/NAK가 믿을 만 한가에 대한 의심으로 RDT 2.1이 등장했다.
  • sequence number를 패킷마다 부여해서 해결.
    • ACK(1) -> 1번 패킷 잘 받았어~~라는 뜻
• RDT 2.2에서는 굳이 ACK/NAK를 나눠야 할까라는 의문점에서 출발
  • NAK를 삭제하고, ACK 뒤의 패킷 넘버를 붙여줌.
    • 예를 들어 0번 패킷을 보냈는데, ACK(1)이 왔다면, NAK라는 뜻
• RDT 3.0에서는 Timeout이 도입되었다.
  • 송신자는 수신자의 대답을 Timeout만큼만 기다린다!
  • Timeout 상황이 되면 그 이후의 대답이 오든가 말든가 다시 재전송함.
• GO-Back-N(GBN)은 수신 측에서 순서대로 받지 못한 패킷이 있다면 그 패킷부터 다시 재전송하는 방식이다.
  • cumulative ACK라고도 한다.
    • 성공적으로 받은 패킷에 대한 정보를 담아서 보냄.
      • ACK(N) = N+1번부터 전송하면 됨
• Selective repeat(SR)은 수신 측에서 받은 각각의 패킷들에 대해 ACK를 보내고 못 받은 패킷들에 대해서만 재전송함
  • Buffer packet이 필요함.
  • 순서를 신경 쓰지 않음
• SR의 딜레마로 인해 sequence number는 window size(송/수)의 합보다 크거나 같아야 한다!