Jayanth Kumar Kannan and Matthew Chapman Caesar and Ion Stoica and Scott Shenker

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-22

January 31, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-22.pdf

DHT-based routing has been proposed recently in the literature and this new routing paradigm promises several advantages (\eg decreased state requirement) over conventional routing protocols. However, the robustness of such schemes is questionable given the difficulty of maintaining even overlay DHTs on Planetlab. In this work, we seek to address this issue head-on by taking the first steps towards a theory of the consistency of DHT-based routing. We do so by proposing the first {\it fully-decentralized maintenance algorithm} for DHT-based routing and then prove that it guarantees the property of {\it eventual consistency}. We then go on to explore a generalization of DHT-based routing, called a rendezvous service, and explain how routing protocols built using a rendezvous service may offer better convergence properties as compared to DHT-based routing. Although it is presently unclear whether DHT-based routing will ever be deployed in the Internet, we address one of the main technical objections against them: their perceived lack of robustness.

---

BibTeX citation:

@techreport{Kannan:EECS-2007-22,
    Author= {Kannan, Jayanth Kumar and Caesar, Matthew Chapman and Stoica, Ion and Shenker, Scott},
    Title= {On the Consistency of DHT-Based Routing},
    Year= {2007},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-22.html},
    Number= {UCB/EECS-2007-22},
    Abstract= {DHT-based routing has been proposed recently in the literature and this new routing paradigm promises several advantages (\eg decreased state requirement) over conventional routing protocols. However, the robustness of such schemes is questionable given the difficulty of maintaining even overlay DHTs on Planetlab. In this work, we seek to address this issue head-on by taking the first steps towards a theory of the consistency of DHT-based routing. We do so by proposing the first {\it fully-decentralized  maintenance algorithm} for DHT-based routing and then prove that it guarantees the property of {\it eventual consistency}. We then go on to explore a generalization of DHT-based routing, called a rendezvous service, and explain  how routing protocols built using a rendezvous service may offer better convergence properties as compared to DHT-based routing. Although it is presently unclear whether DHT-based routing will ever be deployed in the Internet, we address one of the main technical objections against them: their perceived lack of robustness.},
}

EndNote citation:

%0 Report
%A Kannan, Jayanth Kumar 
%A Caesar, Matthew Chapman 
%A Stoica, Ion 
%A Shenker, Scott 
%T On the Consistency of DHT-Based Routing
%I EECS Department, University of California, Berkeley
%D 2007
%8 January 31
%@ UCB/EECS-2007-22
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-22.html
%F Kannan:EECS-2007-22