[Network] 스위치 구조 : 입/출력 큐잉의 발생 원인 및 버퍼링의 사용

---

1. 큐잉과 패킷 손실

• 패킷 큐는 입력 포트와 출력 포트 모두에서 형성 가능
• 큐의 위치와 범위(입/출력 포트 큐)에 영향을 주는 요인
  • 트래픽 로드
  • 스위치 구조의 상대 속도 및 라인 속도
• 큐가 커질수록 소모되는 메모리의 양이 많아짐
  → 도착하는 패킷을 저장할 수 있는 메모리가 없을 때 패킷 손실(packet loss) 발생

 

---

1.1. 패킷 손실 시나리오

• 가정
  • 입력 및 출력 라인의 속도(전송률)은 모두 초당 R(line) 패킷으로 동일
  • N개의 입력 포트와 N개의 출력 포트가 존재
  • 모든 패킷의 고정 길이가 같고,동기식으로 입력 포트에 도착
    • 임의의 링크 상에서 패킷 송신 시간과 수신 시간은 동일
    • 시간 간격 동안 0 또는 하나의 패킷이 입력 링크상에 도착 가능
  • R(switch) : 패킷이 입력 포트에서 출력 포트로 이동할 수 있는 속도를 뜻하는 스위치 구조 전송률
    
    
• R(switch)가 R(line) 보다 N배 빠른 경우 → 입력 포트에서 발생하는 큐잉은 무시
  • 최악의 경우 모든 N 입력 라인이 패킷들을 수신하고, 모든 패킷이 같은 출력 포트에 전달되는 곳에서
    N패킷들의 배치 작업은 다음 배치 작업이 도착하기 전에 스위치 구조를 통해 삭제될 수 있기 때문

 

 

---

2. 입력 큐잉

---

2.1. 예시를 통해 입력 큐잉 주요 결과 알기

2.1.1. 스위치 구조가 입력 라인 속도에 비해 빠르지 않을 경우

• 지연 없이 구조를 통해 도착하는 모든 패킷을 전송해야하는 스위치 구조가 느린 경우
  → 패킷이 스위치 구조를 통해 출력 포트로 전송되기 위해 차례를 대기

 

2.1.2. 결과를 알기 위해 크로스바 스위치 구조로 가정

• 모든 링크의 속도가 같음
• 입력 링크가 패킷을 받는 속도 == 각 패킷을 입력 포트 ~ 출력 포트 전달 속도
• FCFS 방식으로 패킷은 입력 큐에서 출력 큐로 이동
• 두 패킷이 다른 출력 포트로 향하는 경우 → 여러 패킷이 병렬로 전달 될 수 있음
• 두 패킷이 같은 출력 큐를 향하는 경우, 한 패킷은 차단 및 입력 큐에서 대기
  → 스위치 구조는 한번의 하나의 패킷만 지정된 출력 포트로 전송 가능

임의의 시간 t

HOL 차단 발생

 

2.1.3. 입력 큐에 있는 2개의 패킷이 동일한 출력 포트로 전송

• 입력 큐 앞쪽에 2개의 패킷(짙은 색)을 동일한 오른쪽 상단의 출력 포트로 전송할 때를 가정
  • 파란색 패킷 : 상위 출력 포트에 지정된 패킷
  • 하늘색 패킷 : 중간 출력 포트에 지정된 패킷
  • 회색 패킷 : 하위 출력 포트에 지정된 패킷
    
    
• 결과
  • 왼쪽 하단 큐에 짙은 색으로 처리된 두번째 패킷이 대기해야함
  • 왼쪽 하단의 밝은 패킷 → 검정 패킷 때문에 기다려야함
    • 이 현상을 대기 중인 스위치에서의 HOL(Head Of-the-Line) 차단(블로킹)
    • 라인의 앞쪽에서 다른 패킷이 막고 있음
      입력 큐에서 대기중인 패킷은 스위치 구조를 통해 전송되기 위해 대기해야함
      ← 이는 대기 중인 패킷이 사용할 출력 포트가 사용 가능한 상태여도 발생
      
      
• 입력 링크에서 패킷 도착 속도가 용량의 58%가 되면 입력 큐가 무한정 길이로 증가함.
  → 즉 패킷 손실이 증가된다는 뜻(중요한 패킷이 손실)
  • 이는 HOL 차단 문제로 인해 발생하는 것

 

 

---

