Chapter7. Data Link Control Protocols(Error Control)

1. Flow Control

• Stop-and-Wait Flow Control
• Sliding-Window Flow Control

 

2. Error Control

• Stop-and-Wait ARQ
• Sliding-Window ARQ

• Go-Back-N ARQ
• Selective-Reject ARQ

3. HDLC(High-Level Data Link Control)

: Sliding-Window 방식으로 Flow&Error Control하는 표준 프로토콜

: Ethernet, Wifi의 뿌리

---

Error Control

 

두 개의 frame을 사용한다는 것은 계속 말해왔다.

- Data frame: L2 payload 안에 IP packet 정보 가짐

- ACK frame: IP packet 없음

 

<error 종류 2가지>

- lost frames: RX로 전달 실패

* TX에서 -> timeout되면(걸어둔 제한시간 내에 안 오면) lost 됐다고 판단 OR RX로부터 negative ACK

* RX에서 -> out-of-order delivery(sliding window쓸 때만 알 수 있음: 하나 빼먹고 왔을 때(12456), OR 왔는데 framing이 잘못돼서 시작과 끝을 알 수 없음)

- damaged frames: 왔는데 bit error 존재(CRC 했는데 안 떨어지면 error라고 판단)

=> lost frame이거나 damaged frame이거나 TX에게 다시 보내달라고 요청하는 것은 마찬가지다.

 

- Error detection은 RX쪽에서 한다.

full duplex이면 receive module에서 진행

positive ACK 보냄 -> 상위 계층에서 느끼는 data rate 향상

- Retransmission은 TX쪽에서 한다.

retransmission과 negative ACK 전송은 닭이 먼저냐 달걀이 먼저냐 싸움.

 

Automatic Repeat Request(ARQ)

 

Error Control 진행하는 메커니즘

 

<ARQ의 역할>

"reliablility"

: error가 일어났지만 상위 계층에서는 아무일없다고 느낄 수 있도록 해줌

: RX가 no loss & in order & no duplication 한 데이터 받음

 

<ARQ의 종류>

1. Stop-and-wait ARQ: positive ACK만 사용(알아서 timeout되도록 냅둔다)

2. Sliding Window ARQ

- Go-back-N ARQ(GBN): TCP, HDLC 모두 이거 사용

* RRk(k보낼 차례야), REJk(k부터 다 다시 보내줘)

** REJ2: 01345 순으로 받았다면, 2부터 다시 보내라(2가 안 왔으므로 받은 3,4,5는 의미 없기 때문)

- Selective-reject(repeat) ARQ (SRP)

* ACKk, SREGk(받지 못한 것만 다시 보내라)

**SREG2: 01345 순으로 받았다면, ACK0->ACK1->SREG2->ACK3->ACK4->ACK5

 

-> SRP는 GBN에 비해 individual하다.

 

Stop-and-Wait ARQ

 

<작동 순서>

1. TX->RX: frame을 전송

2. TX는 ACK을 기다림

3. damage 발생

- damaged frame은 위 계층에 올려보내지 않고 버림 -> RX는 왔는지 모르기 때문에 결국 아무것도 오지 않은 상황과 똑같음

- frame은 잘 왔지만 damaged ack이면 TX가 알아차리지 못함

 

<문제 상황>

 

(case1) TX->RX: 데이터 전달 실패

(case2) TX->RX 전달은 됐지만, RX에서 CRC 결과 error

drop -> do nothing

(case3) TX->RX 전달 됐고, CRC 결과 error도 없어 상위계층 IP에게 올려보냈지만

RX->TX: ACK 전달 실패

 

(case4) TX->RX 전달 됐고, CRC 결과 error도 없어 상위계층 IP에게 올려보냈지만

RX->TX: ACK 전달됐지만 damaged ack

 

 

<해결책>

: RX가 받은 frame을 모두 저장하고 새로운 frame 받으면 메모리에 있는 데이터들과 똑같은지 비교 -> 똑같은 게 있으면 올려보내지 않음

-> (문제) layered architecture 각 layer의 independence 위반(payload를 processing한 것이기 때문에,, 택배아저씨가 내 택배를 뜯어본 것과 같음)

-> (해결책) header에 넣어 비교하는 수밖에.. -> "sequence number"에 W=0/1 넣기

 

<timer>

‼️TX에게 1개의 timer 있음 -> timeout되면 RX에게 다시 보냄‼️

 

 

<일반적인 상황>

W=0: "frame 0"을 기다리고 있어

-> 다음과 같이, W=0였던 RX는 TX로부터 데이터를 받으면 IP 계층으로 올려보내고 W=1로 변경

-> W=1: "frame 1"을 기다리고 있어

-> W=1였던 RX는 TX로부터 데이터를 받으면 IP 계층으로 올려보내고 W=0로 변경

 

<loss 일어난 상황>

case3: RX가 보낸 ACK이 중간에 손실된 상황

 

loss된 당시에는 RX가 loss되었다는 사실을 알지 못함

TX가 frame에 해당하는 timer를 그대로 미룸

-> 해당 frame을 나중에 다시 RX에게 보냄

-> RX는 "ACK이 중간에 loss되었었구나"를 알게 됨(이건 IP로 올려보내지는 않음 ∵ 아까 받은 것이기 때문에 duplicate로 판단해 drop)

-> TX에게 loss된 ACK을 다시 보냄

 

 

=> 이렇게 W에 두 값(0/1)만을 사용해서 error correction을 진행하는 방식이다.

 

(+) 단순하다: 그냥 다른 응답이라는 사실만 알면 됨 => 0/1값만 가능한 W 사용.

(-) 비효율적: TX가 중간중간에 놀고 있음 !

 

Sliding Window ARQ

 

