Key-based routing enables massive, networked systems to direct messages to a node responsible for a resource and its key. Our thesis is that key-based routing (KBR) is a reliable primitive for large Internet services. Four issues are addressed. Firstly, most KBR schemes do not support strong routing consistency: routing is consistent when one and only one node delivers messages for a given key to the application layer. Inconsistent routing can cause application-layer performance problems and faults. The faulttolerant active rings (ftar) algorithm of this dissertation is unique in that it is fault-tolerant and it guarantees strong routing consistency: other algorithms either support probabilistic routing consistency or are not fault-tolerant. Routing tables are updated only after a joining or leaving node and its two immediate neighbors agree to the topology change. We formally specify, refine and prove the algorithm using the B Method. Secondly, algorithms are required to maintain one-hop KBR topologies reliably. One-hop topologies can give lower message latency and loss than topologies with small routing tables. Existing one-hop topologies with full routing tables have expensive repair mechanisms or critical points of failure. To avoid these problems, we contribute anti-entropy multicast (aecast), a reliable multicasting algorithm for one-hop topology maintenance. Aecast is compared with another epidemic multicasting algorithm, pbcast, by analysis and simulation; aecast gives at least fivefold fewer out-of-date nodes on average within one round of a topology update; faster updates improve routing performance. Thirdly, accurate analysis of lazy replica repair algorithms is required. Whereas the above algorithms maintain the topology, replication algorithms maintain data stored on the topology. One algorithm lazily repairs replicas when there is a membership timeout for failed nodes; the analysis ignored replica repair times and therefore overestimates availability. The Markov analysis here is more accurate. Fourthly, hierarchic topologies are reliable in that they protect the local topology from remote failures and network partitions; in existing designs, topology changes burden the top of the hierarchy. We devise a hierarchic architecture that avoids this problem.
| Identifer | oai:union.ndltd.org:ADTP/242691 |
| Date | January 2007 |
| Creators | Risson, John, Electrical Engineering & Telecommunications, Faculty of Engineering, UNSW |
| Publisher | Awarded by:University of New South Wales. School of Electrical Engineering and Telecommunications |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Copyright John Risson, http://unsworks.unsw.edu.au/copyright |
Page generated in 0.0019 seconds