Gated-scheduling algorithms in packet switching networks
Resource
Computer Communications and Networks, 1999. Proceedings. Eight International Conference on
Journal
Computer Communications and Networks, 1999. Proceedings. Eight International Conference on
Pages
-
Date Issued
1999-10
Date
1999-10
Author(s)
Tsou, Fu-Ming
Tsai, Zsehong
DOI
N/A
Abstract
In this paper, two novel scheduling algorithms with low implementation complexity are investigated. Most scheduling algorithms proposed so far usually involve a sorting operation with the complexity of O(logN) per packet, where N denotes the number of connections sharing the link. To solve this problem, we propose two new scheduling algorithms with the complexity O(1), implemented with only a single FIFO queue in the output scheduler. The proposed scheduling algorithms make use of the concept of gated scheduling, and thus the schedulers are called gated-scheduling servers (GSS). The key contribution of the GSS algorithms is the successful elimination of output sorter in their designs such that the scheduling mechanism can accommodate a large number of flows. Both delay bounds and fairness index for flows scheduled under these two algorithms are validated with simulations.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
00805530.pdf
Size
569.22 KB
Format
Adobe PDF
Checksum
(MD5):16ea6634a0d3199a391ba76fc2e1e177