3. 출력 큐잉

---

3.1. 출력 포트 큐잉 시나리오

 

3.1.1. 가정

• R(switch)가 R(line)보다 N배 빠름
• N개의 입력 포트 각각에 도착하는 패킷이 동일한 출력 포트로 향함

 

3.1.2. 가정에 대한 해석

• 패킷 전송 시간 = N개의 새로운 패킷이 출력 포트에 도착하는 시간
  • 패킷 전송 시간 : 출력 링크에 단일 패킷 전송에 걸리는 시간
  • 새로운 패킷이 N개의 입력 포트 각각에 하나씩 도착한다는 뜻
    
    
• 출력 포트는 시간 단위(패킷 전송 시간)에 단일 패킷만 전송 가능
  → N개의 도착 패킷은 출력 링크를 통한 전송 큐에서 대기해야함
  
  
• 대기 중인 N개의 패킷 중에서 하나를 전송할 때 다시 N개의 새로운 패킷이 도착
  → 스위치 구조가 포트 라인 속도보다 N배 빠른 경우, 패킷 큐잉이 출력 포트에서 발생 가능

 

---

4. 출력 포트의 저장 메모리가 충분하지 않을때의 동작

• 대기 중인 패킷의 수가 출력 포트에서 사용 가능한 메모리를 다 소모할 만큼 많아질 수 있음
• 출력 포트의 메모리가 충분치않을때, 다음의 정책 중 하나를 채택
  1. 삭제 정책(drop-tail) : 도착한 패킷을 삭제
  2. 이미 대기 중인 하나 이상의 패킷을 제거 → 새로운 패킷을 저장하기 위한 공간 확보
  3. 혼잡 신호 제공 : 버퍼가 가득 차기 전에 패킷을 삭제하여 송신자에게 알림
     • 명시적 혼잡 알림(ECN) 비트를 사용하여 수행 가능

 

4.0.1. AQM(Active Queue Management) 알고리즘(정책)

• 많은 ‘패킷 삭제’와 ‘패킷 마킹’ 정책에 대한 연구가 활발히 일어나고 있음
• RED(Random Early Detection) : 가장 폭 넓게 연구되고 구현된 AQM 알고리즘
• 최근의 AQM 정책 → PIE(Proportional Integral controller Enhanced) 및 CoDel 포함

 

---

4.1. 출력 포트 큐잉 동작

시각 t에서 출력 포트 경쟁 발생

 

 

4.1.1. 가정

• 시각 t에서 패킷은 각각의 입력 포트에 도달 후, 각 포트는 맨 앞의 출력 포트로 향함
• 동일한 라인 속도를 가진다.
• 포트 라인 속도(큐잉 속도)가 패킷 수신 시간의 3배라고 가정
  • 여기서의 패킷 수신 시간 → 새로운 N개의 패킷이 출력포트에 도착하는 시간

 

4.1.2. 해석

• 임의의 시간 t에 기존의 패킷 3개가 모두 출력 포트로 전송되어 대기 중일 것
  • 3개의 패킷 중 하나는 다음번에 출력 라인을 통해 전송될 것이다.
    
    
• 해당 그림에서는 2개의 새로운 패킷이 스위치의 수신 측에 도착
  → 2개의 패킷 중 하나는 맨 앞의 출력 포트로 전송됨
  • 패킷은 출력 포트의 패킷 스케쥴러(packet scheduler)가 선택함
    
    
• 패킥 도착 속도는 패킷이 전달될 수 있는 속도를 일시적으로 초과할 수 있다.
  • 불일치가 지속되는 시간이 길어질수록 큐는 더 길어지고,
    결국에는 포트의 버퍼가 가득 차서 패킷이 삭제됨

 

---

5. 얼마나 많은 버퍼가 요구되는가?

---

5.1. 포트에 얼마나 많은 버퍼링이 제공되어야 하는가?

5.1.1. 과거 버퍼 크기에 대한 규칙

• 버퍼링의 양(B, 버퍼의 크기)는 링크 용량이 C일때, RTT(평균 왕복 시간)과 같아야 한다.
  • RTT가 250ms인 10Gbps 링크의 버퍼들이 필요한 버퍼의 양
    • B = RTT x C = 2.5Gb와 같은 버퍼의 양이 필요
      
      
• 이 결과는 상대적으로 작은 양의 TCP 흐름에 대한 큐잉 분석에 기반을 둔다.

 

