Problem 24
Consider distributing a file of \(F\) bits to \(N\) peers using a client-server architecture. Assume a fluid model where the server can simultaneously transmit to multiple peers, transmitting to each peer at different rates, as long as the combined rate does not exceed \(u_{s^{*}}\) a. Suppose that \(u_{s} / N \leq d_{\min } .\) Specify a distribution scheme that has a distribution time of \(N F / u_{s^{*}}\) b. Suppose that \(u_{s} / N \geq d_{\min }\). Specify a distribution scheme that has a distribution time of \(F / d_{\min }\). c. Conclude that the minimum distribution time is in general given by \(\max \left\\{N F / u_{s}, F / d_{\min }\right\\} .\)
Problem 24
Consider a DHT with a mesh overlay topology (that is, every peer tracks all peers in the system). What are the advantages and disadvantages of such a design? What are the advantages and disadvantages of a circular DHT (with no shortcuts)?
Problem 25
Consider an overlay network with \(N\) active peers, with each pair of peers having an active TCP connection. Additionally, suppose that the TCP connections pass through a total of \(M\) routers. How many nodes and edges are there in the corresponding overlay network?
Problem 25
List at least four different applications that are naturally suitable for P2P architectures.
Problem 26
Suppose Bob joins a BitTorrent torrent, but he does not want to upload any data to any other peers (so called free-riding). a. Bob claims that he can receive a complete copy of the file that is shared by the swarm. Is Bob's claim possible? Why or why not? b. Bob further claims that he can further make his "free-riding" more efficient by using a collection of multiple computers (with distinct IP addresses) in the computer lab in his department. How can he do that?
Problem 29
Because an integer in \(\left[0,2^{n}-1\right]\) can be expressed as an \(n\)-bit binary number in a DHT, each key can be expressed as \(k=\left(k_{0}, k_{1}, \ldots, k_{\mathrm{n}-1}\right)\), and each peer identifier can be expressed \(p=\left(p_{0}, p_{1}, \ldots, p_{\mathrm{n}-1}\right)\). Let's now define the XOR distance between a key \(k\) and peer \(p\) as $$ \mathrm{d}(k, p)=\sum_{j=0}^{n-1}\left|k_{j}-p_{j}\right| 2^{j} $$ Describe how this metric can be used to assign (key, value) pairs to peers. (To learn about how to build an efficient DHT using this natural metric, see [Maymounkov 2002] in which the Kademlia DHT is described.)
Problem 30
As DHTs are overlay networks, they may not necessarily match the underlay 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?
Problem 34
We have seen that Internet TCP sockets treat the data being sent as a byte stream but UDP sockets recognize message boundaries. What are one advantage and one disadvantage of byte-oriented API versus having the API explicitly recognize and preserve application-defined message boundaries?
Problem 35
What is the Apache Web server? How much does it cost? What functionality does it currently have? You may want to look at Wikipedia to answer this question.
