한동대학교/Computer Networking

[컴퓨터 네트워크] Chapter 3. Transport Layer (Part2) - (2)

pangil_kim 2025. 6. 27. 14:13
728x90

일자 : 24-2 7주차 2차시

[10] Performance of rdt3.0 (stop-and-wait)

  • U sender: utilization – fraction of time sender busy sending
  • example: 1 Gbps link, 15 ms prop. delay, 8000 bit packet
    • time to transmit packet into channel
      $D_{trans}$ = $L\over R$ = $8000bits\over 10^9bits/sec$ = 8 microsecs

[11] rdt3.0: Stop-and-Wait 동작

1) 기본 동작

1-1. 첫 번째 패킷 비트 전송, t = 0

  • 송신자가 첫 번째 패킷을 전송하며 시간은 0이 됨.

1-2. 첫 번째 패킷 비트 도착

  • 수신자가 첫 번째 패킷을 받음.

2-1. 마지막 패킷 비트 도착, ACK 전송

  • 수신자가 마지막 패킷 비트를 받은 후, 송신자에게 ACK(응답)를 전송.

2-2. ACK 도착, 다음 패킷 전송, t = RTT + L/R

  • 송신자가 ACK을 받은 후, 다음 패킷을 전송하고, 시간은 왕복 전송 시간(RTT)과 전송 대역폭(L/R)을 합친 값으로 계산됨.

2) 문제점 분석

  • rdt 3.0 프로토콜은 성능이 떨어진다!

    • rdt 3.0 프로토콜은 패킷 전송 속도가 낮고, 지연 시간이 길어 성능이 제한적이다.

  • 프로토콜은 하위 인프라(채널)의 성능을 제한한다.

    • Stop-and-Wait 프로토콜은 송수신 사이의 대기 시간 때문에 네트워크 채널의 효율적인 활용을 제한한다.

[12] rdt3.0: 파이프라인 프로토콜 작동

  • 파이프라이닝(pipelining): 송신자가 여러 개의 패킷을 "비행 중(in-flight)" 상태로 전송하고, 아직 ACK(응답)를 받지 않은 상태에서 계속 전송하는 방식
    • 이 경우 시퀀스 번호 범위를 확장해야 한다.
    • 송신자 또는 수신자 측에서 버퍼링이 필요하다.
    • 파이프라이닝은 송신자가 여러 개의 패킷을 전송한 후, ACK를 기다리는 대신 동시에 여러 패킷을 보내는 방식이다. 이는 네트워크의 대기 시간을 줄이고, 성능을 향상시킬 수 있다. 송신자는 ACK를 기다리지 않고 패킷을 전송하며, 패킷들이 "비행 중"인 상태로 네트워크를 통해 전송된다.
  • 2가지 방법
    1. 정지-대기(stop-and-wait) 프로토콜: 한 번에 하나의 패킷만 보내고 ACK를 기다리는 방식.
      • 이 방식은 단순하지만 대기 시간이 길어질 수 있다.
    2. 파이프라인 프로토콜: 여러 개의 패킷을 동시에 보내고, ACK를 기다리지 않고 계속해서 다음 패킷을 보내는 방식.

[13] 파이프라이닝: 증가된 활용도 (utilization)

1) 과정

1-1. 첫 번째 패킷 비트 전송, t = 0

  • 송신자가 첫 번째 패킷을 전송하며 시간은 0이 됨.

1-2. 첫 번째 패킷 비트 도착

  • 수신자가 첫 번째 패킷을 받음.

1-3. ACK 도착, 다음 패킷 전송, t = RTT + L/R

  • 송신자가 ACK를 받고, 다음 패킷을 전송하며 시간은 RTT + L/R임.

2-1. 마지막 비트 전송 완료, t = L / R

  • 첫 번째 패킷의 마지막 비트가 전송됨.

2-2. 마지막 패킷 비트 도착, ACK 전송

  • 수신자가 첫 번째 패킷의 마지막 비트를 수신하고, ACK를 송신자에게 보냄.

3-2. 두 번째 패킷의 마지막 비트 도착, ACK 전송

  • 수신자가 두 번째 패킷의 마지막 비트를 수신하고, ACK를 송신자에게 보냄.

