[정보통신공학] CH 7 Data Link Control Protocols

 Flow Control

 

* send 하는 entity가 receive 하는 entity의 data를 넘지않게 보장하는 것 

 - buffer overflow 방지

  ① receiving entity는 data buffer 할당(Maximum Transfer Unit의 몇배)

  ② 데이터를 high level로 올리기 전에 receiver가 먼저 처리

  ③ flow control이 없으면 receive buffer는 넘침

 

* receive buffer가 넘치는데에 영향 미치는 것

 ① transmission time :  L bit짜리 frame transmit 하는데 걸리는 시간 ( framesize / data rate )

 ② propagation time :  nth bit가 출발해서 도착하는데 걸리는 시간 ( link length / prop Speed )

 

1. Stop-and-Wait Flow Control

 (1) 가장 간단한 flow control 형태

  ① TX가 frame 전송

  ② RX가 ACK를 TX에 보내면서 msg 받았다고 알려줌

  ③ TX는 다음 frame을 보내기 전에 ACK를 기다림

  ④ RX는 ACK를 보내지 않음으로써 flow를 멈출 수 있음

 + 따로 negative ACK(더이상 frame 보내지마라는 뜻)는 없음. 그냥 RX가 ACK를 보내지 않으면 TX가 더 frame을 보내지 않음.

 

 (2) 큰 framesize로 msg를 보내는 것이 효율적

  - frame size를 키움으로써 frame 수를 줄이면 ACK를 기다리는 시간이 줄어들어 효율이 올라감

 

1 cycle = Ttrans + 2Tprop 

(Ttrans: frame 출발해서 last bit가 출발하는 곳까지의 시간) 

(Tprop: ① last bit 출발 ~ 도착  ② ACK의 시간(작아서 Ttrans 무시))

 

* Link Utilization = T trans / 1 cycle

 

 (3) 왜 msg를 다수의 small block으로 쪼개서 보낼까?

  ① RX의 limited buffer size

  ② frame이 길면 error가 났을 때 어디서 난지 몰라서, 긴 frame을 처음부커 다시 보내야함. 하지만 이를 쪼개면 좀 더 세부적으로 에러의 위치를 확인 가능함.

  ③ 한 station이 오랫동안 medium을 차지하고 있는 것을 막음

 * 끊어보내든 한 번에 보내든 avg delay는 같지만, 한 번에 보내면 max delay가 너무 큼 ≫ 끊어보내는 게 좋다

 

2. Sliding-Window Flow Control

 - w개의 frame 한 번에 보냄 (w: window size, TX가 ACK 없이 보낼 수 있는 frame의 수)

 - RX는 W frames 만큼 buffer 할당

 - 각각의 frame은 번호(sequence #) 매겨짐

 - ACK에는 다음에 보내야 할 frame의 sequence # 정보 포함

 - frame은 2^k modulo로 번호 매겨짐. max window size(ACK을 보내지 않고 한 번에 보낼 수 있는 frame 개수) : 2^k -1

 

* ACK

  (1) RRk

   - (k-1)번째 frame까지 받았고 k번째 frame부터 보내주면 된다는 의미의 ACK

   - TX는 이 ACK를 받으면 추가적으로 frame을 보내도 됨

 

  (2) RNRk

   - (k-1)번째 frame까지 받았고(Received) k번째 frame을 받을 준비가 되지 않았다(Not Ready for the Kth frame)는 의미의 ACK 

   - resume 하기 위해서는 ACK를 다시 보내야만함

 

  (3)Piggybacking

   - TX, RX 모두 RX, TX 역할도 할 수 있을 때(full duplex), ACK을 보내는 동시에 frame도 보내면 좋겠다는 아이디어에서 만들어진 것

  ① data와 ACK를 함께 보냄

  ② ACK은 있는데 data는 없다면 ACK만 보냄

  ③ data는 있는데 보낼 ACK이 없다면, 마지막에 보냈던 것 계속 다시 보냄

 

* Utilization

 case 1) W ≥ 1 cycle / Ttrans

≫ Utilizaion = 100%

 case 2) W < 1 cycle / Ttrans

≫ Utilization = ( (W * Ttrans) / 1 cycle ) *100 < 100%

 

 

 

 Error Control

 

* Two types of errors

① Lost frames: frame이 도착하는 것에 실패함 

  - at TX: timeout (loss 거나 ACK을 했지만 그것이 loss) -> retransmission

  - at RX: out of order delivery

