P2P Computing Fundamentals Class Take Home Final
...factor to scale the Routing Table. 2) (25) Kademlia Discuss the main strength of the XOR metric in Kademlia as compared to the Lexicographic metric used in Pastry. In particular, describe the procedure for Join and Leave operations in a small network using each approach. Pastry uses prefix-based routing to map a key to a particular node. Each node that receives a message compares its nodeId to the key of the message. It then forwards the message to a node with a nodeId which shares a prefix with the key which is one digit more in length than its own shared prefix. If such a node is not in the routing table, the node forwards the message to a node with nodeId numerically closer, sharing the same length prefix. In this manner keys become mapped to nodes. Kademlia uses 160-bit nodeId and each node maintains 160 k-buckets (lists) each of max size k (replication parameter). Each bucket i, 0≤i<160, keeps info about nodes (sorted with most recently seen at the tail) within XOR metric distance of 2i and 2i+1. I think the main strength of the XOR metric in Kademlia is that distance between node not only works algebraically and also can be visualized into a tree so that it is more intuitive geometrically. Besides the main strength, it is symmetric and unidirectional which implies that lookups for a key converge along one path as a consequence of which caching along the path is necessary to tide over hot spots. . Kademlia has simple procedure for Join and no operation is needed for Leave. When a new node arrives, it joins with the a node that is already in the network and the new node will add the node just joined with to its k-buckets and then it will do a self-lookup, filling up all the buckets with its closest neighbors. In contrast, Pastry has a complicated procedure for Join. When new node joins Pastry, it would join with some node already on Pastry and initialized the Routing table with the node just joined with. Let node X be the new node and node A be the node you joined with, then X initializes its routing table by copying a row from the routing table of each of the other nodes along the path from A to the node with the closest nodeId to X. X must then inform all nodes in its tables about its state information. Upon node failure or departure, other nodes lazily update their leaf tables to reflect the change. Also, routing entries of other nodes are lazily updated by replacing the routing entries with suitable entries obtained from other nodes in their routing tables. Why Kademlia has a much simpler join algorithm is that it doesn’t have to get involved with a lot of nodes along the way of the node you are joining. Thanks to XOR-metric, it enables new node to peform a self lookup - (discovering the k closest neighbors to fill to k buckets) with just calculating XOR distance with the new node and insert the node found into the routing table. As XOR metric provides a good, easy-to-implement locality which Lexicographic metric couldn’t achieve, join operation for Kademlia is stable and efficient as opposed to Pastry’s Join, which is no guarantee and less efficient. 3) (25) Small-World Academic research on P2P has been focused mostly on DHTs and structured P2P networks. These architectures show great efficiency in routing but require fairly expensive network maintenance. Meanwhile, P2P networks actually in use today such as Edonkey/Emule, KaZaA, and WinMx/Limewire are based on Small-World models even though they serve communities with hundred thousand nodes. • Argue why the DHT-based P2P architectures are merely academic with little or no influence in the actual P2P marketplace. • Point out the main tradeoffs between DHT based approach and Small-World based approach in P2P routing. When are DHTs useful? HINT: Consult the paper "When Multi-Hop Peer-to-Peer Lookup Matters" presented in class on 5/26 (available from the class Calendar on CourseWeb or by CTRL-clicking here). The reason why DHT-based P2P architectures are merely academic is because it is not suitable for end-user P2P file sharing application. Since end-user tends to be on and off the internet very often, the cost of maintaining keys/replicas as well as routing table becomes a burden to the network and it would take too long to return the queries. The main tradeoffs of using DHT based approach is you get to choose between the routing table size and the network diameter. If we make a DHT-based P2P application, we are very likely to use multi-hop since one-hop is impractical considering that the “lifetime” of end-users is short and it will take forever to update it. So as it uses multi-hop, every node is responsible for routing messages. Especially if there is a file transferring between it incurs a lot of unwanted traffic to end-users which probably has narrower bandwidth relatively. So it is not efficient and has larger latency for end-user sharing application as compared to Small-World model. The small world model is the idea of keeping a relatively small routing table. In case of queries, you can only hope that your buddies (neighbors) know where to route your messages. The tradeoff made here is for unpopular contents that are actually on the small-world n...