프레임은 데이터 전송에서 중요한 개념입니다. 이는 전송 중인 비트 스트림을 더 큰 의미 있는 블록으로 분할하는 것을 의미합니다. 이것은 데이터를 수신 측에서 이해하기 쉬운 형태로 전달하기 위해 필요합니다.

프레임은 일반적으로 헤더, 페이로드 및 트레일러로 구성됩니다. 헤더는 프레임의 시작 부분에 위치하며, 프레임의 길이, 프로토콜 버전, 목적지 및 출발지 주소 등의 정보를 포함합니다. 페이로드는 전송 중인 실제 데이터를 포함하며, 데이터의 형식 및 구조는 프로토콜에 따라 다릅니다. 마지막으로, 트레일러는 프레임의 끝 부분에 위치하며, 오류 검사 및 프레임 종료를 나타내는 정보를 포함합니다.

수신 측은 비트 스트림을 프레임으로 분할하고 각 프레임의 헤더를 읽어 프레임의 길이와 형식을 확인합니다. 그런 다음 페이로드를 추출하여 수신 측에서 필요한 처리를 수행합니다. 마지막으로, 트레일러를 검사하여 오류가 있는지 여부를 확인합니다. 이러한 프로세스를 통해 데이터를 안전하고 정확하게 전송할 수 있습니다.

Fixed size framing

• 고정 비트 수
• 구분 기호가 필요하지 않음
• 비효율성을 야기할 수 있음 - 프레임 크기가 1000 비트인 경우 - 보내야 할 비트가 50개일지라도, 프레임은 여전히 1000 비트여야 함

Variable size framing

각 프레임은 다른 비트 수를 가질 수 있음
• 프레임을 식별하기 위해 구분 기호가 필요함
• 보낸 데이터에 따라 프레임을 구성할 수 있음  효율적임 – 보내야 할 비트가 50개인 경우, 프레임을 50비트로 만들 수 있음

플래그: 프레임의 시작과 끝을 가리키는 표시기
• 헤더: 제어를 위해 데이터 앞에 삽입된 비트
• 트레일러: 제어를 위해 데이터 뒤에 삽입된 비트
• 데이터/페이로드: 전송할 데이터

위의 예시에서, 프레임의 시작과 끝을 나타내는 플래그는 "01111110" 입니다. 그러나 데이터(페이로드) 내부에도 "01111110" 이 포함될 수 있습니다. 예를 들어, 데이터가 "0010101111110100" 이고, 헤더와 트레일러가 없다면, 이 데이터를 전송하기 위한 프레임은 "01111110001010111111010001111110" 이 됩니다.

이 경우 문제는 수신측에서 "01111110" 이 데이터의 일부로 해석될 수 있다는 것입니다. 즉, 수신측은 "01111110001010111111" 이라는 데이터를 수신한 후, 다음에 오는 "01111110" 이 프레임의 끝을 나타내는 플래그인지, 아니면 데이터 내부에 포함된 값인지 판단하기 어렵습니다. 이러한 상황은 프레임을 제대로 인식하지 못하고 데이터 오류가 발생할 가능성이 있습니다.

이를 방지하기 위해서는, 데이터 내부에 있는 "01111110"과 같은 값은 다른 값으로 대체하거나, 데이터를 인코딩하여 프레임의 시작과 끝을 나타내는 플래그와 혼동되지 않도록 보호할 필요가 있습니다.

문제

• 페이로드에서 마커 패턴이 나타나면, 수신측은 이를 끝 표시기로 인식할 수 있습니다. 이는 잘못된 프레임을 형성할 수 있습니다.

해결책

• 마커 패턴이 페이로드에서 나타나지 않도록 보장합니다.
• 만약 "11111" 이 나타나면, 패턴 뒤에 "0"을 추가합니다.
  • 비트 스터핑 → 11110
• 수신측은 "11111" 다음에 오는 "0"을 스터핑 비트로 인식하여 제거합니다.

비트 스터핑(Bit stuffing)은 데이터 전송 시, 일정한 패턴의 비트가 발생할 경우, 수신측에서 잘못된 프레임 구분을 할 수 있는 문제를 해결하기 위해 사용되는 기법입니다.

일반적으로, 프레임의 시작과 끝을 나타내는 패턴(예: "01111110")을 사용하여 프레임의 경계를 식별합니다. 그러나, 만약 데이터에서 이와 같은 패턴이 발견되면 수신측에서는 이를 프레임의 끝으로 오해할 수 있습니다. 이를 방지하기 위해 데이터 내부에서 이와 같은 패턴이 발견되면, 패턴 뒤에 추가적인 비트를 삽입하여 수신측에서 패턴을 식별하지 못하도록 하는 것이 비트 스터핑의 기본 아이디어입니다.

