Robust peer-to-peer protocols via randomized forwarding
Randy Howard Katz, Adam M. Costello · 2005
Forwarding is the relaying of a message from one machine (node) to another toward a destination, to provide a communication path between non-adjacent nodes. Forwarding services are traditionally designed to construct optimal paths, detect faults, then reconstruct the paths to route around the faults. Peer-to-peer systems, by using multi-hop forwarding to allow the peers to find each other as needed, enable large-scale reliable services to be built from many small diverse unreliable components, which makes faults more common and less predictable. To let these systems better tolerate faults we introduce randomized forwarding---peers retransmit messages along random paths rather than optimal paths, preemptively routing around faults without detecting them or waiting for paths to be reconstructed. We demonstrate this technique in two new protocols, Search Party and Rumor Mill, which use network-layer randomized forwarding to solicit local retransmissions for lost multicast packets; and in a third new protocol, Tangle, which uses application-layer randomized forwarding to find rendezvous points in a distributed hash table. Through analysis and experiments in these different problem domains we show that peer-to-peer protocols, by using randomized forwarding instead of deterministic forwarding, can pay a small performance penalty in exchange for a great improvement in fault tolerance. Internet applications have a long history of using both the client-server architecture, where a large central server provides a service to many independent clients, and the peer-to-peer architecture, where many small peers cooperate to provide a service to themselves by acting as both clients and servers to each other. Traditional Internet applications like file transfer, mail, Usenet, the domain name system, and chat have use a hybrid client-peer model where many unaffiliated always-running peers interact as both clients and servers to provide a service to an even larger number of short-lived strict clients. Other applications have used a pure peer-to-peer model, like the Mbone conferencing tools that use IP multicast rather than application servers to reach other interested nodes. Other applications, particularly the World Wide Web, have used a pure client-server model. The Web was so explosively successful, and the client-server model suddenly so dominant, that it seemed revolutionary when the peer-to-peer model reemerged with instant messaging and file-sharing systems. Developers and researchers turned to pure peer-to-peer systems to spread out the sometimes prohibitive cost of scaling up centralized services and to eliminate the single point of failure. (Abstract shortened by UMI.)