파이프라인된 프로토콜 파이프라이닝: 송신자는 확인 응답을 기다리지 않고 여러 패킷을 전송하도록 허용

Presentation on theme: "파이프라인된 프로토콜 파이프라이닝: 송신자는 확인 응답을 기다리지 않고 여러 패킷을 전송하도록 허용"— Presentation transcript:

1 파이프라인된 프로토콜 파이프라이닝: 송신자는 확인 응답을 기다리지 않고 여러 패킷을 전송하도록 허용
순서번호의 범위가 증가되어야 한다. 각각의 전송 중인 패킷은 유일한 순서번호를 갖는다. 프로토콜의 송신 측과 수신 측은 한 패킷 이상을 버퍼링 해야 한다. 송신자는 전송되었으나 확인응답 되지 않은 패킷을, 수신자는 정확하게 수신 된 패킷들을 버퍼링해야 한다. 파이프라인된 프로토콜의 두 가지 접근방법: go-Back-N, selective repeat Transport Layer

2 GBN(Go-Back-N): 슬라이딩-윈도우 프로토콜
송신자: 패킷 헤더에 k-bit #순서번호를 포함, 순서번호공간[0, 2k -1]이 된다. 확인응답이 안된 패킷의 최대 허용 수는 “윈도우 크기” N보다 작아야 한다. N: 윈도우 크기, base: 확인 응답이 안된 가장 오래된 패킷의 순서번호, nextseqnum: 전송될 다음 패킷의 순서번호 순서번호공간 [0,base-1]: 이미 전송되고 확인응답이 된 패킷의 순서번호 범위 [base, nextseqnum-1]:송신은 되었지만 아직 확인응답은 안된 패킷(<윝도우 크기) [nextseqnum-1, base+N-1]: 상위계층으로 데이터가 도착하면 바로 전송될 수 있는 패킷 [base+N, ]: 확인응답 안된 패킷의 확인응답이 도착될 때 까지 사용될 수 없다. 프로토콜이 동작하면 순서번호공간에서 윈도우가 오른쪽으로 이동-슬라이딩 윈도우 프로토콜 modulo 2k -1 연산: 순서번호 2k -1 다음에 0이 온다. Transport Layer

3 GBN: 송신자의 확장된 FSM 상위로부터의 지시 L 타임아웃이벤트 Wait ACK의 수신 rdt_send(data)
if (nextseqnum < base+N) { sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) start_timer nextseqnum++ } else refuse_data(data) L base=1 nextseqnum=1 타임아웃이벤트 timeout Wait start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base+1]) … udt_send(sndpkt[nextseqnum-1]) rdt_rcv(rcvpkt) && corrupt(rcvpkt) ACK의 수신 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) base = getacknum(rcvpkt)+1 If (base == nextseqnum) stop_timer else start_timer Transport Layer

4 GBN: 송신자의 확장된 FSM 순서번호 n을 가진 패킷이 정확하게 순서대로 수신된다면 그 외의 경우(순서가 잘못된 패킷):
default udt_send(sndpkt) rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) L Wait expectedseqnum=1 sndpkt = make_pkt(expectedseqnum,ACK,chksum) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt) expectedseqnum++ 순서번호 n을 가진 패킷이 정확하게 순서대로 수신된다면 패킷 n에 대한 ACK를 송신하고 상위 계층에 패킷의 데이터 부분을 전달 수신자는 단지 다음 순서 패킷의 순서번호, expectedseqnum만 유지하면 된다. 송신자는 윈도우 상위와 하위 경계, nextseqnum의 위치를 유지. 그 외의 경우(순서가 잘못된 패킷): 정확하게 수신되어도 순서가 잘못된 패킷은 버린다. 버퍼링을 하지 않는다.->단지 expectedseqnum만 유지 가장 최근의 순서번호를 갖는 패킷의 ACK를 재전송 단점: 손실이 많은 경우 송신 측에서의 많은 재전송이 필요. Transport Layer

5 GBN 동작 Transport Layer

6 선택적 반복: Selective Repeat
수신자에게 오류가 발생한 수신 패킷만을 송신자가 다신 전송하여 불필요한 재전송을 피한다. 송신자는 정확하게 수신된 패킷에 대해 순서와 무관한 개별 확인응답을 요구한다. 순서가 틀린 패킷들은 분실된 패킷이 수신될 때 까지 버퍼에 저장 분실된 패킷을 정확하게 재전송 받으면 버퍼에 있는 패킷들과 순서대로 상위계층에 전달 송신자는 ACK를 못 받은 패킷만을 재전송 한다. 송신자 타이머가 필요 송신자 윈도우 N개의 연속적인 순서번호의 패킷으로 구성 Ack 응답을 받지 못한 패킷에 의해서 순서번호 공간이 제한을 받는다.(그림 3.27) Transport Layer

