EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management
EpiChord is a DHT lookup algorithm that demonstrates that we canremove the O(log n)-state-per-node restriction on existing DHTtopologies to achieve significantly better lookup performance andresilience using a novel reactive routing state maintenance strategythat amortizes network maintenance costs...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30493 |
| _version_ | 1811090786329034752 |
|---|---|
| author | Leong, Ben Liskov, Barbara Demaine, Erik D. |
| author2 | Programming Methodology |
| author_facet | Programming Methodology Leong, Ben Liskov, Barbara Demaine, Erik D. |
| author_sort | Leong, Ben |
| collection | MIT |
| description | EpiChord is a DHT lookup algorithm that demonstrates that we canremove the O(log n)-state-per-node restriction on existing DHTtopologies to achieve significantly better lookup performance andresilience using a novel reactive routing state maintenance strategythat amortizes network maintenance costs into existing lookups and byissuing parallel queries. Our technique allows us to design a newclass of unlimited-state-per-node DHTs that is able to adapt naturallyto a wide range of lookup workloads. EpiChord is able to achieveO(1)-hop lookup performance under lookup-intensive workloads, and atleast O(log n)-hop lookup performance under churn-intensiveworkloads even in the worst case (though it is expected to performbetter on average).Our reactive routing state maintenance strategy allows us to maintainlarge amounts of routing state with only a modest amount of bandwidth,while parallel queries serve to reduce lookup latency and allow us toavoid costly lookup timeouts. In general, EpiChord exploits theinformation gleaned from observing lookup traffic to improve lookupperformance, and only sends network probes when necessary. Nodespopulate their caches mainly from observing network traffic, andcache entries are flushed from the cache after a fixed lifetime.Our simulations show that with our approach can reduce both lookuplatencies and pathlengths by a factor of 3 by issuing only 3 queriesasynchronously in parallel per lookup. Furthermore, we show that weare able to achieve this result with minimal additional communicationoverhead and the number of messages generated per lookup is no morethan that for the corresponding sequential Chord lookup algorithm overa range of lookup workloads. We also present a novel token-passingstabilization scheme that automatically detects and repairs globalrouting inconsistencies. |
| first_indexed | 2024-09-23T14:51:55Z |
| id | mit-1721.1/30493 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:51:55Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/304932019-04-11T06:23:33Z EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management Leong, Ben Liskov, Barbara Demaine, Erik D. Programming Methodology EpiChord is a DHT lookup algorithm that demonstrates that we canremove the O(log n)-state-per-node restriction on existing DHTtopologies to achieve significantly better lookup performance andresilience using a novel reactive routing state maintenance strategythat amortizes network maintenance costs into existing lookups and byissuing parallel queries. Our technique allows us to design a newclass of unlimited-state-per-node DHTs that is able to adapt naturallyto a wide range of lookup workloads. EpiChord is able to achieveO(1)-hop lookup performance under lookup-intensive workloads, and atleast O(log n)-hop lookup performance under churn-intensiveworkloads even in the worst case (though it is expected to performbetter on average).Our reactive routing state maintenance strategy allows us to maintainlarge amounts of routing state with only a modest amount of bandwidth,while parallel queries serve to reduce lookup latency and allow us toavoid costly lookup timeouts. In general, EpiChord exploits theinformation gleaned from observing lookup traffic to improve lookupperformance, and only sends network probes when necessary. Nodespopulate their caches mainly from observing network traffic, andcache entries are flushed from the cache after a fixed lifetime.Our simulations show that with our approach can reduce both lookuplatencies and pathlengths by a factor of 3 by issuing only 3 queriesasynchronously in parallel per lookup. Furthermore, we show that weare able to achieve this result with minimal additional communicationoverhead and the number of messages generated per lookup is no morethan that for the corresponding sequential Chord lookup algorithm overa range of lookup workloads. We also present a novel token-passingstabilization scheme that automatically detects and repairs globalrouting inconsistencies. 2005-12-22T01:36:42Z 2005-12-22T01:36:42Z 2004-08-13 MIT-CSAIL-TR-2004-054 MIT-LCS-TR-963 http://hdl.handle.net/1721.1/30493 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 18 p. 27633175 bytes 1206942 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Leong, Ben Liskov, Barbara Demaine, Erik D. EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management |
| title | EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management |
| title_full | EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management |
| title_fullStr | EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management |
| title_full_unstemmed | EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management |
| title_short | EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management |
| title_sort | epichord parallelizing the chord lookup algorithm with reactive routing state management |
| url | http://hdl.handle.net/1721.1/30493 |
| work_keys_str_mv | AT leongben epichordparallelizingthechordlookupalgorithmwithreactiveroutingstatemanagement AT liskovbarbara epichordparallelizingthechordlookupalgorithmwithreactiveroutingstatemanagement AT demaineerikd epichordparallelizingthechordlookupalgorithmwithreactiveroutingstatemanagement |