根據先前的研究顯示，在非結構疊蓋式網路系統(unstructured peer-to-peer system)上有超過70%的溝通路徑沒有好好利用真實網路層上的連線路徑，而發生以上的情形就是所謂的拓蹼不匹配問題(topology mismatch problem)，而拓蹼不匹配問題(topology mismatch problem)在疊蓋式網路會造成較長的溝通路徑(communication latencies)以及多餘的網路交通量(network traffics)。
先前有關於解決疊蓋式網路不匹配問題的研究並沒有提出各種效能保證的結果，這些效能參數包括疊蓋式網路上任意兩點間的溝通路徑距離和每個點的廣播範圍。
因此我們提出一個解決疊蓋式網路不匹配問題的演算法，這個方法能保證效能參數的品質。在這個演算法裡，每一個在疊蓋式網路的電腦都會用分散式的方法來建立和維護固定數量的連線。我們的研究顯示，(一)在同儕式網路上任兩台電腦之間的溝通路徑(communication delay)期望值為常數。(二)此外，每台電腦的廣播範圍(broadcasting scope)是以指數成長。(三)還有，每台電腦在加入這個同儕式網路且找到鄰近的電腦連線的花費(overhead)是對數成長。經由大量實驗模擬的結果發現，我們的方法不論是在平均的溝通路徑(communication delay)或廣播範圍(broadcasting scope)等效能參數都比THANCS和mOverlay這兩種方法優秀。

Abstract—Prior studies showed that more than 70% of communication
paths in a popular unstructured peer-to-peer (P2P)
system (i.e., Gnutella) do not exploit the physical network
topology, leading to the topology mismatch problem and thus
lengthy communication latencies and redundant network traffics.
While previous efforts in solving overlay topology matching
problems do not guarantee the bounds of performance metrics
(e.g., the communication delay between any two overlay peers and
the broadcasting scope of any participating peer), we in this paper
present a novel topology matching algorithm having the provable
performance qualities. In our proposal, each participating node
creates and manages a constant number of overlay connections
to other peers in a distributed manner. We show that (i) the
expected overlay communication delay between any two nodes
in our P2P network is a constant. (ii) In addition, any joining
node has the exponential broadcasting scope in expectation.
(iii) Furthermore, a participating node takes polylogarithmic
overhead to exploit the physical network locality and to maintain
its flooding scope. Through extensive simulations, our proposal
significantly outperforms two recent solutions, i.e., THANCS and
mOverlay, in terms of the overlay communication latency and/or
the broadcasting scope.

