[Network] 파이프라이닝 오류 회복 방법 - GBN,SR 정리

---

GBN(Go-Back-N, N부터 반복) 프로토콜

• 프로토콜 이름은 손실이 있거나 아주 긴 지연된 패킷이 있을 때의 송신자 동작으로부터 유래됨
• 해당 프로토콜에서 송신자는 확인응답을 기다리지 않고 여러 패킷을 전송할 수 있다.
• 파이프라인에서 확인응답이 안 된 패킷의 최대 허용 수 N보다 크면 안 된다.
• GBN 프로토콜의 사용으로 송신자는 패킷으로 파이프라인을 채우는 것이 가능해짐

 

---

송신자 관점의 순서 번호 범위

• base : 확인응답이 안 된 가장 오래된 패킷의 순서 번호
• nextseqnum : 사용되지 않은 가장 작은 순서 번호
  • 전송될 다음 패킷의 순서 번호

 

4가지 순서 번호 범위

• 간격 [0, base-1]
  • 순서 번호는 이미 전송되고 확인응답된 패킷에 대응된다.
    
    
• 간격 [base, nextseqnum-1]
  • 송신은 되었지만 아직 확인응답되지 않은 패킷에 대응
    
    
• 간격 [nextseqnum, base+N-1]
  • 상위 계층으로부터 데이터가 도착하면 바로 전송될 수 있는 패킷을 위해 사용
    
    
• base+N 이상의 순서 번호
  • 파이프라인에서 확인응답이 안 된 패킷의 확인응답이 도착할 때까지 사용될 수 없음
    • 확인응답이 안 된 패킷 → 순서 번호 base를 가진 패킷

 

슬라이딩 윈도 프로토콜(sliding-window protocol)

• GBN 프로토콜은 슬라이딩 윈도 프로토콜이라고 부름
• 윈도 크기(window size), N
  • 전송됐지만 아직 확인응답이 안 된 패킷을 위해 허용할 수 있는 순서 번호의 범위 상의 크기
  • 프로토콜이 동작할 때, 이 윈도는 순서 번호 공간에서 오른쪽으로 이동(slide)한다.
    → 슬라이딩 윈도 프로토콜이라고 불리는 이유

 

패킷의 순서 번호

• 패킷의 순서 번호는 패킷 헤더 안의 고정된 길이 필드에 포함된다.
• k가 패킷 순서 번호 필드의 비트 수인 경우의 순서 번호의 범위 → [0,2^k-1]
• 순서 번호를 포함하는 모든 계산은 모듈로 2^k 연산을 이용한다.
  • 이는 링처럼 구성됨(순서 번호 2^k-1 다음에 0이 온다.)

 

---

GBN 프로토콜의 확장된 FSM

• ACK 기반의 NAK 없는 GBN 프로토콜의 송신 측과 수신 측
• GBN 프로토콜은 TCP의 신뢰적인 데이터 전송 구성요소를 다룰 때의 기술이 통합됨

 

확장된 FSM인 이유

• FSM에 base와 nextseqnum 변수를 추가
• 위의 변수에서의 동작과 변수를 포함하는 조건부 동작을 추가
• 송신자는 윈도 상위와 하위 경계와 윈도 안에 있는 nextseqnum 위치를 유지해야 한다.

 

GBN 송신자 - 세 가지 이벤트 타입에 반응

GBN 송신자의 확장된 FSM

 

• 상위로부터의 호출
  • rdt_send()가 위로부터 호출되면, 송신자는 우선 윈도가 가득 찾는지 확인
    → 즉, N개의 아직 확인응답되지 않은 패킷이 있는지 확인
    • 윈도가 가득 차 있지 않은 경우
      • 패킷이 생성 및 송신되고, 변수들이 적절하게 갱신된다.
        
        
    • 윈도가 가득 차있는 경우
      • 송신자는 단지 데이터를 상위 계층으로 반환
        → 윈도가 가득 차 있다는 함축적 의미를 상위 계층에 전달
        
        
      • 이후, 상위 계층은 나중 다시 시도함
        
        
    • 실제적인 구현에서는 rdt_send()를 호출할 때의 동기화 메커니즘을 사용
      • rdt_send()를 호출하는 경우
        • 송신자가 이 데이터를 버퍼링 하는 경우
        • 윈도가 가득 차 있지 않을 때
          
          
      • 예시 : 세마포어, 플래그

 

