(Automatic Repeat reQuest) ARQ

(1)

(Automatic Repeat reQuest) ARQ

(2)

Error in Computer Network

 Error in Communication: 보낸 것과 받은 것이 다른 것

 2 different Binary Channel Models

 Binary Channel이란 송신자 0과 1의 두 가지 Symbol만을 전송하는 채널

0

1

0

1

0

1

0

1 𝑝 ?

1 − 𝑝

𝑝

1 − 𝑝

𝑝 𝑝 1 − 𝑝

1 − 𝑝

Binary Symmetric Channel Binary Erasure Channel

0 1 1 0 0 1 BSC

BEC

0 1 0 0 1 1

0 1 0 1

(3)

Error in Computer Network

 Bit Level Error와 Packet Level Error로 일반적으로 분류

 Bit Level Error – Bit 값이 0  1, 1  0

 Link나 Channel 단위에서 발생

 Packet Level Error – Packet이 소실 (Erased/Lost)

 과도한 Bit Level Error가 발생하여 패킷을 복원하기 어려운 경우 하위 계층에서 제거

 또는 네트워크 계층에서 혼잡(Congestion) 등으로 인해 스위치(라우터)가 수신한 Packet을 처리하지 못하여 Drop 시켜 발생하기도 함

N1 2 N2 N3

(Channel)Link Link (Channel)

noise 1 3

Buffer(Queue) Full Congestion

3

2 1

2 1 1

2 3

(4)

Error Detection & Recovery

 Error Detection

 Bit Level Error – Error Detecting Code

• Parity Bit, CRC

 Packet Level Error – Loss, Out of Order, Duplicate

• ARQ – Acknowledgement, Sequence Number

 2 Approaches in Error Recovery

 Retransmission

• 수신자 측에서 송신자 측으로 Feedback을 보내고 이를 기반으로 송신자가 문제가 된 데이터를 재전송

 FEC (Forward Error Correction)

• 송신자가 데이터 외에 추가 정보 (Redundancy)를 보내 에러 발생 시 송신자로부터의 재전송 없이 추가 정보만으로 수신자가 자체 복구하는 방법

송신 수

신

2 1 4 3 5

3 Q

송신 수

신

2 1 4 3

5 R

3

(5)

STOP AND WAIT PROTOCOL

(6)

강의의 목표

 Stop and Wait Protocol의 구성 요소와 동작 원리를 설명할 수 있다.

 Network Delay를 구성하는 요소를 이해하고 설명할 수 있다.

 컴퓨터 네트워크에서 Delay가 가변적인 이유와 그것이 통신 품질에 미치는 영향을 설명할 수 있다.

 RTT(Round Trip Time)을 알 때 Stop and Wait Protocol의 성능을 구 할 수 있다.

 교재 Chapter 7. Data Link Control Protocol

(7)

ARQ

 ARQ – Automatic Repeat reQuest

 Packet Level Error Control Mechanism based on Retransmission

 Error Detection

 Positive Acknowledgment

 Retransmission after Timeout

 3 ARQ versions

1. Stop-and-Wait ARQ

2. Go-back-N ARQ ~ Sliding Window + Cumulative ACK 3. Selective Repeat ARQ ~ Sliding Window + Selective ACK

(8)

Stop and Wait

 Source

 Transmit Single frame and Wait for ACK

 Receiving ACK, Transmits the next frame

 If no ACK within Timeout, Retransmit

 Receiver

 If received frame damaged, discard it.

 Otherwise, received a frame without damage, Transmits ACK

 구성 요소

 ACK, Timeout, Retransmission, SEQ Number, ACK Number

 고려 사항

 SEQ Number와 ACK Number는 왜 필요할까?

 Timeout 값은 어떻게 설정하는 것이 좋을까?

(9)

Stop and Wait

*

Time Out

ACK

Time Out

Duplication

*

How to detect Duplication ?

Sequence Number

0 0 1

*

(10)

0

*

0 0 0 1

* 2

Timeout

ACK

(A)

Duplication ! Send ACK ?

Timeout

(B)

Duplication ! Send ACK ?

In case of Duplication, should we send ACK ?

Acknowledge Number

(11)

Stop and Wait – Pros and Cons

 Simple

 Inefficient

 Ex) Frame Size = 1Kbyte, Link Bandwidth = 8Mbps, One-way Propagation