② Damaged frames: frame이 도착은 했지만, 이상한 frame이 도착함 -> negative ack을 보냄

 

* Automatic Repeat Request (ARQ)

 - error control mechanisms의 이름

 - loss frame을 no-loss & in-order frame으로 바꿔줌

 - 종류: Stop-and-wait ARQ, Sliding-window ARQ(Go-back-N ARQ, Selective-reject ARQ)

 

1. Stop-and-Wait ARQ

 (1) 하나의 frame을 전송한다

 (2) ACK을 기다린다 (ACK이 올 때까지 다른 data는 보내지 않음)

 (3-1) 도착한 frame이 손상됐으면 버린다 (이 경우 RX에서 ack을 보내지 않으므로 TX에서는 timeout, retransmit 해야함)

 (3-2) ACK을 보냈지만 이것이 손상된 경우, TX는 인지하지 못함 (TX는 retransmit 해야함, RX는 같은 frame을 다시 한 번 더 받음 -> frame에 다르게 label(ACK0, ACK1)을 하며 해결할 수 있음 -> frame 0 or 1로 판단해서 아까 받은 거구나를 인지하고 high level인 IP에 아까 보냈던 것을 똑같이 보내지 않고 discard함)

- 장점: 간단, 단점: 비효율

- send W = 1

- receive w = 1

- TX에 하나의 timer가 있음 ≫ 하나 보내고 하나 잘 갔는지 기다림

 

2. Go-Back-N ARQ

 (1) 가장 많이 사용되는 error control

 (2) sliding-window flow control 기반

 (3) window size 사용

 (4) 에러가 나지 않는다면 RX는 다음번에 받아야 할 frame number 정보를 포함한 ack을 보냄

   - RR(RR1: 0까지 잘 받았으니 1부터 보내주면 된다) or Piggybacked ACK

 (5) RX가 에러를 감지 했다면 negative ACK인 REJ를 보냄 (REJ4: 3까지 잘 줬는데 4부터 다시 보내라)

   - RX는 에러가 난 frame을 버리고, TX는 다시 보내줘야함

 

3. Selective-Reject ARQ

 (1) SREJ 나 time-out frame만 다시 보내져야함 (에러가 난 것만 다시 달라고 함. RX가 나머지 제대로 온 것들은 저장)

 (2) 장점 : retransmission의 양을 최소화 함

 (3) 단점 :  RX는 buffer 공간을 크게 유지해야함. TX와 RX에 복잡한 logic 필요

 (4) Tprop가 큰(propagation delay가 긴)  satelite link 같은 곳에 유용(GBN은 모두 다시 보내야 하는데, 너무 거리가 머니까 그냥 buffer space의 memory를 더 할당해주는 것이 나음)

 

* GBN

 -send W = 2^k -1

 -receive W = 1

 

* Selective-Reject

 - send W = 2^(k-1)

 - receive W = 2^(k-1)

 

 

 

 High-Level Data Link Control (HDLC)

 

* 가장 중요한 data link control protocol

* communication station의 3종류 : primary, secondary, combined

* link configuration의 2종류: unbalanced, balanced

* data transfer의 3가지 mode: NRM, ABM, ARM

 

1. Frame Structure

 - synchronous transmission 사용

 - single frame format 사용

  ① Flag: at start and end

  ② Address: multi-point link에 addressing

  ③ Control: flow and error control

  ④ Information: payload data or link management data

  ⑤ FCS: for error detection

 

 (1)Flag Fields (1 byte)

  - 01111110

  - 한 frame의 closing flag & 다음 frame의 opening flag

  - RX가 synch 맞추기 위해 사용

  - Bit stuffing: flag가 아닌 data에서 flag인 01111110 포함하는 것을 막음

   + TX : 1이 5개 연속으로 있으면 0을 추가함

   + RX: 1이 5개 연속 감지되고 다음 비트가 0이면 버림, 01111110이면 flag로 감지, 01111111이면 에러로 판정

 

 (2) Control Field (1 or 2 bytes)

  * frame type을 구별

   - Information frame (I) : IP pck에 가는 것

   - Supervisory-frame (S) : ARQ mechanism 제공 (piggybacking 사용되지 않을 떄)

   - Unnumbered frame (U) : supplemental link control functions 제공

 

2. HDLC Operations

 (1) I, S or U frame을 교환

 (2) 3단계

  ① Link setup or Initialization : U

  ② Actual Data transfer: I and S

  ③  Link Disconnect : U