예를 들어, 패턴이 "11111"인 경우, 데이터에서 이와 같은 패턴이 발견되면, 패턴 뒤에 "0"을 추가하여 "111110"으로 변환합니다. 수신측에서는 "11111" 다음에 오는 "0"을 스터핑 비트로 인식하여 제거하고, 데이터를 원래의 모습으로 복원합니다. 이를 통해 데이터 내부에 있는 패턴이 프레임의 경계를 식별하는 패턴과 혼동되지 않도록 보호할 수 있습니다.

바이트 스터핑(Byte stuffing)은 데이터 전송 시, 일정한 바이트 패턴이 발생할 경우, 수신측에서 잘못된 프레임 구분을 할 수 있는 문제를 해결하기 위해 사용되는 기법입니다.

일반적으로, 프레임의 시작과 끝을 나타내는 바이트 패턴(예: 0x7E)을 사용하여 프레임의 경계를 식별합니다. 그러나, 데이터에서 이와 같은 패턴이 발견되면 수신측에서는 이를 프레임의 끝으로 오해할 수 있습니다. 이를 방지하기 위해 데이터 내부에서 이와 같은 패턴이 발견되면, 패턴 뒤에 추가적인 바이트를 삽입하여 수신측에서 패턴을 식별하지 못하도록 하는 것이 바이트 스터핑의 기본 아이디어입니다.

예를 들어, 패턴이 0x7E인 경우, 데이터에서 이와 같은 패턴이 발견되면, 패턴 뒤에 0x7D 바이트를 삽입하여 "0x7E"를 "0x7D 0x5E"로 변환합니다. 수신측에서는 "0x7D 0x5E"를 다시 "0x7E"로 복원하여 데이터를 원래의 모습으로 복원합니다. 이를 통해 데이터 내부에 있는 패턴이 프레임의 경계를 식별하는 패턴과 혼동되지 않도록 보호할 수 있습니다

💡 **7E → 7D 5E 7D → 7D 5D** 💡 7E : start/end marker 맨앞 맨뒤에 온다

ARQ

에러가 검출되면, 신뢰성 있는 통신을 위해 수신측은 송신측에게 해당 프레임을 재전송하도록 요청해야 합니다. 이를 위해 사용되는 기술 중 하나가 Automatic Repeat Request (ARQ)입니다.

ARQ는 데이터 전송 중 오류가 발생할 경우, 송신측으로부터 오류를 인식하고, 재전송 요청을 보내어 손실된 데이터를 복구하는 기술입니다. 이를 위해 송신측과 수신측 사이에서 반복적으로 메시지를 교환하여, 데이터 전송의 신뢰성을 보장합니다.

ARQ는 보통 Stop-and-Wait ARQ, Go-Back-N ARQ, Selective Repeat ARQ 등의 방식으로 구현됩니다. 이들 방식은 각각 다른 방법으로 데이터 전송을 관리하며, 데이터 전송의 효율성과 신뢰성을 각기 다르게 보장합니다.

Stop-and-wait

ACK

확인 응답(ACK) 프레임은 수신측이 프레임을 성공적으로 수신한 경우, 수신측에서 송신측으로 보내는 프레임입니다. 이 응답 프레임은 수신측이 송신측에게 데이터 수신이 완료되었음을 알리는 역할을 합니다.

ACK 프레임은 송신측에서 전송된 프레임이 수신측에서 정상적으로 처리되었는지 확인하기 위해 사용됩니다. 송신측에서는 데이터를 전송하고 일정 시간 동안 ACK 프레임을 기다립니다. 이 시간 동안 ACK 프레임을 받지 못하면, 송신측은 데이터 전송에 실패한 것으로 간주하고, 해당 프레임을 재전송합니다.

ACK 프레임을 통해 송신측과 수신측 사이에서 데이터 전송의 성공 여부를 확인할 수 있으며, 이를 통해 데이터 전송의 신뢰성을 보장합니다.

Timeout, RTT

적절한 타임아웃 기간은 RTT (Round-Trip Time)를 기반으로 설정해야 합니다.

RTT란 송신측에서 프레임 전송을 시작하고 ACK를 수신하는 데 걸리는 시간을 의미합니다. 이는 전송 시간, 전파 시간, ACK 전송 시간, ACK 전파 시간 및 송신 및 수신 측에서의 처리 시간 등을 포함합니다.

일반적으로 RTT를 기반으로 한 타임아웃 기간은 T = RTT + 마진 으로 설정됩니다. 여기서 마진은 예측할 수 없는 지연 (예: 처리 시간)을 고려한 것입니다. 따라서 이 마진을 추가하여 송신측에서 전송한 프레임에 대한 응답을 받지 못한 경우, 송신측은 데이터 전송이 실패한 것으로 간주하고 해당 프레임을 재전송합니다. 이를 통해 데이터 전송의 신뢰성을 보장할 수 있습니다.

