[네트워크/Network] 라우터의 패킷 지연과 패킷 스케줄링 방법

💡 0. 들어가면서 

지난 포스팅에서는 라우터의 구조를 간단하게 살펴보고, 입력포트의 기능에 대해 공부했습니다. 특히, 입력 포트의 마지막 부분에서는 포워딩 테이블을 참조하여 도착된 패킷이 스위칭 구조를 통해 전달되는 라우터 출력 포트를 결정했는데요. 이 때 수많은 패킷 주소를 적은 수의 포워딩 테이블 엔트리로 관리하기 위해 프리픽스(Prefix)를 이용한 목적지 기반 전달 방법에 대해 살펴봤었습니다.

 

[네트워크/Network] 라우터의 입력 포트 처리 및 목적지 기반 전달

 

이번 시간에 공부하고자 하는 내용은 라우터에서 발생하는 큐잉(Queueing)입니다. 어느 지점에서 큐잉 지연이 발생하며, 이를 해결하기 위해서는 어떤 패킷 스케줄링 방법을 사용할 수 있는지에 대해 공부해보겠습니다.

 

 

🤔 1. 큐잉(Queueing)의 발생지점

이전 시간에 살펴본 라우터의 구조를 다시 한 번 보겠습니다.

 

라우터 구조와 패킷 지연

 

그림에서 주황색으로 표시한 부분이 있는데요. 패킷(우편모양)은 입력 포트로 들어오는 시점과 스위칭 구조에서 출력 포트로 들어오는 시점에서 큐에 들어가게 됩니다. 즉, 패킷 큐는 입력 포트와 출력 포트 모두에서 형성될 수 있다는 뜻이죠.

 

이 때, 대기열의 위치와 범위는 트래픽의 정도와 스위칭 구조의 상대 속도 및 회선 속도에 따라 달라질 수 있습니다. 대기열이 더 길어지면 라우터의 메모리가 더 많이 소모되고, 도착하는 패킷을 저장할 수 있는 메모리가 부족해지는 상황이 오면 패킷 손실이 발생하게 되죠.

 

✅ 1-1) 입력 큐잉

입력 큐잉은 스위칭 구조의 패킷 전달 속도가 입력 포트에서 보내주는 패킷 전달 속도보다 느릴 때 발생합니다. 쉽게 말해서 입력포트에서 패킷을 다음 출력 포트로 전달해주기 위해 스위칭 구조에게 처리를 맡겼는데, 스위칭 구조에서 밀려오는 패킷을 빠르게 전달하지 못할 때 발생하는 것이죠.

 

예를 들어, 만약 스위칭 구조가 크로스바 형태를 가졌다고 해볼까요? 이 때 모든 링크의 속도는 같고, 입력 링크가 패킷을 받는 것과 같은 속도로 하나의 패킷을 입력 포트에서 주어진 출력포트로 전달한다고 가정하겠습니다. 출력 포트가 다르다면 여러 패킷이 병렬로 전달될 수 있지만, 두 패킷이 같은 출력 큐로 향한다면 이 중 하나의 패킷은 차단되고 입력 큐에서 기다려야 합니다.

 

그리고 이 현상을 HOL(Head-Of-the-Line) 차단 현상이라고 하는데요. 회선의 앞쪽에서 다른 패킷이 막고 있으므로 입력 큐에서 대기 중인 패킷은 사용할 출력 포트가 사용 중이지 않아도 스위칭 구조를 통해 전송되기 위해서 기다려야 한다는 것이죠.

 

HOL Blocking

위 그림을 보면 세 개의 입력 포트에서 모두 첫번째 출력 포트로 패킷을 전송하는 것을 볼 수 있습니다.

 

이 상황에서 스위칭 구조는 두 번째 입력 포트의 패킷을 보낸다고 해볼까요? 그러면 두번째 입력포트의 초록, 검정 패킷이나 세번째 입력포트의 검정 패킷은 분명 목적지 출력 포트가 사용 중이지 않음에도 불구하고 기다려야 하는 상황을 볼 수 있습니다.

 

✅ 1-2) 출력 큐잉

출력 큐잉을 설명하기 위해 앞서 설명한 입력 큐잉이 발생하지 않는 상황을 가정해보려고 합니다. 만약 스위치 구조가 처리할 수 있는 패킷의 양이 입력 포트가 처리하는 패킷의 양보다 N배 빠르고, N개의 입력 포트 각각에 도착하는 패킷이 동일한 출력 포트로 향한다고 해보겠습니다.

 

이 경우, 출력 링크에 단일 패킷을 보내는 데 걸리는 시간에 N개의 새로운 패킷이 출력 포트에 도착할 수 있게 됩니다. 스위칭 구조가 모든 입력 포트에서 오는 패킷을 재빨리 전달할 수 있으니까요.

 

한편, 출력 포트는 시간 단위(패킷 전송 시간)에 단일 패킷만을 전송할 수 있으므로, N개의 도착 패킷은 출력 링크를 통한 전송 큐에서 대기해야만 합니다. 그러면 대기 중인 N개의 패킷 중에서 하나를 전송하는 순간 다시 N개의 패킷이 도착해버리는 상황이 됩니다. 따라서, 스위칭 구조가 포트 회선 속도의 N배가 빨라도 패킷 큐잉이 출력 포트에서 발생할 수 있다는 뜻입니다.

 

