Peer-to-peer applications: class #1

Material:

Example of analysis of unstructured p2p system.

(Note that I'm using the initial definition for pi, not the one the professor changed to at midclass)

Nodes cache copies of the files. The more copies the shorter the search. Caches have limited sizes (one peer cannot store everything).

Files have different popularity

  • m objects, n peers, each peer can store c files (total capacity of the system is cn)
  • qi is the request rate of object i, the number of times file i is asked for by users. $q_i \leq q_{i+1}$.
  • pi is the fraction of the total storage space used to store file i. $\sum^m_{i=1} p_i = 1$
  • At each round a user asks to a peer chosen uniformly at random for an object i (no memory).

How to choose the pi?

Spirit: files more frequently asked for should have more copies.

How to implement that in a distributed way?

  • What is the expected lenght (s) of a search for object i?
  • What is the global network bandwidth (b) used to search for all objects?
  • Allocations used in practice.
    1. Uniform: $p_n = \frac 1 m \ \forall m$
    2. Proportional: $p_i = a q_i$, where $a = \frac 1 {\sum^m_{i=1} q_i}$ is a normalization function.
  • How do you implement these policies in practice?
  • What do you expect? Which is better?
  • What is b for these two policies.
  • Conclude: can you do better?

What is the probability of finding the object after j trials? $P[s = j]$

The expectation of finding the object in j trials is $E[s] = \sum P[s = j] j$

Probability of not finding the file: $q_i = 1 - p_i$

(1)
\begin{eqnarray} P[s = 1] & = & p_i \\ P[s = 2] & = & q_i p_i \\ P[s = 3] & = & q_i^2 p_i \\ P[s = j] & = & q_i^{j-1} p_i \\ \\ E[s] & = & \sum_{j=1}^\infty j q^{j-1} p \\ \\ \textrm{If} ~ M & = & \sum_{j=0}^\infty q^j = \frac 1 {1-q} \\ \\ \Rightarrow \frac {\delta M} {\delta q} & = & \sum_{j=1}^\infty j q^{j-1} = \frac 1 {(1-q)^2} \\ \\ \Rightarrow E[s] & = & \frac p {(1 - q)^2} = \frac 1 p \qquad [ q = 1 - p ] \\ \end{eqnarray}

2. Bandwidth of searching for all objects (but not just once!)

(2)
\begin{align} B = \sum_{i=1}^m \frac {q_i} {p_i} \end{align}

For the uniform case, $p_1 = \frac 1 m$

(3)
\begin{align} B = \sum_{i=1}^m q_i m = \frac m a \end{align}

For proportional, $p_i = a q_i$

(4)
\begin{align} B = \sum_{i=1}^m \frac 1 {a _i} = \frac m a \end{align}
Unclear, need to ask the teachers, since most is obviously derived works.