9. 슬라이딩 윈도우 (Sliding-Window)

슬라이딩 윈도우 (Sliding Window)

• 이디어: 송신자가 ACK를 받기 전에 여러 개의 프레임을 전송할 수 있도록 한다 → 파이프가 꽉 차게 된다.
• ACK를 받지 않은 상태에서 보내지는 프레임 (outstanding frame)이 복수개로 늘어난다. 그 수는 window size에 맞게 제한된다.
  • outstanding frame: 현재 전송이 진행중인 frame = 언제든지 오류 복구가 필요한 frame
  • 모두 오류 제어 대상이며, 순서 번호가 필요하다. (누가 ACK를 보냈는지 구분하기 위해)
  • stop&wait는 sliding window의 window size가 1인 경우이다.
• 각각의 프레임에 대해서는 ARQ, 즉 Ack / timeout & 재전송을 수행한다.
• 효율 높은 오류 제어가 가능하다. (효율은 부가적이고 중요한 것은 오류제어)
  • 버퍼링보다 오류가 핵심이다.

Sliding Window Protocol의 성능

• 윈도우 크기 N이 충분히 크면, 효율은 1이 된다.
• Ack가 올때까지 윈도우가 모두 소진되지 않으면 기다리는 시간 없이 100% 통신 가능하다.

시간 진행 표시법 및 해석

• 성능 분석이 목적인 경우 Sliding window 그리기
• 시간 상황이 겹치는 세부 사항 분석이 필요할 경우 축약형 그리기

Sliding Window 개념: 오류 없는 경우

• 보낸 Frame들은 재전송을 위해 버퍼링이 필요하다.
• 보낸 Frame에 대한 ACK 가 돌아온다면 (여기서는 누적 ACK) 해당 Frame들의 버퍼를 해제한다.

슬라이딩 윈도우의 오류 복구

• 복수의 outstanding frame 중 어떤 프레임에서도 오류 발생 가능 → 모든 프레임은 개별적으로 재전송 준비 (버퍼+타임아웃) 되어야 한다.
• 오류 처리 정책
  • Go-Back-N: 오류 발생한 지점부터 새 출발
  • Selective-Repeat: 오류 발생한 프레임만 재전송
• Selective-Repeat에서는 누적 ACK를 사용하기 곤란하다.
  • 어떤 Frame에서 Error가 났는지 구체적으로 알기 힘들기 때문에 개별 ACK가 필요하다.

다른 오류 복구 정책의 상호 운영성

• 송신쪽과 수신쪽이 서로 다른 오류 정책을 사용하면 연동이 가능할까?

→ 상대방과 세부 정책이 달라도 통신 가능하다. 더 간단한 쪽에 맞춘다. but 효율은 낮다.

• 개별 오류 정책의 목적: 오류 복구
  • 복구 효율은 다음 문제이다.
  • 오류 복구만 된다면 연동이 가능하다고 보면 된다.

Ex.

송신 - Sliding window, Go-Back-N / 수신 - stop & wait → stop&wait에 맞춘다.

송신 - stop & wait / 수신 - sliding window, Go-Back-N → stop & wait 에 맞춘다.

송신 - sliding window, Go-Back-N / 수신 - Selective Repeat → Go-Back-N

Go-Back-N (구현) 옵션

• 수신 쪽에서 out-of-order 프레임을 어떻게 처리하는 가에 따라서
  • ACK를 보낼 것인가? (”~까지” 라는 누적 ACK 개념 유지)
  • 도착한 Frame을 저장할 것인가?
  → 수업에서는 저장하고, ACK는 안 보내는 방식 사용
• 송신쪽은 동일하게 동작
  • 각 outstanding 프레임에 대해
    • 재전송 버퍼에 저장; 타임아웃 설정
  • 오류 발생 인지 후 (타임아웃이 발생할 때)
    • 모든 outstanding frame을 동시 전송할지, 각 frame의 타임아웃 발생시에 순차적으로 전송할지는 송신측의 선택 사항이다.
  • 어떤 옵션으로 구현되어도 오류 복구 가능하다.

오류 처리 정책: Go-Back-N 재검토

• 오류 발생한 N부터 다시 출발하는 것
• “~까지 잘 받았고, 다음은 *번”이라는 의미의 ACK 사용
• ACK를 보내는 시점은 수신자의 선택
• 진행을 돕기 위해 ACK를 보낸다면 중복 ACK만 가능하다.
• 수신쪽의 버퍼링은 수신자가 독립적으로 결정한다.
  • 버퍼링은 안 해도 되지만 교재에서는 버퍼를 유지하면서 순서가 바뀐 데이터를 수신한다고 가정한다.

오류 처리 : Selective-Repeat

• 필요 조건
  • 수신 쪽은 out-of-order 프레임 수신하고, 버퍼링이 필수이다.
  • 수신쪽의 정확한 수신 상황 정보를 송신쪽으로 알려주어야 한다.
    • “~은 잘 받았다”라는 뜻의 개별/선택 ACK 가 필수적이다.
    • 누적 ACK는 사용하지 않는다.

