10장_오류제어와 흐름제어

[10-1] 에러제어(Error Control)

에러제어(Error Control)

 - 에러제어에는 검출, 복구, 전진에러 수정이 있다.

 - 에러제어 방식

  · 에러를 무시 

  · 루프(loop) 혹은 에코(ehco)에 의한 점검 : 수신된 데이터를 송신측에 그대로 전송해서 전송 중에 에러가 있는 판단

  · 에러 검출 방식 = 패리티 비트 방식, 블록 합 검사, CRC, Checksum

  · 에러 검출 후 재전송 (ARQ : Automatic Repeat reQuest)

    - stop-and-wait ARQ

    - 연속적 ARQ = Go-Back-N ARQ / Selected Repeat

  · 전진 에러 수정(FEC : Forward Error correction)

 

오류 검출 (Error Detection)

 - 송신측에서 보내고자 하는 원래의 정보 이외에 별도로 잉여분의 데이터를 추가

 - 수신측에서는 이 잉여(Redundancy) 데이터를 검사함으로써 오류 검출이 가능

 - 패리티 검사, 블록 합 검사, CRC(Cyclic Redundancy Check), Checksum 등

 

패리티 검사(Parity Check)

 - 한 블록의 데이터 끝에 한 비트 추가하는 가장 간단한 에러 검출 기법

 - 구현이 간단하여 널리 사용

 - 종류

  · 짝수 패리티 : 1의 전체 개수가 짝수 개

  · 홀수 패리티 : 1의 전체 개수가 홀수 개

 - 동작 과정

  · 송신측

   - 짝수/홀수 패리티의 협의에 따라 패리티 비트 생성

   - ASCII 문자(7bit) + 패리티 비트(1bit) 전송

  · 수신측

   - 1의 개수를 세어 오류 유무 판단

   - 맞지 않을 경우 재전송 요청

 - 단점 : 짝수개의 오류는 검출 불가 (원시 데이터의 정보 중 짝수개의 비트가 오류일 경우 검출 불가)

 

블록 합 검사 (Block Sum Check)

 - 이차원 패리티 검사 : 가로와 세로로 두 번 과찰

 - 검사의 복잡도 증가 : 다중 비트 오류(Multi-bit-Error)와 집단 에러(burst Error)를 검출할 가능성을 높임

 - 동작 과정

  1. 데이터를 일정크기의 블록으로 묶음

  2. 각 블록을 배열의 열로 보고 각 행의 패리티를 수행한 결과를 마지막 열에 추가

  3. 모든 행에 대해 패리티 비트가 추가되면, 열을 중심으로 첫번째 열부터 마지막에 각 행의 패리티 비트로 구성된

    열까지 다시 패리티를 수행하여 마지막 행에 추가한다. 이러한 작업으로 블록을 구성

  4. 송신측은 재구성된 블록을 행단위로 전송 

  5. 수신측은 송신측과 미리 약속된 크기에 데이터를 수신하게 되면 블록을 구성하고, 블록합을 검사함으로써 에러검출

  6. 검사가 완료되면 수신측은 패리티 비트를 제거하여 순수한 데이터만 얻게 됨

 - 단점

  · 다중 비트 에러, 집단 에러를 검출할 확률은 증가했지만, 블록 합 검사로 검출하지 못하는 패턴 존재

  · 하나의 블록(데이터단위) 내에서 두 비트가 송상되고, 다른 블록(데이터단위)에서 정확히 같은 위치의 두 비트가

   손상되면 블록 함 검사는 에러를 검출하지 못하게 된다.

 

CRC(Cyclic Redundancy Check)

 - 현재 컴퓨터에서 널리 사용되고 잇는 에러 검출 방법

 - 다항식 코드(polynomial codes)로도 알려져 있다.

 - 패리티는 문자단위 검사 방법이라면 CRC는 연속적인 2진 데이터 전송에서 전체 블록을 대상으로 에러 검출

 - 전체 블록 검사를 할 수 있고, 나눗셈 기반으로 하므로 패리티보다 효율적이고 에러 검출 능력이 뛰어남

 - 동작과정

  1. 전송되는 메시지는 하나의 2진수로 간주된다.

  2. 이 수는 특정한 재수(generator)에 의해 나누어지며 이때 생긴 나머지는 송신프레임에 첨부된다.

   이 나머지를 CRC비트 또는 FCS(Frame Check Sequence), BSS(Block Check Charater)라고 함

  · 특정한 이진 소수에 의해 나누어짐

  · 나머지는 송신되는 프레임에 첨부 (나머지를 BCC라고도 함)

  3. 프레임이 수신되면 수신기는 같은 재수를 사용하여 나눗셈의 나머지를 검사

  4. 수신측에서 검사결과에서 나머지가 0이면 에러가 없음을 의미

 

Checksum

 - 데이터의 정확성을 검사하기 위한 용도로 사용되는 방법

 - 데이터의 전송이 제대로 되었는지를 확인하기 위해 전송데이터의 맨 마지막에,

   앞서 보낸 데이터를 다 더한 합계를 보수화 하여 전송

 - 수신측에서는 모든 수를 합산하여 검사하는 방법

 - 체크섬은 데이터 단위를 세그먼트로 나누어 에러검출을 수행하는 방법

 

