Abstract
隨著網際網路(Internet)的發達‚越來越多人開始在網際網路上分享彼此所擁有的資源(Resource)。這裡所提到的資源‚可以是檔案(file)、服務(Service)、或是電腦的運算能力。而眾多分享應用(application)中‚目前最熱門的是分享檔案(file)應用。在這些分享應用裡‚如何有效率找尋自己需要的資源‚則一直以來都是網路研究的重點項目之一。 傳統的搜尋架構‚主要是架構在要求-服務(Client-Server)的模式下‚也就是將所有可利用的資源索引於固定伺服器(Server)的資料庫中‚而資源要求者(Client)再透過伺服器搜尋自己需要的資源。但是這種架構存在著許多的缺點‚主要缺點在於容易因為單一伺服器的損壞‚而造成整個分享服務的中斷。除此之外‚在要求-服務的架構底下‚單一伺服器有限的硬體資源也會影響整個分享機制的效能。 對等式(Peer-to-Peer)的資源分享模式可以解決要求-服務模式的缺點。所謂的對等式架構‚相對於要求-服務架構而言‚即是沒有固定的伺服器做為分享資源的集中管理站‚所分享的資源平均存在於每個在對等式網路上的節點‚並不集中索引於固定的伺服器上。這裡所謂的節點可以是個人電腦、工作站、或是任何可以執行對等式服務軟體的網路終端設備。而當需要利用某項資源時‚則必須在對等式網路上搜尋所要的資源‚此時網路上的節點可以視需求扮演資源提供者(Server)、資源要求者(Client)、或為轉送訊息者(Router)。當本身無法提供別人欲搜尋的資源‚將訊息轉送其他節點以繼續搜尋時‚即是扮演Router角色。 目前有許多對等式網路分享架構在設計開發中。而不同的對等式網路分享架構‚有著不同的搜尋資源方式。我們將目前的對等式網路分享架構依其不同的搜尋資源方式分類‚大致上分類為兩種 Flooding-Based Resource-Locating 與 Routing-Based Resource-Locating 架構。所謂的Flooding-Based Resource-Locating‚即無法得知分享資源所存在的位址‚所以當我們搜尋資源時‚必須採用訊息洪流類(Flooding-Like)的搜尋方式‚廣泛詢問每個存在於對等式網路上的節點。而這類架構的代表為Gnutella[7]‚是目前已被廣泛使用的檔案分享系統。除此之外‚Freenet[6]利用深度優先搜尋方式在對等式網路上搜尋所需資源‚亦可歸屬於這一類架構。至於Routing-Based Resource-Locating‚則是每個欲分享的資源‚皆會利用雜湊函數(Hash Function)‚將資源名稱或代號對應到某個網路上的節點位址‚進而將分享資源的實體或是位址資訊(Location Information)配置在該節點位址所對應的節點上。所以當我們搜尋資源時‚若已知所需資源之名稱或代號‚則只需繞送(Route)到配置該資源資訊的節點上‚即可獲得該資源。而今屬於這種架構的有﹕Pastry、Tapestry、CAN 與 Chord[8,9,10,11]。 由於 Routing-Based Resource-Locating 架構能夠明確定址所分享的資源‚不需廣泛詢問所有節點‚所以比起 Flooding-Based Resource-Locating 架構‚Routing-Based Resource-Locating 架構在搜尋資源時‚會產生較少的網路流量(Network Traffic)。也因此‚多數研究試圖發展更有效率的 Routing-Based Resource-Locating 架構‚甚而有人提出改進 Gnutella 為近似於 Routing-Based Resource-Locating 架構的方法[17]。因為依分類‚Gnutella 原屬 Flooding-Based Resource-Locating架構。不過‚也由於 Routing-Based Resource-Locating 架構下的分享/搜尋機制‚依賴於利用雜湊函數‚將資源的名稱或是資源的代號明確對應到對等式網路上的節點位址‚而造成 Routing-Based Resource-Locating 架構無法提供較為彈性的搜尋方法‚例如﹕關鍵字搜尋。此處關鍵字搜尋的定義是在每筆資源皆擁有各自關鍵字集合(set)的情況下‚可透過關鍵字查詢相關的資源‚而此處每筆分享資源的關鍵字集合‚來源可以是資源名稱中有意義的子字串‚或是資源的 meta-data[26]‚ 而 meta-data 是用來描述資料的資料‚如﹕資料的提供者、資料型別或資料內容簡述等。 如何在 Routing-Based Resource-Locating 架構上提供關鍵字搜尋功能﹖此一問題‚目前並沒有學者提出相關的解決方法。我們將實際提出一個在 Routing-Based Resource-Locating 架構下提供關鍵字搜尋的機制‚用以解決原架構無法提供關鍵字搜尋的問題‚並分析此一機制對於原Routing-Based Resource-Locating 架構的影響。