Lecture 3a.1 ~ 3a.5: Link Layer, Part A

3a-1 Overview of the Link Layer

 

Where we are in the Course

 

 

Scope of the Link Layer

 

In terms of layers...

- Network 계층에서 전달된 패킷에 Header와 Trailer를 붙인 Frame을 Physical 계층으로 전송

- Physical 계층 간에 데이터가 전달

- 수신측에서 Physical 계층에서 Link 계층으로 Frame이 전달되며, Header와 Trailer를 제거한 Packet을 Network 계층으로 전달

 

 

Typical Implementation of Layers

 

Topics

 

 

 

 

3a-2 Framing

 

Topic

 

Framing Methods

- 실제 환경에서는 Physical 계층과 Link 계층은 합쳐져 있다

 

 

Byte Count

Byte Count 방식의 단점을 찾아보아라

 

- 2번째 Frame의 7이 잘못 전달된 수라고 가정하면 돌이킬 수 없다

 

 

Byte Stuffing

- Byte Count 방식의 단점이었던 re-synchronize 문제를 해결

- 실제로 사용하는 방식

- 다만 Payload field에 escape 코드가 존재 시 이를 무시하는 방법이 필요하다

 

- Rules

       - Replace each FLAG in data with ESC FLAG

       - Replace each ESC in data with ESC ESC

 

 

Bit Stuffing

- Byte Stuffing 이전에 사용하던 방식

- 오버헤드는 많이 줄어들지만 연산이 매우 복잡하다

 

- 1이 5번 반복되면 다음 비트 이전에 0을 하나 삽입한다

 

 

 

Link Example: PPP over SONET

- 점대점 프로토콜 (Point-to-Point Protocol) : 네트워크 분야에서 두 통신 노드 간의 직접적인 연결을 위해 일반적으로 사용되는 데이터 링크 프로토콜

- SONET (Synchronous Digital Hierarchy) : 장거리 고속 네트워크 통신을 위해 광섬유를 이용한 동기 전송신호 계층의 구조를 정의하여 동기식 TDM 다중화기를 사용하는 동기식 광 전송 프로토콜

 

- SONET : bit stream

- PPP : framing

 

- HDLC 프레임과 마찬가지로 PPP 프레임의 양 끝에 flag를 두어 시작과 끝을 구분

- 데이터 링크 주소를 사용하지 않기 위해 address 필드는 '11111111'로 고정

- Control 필드는 '11000000'으로 고정되어 순서 번호를 포함하지 않으며 flow 및 error control 하지 않음을 뜻한다

- Protocol 필드는 Data 필드에 실린 사용자 데이터나 기타 정보

- Checksum 필드는 에러검사를 위해 사용

 

- PPP 프레임이 HDLC 프레임과 다른 것은 byte stuffing을 사용하여 플래그와 같은 '01111110'과 같은 문자가 데이터에 나타날 때마다 추가적으로 바이트를 더하여 수신자가 다음의 문자는 플래그가 아니라는 것을 알 수 있게 해준다는 점이다

 

 

 

 

 

3a-3 Error Coding Overview

 

Topic

- Physical layer를 통해 신호를 전달할 때는 노이즈가 발생할 수 밖에 없으므로 이를 해결하는 방법에 대해 알아보자

 

 

Problem - Noise may flip received bits

- 잘못 전달된 신호인지 모를 수도 있다

 

 

Approach - Add Redundancy (중복)

 

Motivating Example

- 단순히 같은 신호를 두번 보낸다

- 두 신호가 다르게 오면 오류가 발생한 것을 알 수는 있으나 이를 수정할 수는 없으며, 같은 위치에 동일한 오류가 두번 발생 시에는 이를 감지할 수도 없다

- 오버헤드가 2배인 것에 비해 효율이 매우 낮은 방식이다

 

 

Using Error Codes

- 송신 측에서는 높은 계층에서 받아온 data bits에 해당하는 check bits를 추가해 낮은 계층으로 전달한다

 

- 수신 측에서는 data bits에 해당하는 check bits를 만들어 전달받은 check bits와 비교한다

- 다만 전달받은 check bits가 잘못된 것일 수도 있다

 

 

Intuition for Error Codes

