.png){kind=icon}
Return
Hashed and hierarchical timing wheels: Efficient data structures for implementing a timer facility
.png){kind=icon}
PRE
AI
DOI：10.1109/90.650142.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The performance of timer algorithms is crucial to many network protocol implementations that use timers for failure recovery and rate control, Conventional algorithms to implement an Operating System timer module take O(n) time to start or maintain a timer, where n is the number of outstanding timers: this is expensive for large n,;his paper shows that by using a circular buffer or timing wheel, it takes O(1) time to start, stop, and maintain timers within the range of the wheel, Two extensions for larger values of the interval are described. In the first, the timer interval is hashed into a slot on the timing wheel, In the second, a hierarchy of timing wheels with different granularities is used to span a greater range of intervals, The performance of these two schemes and various implementation tradeoffs are discussed. We have used one of our schemes to replace the current BSD UNIX callout and timer facilities, Our new implementation can support thousands of outstanding timers without much overhead. Our timer schemes have also been implemented in other operating systems and network protocol packages.
Keywords:
callout facilities
hashed wheels
hierarchical wheels
protocol implementations
Timers
Timer Facilities
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSaveShareSaveCALENDAR QUEUES - A FAST 0(1) PRIORITY QUEUE IMPLEMENTATION FOR THE SIMULATION EVENT SET PROBLEM
OAAI
OAAIShareSaveShareSaveShareSaveShareSave no more
no more