수신측의 관점에서, 데이터 프레임을 받게 되면, 이후에 또 다른 프레임이 도착할 수 있습니다. 이 때 수신측은 이후에 도착한 프레임이 다음 프레임인지 아니면 이전에 송신측에서 재전송한 것인지를 구분해야 합니다. 이를 구분하지 않으면, 수신측은 중복된 데이터를 처리할 수 있으며, 이는 데이터 전송의 정확성과 신뢰성에 문제가 발생할 수 있습니다. 따라서 수신측은 이를 구분하기 위한 프로토콜을 구현하여 데이터 전송의 정확성을 보장해야 합니다.

정상적인 상황에서는 송신측이 프레임을 보내고, 수신측이 프레임을 받은 후 ACK 프레임을 송신측으로 보냅니다. 이후, 송신측은 수신측으로부터 받은 ACK 프레임을 확인하고 다음 프레임을 송신합니다. 이렇게 송수신이 반복되는 동안에 수신측은 새로운 프레임을 받게 됩니다. 이러한 경우, 수신측은 새로운 프레임을 받게 되며, 데이터 전송이 정상적으로 이루어집니다.

재전송 상황 1: 프레임이 손실됨
송신측이 프레임을 전송한 후 수신측이 프레임을 받지 못하면, 일정 시간이 지나면 송신측에서는 타임아웃(timeout) 이 발생합니다. 이 경우 송신측은 이전에 전송했던 프레임을 다시 재전송합니다. 이후, 수신측은 재전송된 프레임을 받게 되고 ACK 프레임을 송신측으로 보냅니다. 이렇게 송수신이 반복되면서 수신측은 새로운 프레임을 받게 됩니다. 이러한 경우, 수신측은 재전송된 프레임을 새로운 프레임으로 처리하고 데이터 전송이 정상적으로 이루어집니다.

재전송 상황 2: ACK가 손실됨
송신측이 프레임을 전송한 후 수신측은 프레임을 정상적으로 받아 ACK 프레임을 송신합니다. 하지만, 이때 ACK 프레임이 손실되면 송신측에서는 일정 시간이 지나면 타임아웃(timeout)이 발생합니다. 이 경우, 송신측은 이전에 전송했던 프레임을 다시 재전송합니다. 이후, 수신측은 재전송된 프레임을 받게 되고 다시 ACK 프레임을 송신합니다. 이렇게 되면, 송신측에서는 이전에 전송했던 프레임이 재전송된 것이라고 인식하여 새로운 프레임이 아닌 재전송된 프레임으로 처리합니다. 이러한 경우, 수신측은 정상적으로 프레임을 받았음에도 불구하고, 송신측에서는 프레임 손실이 발생한 것으로 인식하여 재전송하게 되고, 이로 인해 중복된 프레임이 송수신될 수 있습니다.

재전송 사례 3 : ACK가 타임아웃 이후에 도착한 경우
이 경우는 ACK가 유실되었기 때문에 sender는 timeout이 되어 이전에 보냈던 frame을 재전송하게 됩니다. 이 때, receiver는 이전에 받았던 frame과 같은 frame을 다시 받게 되는데, sender는 이미 이전에 보낸 frame의 ACK를 받았으므로, 새로운 frame을 보내기 시작합니다. 이 때, receiver는 새로운 frame을 받게 되는데, 이전에 보냈던 frame인지, 아니면 새로운 frame인지 판단할 수 없습니다. 따라서 sender는 sequence number와 같은 정보를 통해 이를 구분하게 됩니다.

수신자는 프레임이 도착하면 ACK를 보내지만, 나중에 다른 프레임이 도착하면 이게 새로운 프레임인지 아니면 재전송된 프레임인지를 알지 못합니다. 이는 재전송과 관련된 문제 중 하나인 "Duplicate Frame" 문제입니다. 따라서 수신자는 이전에 받았던 프레임의 번호를 추적하고, 도착한 프레임의 번호와 비교하여 새로운 프레임인지, 아니면 재전송된 프레임인지를 판별해야 합니다.

프레임 헤더에 일련 번호를 포함합니다.
• 일련 번호는 각 프레임마다 증가됩니다.
• 일련 번호의 범위 : [0 ... N] - 다음 프레임(N)은 프레임(0)입니다.
• ACK에도 일련 번호가 있습니다. - "다음에 예상되는 프레임"의 일련 번호를 나타냅니다. - 수신자가 프레임(0)을 수신하면 ACK(1)을 보냅니다.

