Data Communications 제 10 장 오류 제어와 흐름 제어.

Presentation on theme: "Data Communications 제 10 장 오류 제어와 흐름 제어."— Presentation transcript:

1 Data Communications 제 10 장 오류 제어와 흐름 제어

2 목차 10.1 오류 제어 (Error Control) 10.2 흐름 제어 (Flow Control)

3 10.1 오류 제어(1/43) 오류 검출 (Error Detection)
송신측에서 보내고자 하는 원래의 정보 이외에 별도로 잉여분의 데이터를 추가 수신측에서는 이 잉여(Redundancy) 데이터를 검사함으로써 오류검출이 가능 종류 패리티 검사, 블록 합 검사, CRC(Cyclic Redundancy Check), Checksum등

4 10.1 오류 제어(2/43) 패리티 검사(Parity Check) 한 블록의 데이터 끝에 한 비트 추가
구현이 간단하여 널리 사용 종류 짝수 패리티 : 1의 전체 개수가 짝수개 홀수 패리티 : 1의 전체 개수가 홀수개 동작과정 송신측 짝수 또는 홀수 패리티의 협의에 따라 패리티 비트 생성 ASCII 문자(7bit) + 패리티 비트(1bit) 전송 수신측 1의 개수를 세어 오류 유무 판단(짝수 또는 홀수) 맞지 않다면 재전송 요청

5 10.1 오류제어(3/43) 예 단점 홀수 패리티 사용 전송하고자 하는 데이터 : 1101001
1의 개수를 홀수로 하기 위해 패리티 비트를 1로 지정 패리티 비트 추가한 최종 전송 데이터 : 수신측은 패리티 비트를 포함한 데이터 내의 1의 개수를 세어 홀수인지 판단 홀수가 아니면 재전송 요청 단점 짝수개의 오류는 검출 불가 : 짝수개의 오류가 발생하여 1의 개수가 홀수인 경우

6 10.1 오류제어(4/43) 블록 합 검사(Block Sum Check) 이차원 패리티 검사 : 가로와 세로로 두 번 관찰
검사의 복잡도를 증가 다중 비트 오류와 폭주오류를 검출할 가능성을 높임 동작과정 데이터를 일정크기의 블록으로 묶음 각 블록을 배열의 열로 보고 패리티 비트를 계산하여 추가 각 블록의 행에 대한 패리티 비트를 계산하여 추가한 후 전송

7 10.1 오류제어(5/43) 예 전송하고자 하는 데이터 그림의 최하위 비트들이 함께 더해지고 블록 합에 따라 짝수 혹은 홀수 중 하나의 패리티를 얻음 두 번째 비트들이 더해지고 패리티 비트가 얻어짐 블록 합의 마지막 비트는 블록 합 데이터 단위 자체를 위한 패리티 비트이고 블록 내의 모든 패리티 비트들을 위한 비트임

8 10.1 오류제어(6/43) 단점 하나의 블록에서 두개에 오류가 생기고, 다른 블록의 동일한 위치에서 두개의 오류가 발생한 경우 검출 불가 두번째 블록과 마지막 블록의 동일 위치에 각 두개의 오류발생

9 10.1 오류제어(7/43) CRC(Cyclic Redundancy Check) 전체 블록검사 이진 나눗셈을 기반 계산 방법
메시지는 하나의 긴 2진수로 간주 특정한 이진 소수에 의해 나누어짐 나머지는 송신되는 프레임에 첨부 나머지를 BCC(Block Check Character)라고도 함 프레임이 수신되면 수신기는 같은 제수(generator)를 사용하여 나눗셈의 나머지를 검사 나머지가 0이 아니면 오류가 발생했음을 의미

10 10.1 오류제어(8/43) 부호화 과정 각 비트들의 값을 보면서 하나의 함수를 만드는 과정
정보 비트를 전송비트의 다항식에 의한 표현으로 변환

