[정보통신공학] 7. Data link control protocols

• Data link control protocol requirements
  - frame synchronization
  - flow control
  - error control
  - addressing
  - control and data on same link: receiver가 어떤 데이터를 받았을 때, 데이터와 control information 둘 사이를 구분하는 것이 가능해야 함
  - link management: link initialization, maintenance, termination

Flow Control

: receiver가 받을 수 있는 만큼만 sender가 데이터를 보내도록 보장하는 기술 => buffer overflow 방지

• transmission time: 매체로 frame의 모든 bit을 내보내는 데 걸리는 시간 => $t_{frame}$
• propagation time: 송신자와 목적지 사이에 한 bit가 link를 traverse하는 데 걸리는 시간 => $t_{prop}$

모든 frame은 frame lost나 error 없이 받는다고 가정한다

Stop-and-Wait

1. source entity transmits a frame
2. destination receives the frame and replies with acknowledgement (ACK)
3. source waits for ACK before sending next frame
4. destination can stop flow by withholding ACK
5. works well for a message sent in a few large frames

• Link Utilization (efficiency)
  U = 1 / (1+2a) where a = $t_{prop}$ / $t_{frame}$

• fragmentation: large block of data -> smaller frames
  - receiver's limited buffer size
  - transmission 길어지면 ⬆, error ⬆ -> retransmission of entire long frame
  - errors detected sooner -> retransmission of smaller frames
  - 독점 방지

=> multiple frames for a single message. bit length of link > frame length (a > 1) => stop-and-wait 비효율적

Sliding-Window

1. receiver allocates buffers for W frames
   • w: window size. receiver 입장에서 ACK을 보내지 않고 내 buffer에 보관할 수 있는 frame의 최대 개수
2. transmitter can send up to W frames without ACK
   • w: transmitter 입장에서 상대방으로부터 ACK을 받지 않고 전송할 수 있는 frame의 최대 개수
3. each frame is labeled with a sequence number
4. ACK includes # of next frame expected
   ex) 2 3 4 -> <- RR5 (received ready 5)
5. sequence number is bounded by size of field (k)
   • frames are numbered modulo $2^k$
   • maximum window size: $2^k - 1$

• Link Utilization
  U = 1 (w >= 2a+1) or w/2a+1 (w < 2a+1)

• Receive Not Ready (RNR)
  - receiver can acknowledge frames w/p permitting further transmission
  - must send a normal ACK to resume
• Piggybacking: # seq field + ACK 포함
  - If data & ACT to send => send them together
  - If data but !ACK to send => send the last sequence num again
  - If ACK but !data to send => use ACK frame

Error Control

: mechanism to detect and correct errors
lost frame / damaged frame

• Automatic Repeat Requrest (ARQ)
  : collective name for error control mechanisms
  => turn an unrealible data link into a reliable one
  - error detection
  - positive ACK: 오류X
  - retransmission after timeout
  - negative ACK and retransmission: 오류 발생

Stop-and-Wait

based on stop-and-wait flow control
1. source transmits a single frame and wait for ACK
2. if received frame is damaged, discard it
- transmitter's timer expires
- if no ACK within timeout, retransmit the frame
3. if ACK is damaged, transmitter will not recognize it => lost
- transmitter will retransmit
- receiver gets two copies of the frame
- solution: alternatively label frames with 0 and 1 (ACK1 and ACK0)

simple & inefficient mechanism

Go-Back-N

based on sliding-window flow control
1. use window to control number of outstanding(미해결) frames
2. if no error => ACK with next frame number expected
3. if error => reply with rejection (REJ)
- receiver discard that frame and all future frames until error frame received correctly. 거절당한 프레임 이후 모두 제거
- transmitter must retransmit that frame in error and all subsequent frames

• maximum window size: $2^k - 1$

Selective-Reject

Only rejected (SREJ) or time-out framres are retransmitted
subsequent frames are accepted and buffered by the receiver
(+) minimize the amount of retransmission
(-) receiver must maintain large buffer space, more complex logic in transmitter and receiver
useful for satellite links with long propagation delays

• maximum window size: 2^(k-1)

HDLC

• High-Level Data Link Control: ISO 3009, ISO 4355. Non-LAN은 HDLC 기반.

Station Types

• Primary Station
  - responsible for controlling operation of link
  - commands: frames issued
  - secondary station과 separate logical link 유지
• Secondary Station
  - primary station의 control 하에 작동
  - responses: frames issued
