Question regarding lower bound of P2P transmission delay of a file

Question regarding lower bound of P2P transmission delay of a file

by Devrim Celik -
Number of replies: 2

Hello,

I would love to get an intuition for the lower bound of the P2P transmission delay of a file. To be more more specific, I understand the following about the elements of the max function:

1. \frac{F}{u_s}: Just the time of Alice to upload her file [understood]

2. \frac{F}{d_{min}}: The download time of the end system with the slowest download speed [understood]

3. \frac{3*F}{u_s + \sum_i (d_i)}: Here lies the problem. While the first argument capture the uploading of the file and the second argument captures the initial distribution of the file fragements, this 3rd argument should capture the distribution of the file between the friends, given that each friend already has their file fragment. For a given friend, let's say Bob, this means that the distribution delay is max(\frac{2*F/3}{u_b}, \frac{F/3}{min(d_c, d_d)}. For all of the 3 friends that are going to distribute files this would mean the total distribution delay is:

max(\frac{2*F/3}{u_b}, \frac{F/3}{min(d_c, d_d)} + max(\frac{2*F/3}{u_v}, \frac{F/3}{min(d_b, d_d)} + max(2*\frac{F/3}{u_f}, \frac{F/3}{min(d_b, d_b)}

Now if we assume that the upload speed is generally much slower than the download speed, this would result in

= \frac{2*F/3}{u_b} + \frac{2*F/3}{u_c} + \frac{2*F/3}{u_d}

which is the closest I could get the supplied term (while assuming that the upload speed in not parallelized). I know that you said that this is just an approximation and maybe there is nothing more to be understood about it, but I'd love to get the a bit of a mathematically intuition. - I do not understand why Alice's upload speed is included in the distribution time, since (from what I can remember, and this might be wrong) it was said that the 3 friends divide the fragments between themselves.
- Also I am confused by the 3F: In terms of uploading, I would have argued that each friend needs to upload 2 file fragments (i.e. 2 * F/3) which they would do simultaneously...

I hope I was able to properly explain my confusion :)

In reply to Devrim Celik

Re: Question regarding lower bound of P2P transmission delay of a file

by Katerina Argyraki -

This is an excellent question, Devrim.

You are right, I did not clarify this point in class.

Notice the animation on the slide that shows the P2P  file distribution: Alice does not *only* participate in the first round. She participates in subsequent rounds as well, as needed. Basically, Alice first pushes one copy of the file to the rest of the peers. Then all the peers together *including Alice* continue to exchange pieces of the file until everyone has every piece.

You might ask: if Alice pushes more than 1 copy of the file into the network, why is the first term F/u_A? Because that's the *minimum* that she has to push -- she may have to push more. 

Here's a way to think about it:

  • What is the minimum that Alice must do? Push one copy of the file (but perhaps more) into the network.
  • What is the minimum that each peer must do? Pull one copy of the file from the network.
  • What is the minimum that *all the peers together including Alice* must do? Push N copies of the file into the network.

Each of these components may end up being the bottleneck.

Another way to think about it: The 1st and 3rd terms of the bound do not refer to two separate stages of the file distribution. The 3rd term may *subsume* the 1st one. 

Is this making any sense so far?

In reply to Katerina Argyraki

Re: Question regarding lower bound of P2P transmission delay of a file

by Devrim Celik -

Yeah it does, I think I get the idea now. Thanks a lot!