CHAP 3. The Data Link Layer: Part 2

강의내용 - Stalling책

• Chap 7. 데이터링크 제어 프로토콜

• 강의 내용

① Framing

*② Flow Control: 송신자와 수신자 간에 얼마만큼의 frame들을 전송할 것인가?

*③ Error Control: Error가 발생한 frame들을 어떻게 재전송할 것인가?

*④ Data Link Layer Protocols: HDLC(High-level Data Link Control)

(Stallings 10th ed.) p.218

• LAN: Logical Link Control (frame 작성 & 전송)

• WAN: Data Link Layer

• Computer Network

- Horizontal View

S

R

R

R

R

R

R

R

R

R

R

S

KNUE

충북대

KREN

(서울대)

X.25

NSFNet

U. C. at

Berkeley

U. C. at

L. A.

210.93.99.64

Data Link Layer

- host-switch

- switch-router

- router-router

Network Layer

- host-host

Frame Relay/ATM

• The Data Link Layer in the Internet: The "Network Access" Layer

(Data Link Layer + Physical Layer)

- Vertical View

Network

Access

Layer

TCP

UDP

H/W

interface

IP

process

host

H/W

interface

H/W

interface

IP

gateway/router

H/W

interface

H/W

interface

IP

gateway/router

TCP

UDP

H/W

interface

IP

process

host

WAN

Ethernet

Ethernet

Flow Control

• Purpose: 송신자와 수신자 간에 얼마만큼의 frame들을 전송할 것인가?

⇒ In the absence of flow control, the receiver's buffer may "overflow", while it is processing old frames.

⇒ 송신자와 수신자 간에 주고 받는 “frame의 양”을 조절해야 함.

(Stallings 10th ed.) p.219 Fig. 7.1	(Stallings 7th ed.) p.248 Fig. 7.1

• Idea

- The sender "waits" for a positive ACK from the receiver before advancing to the next frame.

- If ①the timer expires/②NAK is received, the same frame is sent AGAIN.

Thus, the sender requires to maintain a transmitted frame UNTIL an ACK is 'received' for that frame.

(Stallings 10th ed.) p.238 Fig. 7.9(b)(d)(Stallings 7th ed.) p.269 Fig. 7.9

- 이러한 PAR(Positive Ack. with Retransmission)/ARQ protocol에서 한번에 “얼마만큼의” frame들을 보낼 것인가?

① Stop-and-Wait protocol: frame을 하나씩 보내고, ACK를 받음.

(window size = 1)

② Sliding Window protocol: frame을 여러 개씩 보내고, 한꺼번에 ACK를 받음. (window size ≥ 1)

⇒ Window size: sender와 receiver가 buffer에 갖고 있어야 할 frame의 수.

(Stallings 10th ed.) p.223 Fig. 7.3

(Stallings 7th ed.) p.252 Fig. 7.3

1. Stop-and-Wait protocol: simple method

- Idea: The sender transmits a 'single' frame and then wait an ACK.

No other frames can be sent until a receiver's reply arrives at the sender. (window size = 1)

(ex) For a half-duplex line,

Frames queued

for transmission

Frames awaiting

ACK/NAK

Frames in transit

Frames retained

A1

A

B

A1

A2

A3

A

B

NAK

A1

By CRC checking, A1 in error, NAK sent

A1

A

B

A

B

ACK

A1

A1 retransmitted

A1 removed

- Adv.: Small buffer & simple

Disadv.: If link is long, performance loss can be very significant.

⇒ Low utilization of a channel

A1

A

B

Not used

(Stallings 10th ed.) p.221 Fig. 7.2

(Stallings 7th ed.) p.250 Fig. 7.2

(ex) To send 1K bit frames when sender의 전송속도=50Kbps

250msec/trip

A

B

t=0: to start sending

t=1/50sec=20msec: to completely send the frame

t=270msec: to fully arrive

t=520msec: for ACK to arrive back at the sender

⇒ The sender 'wastes' its time at the rate of 500/520 ≃ 96% of the time

- Piggybacking:	ACK can be "piggybacked" on the data frame from the receiver to the sender.

