패킷 스케줄링
- 큐에 있는 패킷이 출력 링크를 통해 전송되는 순서를 결정하는 방식
- 다양한 방식이 존재
FCFS(First-Come-First-Served)
- 라우터에서 일반적으로 사용되는 큐잉 처리 방법
- 흔히 FIFO(First-In-First-Out)으로 알려져 있음
FIFO 링크 스케줄링의 원리
FIFO
- 링크가 현재 다른 패킷을 전송 중인 경우, 출력 링크 큐에 도착한 패킷은 전송을 기다림
- 패킷이 출력되는 링크를 통해 완전히 전송되면, 큐에서 제거됨
- 패킷이 링크를 통해 완전히 전송된다 → 서비스를 받는 경우라는 뜻
- 도착한 패킷을 담을 버퍼 공간이 충분하지 않은 경우
→ 공간 확보를 위해 큐의 패킷 폐기 정책 사용
- 패킷 손실 여부 또는 다른 패킷을 큐에서 제거할 것인지 여부를 결정
- 아래에서의 FIFO 가정은 패킷 폐기를 무시한다고 가정
FCFS(FIFO) 스케줄링 규칙 및 동작
- 출력 링크 큐에 도착한 순서와 동일한 순서로 출력 링크에서 전송할 패킷 선택
FIFO 큐의 동작
FIFO와 관련된 표기
도착한 패킷 : 도착한 순서를 나타내는 숫자와 함께 상단 타임라인 위에 번호가 매겨진 화살표로 표시개별 패킷의 전송 : 하단 타임라인 아래에 표시패킷 전송 중 소비하는 시간 : 두 타임라인 사이의 사각형으로 표시
- 여기서는 패킷이 전송되는데 세 단위 시간이 걸린다고 가정
FIFO 큐의 동작 그림 해석
- FIFO에서는 패킷은 도착한 순서와 동일한 순서로 나가게 됨
- 패킷 4를 전송한 이후에 링크는 패킷 5가 도착할 때까지 유휴 상태로 유지
← 패킷 1 ~ 4까지 모두 전송되고 큐에 남아있는 패킷이 없는 상태이기 때문
우선순위 큐잉
우선순위 큐잉 스케줄링의 클래스 분류
- 출력 링크에 도착한 패킷은 큐에 도착하면 우선순위 클래스로 분류됨
- 실제 네트워크 오퍼레이터는 네트워크 관리 정보를 운반하는 패킷이
사용자 트래픽보다 우선순위를 수신하도록 큐를 구성할 수 있다.
- 예시
- 출발지 또는 목적지 TCP/UDP 포트 번호에 의해 지시되는 것과 같음
- 실시간 VoIP 패킷은 전자메일 패킷과 같은 트래픽보다 우선순위를 받을 수 있음
- 각 우선순위 클래스는 일반적으로 고유한 큐가 존재
패킷 전송 시
- 가장 높은 우선순위 클래스에서 패킷을 선택하여 전송
- 이때, 우선순위 큐는 전송 대기 중인 패킷으로 차 있는 상태
- 우선순위가 동일한 패킷이 여러 개 있을 때
→ 우선순위가 동일한 패킷들 중에서 선택은 FIFO 방식으로 행해짐
우선순위 큐잉 스케줄링의 동작
우선순위큐의 동작
가정
- 우선순위 클래스가 2개인 경우의 큐 동작
- 높은 우선순위 클래스에 속하는 패킷: 1,3,4
- 낮은 우선순위 클래스에 속하는 패킷 : 2,5
동작
- 패킷 1이 도착하고 링크가 사용 중이지 않으면 전송을 시작
- 패킷 1이 전송되는 중에 패킷 2,3이 도착하고 각각 우선순위가 낮은 큐에 대기
- 패킷 1이 전송된 후 패킷 3이 패킷 2보다 먼저 전송된다.
- 패킷 3의 전송이 끝나면 패킷 2의 전송을 시작
- 패킷 2의 전송 중에 패킷 4가 도착
- 우선순위 큐잉 정책에 따라 동작이 달라짐
비선점 우선순위 큐잉(non-preemptive priority queuing)인 경우
- 패킷 4의 우선순위가 높더라도, 이미 패킷 2가 전송 중이기 때문에 중단 X
- 패킷 4는 전송을 위해 대기
- 패킷 2의 전송이 종료된 이후 패킷 4의 전송이 시작됨
라운드 로빈과 WFQ
라운드 로빈 큐잉 규칙
- 패킷은 우선순위 큐잉과 같이 클래스로 분류됨
- 라운드 로빈 스케줄러가 클래스 간에 서비스를 번갈아가며 제공
작업 보존 큐잉(work-conserving queuing) 규칙
- 전송을 위해 큐에서 기다리는 패킷이 있다면 링크는 유휴 상태가 되는 것을 허용 X
- 클래스에서 패킷을 찾았지만 아무것도 찾지 못했을 때
→ 시퀀스의 다음 클래스를 즉시 검사
2개의 클래스 라운드 로빈 큐의 작동
2개의 라운드 로빈
가정
- 패킷 1,2,4는 클래스 1에 속함
- 패킷 3,5는 클래스 2에 속함
동작
- 패킷 1은 출력 큐에 도착하는 즉시 전송을 시작
- 패킷 1이 전송되는 동안 패킷 2,3이 도착하고 이들은 전송을 대기함
- 패킷 1의 전송이 완료되면 링크 스케줄러는 클래스 2 패킷을 찾음 → 패킷 3을 전송한다.
- 패킷 3의 전송이 완료되면 스케줄러는 클래스 1 패킷을 찾음 → 패킷 2를 전송
- 패킷 2의 전송이 완료되면 패킷 4만이 큐에 남음 → 바로 패킷 4를 전송
WFQ(Weighted Fair Queueing)
WFQ(Weighted Fair Queueing)
WFQ 동작
- 도착하는 패킷을 적절한 클래스별 대기 영역에서 분류 및 대기하게 함
- WFQ 스케줄러는 순환 방식으로 동작
- 라운드 로빈 스케줄링도 마찬가지
- 예시 - 클래스가 3개 있는 경우
- 클래스 1 → 클래스 2 → 클래스 3 순으로 동작하는 패턴 작업을 반복
- 작업 보존 큐잉 규칙임 → 빈 클래스 큐를 찾으면 서비스 순서에서 다음 클래스로 즉시 이동
WFQ와 라운드 로빈의 차이점
- WFQ는 각 클래스마다 다른 양의 서비스 시간을 부여받는다.
- 각 클래스 i는 w(i)(weight, 가중치)를 할당받는다.
- cf ) 라운드 로빈은 각 클래스에 모두 동일한 시간을 부여
- 전송률이 R인 링크에 대해 클래스 i는 항상 최소
w(i)/∑w(j)의 처리율을 갖는다.
- 전송할 클래스 i 패킷이 있는 동안, 클래스 i는
w(i)/∑w(j) 서비스 시간을 보장받음
∑w(j) : 전송을 위해 큐에 패킷이 있는 모든 클래스의 합
- 최악의 경우(모든 클래스가 큐에 패킷이 있을 때)
→ 클래스 i는 w(i)/∑w(j) 만큼을 사용할 수 있도록 보장받음
여기서 설명한 WFQ는 이상적인 것
- 여기는 패킷 전송이 다른 패킷을 전송하기 위해 방해되지 않는다는 사실을 고려하지 않았다.