(Chap7) Data Link Control

. Flow control

• Goal) in order to prevent receive buffer overflow at RX by adjusting sending rate at TX 
• Flow control is affected by 

1. Transmission time : time for all bits of L-bit frame to be transmitted onto a link whose data rate is R = L bits / R bps
2. Propagation time : time for one bit to travel from TX to RX =  (distance btw TX and RX) / (speed of link propagation) = d / V

Stop-and-Wait Flow control

• TX cannot send any more frame until it will receive an ACK from RX after it sent one frame --> One frame in transit
• TX holds sending a frame until receiving ACK from RX; 즉 RX는 더 보내지 말라는 의미를 ACK을 안보냄으로써 표현함.
• Less efficient than Sliding window, especially when a frame size is smaller or the number of frames is larger with a given message.
• Link Utilization

1. Transmission Time(L-bit frame) / (total operation time, i.e. one cycle)
2. One cycle = T_trans(L-bit frame) + 2 x T_prop ; (frame 1개 보내고 ACK을 받는 것)이 기본 동작임.
3. d (TX와 RX사이의 거리)가 작을 수록 utilization이 높음.
4. L (frame size) 이 크면, (즉, L > (d/V)xR  이면) 하나의 비트 (ex. 첫 번째 비트)가 TX에서 RX로 전파되는 시간 (propagation time) 동안 링크가 transmission 할 수 있는 비트 개수 보다 프레임 크기(L)가 크다는 뜻임. 그래야 , 첫 번째 비트가 전파되는 시간 동아 링크가 놀지 않아 utilization이 높음.
5. 어찌 되었든 하나의 프레임 보내고 ACK을 기다리는 시간 동안은 transmission을 못하고 쉬기(idle)때문에 이 시간의 효율을 높이기 위해 sliding window (즉, ACK 없이 둘 이상의 frame을 전송)이 등장 함.

 

Sliding window Flow control 

• ACK이 없어도 동시에 W개의 frame을 전송해서 link utilization을 높이려는 알고리즘임.
• TX can send more than one frame in limitation of a window size denoted as W without waiting for an ACK frame from RX.
• 즉, Window size, W = max. # of frames that TX  can send without receiving ACK from RX. 단위: frames
• A value of W should be decided by considering receiver's buffer size
• 여러개를 동시에 보내므로 프레임별 번호를 붙일 필요가 있음. --> Need a (k-bit) sequence number in each frame's head
• A value of W is related with k-bits sequence number field in the layer 2 header.

1. 사용되는 W 값은 (2^k) 값 보다는 작게 설정해야 알고리즘 동작에 오류가 없음.
2. (ex) with k=3, frames can be numbered 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, ....
3. W can NOT be 8 when k = 3.  WHY?  
4. 만일 TX가 8개 프레임 <F4, F5, F6, F7, F0, F1, F2, F3>을 전송하고 RX로 부터 RR4를 받으면 그 의미가 (전송한 8개  프레임을 버퍼가 넘치지 않고 모두 잘 받았으니 < > 안의 F3 다음에 해당하는 새로운 F4 프레임을 기다린다) 는 의미인지, 아니면 (전송한 8개  프레임 모두 어떤 문제가 발생해 (ex. BEC에도 동일 알고리즘이 사용, F4가 CRC fail된 경우) < > 안에 있는 (즉 TX가 기전송했던) F4를 기다린다) 는 의미하는지 알고리즘이 판단하기 어려움. 
5. 따라서 해더의 sequence number field가 k(3) bit 이면 2^k (8)개 보다는 최소 1개 작은 개수(7)로 W를 설정해야 함. 물론 RX 버퍼 상황 및 처리 속도를 고려해서 그 보다 더 작게  (6,5,4,3) 설정할 수도 있음.

• two ACKs used used for Sliding window Flow control 

1. RR5 means RX received well up to F4 and is ready for F5
2. RNR5 means RX received well up to F4 but is not ready for F5 <-- Flow control only

• Piggybacking : Sending user data and ACK together and saving bandwidth in full-duplex connection (A와 B가 full duplex 통신한다고 가정)

