A Routing System Using Minimum Starting-tag Fair Queueing

Abstract

Minimum Starting-tag Fair Queuing (MSFQ) is an efficient packet scheduling algorithm with theoretically proved in performance metrics such as delay bound, fairness, and time complexity. However, MSFQ algorithm didn’t have any implementation yet. In this paper, we established a configurable routing system based on Linux with MSFQ as the routing scheduling algorithm and provide an efficient way to build a testing environment. In the process of implementation, we designed and improved the internal part of data structures, embedded MSFQ algorithm into Linux kernel according to structures of Linux Network Traffic Control extended from Linux advanced routing project called iproute2. In order to boot MSFQ from kernel, we also modified ‘tc’ package in iproute2 project. An analysis model is built to evaluate the performance of proposed routing system. The comparison between MSFQ algorithm and other scheduling algorithms built in Linux kernel such as prio, sfq, etc. is also provided. The result of implementation proved the behaviors of MSFQ both theoretically and essentially. We also offered an easier and faster process to implement other algorithms so that any new algorithms will be implemented and analyzed more efficiently.