Data Link Control Protocols

직접 연결된 송신-수신 스테이션 간 효과적인 데이터 통신을 위한 Requirments와 objectives

• Frame synchronization
• Flow control
• Error control
• Addressing
• Control and data
• Link management

---

Flow Control

송신 측(transmitting entity)이 수신 측(receiving entity)에 과도한 데이터를 보내지 않도록 함
수신 측은 보통 데이터를 전송받기 위해 최대 길이를 가진 데이터 버퍼(buffer)를 할당
데이터가 수신되면, 수신 측은 데이터를 상위 계층 소프트웨어로 넘기기 전에 특정 processing 수행
만약 flow control이 없다면, 수신 측이 이전 데이터를 처리하고 있는 동안 버퍼가 가득 차서 넘쳐버릴 수 있음 → buffer overflow

---

Stop-and-Wait Flow Control

 가장 단순한 형태의 flow control
1. Source는 프레임 하나 전송
2. Destination은 프레임 수신 후 acknowledgement(ACK)을 보냄
3. Source는 다음 프레임 전송 전에 ACK을 기다림
4. Dectination은 ACK을 보내지 않음으로써 flow을 멈출 수 있음

메시지가 소수의 큰 프레임으로 전송되는 경우 적절하지만,
일반적으로 송신 측이 큰 데이터를 여러 개의 작은 블록으로 나누어 여러 개의 프레임으로 전송
→ inefficient

# ACK: 아주 작은 데이터 패킷(링크 사용 시간 적음)

---

Sliding Windows Flow Control

여러 개의 번호가 매겨진 프레임을 동시에 전송하는 것을 허용
수신자의 버퍼 크기: W 개의 프레임
송신자는 ACK 없이 최대 W 개의 프레임까지 전송 가능
ACK은 다음에 오길 기대하는 프레임 번호 포함
Sequence number는 필드의 크기(k: frame bits)에 따라 제한
프레임은 2^k로 modulo 연산하여 번호가 부여됨
최대 window size는 2^k - 1
수신자는 추가 전송은 허용하지 않으면서도 프레임은 ACK할 수 있음
→ RNR(Receive Not Ready)
전송을 재개하기 위해선 정상적인 ACK을 보내야 됨

 

위 예시에선 3비트 시퀀스 번호 사용
따라서 프레임 번호는 0부터 7까지 순차적으로 할당, 이후엔 다시 0부터 반복
그림의 음영 처리된 사각형은 현재 전송 가능한 프레임들을 나타냄
프레임을 하나 보낼 때마다, 음영 처리된 윈도우는 줄어들고(shrink),
ACK을 하나 받을 때마다, 다시 윈도우는 확장됨
수직 막대와 음영 창 사이에 있는 프레임들은 전송은 되었지만 아직 ACK을 받지 못한 상태
이러한 프레임들은 재전송될 수 있으므로 송신자가 버퍼에 보관
# 시퀀스 번호의 길이로 가능한 최대 윈도우 크기를 꼭 사용해야 되는 것은 X
# 최대 윈도우 크기는 7이지만, 5로 설정도 가능
 

3비트 시퀀스 번호 필드, 최대 윈도우 크기 7의 프레임 가정
A가 ACK 없이 3개의 프레임(F0, F1, F2)을 전송하면,
A는 윈도우를 줄여서 4개의 프레임만 더 보낼 수 있고,
이미 전송한 3개의 프레임은 복사본을 유지(재전송 대비)
A의 윈도우는 이제 프레임 3부터 4개까지만 전송 가능하다고 표시
B는 RR3(Receive Ready 3)을 보냄
ACK을 받은 A는 다시 프레임 3부터 7개까지 전송 가능
프레임 0, 1, 2를 메모리에서 지움
이후 A는 F3, F4, F5, F6 전송 / B는 RR4를 보냄
RR4가 A에 도착했을 시점엔 A는 이미 F4, F5, F6까지 전송했으므로,
A는 윈도우를 다시 F7부터 시작하여 4개까지만 전송 가능하도록 엶
# 순서 안 맞으면 Error

---

Error Control 기법

• Error detection
• Positive acknowledgement
• Negative acknowledgement and retransmission
• Retransmission after timeout

 
Lost frames
: 프레임이 수신 측에 도달하지 못한 경우
Damaged frames
: 프레임은 도착했지만 일부 비트에 오류가 있는 경우

---

Automatic Repeat Request(ARQ) ⭐

오류 제어 메커니즘의 총칭적인(collective) 이름
ARQ의 효과: 신뢰할 수 없는 데이터 링크를 신뢰할 수 있는 링크로 변환
ARQ의 버전

