The interesting gaming company problem

Hi,

I was going through some online courses last week and hit this assignment. The problem was a good brushup in terms of some mathematical series involved . So enjoy !!

You own a large gaming company and want to distribute an update to all of your players. The size of the update is 1GB and your server can send data at up to 1GB/s. Your engineers have found that assuming every player can download at 1MB/s leads to very accurate estimates of network performance. Furthermore, they've found you can assume that the server splits its capacity evenly across clients. You have 100,000 players.

One of your engineers recommends that you distribute the update by having all users download the full file from your company's server. You walk through this calculation with the engineer and determine it will take 100,000 seconds (~28 hours) for all of your players to download the update. The server can support 1,000 players downloading the update at once by splitting its 1GB/s across 1,000 1MB/s clients. It will take 100 rounds of 1,000 players for everyone (all 100,000) to receive the update. As it takes 1,000 seconds for a 1MB/s connection to download 1GB, each round will take 1,000 seconds. 100 rounds of 1,000 seconds is 100,000 seconds, or 28 hours.

Another engineer recommends a different, peer-to-peer, strategy. In this strategy, players who have downloaded the patch allow other players to download it from them. So in the first round, 1,000 players download the patch from the server. In the second round, 1,000 new players download the patch from the server, and 1,000 new players pair with the first round downloaders. In the third round, 1,000 new players download the patch from the server, and 3,000 new players download the patch from players who have already downloaded it.

Calculate how long it will take until the last player to receive the update using the second strategy. How much faster is it than the first strategy?

Solution- Do not confuse the big nos here . Consider 1000 players to be a single unit that had total download capacity of 1 Gbps. So we have 100 such unit

Let us define 1 round as

1 round = 1 stream to get 1 Gb data @ 1Mbps = 1000 sec tp n no of subs               

Now for each round how many such set receive the msg

Round 1  - 1 (from server to 1 set)

Round 2 - 2 (1 from server and 1 from set that got in round 1)

...

Round n - 2 ^n-1

In how many such round will 100 unit get the data or

for which n will we have

Σ 2 ^n-1   > = 100

We know that 1 + 2 +4 + 2 ^n-1 < 2 ⁿ

For which n

 2 ⁿ   >=100

n = 7  (approx)

So total time taken = 7 x (time for 1 round)

                                       =  7 x 1000

                                      =  7000 sec approx