對於一個點對點同儕網路(P2P)而言，通常需要具備下列特性：可擴充性(scalability)、點和點之間的通訊延遲短，以及具有低的系統維護成本(system-wide overhead)。
以scalability而言，每個點只需維護整個P2P網路的一小部分資訊，並且只和少數的點相互連接；以快速通訊的目的而言，一個P2P網路會盡可能使任兩點之間的通訊延遲縮短；至於low system-wide overhead，一個P2P網路在維護系統效能以及系統功能的正確性時，須將網路流量抑制在最小。
本篇論文提出了一個scalable、具有短的通訊延遲，以及具有較低system-wide overhead的樹狀P2P網路，其優點包括下列：(1)分散式運作的樹狀P2P網路。(2)無論系統成長到多大，每個點的分支度過(degree)皆有很大機率會維持在常數，且此樹狀網路的網路直徑(diameter)隨著系統大小的成長，會以對數函數的等級增加，特別是當我們給定一個具有power-law latency expansion特性的實體網路時，我們可以證明此樹狀網路的直徑(diameter)為常數。(3)我們的提案中具有可驗證的效能保證。
我們以精確的效能分析來驗證提案，再以大量模擬實驗來輔助說明。

Keywords: peer-to-peer, overlay, diameter, degree, overhead

Peer-to-peer (P2P) networks often demand scalability, low communication latency among nodes, and low system-wide overhead. For scalability, a node maintains partial states of a P2P network and connects to a few nodes. For fast communication, a P2P network intends to reduce the communication latency between any two nodes as much as possible. With regard to a low system-wide overhead, a P2P network minimizes its traffic in maintaining its performance efficiency and functional correctness. In this thesis, we present a scalable tree-based P2P network with low communication delay and low system-wide overhead. The merits of our tree-based network include: (i) a tree-shaped P2P network which operates in a decentralized manner. (ii) It guarantees that the degree of a node is constant in probability regardless of the system size. The network diameter in our tree-based network increases logarithmically with an increase
of the system size. Specially, given a physical network with a power-law latency expansion property, we show that the diameter of our tree network is constant. (iii) Our proposal has the provable performance guarantees. We evaluate our proposal by rigorous performance analysis, and validate by extensive simulations.

Keywords: peer-to-peer, overlay, diameter, degree, overhead

[1] S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable Application Layer Multicast. In Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 205–217. ACM Press, August 2002.

[2] S. M. Banik, S. Radhakrishnan, and C. N. Sekharan. Multicast Routing with Delay and Delay Variation Constraints for Collaborative Applications on Overlay Networks. IEEE Transactions on Parallel and Distributed Systems, 18(3):421–431, March 2007.

[3] A. Bharambe, S. Rao, V. Padmanabhan, S. Seshan, and H. Zhang. The Impact of Heterogeneous Bandwidth Constraints on DHT-Based Multicast Protocols. In Proceedings of the International Workshop on Peer-to-Peer Systems. Springer Press, February 2005.

[4] M. Bishop, S. Rao, and K. Sripanidkulchai. Considering Priority in Overlay Multicast Protocols under Heterogeneous Environments. In Proceedings of IEEE INFOCOM, pages 1–13, March 2006.

[5] M. Castro, P. Druschel, A. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. SplitStream: High-bandwidth Content Multicast in a Cooperative Environment. In Proceedings of the Symposium on Operating Systems Principles, pages 298–313. ACM Press, October 2003.

[6] M. Castro, M. B. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman. An Evaluation of Scalable Application-Level Multicast Built Using Peer-to-Peer Overlays. In Proceedings of IEEE INFOCOM, pages 1510–1520, March 2003.

[7] C.Y. Chou, T.-Y. Huang, K.-L. Huang, and T.-Y. Chen. SCALLOP: A Scalable and Load-Balanced Peer-to-Peer Lookup Protocol. IEEE Transactions on Parallel and Distributed Systems, 17(5):419–433, May 2006.

[8] Y. Chu, S. Rao, and H. Zhang. A Case for End System Multicast. In Proceedings of the International Conference on Measurements and Modeling of Computer Systems, pages 1–12. ACM Press, 2000.

