Broadband integrated services packet networks rely on traffic scheduling algorithms within individual switches or routers to provide a wide range of Quality-of-Service (QoS) guarantees. The function of a scheduling algorithm is to select, for each outgoing link of the switch, the packet to be transmitted in the next cycle from the available packets belonging to the flows sharing the output link.
Weighted Fair Queueing (WFQ) is known as an ideal traffic scheduling algorithm in terms of its delay and fairness properties. However, timestamp computation in the WFQ scheduler serving N sessions has a complexity of O(N) per packet-transmission time which makes its implementation difficult. There have been efforts in the past to simplify the implementation of WFQ, such as Self-Clocked Fair Queueing (SCFQ), Starting Potential Fair Queueing(SPFQ), Minimum Delay Self-Clocked Fair Queueing (MD-SCFQ), etc. SCFQ is simpler and more feasible for high-speed implementation than WFQ since it is based on an internally generated virtual time, but it has unbounded delay property due to its poor isolation properties among sessions; SPFQ achieves the same delay bounds of WFQ and comparable fairness index to WFQ, but it needs selecting a new minimum virtual start time every time a packet completes service, thus requiring another sorting procedure according to the virtual start time of the packets and has a virtual time computation complexity of O($\log N$); MD-SCFQ also has the same delay bounds of WFQ and comparable fairness index to WFQ, but it needs to keep some information and perform additional calculations to obtain the weighted average virtual start time of packets in the head-of-line of each queue.
In this thesis we propose a new and efficient fair queueing algorithm, called Emulated Weighted Fair Queueing (EWFQ), which has a virtual time computation complexity of O(1), while it emulates perfectly the delay and fairness properties of WFQ. Key idea of EWFQ is that we recalibrate the system virtual time only at the end of each packet transmission using the same mechanism as applied to WFQ, while the system virtual time increases linearly with real time between two recalibration times of the system virtual time for a newly arrived packet, which is an important characteristic of Rate Proportional Schedulers (RPS). Therefore, EWFQ can emulate perfectly the delay and fairness performance of WFQ and the implementation complexity is drastically reduced to O(1).
We show that EWFQ has the same delay bound as that of WFQ by proving that EWFQ belongs to the RPS class and we give the fairness index of EWFQ in the explicit form to easily compare with fairness indices of existing algorithms.
We also present some simulation results for a multi-hop network configuration as well as for a single node to verify our analytical bounds and to compare the actual delays seen by sessions in realistic network topologies.
광대역 통합 서비스망은 다양한 범위의 서비스 품질(Quality of Service)을 제공하기 위하여 각각의 스위치 또는 라우터에서 트래픽 스케줄링 알고리즘을 필요로 한다. 스케줄링 알고리즘의 기능은 스위치의 각 출력링크에 대하여 그 링크를 공유하는 연결에 존재하는 패킷들 중 다음에 전송할 패킷을 선택하는 것이다.
Weighted Fair Queueing (WFQ) 알고리즘은 실제적인 패킷 시스템에서 지연과 공정성의 특징의 관점에서 이상적인 트래픽 스케줄링 알고리즘으로 알려져 있다. 그러나 N개의 세션을 서비스하는 WFQ 스케줄러의 가상시간 계산의 복잡도는 O(N) 이며 이는 고속의 망에서 구현상의 어려움을 가지고 있다. 지금까지 WFQ의 그러한 단점을 극복하기 위한 노력들이 존재해왔으며 대표적인 알고리즘으로 Self-Clocked Fair Queueing (SCFQ), Starting Potential Fair Queueing (SPFQ), Minimum Delay Self-Clocked Fair Queueing (MD-SCFQ) 등이 존재한다. SCFQ는 알고리즘 자체에서 생성되는 값을 이용하여 가상 시간을 계산하기 때문에 고속의 망에서 구현의 용이성을 가지고 있지만 각각의 세션들간에 독립성을 제공하지 못함으로서 지연의 한계가 세션의 수에 따라서 증가하는 단점을 가지고 있다. SPFQ는 WFQ와 같은 지연의 한계를 가지고 있으며 WFQ와 유사한 공정성 지수를 가지고 있지만 가상 시간 계산을 위하여 최소의 가상 시작 시간 값을 필요로 하기 때문에 가상 시작 시간 값에 따르는 별도의 정렬 구조가 필요하며 결국 O(\log N)의 가상 시간 계산 복잡도를 가지는 단점을 가지고 있다. MD-SCFQ 역시 WFQ와 동일한 지연 한계 및 공정성 특징을 가지고 있지만 가상 시작 시간의 가중 평균값을 구해야 하는 단점을 가지고 있다.
본 논문에서는 Emulated Weighted Fair Queueing (EWFQ)로 명명되는 새로운 Fair Queueing 알고리즘이 제안된다. EWFQ 알고리즘은 O(1)의 가상시간 계산의 복잡도를 가지고 있으며 WFQ 의 성능을 거의 완벽하게 에뮬레이션한다. EWFQ의 기본적인 아이디어는 Rate Proportional Schedulers (RPS) 클래스에 속하는 알고리즘의 기본적인 절차와 같이 매 패킷의 전송이 끝나는 시점에서 가상 시간의 재조정이 이루어 지며 두 가상시간 재조정 시간 사이에서는 실시간의 증가량으로 가상시간을 증가시킨다. 가상시간의 재조정은 WFQ와 같은 방법으로 가상 시간이 계산된다. 즉, 그 시점에서의 활성화된 세션(active session)들의 요구 속도의 합을 이용한다. 이렇게 함으로서 EWFQ 알고리즘은 WFQ가 가지는 가상 시간 계산의 복잡성을 줄였으며 WFQ의 성능을 에뮬레이트할 수 있다.
본 논문에서는 EWFQ 알고리즘이 RPS 클래스에 속하는 것을 보임으로써 EWFQ 알고리즘의 지연 특성이 WFQ와 같음을 보이며 공정성 지수를 계산하여 기존 알고리즘의 공정성 (fairness)와 비교하며 EWFQ 알고리즘의 공정성 지수는 WFQ의 공정성 지수에 상응하는 값을 가짐을 보인다.
또한, 단일 노드 환경과 다중 노드 환경하에서 수식적으로 계산된 지연 특성을 실제적인 망환경에서의 지연과 비교함으로써 수식적인 지연 한계를 확인하며 입력 트래픽의 버스트니스의 변화를 통하여 간접적인 방법으로 공정성을 비교하여 제안한 EWFQ 알고리즘의 공정성의 우수함을 보인다.