P2P 網路搜尋

在『6個人的小世界』這本書中,簡單的提到了一些網路搜尋的應用,其實這幾年當紅的 P2P 搜尋,在學術界也做了相當多的研究。

補充:有名的 BT client 軟體 BitComet 也推出無 SERVER 下載 tracker 種子檔的版本 (0.59)。詳細內容

近年來,在 serverless 網路搜尋 (P2P) 方面的研究可分為 brocasting 跟 structured 兩大範疇,brocasting以 Gnutella, Kazza…etc.為首, 而 structured 則有 Chord, CAN, Kad (emule) 等著名的 protocol。
Brocasting的立論基礎即為 small world, 以此來證明最終有很大的機率可以找到搜尋的標的。Gnutella 是最早被提出的系統,透過廣播的方式,要求資源的訊息會被散佈到有相連的節點上,每一個節點收到要求訊息會立刻檢查本身是否擁有要求的資源,如果存在的話則回傳訊息回去,否則就將要求訊息再散佈出去,一些改良 Gnutella 的系統則是增加所謂歷史紀錄,或是加上群組的機制,而每一個要求訊息都有一個存活期 (TTL) 的紀錄,一旦訊息流動的次數超過存活期則此要求訊息將被丟棄。
這一類的系統最大的好處是作到完全的分散式,每一個節點只需管理自己的資源,但是由於是採取廣播的方式,雖然每一個要求訊息會被存活期限制住,但在廣域網路上還是容易產生訊息氾濫的現象增加整個網路的負擔,其次由於存活期的限制可能造成每次只能搜尋到部分資源,或甚至找不到所需資源。
Gnutella
而 Structured 則是透過 hash function 以及特殊的 index 擺放方式來達到搜尋的目的,使用雜湊表與生俱來的好處,就是可以達到平衡負載 (Load Balancing),透過分散式雜湊表的方式,每一個節點及提供的資源都會經由雜湊函數 (Hash Function) 被轉換成一串的數值(索引值),這些索引值 s 會被放置於某一些特定的節點 s 上,當使用者想要搜尋一資源時,所輸入的資源資料會被轉換成索引值,透過分散式雜湊表的對應,便能很快的查詢到此資源的所在位置。
chord

如果您喜歡這篇文章,或覺得這篇文章對您有幫助,歡迎留言或利用左側按鈕分享。也別忘了可以訂閱本站 RSS 接收未來的更新唷!