7 송신자 수신자 윈도우간의 동기화가 이루어지지 않는다.
선택적 반복 : 송신자, 수신자 윈도우 송신자 수신자 윈도우간의 동기화가 이루어지지 않는다. Transport Layer

8 선택적 반복 : 송신자 수신자의 이벤트 sender receiver 상위에서 데이터 받음 :
순서번호가 송신자 윈도우내에 있으면, 패킷 전송 timeout(n): GBN의 단일 타이머가 아닌 각각의 패킷은 자신의 논리 타이머를 갖고 timeout이 발생한 n번째 패킷을 재전송 후 타이머를 재 시작한다. ACK(n) in [sendbase,sendbase+N-1]: 윈도우 안의 패킷에 대한 Ack가 수신되면 수신완료로 표기 만약 ACK를 수신한 패킷이 base라면 윈도우를 오른쪽으로 이동하고 이동된 윈도우 내에 미전송 패킷이 있으면 전송한다. 윈도우[rcvbase, rcvbase+N-1]안의 n 번째 패킷 수신을 수신하면: ACK(n)를 보내고 순서가 맞지 않으면 버퍼링 순서에 맞으면: 상위 계층으로 전달되고, base와 같은 순서번호를 가졌다면 윈도우가 오른쪽으로 이동된다. 윈도우 이전 [rcvbase-N,rcvbase-1] 패킷을 수신하면 ACK(n)만 보낸다. 그렇지 않으면: 무시한다. Transport Layer

9 선택적 반복의 동작 Transport Layer

10 선택적 반복의 문제점 예: 순서번호 공간: 0, 1, 2, 3 윈도우 크기=3 (a)첫 번째 패킷의 재전송
(b)다섯 번째 패킷의 새로운 전송 수신자는 구별할 수 없다. 정상동작이 되지 않는 SR프로토콜 Q: SR프로토콜에서 정상동작을 위한 윈도우의 크기는? 윈도우 크기<=(순서번호 공간의 크기/2) Transport Layer

11 TCP: Overview RFCs: 793, 1122, 1323, 2018, 2581 전이중(full-duplex) 서비스:
연결에서 데이터의 흐름이 양방향 최대 세그먼트 크기(MSS: maximum segment size): app. 계층의 데이터에 대한 최대 크기 송수신 버퍼 흐름제어 송신 측과 수신 측의 송수신 속도 동기화 점대점(point-to-point) 단일 송신자와 단일 수신자 파이프라이닝 TCP 혼잡제어와 흐름제어를 위한 윈도우가 사용 신뢰적인 전송(연결지향형 서비스) 세 방향 핸드세이크: 데이터를 교환하기 전에 송신자와 수신지의 상태를 초기화 Transport Layer

12 3.5.2 TCP 세그먼트 구조 source port # dest port # application data
32 bits application data (variable length) sequence number acknowledgement number Receive window Urg data pnter checksum F S R P A U head len not used Options (variable length) URG: urgent data (generally not used) counting by bytes of data (not segments!) ACK: ACK # valid PSH: push data now (generally not used) # bytes rcvr willing to accept RST, SYN, FIN: connection estab (setup, teardown commands) Internet checksum (as in UDP) Transport Layer

13 simple telnet scenario
TCP 순서번호와 확인응답 순서번호: 전송된 세그먼트의 번호가 아닌 각 세그먼트에서 첫 바이트의 바이트 스트림 “번호”이다. 확인 응답(ACKs): 상대 측에서 기대하는 다음 바이트의 순서번호 누적 확인 응답 Q: 순서가 틀린 세그먼트를 수신하는 경우 호스트는 어떤 행동을 하는가? 규칙 부여 없이 TCP 구현 개발자가 자유로이 선택 세그먼트를 버리거나, 유지 Host A Host B Seq=42, ACK=79, data = ‘C’ Seq=79, ACK=43, data = ‘C’ Seq=43, ACK=80 사용자가 입력 ‘C’ 호스트가 반향 된 ‘c’수신 후에 ACK 호스트는 ‘c’수신 후에 ACK ‘ C’를 반향 time simple telnet scenario Transport Layer