• Combined Station
  - primary와 secondary의 특징 조합
  - commands, responses 모두 issue
  

Link Configurations

• Unbalanced
  - primary == 1, secondary >= 1
  - full-duplex, half-duplex 모두 지원
• Balanced
  - two combined stations
  - full-duplex, half-duplex 모두 지원

Transfer Modes

• Normal Responsed Mode (NRM)
  - unbalanced configuration
  - primary: initiates data transfer to a secondary
  - secondary: only transmit data in reponse to command from primary (primary에 대한 응답으로만 데이터 전송 가능)
  - multidrop lines: host computer (primary) polls each terminal (secondary) for input
  - point-to-point links: terminal이나 other peripheral을 컴퓨터에 연결
  

• Asynchronous Balanced Mode (ABM)
  - balanced configuration
  - either combined station: transmission 가능. 다른 station 허락 필요 X
  - most widely used
  - polling overhead X: efficient use of full-duplex point-to-point link

• Asynchronous Response Mode (ARM)
  - unbalanced configuration
  - secondary: initiate transmission w/o primary 허락
  - primary: responsible for line
  - rarely used

Frame Structure

Synchronous Transmission (bit-oriented)
all transmissions in frames
single frame format for all data and control exchanges

• Flag Fields: delimit frame at both ends with 01111110
  - 한 frame의 closing flag, next frame의 opening flag로 사용 가능
  - receiver: hunts for flag sequence to synchronize
  - Bit Stuffing: 01111110을 포함하는 data와의 confusion 방지

  Bit Stuffing

  • transmitter: 5개의 1이 나온 뒤에 0을 삽입
  • receiver: 5개의 1 감지 시, next bit check
    - 0: delete
    - 1 & 7th bit가 0: flag
    - 6th & 7th bit가 모두 1: abort condition (폐기)
    

• Address Field
  - identifies secondary station that sent or will receive frame
  - 주로 8bits long
  - multiple of 7 bits extend 가능
  : leftmost bit of each octet: last octet(1), not last bit(0)
  - all 1s (11111111): broadcast

• Control Field: frame type에 따라 differ (처음 1~2 bit가 frame 결정)
  - Information frame (I-frame)
  : user에게 전송할 data carry
  : flow, error control: piggybacked on I-frame
  - Supervisory frame (S-frame)
  : provide ARQ mechanism when piggybacking is not used
  (보낼 data X. ACK 보낼 때)
  - Unnumbered frame (U-frame)
  : provide supplemental link control functions

• Poll / Final Bit: 모든 control field는 P/F bit 가지고 있음. context에 따라 사용
  - command frame: P bit
  1로 설정. solicit (poll) response from peer HDLC entity
  - reponse frmae: S bit
  1로 설정. indicate response frame for soliciting command
  

• Information field
  - I-frame과 몇몇의 U-frame에만 있음. (S-frame: 사용자 data 보내지 X)
  - must contain integral number of octets
  - variable length up to system-defined maximum (system마다 다름)

• Frame Check Sequence field
  - error-detecting code
  - calculated from remaining bits of frame (flag 제외 나머지 bits)
  - 16-bit CRC-CCITT
  - Optional 32-bit CRC-32

Operation

: 두 개의 station 간의 I, S, U frame 교환 작업

1. Initialization

• either side에서 requested. issuing one of six set-mode commands
  - initialization 요청된 side에게 signal 보냄
  - specify requested mode (NRM, ABM, ARM)
  - specify whether 3- or 7- bit sequence number used
• Accept: unnumbered acknowledgement (UA) frame => U frame
• Reject: disconnected mode (DM) frame => U frame

2. Data transfer

• initialization is requested and accepted => logical conection is established
• both sides에서 I-frame에 data 전송 가능. seq number는 0으로 시작
• N(S), N(R) fields: flow and error control
• S-frames: flow and error control (RR, RNR, REJ, SREJ)

3. Disconnect

• either module이 disconnect initiate 가능
  - on own initiative if there is some fault
  - at the request of its higher-layer user
• issue disconnect (DISC) frame => U frame
• accept the disconnect by (2계층)
  - replying with UA
  - informing its layer 3 user the termination
• any outstanding unacknowledged I-frames may be lost (2계층) and their recovery is reponsibility of higher layer(recovery)
  => protocol 작동 원리. 3(IP) 주로 해결 X. 4(TCP)가 거의 해결