큐잉과 패킷 손실
- 패킷 큐는 입력 포트와 출력 포트 모두에서 형성 가능
- 큐의 위치와 범위(입/출력 포트 큐)에 영향을 주는 요인
- 트래픽 로드
- 스위치 구조의 상대 속도 및 라인 속도
- 큐가 커질수록 소모되는 메모리의 양이 많아짐
→ 도착하는 패킷을 저장할 수 있는 메모리가 없을 때 패킷 손실(packet loss) 발생
패킷 손실 시나리오
- 가정
- 입력 및 출력 라인의 속도(전송률)은 모두 초당
R(line) 패킷으로 동일
- N개의 입력 포트와 N개의 출력 포트가 존재
- 모든 패킷의 고정 길이가 같고,동기식으로 입력 포트에 도착
- 임의의 링크 상에서 패킷 송신 시간과 수신 시간은 동일
- 시간 간격 동안 0 또는 하나의 패킷이 입력 링크상에 도착 가능
R(switch) : 패킷이 입력 포트에서 출력 포트로 이동할 수 있는 속도를 뜻하는 스위치 구조 전송률
R(switch)가 R(line) 보다 N배 빠른 경우 → 입력 포트에서 발생하는 큐잉은 무시
- 최악의 경우 모든 N 입력 라인이 패킷들을 수신하고, 모든 패킷이 같은 출력 포트에 전달되는 곳에서
N패킷들의 배치 작업은 다음 배치 작업이 도착하기 전에 스위치 구조를 통해 삭제될 수 있기 때문
입력 큐잉
예시를 통해 입력 큐잉 주요 결과 알기
스위치 구조가 입력 라인 속도에 비해 빠르지 않을 경우
- 지연 없이 구조를 통해 도착하는 모든 패킷을 전송해야하는 스위치 구조가 느린 경우
→ 패킷이 스위치 구조를 통해 출력 포트로 전송되기 위해 차례를 대기
결과를 알기 위해 크로스바 스위치 구조로 가정
- 모든 링크의 속도가 같음
- 입력 링크가 패킷을 받는 속도 == 각 패킷을 입력 포트 ~ 출력 포트 전달 속도
- FCFS 방식으로 패킷은 입력 큐에서 출력 큐로 이동
- 두 패킷이 다른 출력 포트로 향하는 경우 → 여러 패킷이 병렬로 전달 될 수 있음
- 두 패킷이 같은 출력 큐를 향하는 경우, 한 패킷은 차단 및 입력 큐에서 대기
→ 스위치 구조는 한번의 하나의 패킷만 지정된 출력 포트로 전송 가능
임의의 시간 t
HOL 차단 발생
입력 큐에 있는 2개의 패킷이 동일한 출력 포트로 전송
- 입력 큐 앞쪽에 2개의 패킷(짙은 색)을 동일한 오른쪽 상단의 출력 포트로 전송할 때를 가정
- 파란색 패킷 : 상위 출력 포트에 지정된 패킷
- 하늘색 패킷 : 중간 출력 포트에 지정된 패킷
- 회색 패킷 : 하위 출력 포트에 지정된 패킷
- 결과
- 왼쪽 하단 큐에 짙은 색으로 처리된 두번째 패킷이 대기해야함
- 왼쪽 하단의 밝은 패킷 → 검정 패킷 때문에 기다려야함
- 이 현상을 대기 중인 스위치에서의
HOL(Head Of-the-Line) 차단(블로킹)
- 라인의 앞쪽에서 다른 패킷이 막고 있음
입력 큐에서 대기중인 패킷은 스위치 구조를 통해 전송되기 위해 대기해야함
← 이는 대기 중인 패킷이 사용할 출력 포트가 사용 가능한 상태여도 발생
- 입력 링크에서 패킷 도착 속도가 용량의 58%가 되면 입력 큐가 무한정 길이로 증가함.
→ 즉 패킷 손실이 증가된다는 뜻(중요한 패킷이 손실)
출력 큐잉
출력 포트 큐잉 시나리오
가정
R(switch)가 R(line)보다 N배 빠름- N개의 입력 포트 각각에 도착하는 패킷이 동일한 출력 포트로 향함
가정에 대한 해석
- 패킷 전송 시간 = N개의 새로운 패킷이 출력 포트에 도착하는 시간
- 패킷 전송 시간 : 출력 링크에 단일 패킷 전송에 걸리는 시간
- 새로운 패킷이 N개의 입력 포트 각각에 하나씩 도착한다는 뜻
- 출력 포트는 시간 단위(패킷 전송 시간)에 단일 패킷만 전송 가능
→ N개의 도착 패킷은 출력 링크를 통한 전송 큐에서 대기해야함
- 대기 중인 N개의 패킷 중에서 하나를 전송할 때 다시 N개의 새로운 패킷이 도착
→ 스위치 구조가 포트 라인 속도보다 N배 빠른 경우, 패킷 큐잉이 출력 포트에서 발생 가능
출력 포트의 저장 메모리가 충분하지 않을때의 동작
- 대기 중인 패킷의 수가 출력 포트에서 사용 가능한 메모리를 다 소모할 만큼 많아질 수 있음
- 출력 포트의 메모리가 충분치않을때, 다음의 정책 중 하나를 채택
삭제 정책(drop-tail) : 도착한 패킷을 삭제- 이미 대기 중인 하나 이상의 패킷을 제거 → 새로운 패킷을 저장하기 위한 공간 확보
혼잡 신호 제공 : 버퍼가 가득 차기 전에 패킷을 삭제하여 송신자에게 알림
- 명시적 혼잡 알림(ECN) 비트를 사용하여 수행 가능
AQM(Active Queue Management) 알고리즘(정책)
- 많은 ‘패킷 삭제’와 ‘패킷 마킹’ 정책에 대한 연구가 활발히 일어나고 있음
RED(Random Early Detection) : 가장 폭 넓게 연구되고 구현된 AQM 알고리즘- 최근의 AQM 정책 → PIE(Proportional Integral controller Enhanced) 및 CoDel 포함
출력 포트 큐잉 동작
시각 t에서 출력 포트 경쟁 발생
가정
- 시각 t에서 패킷은 각각의 입력 포트에 도달 후, 각 포트는 맨 앞의 출력 포트로 향함
- 동일한 라인 속도를 가진다.
- 포트 라인 속도(큐잉 속도)가 패킷 수신 시간의 3배라고 가정
- 여기서의 패킷 수신 시간 → 새로운 N개의 패킷이 출력포트에 도착하는 시간
해석
- 임의의 시간 t에 기존의 패킷 3개가 모두 출력 포트로 전송되어 대기 중일 것
- 3개의 패킷 중 하나는 다음번에 출력 라인을 통해 전송될 것이다.
- 해당 그림에서는 2개의 새로운 패킷이 스위치의 수신 측에 도착
→ 2개의 패킷 중 하나는 맨 앞의 출력 포트로 전송됨
- 패킷은 출력 포트의 패킷 스케쥴러(packet scheduler)가 선택함
- 패킥 도착 속도는 패킷이 전달될 수 있는 속도를 일시적으로 초과할 수 있다.
- 불일치가 지속되는 시간이 길어질수록 큐는 더 길어지고,
결국에는 포트의 버퍼가 가득 차서 패킷이 삭제됨
얼마나 많은 버퍼가 요구되는가?
포트에 얼마나 많은 버퍼링이 제공되어야 하는가?
과거 버퍼 크기에 대한 규칙
- 버퍼링의 양(B, 버퍼의 크기)는 링크 용량이 C일때, RTT(평균 왕복 시간)과 같아야 한다.
- RTT가 250ms인 10Gbps 링크의 버퍼들이 필요한 버퍼의 양
- B = RTT x C = 2.5Gb와 같은 버퍼의 양이 필요
- 이 결과는 상대적으로 작은 양의 TCP 흐름에 대한 큐잉 분석에 기반을 둔다.
최근의 이론과 실험
- 많은 수의 독립적인 TCP 흐름(N)이 링크를 통과할 때를 기반으로 둠
- 필요한 버퍼링은 B = RTT x C / root(N) 이라고 제안
- 거대한 백본 라우터 링크를 통과하는 많은 수의 TCP 흐름이 있는 코어 네트워크(일반적인 경우)
→ N 값은 커질 수 있고, 필요한 버퍼 크기의 감소가 두드러짐
버퍼링의 지연 기반 고려사항
- 버퍼링은 지연 기반 사항을 고려할 때, 양날의 검이라고 할 수 있다.
- 트래픽의 단기 통계 변동을 흡수하는데 사용될 수 있음
→ But, 지연과 그에 따른 우려그 증가할 수 있다.
- 버퍼링이 클수록 라우터의 패킷 손실률이 감소 → 버퍼가 클수록 큐잉 지연이 길어진다.
- 버퍼링이 크면 라우터가 패킷 도착 속도의 큰 변동을 흡수하기 때문에 패킷 손실률을 감소시킴
- 패킷 손실을 줄이기 위해 홉당 버퍼의 양을 10배 늘리는 경우
→ 종단 간 지연 10배 증가
- 증가된 RTT는 TCP 송신자의 초기 혼잡 및 패킷 손실에 대한 응답 속도를 떨어뜨림
버퍼블로트(bufferbloat)
버퍼블로트(bufferbloat) : 지속적인 버퍼링으로 인한 긴 지연이 생기는 것
→ 패킷의 과도한 버퍼링으로 인해 생기는 패킷 교환 네트워크의 높은 대기 시간의 원인
네트워크 가장자리 - 버퍼블로트 발생 시나리오
- 위에서 얘기했던 버퍼링은 모두 혼잡한 링크에서 대역폭과 버퍼를 놓고 경쟁하고 있다고 가정했었음
→ 네트워크 코어 내에 라우터에는 맞지만, 네트워크 가장자리에서는 아닐수도 있음
버퍼 플로우: 영속 큐
버퍼 플로우 발생에 따른 큐 길이 그래프
- 가정
- 홈 라우터가 TCP 세그먼트를 원격 게임 서버로 전송
- 홈에서 보내는 TCP 세그먼트를 포함하는 패킷을 전송하는데 20ms 소요됨
- 큐잉 지연은 무시한다.
- 게임 서버의 다른 곳에서 지연되며 RTT는 200ms
- t = 0 에서 25개 패킷의 버스트가 큐에 도착한다고 가정
- 과정
- 20ms마다 하나씩 대기 중인 패킷들 중 하나가 전송됨
→ t = 21번째 패킷이 전송되는 것처럼, 200ms에서 첫번째 ACK가 도착
- 이 ACK의 도착이 TCP 송신자는 다른 패킷을 보내게 함
- 홈 라우터의 송신 링크 t = 220에서 다음 ACK가 도착하고, 또 다른 ACK가 도착
- TCP 세그먼트는 홈에 의해 해제되며, 22번째 패킷은 전송되는 큐에 놓인다.
- 해당 시나리오에서, ACK 클록은 대기 중인 패킷이 있을때마다 새 패킷이 큐에 도착 후 전송
→ 홈 라우터의 송신 링크에서 큐 크기가 항상 5 패킷이 됨
- 종단 간 파이프는 꽉 찼지만 큐잉 지연의 양은 일정하고 지속적이다.
- 홈 네트워크에 다른 트래픽이 존재하지 않는 경우에도 지나치게 긴 지속 지연의 이유가 설명이 안됨
- 종단 간 파이프가 꽉 찼다는 의미 → 매 20ms 병목률로 한 패킷의 경로의 목적지까지 전송함
위 시나리오의 결론
- 버퍼블로트는 버퍼의 처리량뿐만 아니라 최소 지연도 중요하단 것을 알려줌
- 네트워크 가장자리와 네트워크 내 큐에서 송신자 간의 상호작용이 실제로는 어렵다.
- 최근 버퍼블로트를 방지하기 위해 특정 AQM 메커니즘을 추가하면서 대량 처리 성능을 보존