• ACK의 수신
  • GBN 프로토콜에서 순서 번호 n을 가진 패킷에 대한 확인응답은 누적 확인 응답으로 인식
    • 누적 확인 응답 : n까지의 순서 번호를 가진 모든 패킷에 대한 확인 응답
      • 수신 측에서 올바르게 수신된 n을 포함한다.
        
        
• 타임아웃 이벤트
  • 타이머는 손실된 데이터 또는 손실된 확인응답 패킷으로부터 회복하는 데 사용
    • 전송 후 대기 프로토콜과 유사
      
      
  • 타임 아웃 발생 시의 송신자의 행동
    → 이전에 전송되었지만 아직 확인응답되지 않은 모든 패킷을 다시 송신
    
    
  • 그림에서 가장 오래된 전송 했지만, 아직 확인응답 안 된 패킷에 대한 단일 타이머를 사용
    • ACK가 수신되었지만 전송했지만 아직 확인응답 안 된 패킷이 존재하는 경우
      → 타이머는 다시 시작됨
      
      
    • 아직 확인응답 안 된 패킷이 없는 경우 → 타이머는 멈춘다.

 

GBN 수신자

GBN 수신자의 확장된 FSM

• 순서 번호 n을 가진 패킷이 오류 없이 순서대로 수신되는 경우
  (상위 계층에 마지막으로 전달된 데이터가 순서 번호 n-1을 가진 패킷에서 온 것인 경우)
  → 수신자는 패킷 n에 대한 ACK를 송신하고 상위 계층에 패킷의 데이터 부분을 전달
  • 패킷 k가 수신되고 상위 계층에게 전달됐다면,
    이미 k보다 낮은 순서 번호를 가진 패킷 또한 전달된 상태임
    
    → 누적 확인응답을 사용하는 것은 GBN을 위한 자연스러운 선택
    
    
• 그 외의 경우
  → 그 패킷을 버리고 가장 최근에 제대로 수신된 순서의 패킷에 대한 ACK를 재전송
  
  
• 수신자가 순서가 잘못된 패킷들을 버리는 이유
  • 패킷 n이 수신되어야 하지만, 다음 패킷인 n+1이 먼저 도착한 경우
    1. 데이터가 순서대로 전달되어야 하므로, 수신자는 패킷 n+1을 저장
    2. 나중에 n이 수신되고 전달된 후에 상위 계층에 이 패킷을 전달한다.
       • 이 과정에서 패킷 n이 손실된다면?
         → GBN 재전송 규칙에 따라 패킷 n과 n+1이 모두 재전송될 것
         
         
  • 수신자 버퍼링이 간단해진다.
    → 수신자는 어떤 순서가 잘못된 패킷에 대해 버퍼링 할 필요가 없다.
    
    
• 수신자는 다음 순서 패킷의 순서 번호를 유지해야 한다.
  • 위 그림에서 expectedseqnum 변수에서 유지된다.
  • 패킷을 버리는 것의 단점은 그 패킷의 재전송이 손실되거나 왜곡될 수 있다.
    → 많은 재전송이 필요할 수도 있다는 것

 

---

GBN 프로토콜의 동작

• 윈도 크기가 4 패킷인 경우에 대한 GBN 프로토콜의 동작을 보여줌
  • 윈도 크기 제한으로 인해 패킷 0 ~ 3까지 송신한다.

GBN에서의 동작

1. 송신을 계속하기 전에 하나 이상의 패킷이 긍정 확인응답되는 것을 기다려야 함
2. 각각의 성공적인 ACK(여기서는 ACK0, ACK1)가 수신
   → 윈도는 앞으로 이동하고 송신자는 하나의 새로운 패킷(각각 pkt4, pkt5)을 전송
   
   