- D + R 비트로 구성된 신호가 갖게되는 경우의 수는 2^(D+R)이며, 정확하게 전달된 체크 비트는 하나이므로 correct codewords의 경우의 수는 2^D이다

- 따라서 전체 codewords에서 임의로 선택된 codeword가 correct codeword일 확률은 2^(-R)이므로 비교적 오버헤드가 낮다

 

 

Hamming Distance

- Distance = 같아지기 위해 flip 되어야 하는 bit 수

 

- Hamming Distance를 d + 1이라고 했을 때, 최대 d bit에 해당하는 에러는 검출 가능하다

- 위의 예시에서 2개의 비트가 flip된 6가지 경우는 감지 가능하며 3개의 비트가 모두 flip된 경우는 감지 불가능하다

 

- Hamming Distance를 2d + 1이라고 했을 떄, 최대 d bit에 해당하는 에러는 수정 가능하다

 

 

 

 

 

3a-4 Error Detection

 

Topic

 

 

Simple Error Detection - Parity Bit

- Data bit의 합이 3이고 이를 2로 나눈 나머지인 1이 parity bit가 된다

 

- 위의 방식은 1개의 에러는 감지되고 2개의 에러가 동시에 발생하면 감지되지 못하므로 distance는 2이다

- 따라서 감지할 수 있는 에러는 1개 비트이며, 수정은 할 수 없다

- 단점으로는 홀수개의 에러만 감지 가능하다는 것이다

 

 

Checksums

- 합산하는 방식인 것은 Parity와 동일하지만 1 bit가 아닌 N-bit words를 사용해서 좀 더 안전한 방식이다

 

 

Internet Checksum

- 1의 보수 : 단순히 모든 bit를 flip하면 음수가 나온다

- 2의 보수 : 1의 보수 + 1

 

- 송신측에서는 0000을 더하고 overflow된 carry 값은 다시 더해준 다음 이 값의 1의 보수값을 전송한다

- 수신측에서는 나머지 비트와 체크섬을 함께 더한 뒤 overflow된 carry 값은 다시 더해준 다음 이 값의 1의 보수값을 수신한다

 

 

 

Cyclic Redundancy Check (CRC)

- CRC 기법은 수학적 연산 과정은 복잡하나, 높은 오류 검출율과 간단한 H/W 구현 가능

- CRC-8 / -10 / -16 / -32 유형 존재

- 송신측에서는 CRC 값을 데이터에 붙인 코드워드를 전송하며, 수신측에서는 수신된 코드워드에서 CRC 값을 이용하여 에러 발견

- 송신부의 처리 과정

1. 임의의 CRC 발생 코드를 선정

2. CRC 발생코드의 최고차 차수만큼 원래 데이터의 뒤에 '0'을 붙인다

3. 확장데이터를 modulo-2 연산을 사용하여 CRC 발생코드로 나눈다

4. 나머지가 '0'이면 확장데이터를 그대로 전송한다

5. 나머지가 '0'이 아니면 원래 데이터에 나머지를 붙여 전송한다

 

- 수신부의 처리 과정

1. 수신장치는 수신된 코드를 동일한 CRC 발생코드로 나눈다

2. 나머지가 '0'이면 오류가 발생하지 않은 것이다

 

 

Error Detection in Practice

 

 

CRC 참고

25. 오류검출코드 (CRC : Cyclic redundancy check)

 

 

 

 

 

3a-5 Error Correction

 

Topic

 

Why Error Correction is Hard

- 체크 비트에서도 에러가 발생할 수 있어서 에러 수정은 어렵다

 

 

Intuition for Error Correcting Code

- Valid codeword 간 Hamming Distance는 3이다

- Error codeword는 가까운 valid codeword로 수정된다

 

 

Hamming Code

- n : 데이터 비트

- k : 체크 비트

- 2^k >= n + k + 1

- 첫번째 체크비트는 자기 자신의 비트 위치를 포함하여 한칸 단위로 포함

- 두번째 체크 비트는 두칸 단위

- 네번째 체크 비트는 네칸 단위

- 예제는 짝수 parity & big endian

에러 없는 경우

 

에러 있어서 수정되는 경우

 

Other Error Correction Codes

 

 

Other Codes - LDPC

 

LDPC 참고

LDPC

 

 

 

Detection vs Correction

- in burst of : 폭발적으로

 

 

Error Correction in Practice