14 3.5.3 TCP 왕복 시간(RTT) 예측과 타임아웃 Q: TCP 타임아웃 주기를 어떻게 설정하는가? 왕복시간의 예측
너무 짧게 설정하면: 너무 이른 타임아웃에 의하여 불필요한 재전송이 발생한다. 너무 길게 설정하면: 세그먼트 손실에 대한 너무 느린 반응에 의하여 데이터 전송 지연이 발생 왕복시간의 예측 SampleRTT: 세그먼트를 전송하여 긍정응답이 도착한 시간까지의 양 재 전송한 세그먼트에 대한 SampleRTT는 계산하지 않는다. SampleRTT은 혼잡과 종단시스템의 가변 부하 때문에 변동이 심하고 불규칙하다. 따라서 왕복시간을 예측하기 위해서 각 SampleRTT값의 평균 값을 취한다. Transport Layer

15 EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT
TCP 왕복 시간(RTT) 예측과 타임아웃 EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT 긍정확인응답을 수신하고 새로운 SampleRTT값을 획득하면 위 공식에 따라서 EstimatedRTT값을 갱신한다. EWMA:Exponential weighted moving average 과거 SampleRTT값의 가중평균에 미치는 영향이 지수적으로 빠르게 감소 즉, 가중평균은 예전 샘플보다 최근 샘플에 높은 가중치를 준다. 일반적으로 권장되는 값  = 0.125 Transport Layer

16 Example RTT estimation:
Transport Layer

17 TimeoutInterval = EstimatedRTT + 4*DevRTT
TCP 왕복 시간(RTT) 예측과 타임아웃 타임아웃 주기의 설정 EstimtedRTT의 변화율 SampleRTT가 EstimatedRTT로부터 얼마나 벗어나는지에 대한 예측 DevRTT = (1-)*DevRTT + *|SampleRTT-EstimatedRTT| (일반적으로,  = 0.25) 타임아웃 주기의 설정: TimeoutInterval = EstimatedRTT + 4*DevRTT Transport Layer

18 3.5.4 TCP 신뢰적인 데이터 전달 TCP는 IP의 비신뢰적인 최선형 서비스에서 신뢰적인 데이터 전달 서비스를 제공한다.
신뢰적인 데이터 전달이란 프로세스가 자신의 수신버퍼로부터 읽은 데이터 스트림이 손상되지 않고, 손실되지 않으며, 중복이 없고, 순서가 유지된다는 것을 보장 세그먼트의 파이프라이닝 누적 확인응답 단일 재전송 타이머 사용 재전송의 다음 두 가지 요건에 의하여 발생한다.: 타임아웃 이벤트 중복된 acks 간단한 TCP 고려 중복된 acks의 수신이 없다. 흐름제어 및 혼잡제어가 없다. Transport Layer

19 TCP 송신자 이벤트 간단한 TCP 송신자를 다음과 같이 가정한다. wait for event
event: data received from application above 간단한 TCP 송신자를 다음과 같이 가정한다. 중복된 acks의 수신이 없다. 흐름제어 및 혼잡제어가 없다. create, send segment wait for event wait for event event: timer timeout for segment with seq # y retransmit segment event: ACK received, with ACK # y ACK processing Transport Layer

20 TCP 송신자 이벤트 상위 app.으로부터 수신된 데이터: 타임 아웃: 순서번호를 갖는 세그먼트를 생성
순서번호는 세그먼트에서 첫 바이트의 바이트 스트림 “번호”이다. 확인 응답 안된 세그먼트에 의한 타이머가 동작되고 있지 않다면 타이머를 시작한다. 타임아웃 주기 설정 TimeoutInterval = EstimatedRTT + 4*DevRTT 타임 아웃: 타임 아웃이 발생한 세그먼트를 재전송 타이머 재시작 타임아웃주기 설정법이 다른 두 이벤트의 경우와 같지 않다. 즉 이전 타임아웃 주기의 두 배로 설정한다. Ack 수신: 확인 응답 안된 세그먼트의 Ack를 수신한다면 수신 확인응답이 안된 가장 오래된 바이트의 순서번호인 SendBase를 갱신 누적확인응답. 아직 확인응답이 안된 세그먼트들이 존재한다면 타이머를 재시작 TimeoutInterval = EstimatedRTT + 4*DevRTT Transport Layer