11 10.1 오류제어(9/43) CRC 비트의 생성 캐리(Carry)가 없는 Modulo-2 연산
전송 하고자 하는 데이터 : 원하는 BCC 비트의 길이 : n 제수의 길이 : n+1 연산과정 전송하고자 하는 데이터 뒤쪽에 n개의 0을 삽입 제수로 나눔 데이터 뒤의 n개의 0을 R로 대체 전송

12 10.1 오류제어(10/43) 오류 검출 방법 수신된 데이터를 송신측과 합의된 제수로 나눔 연산결과 나머지가 0이면 오류 없음
그렇지 않다면 재전송 요청

13 10.1 오류제어(11/43) 하드웨어로 구성된 CRC 계산된 BCC는 쉬프트레지스터(Shift register)에 축적
레지스터 중에 있는 각 구분은 생성다항식의 등급과 동일 Exclusive-OR요소들의 수도 또한 그 다항식과 관계되는 수 종류 CRC-16 CRC-32 CRC-CCITT 등

14 10.1 오류제어(16/43) CRC-16 8비트 캐릭터용의 동기방식에 응용 BCC축적은 16비트
생성다항식 : x16+x15+x2+1 검출능력 집단오류검출은 최대 16비트 길이까지 가능 오류의 집단이 16비트보다 큰 경우는 99%이상의 확률

15 10.1 오류제어(17/43) 송신측

16 10.1 오류제어(18/43) 수신측

17 10.1 오류제어(15/43) CRC-CCITT 유럽시스템들의 표준 BCC
생성다항식 : x16+x12+x5+1 집단 오류의 검출은 최대 16비트 길이까지 됨

18 10.1 오류제어(16/44)

19 10.1 오류제어(19/43) Checksum 전송 데이터의 맨 마지막에 앞서 보낸 모든 데이터를 다 합한 합계를 보수화하여 전송 수신측에서는 모든 수를 합산하여 검사하는 방법 동작과정 송신측 데이터 단위를 n(보통은 16) 비트의 여러 세그먼트로 나눔 이 세그먼트들은 전체 길이도 또한 n비트가 되도록 1의 보수 연산을 이용하여 합산 전체 합은 보수화되고 원래 데이터 단위의 끝에 삽입 이렇게 확장된 데이터 단위는 네트워크를 통해 전송

20 10.1 오류제어(20/43)

21 10.1 오류제어(21/43) 수신측 검사 합을 포함하여 모든 세그먼트들을 더했을 때 모든 비트가 1이 나오지 않으면 오류
송신측에서 검사 합을 최종 삽입할 때 1의 보수를 삽입하기 때문에 원래의 세그먼트들의 합을 더해주면 1이 되기 때문

22 10.1 오류제어(22/43) 송신측 수신측 전송하고자 하는 데이터 : (11100101, 01100110, 11100110)
최종 데이터 ( , , , ) 수신측 수신된 데이터 : ( , , , ) 최종 합은 1이며, 오류 없음

23 10.1 오류제어(16/43)

24 10.1 오류 복구(23/43) 오류 복구 Stop-and-Wait ARQ 송신측이 하나의 프레임을 전송
수신측에서는 해당 프레임의 오류유무를 판단 오류가 없을 경우 송신측에게 ACK를 전송 오류가 있는 경우 NAK를 전송하여 재전송 유도 특징 흐름제어 방식 중에 가장 간단한 형태 한번에 한 개의 프레임만 전송 한 개의 연속적인 블록이나 프레임으로 메시지를 전송할 때 효율적 전송되는 프레임의 수가 한 개이므로 송신측이 기다리는 시간이 길어져 전송효율 저하 송ㆍ수신측 간의 거리가 멀수록 각 프레임 사이에서 응답을 기다리는 데에 낭비되는 시간 때문에 효율 저하

25 10.1 오류 복구(24/43) 동작 과정 송신측은 데이터 전송 후 ACK, NAK를 받을 때 까지 대기
수신측은 수신 프레임에 대하여 오류검사를 수행 오류가 없으면 ACK를 송신 오류가 있으면 NAK를 송신 송신측에서는 NAK를 수신할 경우 프레임을 재전송