⇒ ACK를 data frame에 얹어서 운반.	(Stallings 10th ed.) p.224

⇒ Increase utilization

ex)

A1

A

B

A1

A2

A

A1

A2

B

ACK1

A2

A

B

A

B

ACK2

B2

B1

B2

B3

B1

B1

B2

B3

A3

A3

ACK1

A3

A2

B1

B2

B3

B2

B3

A2

A3

2. Sliding Window Protocol

- Idea

□A sender may send a "series" of frames determined by window size.

⇒ A receiver can acknowledge "multiple" frames.

□Each outbound frame contains a "seq. no.", ranging from 0 up to some maximum.

(ex) For n-bit field, the seq. no. is 0 ~ 2n-1.

⇒ A receiver acknowledges a series of frames by sending ACK that includes the seq. no. of the "last" frame received without error.

(ex) B receives frames 2, 3, 4.

By returning seq. no. 4, B ACKed frame 2, 3, 4 at one time.

⇒ OR use a RR(Receive Ready) frame.

(Stallings 10th ed.) p.225 Fig. 7.4	(Stallings 7th ed.) p.253 Fig. 7.4

RR7

□At any instant of time, the sender maintains a list of consecutive seq. no.'s corresponding to frames it is "permitted to send". (the "sending" window)

⇒ The receiver also maintains a receiving window corresponding to frames it is "permitted to accept". (the "receiving" window)

□If the window size is n, the sender needs "n buffers" to hold the 'unACKed' frames.

(Stallings 10th ed.) p.223 Fig. 7.3

(Stallings 7th ed.) p.252 Fig. 7.3

(ex) window size = 7 (max. no. of frames to be sent = 2n-1, Why?)

⇒ "Synchronization": sender와 receiver의 window size는 항상 일치시켜야 함.

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

Sender A

Receiver B

①A may send 7 frames

②B is prepared to receive 7 frames

000

001

010

③A send 3 frames

⑧B ACKed all 3 frames and adjusts its window

0

1

2

3

4

5

6

7

010

⑦B ACKed frame2

last frame no.

without error

0

1

2

3

4

5

6

7

④⑤⑥A shrink its window with each transmission

⑤

⑥

⑨A expand its window with ACK

④

Sender와 Receiver의

window가 일치되었음

Next time, A send 6 frames.

0

1

2

3

4

5

6

7

⑩A send 6 frames

011

100

101

110

111

000

000

⑪B ACKed frame0

Error Control

• Purpose: Error가 발생한 frame들을 어떻게 재전송할 것인가?

⇒ Flow control with "errors"

- Window size = 1의 경우

① Stop-and-Wait ARQ: Error가 발생한 frame을 재전송.

- Window size ≥ 1의 경우

② Go-back-N ARQ: Error가 발생한 frame부터 모두 재전송.

③ Selective Repeat ARQ: Error가 발생한 frame만 재전송.

1. Stop-and-Wait ARQ

- Error가 발생할 경우, 보냈던 frame을 재전송

(Stallings 10th ed.) p.228 Fig. 7.5	(Stallings 7th ed.) p.257 Fig. 7.5

2. Go-Back-N ARQ

- Idea

□A(sender) may send a series of frame determined by window size.

□If B(receiver) detects an error on one of the frames, it sends a NAK for that frame, and discards "all" future incoming frames until the frame in error is correctly received.

□Thus, A, when it receives a NAK, must retransmit the frame in error "plus all succeeding frames".

⇒ error없는 frame들도 버려야 함

(Stallings 10th ed.) p.230 Fig. 7.6(a)

(Stallings 7th ed.) p.260 Fig. 7.6

- Adv.

□Higher utilization than Stop-and-Wait ARQ.

(ex) Stop-and-Wait ARQ

0

0

1

1

2

ACK0

ACK1

"Wasted"

"Wasted"

"Wasted"

……

……

- Disadv.

□Can waste a lot of frames if the error rate is "high".

(회선의 품질이 낮은 경우, 버리는 frame의 수가 많아짐)

- A seq. space of 2n can support a window size of only (2n-1) for Go-Back-N.