Delay = 10ms 일 때 Error가 발생하지 않을 경우 Stop and Wait의 최대 성능은 ? (단 역방향으로는 별도의 Link를 사용하며 Propagation Delay는 동일하다)

Idle Period

(Waste of Resource)

(12)

Network Delay (1)

 Transmission Delay (전송 지연)

 어떤 양의 신호를 보내는데 걸리는 시간

 전송용량(대역폭)과 정보의 양에 의해 결정

 전송지연 = 정보의 양 / 전송용량

 Propagation delay (전파지연)

 신호가 송신지에서 수신지까지 전파되는데 걸리는 시간

 전송길이 및 빛의 속도에 의존

 전파지연 = 전송길이 / 전파속도

 예) 10 km 떨어진 곳에 수도관을 통해 100톤의 물을 전달하려고 한 다. 물의 유속은 시속 20 km이고, 수도관의 용량은 1분에 2톤을 처 리할 수 있다. 물 전달에 걸리는 시간을 구하라.

 Processing Delay, Store and Forward Delay, Queueing Delay

(13)

Network Delay (2)

Time

Propagation Delay

Transmission Delay

(14)

Network Delay (3)

Time

Store and Forward Delay Circuit Switching

Packet Switching

Queueing Delay

(15)

Network Delay 예제

Time

1

녹음장치 전송

장치 재생

수신 장치 전송용량 : 128Kbps 장치

전송선 길이 = 200Km, 신호 속도: 2ⅹ 10⁸m/sec

2 3 4 5 6

녹음 시작

Packetizaion/

Frame Delay

1 2 3 4 5 6

1번 전송 시작

Propagation Delay

1 2

Transmission Delay

1 2

1번수신 완료 및 재생 시작

Total Delay

3

4 5

3 *

Delay Jitter

(16)

SLIDING WINDOW PROTOCOL

(17)

강의의 목표

 Stop and Wait Protocol과 Sliding Window Protocol을 비교하여 설 명할 수 있다.

 Sliding Window Protocol의 성능을 구할 수 있다.

 Window 값이 미치는 영향을 이해하고 적절한 Window 값 설정을 위한 기본 개념을 이해한다.

 Flow Control의 필요성을 이해하고 Sliding Window Protocol을 통 한 Flow Control의 핵심 원리를 설명할 수 있다.

(18)

Sliding Window Protocol

 Window size W: Number of Frames that can be transmitted without an ACK

 Stop and Wait : W = 1

 예) Stop and Wait의 예에서 에러가 전혀 발생하지 않고 모든 프레임에 대해 항 상 ACK을 보낸다고 할 때 최대 전송 속도를 얻기 위한 W의 크기는 ?

 Sliding Window Protocol의 성능은?

0

W=3 2

1 1

2 0

1

3

2

0 1

1 0

3 0

1

2 2 1

2

3 1 2

(19)

Sliding Window Diagram

(20)

Example Sliding Window

(21)

Positive ACK / Negative ACK

 Positive ACK

 Negative ACK

0

1

2

1 3

3 2

4

*

??

0

N.3 2

1 3 4

*

3 3

Timeout

*

3 Timeout

5 6

*

N.3

7 0

(22)

Cumulative ACK / Selective ACK

 Cumulative ACK

 Selective ACK

0

1

2

1 3

3 2

4

*

5 6

4

*

4 4

Timeout

4

7

0

2

1 3

2 1

4

*

5 6

3

*

5 6

0 1

0 2

10

32 1

53 2

4

(23)

Go Back N

 Based on sliding window

 Use window to control number of outstanding frames

 If no error, ACK as usual with next frame expected

 If error, reply with rejection

 Discard that frame and all future frames until error frame received

 Transmitter must go back and retransmit that frame and all subsequent frames

 Combination of Cumulative ACK and Negative ACK

(24)

Selective Repeat

 Also called selective retransmission

 Only lost frames are retransmitted

 Subsequent frames are accepted by the receiver and buffered

 Minimizes retransmission

 Receiver must maintain large enough buffer

 More complex login in transmitter

(25)

Flow & Congestion Control

 Flow Control

 keep sender from overrunning receiver

 Congestion control

 keep sender from overrunning network

 Sender가 전송 속도를 조절하는 것.

 (좁은 의미의) Flow Control과 Congestion Control을 구분하지 않고 이 둘을 결합하여 (넓은 의미의) Flow Control 이라고도 함

 TCP는 Flow/Congestion Control 기능이 있지만 UDP는 없음

S Net R

Sender

전송 속도 조절

