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 오류 검출 (Error Detection)
송신측에서 보내고자 하는 원래의 정보 이외에 별도로 잉여분의 데이터 를 추가 수신측에서는 이 잉여(Redundancy) 데이터를 검사함으로써 오류검출이 가능 종류 패리티 검사, 블록 합 검사, CRC(Cyclic Redundancy Check), Checksum등

4 오류 복구 기본은 재전송을 요청 수신측 : 수신 받은 데이터에 대한 오류 검출 과정 수행 송신측에 재전송을 요청
ARQ ( Automatic Repeat reQuest) : 수신측에서 오류가 검축된 데이터에 대한 재전송을 요청하는 일련의 과정 Stop-and-wait ARQ(Idle ARQ), Go-Back-N ARQ, 선택적 재전송(Selective repeat ARQ),

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

6 동작 과정 송신측은 데이터 전송 후 ACK, NAK를 받을 때 까지 대기 수신측은 수신 프레임에 대하여 오류검사를 수행
3번 프레임의 전송 중 오류가 발생한 경우 수신측은 NAK를 전송 송신측은 NAK를 수신하면 3번 프레임을 재전송

7 2) Go-Back-N ARQ 연속적 ARQ(continuous ARQ) 수신응답 대기의 오버헤드 감소 특징 동작과정
프레임의 수신은 순차적 프레임에 순서번호를 삽입 포괄적 수신확인 오류 발생 프레임 부터 모두 재전송 동작과정 수신측이 4번 프레임이 잘못되었음을 인지하고 NAK를 전송 송신측은 4번부터 모두 재전송

8 3) Selective Repeat 연속적 ARQ 오류가 발생한 프레임만 재전송 특징 동작과정
송신측과 수신측은 동일한 크기의 Sliding-window를 보유 수신측은 프레임의 순서에 상관없이 수신 각각의 프레임에 대한 수신확인을 수행 동작과정 오류가 검출된 4번 프레임에 대해서만 재전송 수행

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

10 전진오류 정정(Forward Error Correction)
수신측에서 오류를 정정 ARQ와 FEC 재전송 요청하는 방법(ARQ) 구현이 단순 재전송으로 인한 대역폭을 요구 오류 정정 코드를 삽입, 수신측에서 직접 정정하는 방법(FEC) 구현 복잡 FEC를 위한 별도의 코드 삽입으로 전송 시 대역폭을 요구 오류정정 코드는 오류 검출 코드보다 훨씬 복잡하고 많은 패리티비트를 요구 단일비트 오류 정정, 해밍코드, 상승코드

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

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

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

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

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

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

17 예 구성 쉬프트 레지스터 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=( )

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

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

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

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

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

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

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

25 ARQ나 FEC 어느 것이나 이용될 수 있는 응용

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

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

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

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

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

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

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

33 동작과정 최대 윈도우 크기 : 7(0~7) 빗금 친 부분
송신측 : 전송 가능 범위 수신측 : 수신 가능 범위 처음에 시스템 A와 B는 프레임 0(F0으로 표현)에서 시작, 7개 프레임을 송신할 수 있는 윈도우를 가짐 시스템 A는 프레임(F0,F1,F2)을 전송 윈도우 4개로 줄어듬 시스템 B는 그러고 나서 ACK3(포괄적 수신확인)을 전송 시스템 A는 프레임 3, 4, 5, 6의 전송을 진행 ACK4를 시스템 A에게 전송 그러면 시스템A는 하나의 응답만을 받았으므로 윈도우를 하나 늘려 7번 프레임부터 2번 프레임까지 4개의 프레임을 전송할 수 있음

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

35 레포트 “12장 무선 통신과 무선통신의 기술” 내용 요약 A4지에 손글씨로 작성하여 6월 13일 제출