Stop-and-wait ARQ에서 시퀀스 번호는 [0,1]의 범위를 가집니다. 송신 측은 frame(0)을 보내고, 수신 측은 frame(0)을 받으면 ACK(1)을 보내고, 송신 측은 ACK(1)을 받으면 frame(1)을 보냅니다. 이후에도 마찬가지로 송신 측이 보낸 frame와 수신 측이 받은 frame의 시퀀스 번호가 번갈아가며 0과 1이 반복됩니다. 이 과정에서 수신 측은 항상 "다음에 기대되는 프레임의 시퀀스 번호"를 ACK에 포함하여 송신하게 됩니다.

frame(0)→ACK(1)→frame(1)→ACK(0)→frame(0)…

Stop-and-wait : frame structure

Frame(0)은 송신자가 보낸 첫 번째 프레임을 의미합니다. 이 프레임은 수신자에게 전송되고, 수신자는 이 프레임의 수신을 확인하기 위해 ACK(1)을 송신자에게 보냅니다. ACK(1)은 송신자에게 다음 프레임인 frame(1)을 전송하도록 지시합니다. 이어서, 송신자는 frame(1)을 보내고, 이번에는 수신자는 ACK(0)을 보내며, 다시 frame(0)을 보내도록 지시합니다. 이후에도 계속해서 frame(1), ACK(0), frame(0), ACK(1) 순서로 프레임과 ACK가 전송됩니다. 이러한 방식을 stop-and-wait ARQ라고 합니다.

Stop-and-wait: error 1. frame lost

이 경우, S(Sender)는 frame(0)을 보냅니다. 그러나 R(Receiver)는 해당 프레임을 받지 못합니다. 따라서 S는 timeout이 발생하면서 frame(0)을 다시 전송합니다. 이번에는 R이 frame(0)을 수신하고 ACK(1)을 보내게 됩니다. 이 때, S는 ACK(1)을 받고 다음 프레임을 전송할 수 있습니다. 이러한 상황은 ARQ의 목적인 데이터 전송 신뢰성 확보를 위해 재전송이 이루어지는 정상적인 상황입니다.

Stop-and-wait: error 2. ACK lost

이 경우에는 ACK가 손실되었으나, 재전송에 의해 문제가 해결되었습니다. 보낸 쪽(S)은 frame(0)을 보내고 받은 쪽(R)은 ACK(1)을 보내왔는데, ACK가 손실되어 S는 frame(0)을 다시 보냅니다. 이번에는 R이 frame(0)을 받고 ACK(1)을 다시 보내왔습니다. 이후에는 S가 ACK(1)을 받아 문제가 해결되었습니다.

Stop-and-wait: error 3. ACK arrives after timeout

이 경우, 송신자는 frame(0)을 전송하고 수신자는 frame(0)을 받아 ACK(1)을 보냅니다. 그러나 ACK(1)이 손실되어 송신자는 타임아웃을 호출하고 frame(0)을 다시 전송합니다. 이후, 수신자는 frame(0)을 다시 받고 ACK(1)을 보내고, 송신자는 ACK(1)을 받습니다.

하지만 이번에는 ACK(1)이 frame(0) 재전송 전에 도착합니다. 그래서 송신자는 이미 다음 프레임인 frame(1)을 전송합니다. 수신자는 이미 frame(0)을 받았고, frame(1)을 기다리고 있기 때문에, frame(0)을 무시하고 바로 ACK(1)을 보냅니다.

그리고 나서, 수신자는 frame(1)을 받아 ACK(0)을 보내고, 송신자는 ACK(1)을 받아 무시합니다. 마지막으로, 송신자는 ACK(0)을 받아 frame(0)을 전송합니다. 이 경우, frame(0)은 이미 받았던 frame(0)과는 다른 새로운 프레임입니다. 따라서, 이 문제는 해결되었습니다.

정지-대기 ARQ(stop-and-wait ARQ)를 사용하는 시스템이 있다고 가정해보겠습니다. 링크 대역폭(link bandwidth)은 1Mbps이며 RTT는 20ms로 고정되어 있습니다. 오류가 없고 무한한(timeout) 시간이 있다고 가정할 때, 전송량(throughput)은 얼마입니까? 프레임 크기(frame size)가 1000비트이라고 가정합시다.
• 대역폭 대비 전송량(throughput)의 비율은 얼마입니까? -> 대역폭이 낭비됩니다!

먼저 전송량(throughput)을 계산하면 다음과 같습니다.

💡 전송량 = 전송되는 데이터의 양 ÷ 걸리는 시간

프레임 크기가 1000비트이므로, 전송되는 데이터의 양은 1000비트입니다. 무한한(timeout이 없으므로) RTT는 무시할 수 있습니다. 그러므로, 전송량은 1Mbps ÷ 1000비트 = 1000 프레임/초입니다.

