에러 검출 및 복구 (에러 제어)
데이터 전송 중 발생할 수 있는 에러를 검출하고 복구하기 위한 방법들이다.
여기서 에러 검출방법은 이미 지난번에 했다.
https://guhonga.tistory.com/221
데이터 에러 검출 기법
Hamming 코드 데이터 전송 도중 발생한 에러를 검출할 때, 이 때 Hamming 코드가 사용된다.Hamming 코드는 비트 오류를 검출하고 정정할 수 있는 코드이다. 오류가 발생한 위치를 식별하고 수정할 수
guhonga.tistory.com
에러를 복구하는 방법으로 자동 재전송 요청 (Automatic Repeat reQuest, ARQ)이 있는데
ARQ에는 3가지 방법이 있다.
Stop-and-Wait ARQ
송신측은 하나의 프레임을 전송한 후, 수신측의 ACK(Acknowledgement)를 기다린다. 응답을 기다리는 동안 다른 프레임을 전송하지 않는다.
이 프레임은 데이터와 함께 필요한 제어정보(예: 순서번호)를 포함한다.
ACK를 수신하면 다음 프레임을 전송하고, 타임아웃 시 재전송을 요청한다.
수신측 데이터 링크 컨트롤(DLC)에 프레임 오류가 있거나 잘못 수신한 경우, 부정(NAK) 신호를 보내고, 송신측이 NAK 신호를 수신하면 해당 프레임을 재전송한다.
이러한 과정을 통해 오류 발생 시, 오류가 있는 프레임만 재전송할 수 있고
수신측에서 프레임을 성공적으로 수신했는지 여부를 확인할 수 있다.
하지만, 송신측이 프레임을 전송한 후 ACK 또는 NAK 응답을 기다리는 동안 아무것도 전송하지 않기 때문에 데이터 전송의 효율성이 떨어질 수 있다.
Stop-and-Wait ARQ 에러 검출 방법
송신된 데이터 프레임과 응답(ACK 또는 NACK) 모두에 대해 CRC와 같은 에러 검출 코드를 사용하여 에러를 확인한다.
송신 측은 응답이 없거나 지연될 경우, 타임아웃(time-out)을 확인하고 재전송을 시도한다.
수신 측은 프레임이 중복된 것인지 아니면 새로운 것인지 프레임의 순서 번호(sequence number)를 사용하여 구별한다.
중복 문제를 해결하기 위한 순서 번호를 사용하는 방식은 다음과 같다.
1. 순서번호 부여:
- 송신측은 각 전송된 프레임에 송신 번호(SN)를 부여
- SN은 보통 0과 1과 같은 간단한 모듈로 2 값으로 순환
2. 수신측의 확인:
- 수신측은 수신 요청 번호(RN)를 사용하여 송신측의 패킷을 확인
- RN은 수신측이 다음으로 기대하는 프레임의 번호를 나타낸다.
3. 중복 문제 해결:
- 수신측은 SN을 확인하여 프레임이 중복되는지 아니면 새로운 프레임인지 판별한다.
- 만약 중복된 프레임이 수신되면, 수신측은 이를 무시하고 이전의 ACK를 재전송한다.
4. 추가 공간 필요:
- SN과 RN은 패킷 헤더에 추가해야 하므로, 이를 위해 추가적인 공간이 필요하다.
송수신 알고리즘
송신측 알고리즘
- SN ← 0
- 새 프레임을 상위 층으로부터 받아들이고, SN을 할당한다.
- SN을 순서번호로 하여 SN번째 패킷을 전송한다.
- 만약 B로부터 확인 신호를 받고, SN ≠ RN이면,
- SN ← RN으로 세트하고 step 2로;
- 같으면 혹은 타임아웃이면 step 3으로.
수신측 알고리즘
- RN ← 0, 그리고 프레임 수신 대기.
- SN = RN인 정상적인 패킷을 받으면,
- 프레임을 상위 계층에 전달하고,
- RN ← RN + 1;
- 에러 있는 패킷 경우는 RN ← RN.
- A에게 RN을 전송하여,
- 에러 없는 경우 다음 패킷을 요청,
- 에러 있는 경우 재전송을 요구한다.
상태전이 다이어그램
상태 (0, 0)
송신자와 수신자가 모두 초기 상태에 있고, 송신자는 프레임 0을 전송할 준비가 되어있다.
송신자가 프레임 0을 전송하여, 노드 B가 프레임 0을 받으면, 상태 (0, 1)으로 전이된다.
상태 (0, 1)
송신자가 프레임 1을 전송한 후, 수신자로부터 프레임 1의 수신 확인(ACK)을 기다리는 상태다.
송신자가 프레임 1을 전송하면 상태 (1, 0)으로 전이된다.
상태 (1, 1)
송신자가 프레임 0을 전송한 후, 수신자로부터 프레임 0의 수신 확인(ACK)을 기다리는 상태다.
수신자가 프레임 1을 성공적으로 수신하고 ACK를 보내면 상태 (0, 0)으로 전이된다.
만약 ACK를 받지 못하면 프레임 1을 재전송한다.
상태 (1, 0)
송신자가 프레임 1을 전송한 후, 수신자로부터 프레임 1의 수신 확인(ACK)을 기다리는 상태다.
수신자가 프레임 1을 성공적으로 수신하고 ACK를 보내면 상태 (0, 0)으로 전이된다.
만약 ACK를 받지 못하면 프레임 1을 재전송한다.
Go-back-N ARQ
송신측은 여러 개의 프레임을 연속으로 전송할 수 있으며
수신측은 패킷 수신 및 순서번호가 지켜지는지 확인하고, 모든 프레임에 대해 ACK를 보낸다.
만약 수신측에 순서 번호가 맞지 않는 패킷이 수신되면, 오류가 발생한 위치와 관련된 ACK를 보내고
송신측은 이러한 ACK를 받은 후, 필요에 따라 해당 패킷과 그 이후의 모든 패킷을 재전송해야 한다.
패킷이 성공적으로 수신되고, 이에 대한 ACK를 받기 전까지는 윈도우 내의 모든 패킷을 대기해야 한다.
또한 수신 확인 응답 RN을 받기 전에 계속 패킷을 윈도우 크기 n만큼 전송할 수 있다.
여기에서 인 경우는 정지-대기 ARQ와 동일하게 동작하며, 송신측은 ACK를 받을 때까지 대기하게 된다.
Go-back-N ARQ에서 에러가 발생한 경우
에러가 발생한 패킷 이후의 패킷은 모두 재전송되어야 한다.
송신측은 최소한 최근의 n개의 패킷을, 재전송에 대비하여 보관하고 있어야 한다.
위 예시 그림 과정
- 송신측: 패킷 0, 1, 2, 3 전송
- 수신측: 패킷 0, 1 수신 후 패킷 2에서 오류 발생
- 수신측: 패킷 2의 재전송 요청
- 송신측: 패킷 2와 이후 패킷들 재전송
- 수신측: 정상적으로 패킷 2, 3 수신 후 window에 ACK=2 송신
Go-Back-N ARQ에서의 송신단과 수신단의 동작
송신단에서 각 블록은 순서 번호를 가지고 있으며, 송신 윈도우 크기 n에 따라 최대 n개의 블록을 전송할 수 있다.
송신단은 각 데이터 블록에 대해 수신단으로부터 ACK(정상 수신 확인) 또는 NAK(손상된 블록 확인)를 수신하기를 기다린다.
만약 NAK 수신 시, 특정 데이터 블록이 손상되었음을 의미하므로
송신단은 NAK가 수신된 데이터 블록부터 시작하여, 그 이후의 모든 데이터 블록을 재전송한다.
ACK 수신 시, 데이터 블록이 정상적으로 수신되었다는 것을 의미하므로
송신단은 윈도우를 이동시키고, 다음 데이터 블록을 전송할 수 있다.
( 각 패킷에 순서번호를 할당하고, 순서를 하나씩 증가(패킷 이동)시킴 )
그런데 Go-Back-N ARQ에서 위와 같이 delay되는 time out이 윈도우 크기 n과 비교해서 매우 큰 경우 문제가 된다.
너무 짧은 시간은 필요 이상의 재전송을 유발하고,
너무 긴 시간은 수신측 대기 시간을 증가시켜 전송 효율을 떨어뜨릴 수 있기 때문에
적당한 trade - off가 필요하다.
Selective Repeat ARQ
송신측은 여러 프레임을 전송할 수 있으며, 수신측은 에러가 발생한 특정 프레임만 재전송 요청기 때문에
이 방식은 Go-back-N ARQ보다 효율적이다.
수신단은 정상적으로 수신된 블록을 버퍼에 저장하고, 손상된 블록이 재전송될 때까지 기다리는 것으로
블록 순서를 재조립할 수 있다.
송신단에서는 전송 데이터 블록에 대한 ACK가 도착할 때까지 버퍼에 보관해야 하며,
NAK가 도착하면 해당 블록만 선택적으로 재전송하기 때문에 버퍼 관리가 복잡하다.
위 그림에 대한 과정은 다음과 같다.
- 송신단에서 데이터 블록 1, 2, 3...을 연속적으로 전송
- 수신단은 데이터 블록 1과 3은 정상적으로 수신되었으나, 데이터 블록 2에서 오류가 발생
- 수신단은 데이터 블록 2에 대해 NAK를 송신단에 전송
- 송신단은 NAK를 수신한 후, 데이터 블록 2를 재전송
- 수신단은 재전송된 데이터 블록을 수신하고, 정상적으로 모든 수신된 데이터 블록에 대해 ACK를 송신단에 전송