【正文】 而網(wǎng)絡(luò)中有106 個節(jié)點時，每個節(jié)點的路由表平均包括75個表項，預(yù)期的路由跳數(shù)是5。如果網(wǎng)絡(luò)中有109個節(jié)點，則路由表平均會有105項，而預(yù)期的路由步數(shù)也將增加到7。葉子節(jié)點集維護的是nodeId和本節(jié)點最接近的節(jié)點，其中一半是nodeId大于當(dāng)前節(jié)點的，另一半是nodeId小于當(dāng)前節(jié)點的。葉子節(jié)點集在路由時需要用到。鄰居節(jié)點集維護按給定的評測指標(biāo)距離本節(jié)點最近的節(jié)點，正常的路由過程并不使用鄰居節(jié)點集，它的主要作用是維護路由的本地性。通常這兩個集合的大小分別為2b或者22b。 Pastry的路由Pastry的路由過程是：節(jié)點收到一條查詢消息時，首先檢查該消息的關(guān)鍵字是否落在葉子節(jié)點集范圍內(nèi)。如果是，則直接把消息轉(zhuǎn)發(fā)給對應(yīng)的節(jié)點，也就是葉子節(jié)點集中nodeId和關(guān)鍵字最接近的節(jié)點。如果關(guān)鍵字沒有落在葉子節(jié)點集范圍內(nèi)，節(jié)點就會把消息轉(zhuǎn)發(fā)給路由表中的一個節(jié)點，該節(jié)點的nodeId和關(guān)鍵字的相同前綴至少要比當(dāng)前節(jié)點的nodeId和關(guān)鍵字的相同前綴長一個數(shù)位。如果路由表中相應(yīng)的表項為空，或者表項中對應(yīng)的節(jié)點不可達，這時候查詢消息將被轉(zhuǎn)發(fā)給前綴長度相同但是節(jié)點號數(shù)值更接近關(guān)鍵字的節(jié)點。除非消息已經(jīng)到達目的節(jié)點，否則這樣的節(jié)點一定位于葉子節(jié)點集中。而且，只要葉子節(jié)點集中一半以上的節(jié)點不同時失效，就一定可以找到滿足要求的節(jié)點。很明顯，路由的每一步都比上一步向目標(biāo)節(jié)點前進了一步，因此路由過程總是收斂的。 節(jié)點加入和退出 新節(jié)點加入時需要初始化自身的狀態(tài)表，并通知其他節(jié)點自己已經(jīng)加入系統(tǒng)。假定新加入節(jié)點的nodeId為X，同時假定X在加入Pastry之前知道系統(tǒng)中和自己距離相近的節(jié)點A。新節(jié)點X首先請求A路由一條“加入”消息，消息的關(guān)鍵字就是X。這條消息最終會到達nodeId和X最接近的節(jié)點Z。作為應(yīng)答，節(jié)點A、節(jié)點Z以及從A到Z的路徑上所有經(jīng)過的節(jié)點都會把自己的狀態(tài)表發(fā)送給節(jié)點X。節(jié)點X利用這些信息初始化自己的狀態(tài)表，然后節(jié)點X再通知其他節(jié)點它已經(jīng)加入了系統(tǒng)。從交換的消息數(shù)量上說，節(jié)點加入操作的復(fù)雜度為O（log2bN）。Pastry中節(jié)點很可能失效或者突然離開系統(tǒng)。若nodeId空間中的相鄰節(jié)點無法和某個節(jié)點通信時，就認為該節(jié)點失效了。一旦節(jié)點檢測出其葉子節(jié)點集L中的某個節(jié)點失效，它就會請求該集合中nodeId最大或最小的節(jié)點把其葉子節(jié)點集L’發(fā)送過來。（如果失效節(jié)點的nodeId比當(dāng)前節(jié)點的nodeId大，則用葉子集中nodeId最大的節(jié)點，反之則用nodeId最小的節(jié)點。）當(dāng)前節(jié)點將從L’中選擇一個L中沒有的活動節(jié)點來替代失效節(jié)點。如果節(jié)點檢測出其路由表中某項對應(yīng)的節(jié)點失效，它將從該項所在的路由表行中選擇另一個節(jié)點，要求該節(jié)點把路由表中對應(yīng)位置的項發(fā)過來。如果當(dāng)前節(jié)點的路由表中對應(yīng)行已經(jīng)沒有可用節(jié)點了，那么當(dāng)前節(jié)點將從路由表的下一行中選擇一個節(jié)點，這個過程將繼續(xù)到當(dāng)前節(jié)點能夠得到一個替代失效節(jié)點的節(jié)點號，或者當(dāng)前節(jié)點遍歷了路由表為止。節(jié)點也會周期性地和鄰居節(jié)點集中的節(jié)點交換信息以檢測這些節(jié)點是否仍在Pastry系統(tǒng)中，如果節(jié)點檢測出其鄰居節(jié)點集中的某個節(jié)點失效，它將請求其他鄰居節(jié)點把其鄰居節(jié)點集發(fā)送過來并從中選擇一個新的鄰居節(jié)點替換失效節(jié)點。 CANUC Berkeley提出的CAN（Content Addressable Network，內(nèi)容尋址網(wǎng)絡(luò)）【25】實現(xiàn)了文件索引和存放位置的有效映射，不需要任何形式的中央控制點，節(jié)點只需要維護少量的控制狀態(tài)而且狀態(tài)數(shù)量獨立于系統(tǒng)中的節(jié)點數(shù)量，具有完全自組織和分布式的結(jié)構(gòu)，并且有良好的可擴展性和容錯性。 CAN的設(shè)計CAN的設(shè)計基于虛擬的d維笛卡兒坐標(biāo)空間，這個坐標(biāo)空間完全是邏輯的，和任何物理坐標(biāo)系統(tǒng)都沒有關(guān)系。在任何時候，整個坐標(biāo)空間動態(tài)地分配給系統(tǒng)中的所有節(jié)點，每個節(jié)點負責(zé)維護獨立的互不相交的一塊區(qū)域。CAN中的節(jié)點自組織成一個代表這個虛擬坐標(biāo)空間的重疊網(wǎng)絡(luò)（overlay network）。每個節(jié)點要了解并維護相鄰區(qū)域中節(jié)點的IP地址,用這些鄰居信息構(gòu)成自身的坐標(biāo)路由表。有了這張表，CAN可以在坐標(biāo)空間中任意兩點間進行尋路。[0, 1][0, 1]的笛卡兒坐標(biāo)空間劃分成五個節(jié)點區(qū)域的情況。虛擬坐標(biāo)空間采用下面的方法保存（K, V）對。當(dāng)保存（K1, V1）時，使用統(tǒng)一的哈希函數(shù)把關(guān)鍵字K1映射成坐標(biāo)空間中的點P。那么這個值將被保存在該點所在區(qū)域的節(jié)點中。當(dāng)需要查詢關(guān)鍵字K1對應(yīng)的值時，任何節(jié)點都可以使用同樣的哈希函數(shù)找到K1對應(yīng)的點P，然后從該點對應(yīng)的節(jié)點取出相應(yīng)的值V1。如果此節(jié)點不是發(fā)起查詢請求的節(jié)點，CAN將負責(zé)將此查詢請求轉(zhuǎn)發(fā)到P所在區(qū)域的節(jié)點上。因此，有效的路由機制是CAN中的一個關(guān)鍵問題。 五個節(jié)點維護的CAN虛平面 CAN的路由CAN中的路由很簡單，沿著坐標(biāo)空間中從發(fā)起請求的點到目的點之間的一條路徑轉(zhuǎn)發(fā)即可。為此，每個CAN節(jié)點都要保存一張坐標(biāo)路由表，其中包括它的鄰居節(jié)點的IP地址和其維護的虛擬坐標(biāo)區(qū)域。兩個節(jié)點互為鄰居是指：在d維坐標(biāo)空間中，兩個節(jié)點維護的區(qū)域在d－1維的坐標(biāo)上有重疊而在剩下的一維坐標(biāo)上相互鄰接。例如，而D和B就不是鄰接節(jié)點, 因為D和B在X軸和Y軸上都鄰接。每條CAN消息都包括目的點坐標(biāo)。路由時節(jié)點只要朝著目標(biāo)節(jié)點的方向把消息轉(zhuǎn)發(fā)給自己的鄰居節(jié)點即可。 CAN的查找示例如果一個d維空間劃分成n個相等的區(qū)域，那么平均路由長度是(d/4)(n1/d)，每個節(jié)點只需要維護2d個鄰居節(jié)點的信息。這個結(jié)果表明CAN的可擴展性很好，節(jié)點數(shù)增加時每個節(jié)點維護的狀態(tài)信息不變，而路由長度只是以O(shè)（n1/d）的數(shù)量級增長。因為坐標(biāo)空間中兩點之間可以有許多條不同的路徑，所以單個節(jié)點的失效對CAN基本上沒有太大的影響。遇到失效節(jié)點時，CAN會自動沿著其他的路徑進行路由。 節(jié)點加入和退出 因為整個CAN空間要分配給系統(tǒng)中現(xiàn)有的全部節(jié)點，當(dāng)一個新的節(jié)點加入網(wǎng)絡(luò)時必須得到自己的一塊坐標(biāo)空間。CAN通過分割現(xiàn)有的節(jié)點區(qū)域?qū)崿F(xiàn)這一過程。它把某個現(xiàn)有節(jié)點的區(qū)域分裂成同樣大小的兩塊，自己保留其中的一塊而另一塊分給新加入的節(jié)點。整個過程分為以下三步：1. 新節(jié)點首先找到一個已經(jīng)在CAN中的節(jié)點。2. 新節(jié)點使用CAN的路由機制找到一個區(qū)域?qū)⒁环指畹墓?jié)點。3. 執(zhí)行分割操作，然后原有區(qū)域的鄰接區(qū)域必須被告知發(fā)生了分割，這樣新節(jié)點才能被別的節(jié)點路由到。當(dāng)節(jié)點離開CAN時，必須保證它的區(qū)域被系統(tǒng)中剩余的節(jié)點接管，也即分配給其他仍然在系統(tǒng)中的節(jié)點。一般是由某個鄰居節(jié)點來接管這個區(qū)域和所有的索引數(shù)據(jù)（K，V）對。如果某個鄰居節(jié)點負責(zé)的區(qū)域可以和離開節(jié)點負責(zé)的區(qū)域合并形成一個大的區(qū)域，那么將由這個鄰居節(jié)點執(zhí)行合并操作。否則，該區(qū)域?qū)⒔唤o其鄰居節(jié)點中區(qū)域最小的節(jié)點負責(zé)。也就是說，這個節(jié)點將臨時負責(zé)兩個區(qū)域。正常情況下，每個節(jié)點向其所有鄰居節(jié)點發(fā)送周期性的更新消息，消息中包括自身的區(qū)域范圍、它的鄰居列表以及這些鄰居節(jié)點負責(zé)的區(qū)域范圍。如果多次沒有接收到某個鄰居的更新消息，那么節(jié)點就認為這個鄰居失效了。這時，節(jié)點將啟動接管機制，并啟動一個時鐘。失效節(jié)點的每個鄰居節(jié)點相互獨立地執(zhí)行該過程，每個時鐘大小都和相應(yīng)節(jié)點負責(zé)的區(qū)域面積成比例。如果時鐘超時，節(jié)點將向失效節(jié)點的所有鄰居節(jié)點發(fā)送接管消息，該消息中包括它自己的區(qū)域面積信息。當(dāng)某個節(jié)點接收到接管消息后，如果它的區(qū)域面積比發(fā)出消息的節(jié)點大，那么它將取消接管操作。否則它將發(fā)出自己的取代消息。采用這種機制可以有效地選擇面積最小的鄰居節(jié)點來接管失效節(jié)點。在特殊情況下，還有可能出現(xiàn)多個相鄰的節(jié)點同時失效的情況。例如，節(jié)點檢測到某個節(jié)點失效，但是失效節(jié)點地鄰居中超過一半可能都不可達。這時，如果讓該節(jié)點接管失效節(jié)點地區(qū)域，就有可能導(dǎo)致CAN中狀態(tài)不一致。所以在這種情況下，CAN在執(zhí)行修復(fù)操作之前，會搜索失效區(qū)域附近的節(jié)點，搜索逐步擴大直至獲得足夠的鄰居狀態(tài)，以便安全地開始接管過程。 TapestryTapestry【26】是UC Berkeley提出的一種新型的P2P網(wǎng)絡(luò)定位和路由算法。該算法可以對消息進行與位置無關(guān)的路由，把查詢消息傳遞到最近的存儲有目標(biāo)對象拷貝的節(jié)點。Tapestry具有自組織、容錯和負載平衡等特點。每個Tapestry 節(jié)點只需維護O（log N）大小的路由表信息，路由最多在O（log N）跳數(shù)內(nèi)完成。 Tapestry的設(shè)計Tapestry從一個標(biāo)識符空間中為每個節(jié)點隨機分配一個節(jié)點標(biāo)識符nodeID，對象也從同一個標(biāo)識符空間中分配一個全局唯一標(biāo)識符GUID（globally unique identifier）。Tapestry使用SHA1來產(chǎn)生標(biāo)識符，使得nodeID和GUID均勻分布在標(biāo)識符空間中。為了討論問題的方便，用Nid來表示節(jié)點N的標(biāo)識符，用OG表示對象O的標(biāo)識符。Tapestry目前使用160比特的標(biāo)識符空間，標(biāo)識符用一個全局統(tǒng)一的進制表示（例如使用16進制，則標(biāo)識符是一個40位的數(shù)字），所有的節(jié)點依據(jù)標(biāo)識符自組織成一個重疊網(wǎng)絡(luò)。Tapestry動態(tài)地把每個標(biāo)識符G映射到當(dāng)前系統(tǒng)中一個節(jié)點上，該節(jié)點稱為G的根節(jié)點，表示為GR。如果某節(jié)點的Nid＝G，則這個節(jié)點就是G的根節(jié)點。為了轉(zhuǎn)發(fā)查詢消息，每個節(jié)點需要維護一個鄰居映射表，每個表項包括一個鄰居節(jié)點的標(biāo)識符和IP地址。往GR路由時，消息將沿著鄰居指針向節(jié)點標(biāo)識符在標(biāo)識符空間中更接近G的節(jié)點轉(zhuǎn)發(fā)（例如，匹配更大的前綴）。Tapestry中的每個節(jié)點都保存有鄰居映射表。鄰居映射表可以用于把消息按照目的地址一位一位地向前傳遞，比如從4***=42**98=42A*=目的節(jié)點42AD（這里*表示通配符）。這種方式類似于IP分組轉(zhuǎn)發(fā)過程中的最長前綴匹配。節(jié)點N的鄰居映射表分為多個級別，每個級別包含的鄰居節(jié)點的數(shù)量等于標(biāo)識符表示法的基數(shù)，而每個級別中鄰居節(jié)點標(biāo)識符和本節(jié)點標(biāo)識符的相同前綴都比前一級別多一個數(shù)位。也就是說，第j級鄰居表的第i項是標(biāo)識符以prefix(N, j1) ＋ “i”為前綴而且離當(dāng)前節(jié)點最近的鄰居節(jié)點。例如，節(jié)點325AE的鄰居映射表中第4級第9項是系統(tǒng)中標(biāo)識符以325 + “9” =3259為前綴的某個節(jié)點。 Tapestry節(jié)點鄰居實例，從圖中可以看到第一級的鄰居節(jié)點標(biāo)識和本節(jié)點標(biāo)識沒有共同前綴，而第二級的鄰居節(jié)點標(biāo)識都以4開頭，即和本節(jié)點標(biāo)識具有相同的一個數(shù)位的前綴。 Tapestry的路由 Tapestry采用的基本查找和路由機制和【30】很類似。當(dāng)一條查找消息到達傳遞過程中的第n個節(jié)點時，該節(jié)點和目的節(jié)點的共同前綴長度至少大于n。為了進行轉(zhuǎn)發(fā)，該節(jié)點將查找鄰居映射表的第n+1級中和目的標(biāo)識符下一數(shù)位相匹配的鄰居節(jié)點。轉(zhuǎn)發(fā)過程將在每個節(jié)點中依次進行直到到達目的節(jié)點。這種方法可以保證路由至多經(jīng)過logbN個節(jié)點就可以到達目的節(jié)點，這里N是節(jié)點標(biāo)識符名字空間的大小，而b是標(biāo)識符使用的基數(shù)。同樣，由于每個節(jié)點的鄰居映射表的每個級別只需要保存b個表項，因此，鄰居映射表的空間為blogbN。 Tapestry路由實例。圖中節(jié)點標(biāo)識符的基數(shù)是4，查詢消息從5230發(fā)出，目的節(jié)點是42AD。Tapestry中的節(jié)點在共享數(shù)據(jù)時被稱為服務(wù)器，請求數(shù)據(jù)時被稱為客戶，轉(zhuǎn)發(fā)消息時被稱為路由器。也就是說每個節(jié)點可以同時具有客戶、服務(wù)器和路由器的功能。服務(wù)器S通過向?qū)ο驩（GUID為OG）的根節(jié)點OR定期的發(fā)送消息來報告S保存有對象O。在這條發(fā)布路徑上的每個節(jié)點都保存關(guān)于這個對象O的位置信息指針OG, S，這里的位置信息只是一個指向S的指針，而并不是對象O的拷貝。當(dāng)多個都存有同一對象拷貝的服務(wù)器分別向根結(jié)點發(fā)布消息時，路徑上的每個節(jié)點按各個服務(wù)器離自己的網(wǎng)絡(luò)時延遞增的順序保存這些位置指針列表。當(dāng)需要定位一個對象O時，客戶向?qū)ο驩的根節(jié)點發(fā)出查詢消息，查詢消息轉(zhuǎn)發(fā)路徑上的每個節(jié)點都檢查自己是否存有對象O的位置指針，如果有，該節(jié)點直接把查詢消息轉(zhuǎn)發(fā)個服務(wù)器S，否則，消息將到達O的根節(jié)點，然后由根節(jié)點把查詢消息轉(zhuǎn)發(fā)給服務(wù)器。Tapestry有一個重要的特性是：查詢消息可以被轉(zhuǎn)發(fā)到距離客戶最近的存有對象拷貝的服務(wù)器上。在Tapestry中，從兩個臨近節(jié)點向同一個目的節(jié)點OR發(fā)出兩條消息時，它們的轉(zhuǎn)發(fā)路徑很快就會交叉，這是因為路由過程的每一步都是使得下一個節(jié)點標(biāo)識符和OR具有更長的相同前綴；到根結(jié)點的路徑只是目的標(biāo)識符的函數(shù)，而不是消息發(fā)起節(jié)點標(biāo)識符的函數(shù)；而且，路由過程中的下一跳鄰居節(jié)點是根據(jù)網(wǎng)絡(luò)距離選擇的，因而客戶離服務(wù)器越近，那么查詢路徑碰到發(fā)布路徑的速度就越快。也就是說，查詢消息會被轉(zhuǎn)發(fā)到最近的服務(wù)器上。 節(jié)點加入和退出 Tapestry的節(jié)點加入算法和Pastry類似。節(jié)點N在加入Tapestry網(wǎng)絡(luò)之前，也需要知道一個已經(jīng)在網(wǎng)絡(luò)中的節(jié)點G。然后N通過G發(fā)出路由自己的節(jié)點ID的請求，根據(jù)經(jīng)過的節(jié)點的對應(yīng)的鄰居節(jié)點表構(gòu)造自己的鄰居節(jié)點表。構(gòu)造過程中還需要進行一些優(yōu)化工作。構(gòu)造完自己的數(shù)據(jù)結(jié)構(gòu)后，節(jié)點N將通知網(wǎng)絡(luò)中的其他節(jié)點自己已經(jīng)加入網(wǎng)絡(luò)。通知只針對在N的鄰居映射表中的主鄰居節(jié)點和二級鄰居節(jié)點進行。Tapestry采用兩種機制處理節(jié)點的退出。一種情況是節(jié)點從網(wǎng)絡(luò)中自行消失（主要原因是節(jié)點失效），在這種情況下，它的鄰居可以檢測到它已經(jīng)退出網(wǎng)絡(luò)并可以相應(yīng)的調(diào)整路由表。另一種機制是節(jié)點在退出系統(tǒng)之前通過后向指針通過所有把它作為鄰居的節(jié)點，這些節(jié)點會相應(yīng)調(diào)整路由表并通知對象服務(wù)器該節(jié)點已經(jīng)退出網(wǎng)絡(luò)。檢測正常操作過程中的鏈路和服務(wù)器失效，可以使用TCP連接超時機制。除此之外，每個Tapestry節(jié)點都使用后向指針周期性的發(fā)送“心跳”(heartbeats)UDP分組給把自己加入鄰居映射表的節(jié)點。每個節(jié)點都可以根據(jù)自己收到的心跳分組來決定自己的鄰居映射表中是否有節(jié)點失效。在鄰居節(jié)點表中，除了主鄰居節(jié)點（最近的鄰居）之外，每個路由項還保存了兩個備份的鄰居節(jié)點，當(dāng)檢測到主鄰居節(jié)點失效后，鄰居節(jié)點表將順序選擇備份鄰居節(jié)點。 本章小結(jié)目前，P2P文件共享系統(tǒng)已經(jīng)成為Internet上最為流行的應(yīng)用之一，也是Internet上業(yè)務(wù)流量的一個重要來源。因而，這些系統(tǒng)是否具有可擴展性是一個很重要的衡量指標(biāo)，但很遺憾的是