Chapter7. Data Link Control Protocols(Flow 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의 뿌리

---

Layer 2 Protocol Data Unit(PDU): "frame"

 

Data frame(I)

 

: payload에 IP packet 내용 넣음

: data transfer할 때 사용

 

ACK frame(S)

 

: payload 없음(IP packet 내용 없음)

: 잘 받았다고 ACK 보낼 때 사용

 

<positive ACK frame>

: "여태까지 잘 받았고 다음 것도 받을 수 있어"

 

<negative ACK frame>

: "여태까지 잘 받았는데 다음 건 못 받을 것 같아" 또는 "못 받았어"

 

Control frame(U)

 

: payload 있긴 한데 IP packet 내용을 넣지 않고 control을 위한 정보(프로토콜끼리 주고받는 내용) 넣음

: connection / disconnection할 때

 

=> 세 개 모두 같은 header 쓰지만 control 값은 다르다.

다음과 같이 I는 3bit짜리 sequece number 2개를, S는 sequence number 1개를, U에는 없다는 점을 기억하자.

 

 

Flow Control

 

받는 쪽의 buffer가 넘치지 않도록 함. 수도꼭지에 비유하면 다음과 같다.

buffer에 들어오는 속도와 버퍼의 processing 속도가 일치하지 않아 loss되는 현상을 막기 위해 buffer 필요

정해진 buffer size를 overflow하는 현상을 막기 위해 λ'를 조절해줘야 한다.

 

1. MTU*x 크기만큼의 buffer 가지고 있음

* L2의 MTU: 한 번에 보낼 수 있는 size(Ethernet: 1500byte)

=> 하지만 MTU가 data rate 결정하는 게 아니라, 그 MTU를 초당 얼만큼 보내는지가 rate 결정(bps)

 

2. receiver가 header를 처리할 때 processing time(error check(CRC), error control 등)

=> buffer 필요. 꽉 차서 넘치면 loss

 

 

<flow control 결정 요인>

 

- Transmission time

MTU frame size=Lbit, signal로 바꾸는 속도=Rbps라고 할 때,,

 

(Lbit를 모두 signal로 바꾸는 데 걸리는 시간)

 

- Propagation time

1bit가 link를 거쳐 src에서 dst까지 가는 데 걸리는 시간

link length(d meters)/propagation speed(v)

 

왼쪽은 error 없다고 가정했을 때, 오른쪽은 error가 생길 때

 

<msg가 왜 frame 단위로 쪼개져서 보내지는지?>

 

1. receiver의 제한된 buffer size

* 표준이 있는 것이 아니라, RX가 정해서 알려줌

 

2. error 발생 -> 더 빨리 캐치 가능

* card 꼽혀 있으면 상위 계층에서 MTU가 몇인지 알 수 있음 -> 쪼개서 아래 계층으로 내려보냄

* error 나면 전체 데이터가 아니라, error가 난 데이터 부분만 retransmission 가능

-> 절약해서 다른 데이터 보내기 가능 -> link 효율↑

* 끊어서 보내면 빨리 도착해서 그것만 detection해서 다시 달라고 하기 때문에 앞쪽에 있으면 더 빨리 감지 가능 

 

3. worst delay 줄이기 가능

* shared medium에서 average delay는 같을 수 있지만,

쪼개 보내지 않으면 한 번 당 기다려야 하는 시간이 길기 때문에 원인 모른 채 답답함

 

Stop-and-Wait(S&W)

 

: RX는 한 손밖에 없음

=> 한 개씩 처리(첫 번째꺼 받고 처리하고 넘겨주고, 그 다음 두 번째꺼 받고 처리하고 넘겨주고..)

=> positive ACK만 존재(가장 간단한 방법) & buffer 필요 없음

 

TX와 RX는 같은 프로토콜을 공유하기 때문에 다음과 같은 동작이 이루어질 수 있다.

 

<1 cycle>

TX가 하나의 frame 전송(IP packet 1개씩 frame에 담겨 전송됨)
-> RX가 받아 header processing(flow control&error control)
-> 완료되면 ACK으로 응답
-> TX가 ACK 받으면 다른 frame 전송(ACK 받지 못하면 TX가 다음에 안 보냄)

 

message 길이가 길 때 효과 good(더 빨리, link 효율 좋게)

** message를 frame 단위로 쪼개 보냄 => message가 아니라 frame을 보내는 것임 => message size가 아니라 frame size가 중요한 것임

 

더 많이 쪼개질수록 안 좋음

1. propagation delay가 많아짐 (중간중간 더 많이 기다림)

2. wait idle이 많아지면서 link 효율 떨어짐

 

"link utlization"

utilization = transmission time(Ttrans)

frame size(L) 클수록, link length(d) 작을수록 → S&W 방식의 utilization ↑

 

 

다음 두 가지 경우를 보자.

1. Tprop < Ttrans (d/v < L/R => d/v *R < L)

2. Tprop > Ttrans (d/v > L/R => d/v *R > L)

 

왼쪽이 1번, 오른쪽이 2번이다. L(frame size)이 작은 2번이 idle time이 많아 utilization이 안 좋다.

 

 

<예제1>-장거리 통신(Tprop>Ttrans)

 

<예제2>-단거리 통신(Tprop<Ttrans)

 

Flow Control: Sliding-Window

 

Stop-and-Wait 방식에서 놀고 있는 시간이 많다는 점을 개선한 것이 sliding-window 방식이다.

=> 한 개가 아니라 여러 개의 frame을 보낼 수 있다.(<-> stop-and-wait)

 

 

frame 수가 적은 것이 좋기 때문에, 보낼 수 있는 frame 수(W)를 적어놓았다.

W(Window size) = frame size(L) * frame 개수

=> 이 정보는 RX가 자신의 buffer size를 고려하여 정하는데, connection을 통해 TX에게 알려준다.

 

 

여러 frame을 동시에 보내기 때문에 문제가 생길 수 있음

=> IP packet 내용을 볼 수는 없기 때문에, frame마다 다음 frame의 sequence number를 매겨 header에 추가(3bit) -> error detection 가능

다음 빨간색이 sequence number다.

 

Sequence number가 3bit이기 때문에

sequence number modulo에 들어갈 수 있는 숫자는 0, 1, 2, ..., 2^k-1 이다. 더 필요하면 처음부터 다시 쓴다.

=> 0, 1, 2, ..., 2^k-1, 0, 1, 2, ...2^k-1, 0, 1, 2, ...

=> 몇 개를 같이 보내느냐는 그때그때 결정한다.

 

<ACK frame의 종류>-RR & RNR

ACK frame은 RX가 보냄

 

1. RRk

: positive ACK(잘 받았다는 답장)

: error control & flow control 둘 다 사용 가능

RX -> TX: "k-1 번째 frame까지 잘 받았고 k번째 받을 준비 됐어"

* cumulative하기 때문에 RR4를 못 받아도 RR6를 받으면 문제 없음!

* ACK은 가능한 한 빨리 보내줘야 data rate이 올라감

 

2. RNRk

: negative ACK(못 받았거나 에러가 있다는 답장)

: flow control할 때만 사용

RX -> TX: "k-1번째 frame까지 잘 받았지만 buffer에 문제가 생겨서 k번째는 못 받아"

* TX -> RX: TX가 resume하고 싶으면 RX에게 resume하고 싶다는 ACK 보냄

 

 

<W & k 간 관계>

 

Q) kbit짜리 sequence number field, W의 최댓값은?

