[데이터통신] 9. Data Link Control Protocols

SUbbb·2021년 12월 10일

데이터통신

목록 보기

8/13

Data Link Control Protocols

DataLink layer에서는 Frame 단위를 송수신

두 송수신 stations간 아래의 요구사항이 지켜져야 한다
Frame Synchronization : 송신은 frame 단위로 이루어지고, 이에 대한 동기화가 필요하다.
Flow Control : 흐름 제어 (수신측에서 받을 수 있는 크기로 송신측이 전송(overflow 방지를 위함))
Error Control : detection + correction(재전송, forward error correction)
Addressing : 주소 부여 (고유한 주소가 필요), 논리적인 주소
Control and data
Link management

Flow Control

송신 개체가 수신 개체에 data를 과도하게 전송하지 않도록 보장하기 위함

수신 개체는 전송을 수신하기 위한 data buffer를 할당
data가 수신되면, 수신 개체는 일정량의 처리를 수행한 후 상위로 data를 전달해야 함

flow control이 없다면, 수신측의 buffer는 가득차고, old data를 처리하는 동안 overflow가 발생할 것이다.

(b)에서,
frame2는 수신측의 buffer가 가득 차서 수신이 불가하고
frame4는 송신 중 noise로 인해 Garble(왜곡)됨

Stop-and-Wait Flow Control

flow control의 가장 간단한 형태
수신측은 data를 정상적으로 수신한 경우 ACK(일종의 frame)을 전송
$\rarr$ 송신측은 수신측의 ACK를 수신한 경우에만 다음 frame을 전송

Stop-and-Wait Utilization

긴 data를 frame 단위로 나눠서 전송

transmission time: frame이 도착해서 끝까지 다 수신되는데까지 걸리는 시간
propagation time: frame이 송신측에서 수신측으로 도착하기까지 걸리는 시간 (거리에 의존)
이를 다르게 그려보면,

U=\frac{T_x}{2T_p+T_x} = \frac{1}{2\frac{T_p}{T_x}+1}=\frac{1}{2a+1} \,\,(a=\frac{T_p}{T_x})

위 식을 해석하면, $T_p$ 안에 얼마의 frame을 보내는가를 알아낼 수 있는데, $2a+1$ 시간동안 겨우 1개의 frame을 전송하므로, 낭비

Sliding windows Flow Control

stop-and-wait 방식에서 번호를 붙인 frame을 연속으로 보냄으로써 utilization을 높임

수신측이 $W$ 크기의 buffer를 가지고 있다고 가정,
송신측은 ACK없이 $W$ frames를 전송
수신측으로부터의 ACK은 송신측이 전송한 마지막 frame의 번호 + 1의 값을 담아서 전송
$\rarr$ n-1번까지 잘 받았고, 이제 n번 frame을 줘 = ACK(n)
frame의 sequence number는 field size k로 제한

frames는 modulo $2^k$
max window size는 $2^k$ -1

Example

Maximum window size = 7, Sequence # = 3bit

A의 window size는 수신측 buffer에 의존하여 증감
B에서 ACK 전송까지 마친 frame들을 buffer에서 지우고 상위로 전달

Error Control Techniques

Error detection
Positive acknowledgement: frame을 잘 수신함
Retransmission after timeout: 일정 시간 이후 재전송
Negative acknowledgement and retransmission: frame에 오류가 있음을 알리고, 재전송

Lost frames: buffer overflow 등으로 인해 frame이 수신되지 않음
Damaged frames: 수신한 frame에 bit error가 있음

Automatic Repeat Request (ARQ)

재전송을 요청

ARQ의 versions
IDLE RQ (1개씩만 전송)

Stop-and-wait

Continuous RQ (연속적으로 전송 $\rarr$ flow control이 필요)

Selective-repeat
Go-back-N

Stop and Wait ARQ

송신측이 single frame을 전송
ACK을 wait
수신측에서는 수신한 frame에 error가 있는 경우, discard!
- transmittier는 timer를 가지고 있어서, 일정 시간 내에 ACK이 오지 않는 경우 재전송!
ACK에 error가 있는 경우, transimitter는 인식하지 않음
- ACK이 송신측으로 오지 않았다면, 송신측은 재전송하고 수신측은 이미 받은 frame이기 때문에 저장하지 않고 ACK만 전송
- alternate numbering & ACK0, ACK1 사용

Go-Back-N ARQ

sliding-window 기반
window size로 ACK을 수신하지 못한 frames 제어
error가 없다면, 수신측은 수신한 frame에 대한 ACK 전송

RR = receive ready (ACK)

error를 감지했다면, negative ACK을 전송

