Transcript Week11_2
Node Lookup in P2P Networks Node lookup in p2p networks • In a p2p network, each node may provide some kind of service for other nodes and also will ask other node for service. • The problem is to locate a node who provides the service I need. • In our project there is a central server who assigns nodes to others. Node lookup in p2p networks • P2P networks may have a very large number of nodes, such that a single central server may not be able to handle. • Besides, there are legal issues. • So, how to design lookup mechanism, such that I can find the node providing the service I need? • For simplicity, let’s use the same model as in our project – Each node may have some files, and the job is to find a node with the file I need. Node lookup in p2p networks • Any suggestions? • Ask the nodes in the network one-by-one? • Flood the network? – Flooding means everyone will be asking everyone Node lookup in p2p networks • Two costs we have to consider. – The lookup time – The number of messages sent • Assume that there is only one node with the file I need, what is the cost for – Linear search? – Flood? – Are they any good? The key idea • There is really not so much we can do if the network does not have a structure. • Introduce structure to the network. • Distributed Hash Table (DHT). Chord • Each node has a unique ID – By hashing its IP address by SHA-1 to get a 160-bit ID. • Each file also has a unique ID, called key. – By hashing the file name by SHA-1 to get a 160-bit ID. Chord • Successor of a key x or ID x. – Arrange the node as a circle. Start at x and travel clockwise. The first (real) node we visit is the successor of F. • The predecessor can be similarly defined. Chord • successor(F) is the node in charge of telling other people where to get F. • If a node has file F, it tells successor(F) that it has F. • So, if we can find successor(F), meaning that the IP address of it, we are done. Chord • How to find successor(F)? • Any suggestions? Chord • You know your location on the circle. You know the location of F on the circle. • If every node keeps the IP address of its neighbor on the circle, need to do a linear search. Chord • But we control what nodes should remember. • What do we want the nodes to remember, such that the searching time is small and the number of message is small? Chord • What Chord does is this. – remembering the successors of m locations if the node ID and key are m bits. • Consider a node with ID k. The ith entry of its Finger Table is the IP address of the successor of k+2i mod 2m. • Given this, how do you design the routing algorithm? Chord • Start with k as the routing point (RP). • If RP < F < successor(RP), successor(RP) = successor(F) and we are done. • Else, let the next RP be the one in the RP’s finger table that is the closest predecessor of F. Repeat. Chord • Chord needs O(m) routing steps. • The reason is every time, roughly speaking, the distance from the RP to the key is at least halved. – WLOG, suppose the current RP is 0, and F is between 2i and 2i+1. So if there is at least one valid node between 2i and F, we will go to such a node, distance is halved.