21 TCP Sender (simplified)
NextSeqNum = InitialSeqNum SendBase = InitialSeqNum loop (forever) { switch(event) event: data received from application above create TCP segment with sequence number NextSeqNum if (timer currently not running) start timer pass segment to IP NextSeqNum = NextSeqNum + length(data) event: timer timeout retransmit not-yet-acknowledged segment with smallest sequence number event: ACK received, with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) } } /* end of loop forever */ TCP Sender (simplified) Transport Layer

22 TCP: 재전송 시나리오 X loss premature timeout time time lost ACK scenario
Host A Seq=92, 8 bytes data ACK=100 loss timeout lost ACK scenario Host B X time Host A Host B Seq=92 timeout Seq=92, 8 bytes data Seq=100, 20 bytes data ACK=100 ACK=120 Sendbase = 100 Seq=92, 8 bytes data SendBase = 120 Seq=92 timeout ACK=120 SendBase = 100 SendBase = 120 premature timeout time Transport Layer

23 Cumulative ACK scenario
TCP: 재전송 시나리오 Host A Seq=92, 8 bytes data ACK=100 loss timeout Cumulative ACK scenario Host B X Seq=100, 20 bytes data ACK=120 time 타임아웃주기의 두 배화 TCP는 재전송 시 타임아웃주기를 EstimateRTT와 DevRtt로 부터 계산하지 않고, 이전 값의 두 배로 설정한다. 타임아웃은 주로 네트워크의 혼잡에 의해서 발생 지속적인 재전송은 네트워크 혼잡을 더욱 악화 따라서 타임아웃주기를 두 배로 늘려 재전송 비율을 낮춘다. SendBase = 120 Transport Layer

24 TCP ACK 생성 권고 [RFC 1122, RFC 2581] Event at Receiver
기다리는 순서번호를 가진 순서에 맞는 세그먼트의 도착, 이미 확인된 기다리는 순서번호까지의 모든 데이터 수신 세그먼트의 도착, ACK 전송을 기다리는 다른 하나의 순서에 맞는 세그먼트 기다리는 것보다 높은 순서번호를 가진 순서가 틀린 세그먼트의 도착, 격차가 발견된다. 수신 데이터에서 격차를 부분 또는 모두 채우는 세그먼트의 도착 TCP Receiver action 지연된 ACK, 또 다른 순서에 맞는 세그먼트의 도착을 위해 500ms를 기다린다. 만약 다음 순서에 맞는 세그먼트가 이 기간에 도착하지 않으면 ACK를 보낸다. 즉시, 두 개의 순서에 맞는 세그먼트를 ACK하기 위해 하나의 누적된 ACK를 보낸다. 즉시, 다음의 기대되는 바이트의 순서번호를 가리키는 중복 ACK를 보낸다. 즉시, 세그먼트가 격차의 낮은 쪽으로 시작하도록 제공하는 ACK를 보낸다. Transport Layer

25 빠른 재전송(fast retransmit)
타임아웃주기가 비교적 길다: 손실 패킷에 대한 재전송 전에 지연을 증가 시킨다. 중복 ACK에 의해서 패킷 손실을 발견할 수 있다. 송신자는 종종 세그먼트들을 연속해서 보내므로 많은 중복 ACK가 여러 번 존재 할 수 있다. 만일 세그먼트가 손실된다면, 많은 중복된 ACK가 발생할 것이다. 만약, 송신자가 같은 데이터에 대한 3개의 중복 ACK를 수신한다면, ACK를 수신한 데이터 후에 전송된 세그먼트는 손실된 것으로 본다. 빠른 재전송: 타임아웃 발생 전에 세그먼트를 재전송한다. Transport Layer