5.1.2. 최근의 이론과 실험

• 많은 수의 독립적인 TCP 흐름(N)이 링크를 통과할 때를 기반으로 둠
• 필요한 버퍼링은 B = RTT x C / root(N) 이라고 제안
  • 거대한 백본 라우터 링크를 통과하는 많은 수의 TCP 흐름이 있는 코어 네트워크(일반적인 경우)
    → N 값은 커질 수 있고, 필요한 버퍼 크기의 감소가 두드러짐

 

---

5.2. 버퍼링의 지연 기반 고려사항

• 버퍼링은 지연 기반 사항을 고려할 때, 양날의 검이라고 할 수 있다.
  • 트래픽의 단기 통계 변동을 흡수하는데 사용될 수 있음
    → But, 지연과 그에 따른 우려그 증가할 수 있다.
    
    
• 버퍼링이 클수록 라우터의 패킷 손실률이 감소 → 버퍼가 클수록 큐잉 지연이 길어진다.
  • 버퍼링이 크면 라우터가 패킷 도착 속도의 큰 변동을 흡수하기 때문에 패킷 손실률을 감소시킴
  • 패킷 손실을 줄이기 위해 홉당 버퍼의 양을 10배 늘리는 경우
    → 종단 간 지연 10배 증가
    
    • 증가된 RTT는 TCP 송신자의 초기 혼잡 및 패킷 손실에 대한 응답 속도를 떨어뜨림

 

---

5.3. 버퍼블로트(bufferbloat)

• 버퍼블로트(bufferbloat) : 지속적인 버퍼링으로 인한 긴 지연이 생기는 것
  → 패킷의 과도한 버퍼링으로 인해 생기는 패킷 교환 네트워크의 높은 대기 시간의 원인

 

5.3.1. 네트워크 가장자리 - 버퍼블로트 발생 시나리오

• 위에서 얘기했던 버퍼링은 모두 혼잡한 링크에서 대역폭과 버퍼를 놓고 경쟁하고 있다고 가정했었음
  → 네트워크 코어 내에 라우터에는 맞지만, 네트워크 가장자리에서는 아닐수도 있음

버퍼 플로우: 영속 큐

버퍼 플로우 발생에 따른 큐 길이 그래프

 

• 가정
  • 홈 라우터가 TCP 세그먼트를 원격 게임 서버로 전송
  • 홈에서 보내는 TCP 세그먼트를 포함하는 패킷을 전송하는데 20ms 소요됨
  • 큐잉 지연은 무시한다.
  • 게임 서버의 다른 곳에서 지연되며 RTT는 200ms
  • t = 0 에서 25개 패킷의 버스트가 큐에 도착한다고 가정
    
    
• 과정
  1. 20ms마다 하나씩 대기 중인 패킷들 중 하나가 전송됨
     → t = 21번째 패킷이 전송되는 것처럼, 200ms에서 첫번째 ACK가 도착
     • 이 ACK의 도착이 TCP 송신자는 다른 패킷을 보내게 함
       
       
  2. 홈 라우터의 송신 링크 t = 220에서 다음 ACK가 도착하고, 또 다른 ACK가 도착
  3. TCP 세그먼트는 홈에 의해 해제되며, 22번째 패킷은 전송되는 큐에 놓인다.
     
     
• 해당 시나리오에서, ACK 클록은 대기 중인 패킷이 있을때마다 새 패킷이 큐에 도착 후 전송
  → 홈 라우터의 송신 링크에서 큐 크기가 항상 5 패킷이 됨
  • 종단 간 파이프는 꽉 찼지만 큐잉 지연의 양은 일정하고 지속적이다.
    • 홈 네트워크에 다른 트래픽이 존재하지 않는 경우에도 지나치게 긴 지속 지연의 이유가 설명이 안됨
    • 종단 간 파이프가 꽉 찼다는 의미 → 매 20ms 병목률로 한 패킷의 경로의 목적지까지 전송함

 

5.3.2. 위 시나리오의 결론

• 버퍼블로트는 버퍼의 처리량뿐만 아니라 최소 지연도 중요하단 것을 알려줌
• 네트워크 가장자리와 네트워크 내 큐에서 송신자 간의 상호작용이 실제로는 어렵다.
• 최근 버퍼블로트를 방지하기 위해 특정 AQM 메커니즘을 추가하면서 대량 처리 성능을 보존