Chapter4. 네트워크 계층: 데이터 평면

4.2 라우터 내부에는 무엇이 있을까?

4.2.4 어디에서 큐잉이 일어날까?

패킷 큐는 입력 포트와 출력 포트 모두에서 형성될 수 있음. 큐의 위치와 범위는 트래픽 로드, 스위치 구조의 상대 속도 및 라인 속도에 따라서 달라짐.

큐가 더 커지면 → 라우터의 메모리가 소모될 수 있고 도착하는 패킷을 저장할 수 있는 메모리가 없을 때 패킷 손실이 발생함!

이전에는 패킷이 네트워크 내에서 손실 되거나 라우터에서 감소된다고 언급했었는데, 여기 라우터 내의 패킷이 실제로 삭제되고 손실되는 큐에 있음.

입력큐잉

지연 없이 구조를 통해 도착하는 모든 패킷을 전송하기에 스위치 구조가 충분히 빠르지 않다면? ⇒ 패킷이 스위치 구조를 통해 출력포트로 전송되기 위해 차례를 기다려야 함.

이 큐잉의 중요한 결과를 살펴보기 위해 크로스바 스위치 구조를 가정해본다.

• 모든 링크의 속도는 같다.
• 입력 링크가 패킷을 받는 것과 같은 속도로 하나의 패킷을 입력 포트에서 주어진 출력 포트로 전달한다.
• FCFS 방식으로 패킷은 입력 큐에서 출력 큐로 이동된다.

출력 포트가 다르다면 여러 패킷이 병렬로 전달 가능하지만, 두 패킷이 같은 출력 큐로 향한다면 이 중 한 패킷은 차단되고 입력 큐에서 기다려야함. 즉, 스위치 구조는 한 번에 하나의 패킷만 지정된 출력포트로 전송이 가능함.

위의 그림은 입력 큐 앞 쪽에 있는 2개의 패킷이 동일한 오른쪽 상단의 출력 포트로 보내지는 예시임.

• 스위치 구조가 왼쪽 상단 큐의 앞쪽에서 패킷을 전송한다고 가정
• 왼쪽 하단 큐에 짙은 색으로 처리된 두 번째 패킷이 대기해야 함.
• 아래쪽 밝은 패킷은 이동하려는 출력 링크가 경쟁이 없는 상태이지만, 바로 앞의 검정 패킷 때문에 기다려야 함. ⇒ 이 현상은 입력 대기 중인 스위치에서의 HOL차단이라고 함.

라인의 앞쪽에서 다른 패킷이 막고 있으므로 입력 큐에서 대기 중인 패킷은 사용할 출력 포트가 사용 중이지 않아도 스위치 구조를 통해 전송되기 위해 기다려야 함.

(입력 링크에서 패킷 도착 속도가 용량의 58%가 되면 HOL차단 때문에 입력 큐가 무한정 길이로 증가함 ⇒ 패킷 손실이 증가함.)

출력 큐잉

스위치의 출력 포트에서 큐잉이 발생할 수 있는지 여부를 살펴보자.

R 스위치가 다시 R(line)보다 N배 빠르며 N개의 입력 포트 각각에 도착하는 패킷이 동일한 출력 포트로 향하는 것을 가정하자.

• 출력 링크에 단일 패킷을 보내는 데 걸리는 시간에 N개의 새로운 패킷이 출력 포트에 도착함.
• 출력 포트는 시간 단위에 단일 패킷만을 전송할 수 있기 때문에 N개의 도착 패킷은 출력 링크를 통한 전송 큐에서 대기해야 함.
• 대기 중인 N개의 패킷 중에서 하나를 전송할 때 다시 N개의 새로운 패킷이 도착할 수 있음.

⇒ 스위치 구조가 라인 속도보다 N배 빠른 경우에도 패킷 큐잉이 출력 포트에서 발생할 수 있음! & 대기 중인 패킷의 수가 출력 포트에서 사용 가능한 메모리를 다 소모할 만큼 충분히 많아질 수 있음.

들어오는 패킷을 저장할 메모리가 충분하지 않을 때 도착한 패킷을 삭제하거나 이미 대기 중인 하나 이상의 패킷을 제거하여 새로 도착한 패킷을 저장하기 위한 공간을 확보해야 함. 버퍼가 가득 차기 전에 패킷을 삭제(or 헤더를 마킹)하여 송신자에게 혼잡 신호를 제공하는 것이 바람직할 수 있음. (마킹은 ‘명시적 혼잡 알림’ 비트를 사용하여 수행 가능)