A) W <= 2^k-1

k=3일 때, sequence number field에는 0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1,2,...

* TX가 8개의 frame씩 동시에 보낼 수 있을 때(W=8)

 

동시에 7개까지 보낼 수 있다.

 

* 반대로 W=16이면 k(sequence number field)는 최소 5bit 이상이어야 함 (16<=2^5-1)

 

<piggybacking>-한꺼번에 처리!!

 

TX와 RX 역할을 동시에 수행하는 "full-duplex"에서만 가능

- TX: data sequence number를 포함한 data frame을 보내고 ACK 받음

- RX: data frame을 받고 ACK sequence number를 포함한 ACK 보냄

즉, 위에서 내려오는 data를 보내면서 ACK 받고, 상대방에게서 data를 받으면서 ACK 보냄 => two-dimensional

1. (I-frame) 데이터 보내고 싶은데 ACK도 보내야 할 때 -> 따로 보내면 overhead 생기므로 같이 보냄(piggybacking)

* sequence number field 2개 = 내가 지금 보내는 data의 sequence number + ACK sequence number

2. (S-frame) 보낼 데이터 없어도 ACK 해야 하는 경우: ACK은 빨리 할수록 좋기 때문

* sequence number field 1개 = 상대방이 보낸 것에 대한 ACK의 sequence number

3. (I-frame) 처음 보내는 거라 보낼 ACK 없을 때 -> 마지막 ACK를 한 번 더 보냄

 

세 가지 경우는 다음 예시에서 초록색으로 표시해뒀다.

A와 B가 보내는 숫자는 같은 숫자라 하더라도 서로 독립적이고 다른 숫자임을 꼭 명심하자. (A의 1과 B의 1'는 다름)

<예제>-W 예측하기

Q) TX가 RX에게 F0, F1, F2, F3, F4, F5, F6 보냄 => W>=7

TX는 RX로부터 F0과 F1이 잘 도착했다는 "RR2" ACK을 받음(W=7이었다면 ACK은 빨리 보내야 다른 것 보낼 수 있기 때문)

-> ACK을 포함해 최대 5개를 더 보낼 수 있었음(W=7이었다면 최대 2개까지만 더 보낼 수 있었을 것임..)

-> W는?

 

A)

W = ACK을 안 받고도 보낼 수 있는 최대 frame 개수(아직 unacked상태인 최대 frame size)

아직 unacked 상태인 frame = 5개(F2, F3, F4, F5, F6)+추가로 받은 5개의 unacked frame

-> 총 10개의 frame이 unacked인 상태

=> W=10

 

Sliding Window Diagram

sequence number를 담은 자료구조인데

당장 IP packet이 오면 첫 번째로 붙일 수 있는 sequence number = 0이고,

W=7이라고 가정하면, 7-2=5이므로,

다음 5개 sequence number인 0~4 사이의 숫자 이외의 숫자들이 오면 오류라고 판단하게 된다.

 

 

flow control 시 => TX의 W = RX의 W

error control 시 => TX의 W != RX의 W

 

<예제>

k와 W값을 고려해, ACK 받기 전과 후를 잘 살펴보는 것이 중요하다.

 

다음은 utilization이 100%인 경우와 아닌 경우를 나눈 것이다.

- ACK 도착시간이 W보다 작으면, 아직 처리하지 않았는데도 일감이 계속 들어오는 상황이라고 볼 수 있으므로 util=100%

- ACK 도착시간이 W보다 빠르면, 놀고 있는 시간이 있다고 볼 수 있으므로 util<100%

 

W=5, 6 이어도 왼쪽은 여전히 util=100%

저속이지만 옆에 성능 좋은 기계가 붙어있을 때 왼쪽