REJ = reject, 이 frame부터 다시 보내줘
수신측은 error가 있는 frame이 정상적으로 다시 수신될 때까지 수신되는 모든 frames을 저장하지 않는다.
전송측은 해당 N번째 frame으로 돌아가 그 지점부터 모든 frame들을 재전송해야 한다.

piggybacking: 수신측이 ACK을 보내면서 보내고자하는 data를 함께 전송하는 것
서로 data 전송 시 사용

The limitation to Maximum Window Size

3-bit sequence number 가정 (frame #: 0 ~ 7)
송신측은 frame 0을 보내고 RR1(=frame0을 잘 받았고 1을 보내줘)를 수신
$\rarr$ 송신측은 이제 frame 1,2,3,4,5,6,7,0을 보내고 RR1(frame 0을 마지막으로 전송했기에)을 수신할 것

8개의 frame들이 잘 수신되었고, RR1 전송 (cumulative ack(individual ack의 반대))
8개의 frame들이 모두 정상수신되지 않았고, 수신측은 다시 RR1을 전송

위의 두 상황은 서로 다른 상황이지만, 송신측에서는 구별할 수 없음!

solution: windows의 최대 size를 $2^{bit\,sequence\,number}$ -1로 지정

Selective-Repeat ARQ

제대로 온 frame은 수신측이 buffering 수행
error가 발생한 frame에 대해서는 buffering을 수행하지 않고 재전송을 기다림
$\rarr$ 재전송이 이루어져 buffer에 채워지면 상위로 전달

재전송을 최소화
수신측은 매우 크고 충분한 buffer를 유지해야 함
긴 propagation delays를 가지는 위성 links에서 사용

Maximum Window Size for Selective Repeat ARQ

k-bit sequence number field에 대해 $2^{k-1}$ 의 window size

Dilemma

seq #'s: 0,1,2,3
window size = $2^2$ -1 = 3

(a)의 경우, 문제되지 않는다.
(b)의 경우, 송신측에서 송신한 frame에 대한 모든 ACK이 전송되지 않아 timeout으로 인해 이전 data frame 0에 대해 재전송을 수행하지만, 수신측에서는 새로운 data frame 0으로 인식하게 되는 문제 발생

따라서, $2^k$ -1 window size가 아닌 $2^{k-1}$ window size가 필요

High Level Data Link Control (HDLC)

Station types

Primary: link operation을 제어 (송수신 제어)
Secondary: primary station에 의해 제어
Combined: primary & secondary 모두 가능

Link configurations

Unbalanced: 1 primary, multiple secondary
Balanced: 2 combined stations

HDLC Data Transfer Modes

Normal Response Mode(NRM)

unbalanced configuration 사용
Primary가 전송 시작
- Point-to-Point의 경우는 주소가 사실은 필요하지 않다.
- Multipoint의 경우 frame을 받을 주소가 명시되어야 한다.

Asynchronous Balanced Mode(ABM)

balanced configuration 사용
각 station이 전송 시작 $\rarr$ Polling overhead가 없음
- polling: primary가 secondary한테 전송할 data가 있는지 물어보는 행위

Asynchronous Response Mode(ARM)

unbalanced configuration 사용
primary의 허가 없이 secondary가 전송

HDLC Frame Structure

Flag: Frame의 시작을 알리는 code (01111110) & 끝을 알림
Address: multipoint 시, 주소 명시를 위해 필요
Control (8 bit, 16 bit)
- I: Information : 실제 data 전송 의미
  - N(S): seq # send, N(R): seq # receive $\rarr$ piggybacking 용으로 사용
  - P/F: Poll/Final bit
- S: Supervisory : piggybacking을 사용하지 않는다 의미
- U: Unnumbered : link control functions 제공 의미
- 8 bit $\rarr$ 16 bit로 증가 시, seq # field가 증가
Information
- Frame의 시작을 알리는 flag와 동일한 bit sequence가 나타나면, 수신측에서의 정상적인 해석이 불가
- 따라서, 1이 연속으로 5개가 나타나면 그 뒤에 0을 추가해주는 bit insertion을 수행

Flag Fields

frame의 시작과 끝을 알리는 code: 01111110, B=0x7E

수신측은 동기화를 위해 flag sequence look up
Bit stuffing(insertion)
- 01111110을 포함하는 data를 없애기 위해 사용
- 송신측은 1이 연속으로 5번 나타나는 sequence에 0을 추가
- 수신측은 5번 연속으로 나타나는 1을 감지하고 그 다음 bit를 확인
  - 0인 경우, 감지하고 destuffing(0 삭제)
  - 1이고, 그 다음 bit가 0이면 flag로 인지
  - 1이고, 그 다음 bit도 1이면 error로 감지하고 abort

Bit inverted로 인한 두 가지의 error 가능성