Automatically assigned DDC number: 00462

Manually assigned DDC number: 00543

Number of references: 4

Title: Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility

Author:

Author:

Subject: George Varghese,Tony Lauck Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility

Description: 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. This 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. 1 Introduction In a ...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1996-11-19

Pubyear: 1996

Format: ps

Identifier: http://citeseer.ist.psu.edu/144652.html

Source: http://www.ccrc.wustl.edu/~varghese/PAPERS/twheel.ps.Z

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/6291.html"   Type="inproceedings"   CiteSeer_Book="SIGCOMM"   CiteSeer_Volume=""   Title="{TCP}   Vegas:   New   Techniques   for   Congestion   Detection   and   Avoidance,">

            <identifier   Org="ISBN:047084468X"   Paper_ID="/6291.html"   Extracted="047084468X"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0471003972"   Paper_ID="/6291.html"   Extracted="0471003972"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0780339266"   Paper_ID="/6291.html"   Extracted="0780339266"   />

            <identifier   Org="ISBN:0824753216"   Paper_ID="/6291.html"   Extracted="0824753216"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:084931075X"   Paper_ID="/6291.html"   Extracted="084931075X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0849368383"   Paper_ID="/6291.html"   Extracted="0849368383"   DDC="621.382/12"   Normalized_DDC="62138212"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:1584884657"   Paper_ID="/6291.html"   Extracted="1584884657"   DDC="621.384"   Normalized_DDC="621384"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540200509"   Paper_ID="/6291.html"   Extracted="3540200509"   DDC="004.6/068"   Normalized_DDC="0046068"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540219595"   Paper_ID="/6291.html"   Extracted="3540219595"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540225714"   Paper_ID="/6291.html"   Extracted="3540225714"   DDC="621.382"   Normalized_DDC="621382"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540230343"   Paper_ID="/6291.html"   Extracted="3540230343"   />

            <identifier   Org="ISBN:3540232389"   Paper_ID="/6291.html"   Extracted="3540232389"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540235515"   Paper_ID="/6291.html"   Extracted="3540235515"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540244670"   Paper_ID="/6291.html"   Extracted="3540244670"   DDC="004.62"   Normalized_DDC="00462"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354025899X"   Paper_ID="/6291.html"   Extracted="354025899X"   DDC="004.678"   Normalized_DDC="004678"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540308814"   Paper_ID="/6291.html"   Extracted="3540308814"   DDC="004.16"   Normalized_DDC="00416"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540425225"   Paper_ID="/6291.html"   Extracted="3540425225"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354072589X"   Paper_ID="/6291.html"   Extracted="354072589X"   />

      </rec>

      <rec   ID="/19249.html"   Type="article"   CiteSeer_Book="IEEEslash   ACM   Transactions   on   Networking"   CiteSeer_Volume="5"   Title="A   reliable   multicast   framework   for   light-weight   sessions   and   application   level   framing,">

            <identifier   Org="ISBN:0387496890"   Paper_ID="/19249.html"   Extracted="0387496890"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0471466182"   Paper_ID="/19249.html"   Extracted="0471466182"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0849319854"   Paper_ID="/19249.html"   Extracted="0849319854"   DDC="670.42/7"   Normalized_DDC="670427"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0897917111"   Paper_ID="/19249.html"   Extracted="0897917111"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:0898713552"   Paper_ID="/19249.html"   Extracted="0898713552"   DDC="519.4/0285/51"   Normalized_DDC="5194028551"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:1581130368"   Paper_ID="/19249.html"   Extracted="1581130368"   DDC="006.7"   Normalized_DDC="0067"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:1930708149"   Paper_ID="/19249.html"   Extracted="1930708149"   />

            <identifier   Org="ISBN:1930708394"   Paper_ID="/19249.html"   Extracted="1930708394"   DDC="658.4038"   Normalized_DDC="6584038"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540001417"   Paper_ID="/19249.html"   Extracted="3540001417"   DDC="004.01/51"   Normalized_DDC="0040151"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540002669"   Paper_ID="/19249.html"   Extracted="3540002669"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540220607"   Paper_ID="/19249.html"   Extracted="3540220607"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540296417"   Paper_ID="/19249.html"   Extracted="3540296417"   DDC="004.6068"   Normalized_DDC="0046068"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540404562"   Paper_ID="/19249.html"   Extracted="3540404562"   DDC="004.67/8"   Normalized_DDC="004678"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540411402"   Paper_ID="/19249.html"   Extracted="3540411402"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540423028"   Paper_ID="/19249.html"   Extracted="3540423028"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540428240"   Paper_ID="/19249.html"   Extracted="3540428240"   DDC="004.69"   Normalized_DDC="00469"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540437096"   Paper_ID="/19249.html"   Extracted="3540437096"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540625739"   Paper_ID="/19249.html"   Extracted="3540625739"   DDC="004.6/185"   Normalized_DDC="0046185"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540658211"   Paper_ID="/19249.html"   Extracted="3540658211"   DDC="004.3"   Normalized_DDC="0043"   Normalized_Weight="0.05263157894736842"   />

            <identifier   Org="ISBN:3540673814"   Paper_ID="/19249.html"   Extracted="3540673814"   DDC="005.8"   Normalized_DDC="0058"   Normalized_Weight="0.05263157894736842"   />

      </rec>

      <rec   ID="/15205.html"   Type="inproceedings"   CiteSeer_Book="ACM   SIGCOMM   88"   CiteSeer_Volume=""   Title="Congestion   Avoidance   and   Control,">

            <identifier   Org="ISBN:0134722426"   Paper_ID="/15205.html"   Extracted="0134722426"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:0139738436"   Paper_ID="/15205.html"   Extracted="0139738436"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:0471330361"   Paper_ID="/15205.html"   Extracted="0471330361"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:0780349857"   Paper_ID="/15205.html"   Extracted="0780349857"   />

            <identifier   Org="ISBN:081862048X"   Paper_ID="/15205.html"   Extracted="081862048X"   />

            <identifier   Org="ISBN:084931075X"   Paper_ID="/15205.html"   Extracted="084931075X"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:1402062656"   Paper_ID="/15205.html"   Extracted="1402062656"   DDC="629.8"   Normalized_DDC="6298"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:1402075707"   Paper_ID="/15205.html"   Extracted="1402075707"   DDC="621.382/2"   Normalized_DDC="6213822"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:158053354X"   Paper_ID="/15205.html"   Extracted="158053354X"   DDC="621.382/12"   Normalized_DDC="62138212"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540225714"   Paper_ID="/15205.html"   Extracted="3540225714"   DDC="621.382"   Normalized_DDC="621382"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540233881"   Paper_ID="/15205.html"   Extracted="3540233881"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540244670"   Paper_ID="/15205.html"   Extracted="3540244670"   DDC="004.62"   Normalized_DDC="00462"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540253386"   Paper_ID="/15205.html"   Extracted="3540253386"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:354025899X"   Paper_ID="/15205.html"   Extracted="354025899X"   DDC="004.678"   Normalized_DDC="004678"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540408274"   Paper_ID="/15205.html"   Extracted="3540408274"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540418660"   Paper_ID="/15205.html"   Extracted="3540418660"   DDC="004.1/9"   Normalized_DDC="00419"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540427082"   Paper_ID="/15205.html"   Extracted="3540427082"   DDC="004.6/2"   Normalized_DDC="00462"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540729895"   Paper_ID="/15205.html"   Extracted="3540729895"   DDC="621.382"   Normalized_DDC="621382"   Normalized_Weight="0.0625"   />

            <identifier   Org="ISBN:3540766383"   Paper_ID="/15205.html"   Extracted="3540766383"   />

      </rec>

      <rec   ID="/63303.html"   Type="article"   CiteSeer_Book="IEEEslash   ACM   Transactions   on   Networking"   CiteSeer_Volume="1"   Title="Implementing   network   protocols   at   user   level,">

            <identifier   Org="ISBN:0387215093"   Paper_ID="/63303.html"   Extracted="0387215093"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:041271180X"   Paper_ID="/63303.html"   Extracted="041271180X"   DDC="004.62"   Normalized_DDC="00462"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0471139408"   Paper_ID="/63303.html"   Extracted="0471139408"   />

            <identifier   Org="ISBN:0780329635"   Paper_ID="/63303.html"   Extracted="0780329635"   />

            <identifier   Org="ISBN:0792385276"   Paper_ID="/63303.html"   Extracted="0792385276"   DDC="005.27/6"   Normalized_DDC="005276"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0792386906"   Paper_ID="/63303.html"   Extracted="0792386906"   DDC="004.62"   Normalized_DDC="00462"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0792395123"   Paper_ID="/63303.html"   Extracted="0792395123"   DDC="004.6/5"   Normalized_DDC="00465"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818672161"   Paper_ID="/63303.html"   Extracted="0818672161"   />

            <identifier   Org="ISBN:0818672935"   Paper_ID="/63303.html"   Extracted="0818672935"   />

            <identifier   Org="ISBN:0818674539"   Paper_ID="/63303.html"   Extracted="0818674539"   DDC="004.6/2"   Normalized_DDC="00462"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818676175"   Paper_ID="/63303.html"   Extracted="0818676175"   />

            <identifier   Org="ISBN:0818677929"   Paper_ID="/63303.html"   Extracted="0818677929"   DDC="004.35"   Normalized_DDC="00435"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:0818680628"   Paper_ID="/63303.html"   Extracted="0818680628"   />

            <identifier   Org="ISBN:081868142X"   Paper_ID="/63303.html"   Extracted="081868142X"   />

            <identifier   Org="ISBN:0897917111"   Paper_ID="/63303.html"   Extracted="0897917111"   DDC="004.6"   Normalized_DDC="0046"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:1880446766"   Paper_ID="/63303.html"   Extracted="1880446766"   />

            <identifier   Org="ISBN:3540584943"   Paper_ID="/63303.html"   Extracted="3540584943"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.1"   />

            <identifier   Org="ISBN:3540600426"   Paper_ID="/63303.html"   Extracted="3540600426"   DDC="004/.36"   Normalized_DDC="00436"   Normalized_Weight="0.1"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Hashed   and   Hierarchical   Timing   Wheels:   Efficient   Data   Structures   for   Implementing   a   Timer   Facility">

            <identifier   Org="ISBN:0201615894"   Paper_ID="SELF"   Extracted="0201615894"   DDC="005.7/1376"   Normalized_DDC="00571376"   Normalized_Weight="1.0"   />

            <identifier   Org="ISBN:3827373301"   Paper_ID="SELF"   Extracted="3827373301"   />

            <identifier   Org="ISBN:9043009865"   Paper_ID="SELF"   Extracted="9043009865"   />

      </rec>

</references_metadata>

www.000webhost.com