그러나 정지-대기 ARQ에서는, 수신자(receiver)는 각각의 프레임(frame)을 받은 후 ACK를 보내야합니다. 이 때문에, 각각의 프레임(frame)이 전송되고 ACK가 도착하는데 걸리는 시간은 RTT입니다. 따라서, 각각의 프레임(frame)이 전송되고 ACK가 도착하는데 걸리는 시간은 2 × RTT입니다. 따라서 대역폭 대비 전송량(throughput)의 비율은 1000 프레임/초 ÷ 1Mbps = 0.001, 즉 0.1%입니다. 이는 대역폭이 매우 낭비되는 것을 의미합니다.

Go-back-N

일정 프레임에 대한 ACK를 기다리는 것은 낭비적입니다. 대신에, 링크 파이프를 채우기 위해 여러 프레임을 연속으로 전송한 다음 ACK를 기다리는 것이 좋습니다. 만약 특정 프레임에서 오류가 발생하면 해당 프레임 이후에 보낸 모든 프레임을 무시하고 그 프레임부터 다시 시작하는 것이 좋습니다. 이를 Go-Back-N 방식이라고 합니다.

Q)

How many frames should the sender send before
receiving an ACK?
• What should be the sequence number range?
• What should we do when an error occurs?

Go-Back-N 프로토콜에서는, 송신자는 ACK를 수신하기 전에 여러 개의 프레임을 보내야 합니다. 이 때, ACK를 수신하기 전에 보낼 수 있는 프레임의 개수를 송신자의 윈도우 크기라고 합니다.

Go-Back-N 프로토콜에서의 시퀀스 번호 범위는 [0, 2^k - 1] 입니다. 여기서 k는 시퀀스 번호에 사용되는 비트 수입니다. 예를 들어, k=3이면 시퀀스 번호 범위는 [0, 7] 입니다.

에러가 발생하면, 수신자는 손상된 프레임에 대해 부정적인 ACK(NAK)를 보내고, 송신자는 손상된 프레임 이후에 보낸 모든 프레임을 다시 전송합니다. 이 때, 수신자는 손상된 프레임 이전에 이미 수신한 모든 프레임을 폐기합니다.

Sliding window

슬라이딩 윈도우는 송신자와 수신자 각각이 가지고 있는 고정된 크기의 윈도우입니다. 송신자는 보내기 윈도우를, 수신자는 받기 윈도우를 가지고 있습니다. 슬라이딩 윈도우는 전송 제어 프로토콜에서 사용되며, 송신자와 수신자 모두에게 어떤 프레임을 전송하고, 어떤 프레임을 받아들일지를 결정하는 역할을 합니다. 윈도우의 크기는 고정되어 있으며, 프로토콜의 종류에 따라 다르게 설정될 수 있습니다. 슬라이딩 윈도우 프로토콜 중에서는 Go-Back-N, Selective Repeat 등이 있습니다.

Send window는 Sender가 보낼 수 있는 프레임의 범위를 의미합니다. Sender는 send window 안에서만 프레임을 보낼 수 있습니다. 그리고 ACK를 받으면 window가 오른쪽으로 이동하게 됩니다.

위의 그림에서 보시면, 왼쪽에 있는 Frames 13-15는 이미 보내졌고 ACK를 받은 상태입니다. 0-6까지는 보낸 프레임이지만 아직 ACK를 받지 못한 상태이며, 이를 "outstanding frames"라고 합니다. 7-14까지는 보낼 수는 있지만 준비되지 않은 프레임들입니다. 오른쪽에서 보시면, Frame 15부터는 아직 보낼 수 없는 프레임들입니다.

Sf는 First outstanding frame로, 아직 ACK를 받지 못한 첫 번째 프레임을 의미합니다. 즉, 전송 중인 상태이며, 이후 ACK를 받으면 다음 프레임을 전송할 수 있습니다.

Sn은 Next frame to read로, 아직 전송되지 않은 첫 번째 프레임을 의미합니다. 이전에 전송된 모든 프레임들은 이미 Sf에서 처리되었습니다.

Ssize는 Send window size로, 전송 가능한 최대 프레임 수를 나타냅니다. Sf와 Sn은 Ssize를 기반으로 계산됩니다. 즉, Sf + Ssize = Sn입니다. 이 값을 조정하여 전송 효율을 최적화할 수 있습니다.

ACK가 수신되면, 슬라이딩 윈도우는 오른쪽으로 이동합니다. 예를 들어, 그림 a에서 프레임 0-2에 대한 ACK가 수신된 경우, 슬라이딩 윈도우는 그림 b와 같이 이동합니다.

