Question
As DHTs are overlay networks, they may not necessarily match the under-lay physical network well in the sense that two neighboring peers might be physically very far away; for example, one peer could be in Asia and its neighbor could be in North America. If we randomly and uniformly assign identifiers to newly joined peers, would this assignment scheme cause such a mismatch? Explain. And how would such a mismatch affect the DHT’s performance?
Answer
Yes, randomly assigning keys to peers does not consider the underlying network at all, so it very likely causes mismatches.
Such mismatches may degrade the search performance. For example, consider a logical path p1 (consisting of only two logical links): ABC, where A and B are neighboring peers, and B and C are neighboring peers. Suppose that there is another logical path p2 from A to C (consisting of 3 logical links): ADEC.
It might be the case that A and B are very far away physically (and separated by many routers), and B and C are very far away physically (and separated by many routers). But
it may be the case that A, D, E, and C are all very close physically (and all separated by few routers). In other words, a shorter logical path may correspond to a much longer physical path.