• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Robust Backup Path Selection in Overlay Routing with Bloom Filters

Vol. 7, No. 8, August 29, 2013
10.3837/tiis.2013.08.009, Download Paper (Free):

Abstract

Routing overlay offers an ideal methodology to improve the end-to-end communication performance by deriving a backup path for any node pair. This paper focuses on a challenging issue of selecting a proper backup path to bypass the failures on the default path with high probability for any node pair. For existing backup path selection approaches, our trace-driven evaluation results demonstrate that the backup and default paths for any node pair overlap with high probability and hence usually fail simultaneously. Consequently, such approaches fail to derive a robust backup path that can take over in the presence of failure on the default path. In this paper, we propose a three-phase RBPS approach to identify a proper and robust backup path. It utilizes the traceroute probing approach to obtain the fine-grained topology information, and systematically employs the grid quorum system and the Bloom filter to reduce the resulting communication overhead. Two criteria, delay and fault-tolerant ability on average, of the backup path are proposed to evaluate the performance of our RBPS approach. Extensive trace-driven evaluations show that the fault-tolerant ability of the backup path can be improved by about 60%, while the delay gain ratio concentrated at 14% after replacing existing approaches with ours. Consequently, our approach can derive a more robust and available backup path for any node pair than existing approaches. This is more important than finding a backup path with the lowest delay compared to the default path for any node pair.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
X. Zhou, D. Guo, T. Chen, X. Luo, "Robust Backup Path Selection in Overlay Routing with Bloom Filters," KSII Transactions on Internet and Information Systems, vol. 7, no. 8, pp. 1890-1910, 2013. DOI: 10.3837/tiis.2013.08.009.

[ACM Style]
Xiaolei Zhou, Deke Guo, Tao Chen, and Xueshan Luo. 2013. Robust Backup Path Selection in Overlay Routing with Bloom Filters. KSII Transactions on Internet and Information Systems, 7, 8, (2013), 1890-1910. DOI: 10.3837/tiis.2013.08.009.

[BibTeX Style]
@article{tiis:20348, title="Robust Backup Path Selection in Overlay Routing with Bloom Filters", author="Xiaolei Zhou and Deke Guo and Tao Chen and Xueshan Luo and ", journal="KSII Transactions on Internet and Information Systems", DOI={10.3837/tiis.2013.08.009}, volume={7}, number={8}, year="2013", month={August}, pages={1890-1910}}