Go-Back-N ARQ의 시퀀스 번호 범위는 전송자의 슬라이딩 윈도우의 크기와 시퀀스 번호를 나타내는 데 사용 가능한 비트 수에 따라 결정됩니다. 시퀀스 번호 범위는 전송자가 확인 응답을 기다리지 않고 여러 패킷을 전송할 수 있도록 충분히 넓어야 하지만, 시퀀스 번호를 나타내는 데 너무 많은 비트를 사용하지 않도록 충분히 좁아야 합니다.

일반적으로 Go-Back-N ARQ의 시퀀스 번호 범위는 2의 거듭제곱으로 선택됩니다. 이렇게 하면 시퀀스 번호를 고정된 비트 수로 표현할 수 있습니다. 예를 들어, 전송자의 슬라이딩 윈도우 크기가 8이면 시퀀스 번호 범위는 [0...7]일 수 있으며, 이를 나타내는 데 3개의 비트가 필요합니다. 슬라이딩 윈도우 크기가 16이면 시퀀스 번호 범위는 [0...15]가 될 수 있으며, 이를 나타내는 데 4개의 비트가 필요합니다.

시퀀스 번호 범위의 선택은 기저 전송 매체의 특성에 따라 달라집니다. 예를 들어, 전송 매체가 노이즈가 많으면 불필요한 패킷 재전송을 줄이기 위해 작은 시퀀스 번호 범위가 선호될 수 있습니다. 반면, 전송 매체가 신뢰성이 높으면 대역폭 향상을 위해 더 큰 시퀀스 번호 범위를 사용할 수 있습니다.

만약 송신 윈도우 크기가 N이라면, 시퀀스 번호 범위는 N보다 넓어야 합니다. 즉, 시퀀스 번호를 나타내는 데 사용되는 비트 수(m)에 따라 송신 윈도우 크기는 2의 m승보다 작아야 합니다.

예를 들어, 만약 송신 윈도우 크기가 4이면, 시퀀스 번호 범위는 최소한 [0,4]여야 합니다. 이를 나타내는 데 사용되는 비트 수는 3이 되므로, 송신 윈도우 크기는 2의 3승인 8보다 작아야 합니다. 즉, 송신 윈도우 크기는 4보다 작거나 같아야 합니다.

윈도우 크기와 시퀀스 번호 범위는 Go-Back-N ARQ와 같은 슬라이딩 윈도우 프로토콜을 설계할 때 중요한 매개 변수입니다.

윈도우 크기는 송신자가 한 번에 보낼 수 있는 미확인 패킷의 최대 수를 결정합니다. 또한 프로토콜의 처리량에 영향을 미칩니다. 윈도우 크기가 더 크면 송신자가 확인 응답을 기다리기 전에 더 많은 패킷을 전송할 수 있으므로 처리량이 향상될 수 있지만, 네트워크에서 오류나 혼잡이 발생하면 지연 시간과 재전송률이 증가할 수 있습니다.

반면에 시퀀스 번호 범위는 프로토콜에서 패킷을 식별하는 데 사용되는 값의 범위를 결정합니다. 윈도우 크기를 수용할 수 있는 넓이가 있어야 하지만, 비트를 낭비하거나 불필요한 오버헤드를 만들지 않도록 지나치게 넓게 설정해서는 안됩니다. 너무 좁은 시퀀스 번호 범위는 수신측에서 새로운 패킷을 재전송된 패킷으로 오해할 수 있으며, 너무 넓은 범위는 프로토콜에서 불필요한 오버헤드를 초래할 수 있습니다.

요약하면, 윈도우 크기와 시퀀스 번호 범위는 서로 관련되어 있으며, 슬라이딩 윈도우 프로토콜에서 최적의 성능과 효율성을 달성하기 위해 신중하게 선택해야 합니다.

Go-Back-N은 sliding window 기반의 ARQ (Automatic Repeat Request) 프로토콜로, 네트워크 상에서 전송된 패킷이 손상되거나 유실되었을 때, 송신자가 재전송하는 방식으로 통신을 보장합니다.

Normal case에서는, 송신자가 sliding window 내의 데이터 프레임들을 순차적으로 전송하면서 수신자는 정상적으로 수신하여 확인응답(ACK)를 송신자에게 전송합니다. 이때 송신자는 sliding window의 가장 왼쪽 끝의 데이터 프레임이 ACK로 확인되면 다음 데이터 프레임을 전송합니다.

Timeout case에서는, 수신자가 송신자로부터 데이터 프레임을 수신하지 못하거나 손상된 데이터 프레임을 수신할 경우 ACK를 송신하지 않습니다. 이 경우 송신자는 ACK를 수신하지 못한 패킷부터 sliding window 내의 모든 패킷을 재전송합니다. 이때 송신자는 일정 시간이 지나도록 ACK를 수신하지 못한 경우, 타임아웃이 발생하여 sliding window 내의 모든 패킷을 재전송합니다.

