點對點環境的草履蟲自組織和協作路由方法
2023-06-02 00:30:36 3
專利名稱：點對點環境的草履蟲自組織和協作路由方法
技術領域：
點對點環境的草履蟲自組織和協作路由方法屬於計算機網絡技術領域。
背景技術：
隨著計算機科學和技術的發展，個人計算機的性能正按照莫爾定律每隔十八個月翻一番的速度發展。與此同時，存儲和網絡的帶寬的發展速度超越了莫爾定律。現代個人計算機的能力已經大大超過了20年前的超級計算機。有研究表明大多數時候個人PC的利用率不到10％。人類具有相互合作、分享的社會特性。在這種背景下，點對點(P2P)作為對客戶機/伺服器服務模式的顛覆和一種全新的結構模式應運而生。
P2P強調的是對等服務，不區分伺服器和客戶端。每個節點在索取其他節點服務同時，也和其他節點相配合提供相同的服務。它是一種扁平而不是層次化的結構，每個參與節點的地位都相等。
P2P的思想最早體現在Napster系統中。它提供的服務允許音樂迷們自由交流MP3文件。Napster提供了一個軟體供音樂迷在自己的硬碟上共享歌曲文件，檢索位於Napster伺服器上其他用戶共享的歌曲的索引，併到其它使用Napster服務的用戶硬碟上去下載歌曲的服務。
Gnutella和KazAa成為第二代P2P的代表。Gnutella和KazAa把共享的範圍拓展到所有的文件，包括電影、應用程式等。Gnutella和KazAa沒有中央索引伺服器，所有的文件都存在節點本地。他們的搜索採用廣度優先或深度優先的方法，配合適當的啟發式方法。系統中只存在「眾所周知」的入口節點，節點也可通過任何它所知道的在線節點加入系統中。每個節點維護一個它所知道的節點的IP的列表(稱為鄰居)。表中除了入口節點，其它項都是動態學習來的。這一代是非結構化(unstructured)的P2P系統。
CAN、Chord、Pastry、Tapestry和SkipNet等協議的出現標誌著第三代P2P系統的萌芽。這些都是結構化(structured)的系統。它們提出了NodeId、Key、對象和路由的概念。NodeId和Key是數字標識，分別標識節點和對象。對象代表存儲在系統中的數據。節點按照某種方式和其本身的NodeId組織成P2P系統。對象根據其Key和路由方法保存在適當的節點上。這種結構化帶來了負載平衡和可用來構造永久存儲系統等特點。而隨著節點的離開導致共享的內容不可用正是第一代和第二代P2P系統的致命缺點。這些系統通常稱為DHT(DistributedHash Table)。
DHT系統強調參與節點角色對等的同時忽略了網絡組織的結構性。現存的網絡是個層次化的transit-sub結構。終端節點通過交換機或路由器實現局部互聯，再由路由器連接到更大的網絡。同一個區域網內互聯的速度較快，網間互連的速度則比較慢。在DHT的組織中，由於節點的ID近乎隨機產生，因此同一個子網內的節點均勻分布在ID空間中。這樣雖然帶來了負載平衡和容錯的好處，但同時產生了一系列的問題1)一個節點的加入和離開會導致路由表中包含它的節點的路由表發生變化。這些節點在地理上分布在各地，並且連接的網絡速度較慢。如果加入和離開的速度較快，容易導致整個路由系統出現混亂。
2)在具體的特別是涉及到多個自治組織的應用中，數據的放置位置一般有一定的要求，如必須放置在部門或組織內。傳統的DHT經過散列後地理的局部性被打亂了，節點和數據都是隨機分布，無法控制數據的放置。
針對點對點環境中的重點和難點，我們提出了自己的可行方案，實現了在快速變化點對點的環境中在沒有中央伺服器的情況下實現可擴展的參與節點的穩定的自組織和協作路由，我們的方法可以很有效地實現。
發明內容
本發明的目的在於提供一種點對點環境中草履蟲自組織和協作路由方法，以便為實現點對點系統奠定基礎。
本發明的特徵在於它是在傳統的TCP/IP協議點對點環境下，由草履蟲系統內的各計算機按以下情況分別依次實現的，所述的草履蟲系統既可以是本地的草履蟲系統，也可以是遠程草履蟲系統設定對草履蟲系統內的每個節點用無衝突且均勻分布的哈希的方法賦予一個160二進位位的數字節點標識-NodeId，形成首位為0，末位為2160-1且首尾相接的NodeID數字空間；對於節點中存儲的對象也用上述方法賦予一個160位二進位位的數字鍵標識-Key，形成首位為0，末位為2160-1且首尾相接的Key數字空間；再把NodeID數字空間分割成若干相互既不包含也不重疊，彼此銜接的細胞，每個細胞由二元組[左邊界，右邊界](可見左邊界和右邊界都是數字)來標識，細胞的疆界的併集覆蓋整個NodeId空間；草履蟲向上層提供以下應用程式接口，即APIJoin(BootNodeIP)通過在線的網絡地址為BootNodeIP的節點把一個本節點帶入系統；Route(NodeID/Key)給定一個節點的NodeID或Key，在系統中查找另一個節點，這個節點所在的細胞包含這個給定的NodeID/Key並且這個節點的ID和這個給定的NodeID/Key的絕對值之差在這個細胞裡的所有的節點中是最小的；每個節點有兩套路由表節點的細胞內路由表包含所在細胞內所有節點的NodeId和網絡地址(IP)節點的細胞間路由表由若干行組成，每行包括如下信息所要到達的細胞距離出行節點所在的細胞中心的距離、對於出行節點而言它的節點ID、節點IP和節點所在的細胞的疆界。其中，上述距離按照以下標準選取「出發節點所在細胞的半徑＝|右邊界-左邊界|/2」，以「R＝出發節點所在細胞的半徑+1」作為單位步長，分別依次選取如下項L0＝R*20，L1＝R*21，L2＝R*22，…。Li＝R*2I小於或等於數字空間長度的一半，即2160/2。
通過引入細胞結構，在快速變化點對點的環境中和在沒有中央伺服器的情況下，所述可擴展的參與節點的穩定的自組織和協作路由以下5個過程按需求實現1.路由路由的方法很簡單。路由的目的是找到在包含給定的Key的細胞內和給定的Key最靠近(兩者之差的絕對值最小)並且最靠近細胞左邊界的節點。如果給定的Key在本細胞內則使用細胞內路由表進行路由。否則把路由請求發送到在細胞間路由表中距離目標最近並且沒有超過目標的細胞中的節點，即細胞的某邊疆界距離目標最近，再由這個節點進行中繼路由。詳細步驟如下[1]節點A在網絡上(TCP/IP協議)偵聽路由請求[2]節點A收到節點B的路由請求，假定給定的NodeID/Key為X[3]節點A根據自己的所在的細胞的疆域[B1，B2]判斷X是否在自己所在的細胞的疆域內，即B1＜＝X＜＝B2a)如果X在[B1，B2]範圍內，則A在細胞內路由表中查找NodeID和X最接近的一個節點，把這個節點的IP和NodeID通過TCP/IP協議返回給請求路由的節點Bb)如果X不在[B1，B2]範圍內，則A過TCP/IP協議把路由請求發送到在細胞間路由表中NodeID和X最接近並且沒有超過X的細胞中的節點，假定為C，這個C進行中繼路由。節點A等待C返回的結果，把結果通過TCP/IP協議返回給B；[4]節點A繼續偵聽路由請求2.路由表的維護細胞內路由表使用廣播的方法來維護和發現存活節點信息。節點周期性地查詢與自己的細胞相距特定距離的細胞，更新自己的細胞間路由表。
細胞內路由表的維護由4個獨立的子過程組成[1]每隔5分鐘，細胞內路由表的維護程序對細胞內路由表中的每一項對應的節點通過TCP/IP協議發起連接請求。如果連接是失敗，則把這一項從細胞內路由表中刪掉；[2]每隔15分鐘，細胞內路由表的維護程序把自己的節點的細胞內路由表通過TCP/IP協議發送給細胞內路由表中的所有節點；[3]細胞內陸由表程序從節點啟動開始就偵聽和接收其他節點發送來的它們的細胞內路由表，據此更新自己的路由表依次取出接收到的細胞內路由表中的每一項，如果這一項的NodeID不在自己的細胞內路由表中，把這一項加入到自己的細胞內路由表；假定節點的NodeID是X，它所在的細胞的疆域是[B1，B2]，細胞間路由表的維護過程如下[1]每隔20分鐘啟動一次維護細胞間路由表的過程[2]令R＝1+|B1-B2|/2；L0＝R*20，L1＝R*21，L2＝R*22，…。其中Li＝R*2I＜＝2160/2。
X依次路由Li，把路由的結果填入對應的細胞間路由表。
3.加入草履蟲的一個關鍵設計就是在面臨節點加入和離開的情況下維護系統的結構不變，即每個節點的路由表符合設定的要求。
節點加入過程[1]假定節點X，X的NodeID就是X，要加入系統。X通過其它方法知道一個節點A在系統中，[2]X用自己的NodeId---X---作為Key，請求A路由X，[3]A使用1中所述的路由方法路由X， X得到A路由X的結果，假定為節點D，[5]X通過TCP/IP協議取得D的細胞內路由表和細胞間路由表，並把它們作為自己對應的路由表，[6]X通過TCP/IP協議通知自己細胞內路由表中的每個節點，自己加入這個信息，[7]接收到這個信息的節點把X加入到自己的細胞內路由表中；4.分裂當一個細胞中節點的個數超過預定閥值時，細胞內的節點通過爭奪的方式由某個節點取得領導權，發起分裂操作，分裂後兩個子細胞中節點的個數基本相等，過程如下[1]每個節點每隔30分鐘檢查一下自己細胞內路由表中節點的數目。如果個數超過閥值，節點發起分裂操作，假定這個節點是X，[2]X向細胞內路由表中的每個節點通過TCP/IP協議發出分裂請求，等待它們的回答，[3]收到分裂請求的節點，假定為Y，如果本身沒有發起分裂請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起分裂的請求，不然返回「拒絕」的回答，[4]X接收返回的回答。只要有一個「拒絕」的回答，X就放棄發起分裂操作的企圖，[5]經過上述的1-4步，必然有一個節點勝出，取得分裂的領導權，假定這個節點為Z，[6]Z所在的細胞的疆域是[B1，B2]。Z把[B1，B2]分成兩個相等的細胞S1和S2[B1，(B1+B2)/2]，[1+(B1+B2)/2，B2]。假定Z現在屬於S1，即B1＜＝X＜＝(B1+B2)/2[7]Z向細胞內路由表中的每個節點通過TCP/IP協議發送分裂的結果S1和S2[8]Z把自己的細胞內路由表中不屬於S1的節點的對應的項刪掉，[9]Z調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表，[10]收到分裂結果的節點判斷自己屬於哪個細胞，假定為Si；把自己的細胞內路由表中不屬於Si的節點的對應的項刪掉；調用2中的細胞間路由表更新過程更新自己的細胞間路由表；5.融合當一個細胞中節點的個數少於預定閥值時，細胞向左邊細胞和右邊細胞中節點個數較少的一個請求融合操作，它依次執行一下步驟[1]每個節點每隔30分鐘檢查一下自己細胞內路由表中節點的數目。如果個數少於閥值，節點發起融合操作。假定這個節點是X，[2]X向細胞內路由表中的每個節點通過TCP/IP協議發出融合請求，等待它們的回答， 收到X融合請求的節點，假定為Y，如果本身沒有發起融合請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起融合的請求，不然返回「拒絕」的回答，[4]X接收返回的回答。只要有一個「拒絕」的回答，X就放棄發起融合操作的企圖，[5]X通過細胞間路由表的的第一項，即步長為L0＝R*20的那項對應的節點發出融合請求，假定這個節點是X』。X所在的細胞和X』所在的細胞必然是相鄰的，[6]X1向細胞內路由表中的每個節點通過TCP/IP協議發出融合請求，等待它們的回答，[7]收到X1融合請求的節點(假定為Y)如果本身沒有發起融合請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起融合的請求，不然返回「拒絕」的回答。
X1接收返回的回答。只要有一個「拒絕」的回答，X1就向X返回「拒絕」的回答，否則返回「同意」的回答，[9]X接收X1返回的回答。如果是「拒絕」的回答，X就放棄發起融合操作的企圖。
經過上述的1-10步，必然有一個節點勝出，取得融合的領導權。假定X2勝出。
X2所在的細胞的疆域是[B1，B2]，X1的則是[B2+1，B3](注意，它們必定相鄰)。X2把它們合併成[B1，B3]。
X2通過TCP/IP協議向X1索取它的細胞內路由表，並把所取到的細胞內路由表的表項加入到自己的細胞內路由表中，[13]X2向自己新的細胞內路由表中的每個節點通過TCP/IP協議發送融合的結果[B1，B3]和自己新的細胞內路由表，[14]X2調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表，[15]收到融合結果的節點用收到的細胞內路由表替換自己的細胞內路由表；調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表。
實驗證明測試所使用的機器IBM T40 14UPentium M 1.3G，256M內存；Windows XP with servicepack 1所有的讀寫都是串行的。為了避免java的JIT帶來的問題，所有的實驗都先讀寫3次進行預熱，過了1分鐘後再進行測試。結果取3次的平均值。測試用的數據包共1024個。每個數據包的Key隨機生成，隨機選擇一個節點作為發起節點，通過它將數據包插入系統。寫完1024個數據包後隨機選擇不同的節點讀出這些數據包，即先路由再寫和讀。從實驗的數據圖(圖5)可以看到，無論讀還是寫，路由是正確的，速度達到了設計的要求。
圖1路由過程的程序流程執行2節點加入過程的程序流程執行3分裂過程的程序流程執行4融合過程的程序流程執行532和64節點的路由性能具體實施方式
草履蟲的每個節點被賦予一個16二進位位的數字節點標識-NodeId。每個要存儲的對象(可以是任何數據文件、數字等)也有一個160位的數字鍵標識-Key。NodeID和Key是同一個概念，但標識不同的對象。NodeId空間和Key空間是同一個數字空間，並且都首尾相接(0和2160-1)形成一個環。NodeId和Key可以用無衝突且均勻分布的哈希的方法產生，例如安全哈希算法(SHA-1)。草履蟲提出細胞的概念。每個細胞由二元組[左邊界，右邊界]來標識，稱為細胞的疆界。例如如果ID為6位二進位長，[111000，111100]、和[110000，001000]都是細胞標識的例子。細胞相互不包含和不重疊；細胞的疆界的併集覆蓋整個NodeId空間。給定一個Key，草履蟲可以高效分布式地找到這樣一個節點這個節點的所在的細胞包含這個Key，並且這個節點的NodeId和這個Key最接近。
草履蟲向上層提供以下APIJoin(BootNodeIP)通過在線的BootNode將本節點帶入系統Route(NodeID/Key)給定一個節點的NodeID或Key，在系統中查找一個節點，這個節點所在的細胞包含這個給定的NodeID並且這個節點的ID和這個給定的ID的絕對值之差在這個細胞裡的所有的節點中是最小的。
每個節點有兩套路由表細胞內路由表和細胞間路由表。節點的細胞內路由表包含所在細胞內所有節點的NodeId和網絡地址(IP)。因此節點在細胞內部是全連接的。節點的細胞間路由表由若干行組成，每行包括如下信息距離本細胞的中心的距離、節點ID、節點IP和節點所在的細胞的疆界。距離本細胞中心的距離按照以下標準選取「出發節點所在細胞的半徑＝|右邊界一左邊界|/2」，以「R＝(出發節點所在細胞的半徑+1)」作為單位步長，分別依次選取如下項L0＝R*20，L1＝R*21，L2＝R*22，…，Li＝R*2I小於或等於數字空間長度的一半，即2160/2。這種組織方法使得每個節點的路由表都很小，並且具有良好的可擴展性。
1.路由路由的方法很簡單。路由的目的是找到在包含給定的Key的細胞內和給定的Key最靠近(兩者之差的絕對值最小)並且最靠近細胞左邊界的節點。如果給定的Key在本細胞內則使用細胞內路由表進行路由。否則把路由請求發送到在細胞間路由表中距離目標最近並且沒有超過目標的細胞中的節點，即細胞的某邊疆界距離目標最近，再由這個節點進行中繼路由。詳細步驟如下(錯誤！未找到引用源。)[1]節點A在網絡上(TCP/IP協議)偵聽路由請求[2]節點A收到節點B的路由請求，假定為X[3]節點A根據自己的所在的細胞的疆域[B1，B2]判斷X是否在自己所在的細胞的疆域內，即B1＜＝X＜＝B2a)如果X在[B1，B2]範圍內，則A在細胞內路由表中查找NodeID和X最接近的一個節點，把這個節點的IP和NodeID通過TCP/IP協議返回給請求路由的節點Bb)如果X不在[B1，B2]範圍內，則A過TCP/IP協議把路由請求發送到在細胞間路由表中NodeID和X最接近並且沒有超過X的細胞中的節點(假定為C)，這個C行中繼路由。節點A等待C返回的結果，把結果通過TCP/IP協議返回給B[4]節點A繼續偵聽路由請求2.路由表的維護細胞內路由表使用廣播的方法來維護和發現存活節點信息。節點周期性地查詢與自己的細胞相距特定距離的細胞，更新自己的細胞間路由表，維護和提高路由的性能。
細胞內路由表的維護由4個獨立的子過程組成[1]每隔5分鐘，細胞內路由表的維護程序對細胞內路由表中的每一項對應的節點通過TCP/IP協議發起連接請求。如果連接是失敗，則把這一項從細胞內路由表中刪掉；[2]每隔15分鐘，細胞內路由表的維護程序把自己的節點的細胞內路由表通過TCP/IP協議發送給細胞內路由表中的所有節點；[3]細胞內陸由表程序從節點啟動開始就偵聽和接收其他節點發送來的它們的細胞內路由表，據此更新自己的路由表依次取出接收到的細胞內路由表中的每一項，如果這一項的NodeID不在自己的細胞內路由表中，把這一項加入到自己的細胞內路由表；
假定節點的NodeID是X，它所在的細胞的疆域是[B1，B2]，細胞間路由表的維護過程如下[1]每隔20分鐘啟動一次維護細胞間路由表的過程[2]令R＝1+|B1-B2|/2；L0＝R*20，L1＝R*21，L2＝R*22，…。其中Li＝R*2I＜＝2160/2。
X依次路由Li，把路由的結果填入對應的細胞間路由表。
3.加入草履蟲的一個關鍵設計就是在面臨節點加入和離開的情況下維護系統的結構不變，即每個節點的路由表符合設定的要求。
節點加入過程很簡單(錯誤！未找到引用源。)[1]假定節點X，X的NodeID就是X，要加入系統。X通過其它方法知道一個節點A在系統中，[2]X用自己的NodeId---X---作為Key，請求A路由X，[3]A使用1中所述的路由方法路由X，[4]X得到A路由X的結果，假定為節點D，[5]X通過TCP/IP協議取得D的細胞內路由表和細胞間路由表，並把它們作為自己對應的路由表，[6]X通過TCP/IP協議通知自己細胞內路由表中的每個節點，自己加入這個信息，[7]接收到這個信息的節點把X加入到自己的細胞內路由表中；4.分裂當一個細胞中節點的個數超過預定閥值時，細胞內的節點通過爭奪的方式由某個節點取得領導權，發起分裂操作，分裂後兩個子細胞中節點的個數基本相等，過程如下[1]每個節點每隔30分鐘檢查一下自己細胞內路由表中節點的數目。如果個數超過閥值，節點發起分裂操作，假定這個節點是X，[2]X向細胞內路由表中的每個節點通過TCP/IP協議發出分裂請求，等待它們的回答，[3]收到分裂請求的節點，假定為Y，如果本身沒有發起分裂請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起分裂的請求，不然返回「拒絕」的回答，[4]X接收返回的回答。只要有一個「拒絕」的回答，X就放棄發起分裂操作的企圖，[5]經過上述的1-4步，必然有一個節點勝出，取得分裂的領導權，假定這個節點為Z，[6]Z所在的細胞的疆域是[B1，B2]。Z把[B1，B2]分成兩個相等的細胞S1和S2[B1，(B1+B2)/2]，[1+(B1+B2)/2，B2]。假定Z現在屬於S1，即B1＜＝X＜＝(B1+B2)/2，例如假定Z所在的細胞是[10，100]，那麼B1＝10，B2＝100，(B1+B2)/2＝55，那麼S1和S2分別是[10，55]，[56，100][7]Z向細胞內路由表中的每個節點通過TCP/IP協議發送分裂的結果S1和S2[8]Z把自己的細胞內路由表中不屬於S1的節點的對應的項刪掉，[9]Z調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表，[10]收到分裂結果的節點判斷自己屬於哪個細胞，假定為Si；把自己的細胞內路由表中不屬於Si的節點的對應的項刪掉；調用2中的細胞間路由表更新過程更新自己的細胞間路由表；5.融合當一個細胞中節點的個數少於預定閥值時，細胞向左邊細胞和右邊細胞中節點個數較少的一個請求融合操作，它依次執行一下步驟[1]每個節點每隔30分鐘檢查一下自己細胞內路由表中節點的數目。如果個數少於閥值，節點發起融合操作。假定這個節點是X，[2]X向細胞內路由表中的每個節點通過TCP/IP協議發出融合請求，等待它們的回答，[3]收到X融合請求的節點，假定為Y，如果本身沒有發起融合請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起融合的請求，不然返回「拒絕」的回答，[4]X接收返回的回答。只要有一個「拒絕」的回答，X就放棄發起融合操作的企圖，[5]X通過細胞間路由表的的第一項，即步長為L0＝R*20的那項對應的節點發出融合請求，假定這個節點是X』。X所在的細胞和X』所在的細胞必然是相鄰的，[6]X1向細胞內路由表中的每個節點通過TCP/IP協議發出融合請求，等待它們的回答，[7]收到X1融合請求的節點(假定為Y)如果本身沒有發起融合請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起融合的請求，不然返回「拒絕」的回答。
X1接收返回的回答。只要有一個「拒絕」的回答，X1就向X返回「拒絕」的回答，否則返回「同意」的回答，[9]X接收X1返回的回答。如果是「拒絕」的回答，X就放棄發起融合操作的企圖。
經過上述的1-10步，必然有一個節點勝出，取得融合的領導權。假定X2勝出。
X2所在的細胞的疆域是[B1，B2]，X1的則是[B2+1，B3](注意，它們必定相鄰)。X2把它們合併成[B1，B3]，例如假定X2所在的細胞是[10，50]，X1所在的細胞是[51，90]，那麼合併後的細胞是[10，90][12]X2通過TCP/IP協議向X1索取它的細胞內路由表，並把所取到的細胞內路由表的表項加入到自己的細胞內路由表中，[13]X2向自己新的細胞內路由表中的每個節點通過TCP/IP協議發送融合的結果[B1，B3]和自己新的細胞內路由表，[14]X2調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表，[15]收到融合結果的節點用收到的細胞內路由表替換自己的細胞內路由表；調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表。
草履蟲在高度變化的環境下能維護系統的正確結構和執行高效的分布式路由。草履蟲的所有操作對上層點對點應用都是透明的。給定一個標識，草履蟲能高效地找到對它負責的節點。上層應用可以把它看成一個執行簡單的插入與查找的本地的哈希表。
需要的硬體環境CPU 500MHZ或以上、內存64M。
需要的軟體環境支持JDK1.4的作業系統、Java1.4運行時環境。
作為一個本地草履蟲系統，對於其中每一個節點設有以下接口[1]Paramecium(NetworkAdapternetworkAdapter，IDid) //創建一個草履蟲實例[2]boolean boot //引導一個獨立的草履蟲系統[3]boolean join(AddressbootAddress) //加入一個已有的的草履蟲系統[4]quit //退出系統[5]NodelightRoute(IDid，CellBoundaryconstraint，java.util.Vector path，int ttl，int tries) //對給定的id、限定範圍constrain、最大距離ttl和嘗試次數tries進行輕量路由，返回目標節點和路徑path[6]Noderoute(IDid，CellBoundaryconstraint，java.util.Vector path，int ttl，int tries) //對給定的id、限定範圍constrain、最大距離ttl和嘗試次數tries進行正常路由，返回目標節點和路徑path[7]int checkCell //檢查所在細胞，進行分裂和融合等操作[8]void ackRouteRequest //響應其它節點的路由請求[9]void updateOuterRoutingTable //更新細胞間路由表[10]void updateLocalsParallelly //更新細胞內路由表一個例子代碼樣例如下//假定某個節點啟動一個新的草履蟲系統dp/public class Boot{public void main(String[]args){//假定本機地址是10.0.0.05，埠是05//構建本節點的網絡地址Address bootAddress＝new Address(″10.0.0.05″，05)；//構建本節點的網絡UDPNetwork network＝new UDPNetwork；//初始化網絡network.init(bootAddress)；//ID是05，構建本草履蟲節點Paramecium bootNode＝new Paramecium(network，new ID(05))；//引導一個新的草履蟲系統bootNode.boot；}}//其它節點加入系統public class Join{public void main(String[]args){//已有系統的入口//構建在線的引導節點的網絡地址Address bootAddress＝new Address(″10.0.0.05″，05)；//假定本機地址是10.0.0.X，埠是Y//構建本節點的網絡地址Address address＝new Address(″10.0.0.X″，Y)；//構建本節點的網絡UDPNetwork network＝new UDPNetwork；//初始化網絡network.init(address)；//ID是Ydp/Paramecium joinNode＝new Paramecium(network，new ID(Y))；//通過在線的引導節點加入joinNode.join(bootAddress)；//NO2查找18的片斷代碼//joinNode.lookup(18，null)；//其它節點通過void ackRouteRequest響應路由請求}}
權利要求
1.點對點環境的草履蟲自組織和協作路由方法，其特徵在於它是在傳統的TCP/IP協議點對點環境下，由草履蟲系統內的各計算機按以下情況分別依次實現的，所述的草履蟲系統既可以是本地的草履蟲系統，也可以是遠程草履蟲系統設定對草履蟲系統內的每個節點用無衝突且均勻分布的哈希的方法賦予一個160二進位位的數字節點標識-NodeId，形成首位為0，末位為2160-1且首尾相接的NodeID數字空間；對於節點中存儲的對象也用上述方法賦予一個160位二進位位的數字鍵標識-Key，形成首位為0，末位為2160-1且首尾相接的Key數字空間；再把NodeID數字空間分割成若干相互既不包含也不重疊，彼此銜接的細胞，每個細胞由二元組[左邊界，右邊界](可見左邊界和右邊界都是數字)來標識，細胞的疆界的併集覆蓋整個NodeId空間；草履蟲向上層提供以下應用程式接口，即APIJoin(BootNodeIP)通過在線的網絡地址為BootNodeIP的節點把一個本節點帶入系統；Route(NodeID/Key)給定一個節點的NodeID或Key，在系統中查找另一個節點，這個節點所在的細胞包含這個給定的NodeID/Key並且這個節點的ID和這個給定的NodeID/Key的絕對值之差在這個細胞裡的所有的節點中是最小的；每個節點有兩套路由表節點的細胞內路由表包含所在細胞內所有節點的NodeId和網絡地址(IP)節點的細胞間路由表由若干行組成，每行包括如下信息所要到達的細胞距離出行節點所在的細胞中心的距離、對於出行節點而言它的節點ID、節點IP和節點所在的細胞的疆界，其中，上述距離按照以下標準選取「出發節點所在細胞的半徑＝|右邊界-左邊界|/2」，以「R＝(出發節點所在細胞的半徑+1)」作為單位步長，分別依次選取如下項L0＝R*20，L1＝R*21，L2＝R*22，…，Li＝R*2I小於或等於數字空間長度的一半，即2160/2；通過引入細胞結構，在快速變化點對點的環境中和在沒有中央伺服器的情況下，所述可擴展的參與節點的穩定的自組織和協作路由以下5個過程按需求實現1.路由路由的方法很簡單。路由的目的是找到在包含給定的Key的細胞內和給定的Key最靠近(兩者之差的絕對值最小)並且最靠近細胞左邊界的節點。如果給定的Key在本細胞內則使用細胞內路由表進行路由。否則把路由請求發送到在細胞間路由表中距離目標最近並且沒有超過目標的細胞中的節點，即細胞的某邊疆界距離目標最近，再由這個節點進行中繼路由。詳細步驟如下；[1]節點A在網絡上(TCP/IP協議)偵聽路由請求，[2]節點A收到節點B的路由請求，假定給定的NodeID/Key為X，[3]節點A根據自己的所在的細胞的疆域[B1，B2]判斷X是否在自己所在的細胞的疆域內，即B1＜＝X＜＝B2a)如果X在[B1，B2]範圍內，則A在細胞內路由表中查找NodeID和X最接近的一個節點，把這個節點的IP和NodeID通過TCP/IP協議返回給請求路由的節點Bb)如果X不在[B1，B2]範圍內，則A過TCP/IP協議把路由請求發送到在細胞間路由表中NodeID和X最接近並且沒有超過X的細胞中的節點，假定為C，這個C進行中繼路由。節點A等待C返回的結果，把結果通過TCP/IP協議返回給B；[4]節點A繼續偵聽路由請求2.路由表的維護細胞內路由表使用廣播的方法來維護和發現存活節點信息。節點周期性地查詢與自己的細胞相距特定距離的細胞，更新自己的細胞間路由表。細胞內路由表的維護由4個獨立的子過程組成[1]每隔5分鐘，細胞內路由表的維護程序對細胞內路由表中的每一項對應的節點通過TCP/IP協議發起連接請求。如果連接是失敗，則把這一項從細胞內路由表中刪掉；[2]每隔15分鐘，細胞內路由表的維護程序把自己的節點的細胞內路由表通過TCP/IP協議發送給細胞內路由表中的所有節點；[3]細胞內陸由表程序從節點啟動開始就偵聽和接收其他節點發送來的它們的細胞內路由表，據此更新自己的路由表依次取出接收到的細胞內路由表中的每一項，如果這一項的NodeID不在自己的細胞內路由表中，把這一項加入到自己的細胞內路由表；假定節點的NodeID是X，它所在的細胞的疆域是[B1，B2]，細胞間路由表的維護過程如下[1]每隔20分鐘啟動一次維護細胞間路由表的過程[2]令R＝1+|B1-B2|/2；L0＝R*20，L1＝R*21，L2＝R*22，…。其中Li＝R*2I＜＝2160/2。[3]X依次路由Li，把路由的結果填入對應的細胞間路由表。3.加入草履蟲的一個關鍵設計就是在面臨節點加入和離開的情況下維護系統的結構不變，即每個節點的路由表符合設定的要求。節點加入過程[1]假定節點X，X的NodeID就是X，要加入系統。X通過其它方法知道一個節點A在系統中，[2]X用自己的NodeId---X---作為Key，請求A路由X，[3]A使用1中所述的路由方法路由X，[4]X得到A路由X的結果，假定為節點D，[5]X通過TCP/IP協議取得D的細胞內路由表和細胞間路由表，並把它們作為自己對應的路由表，[6]X通過TCP/IP協議通知自己細胞內路由表中的每個節點，自己加入這個信息，[7]接收到這個信息的節點把X加入到自己的細胞內路由表中；4.分裂當一個細胞中節點的個數超過預定閥值時，細胞內的節點通過爭奪的方式由某個節點取得領導權，發起分裂操作，分裂後兩個子細胞中節點的個數基本相等，過程如下[1]每個節點每隔30分鐘檢查一下自己細胞內路由表中節點的數目。如果個數超過閥值，節點發起分裂操作，假定這個節點是X，[2]X向細胞內路由表中的每個節點通過TCP/IP協議發出分裂請求，等待它們的回答，[3]收到分裂請求的節點，假定為Y，如果本身沒有發起分裂請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起分裂的請求，不然返回「拒絕」的回答，[4]X接收返回的回答。只要有一個「拒絕」的回答，X就放棄發起分裂操作的企圖，[5]經過上述的1-4步，必然有一個節點勝出，取得分裂的領導權，假定這個節點為Z，[6]Z所在的細胞的疆域是[B1，B2]。Z把[B1，B2]分成兩個相等的細胞S1和S2[B1，(B1+B2)/2]，[1+(B1+B2)/2，B2]。假定Z現在屬於S1，即B1＜＝X＜＝(B1+B2)/2[7]Z向細胞內路由表中的每個節點通過TCP/IP協議發送分裂的結果S1和S2[8]Z把自己的細胞內路由表中不屬於S1的節點的對應的項刪掉，[9]Z調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表，[10]收到分裂結果的節點判斷自己屬於哪個細胞，假定為Si；把自己的細胞內路由表中不屬於Si的節點的對應的項刪掉；調用2中的細胞間路由表更新過程更新自己的細胞間路由表；5.融合當一個細胞中節點的個數少於預定閥值時，細胞向左邊細胞和右邊細胞中節點個數較少的一個請求融合操作，它依次執行一下步驟[1]每個節點每隔30分鐘檢查一下自己細胞內路由表中節點的數目。如果個數少於閥值，節點發起融合操作。假定這個節點是X，[2]X向細胞內路由表中的每個節點通過TCP/IP協議發出融合請求，等待它們的回答，[3]收到X融合請求的節點，假定為Y，如果本身沒有發起融合請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起融合的請求，不然返回「拒絕」的回答，[4]X接收返回的回答。只要有一個「拒絕」的回答，X就放棄發起融合操作的企圖，[5]X通過細胞間路由表的的第一項，即步長為L0＝R*20的那項對應的節點發出融合請求，假定這個節點是X』。X所在的細胞和X』所在的細胞必然是相鄰的，[6]X1向細胞內路由表中的每個節點通過TCP/IP協議發出融合請求，等待它們的回答，[7]收到X1融合請求的節點(假定為Y)如果本身沒有發起融合請求，則通過TCP/IP協議返回「同意」的回答，並且自身在30分鐘內不發起融合的請求，不然返回「拒絕」的回答。[8]X1接收返回的回答。只要有一個「拒絕」的回答，X1就向X返回「拒絕」的回答，否則返回「同意」的回答，[9]X接收X1返回的回答。如果是「拒絕」的回答，X就放棄發起融合操作的企圖。[10]經過上述的1-10步，必然有一個節點勝出，取得融合的領導權。假定X2勝出。[11]X2所在的細胞的疆域是[B1，B2]，X1的則是[B2+1，B3](注意，它們必定相鄰)。X2把它們合併成[B1，B3]。[12]X2通過TCP/IP協議向X1索取它的細胞內路由表，並把所取到的細胞內路由表的表項加入到自己的細胞內路由表中，[13]X2向自己新的細胞內路由表中的每個節點通過TCP/IP協議發送融合的結果[B1，B3]和自己新的細胞內路由表，[14]X2調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表，[15]收到融合結果的節點用收到的細胞內路由表替換自己的細胞內路由表；調用2中所述的細胞間路由表更新過程更新自己的細胞間路由表。
全文摘要
點對點環境的草履蟲自組織和協作路由方法屬於計算機網絡技術領域，其特徵在於通過引入細胞結構，在細胞的各節點內設立細胞內和細胞間的路由表，建立了路由、路由表維護、節電加入、細胞分離和融合五種程序操作和實現，在快速變化的點對點環境中和沒有中央伺服器的情況下實現可擴展的參與節點的自組織和協作路由，為實現點對點的系統打下基礎。
文檔編號H04L12/24GK1564543SQ200410033768
公開日2005年1月12日 申請日期2004年4月16日 優先權日2004年4月16日
發明者楊廣文, 陳明, 武永衛 申請人:清華大學