在這篇博士論文中我們主要研究兩個課題，一個是有關於研究階層式非結構化同儕網路中有關超級同儕疊加網路的設計。一般的階層式非結構化同儕網路主要由超級同儕與一般同儕所組成，這種階層化的同儕網路可以改善既有同儕網路的效能。然而在設計最佳化的超級同儕網路時，需考慮許多因素，包括超級同儕的鄰居數，網路的直徑、網路的擴充性、負載平衡性及廣播查詢訊息的效能。因為完全差距網路可以滿足以上設計超級同儕疊加網路所需的特性，我們以完全差距網路動態地建構與維護超級同儕的網路拓樸，也使用完全差距網路為基礎的廣播演算法傳送查詢訊息，確保每一個超級同儕不會收到重複的查詢訊息。理論結果的分析證明所提出的方法可以有效改善現有超級同儕網路的效能，包括網路拓樸的直徑較小、產生較少的廣播查詢訊息與較少的傳送延遲等。實驗的結果也證明所提出的系統在超級同儕變動的網路中，可以表現很好的查詢效能。
另外本篇論文的另一個研究的課題是有關同儕式網路資料傳輸的研究，新式基於隨機線性編碼的資料傳輸系統，比傳統的資料轉傳的方式與來源編碼的方式有更好的傳輸效能。然而，此種系統需要較大的儲存空間、較高的計算能力與通訊成本。為了解決此一問題，我們提出了一個基於利他主義與重新編碼散播機制的資料傳輸系統。此一系統的原始檔案以所羅門的編碼方式編碼，以產生許多編碼區塊，想要下載此份原始檔案的同儕，利用利他主義的機制提出下載請求，此一下載請求所得到的編碼區塊，不僅對發出下載請求的同儕式是有用的，對此同儕的相鄰同儕也是有用的。當收到下載請求的同儕，依據重新編碼散播的機制，提供既有的編碼區塊或是利用拉格朗日的多項式插入法產生新的編碼區塊，提供給提出下載請求的同儕。根據利他主義與重新編碼散播的機制，系統可以快速地增加編碼區塊的多樣性，防止同儕離開網路後，剩下的同儕無法下載完整的編碼區塊。除此以外，此一提出的資料傳輸系統比線性編碼的資料傳輸系統具有更少的儲存空間、更低的計算與通訊成本，而且提供更有效率的傳輸方式。

In this dissertation, we investigate two research issues. One is about the super-peer overlay topology design in two-layer hierarchy unstructured peer-to-peer (P2P) systems, comprising an upper layer of super-peers and an underlying layer of ordinary peers. The two-layer P2P systems are commonly used to improve the performance of large-scale P2P systems. However, the optimal super-peer network design involves several requirements including super-peer degree, network diameter, scalability, load balancing, and flooding performance. A perfect difference graph has desirable properties to satisfy the above design rationale of super-peers overlay network. This dissertation proposes a two-layer hierarchical unstructured P2P system in which a perfect difference graph (PDG) is used to dynamically construct and maintain the super-peer overlay topology. In addition, the broadcasting performance of the P2P system is enhanced through the use of a PDG-based forwarding algorithm which ensures that each super-peer receives
just one lookup query flooding message. The theoretical results show that the proposed system improves existing super-peer hierarchical unstructured P2P systems in terms of a smaller network diameter, fewer lookup flooding messages, and a reduced average delay and the experimental results show that the proposed two-layer hierarchy P2P system performs very well in the dynamic network environment.
Other is about P2P content distribution systems. The systems based on random linear combination coding schemes outperform traditional block forwarding and source coding systems, but have large storage requirements and high computation and communication overheads. To resolve this problem, this dissertation presents an efficient, scalable P2P content dissemination system based on a novel altruistic demand mechanism and a recoding dissemination mechanism. In the proposed approach, the shared content file is segmented and encoded using Reed-Solomon code at a seed. Downstream peers wishing to obtain the file utilize an altruistic demand mechanism to issue demand requests for coded blocks which are useful not only to themselves, but also to their neighbors. Upon receiving these requests, the upstream peers utilize a recoding dissemination mechanism to provide the downstream peers with either an existing useful coded block or a new coded block produced using a Lagrange polynomial interpolation method. The two mechanisms rapidly increase the diversity of the coded blocks within the network and therefore provide an effective solution to the missing last block problem. In addition, it is shown that the proposed content distribution system demonstrates a substantial improvement over P2P systems based on random linear combination coding in terms of a lower storage requirement, reduced computation and communication costs, and an improved download efficiency.