Go-Back-N은 송신자가 sliding window 내의 모든 패킷을 재전송해야 하므로 네트워크 대역폭이 낮거나 잡음이 많은 경우에는 전송 시간이 길어질 수 있습니다. 따라서 sliding window의 크기와 타임아웃 값은 잘 조정되어야 합니다.

타임아웃이 발생하면, 오류가 발생한 위치로 되돌아가서 재전송을 시작해야 합니다. 이는 수신 윈도우 크기가 1인 경우입니다. 예를 들어, 송신자가 1부터 5까지의 프레임을 보내고 프레임 1이 손실되었지만, 나머지 패킷은 성공적으로 수신되었다고 가정해봅시다. 그럼에도 불구하고, Go-Back-N ARQ는 모든 프레임을 재전송해야 합니다.

Go-Back-N ARQ는 특정 시나리오에서 성능에 영향을 미칠 수 있는 여러 가지 제한 사항이 있습니다. 가장 큰 제한 사항 중 하나는 하나의 패킷 손실 발생 시 모든 미확인 패킷을 재전송해야 한다는 것입니다. 따라서 이후 패킷들이 정상적으로 수신되었더라도 상당한 대역폭 낭비와 데이터 전송 지연을 초래할 수 있습니다.

이러한 문제를 극복하기 위해서는, 수신 측의 수신 창 크기를 1 이상으로 설정한 수정된 슬라이딩 윈도 프로토콜을 사용할 수 있습니다. 이렇게 하면 수신 측이 순서에 상관없이 패킷을 인식할 수 있으므로, 손실된 패킷만 재전송하면 되며 모든 미확인 패킷을 재전송할 필요가 없습니다.

이 수정된 프로토콜에서는 보통 송신 측의 송신 창 크기가 수신 측의 수신 창 크기와 동일하게 설정됩니다. 이렇게 하면 송신 측이 수신 측이 처리할 수 있는 이상의 패킷을 보내지 않도록 하여 수신 측 버퍼 오버플로우로 인한 패킷 손실 가능성을 줄일 수 있습니다.

결과적으로, 이 수정된 슬라이딩 윈도 프로토콜은 데이터 전송에 상당한 지연이나 패킷 손실이 상대적으로 많은 시나리오에서 Go-Back-N ARQ보다 개선된 성능과 효율성을 제공할 수 있습니다.

💡 → receiver window size를 1이상으로 !!!

Selective repeat

Selective Repeat (선택적 재전송)은 슬라이딩 윈도우 기반의 오류 제어 프로토콜 중 하나입니다. 이 프로토콜은 Go-Back-N ARQ와 유사하지만, 수신자가 패킷을 개별적으로 확인하고, 재전송할 패킷을 선택할 수 있다는 점에서 차이가 있습니다.

Selective Repeat에서는 송신자와 수신자 모두 윈도우를 유지합니다. 송신자는 여전히 윈도우 내의 패킷을 전송하고, 수신자는 패킷을 받으면 해당 패킷의 ACK를 전송합니다. 그러나 수신자는 모든 패킷을 저장하고, 윈도우 안의 패킷을 개별적으로 확인합니다. 이렇게 하면 수신자는 손상된 패킷을 선택적으로 재전송하고, 나머지 패킷은 ACK로 확인합니다.

Selective Repeat은 Go-Back-N보다 더 복잡한 프로토콜이며, 메모리 및 처리 능력이 더 많이 필요합니다. 그러나 패킷 손실이 적고 대역폭이 좋은 경우, 성능 면에서 Go-Back-N보다 우수할 수 있습니다.

→ 순서 상관없이 일단 저장해놓는다!

→ R3받을 차례지만, R4, R7, R9도 다 받아줌!

→ 왜? receiver window size가 1보다 크기 때문

→ 그리고 잘못된것만 재전송, 나머지는 ACK보냄

선택적 재전송(Selective Repeat)은 슬라이딩 윈도 프로토콜의 일종으로, 송신자가 송신한 프레임 중 수신자가 제대로 받지 못한 프레임만 다시 전송하는 방식입니다. 수신자는 송신자로부터 전송된 프레임 중에서 하나의 프레임이 제대로 수신되지 않으면 해당 프레임의 재전송을 요청하고, 나머지 프레임은 이미 수신되었다는 ACK를 보냅니다. 이 방식은 Go-Back-N ARQ와 달리 수신측이 ACK를 보낼 때 현재까지 제대로 수신된 가장 마지막 프레임의 번호를 함께 보냅니다. 이를 통해 송신자는 송신한 모든 프레임이 아닌, 재전송이 필요한 일부 프레임만을 재전송함으로써 효율적인 데이터 전송을 할 수 있습니다.

