P2P－Chord

Chord [7]是由麻省理工學院所提出的lookup（key）的演算法，其建立拓樸的方式主要是將每一個加入節點IP 位址利用雜湊函數（Hashing function），產生一個節點代碼（Node ID），這個代碼會對應到一個由N 個整數所形成的邏輯代碼環（identifier circle），代表節點的位置，如圖 2-1 所示，N1、N8、…、N51等節點，即是透過雜湊函數產生代碼，並對應到邏輯代碼環上的位置概念圖。當所加入的節點將檔案分享到Chord 的系統時，Chord 也是利用雜湊函數將所分享的檔案產生代碼，對應到環狀代碼環上的節點儲存起來。例如代碼為1的檔案，則儲存在節點代碼1 中，代碼為2~8 的檔案則儲存在節點代碼8 中，依此類推。為了加快檔案搜尋的速度，每個節點都會維護一個路由表（Fingertable），路由表內所記錄的為每個節點的次節點（successor）的位置，所謂次節點就是沿著邏輯代碼環順時鐘方向前進所遇到的第一個節點，紀錄次節點的內容為（ n + 2i−1 ），n 為該節點的代碼，1≤ i ≤ logN 。因此，當節點搜尋檔案時，則利用代碼來比對節點中的路由表，進行繞送。我們以圖 2-1 舉例說明，當節點代碼8 要搜尋檔案代碼42 時，節點代碼8 則透過節點中的路由表，開始尋找檔案存在的位置。



圖 2-1 的繞送表中，我們可以知道到N8+32 所對應到節點代碼為N42，因此，透過節點的繞送表查詢，可以直接跳躍到所查詢的到的節點，而不需要依照順時鐘方向依序詢問代碼環上的節點，而達到加快搜尋的速度。