1. Only used in Full-duplex communication system. (One node can send and received at the same time.)
2. (case 1) sending (user DATA + new ACK)  <-- 만일 B가 작은 시간차로 A에게 RR4 를 보내야하면서 동시에 F5도 A에게 보내야 한다면, data seq. num=5, ACK seq num.=4 로 해더에 표기하고 payload에 IP 패킷을 넣은 frame 한 개만 A에게 전송하면 됨.
3. (case 2) sending only (ACK)  <-- 만일 B가 A에게 RR4를 보내야하는데 B가 A에게 보낼 IP 패킷은 없는 경우라면 B는 RR4 라는 ACK frame 만 A에게 전송.
4. (case 3) sending (user DATA + repeated ACK)  <-- (case1) 이후, 즉 만일 B가 A 에게 RR4 프레임을 보낸 이후 (A로 부터 아무 frame도 받지 않은 상태에서) 추가로 보낼 IP 패킷이 있어 F6를 보낸다면, B가 A에게 보내는 프레임의 해더에는 data seq. num=6, ACK seq num.=4 (case1과 동일한 값)로 표기 됨.

• More efficient than Stop-and-wait protocol 

1. Since sliding window can send more than one frame while waiting for an ACK frame from RX.
2. 특정 시간에 몇개의 추가 프레임을 전송할 수 있을까? = 설정된 W 값에서 아직 까지도 ack을 받지 못한 프레임들 (unacked frame)의 개수를 뺀 값임.

• Utilization of sliding window depends on a window size W.

1. (case 1) W >= (T_trans + 2 x T_prop) / T_trans  --> Utilization is 100% ; 다시 말해서 TX가 첫번째 보낸 프레임에 대한 ACK을 받으면 추가 frame을 보낼 수 있으므로, 첫 번째 프레임을 보내고 그에 대한 ACK을 받는 시간 (T_trans + 2 x T_prop) 동안 내내 프레임을 보내면 (즉, 그 만큼 크기의 W (단위: frame)를 설정하면) link 는 쉬지 않고 일하므로 utilization는 100%가 됨.
2. (case 2) W < (T_trans + 2 x T_prop) / T_trans    --> Utilization = ( W x T_trans ) / (T_trans + 2 x T_prop) x 100  < 100%

 

< Automatic Repeat Request (ARQ) >

• How to detect "lost frames" : timeout at TX , out-of-order at RX (only when using sliding window)
• What does "reliable transmission" mean? : No loss and in-order data transfer (즉, 2계층 프로토콜이 ARQ를 한다는 것은 3계층 IP 모듈이 이전 노드에서 보낸 IP 패킷들을 손실없이, 순서에 맞게, 중복없이 받게 된다는 의미임.)
• ARQ is Backward Error Correction (BEC) i.e., retransmission by TX.
• Stop-and-wait ARQ

1. positive ACK (ACK0/ACK1), no negative ACK 
2. Q: Why we need alternative ACKs like ACK0/ACK1? In order to distinguish the duplicate frame sent by TX when ACK from RX is lost.

• Go-back-N ARQ

1. Two ACK frames : ACK, SREJ <-- 둘 모두 individual acknowledge 입니다. 각 frame 마다 잘 받았는지 아닌지를 알려줍니다.
2. Q: What does REJ5 means? : Please retx from F5 and subsequent frames, i.e. go back to F5), 
3. Send window size = (2^k) - 1, receive widow size = 1, where k= a size of sequence number field in header
4. At TX, the only one timer is attached to the oldest unacked frame and TX resends from the oldest unacked frame when timeout. 

• Selective reject ARQ

1. Two ACK frames : RR, SREJ
2. It requires more buffer space, more complicated window/buffer management at RX, but less re-transmission overhead than GBN 
3. More appropriate for long propagation connection or low bandwidth link like satellite communication than GBN
4. Send window size = receive window size = (2^k ) / 2, where k=sequence number field size; Selective reject ARQ는 에러가 있는 프레임만 다시 전송하기 때문에 RX 가 새로 받을 것으로 기대하는 sequence number 와 TX가 (RX가 전송한 ACK을 받지 못해) 재전송할 수도 있는 프레임의 sequence number가 겹치지 않고 달라야 함.
5. Timers attached at individual frames in its sending buffer. When each time expires, the corresponding frame is resent. 

< High-level Data Link Control (HDLC) >

• HDLC can be used for a point-to-point link in WAN
• Like TCP, HDLC is a connected-oriented protocol and thus its operation consists of Link setup, data transfer and link disconnect steps.
  
• Unlike Ethernet that uses 48-bit source and destination MAC addresses, HDLC uses one 8-bit address.
• Flag fields are used to recognize one frame correctly. Bit-stuffing is needed.
• HDLC defines three types of frames : Information frame (I-frame), Supervisory frame (S-frame) and Unnumbered frame (U-frame);  Which frame type is used for delivering IP packet?  I-frame