26 10.1 오류 복구(24/43)

27 10.1 오류 복구(25/43) Go-Back-N ARQ 연속적 ARQ(continuous ARQ)
수신응답 대기의 오버헤드 감소 특징 프레임의 수신은 순차적 프레임에 순서번호를 삽입 포괄적 수신확인 오류 발생 프레임 부터 모두 재전송 동작과정

28 10.1 오류 복구(25/43)

29 10.1 오류 복구(26/43) Selective Repeat 연속적 ARQ 오류가 발생한 프레임만 재전송 특징 동작과정
송신측과 수신측은 동일한 크기의 Sliding-window를 보유 수신측은 프레임의 순서에 상관없이 수신 각각의 프레임에 대한 수신확인을 수행 동작과정

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

31 10.1 전진 오류 정정(28/43) 전진오류 정정(Forward Error Correction) 수신측에서 오류를 정정
ARQ와 FEC 재전송 요청하는 방법(ARQ) 구현이 단순 재전송으로 인한 대역폭을 요구 오류 정정 코드를 삽입, 수신측에서 직접 정정하는 방법(FEC) 구현 복잡 FEC를 위한 별도의 코드 삽입으로 전송 시 대역폭을 요구

32 10.1 전진 오류 정정(29/43) 단일 비트 오류 정정(Single bit error correction) 해밍코드
오류가 발생한 위치를 알아야 함 7비트 데이터의 단일 비트 오류 정정을 위해서는 8가지의 상이한 상태를 구별할 패리티 비트가 필요 해밍코드 코드의 구성 연산방법 1의 값을 가진 비트의 위치값을 이진수로 Exclusive-OR한다.

33 10.1 전진 오류 정정(30/43) 최종형태(전송) 수신측 오류 검출 및 정정 방법 오류가 없는 경우
수신한 데이터내의 1의 값을 갖는 비트의 위치값을 계산

34 10.1 전진 오류 정정(31/43) 오류가 발생한 경우 수신 프레임
결과가 1011 이 나왔고, 십진수로 변환하면 11이라는 값이 나오므로 11번째 비트에 오류 발생 오류정정 : 비트값이므로 0은 1로, 1은 0으로 변환

35 10.1 전진 오류 정정(32/43) 단일오류의 수정 및 이중오류의 검출이 가능
n개의 가지 수 중에서 한 가지를 지정하는데 필요한 최소의 비트 수는 log2n 오류가 없는 경우를 검출하기 위해 한 비트를 추가 m ≥ log2(n+1), 즉 2m ≥ n+1 = m+k+1 해밍코드 된 블록은 (n, n-m)으로 표현 해밍코드의 형태 (15, 11) (511, 502) (4095, 4083) 등 블록사이즈와 효율은 비례 전송 중 3개 이상의 간헐적 오류에 의해 파괴될 가능성 수반

36 10.1 전진 오류 정정(33/43) 상승코드(Convolutional Code) 길쌈코드(길쌈부호)
IS-95(CDMA)나 IMT-2000과 같은 이동통신에서 주로 사용 응용 기술 바이터비 코드(Viterbi code) 터보 코드(Turbo code) 현재의 입력이 과거의 입력에 대하여 영향을 받아 부호화되는 방법 비블록화 코드 구성 요소 쉬프트 레지스터(shift register) : 정보를 암호화할 때 사용되는 일종의 기억장치 생성다항식 : 쉬프트 레지스터와 결과 값을 연결할 때 사용(XOR) 출력 원시비트들을 쉬프트 레지스터에 통과시킴 modulo-2 가산기를 사용하여 전송비트 생성

37 10.1 전진 오류 정정(34/43) 동작과정 1최초의 모든 쉬프트 레지스터는 0으로 설정
각 입력 측으로부터 한 비트씩 쉬프트 레지스터로 삽입 가산기는 쉬프트 레지스터의 값들을 modulo-2연산을 통하여 계산 멀티플렉싱 스위치는 가산기의 값을 차례로 하나씩 취함 멀티플렉싱 스위치에서 취한 값들을 나열한 것이 출력 값 전송