이 때, 들어오는 패킷을 저장할 메모리가 충분하지 않다면 도착한 패킷을 폐기하거나 이미 대기하고 있던 패킷을 폐기해서 공간을 확보해야 하는데요. 이러한 패킷 폐기 정책에 대해서는 AQM(Active Queue Management) 알고리즘이 존재하지만 이번 포스팅에서는 이 주제까지는 설명하지 않겠습니다.

 

다만, 지금은 전송 대기 중인 패킷을 실제로 전송하는 과정에서 '어떤 패킷을 출력 포트에서 먼저 전송할 지'에 대한 '패킷 스케줄링'에 대해 설명해보겠습니다.

 

---

 

📝 2. 패킷 스케줄링

스케줄링 기법은 운영체제에서 CPU 스케줄링에 대해 공부할 때 본 적이 있어서 크게 이해하는 데 어렵지는 않을 것 같습니다.

 

✅ 2-1) FIFO(First-In-First-Out)

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

 

FIFO

패킷 하나를 전송하는 데 3 Unit time이 소요된다고 하면 위와 같은 순서를 따라 패킷은 도착한 순서와 동일한 순서로 나가게 됩니다. 이 때 패킷 4를 전송하고 나서 링크는 패킷 5가 도착할 때까지 유휴상태로 존재합니다.

 

✅ 2-2) 우선순위 큐잉

우선순위 큐잉에서 출력 링크에 도착한 패킷은 아래 그림과 같이 우선순위 클래스로 분류됩니다. 각 우선순위 클래스에는 고유한 큐가 존재해서 전송할 패킷을 선택할 때 가장 높은 우선순위 클래스에서 패킷을 전송하게 됩니다. 이 때 동일한 우선순위를 가지는 패킷에 대해서는 FIFO를 적용합니다.

 

우선순위 큐잉

 

아래 그림은 위처럼 우선순위 클래스가 두 개인 경우에서 큐의 동작을 보여주는데요. 패킷 1, 3, 4는 높은 우선순위에 속하고 패킷 2, 5는 낮은 우선순위에 속합니다. 그런데 아래 그림을 자세히 보시면 1번, 3번 패킷의 전송을 마치고 2번 패킷을 전송할 때, 도중에 4번 패킷이 도착하는 것을 볼 수 있습니다. 4번 패킷이 우선순위가 높지만 비선점(Non-Preemptive) 우선순위 큐잉에서는 패킷의 전송이 시작되면 도중에 중단되지 않습니다.

 

비선점 우선순위 큐잉

 

✅ 2-3) 라운드 로빈(Round Robin)과 WFQ(Weighted Fair Queueing)

RR 큐잉에서 패킷들은 우선순위 큐잉과 같이 클래스로 분류됩니다. 하지만 클래스 간에 엄격한 우선순위가 존재하지 않으며, RR 스케줄러가 클래스 간에 서비스를 번갈아서 제공합니다. 예를 들어 RR 스케줄링에서는 클래스1 패킷이 전송된 다음에는 클래스2 패킷을 전송하고, 다시 클래스1 패킷 다음에 클래스2 패킷을 전송하는 식이죠. 

 

그리고 어떤 클래스의 패킷을 처리할 순서가 왔는데 해당 클래스가 비어있다면 바로 다음 클래스로 넘어가버리는데요. 이를 작업 보존(Work-conserving) 큐잉 규칙이라고 합니다.

 

아래 예시는 클래스1에 1, 2, 4번 패킷이 존재하고, 클래스2에 3, 5번 패킷이 존재하는 상황에서 라운드 로빈 스케줄링 시뮬레이션 그림입니다.

 

RR Scheduling

그림에서 클래스1에 속하는 1번 패킷을 보낸 다음에, 클래스 2번에 속하는 3번 패킷을 보내고 그 다음에 다시 클래스 1에 속하는 2번 패킷을 보내는 것을 확인할 수 있습니다.

 

 

한편, 라우터에서 널리 구현된 RR 큐잉의 일반적인 형태를 소위 WFQ(Weighted Fair Queueing) 규칙이라고 하는데요. RR 스케줄링에서처럼 WFQ 스케줄러는 순환 방식으로 동작하며 작업 보존 큐잉 규칙을 따릅니다. 다만, WFQ는 각 클래스마다 다른 양의 서비스 시간을 부여한다는 점에서 RR과 조금 차이점이 있죠. 각 클래스는 서로 다른 가중치를 부여받고, 해당 클래스에 속한 패킷이 처리되는 동안 클래스는 무조건 일정 시간만큼의 시간을 보장받습니다. 이 시간만큼은 Non-Preemtive 하다고 볼 수 있죠!

 

---

 

지금까지 라우터에서 발생할 수 있는 패킷 큐잉 지점들에 대해 공부해보고, 패킷 스케줄링 기법 세 가지를 살펴봤습니다.

 

각 패킷 스케줄링 방법에 따라서 패킷 지연과 패킷 손실이 얼마나 일어나는지에 대한 비교가 없어서 약간 아쉬움이 남는데요. 위에서 넘어갔떤 AQM 알고리즘이나 패킷 스케줄링 방법에 따른 특징에 대해서는 다른 포스팅에서 다시 정리해보도록 하겠습니다.

 

감사합니다.