(26)

How to control the transmitting speed?

 Rate Based Approach

 (X)bps의 속도로 전송하라; X를 조절;

 구현을 위해 Timer 등이 필요.

 Window Based Approach

 추가로 (X)bytes 까지 전송할 수 있다; X를 조절;

 Counter 등으로 간단하게 실현 가능

 TCP를 포함하여 많은 실용 프로토콜에서 쓰임.

 Sliding Window Protocol

 Error Control + Flow Control

 Sliding Window Protocol의 Throughput과 Window 크기 W의 관계는?

 Window의 크기 W를 조정하면 전송 속도를 조정할 수 있다.

• 예) 수신자의 버퍼 크기가 부족하면 W를 줄이고 충분하면 W를 늘이고

(27)

Error and Flow Control in TCP

 전송 계층인 TCP에서도 Error 및 Flow Control 필요

 그 방식은 본 장에서 소개한 기술들을 기반으로 함

 Sliding Window ARQ / Similar to Go back N

 Flow Control – Advertised Window

0 4 10 16 31

Urgent Pointer Source Port Destination Port

Sequence Number

Acknowledgement Number

Data

Offset Reserved Û_G^R Â_K^C _H^P^S ^R_T^S ^Y_N^S _N^FÎ Window Checksum

Options(If any) + Padding Data

20 bytes

(28)

Flow Control in TCP

 TCP에서 수신자는 송신자가 보낸 패킷을 수신하면 ACK Flag을 Setting한 패킷을 송신자에게 보내 Error Control 이 가능하게 한다.

 이 ACK 패킷에는 해당 시점에서 수신자가 추가로 수신 가능한 데이터 양 (여유 버퍼 공간)을 (Advertised) Window에 설정하여 송신자에게 알린다.

 TCP 송신자는 이 Window 이상의 정보를 보내지 않도록 자신의 Window 크 기를 조절한다.

송신자 수신자

TCP (1)

ACK

(1)번 패킷까지 잘 받 았어. 그리고 현재 버퍼에 추가로 5개까

지 더 받을 수 있어

(29)

Flow Control in TCP (참고)

 Send buffer size: MaxSendBuffer

 Receive buffer size: MaxRcvBuffer

 Receiving side

 LastByteRcvd - LastByteRead < = MaxRcvBuffer

 AdvertisedWindow = MaxRcvBuffer - (NextByteExpected - NextByteRead)

 Sending side

 LastByteSent - LastByteAcked < = AdvertisedWindow

 EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)

 LastByteWritten - LastByteAcked < = MaxSendBuffer

 block sender if (LastByteWritten - LastByteAcked) + y > MaxSenderBuffer

 Always send ACK in response to arriving data segment

 Persist when AdvertisedWindow = 0

(30)

Sliding Window Mechanism of TCP (참고)

 Sending side

 LastByteAcked ≤ LastByteSent

 LastByteSent ≤ LastByteWritten

 buffer bytes between LastByteAcked and LastByteWritten

 Receiving side

 LastByteRead < NextByteExpected

 NextByteExpected ≤ LastByteRcvd +1

 buffer bytes between NextByteRead and LastByteRcvd

Sending App. Receiving App.

LastByteAcked LastByteSent

LastByteRead

NextByteExpected LastByteRcvd

TCP

(Advertised) Window Field of TCP Header LastByteWritten

?

(31)

Sending App. Receiving App.

2000

MaxRcvBuffer = 5000 MaxSendBuffer = 3000

① App writes data of 2000 bytes 1) LastByteWritten=2000

② TCP sends a segment of 1000 bytes 1) LastByteSent = 1000

③ TCP receives ACK with AW = 4000 1) LastByteAcked = 1000

④ TCP sends a segment of 500 bytes (A); But lost during Tx.

1) LastByteSent = 1500

⑤ TCP sends a segment of 500 bytes (B) 1) LastByteSent = 2000

① TCP receives a segment of 1000 bytes 1) NextByteRead = 1

2) LastByteRcvd = 1000 3) NextByteExpected=1001

② TCPSend ACK with AW=5000- (N.B.E – N.B.R)

③ App reads data of 800 bytes 1) NextByteRead = 801

④ TCP receives a segment of 500 bytes of (B) 1) LastByteRcvd = 2000

2) NextByteExpected = 1001

⑤ Send ACK with AW=5000 – (N.B.E – N.B.R)

Let Initial Effective Window=1000 B

A B