38 10.1 오류제어(35/43) 예 구성 쉬프트 레지스터 4개, 입력 1개, 출력 5개 -> (k, L, v) : (4,1,5) 입력 x=(1, 1, 0, 1) 과정 입력의 첫 번째 비트 1이 들어가면 s=(1, 0, 0, 0)로 전이 가산기는 각 s의 값을 계산하고, y=(1, 1, 1, 1, 1)이 출력 위와 같은 과정을 x의 4비트 값에 대해 모두 수행 전송되는 y값 y=( )

39 10.1 오류제어(36/43) 디코딩 경계값(Threshold) 디코딩 순차적(sequential) 디코딩
짧은 코드 적은 수의 오류 포함 순차적(sequential) 디코딩 Wozencraft에 의해 발명 오류제어 방법 강력 회로의 복잡도 증가 FEC응용의 주류로 기대 기본개념은 디코딩 트리를 이용하여 가능성 높은 코드를 검색

40 10.1 오류제어(37/43) 디코딩 예 오류가 없는 경우 수신데이터 y = (11111 10101 01101 11011)
처음 입력, 아래쪽으로 이동 다음 값 다시 아래쪽으로 이동 이렇게 y의 각 값을 따라가면 최종위치 아래방향 1, 위 0의 값을 갖게 됨 이렇게 나온 값은 (1, 1, 0, 1) x=(1, 1, 0, 1)값과 동일

41 10.1 오류제어(38/43) 오류가 있는 경우 y=(11111 10101 01101 11011) 수신데이터
r = ( ) r의 처음 5비트가 l=0의 위치에 있는 노드에서 나뉘어 지는 00000과 11111의 각각의 해밍거리를 비교, 작은 쪽으로 패스 결정 00000과는 3비트의 차이가, 11111과는 2비트의 차이가 있으므로 11111쪽으로 결정 두번째 비트열 10110은 01010과 3비트, 10101과는 2비트이므로 아랫쪽으로 결정 위와 같은 방법을 반복 마지막에 을 거쳐 도달하게 되며, 이때 역시 정확한 x값을 얻게 됨

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

43 10.1 오류제어(40/43) 오류 복구 및 정정 기법의 응용 FEC와 ARQ 비 고 FEC ARQ 장 점 단 점
수신측에서 오류를 정정 재전송을 하지 않아 적은 대역폭 사용 필드에 오류 정정 코드 불필요 간단한 구현 원시프레임의 크기에 CRC만 붙음 단 점 오류 정정 코드의 삽입으로 프레임 크기 증가 복잡한 구현 수신측이 자체 오류정정을 못함 재전송에 드는 대역폭 손실 큼

44 10.1 오류제어(41/43) ARQ가 적절한 응용 주기적으로 인터럽트가 가능한 형식으로 전송하는 데이터의 전송응용
FEC에 비해 경량 신속한 전송 가능 응용분야 종이 혹은 자기테이프장치는 전송된 메시지의 사본을 만들 수 있어 ARQ에 적합 ARQ의 응용에서는 어떤 코드의 검출능력이 실질적으로 그것의 수정 능력보다 더 커야 한다. 즉 코드의 잉여도가 크지 않으면 ARQ기법이 FEC보다 유리 오류가 집단적으로 사용되는 경우 ARQ는 데이터 자체에 대한 재전송을 요청하기 때문에 오류의 수와는 직접적인 상관관계가 없어 적절 평균 비트 오류율이 현저하게 줄어든 현재의 네트워크에서는 경량의 ARQ가 FEC보다 적합 간단한 패리티검사코드는 그 경제성으로 인하여 리얼타임 폴링에 사용