26 빠른 재전송 알고리즘 if (y > SendBase) { SendBase = y
event: ACK received, with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) start timer } else { increment count of dup ACKs received for y if (count of dup ACKs received for y = 3) { resend segment with sequence number y a duplicate ACK for already ACKed segment fast retransmit Transport Layer

27 전송량이 너무 많고 송신 속도가 빠른 경우, 송신자가 수신자의 버퍼를 오버플로우 시키는 것을 방지하도록 하는 것
TCP 흐름 제어 전송량이 너무 많고 송신 속도가 빠른 경우, 송신자가 수신자의 버퍼를 오버플로우 시키는 것을 방지하도록 하는 것 flow control (TCP 수신자가 순서가 맞지 않는 세그먼트를 버린다고 가정한다.) 버퍼에서 여분의 공간 = RcvWindow = RcvBuffer-[LastByteRcvd - LastByteRead] LastByteRead : app. 프로세스에 의해서 버퍼로부터 읽혀진 데이터 스트림의 마지막 바이트 수 LastByteRcvd : 네트워크로 부터 도착하여 수신버퍼에 저장된 데이터 스트림의 마지막 바이트 수 LastByteRcvd – LastByteRead <= RcvBuffer : 버퍼오버플로우를 허용하지 않을 조건 TCP의 수신 측은 수신버퍼를 갖는다. app. 프로세스가 버퍼로부터 데이터를 느린 속도로 읽는다고 가정한다. 속도를 일치시키는 서비스: 송신속도와 app.의 데이터를 읽는 속도를 같게 하는 서비스가 흐름제어 서비스이다. Transport Layer

28 TCP 흐름 제어 수신자는 세그먼트안의 수신자윈도우 필드에 값을 설정하여 송신자에게 버퍼의 여유공간을 알려준다.
송신자는 수신자윈도우값보다 작은 확인응답 안된 데이터의 양을 유지하여 수신자 버퍼 오버플로우를 방지한다. 수신 측 버퍼의 오버플로우 방지 조건 LastByteSent – LastByteAcked <= RcvWindow 흐름제어의 문제점 TCP는 전송할 데이터가 있거나, 전송해야 할 응답이 있는 경우에만 세그먼트를 전송한다. 따라서, 수신 측이 송신 측에게 전송할 데이터나 확인응답이 없는 경우 수신윈도우의 변동사항을 송신 측에게 알릴 수 없다. (수신윈도우가 0인 경우) 수신윈도우가 0인 경우 수신자가 1바이트 데이터로 세그먼트를 계속해서 전송하도록 요구하고, 결국에는 수신윈도우가 0이 아닌 값이 전송되어 송신이 재개된다. Transport Layer

29 TCP 연결 관리 Three way handshake:
Step 1: client는 server에게 헤더의 SYN 비트를 1로 설정한 SYN 세그먼트를 송신한다. 순서번호를 초기화 app. 계층 데이터를 포함하지 않는다. Step 2: server는 SYN 세그먼트를 수신하고, SYNACK 세그먼트로 응답한다. server는 연결에 TCP 변수와 버퍼를 할당한다. 수신 측 순서번호를 초기화 Step 3: client는 SYNACK를 수신하고, 버퍼와 변수를 할당한 후, server에게 app. 계층 데이터가 포함된 ACK를 송신한다. TCP 송신자와 수신자는 데이터 세그먼트 교환 전에 연결을 설정해야 한다. TCP 변수 초기화: 순서번호 버퍼, 흐름제어 정보 (예. RcvWindow) client: 연결 초기화 요청 Socket clientSocket = new Socket("hostname","port number"); server: 클라이언트에 의해서 연결 설정 Socket connectionSocket = welcomeSocket.accept(); Transport Layer

30 TCP 연결 관리- Three way handshake:
client 1 단계: 클라이언트 호스트가 TCP SYN 세그먼트를 서버로 송신 초기 순서번호 명시 데이터 없음 2 단계: 서버 호스트 SYN 세그먼트 수신하고, SYNACK 세그먼트로 응답 서버 버퍼를 할당 서버의 초기 순서번호 명시 3단계: 송시자는 SYNACK 세그먼트 수신하고, ACK세그먼트로 응답하되, 데이터를 포함시킬수 있다. server 연결요청 SYN=1, seq=100 연결 허락 SYN=1, seq=200, ack=101 ACK SYN=0, seq=101, ack=201 (데이터) Transport Layer

31 TCP 연결 관리 연결 종료: Step 1: 클라이언트는 TCP FIN 제어 세그먼트를 server에게 보낸다.
client closes socket: clientSocket.close(); Step 1: 클라이언트는 TCP FIN 제어 세그먼트를 server에게 보낸다. Step 2: 서버는 FIN을 받고, 클라이언트에게 ACK로 응답하고 수신 쪽 연결을 종료. 연결 종료를 위한 FIN을 클라이언트에게 보낸다. Step 3: 클라이언트는 서버의 FIN 세그먼트에 확인 응답을 하고, 대기 시간 후에 두 호스트의 모든 자원들은 할당이 해제된다. client FIN server ACK close closed timed wait Transport Layer