Sliding Window 세부사항

• 중요한 것 : 수신자가 out-of-order 를 저장한다고 (버퍼링) Selective-Repeat은 아니다. Go-Back-N에서도 충분히 사용될 수 있다.

프로토콜의 구현

• 오류제어 이전까지는 Adaptor (NIC)에서 하드웨어로 구현했다.
• 오류제어는 소프트웨어로 구현되는 첫 프로토콜
• 소프트웨어에서만 처리 가능하다.
• 송수신 양쪽을 보는 것은 이론적 설명에서만 가능하다.
  • 실제로는 송수신 각각이 독립적으로 동작하기 때문에 프로토콜의 동작에 대해 확실한 이해가 필요하다.
  • 특히 비정상 상황에 대한 이해가 중요하다.
• 구현 난이도는 생각보다 높은 편이다.
  • concurrent and distributed program
  • 설계 과정이 절대적으로 필요하다.

Go-Back-N의 구현

• 송신/수신쪽이 독립적으로 동작 → Event-driven 개발 방식이 사용된다.
• 송신쪽 동작
  • 오류제어 : 각 outstanding frame에 대해
    • 재전송 버퍼에 저장하고 타임아웃을 설정한다.
    • 오류 없을 때 ACK를 받으면 타임아웃을 해제하고, 재전송 버퍼를 해제한다. 버퍼가 해제된 만큼 뒤에 frame을 보낼 수 있게 된다.
    • 타임아웃이 발생하면 재전송한다.
  • 버퍼 + 윈도우 관리 (semaphore 이용)
• 수신쪽 동작
  • 오류 제어 : 제대로 왔을 때 누적 ACK 전송 → 오류 제어 핵심은 ACK를 보내는 것이다.
  • 버퍼 관리 : out-of-order 프레임을 저장(버퍼링)은 하고, ACK는 따로 보내지 않는 형식

슬라이딩윈도우 (GoBackN) 세부 알고리즘(1)

• 송신자
  • 각 프레임에 순서 번호를 할당 (SeqNum_ : 각 outstanding frame의 ID
  • 세 개의 상태 변수를 유지
    • 송신창: send window size (SWS)
    • 마지막으로 받은 ACK의 프레임 번호: Last ACK received (LAR) → LAR은 다음에 보내야 할 프레임의 번호를 의미한다. (ACK 4는 3까지 잘 받았고, 다음은 Frame 4를 보내달라는 뜻)
    • 마지막으로 보낸 프레임 번호: Last Frame Sent (LFS)
  • LFS - LAR + 1 ≤ SWS
    • 누적 ACK라서 LAR이 한 번에 LFS 보다 커질 수 있다.
    • LAR 뒤: 이미 ACK를 받은 프레임들. outstanding frame 아님.
    • LFS 앞: 아직 보내지 않은 프레임들. outstanding frame 아님
    • LAR ≤ x ≤ LFS: outstanding frame (재전송이 필요할 수 있는 프레임들)
• 상위 계층에서 전송 요청을 받으면 LFS를 증가시키고 (LFS 증가가 불가능하면 Wait) 타임아웃을 설정한 후 프레임을 전송한다.
  • 논리적으로는 peer에게 전송하는 것
  • 실질적으로는 하위 계층에 send down 하는 것
• ACK를 받으면 타임아웃을 해제하고, LAR을 증가시키며 이에 따라 새롭게 창이 열리며 전송이 가능해진다. (outstanding frame들이 해제되었으니 새로운 frame들을 보낼 수 있게 된다.)
• 타임아웃이 걸리면 타임아웃을 설정한 후 프레임을 재전송한다.
• SWS 만큼의 프레임은 버퍼에 유지한다. → 재전송에 필요

슬라이딩 윈도우(GoBackN) 세부 알고리즘(2)

• 수신자
  • Out-of-order 프레임을 저장하는 GoBackN 알고리즘
  • 세 개의 상태 변수를 유지
    • 수신창: receive window size (RWS) - SWS와 같을 필요는 없다.
    • 받아들일 수 있는 마지막 프레임: Last Frame Acceptable (LFA)
    • 수신 예상 프레임(앞으로 받아야 할 frame 숫자): Next Frame Expected (NFE)
  • LFA - NFE + 1 ≤ RWS
• SeqNum의 프레임이 도착하면
  • if NFE ≤ SeqNum ≤ LFA → Accept
    • 중간에 빈 곳 없는 연속되는 데이터들은 상위 계층으로 deliver 한다.
    • NFE 이전 값들은 모두 deliver된다.
  • if SeqNum < NFE or SeqNum > LFA → 버림 (discard)
    • SeqNum < NFE는 ACK 전송 필요하다.
    • ACK 안 보내면 송신측에서 ACK 받을 때까지 계속 재전송하게 된다.
  • 누적 ACK를 보낸다. (NFE 값과 동일)