Hierarchical packet fair queueing algorithms
| Autor: | Hui Zhang, Jon C. R. Bennett |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Queueing theory
business.industry Computer Networks and Communications Computer science Network packet Quality of service Computer Science Applications Scheduling (computing) Packet switching Server Resource allocation Resource management Electrical and Electronic Engineering business Packet fair queueing Algorithm Queue Generalized processor sharing Software Computer network Block (data storage) |
| Zdroj: | SIGCOMM |
| ISSN: | 1063-6692 |
| DOI: | 10.1109/90.649568 |
| Popis: | Hierarchical Packet Fair Queueing (H-PFQ) algorithms have the potential to simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link-sharing service. In this paper, we design practical H-PFQ algorithms by using one-level Packet Fair Queueing (PFQ) servers as basic building blocks, and develop techniques to analyze delay and fairness properties of the resulted H-PFQ servers. We demonstrate that, in order to provide tight delay bounds in a H-PFQ server, it is essential for the one-level PFQ servers to have small Worst-case Fair Indices (WFI). We propose a new one-level PFQ algorithm called WF 2 Q+ that is the first to have all the following three properties: (a) providing the tightest delay bound among all PFQ algorithms; (b) having the smallest WFI among all PFQ algorithms; and (c) having a relatively low implementation complexity of O(log N). We show that practical H-PFQ algorithms can be implemented by using WF 2 Q+ as the basic building block and prove that the resulting H-WF 2 Q+ algorithms provide similar delay bounds and bandwidth distribution as those provided by a H-GPS server. Simulation experiments are presented to evaluate the proposed algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|