Search Mechanism
Downloading a file in this network is performed by a flooding search for a peer containing this file.
Assume we want to download file f; the initiator peer will query all of its direct neighbours for f. Each of the neighbours will then do as follows:
- If it has f, it will notify the initiator.
- Otherwise, it will query its own neighbours for f.
This flooding scheme will have two main performance issues:
-
Each peer in the network might receive multiple messages corresponding to the same query, which results in processing an already served query.
-
A query might need to move along many peers to reach a node that contains the requested file.
We use two techniques to mitigate these problems:
-
Each query is associated with a random identifier; this will help peers to avoid serving the same query multiple times.
-
The master will keep the network topology close to a random graph; this helps us to keep the diameter of our network below a certain bound.
A random graph G(n, p) is a graph with n vertices, where any edge in G exists with the probability p.
Diameter of a graph G, denoted by d(G), is defined as follows:
where δ(u,v) is length of the shortest path between u, v in G.
For any positive value of p, d(G) will yield to 2 (refer to this link for a proof: https://math.stackexchange.com/a/1365333).
Using the above fact, we can ensure that d(G) is almost always small; so each flooding search will reach a peer that contains a file in few steps.
The master will keep the network topology close to a random graph;
the value for p is fixed and kept in the attribute prob_edge.