• 시각 t에서 패킷은 각각의 입력 포트에 도달하고 각각의 포트는 맨 앞의 출력 포트로 향함.
• 동일한 라인 속도를 가지고, 라인 속도의 3배로 동작하는 것으로 가정하면 기존의 패킷 3개가 모두 출력 포트로 전송되어 대기 중일 것임.
• 이 3개의 패킷 중 하나는 다음번에 출력 라인을 통해 전송될 것임.
• 예시에서는 2개의 새로운 패킷이 스위치의 수신 측에 도착했는데, 이 패킷 중 하나는 맨 앞의 출력 포트로 전송됨.

⇒ 이러한 큐잉의 결과는 출력 포트의 패킷 스케줄러가 전송 대기 중인 패킷 중 하나의 패킷을 선택해야 한다는 것!

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

위에서는 패킷의 버스트가 라우터의 입력 또는 출력 포트에 도착할 때 패킷 큐가 어떻게 형성되는지, 그리고 패킷 도착 속도는 패킷이 전달될 수 있는 속도를 일시적으로 초과한다는 것을 보여주었음.

불일치가 지속되는 시간이 길어질수록 큐는 더 길어지며, 결국 포트의 버퍼가 가득 차서 패킷이 삭제됨. ⇒ 포트에 얼마나 많은 버퍼링이 제공되어야 하는가?

버퍼 크기에 대한 규칙은 링크 용량이 C일 때, 버퍼링의 양(B)은 평균 왕복 시간(RTT)와 같아야 한다는 것임.

버퍼링이 클수록 라우터가 패킷 도착 속도의 큰 변동을 흡수하여 라우터의 패킷 손실률을 감소시킬 수 있기 때문에 버퍼링이 더 낫다고 생각하는 것보다 버퍼가 클수록 큐잉 지연이 길어진다고 생각하는 편이 나음.

버퍼링은 트래픽의 단기 통계 변동을 흡수하는 데 사용될 수 있지만 지연과 그에 따른 우려를 증가시킬 수도 있음.

독립적인 송신자들이 혼잡한 링크에서 대역폭과 버퍼를 놓고 경쟁하고 있다고 가정했으나, 네트워크 가장자리에서는 가정이 유지되지 않을 수 있음.

(a)는 TCP 세그먼트를 원격 게임 서버로 보내는 홈라우터에 대한 설명임. 게이머의 TCP세그먼트를 퐇마하는 패킷을 전송하는데 20ms가 소요되며, 큐잉 지연이 무시해도 될 정도라고 가정함. RTT는 200ms.

(b)에서와 같이 25개 패킷의 버스트가 큐에 도착한다고 가정. 대기 중인 패킷들 중 하나는 20ms마다 한 번씩 전송되므로, 21번째 패킷이 전송되고 있는 것처럼 t=200ms에서 첫 번째 ACK가 도착함. 이 ACK 도착은 TCP 송신자가 다른 패킷을 보내게 하며, 이것은 다음과 같이 또 대기함. TCP 세그먼트는 게이머에 의해 해제되며, 22번째 패킷은 전송되는 큐에 놓임.

해당 시나리오에서 ACK클록은 대기 중인 패킷이 있을 때마다 새 패킷이 큐에 도착하게 되고, 전송되어 홈 라우터의 송신 링크에서 큐 크기가 항상 5패킷이 됨.

⇒ 종단 간 파이프는 꽉 찼지만 큐잉 지연의 양은 일정하고 지속적임.

지속적 버퍼링으로 인한 긴 지연에 대한 위의 시나리오를 버퍼블로트라고 하는데, 이는 처리량뿐만 아니라 최소 지연도 중요하며 네트워크 가장자리와 네트워크 내 큐에서 송신자 간의 상호작용이 실제로 복잡할 수 있음을 보여줌.

4.2.5 패킷 스케줄링

큐에 있는 패킷이 출력 링크를 통해 전송되는 순서를 결정하는 문제.

라우터에서 일반적으로 사용되는 큐잉 처리 방법: FCFS (FIFO), 라운드 로빈 큐잉

FIFO

위의 그림은 FIFO 링크 스케줄링 분야의 큐 모델의 개념도를 보여줌.

링크가 현재 다른 패킷을 전송 중이면, 출력 링크 큐에 도착한 패킷은 전송을 기다림. 도착한 패킷을 담을 버퍼 공간이 충분하지 않은 경우 도착 패킷 공간을 확보하기 위해 큐의 패킷 폐기 정책은 패킷 손실 여부 또는 다른 패킷을 큐에서 제거할 것인지 여부를 결정함. (여기서는 패킷 폐기를 무시한다.) 패킷이 출력되는 링크를 통해 완전히 전송되면 큐에서 제거됨.

FIFO 스케줄링 규칙은 출력 링크 큐에 도착한 순서와 동일한 순서로 출력 링크에서 전송할 패킷을 선택함.