4-2. 세 번째 패킷의 마지막 비트 도착, ACK 전송

  • 수신자가 세 번째 패킷의 마지막 비트를 수신하고, ACK를 송신자에게 보냄.

2) 결과

  • 3개의 패킷 파이프라이닝을 통해 활용도가 3배로 증가!

[14-1] Go-Back-N: 송신자

  • 송신자: 최대 N개의 연속된 전송 완료 후 ACK를 받지 않은 패킷들로 구성된 "윈도우"
    • 패킷 헤더에 k-비트 시퀀스 번호 포함

  • 누적(cumulative) ACK: ACK(n)은 시퀀스 번호 n까지 포함하여 모든 패킷을 ACK함
    • ACK(n)을 수신할 때, 윈도우를 n+1로 이동
  • 가장 오래된 전송 중인 패킷에 대한 타이머
  • timeout(n): 패킷 n 및 윈도우 내의 모든 높은 시퀀스 번호 패킷을 재전송

[14-2] Go-Back-N: 송신자 확장 FSM

  1. 패킷 전송
    • rdt_send(data)는 전송할 데이터가 있을 때 호출됨.
    • nextseqnum < base+N 조건을 만족하는 경우 패킷을 만들어 전송.
    • 첫 번째 패킷 전송 시 타이머 시작.
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)  // 윈도우 범위를 초과하면 데이터 전송 거부
  1. 타임아웃 발생 시 재전송
    • 타임아웃이 발생하면 현재 윈도우에 있는 모든 패킷을 재전송.
timeout

start_timer
udt_send(sndpkt[base])  // base부터 시작하여 모든 패킷을 재전송
udt_send(sndpkt[base + 1])
udt_send(sndpkt[base + 2])
...
udt_send(sndpkt[nextseqnum - 1])
  1. ACK 수신
    • ACK를 받으면 base 값을 갱신하고 타이머 조정.
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

base = getacknum(rcvpkt) + 1  // ACK 수신 후 base 업데이트
if (base == nextseqnum)
    stop_timer  // 모든 패킷이 ACK되면 타이머 정지
else
    start_timer  // 일부 패킷만 ACK된 경우 타이머 재시작
  1. 손상된 ACK 수신
    • ACK가 손상된 경우, 아무 작업도 하지 않음.
rdt_rcv(rcvpkt) && corrupt(rcvpkt)
  1. 초기화
    • 전송 과정 초기화, 시퀀스 번호를 1로 설정.
base = 1
nextseqnum = 1

[14-3] Go-Back-N: 수신자

  • ACK 전송만: 수신자는 올바르게 수신한 패킷에 대해 항상 ACK를 전송 (최신 시퀀스 번호 사용)
    • 중복 ACK 생성 가능
    • 수신자는 rcv_base만 기억하면 됨.
  • 순서가 맞지 않는 패킷 수신 시:
    • 폐기하거나 버퍼링 가능: 이는 구현에 따라 다름.
    • 최신 순서의 패킷을 ACK로 재전송할 수 있음.

[14-4] Go-Back-N: 수신자 확장 FSM

  1. 다른 이벤트
    • 다른 이벤트가 발생한 경우, ACK 패킷 전송.
any other event

udt_send(sndpkt)
  1. 올바른 패킷 수신
    • 순서가 맞는 패킷을 수신하면 데이터를 전달하고 ACK 전송.
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && hasseqnum(rcvpkt, expectedseqnum)

extract(rcvpkt, data)  // 데이터 추출
deliver_data(data)  // 데이터 전달
sndpkt = make_pkt(expectedseqnum, ACK, checksum)  // ACK 패킷 생성
udt_send(sndpkt)  // ACK 전송
expectedseqnum++
  1. 초기화
    • 기대되는 시퀀스 번호를 1로 설정하고 첫 ACK 생성.
expectedseqnum = 1
sndpkt = make_pkt(0, ACK, checksum)

[15] Go-Back-N 작동 예시

[16] 선택적 재전송 (Selective Repeat)

  • 수신자는 모든 올바르게 수신된 패킷을 개별적으로(individually) ACK 전송
    • 상위 계층에 순서대로 전달할 수 있도록 필요한 경우 패킷을 버퍼에 저장함.
  • 송신자는 ACK를 받지 못한 패킷을 개별적으로 타임아웃 및 재전송
    • 송신자는 ACK를 받지 못한 각 패킷에 대해 개별 타이머를 유지함.
  • 송신자 윈도우
    • 연속된 N개의 시퀀스 번호 포함
    • 전송되었지만 ACK를 받지 못한 패킷의 시퀀스 번호 제한