45 10.1 오류제어(42/43) FEC가 적절한 응용 송수신측 사이에 인터럽트를 받지 않는 연속적인 형태로 데이터가 교환되는 응용에 적합 터미널이 버퍼가 없어도 됨 응용분야 역 채널이 ARQ에 만족할 만한 사항이 아닐 경우 채널의 전파지연시간이 너무 길어 Stop-and-Wait ARQ가 부적합한 경우에 적절 4800bps이상 속도의 시분할 멀티플랙서들 사이에서의 전이중방식 전송은 데이터 전송과정에서의 인터럽트가 정상적으로는 허용될 수 없으므로 FEC의 사용이 적합

46 10.1 오류제어(43/43) ARQ나 FEC 어느 것이나 이용될 수 있는 응용

47 10.2 흐름제어(1/9) 정의 송신기가 확인 응답을 기다리기 전에 보낼 수 있는 데이터의 양을 제한시키기 위해 사용되는 기법 목적 버퍼의 오버플로우(overflow)로 인한 데이터의 손실방지 네트워크 자원을 낭비하는 재전송 방지

48 10.2 흐름제어(2/9) Xon/Xoff 컴퓨터와 주변기기간의 비동기 통신 제어에 사용되는 프로토콜
모뎀에서 데이터의 흐름제어를 위해 사용 특징 컴퓨터와 주변기기간의 상이한 전송속도로 인해 발생되는 통신상의 문제를 해결 부호화된 문자로 비트통신에서 인식되지 않을 가능성 수신측이 송신측의 데이터 송신을 제어

49 10.2 흐름제어(3/9) 동작과정 컴퓨터는 프린터에게 출력할 데이터를 전송
컴퓨터가 보내는 속도보다 프린터가 출력하는 속도가 느리기 때문에 프린터는 버퍼가 꽉 차게 되면 Xoff 를 보내어 컴퓨터의 송신을 잠시 멈춤 버퍼에 여유가 생기면 프린터는 다시 컴퓨터에게 송신을 하라는 Xon을 전송 컴퓨터는 데이터를 계속해서 송신 이러한 과정이 컴퓨터가 데이터를 모두 송신할 때 까지 계속

50 10.2 흐름제어(4/9) RTS/CTS RS-232C에 사용 모뎀을 이용한 통신에서 상이한 보오율을 조정
산업용 네트워크에서 사용 특징 충돌방지를 위해 상호간 전송예비신호 전송 특정 핀을 이용하여 원하는 신호 전달

51 10.2 흐름제어(5/9) 동작과정 A는 보내고자 하는 데이터가 있을 때 4번 핀을 이용하여 RTS신호 set(raising:1) B는 이에 받을 준비가 되었다는 CTS를 5번 핀을 set(raising:1) A는 응답을 받고, 2번 핀을 이용하여 실제 데이터를 전송 이때 B측이 데이터를 더 이상 받지 않기를 원하면 5번 핀을 reset(lowering:0) A는 이를 알아채고 데이터 송신 중단

52 10.2 흐름제어(6/9) Xon/Xoff와 RTS/CTS의 비교 비 고 Xon/Xoff RTS/CTS 공통점 차이점
비 고 Xon/Xoff RTS/CTS 공통점 데이터의 흐름을 제어 모뎀에서 송/수신 흐름 제어용으로 사용 차이점 흐름제어를 문자형 프로토콜을 사용하여 제어 수신측이 주가 됨 흐름제어에 물리적 신호를 사용 송신측이 주가 됨

53 10.2 흐름제어(7/9) Sliding-window(연속적 ARQ)
송신측의 송신된 하나의 프레임과 수신측의 수신확인 프레임간의 1:1대응 방식을 탈피 송수신측에 버퍼를 이용한 전송방식 수신측의 응답방식은 포괄적 수신확인 허용 특징 수신측으로부터 응답 메시지가 없더라도 미리 약속한 윈도우의 크기만큼의 데이터 프레임을 전송 송수신 윈도우 사이즈 동일 수신측에서는 확인 메시지를 이용하여 송신측 윈도우의 크기를 조절, 전송속도 제한

54 10.2 흐름제어(8/9) 동작과정 최대 윈도우 크기 : 7(0~7) 빗금 친 부분 송신측 : 전송 가능 범위
수신측 : 수신 가능 범위

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