An Efficient Adaptive Search Algorithm for Scheduling Real-Time Traffic
Xie, Geoffrey G.
Lam, Simon S.
MetadataShow full item record
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.
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
RightsThis 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.
Showing items related by title, author, creator and subject.
Das, Arijit (Monterey, California: Naval Postgraduate SchoolMonterey, California. Naval Postgraduate School, 2019-12); NPS-19-N065-AThe ExMCM is a broad program providing an innovative approach to the Mine Warfare mission area, required to operate with both U.S Navy and U.S. Marine Corps forces. The large number of sonar imagery files (from the MK18 ...
Rodrigues Neto, Jose Augusto (Monterey, California. Naval Postgraduate School, 1994-12);This thesis develops, implements and tests a mine search algorithm for the Naval Postgraduate School Autonomous Underwater Vehicle (Phoenix). The vehicle is 72 inches long and displaces 400 pounds. Its maneuvers are performed ...
Oral, Sabri Onur (Monterey, California. Naval Postgraduate School, 1991-09);The process of finding an exact minimization for a multiple-valued logic (MVL) expression requires an extensive search and enormous computation time. One of the heuristics to reduce this computation time is the Neighborhood ...