Selective Repeat 프로토콜은 Go-Back-N과 달리, 손실된 특정 패킷만 재전송함으로써 네트워크 효율성을 높이고 불필요한 패킷 재전송을 줄이는 방식이다.

[17-1] Selective repeat : sender, receiver windows

Selective Repeat의 sender와 receiver 윈도우에 대해 정리하겠습니다:

1) Sender View (송신자 관점)

  • 윈도우 크기: N
  • 주요 구성요소:
    • send_base: 윈도우의 시작점
    • nextseqnum: 다음 전송할 시퀀스 번호
  • 패킷 상태 표시:
    • 초록색: 이미 ACK 받은 패킷
    • 노란색: 전송했으나 아직 ACK를 받지 않은 패킷
    • 파란색: 아직 전송하지 않은 사용 가능한 패킷
    • 흰색: 사용할 수 없는 시퀀스 번호

2) Receiver View (수신자 관점)

  • 윈도우 크기: N
  • 주요 구성요소:
    • rcv_base: 수신 윈도우의 시작점
  • 패킷 상태 표시:
    • 초록색: 이미 ACK를 보낸 패킷
    • 분홍색: 순서가 맞지 않지만 버퍼에 저장된 패킷
    • 회색: 예상되는 패킷이지만 아직 수신하지 않음
    • 파란색: 수신 가능한 윈도우 내의 패킷
    • 흰색: 사용할 수 없는 시퀀스 번호

3) 주요 특징:

  1. SR(Selective Repeat)은 개별 패킷에 대한 ACK를 사용
  2. 수신자는 순서가 맞지 않는 패킷도 버퍼에 저장 가능
  3. 윈도우 크기(N)는 sender와 receiver 모두 동일
  4. 순서대로 처리되지 않은 패킷도 개별적으로 관리 가능

[17-2] Selective repeat : 송신자와 수신자 윈도우

1) 송신자 (Sender)

  • 상위 계층으로부터 데이터 수신:
    • 윈도우 내에서 사용할 수 있는 다음 시퀀스 번호가 있으면 패킷을 전송합니다.
  • 타임아웃(timeout(n)):
    • 패킷 n을 재전송하고 타이머를 재시작합니다.
  • ACK(n)가 [sendbase, sendbase+N] 내에 있을 때:
    • 패킷 n을 수신됨으로 표시합니다.
    • n이 ACK를 받지 못한 가장 작은 패킷인 경우, 윈도우의 베이스를 다음 ACK되지 않은 시퀀스 번호로 이동합니다.

2) 수신자 (Receiver)

  • 패킷 n이 [rcvbase, rcvbase+N-1] 내에 있을 때:
    • ACK(n)을 송신합니다.
    • 순서가 어긋난 경우: 패킷을 버퍼에 저장합니다.
    • 순서대로 도착한 경우: 데이터를 전달하며, 순서대로 버퍼에 있는 패킷도 함께 전달하고, 아직 수신하지 않은 다음 패킷으로 윈도우를 이동합니다.
  • 패킷 n이 [rcvbase-N, rcvbase-1] 내에 있을 때:
    • ACK(n)을 송신합니다.
  • 그 외의 경우:
    • 패킷을 무시합니다.

Selective Repeat에서 송신자와 수신자는 각 패킷에 대한 개별 ACK를 관리하고, 필요한 경우 특정 패킷만 재전송하여 효율성을 높입니다.

[18] Selective Repeat in action

[19] Selective repeat: a dilemma!

1) 기본 설정:

  • 시퀀스 번호: 0, 1, 2, 3 (4진수 카운팅)
  • 윈도우 크기: 3

2) 문제 없는 상황 (no problem)

  • 송신자가 pkt0, pkt1, pkt2, pkt3을 순차적으로 전송
  • pkt3이 손실되었지만, 나머지 패킷들은 정상적으로 수신
  • 수신자는 pkt0, pkt1, pkt2를 순서대로 받고 ACK 전송
  • 새로운 pkt0이 도착하면 수신자는 정상적으로 수락 가능
  • 송신자와 수신자의 윈도우가 동기화되어 있어 문제 발생하지 않음