[1] Testbed@TWISC - providing integrated access to a wide range of experimental environments: from simulated to emulated to wide-area network testbeds, http://testbed.ncku.edu.tw.
[2] MathWorld, http://mathworld.wolfram.com.
[3] P2P Simulator, http://www. omnetpp.org/index.php.
[4] Gnutella - A protocol for Revolution, http://rfc-gnutella.sourceforge.net.com/.
[5] KaZaA available at http://www.kazaa.com/.
[6] Overnet/edonkey2000, available at http://www. edonkey2000.com/.
[7] Bittorrent, available at http://bitconjurer.org/BitTorrent/.
[8] Knuth D., “The Art of Computer Programming, Vol. 2: Seminumerical Algorithms”, Addison-Wesley, 1969.
[9] Aho A., Hopcroft J. and Ullman J., “The Design and Analysis of Computer Algorithms”, Addison-Wesley, 1974.
[10] B. Bollobas, “Graph Theory: An Introductory Course”, New York: Springer-Verlag, 1979.
[11] B. Bollobs, “Random Graphs”, London: Academic Press, 1985.
[12] R. Lidl, and H. Niederreiter, “Introduction to Finite Fields and their Applications”, Cambridge University Press, 1994.
[13] Douglas B. West, “Introduction to Graph Theory”, Prentice-Hall Inc, 1996.
[14] L. N. Trefethen, and D. Bau, “Numerical Linear Algebra”, Society for Industrial and Applied Mathematics, 1997.
[15] James F. Kurose and Keith W. Ross, “Computer Networking: A Top-down Approach Featuring the Internet”, third edition, Addison Wesley, 2005.
[16] B. Parhami and M. Rakov, “Perfect Difference Networks and Related Interconnection Structures for Parallel and Distributed Systems”, IEEE Trans. on Parallel and Distributed Systems, vol. 16, no. 8,pp. 714-724, Aug. 2005.
[17] B. Parhami and M. Rakov, “Performance, Algorithmic, and Robustness Attributes of Perfect Difference Networks”, IEEE Trans. on Parallel and Distributed Systems, vol. 16, no. 8, pp. 725-736, 2005.
[18] Li Xiao, Zhenyun Zhuang, and Yunhao Liu, “Dynamic layer management in superpeer architectures”, IEEE Trans. on Parallel and Distributed Systems, vol. 16, issue, 11, pp. 1078-1091, Nov. 2005.
[19] J.-S. Li and C.-H. Chao, "An Efficient Super-Peer Overlay-Construction and Broadcasting Scheme Based on Perfect Difference Graph," IEEE Transactions on Parallel and Distributed Systems, 08 Jun. 2009. IEEE computer Society Digital Library, <http://doi.ieeecomputersociety.org/10.1109/TPDS.2009.94>.
[20] R. Ahlswede, N. Cai, S.-YR. Li and R. W. Yeung, “Network Information Flow”, IEEE Trans. on Information Theory, vol. 46, issue 4, pp. 1204-1216, July 2000.
[21] M. Luby, Mitzenmacher, A. Shorkollahi, and D. Speilman, “Efficient erasure correcting codes”, IEEE Trans. on Information Theory, vol. 47, issue 2, pp. 569-584, Feb. 2001.
[22] S-YR Li, R. W Yeung, and N. Cai, “Linear Network Coding”, IEEE Trans. on Information Theory, vol. 49, issue 2, pp. 371-381, Feb. 2003.
[23] A. Shokrollahi, “Raptor Codes”, IEEE Trans. on Information Theory, vol. 52, issue 6, pp. 2551-2567, June 2006.
[24] T.P. Kirkman, “On the Perfect r-Partitions of r2+r+1”. Trans. Historical Soc. of Lancashire and Cheshire, vol. 9, pp. 127-142, 1857.
[25] I. S. Reed and G. Solomon, “Polynomial codes over certain finite field”, Journal of the Society for Industrial and Applied Mathematics, pp. 300-304, June 1960.
[26] Leonard D. Baumert, “Cyclic Difference Sets”, Lecture Notes in Mathematics. Springer-Verlag, volume 182, 1971.
[27] Y. Dalal, R. Metcalfe, “Reverse Path Forwarding of Broadcast Packets”, Communications of the ACM, Vol.21, No12, pp. 1040-1048, Dec. 1978.
[28] R. G. Gallager, P. A. Humblet, and P. M. Spira, “A Distributed Algorithm for Minimum Weight-Spanning Trees”, ACM Trans. on Programming Languages and Systems, January 1983, pp.66-77.
[29] I. Stoica, and R. Morris et al., “Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications”, IEEE/ACM Trans. on Net., vol. 11, no. 1, pp. 17–32, 2003.
[30] B. Y. Zhao et al., “Tapestry: A Resilient Global-Scale Overlay for Service Deployment”, IEEE JSAC, vol. 22, no. 1, pp. 41-53, Jan. 2004.
[31] Y. Zhu, B.C. Li and J. Guo, “Multicast with network coding in application-layer overlay networks”, IEEE Journal on Selected Areas in Communication, Sep. 2004.
[32] Gedik, B., Liu, L., “A Scalable P2P Architecture for Distributed Information Monitoring Applications”, IEEE Transactions on Computers, vol. 54, issue 6, pp. 767 – 782, Jun. 2005.
[33] J. Yan, Y. Yang, and G. K. Raikundalia, “A SwinDeW p2p-based Decentralized Workflow Management System”, IEEE Trans. on Systems, Man and Cybernetics, Part A, Volume 36, Issue 5, pp. 922 – 935, Sept. 2006.
[34] C. Gkantsidis and P. Rodriguez, “Network Coding for Large Scale Content Distribution”, Volume 4, INFOCOM.2005.
[35] J. Byers, J. Considine, M. Mitzenmacher, and A. Rege, “A Digital Fountain Approach to Reliable Distribution of Bulk Data”, SIGCOMM, Sep. 1998.
[36] S. Ratnasamy et al., “A Scalable Content Addressable Network”, Proc. ACM SIGCOMM, pp. 161–72, 2001.
[37] J. Byers, J. Considine, M. Mitzenmacher, and S. Rost, “Useful content delivery across adaptive overlay networks”, SIGCOMM, 2002.
[38] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, “Making gnutella-like P2P systems scalable”, In proceedings of the ACM SIGCOMM 2003.
[39] D. Qiu and R. Srikant, “Modeling and Performance Analysis of BitTorrent like P2P File Sharing System”, SIGCOMM, Sep. 2004.
[40] C. Gkantsidis and P. Rodriguez, “Cooperative security for Network Coding File Distribution”, Tech. Rep. MSR-TR-2004-137, Microsoft Research 2004.
[41] A. R. Bharambe and C. Herley, “Analyzing and Improving BitTorrent Performance”, Tech. Rep. MSR-TR-2005-03, Microsoft Research 2005.
[42] Guy and R. K., “Unsolved Problems in Number Theory”, 2nd New York: Springer-Verlag, pp. 118-121, 1994.
[43] A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-peer Systems”, Proc. Middleware, 2001.
[44] C. Lv, P. Cao, E.Cohen, K. Li, and S. Shenker., “Search and replication in unstructured peer-to-peer networks”, In ICS, 2002.
[45] J. Chu, K. Labonte, and B. Levine, “Availability and Locality Measurements of Peer-to-Peer File Systems”, In SPIE, 2002.
[46] M. Luby, “LT Codes”, In Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 271-282, 2002.
[47] V. Kalogeraki, D. Gunopulos, and D. Zeinalipour-Yazti, “A Local Search Mechanism for Peer-to-Peer Networks”, In CIKM, 2002.
[48] B. Yang and H. Garcia-Molina, “Designing a Super-Peer Network”, Proc. 19th International Conf. Data Eng., Mar. 2003.
[49] D. Tsoumakos and N. Roussopoulos. “Adaptive Probabilistic Search for Peer-to-Peer Networks”, 3rd IEEE Intl Conference on P2P Computing, 2003.
[50] D. Kostic, A. Rodriguez, J. Albrecht, and A. Vahdat, “Bullet: High bandwidth data dissemination using an overlay mesh”, in Symposium on Operating Systems Principles (SOSP), 2003.
[51] Mizrak, A.T., Yuchung Cheng, Vineet Kumar, and Savage S., ”Structured superpeers: leveraging heterogeneity to provide constant-time lookup”, The third IEEE Workshop on Internet Applications WIAPP2003 Proceedings, pp. 104-111, June 2003.
[52] P.A Chou, Y.Wu, and K.Jain, “Practical Network Coding”, in Allerton, Oct.2003.
[53] Montresor, “A robust protocol for building superpeer overlay topologies”, Fourth International Conference on Peer-to-Peer Computing Proceedings, pp. 25-27, Aug. 2004.
[54] Y. J. Pyun, Reeves, and D.S., “Constructing a balanced, (log(N)/loglog(N))-diameter super-peer topology for scalable P2P systems”, Fourth International Conference on Peer-to-Peer Computing Proceedings, pp.210-218, Aug. 2004.
[55] K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim, “A survey and comparison of peer-to-peer overlay network schemes”, IEEE Communications Surveys & Tutorials, 2005.
[56] N. Christin, A. S. Weigend, and John Chuang, “Content availability, pollution and poisoning in file sharing peer-to-peer networks”, in the Proceedings of the 6th ACM conference on Electronic commerce, pp. 68-77, 2005.
[57] Lin Jenn-Wei, Yang Ming-Feng, Huang Chin-Yu, and Lin Chu-Ti, “Reliable Hierarchical Peer-to-Peer File Sharing Systems”, TENCON, 2006 IEEE Region 10 Conference, pp. 1-4, Nov. 2006.
[58] Saeyoung Han and Sungyong Park, “A Dynamic Layer Management Scheme for a Superpeer Ring with a Loosely Consistent DHT”, IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 383-386, Aug. 2007.
[59] R. W. Yeung, “Avalanche: A Network Coding Analysis”, NetCod 2007, San Diego, CA, Jan. 29, 2007.
[60] Watanabe, K., Hayashibara, N. Takizawa, “Performance Analysis of the Superpeer-based Two-layer P2P Overlay Network with the CBF Strategy”, ICDCSW ’07. 27th International Conference on Distributed Computing Systems Workshops, pp. 32-32, June 2007.