[1] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content-Addressable Network,” in Proc. ACM SIGCOMM’01, Aug. 2001, pp. 161–172.
[2] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications,” in Proc. ACM SIGCOMM’01, Aug. 2001, pp.149–160.
[3] A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems,” LNCS 2218, pp. 161–172, Nov. 2001.
[4] 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 J. Selected Areas in Comm., vol. 22, no. 1, pp. 41–53, Jan. 2004.
[5] Gnutella, http://rfc-gnutella.sourceforge.net/.
[6] M. Ripeanu, I. Foster, and A. Iamnitchi, “Mapping the Gnutella Network,” IEEE Internet Computing, vol. 6, no. 1, pp. 50–57, Jan./Feb. 2002.
[7] S. Sen and J. Wang, “Analyzing Peer-to-Peer Traffic Across Large Networks,” IEEE/ACM Trans. Netw., vol. 12, no. 2, pp. 219–232, Apr. 2004.
[8] Y. Liu, “A Two-hop Solution to Solving Topology Mismatch,” IEEE Trans. Parallel Distrib. Syst., 2008, (in press).
[9] Y. Liu, L. Xiao, X. Liu, L. M. Ni, and X. Zhang, Location Awareness in Unstructured Peer-to-Peer Systems,” IEEE Trans. Parallel Distrib. Syst., vol. 12, no. 2, pp. 163–174, Feb. 2005.
[10] C. Law and K.-Y. Siu, “Distributed Construction of Random Expander Networks,” in Proc. IEEE INFOCOM’03, Mar. 2003, pp. 2133–2143.
[11] G. Pandurangan, P. Raghavan, and E. Upfal, “Building Low-Diameter Peer-to-Peer Networks,” IEEE J. Selected Areas in Comm., vol. 21, no. 6, pp. 995–1002, Aug. 2003.
[12] M. K. Reiter, A. Samar, and C. Wang, “Distributed Construction of a Fault-Tolerant Network from a Tree,” in Proc. 24th IEEE Symp. Reliable Distributed Systems (SRDS’05), Oct. 2005, pp. 155–165.
[13] X. Zhang, Q. Zhang, Z. Zhang, G. Song, and W. Zhu, “A Construction of Locality-Aware Overlay Network: mOverlay and Its Performance,” IEEE J. Selected Areas in Comm., vol. 18, no. 28, pp. 995–1002, Jan. 2004.
[14] B. Bollob´as, Random Graphs, 2nd ed. Cambridge University Press, 2001.
[15] B. Bollob´as and W. F. de la Vega, “The Diameter of Random Regular Graphs,” Combinatorica, vol. 2, no. 2, pp. 125–134, June 1982.
[16] J. M. Kleinberg, “The Small-World Phenomenon: An Algorithm Perspective,” in Proc. 32nd ACM Annual Symp. Theory Computing (STOC’00), May 2000, pp. 163–170.
[17] S. Milgram, “The Small-World Problem,” Psychology Today, vol. 2, pp. 60–67, 1967.
[18] D. J.Watts and S. H. Strogatz, “Collective Dynamics of Small-World Networks,” Nature, vol. 393, pp. 440–442, June 1998.
[19] S. Merugu, S. Srinivasan, and E. Zegura, “Adding Structure to Unstructured Peer-to-Peer Networks: the Use of Small-World Graphs,” J. Parallel Distrib. Comput., vol. 65, no. 2, pp. 142–153, Feb. 2005.
[20] Y. K. Hui, C. S. Lui, and K. Y. Yau, “Small-World Overlay P2P Networks: Construction and Handling Dynamic Flash Crowd,” Computer Networks, vol. 50, no. 15, pp. 2727–2746, Oct. 2006.
[21] S. Wang, D. Xuan, and W. Zhao, “Analyzing and Enhancing the Resilience of Structured Peer-to-Peer systems,” J. Parallel Distrib. Comput., vol. 65, no. 2, pp. 207–219, Feb. 2005.
[22] L. Xiao, Y. Liu, and L. M. Ni, “Improving Unstructured Peer-to-Peer Systems by Adaptive Connection Establishment,” IEEE Trans. Computers, vol. 54, no. 9, pp. 1091–1103, Sept. 2005.
[23] S. Jiang, L. Guo, X. Zhang, and H. Wang, “LightFlood: Minimizing Redundant Messages and Maximizing Scope of Peer-to-Peer Search,” IEEE Trans. Parallel Distrib. Syst., vol. 19, no. 5, pp. 601–614, May 2008.
[24] T. Qiu, G. Chen, M. Ye, E. Chan, and B. Y. Zhao, “Towards Location-Aware Topology in both Unstructured and Structured P2P Systems,” in Proc. 36th Int’l Conf. Parallel Processing (ICPP’07), Sept. 2007.
[25] A. Crespo and H. Garcia-Molina, “Routing Indices for Peer-to-Peer Systems,” in Proc. 22nd IEEE Int’l Conf. Distributed Computing Systems (ICDCS’02), July 2002, pp. 23–32.
[26] K. Sripanidkulchai, B. Maggs, and H. Zhang, “Efficient Content Location Using Interest-Based Locality in Peer-to-Peer Systems,” in Proc. IEEE INFOCOM’03, Apr. 2003, pp. 2166–2176.
[27] Y. Zhu and Y. Hu, “Enhancing Search Performance on Gnutella-like P2P Systems,” IEEE Trans. Parallel Distrib. Syst., vol. 17, no. 12, pp. 1482–1495, Dec. 2006.
[28] E. Cohen, A. Fiat, and H. Kaplan, “A Case for Associative Peer to Peer Overlays,” ACM SIGCOMM Comp. Comm. Review, vol. 33, no. 1, pp. 95–100, Jan. 2003.
[29] L. Guo, S. Jiang, L. Xiao, and X. Zhang, “Fast and Low-Cost Search Schemes by Exploiting Localities in P2P Networks,” J. Parallel Distrib. Comput., vol. 65, no. 6, pp. 729–742, June 2005.
[30] Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, “Search and Replication in Unstructured Peer-to-Peer Networks,” in Proc. ACM Int’l Conf. Supercomputing (ICS’02), June 2002, pp. 84–95.
[31] H. Shen, C.-Z. Xu, and G. Chen, “Cycloid: A Scalable Constant-Degree Lookup-Efficient P2P Overlay Network,” Perform. Eval., vol. 63, no. 3, pp. 195–216, Mar. 2006.
[32] Z. Xu, C. Tang, and Z. Zhang, “Building Topology-Aware Overlays Using Global Soft-State,” in Proc. 23rd IEEE Int’l Conf. Distributed Computing Systems (ICDCS’03), May 2003, pp. 500–508.
[33] I. Abraham, D. Malkhi, and O. Dobzinski, “LAND: Stretch (1 + ") Locality Aware Networks for DHTs,” in Proc. 15th ACM-SIAM Symp. Discrete Algorithms (SODA’04), Jan. 2004, pp. 550–559.
[34] T. Locher, S. Schmid, and R. Wattenhofer, “eQuus: A Provably Robust and Locality-Aware Peer-to-Peer System,” in Proc. Sixth IEEE Int’l Conf. Peer-to-Peer Computing (P2P’06), Sept. 2006, pp. 3–11.
[35] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, “Topologically-Aware Overlay Construction and Server Selection,” in Proc. IEEE INFOCOM’02, June 2002, pp. 1190–1199.
[36] S. Ren, L. Guo, S. Jiang, and X. Zhang, “SAT-Match: A Self-Adaptive Topology Matching Method to Achieve Low Lookup Latency in Structured P2P Overlay Networks,” in Proc. 18th IEEE Int’l Parallel Distributed Processing Symp. (IPDPS’04)), Apr. 2004.
[37] L. Lov´asz, “Random Walks on Graphs: A Survey,” Combinatorics, Paul Erd´’os is Eighty, vol. 2,pp. 1–46, 1993.
[38] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge, 2005.
[39] V. King and J. Saia, “Choosing a Random Peer,” in Proc. 23rd ACM Symp. Principles Distributed Computing (PODC’03), July 2004, pp. 125–130.
[40] Z. Xu, M. Mahalingam, and M. Karlsson, “Turning Heterogeneity into an Advantage in Overlay Routing,” in Proc. IEEE INFOCOM’03, Mar. 2003, pp. 1499–1509.
[41] Y. Zhu and Y. Hu, “Efficient, Proximity-Aware Load Balancing for DHT-Based P2P Systems,”IEEE Trans. Parallel Distrib. Syst., vol. 16, no. 4, pp. 349–361, Apr. 2005.
[42] T. S. E. Ng and H. Zhang, “Predicting Internet Network Distance with Coordinates-Based Approaches,” in Proc. IEEE INFOCOM’02, June 2002, pp. 170–179.
[43] H. Zhang, A. Goel, and R. Govindan, “Improving Lookup Latency in Distributed Hash Table Systems Using Random Sampling,” IEEE/ACM Trans. Netw., vol. 13, no. 5, pp. 1121–1134, Oct. 2005.
[44] D. R. Karger and M. Ruhl, “Finding Nearest Neighbors in Growth-Restricted Metrics,” in Proc. 34th ACM Annual Symp. Theory Computing (STOC’02), May 2002, pp. 741–750.
[45] PlanetLab, http://www.planet-lab.org/.
[46] J. C. Chu, K. S. Labonte, and B. N. Levine, “Availability and Locality Measurements of Peer-to-Peer File Systems,” in Proc. SPIE—ITCom: Scalability and Traffic Control in IP Networks, July 2002, pp. 310–321.
[47] S. Saroiu, P. K. Gummadi, and S. D. Gribble, “Measurement Study of Peer-to-Peer File Sharing Systems,” in Proc. Ninth SPIE/ACM Multimedia Computing Networking (MMCN’02). Jan., 2002.
[48] Napster, http://www.napster.com/.
[49] 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-SharingWorkload,” in Proc. 19th ACM Symp. Operating Systems Principles (SOSP’03), Oct. 2003, pp. 314–329.
[50] S. Jin and H. Jiang, “Novel Approaches to Efficient Flooding Search in Peer-to-Peer Networks,” Computer Networks, vol. 51, no. 10, pp. 2818–2832, July 2007.
[51] W. Aiello, F. R. K. Chung, and L. Lu, “A Random Graph Model for Massive Graphs,” in Proc. 32th ACM Annual Symp. Theory Computing (STOC’00), May 2000, pp. 171–180.