송신자: "자, 패킷 0, 1, 2, 3을 순서대로 보낼게!"
수신자: "OK! 0번 받았어, 1번 받았어, 2번 받았어! (3번은 유실)"
      "새로운 0번이 오면 받을 준비가 되어있어!"

3) 문제 발생 상황 (oops!)

  • 송신자가 pkt0, pkt1, pkt2를 전송
  • 모든 패킷과 ACK가 손실됨
  • 타임아웃 발생으로 송신자가 pkt0을 재전송
  • 문제 발생: 수신자가 이전 윈도우의 pkt0인지 새로운 윈도우의 pkt0인지 구분할 수 없음
  • 시퀀스 번호 공간이 작아서(4) 윈도우 크기(3)와 충돌 발생
송신자: "자, 패킷 0, 1, 2를 보낼게!"
(안타깝게도 모든 패킷이 유실됨)
송신자: "어? 응답이 없네. 그럼 0번부터 다시 보낼게!"

수신자: "어라? 이 0번 패킷이... 
       아까 못 받은 첫 번째 0번일까?
       아니면 새로운 라운드의 0번일까?"
       (혼란스러움 발생!)

주요 시사점:

  • 시퀀스 번호 공간은 윈도우 크기의 2배 이상이어야 함
  • 이 예시에서는 윈도우 크기가 3이므로 시퀀스 번호는 최소 6개 이상 필요
  • 현재 4개의 시퀀스 번호로는 패킷의 고유성을 보장할 수 없음

  1. 문제 상황:
  • 수신자(receiver)는 송신자(sender) 쪽의 상황을 볼 수 없음
  • 두 가지 다른 상황에서 수신자의 동작이 동일하게 나타남
  • 수신자는 시퀀스 번호 0인 패킷을 수신할 예정
  1. 특징:
  • 두 시나리오에서 보이는 윈도우 패턴:
    • 0 1 2 3 0 1 2
    • 수신자 입장에서는 동일한 패턴으로 보임

Q. 시나리오 (b)에서 문제를 피하기 위해 시퀀스 번호의 크기와 윈도우 크기 사이에 어떤 관계가 필요한지?
A. 시나리오 (b)의 문제를 피하기 위해서는 시퀀스 번호의 크기(N)와 윈도우 크기(W) 사이에 다음과 같은 관계가 필요하다
-> N > 2W
여기서는 시퀀스 번호가 0,1,2,3으로 N=4이고, 윈도우 크기가 W=3이다.
이 경우 4 > 2(3) = 6이 성립하지 않기 때문에 문제가 발생한다.

[20] Reliable Data Transfer Protocol: 1.0 ~ Selective Repeat

신뢰성 데이터 전송 프로토콜: 1.0 ~ 선택적 재전송

RDT 버전 문제점 해결 방안
1.0 완벽하게 신뢰할 수 있는 채널 없음
2.0 채널에 비트 오류 발생 (패킷 비트 뒤집힘) ACK와 NAK 사용, NAK 수신 시 송신자가 패킷을 재전송
2.1 채널에 비트 오류 발생
ACK/NAK이 손상되면?		 ACK/NAK이 손상된 경우 현재 패킷 재전송
송신자가 각 패킷에 시퀀스 번호 추가
수신자가 중복 패킷을 무시
2.2 채널에 비트 오류 발생
NAK 없이 프로토콜 구성 필요		 NAK 대신, 수신자가 마지막으로 수신한 패킷에 대해 ACK 전송
3.0 오류와 손실이 있는 채널 송신자가 "합리적인" 시간 동안 ACK를 기다림, ACK가 없을 시 재전송
Go-back-N 정지-대기 동작으로 인한 네트워크 활용도 저하 송신자가 여러 개의 "비행 중인"(아직 ACK되지 않은) 패킷을 허용
누적 ACK 사용
Selective Repeat Go-back-N 방식에서는 여러 개의 연속된 패킷이 재전송되며, 수신자가 일부 패킷을 이미 수신한 경우에도 해당 패킷들을 재전송 수신자가 올바르게 수신된 각 패킷에 대해 개별적으로 ACK를 보냄

728x90