- Go-Back-N ARQ

- Selective-Reject ARQ

 

1. Go-Back-N(RR&REJ)

 

TX가 놀지 않도록 하기 위해,,

W를 정할 때, stop-and-wait 방식은 receiver의 buffer만을 고려했다면,

sliding window는 얼마나 많이 retransmission할 수 있을지도 고민한다.

W = min{receiver의 buffer size, retransmit된 frame 최대 개수}

 

=> W는 unacked frame(flow/error 모두 포함)의 최대 개수 조절

 

retransmission만 계속 일어나고 있다면 뭔가 문제가 있다는 것을 알게 됨(link문제, protocol 문제 등)

-> "W를 계속 조절함으로써 retransmission 양 조절"

 

<timer>

‼️TX는 1개의 timer 가지고 있음‼️
(timer은 못 받은 가장 오래된 frame을 가리키고 있음)
-> RRk 받으면 k 버리고 timer reset
-> timeout되면, 아직 ACK 안 된 가장 오래된 frame인 (k+1)부터 다시 다 보냄

==> ACK 받으면 timer가 오른쪽으로 한 칸씩 밀리는 방식으로 진행

 

<error 없으면>

RX가 RR 혹은 ACK을 piggyback해서 보냄

 

<error 있으면>

1. RX->TX: 해당 frame drop & negative ACK(ex. REJ) 보냄

ex. RX가 "F1->F2->F3->F5->F6" 순서대로 받았다면 5 받았을 때 F5 drop하고 , REJ4(4 못 받았어) 보냄

2. TX: RX가 못 받은 것부터 다시 보냄(REJ된 것부터) => W개 받는 것임!!

ex. F4, F5, F6 다시 보냄

 

(scenario1) RX에서 CRC하다가 damaged임 깨달은 경우

-> RX가 바로 TX에게 REJ 보냄

(scenario2) ACK이 가다가 loss된 경우

-> RX는 아직 loss사실을 모르고, TX로부터 다음 frame받았을 때서야 loss되었음을 알게 됨

-> TX로부터 받은 그 frame drop & TX에게 REJ 보냄

 

 

<error 인식 불가한 경우>

: "W=2^k일 때"

-> W=2^k이면 window size만큼의 주기로 인해 error bit와 정상 bit가 똑같아 error로 인식하지 못하게 된다.

예컨대,, W=3인 상태에서 ACK이 가다가 Loss되어도 RX는 모르기 때문에 W=0로 바꿔둔다.

그 후에 오는 k가 0이기 때문에 받고 싶은 것을 받은 것으로 인식해 no error 로 판단하게 된다는 것 !

 

 

 

 

(Sol)

1. sender의 W를 줄이는 방법

- Sender의 W <= 2^k-1

- Receiver의 W=1

 

2. k를 늘림 -> 지수승만큼 더 쓸 수 있음

다음과 같이 k를 하나 늘리면 k값이 2배만큼 늘어나기 때문에 W를 줄이지 않아도 해결 가능하다.

이때 RX가 error를 탐지하여 REGk 보냈는데 

REJk가 timout된 다음 들어왔으면 go back k

(timeout 이전에 들어왔으면 거기서 재개 가능)

 

보라색 부분이 go back k라고 보면 된다.

 

 

2. Selective-Reject(ACK&SREJ)

 

<GBN의 문제 해결>

error 가 너무 많이 일어나면 retransmission 일일이 모두 해줘야 하기 때문에 비효율적

-> selective-reject ARQ는 error가 난 곳만 retransmission해주면 됨

 

<단점1: 버리지 않으므로 RX의 buffer overflow>

RX가 "F1->F2->F4->F5->F6->F7" 순서대로 받았다고 가정해보자.

F3은 받지 못했는데 GBN 방식과 달리 F4,F5,F6,F7을 drop하지 않고 그대로 가지고 있다.

근데 F3이 안 왔다면 IP계층에 이후의 것들 올려보내지 못해 RX의 buffer overflow

-> buffer management가 복잡 !(대기하는 buffer를 따로 둘건지 등등..)

(+ F4는 F3이 올 때까지 계속 buffer에 대기하고 있어야 한다 -> buffer size를 크게 잡아놔야 함)

 

<단점2: Window size(W)를 관리하는 알고리즘도 복잡>

 

 

<장점1: retransmission을 error에 대해서만 하므로 효율적>

<장점2: 장거리 통신에 효과적> ex. satellite(long propagation delay)

 

<Window Size(W)>

- Sender: 2^(k-1)

- Receiver: 2^(k-1)

 

<문제상황>

 

앞에꺼 못 받아도 뒤에꺼 일단 받기 때문에 문제가 생긴다.

아래처럼 ACK0은 가다가 loss됐고 ACK1~6은 모두 잘 도착했다고 하자.

RX는 ACK0이 loss됐다는 사실을 모른 채 (F7, F0, F1, F2, F3, F4, F5) 순서대로 기다리고 있을 것이다.

이때 F0은 이전에 받은 것이 아니라 새로운 것을 의미하지만, TX는 ACK0을 못 받았기 때문에 F0을 다시 보낼 것이다.

그러면 RX는 그 F0을 새로운 F0으로 인식해버리게 된다..

 

(해결책)

W를 반으로 쪼개 씀

-> W=2^(k-1)

ex. k=3 -> 4개씩 쓴다.

 

<예제>

Q) 상위 IP 모듈이 받은 frame의 sequence number은?

A) (0, 1, 2, 3, 4, 5, 6)

2는 예상치 못한 frame이므로 duplicate로 인식해 drop

7은 오다가 loss됐으므로 없고

7을 받지 못했기 때문에 그다음 차례인 0은 받기만 하고 IP로 올려보내지 않는다.