The internet is overwhelmed with traffic, with user demand for bandwidth well in excess of supply and there is bottleneck in router. In order to improve the performance of router, the efficiency of packet scheduling algorithm in scheduler and buffering policy in each I/O port are important.
It has been recently shown that an input-queued switch with an appropriate buffering policy (for example, VOQ; Virtual Output Queueing) and scheduling algorithm (for example, maximum weight matching algorithm) can achieve 100% throughput for independent arrival processes in theory.
Since Maximum Weight Matching algorithm is too complex to implement in hardware, previous work proposed i-MWM (iterative Maximal Weight Matching) to implement simply in hardware. Port partitioning concept is employed to reduce the computational burden of the scheduler within a switch. The input and output ports are divided into two groups such that the matching algorithm is implemented within each group in parallel. The matching is performed by exchanging input and output port groups at every time slot to handle all incoming traffics. Two algorithms, maximal weight matching by port partitioning (MPP) and modified maximal weight matching with port partitioning (MMPP) are presented. MMPP has the lowest delay for every packet arrival rate. The buffer size on a port is approximately 20-60 packets depending on the packet arrival rates. The throughput is illustrated to be linear to the packet arrival rate, which can be achieved under highly efficient matching algorithm.
And this thesis proposes also Dynamic queue scheduling algorithm to support the utility of both DC (Delay-Critical) and LC (Loss-Critical) packets simultaneously.
인터넷의 급격한 발전으로 LAN 에서 외부로 나가는 트래픽 량이 폭발적으로 증가하게 되었다. 따라서 라우터 (router) 에서의 체증현상은 당연히 발생하게 된다. 본 논문에서는 라우터의 성능을 향상시키기 위한 방안에 대해서 연구했다. 그리고 특히 wirespeed 스위치에서 스위치의 성능을 향상시키기 위한 방안에 대해서 연구해 보았다. 그 방안으로 패킷을 스위칭할 때 효율적으로 하기위한 스케쥴링 알고리즘에 대해 조사하고 비교한 후 새로운 스케쥴링 알고리즘을 제시했다.
그 결과 본 연구에서 제시한 MPP (i-MWM-by-Port Partitioning)와 MMPP (Modified-i-MWM-by-Port-Partitioning) 알고리즘이 기존의 i-MWM (iterative Maxmal Weight Matching) 보다 더 좋은 성능을 나타내는 것으로 나타났다.
그리고, 여러 가지 종류의 트래픽을 가정 했을 때, 적절한 QoS (Quality of Service)를 보장 하면서 전체적으로 효용을 극대화 하는 동적 대기행렬 스케쥴링 알고리즘 (Dynamic Queue Scheduling Algorithm) 을 제시 했다. 동적 알고리즘은 어떤 한 종류의 트래픽량이 늘어나도 전체적으로 효용을 극대화 하는 알고리즘이다.
