在非結構化的peer-to-peer系統中，大部分最被普遍使用的搜尋機制為Gnutella的blind flooding。在此機制中，節點將所收到的詢問訊息透過廣播的方式傳遞給其他logic neighbor。此詢問方式簡單，容易達成。然而，在搜尋過程中卻造成了大量不必要的流量以及節點收到多餘訊息等問題。 Li Xiao等學者在2005年提出Adaptive Connection Establish (ACE) 方法透過建構最小生成樹的overlay topology來增進搜尋的效率。ACE減少了傳遞訊息的流量而節點間亦不會收到多餘訊息，然而為了達到較好的效能，ACE需要大量額外的資訊交換以及龐大的運算量，因此造成節點相當大的負擔。 本論文提出了一個以Sollin演算法概念為基礎的方法來建構最小生成樹的overlay topology。透過本論文提及的演算法，每個節點只須針對logic neighbor進行資訊的交換和運算,而不須考慮logic neighbor以外的節點，因此可以大幅降低ACE中節點建構最小生成樹的負擔也使其能以較快的速度建構一個peer-to-peer環境下的最小生成樹overlay topology。 In unstructured P2P system, the most popular search mechanism being used is blind flooding of Gnutella. In this mechanism, nodes receive query messages and forward to other logic neighbor by broadcasting. This method is simple and easy to implement. However, there is a large amount of unnecessary traffic and will receive a lot of redundant messages in search process. In 2005, Li Xiao and other scholars propose the Adaptive Connection Establishment (ACE) to improve the search performance by building a Minimum Cost Spanning Tree (MST) in overlay network. ACE reduces the traffic cost and the nodes do not receive duplicate messages. However, to get a good performance, ACE needs a large amount of extra information exchanging and mass computation. Thus, ACE will has a high overhead on nodes. In this thesis, we propose an approach based on the concept of Sollin algorithm to build a MST in overlay network. By this approach, each node simply exchanges information and computes with all of its logic neighbors instead of considering other nodes. Thus, this approach can reduce the overhead of ACE significantly and build a MST more instantly.
