An Efficient Adaptive Search Algorithm for Scheduling Real-Time Traffic
Loading...
Authors
Xie, Geoffrey G.
Lam, Simon S.
Subjects
Advisors
Date of Issue
1996-10
Date
October 1996
Publisher
Language
Abstract
For many service disciplines that provide delay guarantees, the scheduler of a channel repeatedly searches for the smallest element in a set of priority values (or deadlines). It is required that each search finishes within a time bound. Furthermore, the search algorithm should be highly efficient. To meet these requirements, we have developed a search algorithm based upon a new data structure, called adaptive heap; it behaves like a heap most of the time, but adaptively changes its strategy when necessary to satisfy the time bound. We show that the algorithm has optimal worst case time complexity and good average performance. To further improve efficiency, the basic algorithm is extended to include the use of group scheduling. We present empirical results on the performance of adaptive heap search with and without group scheduling. We conclude that adaptive heap search performs as intended, and that group scheduling provides a substantial reduction in the scheduler’s work when channel utilization is high.
Type
Conference Paper
Description
Proc. Fourth IEEE International Conference on Network Protocols (ICNP), pp. 14-22, Columbus, OH, October 1996.
The article of record as published may be found at http://dx.doi.org/10.1109/ICNP.1996.564885
The article of record as published may be found at http://dx.doi.org/10.1109/ICNP.1996.564885
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funding
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.