오류 복구 (Error Recovery)

 - 에러복구의 기본은 재전송 요청

 - 수신측은 수신한 데이터의 에러 검출과정을 수행

 - 에러가 검출되면 송신측에 재전송을 요청하여 데이터를 다시 수신함으로서 에러 없는 데이터를 수신하게 됨

 - 이러한 과정을 ARQ(Automatic Repeat reQuest)라고 함

 

Stop-and-Wait ARQ

 - 가장 고전적인 방식

 - 송신측이 하나의 프레임을 전송 후 수신측에서는 해당 프레임의 오류 유무를 판단

 - 오류가 없는 경우 송신측에게 ACK 전송 / 오류가 있는 경우 NAK을 전송하여 재전송 유도

 - 특징 

  · 흐름제어 방식 중에 가장 간단한 형태

  · 한번에 한 개의 프레임만 전송 

  · 한 개의 연속적인 블록이나 프레임으로 메시지를 전송할 때 효율적

  · 전송되는 프레임의 수가 한 개이므로 송신측이 기다리는 시간이 길어져 전송 효율이 떨어질 수 있음

  · 송/수신측 간의 거리가 멀수록 각 프레임 사이에서 응답을 기다리는데에 낭비되는 시간 때문에 전송 효율 감소

 - 동작과정

  1. 송신측은 각 프레임을 전송 루 확인응답(ACK, NAK)를 받을 때 까지 다음 전송을 중지하고 대기 (타이머 동작)

  2. 수신측은 수신 프레임에 대하여 오류검사를 수행하고 오류가 없으면 ACK, 있으면 NAK을 송신

  3. 송신측에서는 NAK를 수신할 경우 프레임을 재전송

종류	특징
Stop-and-Wait	- 송신측에서 각 프레임을 하나씩 보내고 수신측으로부터 확인 응답을 받는 방식 - 한번에 한 개의 프레임만 전송 - 송신측이 기다리는 시간이 길어져 전송효율이 낮음
Sliding-window	- 확인 응답 없이 한번에 약속된 윈도우 크기만큼 전송 - 한번에 윈도우 크기만큼 프레임 저송 - 여러개의 프레임이 동시에 전송되느모 전송 효율이 높음

 

Go-Back-N ARQ

 - 연속적 ARQ(continue ARQ)의 한 종류

 - Stop-and-Wail에서 수신응담 대기에서 발생하는 오버헤드를 감소하기 위해 설계

 - 에러가 발생한 프레임부터 모두 다시 재전송 하는 방식

 - 특징

  · 송신측은 확인 응답이 올 때까지 모든 프레임의 사본을 보유하고 있어야함

  · 송신측은 n개의 sliding window를 가지고 있음

  · 프레임에 순서번호를 삽입

  · 포괄적인 수신확인을 사용하여 여러개의 프레임에 대한 수신확인을 하나로 수행

  · 오류 발생 프레임부터 모두 재전송을 하므로 불필요한 재전송 많음

 - 동작과정

  1. 여러개의 프레임들은 순서번호를 붙여서 송식

  2. 수신측은 순서 번호에 따라 ACK, NAK를 보냄

  3. 송신측은 1-5번 프레임을 전송하였으나 NAK3을 수신하였으므로 3-5번 프레임까지 모두 재전송(오버헤드 발생)

 

Selective Repeat

 - 연속적 ARQ의 한 종류

 - 오류가 발생한 프레임만 재전송

 - Go-Back-N의 단점인 불필요한 프레임 재전송으로 인한 대역폭 낭비를 줄이지만, 버퍼 사용으로 구현이 까다롭다.

 - 특징

  · Go-Back-N과 달리 프레임 순서에 영향을 받지 않음

  · 송신측과 수신측은 모두 n개의 동일한 크기의 Sliding-window를 갖고 있다

  · 수신측은 프레임의 순서에 상관없이 수신 (버퍼 필요)

  · 개별적 수신확인 가능

 - 동작과정

  1. 에러 검출된 프레임에 대한 개별적 재전송 요구 가능

  2. 에러나 프레임만 재전송 요구

  3. 수신측에서 순서정렬이 필요 (버퍼 필요)

 

항목	Go-Back-N	Selective Repeat
Sliding-window	송신측만 소유 수신측은 버퍼 하나만 필요	송/수신측 모두 동일한 크기 소유
수신 확인	포괄적 수신 확인	개별적 수신 확인
재전송 방식	오류발생 또는 잃어버린 프레임 이후의 모든 프레임을 재요청하거나 타임아웃으로 자동 재송신	오류발생 또는 잃어버린 프레임에 대해서만 재요청 또는 타임아웃으로 인한 자동 재송신
프레임 수신 방법	프레임의 송신 순서와 수신 순서가 동일해야 수신	순서와 상관없이 윈도우 크기 만큼의 범위 내에서 자유롭게 수신
상위 계층으로의 전달	수신 프레임이 순서적으로 들어올 때 하나씩 상위 계층으로 올려보냄	순서에 상관없이 수신하여 일정수의 윈도우 만큼이 되면 전달
장/단점	간단한 구현 적은 수신측 버퍼 사용	구현 복잡  버퍼 사용 용량 큼  보다 작은 재전송 대역폭

 

