A Structured Overlay for Multi-Attribute Range Queries

Abstract

P2P 網路相關研究中，資源搜尋是一項重要的 課題，其中Chord 為常見的搜尋資源結構。Chord 利用 finger table 記錄節點與後繼節點之間的連結，建立結構化 overlay，使得資源搜尋可在O(log( N) )內完成(N 為節點總 數)。然而，當節點數越多時，Chord 維持overlay 的花費 也越大，而且Chord 僅針對關鍵字搜尋，限制了Chord 適用的環境。 本研究的目標為建構出一個適用於多種應用環境的 overlay。以Chord 為基礎，將節點屬性與節點ID 結合， 再根據屬性建置出一個多屬性、多環的結構化overlay。透 過多屬性階層式搜尋，不但可縮小搜尋範圍，還可提供多 重屬性搜尋的功能。而其多環架構亦可改善系統延展性、 減少overlay 維護的花費。在保留原來Chord 的特性下， 使用雙向連結結構，降低平均搜尋節點數，有效減少搜尋 時間，形成一個提供高靈活度，多屬性、範圍式搜尋的 overlay。本研究經OverSim 模擬實驗顯示確可縮短平均 搜尋節點數，減少資源搜尋時間。