Background an Motivation
隨著個人電腦的進步及價格的低廉，幾乎每個家庭都有個人電腦，不過觀察一下生活
週遭的電腦使用情況，不難發現其實電腦大部分的時間都是處於發呆或是關閉狀態，使電
腦不能真正的有效運用；但隨著網路的頻寬增加以及蓬勃發展，可以利用網路的力量將大
家的電腦資源給結合起來，是未來網路發展的一項重要趨勢，「讓每台電腦都將參與在網路
之中」主要的精神就是將分散在不同地理位置的電腦組織在一起，其中每一台參與計算的
電腦就是屬於整個系統上的一份子，如此整個分散式系統上的所有電腦資源就能夠互相分
享、整個計算也是由所有系統上的電腦共同合力完成。簡單地講，就是把整個網路上的電
腦整合成一台巨大的超級電腦，實現計算資源、存儲資源、資料資源、資訊資源、知識資
源的全面共用。
而近年來，分散式系統蓬勃發展，究其原因，「檔案分享」的應用就是讓他受到大家廣
泛使用的重要因素，目前在網路上大家普遍使用到的分散式系統有 eMule、eDonkey、kuro
等系統，而在此類分散式系統中，使用者可以隨時加入或離開，將自己的一些檔案或資料
分享給其他人，並且也可以透過此系統搜尋所想要的檔案，或是下載所需的檔案。
不過上述的系統中，都有所謂的中央伺服器來記錄來自各地的使用者分享的資料，以
成本的考量上來看，為了要達到如此大規模的檔案分享系統，是需要功能強大的電腦，並
且需要人力來維持中央系統的正常運作，所需資金不匪，故我們希望能將資料分享的運用
建置在完全分散式的 Peer-to-Peer 系統上，如此即可以省掉購買強大伺服器的必要，因為
Peer-to-Peer 系統是不需要中央的伺服器來記錄或管理資料，而是由系統上的所有電腦來共
同負責，彼此的檔案可以透過底層的邏輯架構及路由的資訊，來將檔案的資訊存放在系統
上，在藉由相同的演算法，而可以搜尋到相關的檔案資訊，藉此達到彼此檔案分享的需求。
Project Goal
一、完全分散式的 peer-to-peer 系統
一個完全沒有中央控制機制的系統，網路上的每台電腦扮演相同的腳色，因此不
會因為部分電腦的當機而癱瘓整個系統，且系統中的使用者不需記住整個系統的所有
電腦的資訊或位址，即可找到系統中的任何一台電腦。
二、能提供檔案分享
使用者可以自行將檔案分享給整個系統，而此系統會將相關的檔案訊息放置在系
統中適當的電腦存放。
三、快速的檔案查詢
使用者可以不知道系統中各台電腦的位址的情況下，而以檔名搜尋系統，並找到
系統中此檔案的相關資訊，我們預計提供完整的檔名搜尋及關鍵字搜尋兩種不同的搜
尋功能。
四、能夠容許電腦動態加入及離開、當機
容許許多台電腦可以同時加入系統中，或是多台電腦同時離開，或是多台電腦的
不正常離開系統，而系統還能正常運作或是快速的恢復正常運作。
五、在電腦數目遽增的情況下還維持不錯的效能
當有幾百萬台甚至幾億台電腦加入系統時還能維持系統的效能，即可以有效率的
分享檔案、搜尋檔案、加入系統或是離開系統。
六、快速的下載所需的檔案
利用將一份檔案切割成數個區塊的技術，而能使下載者能同時從不同的來源下載
不同的區塊，以加速檔案取得的時間。
System Architecture
Application Layer:
此層主要是與使用者直接溝通的介面，提供了使用者加入或離開整個系統，而當使用
者加入系統後，即可以分享自己的檔案、搜尋系統中想要的檔案以及下載所想要的檔案。
Object Service Layer:
此層主要是管理使用者的檔案分享及檔案下載，包含了記錄使用者分享的檔案資訊，
而檔案下載時會若得知來源不只一台電腦時，則會同時向不同的來源要求下載不同的檔案
區塊，並將抓回的檔案區塊組合成原本的檔案，最後再將抓取的檔案分享出去。
P2P Base Layer:
建置 Peer-to-peer 的分散式系統，包含節點的加入系統及離開系統、分享檔案資訊的插
入及刪除，還有系統錯誤的更正及修復等等，並提供節點的搜尋、檔案的搜尋等功能。
Design and Algorithm
P2P Base Layer─Base on Chord
Routing Table：
Name resolution
and routing service
Object insert
and
delete service
Topology
construction
and maintenance
Object migration
and
replication service
Object access
and
location service
Object
sharing
Key word
searching
File name
searching
Object
downloading
P2P Base
Layer
Application
Layer
Object
Service
Layer
如同Chord的設計，每個節點會記錄與自己的ID相差2的i次方的ID的代理節點當作自己
的ith neighbor，並且會記錄自己的predecessor與successor的資訊，而不同的是本系統可以依
照系統的特性來設定要記錄的predecessor與successor的數目，記錄的越多系統會能容忍節點
的不正常離開，但也因此必須再加入及離開時有較多的資訊交流。
Routing Algorithm(Node Lookup Algorithm：
首先先檢查欲查詢的目標節點其ID是否在我與我的successors的ID的範圍內，若是即表
示目標ID的代理節點為我的successor，並從successors中找出此ID的代理節點；若否，則檢
查是否我有predecessor，若沒有則檢查目標ID是否座落在離我最遠的successor與我的ID之間，
若是則表示我自己即為此目標ID的代理點。
若非上述的情況，則尋找我的ith neighbor中，其ID最接近目標ID但又不超過目標ID的
節點，並且將尋找目標ID的要求傳給該節點，由該節點採用相同的routing演算法直到找到
目標ID的代理節點為止。
Node Join Algorithm:
若系統目前沒有任何節點，則自己成為系統的第一個節點，並等待別人來加入。
若欲加入的系統已經有節點存在，則以其中一個已知的節點當作gateway，由此節點詢
問到目前系統中代理自己的ID的代理節點，並將此代理節點的predecessors與successors當作
自己的predecessors與successors，接著在詢問此代理節點得到我的ith neighbors。
接著詢問我的predecessors與successors所記錄的檔案資訊，並將該屬於自己記錄的資料
記錄下來，接著告知我的代理節點有關我的加入，並再次詢問其predecessors的資訊，看看
是否同時有新的節點加入，如果有則更新我的predecessors或successors的資訊。
最後再告知我的predecessors與successors有關我的加入，使他們能更新其successors與
predecessors的資訊，並且更新其ith neighbors的資訊。
Node Leave Algorithm:
首先先將我自己分享的案檔的資料從系統中刪除，接著再將原本存放在我身上的檔案
資訊傳給我的successor。
再來在告知我的predecessors與successors有關我的離開，而收到此訊息的節點將會更新
其predecessors與successors的資訊，以及更新其ith neighbor的資訊，最後就可以離開系統。
Failure Detect Algorithm:
為了增加系統的正確性，每個節點將會定期的檢查自己的routing table的資訊是否正確，
即檢查位於自己routing table的節點是否都還存在：如果有predecessor掛掉了，則詢問其他
還存活的predecessor其predecessor的資訊，以補充及更新自己的predecessor的資訊；如果有
successor掛掉了，則詢問其他還存活的successor其successor的資訊，以補充及更新自己的
successor的資訊；若ith neighbor掛掉了，則重新lookup此ith neighbor的ID來找尋到新的代理
者。
Object Insert Algorithm:
首先先將欲分享的檔案的檔名經過SHA1 hash過，而得到此檔案的object ID，再經由
lookup的機制尋找到此ID的代理節點，接著告知此節點有關此案檔的資訊，資訊包含檔案
的檔名、檔案大小及來源節點。
而當此負責此物件資訊的代理節點接到object insert的資訊後，會將此資訊記錄到自己
負責的object的記錄中，接著再將此object insert的資訊告訴其所有的predecessors與successors，
而當代理節點的predecessors與successors接到這樣的資訊後，會將這些資訊放入其cache中。
Object Delete Algorithm:
首先先將欲刪除且已分享的檔案的檔名經過SHA1 hash過，得到此檔案的object ID，再
經由lookup的機制尋找到此ID的代理節點，接著告知此節點將有關此案檔的資訊移除。
當負責此物件資訊的代理節點接到object delete的資訊後，會搜尋自己負責的object的記
錄檔，看看是否有這檔案的資料，如果有則刪除，接著再把此object delete的資訊告訴其所
有的predecessors與successors，而當此代理節點的predecessors與successors接到這樣的資訊後，
會將搜尋其cache看看是否有此資料存在，若有則刪除之。
Object Search Algorithm:
首先先將欲搜尋的檔案的檔名經過SHA1 hash過，得到此檔案的object ID，再經由
lookup的機制尋找到此ID的代理節點，接著詢問此節點是否有有關此案檔的資訊。
當負責此物件資訊的代理節點接到object search的資訊後，會搜尋自己負責的object及
cache的記錄檔，看看是否有這檔案的資料，如果有，則會先確認檔案的來源節點是否活著，
若活著則回傳相關的檔案資訊；若來源節點已掛點，則會將此資料移除。
Object Keyword Search Algorithm:
詢問所有位於我的routing table的節點是否含有預搜尋的keyword的字串的檔案資訊。
而當接收到此搜尋的要求時，節點會檢查自己的object與cache的記錄檔，看看是否記錄
的檔案其檔名包含此keyword，如果有，則會先確認檔案的來源節點是否活著，若活著則回
傳相關的檔案資訊；若來源節點已掛點，則會將此資料移除。
Object Download Algorithm:
當搜尋檔案得到檔案的來源資訊後，會檢查是否有許多不同的來源，若只有單一的來
源則直接與來源節點要求下載檔案。
若有多個來源，則會根據檔案的大小，將檔案分成許多固定大小的小區塊，而同時與
不同的來源要求下載不同的檔案區塊，最後再將所有的區塊重新整合成完整的檔案，並將
此檔案用object insert的方式分享出去。
System Characteristics
Dynamics:
因為當有節點要加入時，會先取得相關的資訊，才會告知系統新節點的加入，減少系
統更正整個網路資訊的時間，並降低發生同時加入時的短暫更正時間；而離開前也是會先
移除自己分享的檔案資訊，且將負責的資料傳給successor，然後告知系統其離開的資訊，
可確保資料已經正確傳給其他節點來負責，故此系統可容許節點動態的加入或離開系統，
或是同時的加入或離開。
Scalability:
因為每個節點要記錄的鄰居的資訊只是O(logN)，所以就算系統可容許264個節點，每個
節點要記錄的鄰居數也不到百個，故此系統可以有很好的擴充性，可適用於目前整個網際
網路。
Fail Tolerance:
因為會定期的確認routing table的正確性，故當有節點不正常離開系統時，可以被偵測
到並且更正，再加上每個檔案的資訊不只是存在該檔案ID的代理節點上，還會被cache在代
理節點的predecessors與successors上，故檔案資訊會存在代理節點的附近區域，故區域內有
節點不正常離開時，還可以從其他人身上得到檔案的資訊。
On demand Correct Object Record:
因為當有人與檔案的代理節點詢問有關檔案的資訊時，代理節點會先檢查是否檔案的
來源還活著，故可以在需要的時候才更新檔案的資訊，減少平常網路的使用及節點本身的
運作，也可以增加回傳的資料的正確性。
Quickly Download:
若系統中存在許多節點分享共同的檔案，則可以加入檔案下載的速度，因為可以同時
從不同的來源同時下載不同的檔案區塊，最後再組合回原本的檔案。
Operation Procedure
因為使用Java RMI作為middle ware，故首先必須執行RMI Registry，然後在執行本程式。
Node Joining and Leaving:
如﹝圖一﹞所示，首先必須先加入網路系統，若是系統的第一點，則直接按connect即
可，而若系統已有其節點存在，則在gateway處加入已存在的節點的ip與port，在按connect
即可加入系統，當加入後即可做檔案的分享與搜尋，而當要離開系統時，按Disconnect即可，
而status處會顯示目前節點的狀態即ID。
﹝圖一﹞
Objects Sharing and Deleting:
如﹝圖二﹞所示，當加入系統後即可做檔案的分享，只要按Open File即會彈出資料夾
選擇視窗，讓使用這選擇要分享的檔案，My Share Files處即會列出目前已經分享出來的檔
案資訊，接著可以從此列表中選擇檔案，按Delete將此分享的檔案資訊從系統中移除。
﹝圖二﹞
Objects Searching and Keyword Searching:
如﹝圖三﹞所示，可以選擇作檔名的搜尋或是關鍵字搜尋，即分別在Filename處或是
Keyword處輸入檔名或是關鍵字，然後按下Start即可搜尋，搜尋的結果會列在Search Result
處，而其中檔案搜尋是只要系統中有人分享及可以搜尋到，而關鍵字搜尋則只有作部分的
搜尋，故可能系統中存在相關的資料，但是卻沒搜尋到，而按Remove即可清除搜尋的結果。
﹝圖三﹞
Objects Downloading:
在﹝圖三﹞中，當搜尋後Search Result處會列出搜尋的結果，接著即可點選欲下載的檔
案，然後按下Download即可開始下載檔案，而目前正在下載的檔案資訊會出現在如﹝圖四﹞
所示的地方，Downloading Files會列出目前正在下載的檔案資料，而可以從此列表中選擇檔
案作出暫停(Stop)、續傳(Continue)、移除(Remove)或是清除已完成的檔案資料(Clean)等動
作。
﹝圖四﹞
Result and Conclusion
因為時間有限，再加上撰寫程式上的不熟練，故本系統最後的成品在測試上還是有錯
誤存在，例如在許多節點不正常離開時，會出現短暫的 routing 錯誤或是有些節點的 routing
table 錯誤，而這方面可以縮短錯誤偵測的時間間隔來加速錯誤的更正。
但是若縮短執行 routing table 錯誤偵測的時間間隔時，會造成網路上各節點不時的在作
維護的動作，因此網路會充斥偵測及更新的封包，但 Java 處理網路傳輸的能力有限，若網
路資料傳輸頻率過大，可能會發生網路傳輸出錯，故若此時有人在下載資料，其資料的傳
輸可能會因此而發生錯誤，所以我們必須在網路的使用率與系統更正的頻率上要選擇最適
當的平衡，故可能要設計新的錯誤偵測與更新的方式，盡量減少網路的資訊交換次數，這
樣才能有效的利用網路，減少因為網路流量過大而造成的網路錯誤。
而在於檔案下載的部分，因為時間關係，並未檢查是否每個要求的下載的檔案區塊都
有正確的取得，故當有來源中途發生當機時，會造成資料無法正確的下載，這方面是未來
需要在改進的部分。
