Chapter 5 링크 계층

링크 계층 데이터 링크 제어에서 전달하는 데이터의 단위를 프레임(frame)이라고 부른다. 목적 이외에, 전송되는 프레임의 시작과 끝을 어떻게 구별할 것인가? 이외에, 전송되는 프레임에 에러가 발생했는가? 송수신 장치간에 속도 차에 의한 프레임의 손실이 발생할 수 있는가? (흐름 제어)

물리 계층과 링크 계층

프레임의 경계 구별 프레임의 시작과 끝을 특별한 문자(혹은 비트 패턴)를 사용하여 구별한다. Character-oriented Bit-oriented

Byte stuffing 만약 프레임 내에 flag byte와 동일한 byte의 데이터가 존재한다면,

Bit stuffing 만약 프레임 내에 flag 비트 패턴과 동일한 비트 패턴의 데이터가 존재한다면,

흐름 제어(flow control) 흐름 제어는 수신 장치가 송신 장치가 보내는 데이터의 양을 조절하도록 하는 절차이다. 흐름 제어의 방법 Stop-and-wait flow control Sliding window flow control

Stop-and-Wait Flow control 송신 장치는 보낸 프레임에 대한 ACK이 오기 전까지 송신을 중단하고, ACK이 도착하면 다음 프레임을 전송한다.

만약 프레임이 손실되었다면,

Sliding window flow control 송신 장치는 ACKf를 받지 않더라도 계속해서 프레임을 전송한다. 하지만 현재 연속해서 보낼 수 있는 가능한 프레임의 수를 계속 모니터링한다. 송신 장치의 window 현재 순간에 ACK를 받지 않더라도 보낼 수 있는 프레임의 수 이것은 결국 현재 수신 장치의 buffer에 비어있는 공간을 크기이다.

송신측 window

예11.6(최대 윈도우 크기=7)

예11.7(재전송 발생)

Error Detection and Correction

오류 제어(error control) 오류 검출(error detection) 오류 정정(error correction) 블록 코드 단순 패리티 코드(parity code) 순환 중복 확인(Cyclic Redundancy Check) 검사합(checksum) 오류 정정(error correction) 전향 오류 정정(forward error correction) 재전송(retransmission)

에러 종류: single bit error

에러 종류: burst error

에러 검출/정정 코드 에러 검출 혹은 정정을 위해서 여분의 비트들(redundancy)을 데이터에 덧붙여서 전송한다.

에러 검출 코드 패러티 비트(parity bit) 순환 중복 확인(Cyclic Redundancy Check) 검사합(checksum)

Even parity bit 비트 1의 수가 짝수(even)가 되도록 데이터 비트에 패리티 비트를 추가한다.

2-dimensional parity

순환 중복 확인(CRC) 가장 널리 사용되는 에러 검출 방법 하드웨어로 쉽게 구현할 수 있다.

에러검출 코드 생성(CRC encoder) 데이터워드: k 비트 Divisor 혹은 generator: m 비트 에러 검출 코드: m-1 비트 데이터워드를 생성기로 (모듈로-2) 나누어서 구한다. 코드워드: n = k + (m-1) 비트 데이터워드에 에러 검출 코드를 덧붙인다. 송신장치는 코드워드를 전송한다.

CRC encoder and decoder

CRC encoder 예 Dataword: 1001 Divisor : 1011 Error detection code: 110 Codeword: 1001110

에러 검출(CRC decoder) 수신한 Codeword를 divisor로 나눈다. 만약 나머지가 0이면 에러가 없거나 에러 발견 실패 만약 나머지가 0이 아니면 에러 발생

CRC decoder 예 에러 발생

CRC 다항식 divisor(혹은 generator)는 다항식으로 표현하기도 한다.

표준 CRC 다항식

CRC는 얼마나 잘 에러를 검출한는가? Divisor가 어떤 것인가에 따라 다르다. 좋은 divisor는 그렇다면, 두 개 이상의 항으로 되어 있어야 한다. X0항의 계수는 1이어야 한다. 0부터 n-1 사이의 t값에 대해서 xt+1을 나누어 떨어지지 않도록 해야 한다. X+1을 인자로 갖고 있어야 한다. 그렇다면, 단일 비트, 두 비트, 홀수개의 비트 에러, 그리고 대부분의 burst error를 검출할 수 있다.

검사합(checksum) CRC가 하드웨어로 구현하기 편리한 반면에 소프트웨어로 구현해야 하는 경우 checksum을 사용한다. 인터넷의 IP와 TCP에서 사용

1의 보수 연산으로 checksum 계산

송신 1. 데이터(프레임)를 16 비트 길이의 워드로 나눈다. 2. Checksum 워드의 자리에는 0을 대입한다. 4. 합한 결과를 1의 보수로 만든다. 5. 이것을 checksum 워드 자리에 대입하여 데이터를 전송한다.

수신 1. 수신한 데이터(프레임)를 16 비트 길이의 워드로 나눈다. 2. Checksum을 포함한 모든 워드들을 1의 보수 연산으로 더한다. 3. 합한 결과를 1의 보수로 만든다. 4. 이 값이 0이면 에러가 없는 것이고 0이 아니면 에러가 발생한 것이다.

예제 10.23 F F F F

에러 제어 에러 제어 에러 검출 에러 정정 CRC Checksum Forward error correction 재전송(retransmission, ARQ) Stop-and-Wait ARQ Go-Back-N ARQ Selective Repeat ARQ

Go-Back-N ARQ . Go-Back-N ARQ는 window가 허락하는 범위에서 프레임을 연속해서 전송한다. I(2)I(3) timeout Retransmit all frames from I(4) from I(7) Error on ACK(8) NAK(4) ACK(8) on I(4) ACK(1) . Go-Back-N ARQ는 window가 허락하는 범위에서 프레임을 연속해서 전송한다. 그런데 프레임 전송에 에러가 발생하면 재전송을 해야 하는데…

Selective Repeat ARQ I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) ACK(1) timeout Retransmit only I(4) only I(1) Error on ACK(2) NAK(4) ACK(2) on I(4) . 현재의 window 크기의 범위 내에서 프레임을 계속 전송하는 것은 같지만 만약 에러가 발생해서 재전송을 해야 할 때 차이가 있다.

예11.8: Selective Repeat ARQ와 window

Piggybacking ACK 프레임을 별도로 전송하지 않고 데이터 프레임을 전송하면서 ACK를 같이 한다.

링크 계층 프로토콜 HDLC PPP

HDLC ISO 표준 point to point와 multipoint 링크 상에서 half-duplex와 full-duplex 통신을 제공한다.

Point-to-Point Protocol(PPP) Cf: Ethernet HDLC 프로토콜에 기반을 두고 HDLC 프레임에 여러 종류의 PPP 패킷을 전송한다. Byte-oriented protocol

PPP 프레임 포맷

상태 전이도

PPP 패킷의 전송