예를 들어, 송신자가 프레임 1, 2, 3, 4, 5를 전송하였고 수신자는 프레임 1, 2, 4를 제대로 수신하였다고 가정해봅시다. 이 경우 수신자는 프레임 3을 수신하지 못했다는 NAK를 송신자에게 보내고, 동시에 ACK(5)를 보내 프레임 5를 요청합니다. 이렇게 함으로써 송신자는 다시 프레임 3과 5만을 전송하면 되므로 전송 시간과 대역폭을 절약할 수 있습니다.

시퀀스 번호가 m 비트를 사용한다면, 송신 창과 수신 창은 2m-1 이하이어야 합니다. 이는 시퀀스 번호의 비트 수에 따라 가능한 번호의 범위가 제한되기 때문입니다. 송신 창과 수신 창의 크기가 가능한 번호의 범위보다 크면, 프로토콜의 오버헤드가 증가하고, 비효율적인 전송을 초래할 수 있습니다

NAK

NAK는 Negative Acknowledgement의 줄임말로, 수신 측이 이전에 전송한 프레임 중 일부가 누락된 경우에 사용됩니다. 예를 들어, 수신 측이 1번 프레임을 받지 못했을 경우 NAK(1)을 보내면 됩니다. 이를 통해 송신 측은 NAK을 받으면 해당 프레임을 재전송하고, 기다리지 않고 다음 프레임을 전송할 수 있습니다. 만약 NAK이 없다면 송신 측은 timeout까지 기다려야 합니다.

수신자가 NAK를 보내는 경우는 다음과 같습니다:

1. 프레임이 도착했지만 이전 프레임이 아직 도착하지 않은 경우
   • 예를 들어, 프레임 3은 도착했지만 프레임 1은 아직 도착하지 않은 경우 NAK(1)을 보냅니다.
2. 동일한 시퀀스 번호에 대해 NAK는 한 번만 보내집니다.
   • 예를 들어, 프레임 1을 수신하지 못한 경우 NAK(1)을 보냅니다. 이후 프레임 2와 3을 순서대로 수신하면 NAK를 보내지 않습니다. 그러나 프레임 4를 수신하지 못한 경우에는 NAK(4)를 보낼 수 있습니다.

NAK는 프레임을 받지 못했을 때 ACK 대신 사용됩니다. NAK를 사용하면 타임아웃이 발생하기 전에 누락된 프레임을 다시 전송할 수 있으므로 전송 속도가 향상됩니다.

수신자가 ACK를 보내는 경우는 다음과 같습니다.

수신자는 프레임을 받았을 때, 그리고 이전에 받은 모든 프레임들이 모두 올바르게 받아졌을 때 ACK를 보냅니다. 이전에 받은 프레임 중 하나라도 손상되었다면, 수신자는 해당 프레임에 대한 NAK(부정응답)를 보내고 재전송을 요청합니다.

즉, 수신자는 이전에 받은 모든 프레임들이 제대로 도착했음을 확인하고, 이제 수신자가 기대하는 다음 프레임을 받을 수 있다는 것을 알리기 위해 ACK를 보냅니다.

수신자의 동작은 다음과 같습니다.

1. 프레임(0)을 받았을 때, 수신자는 ACK(1)을 보냅니다.

2. 프레임(1)을 받았을 때, 수신자는 ACK(2)를 보냅니다.

3. 프레임(3)을 받았을 때, 수신자는 NAK(2)를 보냅니다. 이는 프레임(2)가 제대로 도착하지 않았다는 것을 나타내며, 재전송을 요청합니다.

4. 프레임(4)를 받았을 때, 수신자는 아무런 조치를 취하지 않습니다.

5. 프레임(5)를 받았을 때, 수신자는 아무런 조치를 취하지 않습니다.

6. 마지막으로, 프레임(2)를 받았을 때, 수신자는 ACK(6)을 보냅니다. 이전에 NAK를 보낸 것을 보완하기 위해, 다시 프레임(2)를 받았을 때는 ACK를 보내기 때문입니다.

   → 이미 프레임(4)와 프레임(5)를 받았기 때문에 ACK(6)을 보냄!!!

이렇게 수신자는 모든 프레임을 올바르게 받았다는 것을 확인하고, ACK를 보내어 송신자에게 알립니다. 만약 프레임이 손상되었거나 제대로 도착하지 않았다면, NAK를 보내어 재전송을 요청합니다.

💡 Typical timeout period T = RTT+margin(processing time) 💡 RTT = Transmission time of frame + Propagation time of frame + Transmission time of ACK + Propagation time of ACK + Processing time at sender and receiver 💡 전송량 = 전송되는 데이터의 양 ÷ 걸리는 시간 💡 throughput = bandwidth / framesize 💡 Sf + Ssize = Sn 💡 send/receive window ≤ 2^m-1 (m: m bits)