3. 패킷 2(pkt2)가 손실됨
   → 수신 측에서는 패킷 3,4,5는 순서가 잘못된 패킷으로 발견돼서 제거

 

이벤트 기반 프로그래밍(event-based programming)

• 정의 : 다양한 이벤트에 대한 대응으로 취할 수 있는 동작을 구현하는 다양한 절차
• 이벤트 기반 프로그래밍 프로시저들은 다른 프로시저에 의해 야기, 혹은 인터럽트의 결과로 요청됨
• 송신자에서 이러한 이벤트
  • rdt_send()를 호출하기 위한 상위 계층 개체로부터의 호출
  • 타이머 인터럽트
  • 패킷이 도착했을 때 rdt_rcv()를 호출하기 위한 하위 계층으로부터의 호출

 

---

GBN 프로토콜 자체의 성능 이슈

• 윈도 크기와 대역폭 지역곱의 결과가 모두 큰 경우, 많은 패킷이 파이프라인에 있을 수 있다.
  • GBN은 패킷 하나의 오류 때문은 많은 패킷을 재전송한다.
    → 많은 패킷을 불필요하게 재전송하는 경우가 발생
    → 채널 오류의 확률이 증가할수록 파이프라인은 불필요한 재전송 데이터로 채워짐

 

 

---

SR(Selective Repeat, SR)

---

선택적(Selective)이라고 부르는 이유

• 수신자에서 오류가 발생한 패킷을 수신했다고 의심되는 패킷만을 송신자가 다시 전송
  → 불필요한 재전송을 피할 수 있다.
  
  
• 필요에 따라 각각의 개별적인 재전송을 요구
  • 이는 수신자가 올바르게 수신된 패킷에 대한 개별적인 확인응답을 요구
  • 이때, GBN과는 다르게 송신자는 윈도에 있는 몇몇 패킷에 대한 ACK를 이미 수신함.

 

---

순서 번호 공간에 대한 SR 송신자/수신자 관점

SR 송수신자 순서번호

• SR 수신자는 패킷의 순서와는 무관하게 손상 없이 수신된 패킷에 대한 확인응답을 함
  • 패킷 순서를 맞추는 과정
    1. 순서가 바뀐 패킷은 빠진 패킷이 수신될 때까지 버퍼에 저장
       • 빠진 패킷 → 아직 도착하지 않은 더 낮은 순서 번호를 가진 패킷
         
         
    2. 빠진 패킷이 수신된 시점에서 일련의 패킷을 순서대로 상위 계층에 전달

 

SR 송신자에 의한 이벤트와 행동

• 상위로부터 데이터 수신 : 상위에서 데이터가 수신될 때, SR 송신자는 패킷의 다음 순서 번호를 검사
  • 순서 번호가 송신자 윈도 내에 있으면 데이터는 패킷으로 송신
    • 그렇지 않으면 GBN처럼 버퍼에 나중에 전송하기 위해 되돌려진다.
      
      
• 타임아웃 : 타이머는 손실된 패킷을 보호하기 위해 재사용된다.
  • 타임아웃 시 오직 한 패킷만이 전송되기 때문에, 각 패킷은 자신의 논리 타이머가 있어야 함
    → 하나의 하드웨어 타이머가 여러 개의 논리 타이머를 흉내 내는 데 사용
    
    
• ACK 수신 : ACK가 수신됐을 때, 송신자는 그 ACK가 윈도 내에 있다면 그 패킷을 수신된 것으로 표기
  • 패킷 순서 번호가 send_base와 같은 경우
    → 윈도 베이스는 가장 작은 순서 번호를 가진 아직 확인응답되지 않은 패킷으로 옮겨짐
    
    
  • 윈도가 이동하고 윈도 내의 순서 번호를 가진 미전송 패킷이 있는 경우
    → 이 패킷들을 전송

 

SR 수신자에 의한 이벤트와 행동