[9] S. El-Ansary, L. O. Alima, P. Brand, and S. Haridi. Efficient Broadcast in Structured P2P Networks. In Proceedings of the International Workshop on Peer-to-Peer Systems. Springer Press, February 2003.

[10] D. England, B. Veeravalli, and J. B. Weissman. A Robust Spanning Tree Topology for Data Collection and Dissemination in Distributed Environments. IEEE Transactions on Parallel and Distributed Systems, 18(5):608–620, May 2007.

[11] M. Faloutsos, P. Faloutsos, and C. Faloutsos. On Power-Law Relationships of the Internet Topology. In Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 251–262. ACM Press, August 1999.

[12] Gnutella. http://rfc-gnutella.sourceforge.net/.

[13] K. P. Gummadi, R. J. Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, and J. Zahorjan. Measurement, Modeling, and Analysis of a Peer-to-Peer File-Sharing Workload. In Proceedings of the Symposium on Operating systems principles, pages 314–329. ACM Press, October 2003.

[14] M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava. PROMISE: Peer-to-Peer Media Streaming Using CollectCast. In Proceedings of the International Conference on Multimedia, pages 45–54. ACM Press, November 2003.

[15] D. R. Karger and M. Ruhl. Finding Nearest Neighbors in Growth-Restricted Metrics. In Proceedings of the Annual Symposium on Theory of Computing, pages 741–750. ACM Press, May 2002.

[16] KaZaA. http://www.kazaa.com/.

[17] J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. OceanStore: An Architecture for Global-Scale Persistent Storage. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, pages 190–201. ACM Press, November 2000.

[18] J. Li, J. Stribling, T. M. Gil, R. Morris, and M. F. Kaashoek. Comparing the Performance of Distributed Hash Tables Under Churn. In Proceedings of the International Workshop on Peer-to-Peer Systems. Springer Press, February 2004.

[19] X. Liao, H. Jin, Y. Liu, L. M. Ni, and D. Deng. AnySee: Peer-to-Peer Live Streaming. In Proceedings of IEEE INFOCOM, March 2006.

[20] A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation. In Proceedings of the International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, pages 346–353, August 2001.

[21] M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge, 2005.

[22] T. S. Eugene Ng and H. Zhang. Predicting Internet Network Distance with Coordinates-Based Approaches. In Proceedings of IEEE INFOCOM, pages 170–179, June 2002.

[23] PlanetLab. http://www.planet-lab.org/.

[24] C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. In Proceedings of the Symposium on Parallel Algorithms and Architectures, pages 311–320. ACM Press, June 1997.

[25] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling Churn in a DHT. In Proceedings of the USENIX Annual Technical Conference, June 2004.

[26] S. M. Ross. Introduction to Probability Models. Academic Press, 2nd edition, 1980.

[27] A. Rowstron and P. Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems. Lecture Notes in Computer Science, 2218:161–172, November 2001.

[28] S. Saroiu, P. K. Gummadi, and S. D. Gribble. Measurement Study of Peer-to-Peer File Sharing Systems. In Proceedings of Multimedia Computing and Networking. January, 2002.

[29] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 149–160. ACM Press, August 2001.

[30] Y.-W. Sung, M. Bishop, and S. Rao. Enabling Contribution Awareness in an Overlay Broadcasting System. In Proceedings of the International Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 411–422. ACM Press, September 2006.

[31] D. A. Tran, K. A. Hua, and T. Do. ZIGZAG: An Efficient Peer-to-peer Scheme for Media Streaming. In Proceedings of IEEE INFOCOM, pages 1283–1292, March 2003.

[32] V. Venkataraman and P. Francis. Chunkyspread: Multi-tree Unstructured Peer-to-Peer Multicast. In Proceedings of the International Workshop on Peer-to-Peer Systems. Springer Press, February 2006.

[33] H. Zhang, A. Goel, and R. Govindan. Improving Lookup Latency in Distributed Hash Table Systems Using Random Sampling. ACM/IEEE Transactions on Networking, 13(5):1121–1134, October 2005.

[34] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A Resilient Global-scale Overlay for Service Deployment. IEEE Journal on Selected Areas in Communications, 22(1):41–53, January 2004.