• 도착한 패킷은 도착한 순서를 나타내는 숫자와 함께 상단 타임라인 위에 번호가 매겨진 화살표로 표시됨.
• 개별 패킷의 전송은 하단 타임라인 아래 표시됨.
• 패킷이 전송 중에 소비하는 시간은 두 타임라인 사이의 사각형으로 표시됨.
• FIFO에서 패킷은 도착한 순서와 동일한 순서로 나가게 됨.
• 패킷 4를 전송한 이후에 링크는 패킷 5가 도착할 때까지 유휴 상태로 유지됨.
  • 패킷 1에서 4까지가 모두 전송되고 큐에 남아 있는 패킷이 없는 상태이기 때문임.

우선순위 큐잉

큐잉에서 출력 링크에 도착한 패킷은 위의 그림과 같이 큐에 도착하면 우선순위 클래스로 분류됨. 또한 실시간 VoIP 패킷은 전자메일 패킷과 같은 트래픽보다 우선순위를 받을 수 있음. 각 우선순위 클래스에는 일반적으로 고유한 큐가 있는데, 전송할 패킷을 선택할 때 우선순위 큐는 전송 대기 중인 패킷으로 차 있는 상태이고 가장 높은 우선순위 클래스에서 패킷을 전송함.

우선순위가 동일한 패킷들 중에서의 선택은 전형적으로 FIFO 방식으로 행해짐.

위의 그림은 우선순위 클래스가 2개인 경우 큐 동작을 보여줌.

• 패킷 1, 3, 4 → 높은 우선순위 클래스
• 패킷 2, 5 → 낮은 우선순위 클래스

눈여겨 볼 점은, 패킷 1이 전송된 후 패킷 3이 패킷 2보다 먼저 전송되는 것인데, 패킷 3이 패킷 2보다 우선순위가 높기 때문에 이전에 도착했더라도 패킷 3이 먼저 전송되는 것임.

패킷 3의 전송이 끝나면 패킷 2의 전송을 시작하고 패킷 2의 전송 중에 패킷 4가 도착함. 이때, 패킷 4의 우선순위가 더 높더라도 비선점 우선순위 큐잉에서는 패킷의 전송이 시작되면 중단하지 않으므로 패킷 4는 전송을 위해 대기함.

라운드 로빈과 WFQ

라운드 로빈 큐잉 규칙에서 패킷은 우선순위 큐잉과 같이 클래스로 분류됨. 그러나 클래스 간에는 엄격한 서비스 우선순위가 존재하지 않으며, 라운드 로빈 스케줄러가 클래스 간에 서비스를 번갈아서 제공함.

가장 단순한 라운드 로빈 스케줄링에서는 클래스 1 패킷이 전송된 다음 클래스 2 패킷이 전송되고, 다시 클래스 1 다음에 클래스 2 패킷이 전송됨.

작업 보존 큐잉 규칙의 경우, 전송을 위해 큐에서 기다리는 패킷이 있다면 링크는 유휴 상태가 되는 것을 허용하지 않음.

작업 보존 라운드 로빈 규칙에서는 클래스에서 패킷을 찾지만 아무것도 찾지 못하면 시퀀스의 다음 클래스를 즉시 검사함.

위의 그림은 2개의 클래스 라운드 로빈 큐의 작동을 보여줌.

• 클래스 1 → 패킷 1, 2, 4

• 클래스 2 → 패킷 3, 5

• 패킷 1은 출력 큐에 도착하면 즉시 전송을 시작.

• 패킷 1이 전송되는 동안 패킷 2와 3이 도착하고 전송을 대기.

• 패킷 1의 전송이 완료되면 스케줄러는 클래스 2 패킷을 찾고 패킷 3을 전송.

• 패킷 3의 전송이 완료되면 스케줄러는 클래스 1 패킷을 찾고 패킷 2를 전송.

• 패킷 2의 전송이 완료되면 패킷 4만이 큐에 있기 때문에 바로 패킷 4를 전송.

라우터에서 널리 구현된 라운드 로빈 큐잉의 일반화된 형태는 소위 WFQ 규칙임. 위의 그림에 나와있으며, 여기서 도착하는 패킷은 적절한 클래스별 대기 영역에서 분류되며 대기함. 라운드 로빈 스케줄링에서처럼 WFQ 스케줄러는 순환 방식으로 동작함.

WFQ는 작업 보존 큐잉 규칙이며, 따라서 빈 클래스 큐를 찾으면 서비스 순서에서 다음 클래스로 즉시 이동함.

WFQ는 각 클래스마다 다른 양의 서비스 시간을 부여받는다는 점에서 라운드 로빈과 차이가 있음. 특히 각 클래스는 가중치w를 할당받음.(해당 가중치 값은 클래스별로 다름.)