• Stop-and-wait
• Go-back-N
• Selective-reject

 
Stop-and-wait(ARQ)
1. Source는 single frame 전송
2. ACK을 기다림: Destination의 응답이 올 때까지
3. 프레임이 손상되면, 수신자는 이를 폐기(discard)
: 송신자는 timeout을 설정해두고, 그 시간 내에 ACK을 받지 못하면 재전송
4. ACK이 손상되면 송신자는 이를 알아차리지 못함
: 송신자는 재전송을 수행, 수신자는 프레임을 두 번 받게 됨(two copies)
이를 위해 ACK0/ACK1 같은 교대 비트(alternate numbering)를 사용

 
Go-Back-N(ARQ)
가장 일반적으로 사용되는 오류 제어 방식
슬라이딩 윈도우 방식에 기반
window size에 의해 아직 ACK을 받지 않은 전송된 프레임의 개수 결정됨
1. 오류가 발생하지 않는 동안에는 수신 측이 수신된 프레임에 대해 정상적으로 ACK함 
→ RR(Receive Ready) or piggybacked ACK
2. 수신 측이 오류를 감지하면 negative acknowledgement(NAK)을 전송할 수 있음
→ REJ: reject
수신 측은 해당 오류 프레임과 그 이후의 모든 프레임을 폐기(discard), 오류가 있었던 프레임이 제대로 다시 도착할 때까지 대기
송신 측이 REJ를 수신하면, 오류가 있었던 프레임뿐 아니라 그 사이에 전송된 모든 후속 프레임들도 다시 함께 전송

 
Selective-Reject(ARQ) (= selective retransmission)
negative acknowledgement(SREJ)을 받은 프레임이나 타임아웃된 프레임만 재전송됨
즉, go-back-n과 달리 거부된 프레임만 재전송
거부된 프레임의 이후(subsequent) 프레임은 수신 측이 받은 후 버퍼에 저장
재전송 양을 최소화
수신 측은 충분히 큰 버퍼를 유지
송신 측의 로직이 더 복잡: 그래서 잘 사용되지 X
propagation delay가 긴 위성 링크에 유용

---

Synchronous Transmission

동기식 전송에서는 한 번에 하나의 데이터 그룹을 블록 형태로 전송
→ 이를 frame 또는 packet이라 부름
각 패킷의 시작(start)과 끝(end)에 synchronization character(SYN, 동기화 문자)을 붙임

---

High-level Data Link Control(HDLC) ⭐

OSI 모델의 data link 프로토콜
가장 중요한 data link control 프로토콜
비트 지향 프로토콜(bit-oriented protocol)
전송 측에서는 HDLC가 application 계층에서 데이터를 받아 반대편 수신자에게 전달
수신 측에서는 HDLC가 데이터를 받아 application 계층으로 전달(higher level로)
양쪽 모듈은 frame으로 인코딩된 control information을 주고 받음 
 
HDLC는 3가지 유형의 stations, 2가지 링크 구성, 3가지 데이터 전송 모드로 구성
3 Stations

• Primary station: 링크의 동작을 제어(frames: commands)(능동적)
• Secondary station: Primary의 제어를 받음(frames: responses)
• Combined station: commands와 responses 모두 처리

 
2 Link Configurations

• Unbalanced: 한 쪽이 primary, 다른 쪽이 secondary(1 primary, multiple secondary)
• Balanced: 양쪽이 Combined station(2 combined stations)(상호 동등)

 
3 Data Transfer Modes

• NRM(Normal Response Mode)

- Unbalanced configuration에서 사용
- Primary station이 전송 시작(initiate)

• ABM(Asynchronous Balanced Mode)

- balanced configuration에서 사용
- 양쪽 스테이션이 전송 시작 가능
- Polling overhead 없음
- 가장 널리 사용됨

• ARM(Asynchronous Response Mode)

- unbalanced configuration에서 사용
- Secondary station이 primary의 permission 없이 전송 가능
- 거의 사용되지 않음

---

HDLC는 동기식(synchronous)

# flag, address, control을 통칭하여 헤더라 함
Flag: 프레임 양쪽 끝을 고유한 패턴 01111110으로 구분, 이는 프레임의 시작과 끝을 나타냄
문제: 만약 01111110 패턴이 프레임 내부(information 등)에 등장하면, 동기화가 깨짐 
해결책: bit stuffing

---

Bit Stuffing
start flag와 end flag 사이의 모든 비트에 대해,
송신자는 1이 5번 연속 나오면, 그 뒤에 0비트를 추가로 삽입

1이 5번 연속 등장했을 때의 경우 처리

• 6번째 비트가 0 → 삭제(수신 측에서, 삽입된 것이므로)
• 6번째 비트가 1 → 7번째 비트가 0이면 flag로 간주
• 6번째와 7번째 비트가 모두 1 → abortion(중단, 비정상)로 간주 = error 

---

Address Field
주소 필드는 데이터를 전송했거나 받을 secondary station 식별
보통 8비트 길이
필요하면 7비트 단위로 확장 가능
: 이때 맨 왼쪽 비트는 현재 octet이 마지막인지(1), 아닌지(0)를 나타냄
주소가 11111111이면 primary가 모든 secondary에 프레임을 broadcast

---

Control field
HDLC는 세 가지 프레임 유형, 각 프레임 유형마다 control field format이 다름

• Information frames(I-frames)

: user에게 전송될 데이터
ARQ를 이용한 flow, error control data 포함 가능(I-frame에 piggyback되어)

• Supervisory frames(S-frames)

- no information
- piggyback이 사용되지 않을 때 ARQ 메커니즘 제공
- 00: RR, 01: REJ, 10: RNR, 11: SREJ

• Unnumbered frames(U-frames)

: 추가적인 링크 제어 기능 제공, M1, M2 등 32가지 이상의 기능 지원

P/F(Poll/Final) 비트의 사용은 상황에 따라 달라짐
command frames: P비트를 1로 설정 → 상대 HDLC 장치로부터 응답을 요청(poll)
response frames: F비트를 1로 설정 → 요청된 명령에 대한 응답 프레임임을 나타냄

---

Information Field
오직 I-frame과 일부 U-frame에만 존재
반드시 정수 개의 octet을 포함
가변 길이(variable length)
 
FCS(Frame Check Sequence) Field
프레임 나머지 비트들로부터 계산된 오류 검출 코드(flag 제외)
일반적으로 16비트 CRC-CCITT 코드 사용
기본은 16비트 CRC이지만, 더 높은 정확도가 필요하면 32비트 CRC-32 사용