ARQ (Automatic Repeat request)
Error in Computer Network Error in Communication: 보낸것과받은것이다른것 different Binary Channel Models Binary Channel 이란송신자 0 과 의두가지 Symbol 만을전송하는채널 Binary Symmetric Channel Binary Erasure Channel 0 p p p p 0 0 p p p p 0? 0 0 0 BSC BEC 0 0 0 0 0
Error in Computer Network Bit Level Error와 Packet Level Error로일반적으로분류 Bit Level Error Bit 값이 0, 0 Link 나 Channel 단위에서발생 Packet Level Error Packet 이소실 (Erased/Lost) 과도한 Bit Level Error가발생하여패킷을복원하기어려운경우하위계층에서제거 또는네트워크계층에서혼잡 (Congestion) 등으로인해스위치 ( 라우터 ) 가수신한 Packet을처리하지못하여 Drop 시켜발생하기도함 noise Buffer(Queue) Full Congestion N Link N Link N (Channel) (Channel)
Error Detection Error Detection & Recovery Bit Level Error Error Detecting Code Parity Bit, CRC Packet Level Error Loss, Out of Order, Duplicate ARQ Acknowledgement, Sequence Number Approaches in Error Recovery 5 4 Retransmission 수신자측에서송신자측으로 Feedback 을보내고 송신 Q 수신 이를기반으로송신자가문제가된데이터를재전송 FEC (Forward Error Correction) 송신자가데이터외에추가정보 (Redundancy) 를보내에러발생시송신자로부터의재전송없이추가정보만으로수신자가자체복구하는방법 송신 R 5 4 수신 4
STOP AND WAIT PROTOCOL
강의의목표 Stop and Wait Protocol의구성요소와동작원리를설명할수있다. Network Delay를구성하는요소를이해하고설명할수있다. 컴퓨터네트워크에서 Delay가가변적인이유와그것이통신품질에미치는영향을설명할수있다. RTT(Round Trip Time) 을알때 Stop and Wait Protocol의성능을구할수있다. 교재 Chapter 7. Data Link Control Protocol 6
ARQ ARQ Automatic Repeat request Packet Level Error Control Mechanism based on Retransmission Error Detection Positive Acknowledgment Retransmission after Timeout ARQ versions. Stop-and-Wait ARQ. Go-back-N ARQ ~ Sliding Window + Cumulative ACK. Selective Repeat ARQ ~ Sliding Window + Selective ACK 7
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 값은어떻게설정하는것이좋을까? 8
Time Out Stop and Wait Time Out * ACK Duplication Sequence Number 0 0 * * How to detect Duplication? 9
In case of Duplication, should we send ACK? (A) Timeout (B) Timeout 0 0 0 0 * * ACK Duplication! Send ACK? Duplication! Send ACK? Acknowledge Number 0
Stop and Wait Pros and Cons Simple Inefficient Ex) Frame Size = Kbyte, Link Bandwidth = 8Mbps, One-way Propagation Delay = 0ms 일때 Error가발생하지않을경우 Stop and Wait의최대성능은? ( 단역방향으로는별도의 Link를사용하며 Propagation Delay는동일하다 ) Idle Period (Waste of Resource)
Transmission Delay ( 전송지연 ) Network Delay () 어떤양의신호를보내는데걸리는시간 전송용량 ( 대역폭 ) 과정보의양에의해결정 전송지연 = 정보의양 / 전송용량 Propagation delay ( 전파지연 ) 신호가송신지에서수신지까지전파되는데걸리는시간 전송길이및빛의속도에의존 전파지연 = 전송길이 / 전파속도 예 ) 0 km 떨어진곳에수도관을통해 00톤의물을전달하려고한다. 물의유속은시속 0 km이고, 수도관의용량은 분에 톤을처리할수있다. 물전달에걸리는시간을구하라. Processing Delay, Store and Forward Delay, Queueing Delay
Network Delay () Propagation Delay Transmission Delay Time
Network Delay () Circuit Switching Packet Switching Store and Forward Delay Queueing Delay Time Queueing Delay 4
Network Delay 예제 녹음시작 녹음장치 전송장치 전송선길이 = 00Km, 신호속도 : ⅹ 0 8 m/sec 전송용량 : 8Kbps 수신장치 재생장치 Packetizaion/ Frame Delay 번전송시작 4 Propagation Delay Transmission Delay Total Delay 번수신완료및재생시작 5 6 4 5 6 4 5 * Time Delay Jitter 5
SLIDING WINDOW PROTOCOL
강의의목표 Stop and Wait Protocol과 Sliding Window Protocol을비교하여설명할수있다. Sliding Window Protocol의성능을구할수있다. Window 값이미치는영향을이해하고적절한 Window 값설정을위한기본개념을이해한다. Flow Control의필요성을이해하고 Sliding Window Protocol을통한 Flow Control의핵심원리를설명할수있다. 7
Sliding Window Protocol Window size W: Number of Frames that can be transmitted without an ACK Stop and Wait : W = 예 ) Stop and Wait의예에서에러가전혀발생하지않고모든프레임에대해항상 ACK을보낸다고할때최대전송속도를얻기위한 W의크기는? Sliding Window Protocol 의성능은? W= 0 0 0 0 0 8
Sliding Window Diagram 9
Example Sliding Window 0
Positive ACK / Negative ACK Positive ACK Timeout Timeout 0 4 *?? Negative ACK 0 4 5 6 7 0 * * * N. N.
Cumulative ACK / Selective ACK Cumulative ACK Timeout 0 4 5 6 4 * * Selective ACK 4 4 4 7 0 4 5 6 4 * * 0 5 6 0 0 0 5
Based on sliding window Go Back N 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
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 4
Flow Control Flow & Congestion Control keep sender from overrunning receiver Congestion control keep sender from overrunning network Sender 전송속도조절 S Net R Sender 가전송속도를조절하는것. ( 좁은의미의 ) Flow Control 과 Congestion Control 을구분하지않고 이둘을결합하여 ( 넓은의미의 ) Flow Control 이라고도함 TCP 는 Flow/Congestion Control 기능이있지만 UDP 는없음 5
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를늘이고 예 ) 네트워크가혼잡하면 W를줄이고여유가있으면 W를늘이고 6
Error and Flow Control in TCP 전송계층인 TCP 에서도 Error 및 Flow Control 필요 그방식은본장에서소개한기술들을기반으로함 Sliding Window ARQ / Similar to Go back N Flow Control Advertised Window 0 4 0 6 Data Offset Source Port Destination Port Sequence Number Acknowledgement Number Reserved U A P R S F R C S ST YN IN G K H Window Checksum Urgent Pointer Options(If any) + Padding Data 0 bytes 7
Flow Control in TCP 송신자 TCP () ACK 수신자 () 번패킷까지잘받았어. 그리고현재버퍼에추가로 5 개까지더받을수있어 TCP에서수신자는송신자가보낸패킷을수신하면 ACK Flag을 Setting한패킷을송신자에게보내 Error Control 이가능하게한다. 이 ACK 패킷에는해당시점에서수신자가추가로수신가능한데이터양 ( 여유버퍼공간 ) 을 (Advertised) Window에설정하여송신자에게알린다. TCP 송신자는이 Window 이상의정보를보내지않도록자신의 Window 크기를조절한다. 8
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 9
Sliding Window Mechanism of TCP ( 참고 ) Sending App.? Receiving App. LastByteWritten LastByteRead TCP LastByteAcked LastByteSent NextByteExpected LastByteRcvd (Advertised) Window Field of TCP Header Sending side LastByteAcked LastByteSent LastByteSent LastByteWritten buffer bytes between LastByteAcked and LastByteWritten Receiving side LastByteRead < NextByteExpected NextByteExpected LastByteRcvd + buffer bytes between NextByteRead and LastByteRcvd 0
Sending App. Receiving App. MaxSendBuffer = 000 MaxRcvBuffer = 5000 000 A B B Let Initial Effective Window=000 App writes data of 000 bytes ) LastByteWritten=000 TCP sends a segment of 000 bytes ) LastByteSent = 000 TCP receives a segment of 000 bytes ) NextByteRead = ) LastByteRcvd = 000 ) NextByteExpected=00 TCP receives ACK with AW = 4000 ) LastByteAcked = 000 4 TCP sends a segment of 500 bytes (A); But lost during Tx. ) LastByteSent = 500 5 TCP sends a segment of 500 bytes (B) ) LastByteSent = 000 4 5 TCPSend ACK with AW=5000- (N.B.E N.B.R) App reads data of 800 bytes ) NextByteRead = 80 TCP receives a segment of 500 bytes of (B) ) LastByteRcvd = 000 ) NextByteExpected = 00 Send ACK with AW=5000 (N.B.E N.B.R)