• [rcv_base, rcv_base+N-1] 내의 순서 번호를 가진 패킷은 손상 없이 수신된다.
  • 이 경우는 수신된 패킷이 수신자의 윈도에 속하며, 선택적인 ACK 패킷이 송신자에게 회신됨
  • 패킷이 이전에 수신되지 않았던 것이라면 버퍼에 저장된다.
  • 패킷이 수신 윈도의 base와 같은 순서 번호를 가진 경우
    → 이 패킷과 이전에 버퍼에 저장되어 연속적으로 번호를 가진 패킷들은 상위 계층으로 전달됨
    
    
• [rcv_base-N, rcv_base-1] 내의 순서 번호를 가진 패킷이 수신된다.
  • 이 경우에는 이 패킷이 수신자와 이전에 확인응답한 것이라도 ACK가 생성되어야 한다.
  • 현재의 윈도 base보다 작고, 이미 수신된 특정 순서 번호 패킷을 무시하지 않고 재확인 응답한다.
    • send_base 패킷에 대한 ACK가 없다면, 송신자는 계속 패킷을 재전송할 것이다.
    • 또한, 송신자의 윈도가 앞으로 이동하지 않을 것이다.
      
      
• 그 외의 경우, 패킷을 무시한다.

SR 동작 예시

SR 동작 예시

---

송신자와 수신자 윈도 사이의 동기화 부족 문제

• 송신자와 수신자 윈도 사이의 동기화 부족은 순서 번호의 한정된 범위에서 문제가 됨

문제가 나타날 수 있는 2가지 시나리오

• 가정
  • 한정된 범위의 네 패킷 순서 번호 0,1,2,3과 윈도 크기 3
  • 0부터 2까지의 패킷이 전송되어 올바르게 수신되고, 수신자에게 확인됨
    → 수신자의 윈도는 각각의 순서 번호가 3,0,1인 4,5,6 패킷에 있다.
    
    

1. 첫 번째 시나리오

ACK 손실

• 처음 3개의 패킷에 대한 ACK가 손실되고, 송신자는 이 패킷을 재전송한다.
  → 수신자는 순서 번화가 0인 패킷(처음 보낸 패킷의 복사본)을 수신한다.

 

2. 두 번째 시나리오

ACK 올바르게 전달

• 처음 3개의 패킷에 대한 ACK가 모두 올바르게 전달됨
  → 송신자는 자신의 윈도를 앞으로 이동시켜 순서 번호가 3,0,1인 4,5,6번째 패킷을 보냄
  → 순서 번호 3을 가진 패킷이 손실되고, 순서 번호 0을 가진 패킷(새로운 데이터)은 도착

 

수신자 관점에서 본 2가지 시나리오

• 수신자는 다섯 번째 패킷의 원래 전송과 첫 번째 패킷의 재전송을 구별할 수 없다.
• 순서 번호 공간의 크기보다 1이 작은 윈도 크기에서 SR 프로토콜은 동작하지 않는다.
  • 윈도 크기는 SR 프로토콜에 대한 순서 번호 공간 크기의 절반보다 작거나 같아야 한다.

 

---

패킷 순서 바뀜 현상

• 송신자와 수신자가 단일한 물리적 선으로 연결되어 있을 때
  → 송신자와 수신자 사이의 채널 안에서 순서가 바뀌지 않는다.
  
  
• 연결하는 채널이 네트워크인 경우 → 패킷 순서 바뀜 발생 가능

 

패킷 순서 바뀜 현상으로 발생하는 문제

• 패킷 순서가 바뀌는 채널의 의미
  → 패킷들을 버퍼에 저장하고 나중에 이 패킷들을 임의로 내보낸다고 간주
  
  • 순서 번호가 재사용될 수 있으므로 중복 패킷을 막을 수 있는 조치가 필요
    • 실제 사용하는 해결 방식
      • 송신자가 이전에 송신된 순서 번호를 가진 패킷들이 더는 네트워크상에 없음을
        어느 정도 확신할 때까지 순서 번호를 재사용되지 않음을 확실히 한다.
        
        
• 송수신자의 윈도에 없는 순서/확인 번호를 가진 오래된 패킷의 복사본이 생길 수 있음