전진에러 정정과 재전송

 - 수신측에서 오류를 정정

 - 재전송을 요청하는 방법 (ARQ)

  · 해당 프레임을 재전송 요청하여 다시 수신하는 방법

  · 구현이 단순

  · 재전송으로 인한 대역폭을 요구

  * 오류 발생을 검출하여 송신자에게 다시 보내줄 것을 요청하는 과정

 - 오류 정정 코드를 삽입, 수신측에서 직접 정정하는 방법 (FEC : Forward Error Correction)

  · 원래 코드에 에러정정코드를 삽입하는 방법

  · 구현 복잡이 복잡하나 재전송으로 발생되는 대역폭의 낭비 감소

  · 회선 전송시간이 긴 경우 FEC를 사용하는 것이 효율적

  · FEC를 위한 별도의 코드 삽입으로 전송 시 대역폭을 요구

  * 수신자가 메시지의 중복비트를 이용하여 메시지를 추측해가는 과정

	ARQ	FEC
장점	- CRC를 이용해하기 때문에 코드양이 크지 않음 - 원시프레임의 크기에 CRC만 붙음 - 필드에 오류 정정 코드 불필요 - 간단한 구현	- 재전송에 드는 대역폭이 필요 없음 - 수신측에서 오류를 정정
단점	- 재전송에 드는 대역폭 손실 큼 - 수신측이 자체 오류정정을 못함	- 에러정정 코드로 인한 중복이 커짐 - 오류 정정 코드의 삽입으로 프레임 크기 증가 - 복잡한 구현

 

 

단일 비트 오류 정정 (Single bit error correction)

 - 수신된 데이터의 한 비트가 에러가 있을 시 이를 정정하기 위한 기법

 - 오류가 발생한 위치를 알아야 함

 - 8가지 상이한 상태를 구별할 충분한 패리티 비트가 필요

 

해밍코드

 - 스스로 데이터 에러를 검출하고 수정하는 코드

 - 원래의 데이터들을 이용하여 연산한 결과를 덧붙여 수신측에서 에러를 검출하여 해당 비트를 정정할 수 있게 함

 - 단일 에러 수정 및 다주 에러의 검출이 가능

 - 해밍코드는 비트 수에 따라 해밍 비트의 수가 결정

 · n : 사용자 데이터의 크기 

 · m : 해밍 비트의 크기

 - 해밍코드는 각각 패리티 비트 연산을 수행하여 정해지는 잉여의 데이터들을 삽입하여 에러의 위치를 찾아 이를

 정정하기 위한 방법

 

상승코드(Convolutional Code)

 - 상승코드는 현재의 입력이 과거의 입력에 대하여 영향을 받아 부호화 하는 방법이며 비블록화 코드 방법 중 하나

 - 상승 코드 구현 시 필요한 기본 구성요소

  · Shift register : 정보를 암호화할 때 사용되는 일종의 기억장치 (자리이동 레지스터)

  · 생성 다항식 : shift register와 결과 값을 연결할 떄 사용 (XOR)

 - 출력

  · 원시비트들을 shift register에 통과 시킴

  · modulo-2 가산기 (XOR)를 사용하여 전송비트 생성

 

	종류	특징
오류검출기법	패리티검사	- 한 블록의 데이터 끝에 한 비트를 추가하는 가장 간단한 방법 - 오류가 짝수 개 발생하게 되면 검출 불가능
	블록 합 검사	- 각 비트를 가로와 세로로 두 번 관찰하여 데이터에 적용되는 검사의 복잡도를 증가시킴으로써   오류 검출능력 증대  - 하나의 데이터 단위 내에서 두 비트가 손상되고 다를 데이터 단위 내에서 정확히 같은 위치의   두 비트가 손상되면 블록 합 검사는 오류를 검출하지 못함
	CRC	- 전체 블록 검사를 수행 - 이진 나눗셈을 기반으로 패리티 비트보다 효율적이고 오류검출 기능이 뛰어남
	Checksum	- 전송 데이터의 마지막에 앞서 보낸 모든 데이터를 다 합한 합계를 보수화 하여 보냄 - 수신측에서는 모든 수를 합산하여 검사하는 방법
오류정정기법	단일비트오류정정	- 오류를 정정하기 위해서는 오류 위치를 파악해야함 - 위치를 찾기 위한 패리티 비트를 추가
	해밍코드	- 데이터와 패리티 비트간의 관계를 이용 - 각각 다른 데이터 비트들의 조합을 위한 패리티인 4개의 패리티 비트 삽입
	상승코드	- 현재 값과 과거 값 사이의 상관관계에 의한 값을 얻음 - 미리 약속된 디코딩 트리를 갖고 있어야 함 - 해밍거리를 이용하여 오류에 대한 신뢰성 보장