Recently, real-time services over the Internet are becoming increasingly popular. A large number of real-time services will have made their way into homes and offices. Since real-time services need far more stringent QoS requirements than the typical sort of data applications, they should be guaranteed minimum bandwidth, jitter, and low end-to-end delays to each flow, regardless of the behavior of other flows. At the same time, data rates continue to increase past OC-12 or gigabit rates to OC-48 towards 10-gigabit Ethernet and the number of users is growing exponentially. All these factors make If QoS with the evolution of the Internet a challenging task.
Until now, many mechanisms have presented in order to support QoS guarantees at the network-level. These mechanisms include queuing, traffic scheduling, policing, shaping, and buffer management. It is interesting to observe, however, that the traffic scheduling of all mechanisms is the most critical function in achieving QoS guarantees. This dissertation is on the design, analysis, and implementation framework of traffic scheduling.
We first propose a new input arbitration mechanism to reduce synchronization effect of conventional input arbitration. This mechanism is based on a buffered crossbar switch with VOQ at the input. In the proposed method, the starting points of input modules are different from each other in any case. We evaluate the probability that input modules select cells destined for the same output. From the evaluated probability, we identify that the probability is maximized when the input starting points are same. Therefore, we show that the uniqueness of the starting points improves the switch performance. We also confirm the proposed method is better than the conventional methods under the uniform and on-off traffic by simulation.
Next, we propose an efficient and simple fair queuing algorithm, called new starting potential fair queuing (NSPFQ). Several algorithms using system virtual time of O(1) complexity have been devised, but none of these algorithms matches both delay and fairness properties of WFQ. The proposed NSPFQ scheduling algorithm has O(1) complexity for virtual time computation and also has good delay and fairness properties similar to WFQ. NSPFQ introduces a simpler virtual time recalibration method as it follows a rate-proportional property. The NSPFQ algorithm recalibrates the system virtual time to the minimum virtual start time among all possible virtual start times for head-of line (HOL) packets in backlogged sessions. Through analysis and simulations, we show that the proposed algorithm has good delay and fairness properties.
In the final part of the dissertation, we present an implementation framework for the NSPFQ scheduler and a priority queue architecture based on the pipelined heap manager. The proposed priority queue architecture defines three priority queue operations: insert, extract-min, and replace-min. It scales very well a large number of sessions and also reduces memory cost by using only inactive node count of left sub-tree.
최근에 인터넷을 통한 실시간 서비스에 대한 관심이 고조됨에 따라 가까운 시일 내에 다양한 실시간 서비스들이 가정이나 회사에서 제공될 것으로 예상된다. 실시간 서비스는 전형적인 데이터 응용 서비스보다 훨씬 더 엄격한 품질 보장을 요구하기 때문에 다른 세션의 행위에 영향을 받지 않아야 되며, 세션 별로 최소한의 대역, 지터 및 지연에 대한 요구 사항이 보장되어야 한다. 한편, 데이터의 전송 속도도 10Gb 이상으로 증가되고, 동시에 사용자의 수도 폭발적으로 증가되고 있는 추세이다.
현재까지 많은 메커니즘이 망 차원에서 QoS 보장을 제공하기 위하여 제시되어 왔다. 대표적인 망 차원의 QoS 메커니즘은 큐잉, 트래픽 스케줄링, 폴리싱, 세이핑, 그리고 버퍼 관리 등을 포함한다 그러나 그중에서도 트래픽 스케줄링이 QoS 보장을 달성하는데 가장 중요한 요소로 인식되고 있다.
따라서 본 논문은 입력 버퍼형 스위치 구조에서 동작되는 입력 스케줄링 (중재) 알고리즘과 출력 버퍼형 스위치 구조에서 동작되는 스케줄링 알고리즘, 그리고 스케줄링 알고리즘 구현을 위한 기본 구조를 제안하였다.
첫번째로 본 논문은 기존 입력 중재 메커니즘의 충돌 효과를 줄이기 위한 새로운 입력 중재 메커니즘을 제안하였다. 이 메커니즘은 입력에 가상 출력 큐와 버퍼를 가진 크로스 바 스위치 구조에서 동작된다. 제안한 입력 중재 방법은 모든 입력 포트의 출발점을 항상 다르게 지정한다. 충돌 효과란 두개 이상의 입력 포트가 동시에 같은 출력 포트로 패킷을 전달할 때 일어나는 것으로 그 중 하나만 출력 포트로 전달되기 때문에 스위치 성능에 악 영향을 준다. 본 논문에서는 충돌 현상이 나올 확률을 수학적으로 계산함으로써 충돌이 가장 많이 일어나는 경우를 찾아내고 이를 기반으로 새로운 스위치 성능 개선 방안을 제안하였다. 또한 유니폼 및 버스트 트래픽을 입력으로 하였을 때 스위치 성능면에서 제안한 메커니즘이 기존의 중재 방법 보다 우수함을 시뮬레이션을 통해 확인하였다.
다음으로 본 논문은 새롭고 효율적인 NSPFQ 스케줄링 알고리즘을 제안 하였다. 현재까지 연구되고 있는 스케줄링 알고리즘은 WFQ 와 유사한 성능을 유지하면서 시스템 가상 시간의 계산 복잡도를 줄이는데 노력해 왔다. WFQ 알고리즘은 실제적인 패킷 시스템에서 지연과 공정성의 성능이 가장 이상적인 것으로 알려져 있다. 그러나 $\emph{N}$개의 세션을 서비스하는 WFQ 알고리즘의 가상 시간 계산의 복잡도는 O($\emph{N}$)이며, 이는 고속 망에서의 구현을 어렵게 만든다. SCFQ 는 알고리즘 자체 내에서 생성되는 값을 이용하여 가상 시간을 계산하기 때문에 가상 시간의 계산 복잡도는 O(1)이다. 그러나 각각의 세션들간에 독립성을 가지지 못함으로서 지연의 한계가 세션의 수에 의존한다는 단점을 가지고 있다. SPFQ는 WFQ와 같은 지연의 한계를 가지고 있으며 WFQ와 유사한 공정성 지수를 가지고 있지만 가상 시간 계산을 위하여 최소의 가상 시작 시간 값을 필요로 하기 때문에 가상 시작 시간 값에 따르는 별도의 정렬 구조가 필요하며 결국 O($\emph{logN}$)의 가상 시간 계산 복잡도를 가지는 단점을 가지고 있다. 이와 같이 기존의 스케줄링 알고리즘은 시스템 가상 시간 계산의 복잡도를 O(1)으로 유지하면서 WFQ 와 비슷한 성능을 제시하지 못하였다.
그러나 본 논문에서 제안한 NSPFQ 는 가상 시간 계산의 복잡도를 O(1)으로 유지하면서, WFQ의 성능과 비슷한 결과를 나타낸다. NSPFQ는 현재 HOL에 위치하고 있는 모든 세션 들의 가능한 가상 시작 시간 중 최소의 가상 시작 시간을 시스템 가상 시간으로 재 조정한다. NSPFQ의 공정성 및 지연에 관한 성능은 해석을 통해 분석하였고, 시뮬레이션을 통해 NSPFQ의 성능을 확인하였다.
마지막으로 본 논문은 NSPFQ 스케줄링 알고리즘의 구현을 위한 기본 구조를 제안하고, 힙 기반의 우선 순위 구조를 제안하였다. NSPFQ는 각 세션별로 할당된 타임 스탬프의 증가 순으로 서비스를 한다. 그러나 수백만개의 세션 중 가장 작은 타임 스탬프를 고속으로 찾는다는 것은 매우 어려운 일이다. 본 논문에서는 파이프 라인 힙 메니저를 이용한 우선 순위 구조를 제안하고, 제안된 구조 상에서 동작되는 세 개의 우선 순위 동작을 (insert, extract-min, replace-min) 정의하였다. 제안한 힙 기반의 우선 순위 구조는 많은 세션에도 적용될 수 있는 확장성과 왼쪽 서브 트리의 비활성화 노드 수만을 이용한 알고리즘을 제안하여 메모리 비용을 절감하였다.