⇒ n-bit seq. no. field를 사용하는 경우, 한 번에 보낼 수 있는 최대 전송 frame 수는 (2n-1)

Why?

In most "piggyback" schemes, a fixed-length ACK field of n bits is incorporated into the frame.

⇒ Some no. "must" be put into the frame.

⇒ A station will send an ACK "with a frame", even if the ACK has already been sent.

⇒ "Confusion" can occur in the sender if (frame 수 > 2n-1)

(Stallings 10th ed.) p.230-231	(Stallings 7th ed.) p.261

(ex) n=3의 경우

A send 8 frames

011

100

101

000

Case 1: All 8 frames were received correctly. ⇒ ACK for ②

Case 2: All 8 frames were "lost" in transit, and B is "repeating" its previous ACK0 by piggybacking. ⇒ ACK for ①

∴Max window size for Go-Back-N = 7 (2n-1)

000

000

010

001

110

111

000

①

②

A send 1 frame

A received ACK0

A received ACK0

"Confusion"

따라서, sender가 ACK를 받았을 때, “새로운 ACK”인지, 아니면 “전의 ACK가 반복된 것”인지 혼동하는 경우가 발생

⇒ sender window의 “시작”과 “끝”이 겹치면 안 됨.

0

1

2

3

4

5

6

7

∴ 시작과 끝이 겹치지 않으려면, 최대 전송 frame 수는 (2n - 1)

3. Selective-Repeat ARQ

- Idea

□The frames "only in error" are retransmitted.

(Stallings 10th ed.) p.230 Fig. 7.6(b)

- Adv: Higher utilization than Go-Back-N.

- Disadv:

□The sender requires the logic for sending frame "out of sequence".

⇒ 잘못된 frame을 “찾아서” 다시 보내야 함.

□The receiver requires the logic for "reinserting" the frame in proper sequence.

⇒ 잘못된 frame을 받아서 제 위치에 끼워 넣어야 함.

⇒ The receiver must contain "storage" to save post-NAK frames until the frame in error is retransmitted.

⇒ The Go-Back-N ARQ is more commonly used. (회선 품질의 향상)

- The window size requirement is more "restrictive" for Selective-Repeat that for Go-Back-N.

⇒ The max. window size should be no more than half (2n/2 = 2n-1) the range of seq. no.'s

(즉, n-bit seq. no. field를 사용하는 경우, 한 번에 보낼 수 있는 최대 전송 frame 수는 2n-1임.)

(Stallings 10th ed.) p.231

Why?

Selective-Repeat에서는 순서에서 벗어난 frame도 받음.

⇒ "Confusion" can occur in the receiver if (frame 수 > 2n-1)

(ex) n=3의 경우

Case 1: Frame 0 is a "retransmitted" frame.

Case 2: Frame 0 is a "new" frame.

∴Max window size for Selective-Repeat = 4 (2n-1)

A send 5 frames

010

011

100

001

000

②

000

①

A retransmit frame 0

B received frame 0 (∵Selective-Repeat 에서는 순서대로 받지 않아도 됨)

"Confusion"

100

"lost"

000

000

Time-out

B ACKed all 5 frames and has advanced its window to accept frames 5, 6, 7, 0, 1

⇒ 바로 전 윈도우와 겹치면 안됨

따라서, receiver가 받은 frame이 “재전송된 frame”인지 아니면 “새로 받은 frame”인지 혼동하는 경우가 발생

⇒ receiver에서 “바로 전의 window”와 “현재의 window”에서 겹치는 부분이 없으면, 같은 번호의 frame을 받을 수 없으므로 혼동이 안 됨.

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

전의 window와 겹치는 부분

∴ 바로 전의 window와 겹치지 않으려면, 최대 전송 frame 수는 2n-1

Data Link Layer Protocols

• Framing/Error Detection & Correction/Flow Control/Error Control 기능

• HDLC (High-Level Data Link Control)

①프레임 구조:

(Stallings 10th ed.) p.233 Fig. 7.7	(Stallings 7th ed.) p.263 Fig. 7.7

②동작: (Stallings 10th ed.) p.238 Fig. 7.9