Exploring Tradeoffs in Failure Detection in Routing Overlays

Shelley Zhuang, Dennis Geels, Ion Stoica and Randy Katz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1285
October 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1285.pdf

One of the key reasons overlay networks are seen as an excellent platform for large scale distributed systems is their resilience in the presence of node failures. This resilience rely on accurate and timely detection of node failures. Despite the prevalent use of keep-alive algorithms in overlay networks to detect node failures, their tradeoffs and the circumstances in which they might best be suited is not well understood. In this paper, we study how the design of various keep-alive approaches affect their performance in node failure detection time, probability of false positive, control overhead, and packet loss rate via analysis, simulation, and implementation. We find that among the class of keep-alive algorithms that share information, the maintenance of backpointer state substantially improves detection time and packet loss rate. The improvement in detection time between baseline and sharing algorithms becomes more pronounced as the size of neighbor set increases. Finally, sharing of information allows a network to tolerate a higher churn rate than the baseline algorithm.


BibTeX citation:

@techreport{Zhuang:CSD-03-1285,
    Author = {Zhuang, Shelley and Geels, Dennis and Stoica, Ion and Katz, Randy},
    Title = {Exploring Tradeoffs in Failure Detection in Routing Overlays},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Oct},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6366.html},
    Number = {UCB/CSD-03-1285},
    Abstract = {One of the key reasons overlay networks are seen as an excellent platform for large scale distributed systems is their resilience in the presence of node failures. This resilience rely on accurate and timely detection of node failures. Despite the prevalent use of keep-alive algorithms in overlay networks to detect node failures, their tradeoffs and the circumstances in which they might best be suited is not well understood. In this paper, we study how the design of various keep-alive approaches affect their performance in node failure detection time, probability of false positive, control overhead, and packet loss rate via analysis, simulation, and implementation. We find that among the class of keep-alive algorithms that share information, the maintenance of backpointer state substantially improves detection time and packet loss rate. The improvement in detection time between baseline and sharing algorithms becomes more pronounced as the size of neighbor set increases. Finally, sharing of information allows a network to tolerate a higher churn rate than the baseline algorithm.}
}

EndNote citation:

%0 Report
%A Zhuang, Shelley
%A Geels, Dennis
%A Stoica, Ion
%A Katz, Randy
%T Exploring Tradeoffs in Failure Detection in Routing Overlays
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1285
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/6366.html
%F Zhuang:CSD-03-1285