Chapter 6. Error Detection and Correction

"For two devices linked by a transmission medium to exchange data, a high degree of cooperation is required"

 

1. Timing: Error detection/correction을 위해 비트 읽기

- Asynchronous serial transmission

- Synchronous serial transmission

* parallel transmission: 각 channel이 따로따로 동시에 보냄

* serial transmission: 한 channel에서 한 비트씩 순서대로(one bit after another bit over a single channel)

 

2. Error Detection(TCP, UDP, Ethernet, Wifi)

- Parity check: L1

- Internet checksum: L3,4

- Cyclic redundancy check(CRC): L2

 

3. Error Correction(TCP)

- Backward Error Correction(BEC): Error 고쳐서 다시 돌려줌

- Forward Error Correction(FEC): Error 고치면서 그냥 앞으로 나아감

---

Timing

 

TX와 RX 간 clock sync, 즉, bit interval이 맞지 않아서 생기는 오류

 

*** 1s = 10^6μs ***(꼭 외워놔야 함)

 

TX와 RX는 같은 NIC card를 쓰기 때문에 통신 규약이 같음 하지만..

TX의 bit interval > RX의 bit interval

=> TX의 의도보다 RX가 더 많이 읽게 됨

 

 

 

Transmission between transmitter(TX) & receiver(RX)

 

: TX와 RX가 제대로 소통하기 위해서는..

timing이 서로 맞아야 함

= clock sync가 같아야 함

="bit arrival time"과 "bit duration"이 같다

= Rate, Duration, Spacing이 같다

= TX가 보낸 의도대로 RX가 이해하고 받아들인다

단, TX와 RX의 절대시간이 맞는다는 뜻은 아니다.

 

<TX와 RX의 clock를 synchronize하는 방법>

: RX의 bit interval이 생각보다 느리거나 빠를 수 있음 -> 중간에 맞춰줘야 하는데 얼마나 자주 하는지.

- Asynchronous

- Synchronous

 

1. Asynchronous

: 처음에 한 번 맞추고 다음에는 안 맞추다가 어쩌다 한 번 맞추기

: TX가 frame에 clock 정보 1 char씩 넣어서 RX에게 보냄 -> 조금씩 보내므로 계속 synchronize되는 게 아님.

- synchronization에 대한 정보

: 0(start bit)/1(stop bit) -> 제대로 읽을 수 있을지에 대한 정보

ex. start bit = 0 => 0이 오면 시작한다는 의미로 받아들여짐

 

- TX와 RX가 같은 NIC card 사용

-> data bit 수와 순서, stop bit의 길이, parity bit 존재 여부, parity가 odd인지 even인지, bit interval(transmission speed)에 관한 정보 같음

ex.

TX와 RX가 사전에 7bit 쓰기로 합의(통신규약 통일)

-> clock 맞추기 위해 stop bit 넣음(start bit는 당연히 1bit)

-> parity bit 넣음(error detection을 위해)

 

- 한 번에 한 character(frame)만 보낼 수 있음

* 시작: start bit => 잘못되면 framing error

* character bit = 5~8bits씩 끊어서 보냄 => error 줄임

* 끝에 parity bit

* 맨 마지막: stop bit

 

ex.

=> error detection을 위한 overhead = 1bit(parity bit) => 1/9

=> clock sync를 위한 overhead = 2bit(start bit & stop bit) => 2/9 ~=20%

=> efficiency = 7/9~=80%

** more data -> (+)higher efficiency, 하지만 (-)higher time drift(밀려서 읽는 오류)

** less data -> (-)lower efficiency, 하지만 (+)lower time drift

 

 

<예제>

 

한 character

 

==> 한 character 보내고 다시 돌아오면 timer 리셋되기 때문에 그나마 오류 줄일 수 있음

"Receiver has a new opportunity to resynchronizes at the beginning of each character"

 

(+) 간단하고 비용 낮음

(+) 큰 gap을 가진 데이터에 적합

(-) overhead 큼(1 char당 2~3 bits)

(-) bit 수 많으면 timing error 증가

 

2. Synchronous: TX가 "지금 읽어!"하고 보내면 RX가 읽음 -> RX의 bit interval과 상관 없음

 

(방법 1)

clock signal 정보를 담은 channel을 따로 둠 -> 가면서 계속 맞춤

(-) 짧은 거리면 괜찮지만, 멀리 가면 clock 정보 망가짐

 

(방법 2) 

TX가 RX에게 주는 실제 데이터: 10100100
RX에게 전달되는 데이터: 0110011010011010

 

=> RX가 받는 데이터로부터 실제 데이터를 얻기 위해 encoding (0110011010011010 -> 10100100)

* Encoding: correctly recognizing every bit in a bit stream between TX & RX(각 데이터를 정확하게 읽기)

 

 

전압에 변화가 있을 때 읽으라고 알려줌

- 0->1(상향) => "1"로 읽음

- 1->0(하향) => "0"으로 읽음

 

<예: L2에서의 Framing>

: bit 패턴을 이용해 packet 경계를 인식하여 frame 단위(PDU)로 조각내는 것

"PDU = header + payload"라고 말했었다.

 

HDLC(L2 프로토콜)의 PDU를 예로 들어보자.

 

sender은 처음과 끝에 01111110을 넣어 PDU의 시작과 끝을 알린다.

receiver은 그 8bit를 보고 시작과 끝임을 알아차리고 PDU를 인식할 수 있는 것이다.

 

Ethernet을 예로 들어보자.

시작 비트를 뺴고, control field 대신 size를 넣는다.

* Manchester Encoding: Ethernet이 사용하는 인코딩 방법

"Ethernet이 상위계층에 xMbps를 원하는데 channel bandwidth가 최소 xMbps가 있으면 충분하다" (x)

-> clock sync를 맞추기 위한 encoding bit를 생각하지 않음 

(clock sync 맞추는 overhead는 포함되지 않으므로 encoding bit 따로 넣어줘야 함..)

 

 

<특징: Efficiency>

: data block은 start/stop bit 없이, 쪼개지지 않고 한 번에 쭉 보내짐 <-> asynchronous

ex. HDLC(bit oriented), LAN(character oriented)

- error detection 기능 향상

: control field에 CRC라는 향상된 error detection code를 넣음

- 큰 data block에 대해서는 lower overhead

ex. HDLC

: 8bit씩으로 이루어진 1000개의 data block

-> payload에 한 번에 8000bit 넣되 clock sync 정보는 아래 계층에서 맞출 것이므로 넣지 않음

-> control field는 48bit 

* overhead: 48bits/(8000+48)bits = 0.6%

* efficiency: 8000bits/(8000+48)bits = 99.4%

 

cf) Asynchronous에서는 bit를 쪼개서 보내므로,,

8000bit를 보내기 위해서는 8bit씩 1000번 보내야 했음

	Synchronous	Asynchronous
transmission 속도	빠름 * data frame 사이에 gap 없음	느림 * data frame 사이에 gap 존재
clock sync 정보(L2)	없음	start/stop bit 존재
overhead 양(L2)	low	high character 당 2~3bit
하드웨어의 비용(L1)	비쌈 * 공유할 수 있는 clock signal * transmission이 완료될 때까지 기다릴 memory 필요	쌈 * clock sharing 필요 없음 * buffer 필요 없음
복잡한 정도	복잡	단순
efficiency & reliability	high	low
사용되는 프로토콜	Ethernet, ATM	큰 gap을 가진(데이터가 드문드문 입력되는) 데이터에 적합 ex. keyboard