Pre-order Deficit Round Robin: a new scheduling algorithm for packet-switched networks

檔案

日期

2001-02-01

類型

期刊名稱

COMPUTER NETWORKS-THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNICATIONS NETWORKING

卷期與頁次

第 35 卷第 2-3 期,頁 287–305

ISSN

1389-1286

語言

英文

摘要

In recent years, many packet fair queueing algorithms have been proposed to approximate generalized processor sharing (GPS). Most of them provide a low end-to-end delay bound and ensure that all connections share the link in a fair manner. However, scalability and simplicity are two significant issues in practice. Deficit Round Robin (DRR) requires only O(1) work to process a packet and is simple enough to be implemented in hardware. However, its large latency and unfair behavior are not tolerated. In this work, a new scheme, Pre-order Deficit Round Robin, is described, which overcomes the problems of DRR. A limited number, Z, of priority queues are placed behind the DRR structure to reorder the transmission sequence to approximate packet by packet generalized processor sharing (PGPS). We provide an analysis on latency and fairness, which shows our scheme as a better alternative to DRR. In most cases PDRR has a per-packet time complexity of O(1), and O(log Z) in other specific cases. Simulation results are also provided to further illustrate its average behavior. (C) 2001 Elsevier Science B.V, All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Tsao, S., & Lin, Y. (2001). Pre-order Deficit Round Robin: a new scheduling algorithm for packet-switched networks. COMPUTER NETWORKS-THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNICATIONS NETWORKING, 35(2-3), 287–305. https://doi.org/10.1016/S1389-1286(00)00172-9

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/29872