EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件

EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)2007年6月19日1EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)2007年6月19日1目錄Kademlia簡介及應(yīng)用現(xiàn)狀節(jié)點(diǎn)本地行為節(jié)點(diǎn)初始化讀取配置文件生成ID構(gòu)造本地二叉樹二叉樹生成規(guī)則生成k-bucket節(jié)點(diǎn)之間的交互行為節(jié)點(diǎn)間距離加入網(wǎng)絡(luò)發(fā)送加入網(wǎng)絡(luò)請求處理請求響應(yīng)查找查找其他節(jié)點(diǎn)查找文件（key）對查找二叉樹的使用路由信息的更新現(xiàn)在已知節(jié)點(diǎn)是否仍然有效更新二叉樹更新k-bucket存儲發(fā)布節(jié)點(diǎn)自身要求其他相關(guān)節(jié)點(diǎn)存儲發(fā)布文件信息，其他相關(guān)節(jié)點(diǎn)存儲2目錄Kademlia簡介及應(yīng)用現(xiàn)狀22KADEMLIA簡介Kademlia協(xié)議是美國紐約大學(xué)的PetarP.Maymounkov和DavidMazieres在2002年發(fā)布的一項(xiàng)研究結(jié)果《Kademlia:Apeer-to-peerinformationsystembasedontheXORmetric》。Kademlia是一種分布式哈希表（DHT）技術(shù)，Kademlia通過獨(dú)特的以異或算法（XOR）為距離度量基礎(chǔ)，建立了一種全新的DHT拓?fù)浣Y(jié)構(gòu)，相比于其他算法，大大提高了路由查詢速度。3KADEMLIA簡介Kademlia協(xié)議是美國紐約大學(xué)的P3當(dāng)前應(yīng)用現(xiàn)狀在2005年5月著名的BitTorrent在4.1.0版實(shí)現(xiàn)基于Kademlia協(xié)議的DHT技術(shù)后，很快國內(nèi)的BitComet和BitSpirit也實(shí)現(xiàn)了和BitTorrent兼容的DHT技術(shù)，實(shí)現(xiàn)trackerless下載方式。另外，emule中也很早就實(shí)現(xiàn)了基于Kademlia類似的技術(shù)（BT中叫DHT，emule中也叫Kad，），和BT軟件使用的Kad技術(shù)的區(qū)別在于key、value和nodeID的計算方法不同。4當(dāng)前應(yīng)用現(xiàn)狀在2005年5月著名的BitTorrent4EMULE中KADEMLIA網(wǎng)絡(luò)部分CKademlia是整個Kademlia網(wǎng)絡(luò)的主控類，可以直接開始或者停止Kademlia網(wǎng)，并且含有Process方法來處理日常事務(wù)。CPrefs負(fù)責(zé)處理自身的Kademlia相關(guān)信息，如自身的ID等。CRoutingZone，CRoutingBin和CContact三個類組成了每個節(jié)點(diǎn)所了解的聯(lián)系信息以及由這些聯(lián)系信息所組成的數(shù)據(jù)結(jié)構(gòu)。CKademliaUDPListener負(fù)責(zé)處理網(wǎng)絡(luò)信息。CIndexed負(fù)責(zé)處理本地存儲的索引信息。CSearch，CSearchManager負(fù)責(zé)處理和搜索有關(guān)的操作，其中前者表示的是一個單一的搜索任務(wù)，后者負(fù)責(zé)對所有搜索任務(wù)進(jìn)行處理。CUInt128負(fù)責(zé)處理一個128位的長整數(shù)，并且內(nèi)置其各種運(yùn)算。5EMULE中KADEMLIA網(wǎng)絡(luò)部分CKademlia是整個5節(jié)點(diǎn)本地行為6節(jié)點(diǎn)本地行為66節(jié)點(diǎn)初始化讀取本地配置文件在emule中，配置文件比較多，用于Kademlia網(wǎng)絡(luò)的配置文件是：

src_index.datkey_index.datload_index.dat（索引Indexed.cpp）nodes.dat（上次程序啟動時連接上的節(jié)點(diǎn)RoutingZone.cpp）preferencesKad.dat(上次程序啟動時本地節(jié)點(diǎn)的IP、ID、Port信息Prefs.cpp)生成IDKad網(wǎng)絡(luò)中每個節(jié)點(diǎn)都有一個160bit的ID值作為標(biāo)志符。節(jié)點(diǎn)ID的生成，可以是根據(jù)特定信息Hash或者簡單的隨機(jī)生成（emule中ID為隨機(jī)生成）。在emule中,CUInt128類中定義了ID的生成方式,結(jié)點(diǎn)之間ID做的異或運(yùn)算也在CUInt128里;emule中定義了4個ULong的數(shù)組,總共正好是128位；在Prefs.cpp中Init函數(shù)中對m_uClientID進(jìn)行了隨機(jī)值的設(shè)置:m_uClientID.SetValueRandom();函數(shù)中調(diào)用cryptlib中的函數(shù)生成16位的數(shù)據(jù)塊,然后填充,填充8次,共128位;7節(jié)點(diǎn)初始化讀取本地配置文件77構(gòu)造本地結(jié)點(diǎn)二叉樹在Kad網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都被當(dāng)作一顆二叉樹的葉子，并且節(jié)點(diǎn)的位置都由其ID值的最短前綴唯一的確定。每一個節(jié)點(diǎn)都在本地維護(hù)一個二叉樹,來標(biāo)示網(wǎng)絡(luò)中節(jié)點(diǎn)與自己的距離遠(yuǎn)近,自己則是二叉樹的根節(jié)點(diǎn)；本地結(jié)點(diǎn)二叉樹生成規(guī)則：最高層的子樹，由整顆樹不包含自己的樹的另一半組成；下一層子樹由剩下部分不包含自己的一半組成；依此類推，直到分割完整顆樹。8構(gòu)造本地結(jié)點(diǎn)二叉樹在Kad網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都被當(dāng)作一顆二叉8EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件9EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件10每一個節(jié)點(diǎn)都在本地維護(hù)一個二叉樹,來標(biāo)示網(wǎng)絡(luò)中節(jié)點(diǎn)與自己的距離遠(yuǎn)近,自己則是二叉樹的根節(jié)點(diǎn)；否則測量自己和t的距離，并從自己對應(yīng)的K桶中選擇α個節(jié)點(diǎn)的信息給x。在emule中，配置文件比較多，用于Kademlia網(wǎng)絡(luò)的配置文件是：計算到t的距離：d(x,y)=x⊕y也就是說,每個結(jié)點(diǎn)都對自己附近的情況非常了解,而隨著距離的增大,了解的程度不斷降低降低。dat（上次程序啟動時連接上的節(jié)點(diǎn)RoutingZone.由于每次查詢都能從更接近目標(biāo)節(jié)點(diǎn)的K桶中獲取信息，這樣的機(jī)制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少1bit）的效果，從而保證整個查詢過程的收斂速度為O(logN)，這里N為網(wǎng)絡(luò)全部節(jié)點(diǎn)的數(shù)量。否則測量自己和t的距離，并從自己對應(yīng)的K桶中選擇α個節(jié)點(diǎn)的信息給x。在2005年5月著名的BitTorrent在4.需要說明的是，只有第一步查詢的節(jié)點(diǎn)101，是節(jié)點(diǎn)0011已經(jīng)知道的，后面各步查詢的節(jié)點(diǎn)，都是由上一步查詢返回的更接近目標(biāo)的節(jié)點(diǎn)，這是一個遞歸操作的過程。在Kad網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都被當(dāng)作一顆二叉樹的葉子，并且節(jié)點(diǎn)的位置都由其ID值的最短前綴唯一的確定。另外，emule中也很早就實(shí)現(xiàn)了基于Kademlia類似的技術(shù)（BT中叫DHT，emule中也叫Kad，），和BT軟件使用的Kad技術(shù)的區(qū)別在于key、value和nodeID的計算方法不同。uint32CRoutingZone::GetClosestTo沒有迅速響應(yīng)的節(jié)點(diǎn)將被迅速排除出候選列表，直到其響應(yīng)。的新K桶，并對原K桶內(nèi)的節(jié)點(diǎn)信息按照新的K桶前綴值進(jìn)行重新分配Kademlia協(xié)議包括四種遠(yuǎn)程RPC操作：PING、STORE、FIND_NODE、FIND_VALUE。生成K-BUCKETK-bucket構(gòu)造了Kademlia網(wǎng)絡(luò)的路由表每個節(jié)點(diǎn)都保存和自己一定距離范圍內(nèi)的節(jié)點(diǎn)信息，k-bucket存儲這些信息——

(IPaddress,UDPport,NodeID)數(shù)據(jù)列表。K桶內(nèi)部信息存放位置是根據(jù)上次看到的時間順序排列，最近（least-recently）看到的放在頭部，最后（most-recently）看到的放在尾部。每個桶都有最大不超過k個的數(shù)據(jù)項(xiàng)，這里k是為平衡系統(tǒng)性能和網(wǎng)絡(luò)負(fù)載而設(shè)置的一個常數(shù)，但必須是偶數(shù)；在emule中k=10。11每一個節(jié)點(diǎn)都在本地維護(hù)一個二叉樹,來標(biāo)示網(wǎng)絡(luò)中節(jié)點(diǎn)與自己的距11由于每個K桶覆蓋距離的范圍呈指數(shù)關(guān)系增長，這就形成了離自己近的節(jié)點(diǎn)的信息多，離自己遠(yuǎn)的節(jié)點(diǎn)的信息少，從而可以保證路由查詢過程是收斂。也就是說,每個結(jié)點(diǎn)都對自己附近的情況非常了解,而隨著距離的增大,了解的程度不斷降低降低。經(jīng)過證明，對于一個有N個節(jié)點(diǎn)的Kad網(wǎng)絡(luò)，最多只需要經(jīng)過logN步查詢，就可以準(zhǔn)確定位到目標(biāo)節(jié)點(diǎn)。12由于每個K桶覆蓋距離的范圍呈指數(shù)關(guān)系增長，這就形成了離自己近12EMULE中生成K-BUCKET具體實(shí)現(xiàn)在RoutingBin.h中定義了一個list： ContactListm_listEntries;即為k-bucketCRoutingZone實(shí)際上是一個二叉樹，當(dāng)當(dāng)前的CRoutingZone類為整個二叉樹的葉節(jié)點(diǎn)時，這個指向CRoutingBin類型的指針才有意義。（此時CRoutingZone作為網(wǎng)絡(luò)中的節(jié)點(diǎn)應(yīng)該包含一個k-bucket），由于CRoutingBin中定義了一個ContactList，這個ContactList即為k-bucket。13EMULE中生成K-BUCKET具體實(shí)現(xiàn)在RoutingBi13節(jié)點(diǎn)間交互行為14節(jié)點(diǎn)間交互行為1414KADEMLIA協(xié)議的操作與EMULE中對應(yīng)關(guān)系Kademlia協(xié)議包括四種遠(yuǎn)程RPC操作：PING、STORE、FIND_NODE、FIND_VALUE。PING操作的作用是探測一個節(jié)點(diǎn)，用以判斷其是否仍然在線。對應(yīng)于emule中PING-PONG操作，即發(fā)送KADEMLIA_HELLO_REQ和KADEMLIA_HELLO_RES請求STORE操作的作用是通知一個節(jié)點(diǎn)存儲一個<key,value>對。對應(yīng)emule中publish操作以及Store操作FIND_NODE操作使用一個160bit的ID作為參數(shù)。本操作的接受者返回它所知道的更接近目標(biāo)ID的K個節(jié)點(diǎn)的(IPaddress,UDPport,NodeID)信息。對應(yīng)emule中查找節(jié)點(diǎn)的操作FIND_VALUE操作和FIND_NODE操作類似，不同的是它只需要返回一個節(jié)點(diǎn)的(IPaddress,UDPport,NodeID)信息。如果本操作的接受者收到同一個key的STORE操作，則會直接返回存儲的value值。對應(yīng)emule中文件檢索的操作15KADEMLIA協(xié)議的操作與EMULE中對應(yīng)關(guān)系Kademl15節(jié)點(diǎn)間距離判斷兩個節(jié)點(diǎn)x,y的距離遠(yuǎn)近是基于數(shù)學(xué)上的異或的二進(jìn)制運(yùn)算，d(x,y)=x⊕y，既對應(yīng)位相同時結(jié)果為0，不同時結(jié)果為1。異或操作具有如下性質(zhì)：非負(fù)性對稱性三角不等式單向性傳遞性異或運(yùn)算提供了一種在Kad網(wǎng)絡(luò)上進(jìn)行可靠距離度量的方法。假如Kad網(wǎng)絡(luò)上所有其他用戶都按照和你之間距離的遠(yuǎn)近而排成一條長隊(duì)，如果已知另一個結(jié)點(diǎn)的ID，那么你很容易計算出他在這條長隊(duì)中的位置；如果給定一個距離，你也能很容易從這條長隊(duì)里找出與你的距離最接近給定距離的那些結(jié)點(diǎn)。16節(jié)點(diǎn)間距離判斷兩個節(jié)點(diǎn)x,y的距離遠(yuǎn)近是基于數(shù)學(xué)上的異16EMULE中節(jié)點(diǎn)距離計算的具體實(shí)現(xiàn)CUInt128類根據(jù)128位ID值進(jìn)行異或運(yùn)算，得到節(jié)點(diǎn)之間距離CRoutingZoneuint32CRoutingZone::GetClosestToCRoutingBin節(jié)點(diǎn)之間距離具體運(yùn)算是在查找和發(fā)布時進(jìn)行的，此時CRoutingBin中的k-bucket需要計算節(jié)點(diǎn)之間的距離來確定查找的遞進(jìn)性以及應(yīng)該發(fā)布到哪些節(jié)點(diǎn)uint32CRoutingBin::GetClosestTo17EMULE中節(jié)點(diǎn)距離計算的具體實(shí)現(xiàn)CUInt128類1717節(jié)點(diǎn)加入網(wǎng)絡(luò)如果節(jié)點(diǎn)u要想加入Kad網(wǎng)絡(luò)，它必須要和一個已經(jīng)在Kad網(wǎng)絡(luò)的節(jié)點(diǎn)，比如w，取得聯(lián)系。u首先把w插入自己適當(dāng)?shù)腒桶中，然后對自己的節(jié)點(diǎn)ID執(zhí)行一次FIND_NODE操作，然后根據(jù)接收到的信息更新自己的K桶內(nèi)容。通過對自己鄰近節(jié)點(diǎn)由近及遠(yuǎn)的逐步查詢，u完成了仍然是空的K桶信息的構(gòu)建，同時也把自己的信息發(fā)布到其他節(jié)點(diǎn)的K桶中。在Kad網(wǎng)絡(luò)中，每個節(jié)點(diǎn)的路由表都表示為一顆二叉樹，葉子節(jié)點(diǎn)為K桶，K桶存放的是有相同ID前綴的節(jié)點(diǎn)信息，而這個前綴就是該K桶在二叉樹中的位置。這樣，每個K桶都覆蓋了ID空間的一部分，全部K桶的信息加起來就覆蓋了整個160bit的ID空間，而且沒有重疊。以節(jié)點(diǎn)u為例，其路由表的生成過程為：1．最初，u的路由表為一個單個的K桶，覆蓋了整個160bitID空間;2．當(dāng)學(xué)習(xí)到新的節(jié)點(diǎn)信息后，則u會嘗試把新節(jié)點(diǎn)的信息，根據(jù)其前綴值插入到對應(yīng)的K桶中：①如果該K桶沒有滿，則新節(jié)點(diǎn)直接插入到這個K桶中；②如果該K桶已經(jīng)滿了，⑴如果該K桶覆蓋范圍包含了節(jié)點(diǎn)u的ID，則把該K桶分裂為兩個大小相同的新K桶，并對原K桶內(nèi)的節(jié)點(diǎn)信息按照新的K桶前綴值進(jìn)行重新分配⑵如果該K桶覆蓋范圍沒有包節(jié)點(diǎn)u的ID，則直接丟棄該新節(jié)點(diǎn)信息3．上述過程不斷重復(fù)，最終會形成表1結(jié)構(gòu)的路由表。達(dá)到距離近的節(jié)點(diǎn)的信息多，距離遠(yuǎn)的節(jié)點(diǎn)的信息少的結(jié)果，保證了路由查詢過程能快速收斂。18節(jié)點(diǎn)加入網(wǎng)絡(luò)如果節(jié)點(diǎn)u要想加入Kad網(wǎng)絡(luò)，它必須要和一個已18節(jié)點(diǎn)000的路由表生成演化19節(jié)點(diǎn)000的路由表生成演化1919節(jié)點(diǎn)0100的K-BUCKET分裂過程20節(jié)點(diǎn)0100的K-BUCKET分裂過程2020當(dāng)K桶010滿了之后，由于其覆蓋范圍包含了節(jié)點(diǎn)0100的ID，故該K桶分裂為兩個新的K桶：0101和0100，原K桶010的信息會根據(jù)其其前綴值重新分布到這兩個新的K桶中。注意，這里并沒有使用160bit的ID值表示法，只是為了方便原理的演示，實(shí)際Kad網(wǎng)絡(luò)中的ID值都是160bit的。21當(dāng)K桶010滿了之后，由于其覆蓋范圍包含了節(jié)點(diǎn)010021節(jié)點(diǎn)加入網(wǎng)絡(luò)發(fā)送加入請求處理請求響應(yīng)采用ping-pong機(jī)制機(jī)制CKademliaUDPListener類中函數(shù)ProcessPacket處理所有類型的消息22節(jié)點(diǎn)加入網(wǎng)絡(luò)發(fā)送加入請求2222EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件23EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件24節(jié)點(diǎn)查找以及文件查找查找其他節(jié)點(diǎn)查找文件（key）對查找二叉樹的使用25節(jié)點(diǎn)查找以及文件查找查找其他節(jié)點(diǎn)2525查找其他節(jié)點(diǎn)在Kademlia網(wǎng)絡(luò)中，節(jié)點(diǎn)搜索的實(shí)現(xiàn)方式是迭代式的搜索。這種方式就是說當(dāng)開始搜索某個ID時，在本地聯(lián)系人信息列表中查找到距離最近的聯(lián)系人，然后向它們發(fā)出搜索請求，這樣通常都能夠得到一些距離更近的聯(lián)系人信息，然后再向它們發(fā)送搜索請求，通過不斷得進(jìn)行這樣的搜索查詢，就能夠得到距離目標(biāo)ID最近的那些聯(lián)系人信息。這里對應(yīng)的消息代碼是KADEMLIA_REQ和KADEMLIA_RES。由于每次查詢都能從更接近目標(biāo)節(jié)點(diǎn)的K桶中獲取信息，這樣的機(jī)制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少1bit）的效果，從而保證整個查詢過程的收斂速度為O(logN)，這里N為網(wǎng)絡(luò)全部節(jié)點(diǎn)的數(shù)量。26查找其他節(jié)點(diǎn)在Kademlia網(wǎng)絡(luò)中，節(jié)點(diǎn)搜索的實(shí)現(xiàn)方式是迭26假如節(jié)點(diǎn)x要查找ID值為t的節(jié)點(diǎn)，Kad按照如下遞歸操作步驟進(jìn)行路由查找：計算到t的距離：d(x,y)=x⊕y從x的第[㏒d]個K桶中取出α個節(jié)點(diǎn)的信息（“[]”是取整符號），同時進(jìn)行FIND_NODE操作。如果這個K桶中的信息少于α個，則從附近多個桶中選擇距離最接近d的總共α個節(jié)點(diǎn)。對接受到查詢操作的每個節(jié)點(diǎn)，如果發(fā)現(xiàn)自己就是t，則回答自己是最接近t的；否則測量自己和t的距離，并從自己對應(yīng)的K桶中選擇α個節(jié)點(diǎn)的信息給x。x對新接收到的每個節(jié)點(diǎn)都再次執(zhí)行FIND_NODE操作，此過程不斷重復(fù)執(zhí)行，直到每一個分支都有節(jié)點(diǎn)響應(yīng)自己是最接近t的。沒有迅速響應(yīng)的節(jié)點(diǎn)將被迅速排除出候選列表，直到其響應(yīng)。通過上述查找操作，x得到了k個最接近t的節(jié)點(diǎn)信息。27查找步驟假如節(jié)點(diǎn)x要查找ID值為t的節(jié)點(diǎn)，Kad按照如下遞歸操27ALPHA=1時查詢流程28ALPHA=1時查詢流程2828查找文件當(dāng)用戶使用Kademlia網(wǎng)絡(luò)來進(jìn)行搜索并且下載文件的時候，首先是對一個關(guān)鍵詞進(jìn)行搜索，由于使用的是同樣的hash算法，這樣它只要找到ID值和計算出來的hash值結(jié)果相近的聯(lián)系人信息后，它就可以直接向它們發(fā)送搜索特定關(guān)鍵詞的請求了。如果得到了返回信息，那么搜索者就知道了這個關(guān)鍵詞對應(yīng)了多少文件，然后把這些文件的信息都列出來。當(dāng)用戶決定下載某個文件的時候，針對這一特定文件的搜索過程就開始了，這一次如果搜索成功，那么返回的就是這個文件的文件源信息。這樣emule接下來就只需要按照這些信息去連接相應(yīng)的地址，并且使用傳統(tǒng)的emule協(xié)議去和它們協(xié)商下載文件了。這里對應(yīng)的消息是KADEMLIA_SEARCH_REQ和KADEMLIA_SEARCH_RES。29查找文件當(dāng)用戶使用Kademlia網(wǎng)絡(luò)來進(jìn)行搜索并且下載文件29當(dāng)節(jié)點(diǎn)x要查詢<key,value>對時，和查找節(jié)點(diǎn)的操作類似，x選擇k個ID值最接近key值的節(jié)點(diǎn)，執(zhí)行FIND_VALUE操作，并對每一個返回的新節(jié)點(diǎn)重復(fù)執(zhí)行FIND_VALUE操作，直到某個節(jié)點(diǎn)返回value值。一旦FIND_VALUE操作成功執(zhí)行，則<key,value>對數(shù)據(jù)會緩存在沒有返回value值的最接近的節(jié)點(diǎn)上。這樣下一次查詢相同的key時就會更加快速的得到結(jié)果。通過這樣的方式，熱門<key,value>對數(shù)據(jù)的緩存范圍就逐步擴(kuò)大，使系統(tǒng)具有極佳的響應(yīng)速度30當(dāng)節(jié)點(diǎn)x要查詢<key,value>對時，和查找節(jié)點(diǎn)的操作30313131二叉樹中節(jié)點(diǎn)的查找Kad協(xié)議確保每個節(jié)點(diǎn)知道其各子樹的至少一個節(jié)點(diǎn)，只要這些子樹非空。在這個前提下，每個節(jié)點(diǎn)都可以通過ID值來找到任何一個節(jié)點(diǎn)。這個路由的過程是通過所謂的XOR（異或）距離得到的。節(jié)點(diǎn)通過在逐步底層的子樹間不斷學(xué)習(xí)并查詢最佳節(jié)點(diǎn)，獲得了越來越接近的節(jié)點(diǎn)，最終收斂到目標(biāo)節(jié)點(diǎn)上。32二叉樹中節(jié)點(diǎn)的查找Kad協(xié)議確保每個節(jié)點(diǎn)知道其各子樹的至少32333333需要說明的是，只有第一步查詢的節(jié)點(diǎn)101，是節(jié)點(diǎn)0011已經(jīng)知道的，后面各步查詢的節(jié)點(diǎn)，都是由上一步查詢返回的更接近目標(biāo)的節(jié)點(diǎn)，這是一個遞歸操作的過程。由于各節(jié)點(diǎn)路由信息的不確定性（節(jié)點(diǎn)動態(tài)加入和離開引起），圖2只是展示了多種可能搜索路徑的一個具體實(shí)現(xiàn)。怎么知道的呢？協(xié)議里規(guī)定的嗎34需要說明的是，只有第一步查詢的節(jié)點(diǎn)101，是節(jié)點(diǎn)0011已34從x的第[㏒d]個K桶中取出α個節(jié)點(diǎn)的信息（“[]”是取整符號），同時進(jìn)行FIND_NODE操作。①如果該K桶沒有滿，則新節(jié)點(diǎn)直接插入到這個K桶中；EMULE中生成K-BUCKET具體實(shí)現(xiàn)假如Kad網(wǎng)絡(luò)上所有其他用戶都按照和你之間距離的遠(yuǎn)近而排成一條長隊(duì)，如果已知另一個結(jié)點(diǎn)的ID，那么你很容易計算出他在這條長隊(duì)中的位置；根據(jù)128位ID值進(jìn)行異或運(yùn)算，得到節(jié)點(diǎn)之間距離節(jié)點(diǎn)通過在逐步底層的子樹間不斷學(xué)習(xí)并查詢最佳節(jié)點(diǎn)，獲得了越來越接近的節(jié)點(diǎn)，最終收斂到目標(biāo)節(jié)點(diǎn)上。在Kad網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都被當(dāng)作一顆二叉樹的葉子，并且節(jié)點(diǎn)的位置都由其ID值的最短前綴唯一的確定。每一個節(jié)點(diǎn)都在本地維護(hù)一個二叉樹,來標(biāo)示網(wǎng)絡(luò)中節(jié)點(diǎn)與自己的距離遠(yuǎn)近,自己則是二叉樹的根節(jié)點(diǎn)；對應(yīng)emule中publish操作以及Store操作通常節(jié)點(diǎn)會利用流經(jīng)自己的節(jié)點(diǎn)查詢操作來持續(xù)更新對應(yīng)的K桶信息。否則測量自己和t的距離，并從自己對應(yīng)的K桶中選擇α個節(jié)點(diǎn)的信息給x。當(dāng)節(jié)點(diǎn)x收到一個PRC消息時，發(fā)送者y的IP地址就被用來更新對應(yīng)的K桶，具體步驟如下：另外，emule中也很早就實(shí)現(xiàn)了基于Kademlia類似的技術(shù)（BT中叫DHT，emule中也叫Kad，），和BT軟件使用的Kad技術(shù)的區(qū)別在于key、value和nodeID的計算方法不同。CKademliaUDPListener類中函數(shù)ProcessPacket處理所有類型的消息KADEMLIA協(xié)議的操作與EMULE中對應(yīng)關(guān)系從x的第[㏒d]個K桶中取出α個節(jié)點(diǎn)的信息（“[]35節(jié)點(diǎn)有效性判斷

節(jié)點(diǎn)離開Kad網(wǎng)絡(luò)不需要發(fā)布任何信息，Kademlia協(xié)議的目標(biāo)之一就是能夠彈性工作在任意節(jié)點(diǎn)隨時失效的情況下。為此，Kad要求每個節(jié)點(diǎn)必須周期性的發(fā)布全部自己存放的<key,value>對數(shù)據(jù)，并把這些數(shù)據(jù)緩存在自己的k個最近鄰居處，這樣存放在失效節(jié)點(diǎn)的數(shù)據(jù)會很快被更新到其他新節(jié)點(diǎn)上。通常節(jié)點(diǎn)會利用流經(jīng)自己的節(jié)點(diǎn)查詢操作來持續(xù)更新對應(yīng)的K桶信息。為了避免沒有查詢操作經(jīng)過時而保存了錯誤信息，節(jié)點(diǎn)會對那些在過去一個小時之內(nèi)沒有收到任何節(jié)點(diǎn)查詢操作的K桶執(zhí)行刷新操作（BT協(xié)議實(shí)現(xiàn)規(guī)定為15分鐘）。所謂刷新操作就是說從該K桶中選擇一個隨機(jī)的節(jié)點(diǎn)信息，并對該節(jié)點(diǎn)ID執(zhí)行一次FIND_NODE操作。36節(jié)點(diǎn)有效性判斷

節(jié)點(diǎn)離開Kad網(wǎng)絡(luò)不需要發(fā)布任何信息，Ka36更新K-BUCKET當(dāng)節(jié)點(diǎn)x收到一個PRC消息時，發(fā)送者y的IP地址就被用來更新對應(yīng)的K桶，具體步驟如下：計算自己和發(fā)送者的距離：d(x,y)=x⊕y，x和y是ID值，不是IP地址通過距離d選擇對應(yīng)的K桶進(jìn)行更新操作。如果y的IP地址已經(jīng)存在于這個K桶中，則把對應(yīng)項(xiàng)移到該該K桶的尾部如果y的IP地址沒有記錄在該K桶中如果該K桶的記錄項(xiàng)小于k個，則直接把y的(IPaddress，UDPport，NodeID)信息插入隊(duì)列尾部如果該K桶的記錄項(xiàng)大于k個，則選擇頭部的記錄項(xiàng)（假如是節(jié)點(diǎn)z）進(jìn)行RPC_PING操作如果z沒有響應(yīng)，則從K桶中移除z的信息，并把y的信息插入隊(duì)列尾部如果z有響應(yīng)，則把z的信息移到隊(duì)列尾部，同時忽略y的信息。K桶的更新機(jī)制非常高效的實(shí)現(xiàn)了一種把最近看到的節(jié)點(diǎn)更新的策略，除非在線節(jié)點(diǎn)一直未從K桶中移出過。也就是說在線時間長的節(jié)點(diǎn)具有較高的可能性繼續(xù)保留在K桶列表中。一般來說，最活躍（或者說在線時間更長）的節(jié)點(diǎn)信息，有更大的機(jī)會留在其他節(jié)點(diǎn)的K桶中，這樣可以保持系統(tǒng)穩(wěn)定和減少節(jié)點(diǎn)進(jìn)出的路由維護(hù)代價。對于一個穩(wěn)定的網(wǎng)絡(luò)而言，因?yàn)楦鞴?jié)點(diǎn)一直在線，先加入K桶的節(jié)點(diǎn)不會失效，這樣，離自己時延小的節(jié)點(diǎn)，就更有機(jī)會留在K桶中，而且各節(jié)點(diǎn)的K桶信息是很穩(wěn)定的。37更新K-BUCKET當(dāng)節(jié)點(diǎn)x收到一個PRC消息時，發(fā)送者37存儲

發(fā)布節(jié)點(diǎn)自身要求其他相關(guān)節(jié)點(diǎn)存儲發(fā)布文件信息，其他相關(guān)節(jié)點(diǎn)存儲存放<key,value>對數(shù)據(jù)的過程為：發(fā)起者首先定位k個ID值最接近key的節(jié)點(diǎn)；發(fā)起者對這k個節(jié)點(diǎn)發(fā)起STORE操作執(zhí)行STORE操作的k個節(jié)點(diǎn)每小時重發(fā)布自己所有的<key,value>對數(shù)據(jù)。為了限制失效信息，所有<key,value>對數(shù)據(jù)在初始發(fā)布24小時后過期。另外，為了保證數(shù)據(jù)發(fā)布、搜尋的一致性，規(guī)定在任何時候，當(dāng)節(jié)點(diǎn)w發(fā)現(xiàn)新節(jié)點(diǎn)u比w上的某些<key,value>對數(shù)據(jù)更接近，則w把這些<key,value>對數(shù)據(jù)復(fù)制到u上，但是并不會從w上刪除。38存儲

發(fā)布節(jié)點(diǎn)自身要求其他相關(guān)節(jié)點(diǎn)存儲3838EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)2007年6月19日39EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)2007年6月19日39目錄Kademlia簡介及應(yīng)用現(xiàn)狀節(jié)點(diǎn)本地行為節(jié)點(diǎn)初始化讀取配置文件生成ID構(gòu)造本地二叉樹二叉樹生成規(guī)則生成k-bucket節(jié)點(diǎn)之間的交互行為節(jié)點(diǎn)間距離加入網(wǎng)絡(luò)發(fā)送加入網(wǎng)絡(luò)請求處理請求響應(yīng)查找查找其他節(jié)點(diǎn)查找文件（key）對查找二叉樹的使用路由信息的更新現(xiàn)在已知節(jié)點(diǎn)是否仍然有效更新二叉樹更新k-bucket存儲發(fā)布節(jié)點(diǎn)自身要求其他相關(guān)節(jié)點(diǎn)存儲發(fā)布文件信息，其他相關(guān)節(jié)點(diǎn)存儲40目錄Kademlia簡介及應(yīng)用現(xiàn)狀240KADEMLIA簡介Kademlia協(xié)議是美國紐約大學(xué)的PetarP.Maymounkov和DavidMazieres在2002年發(fā)布的一項(xiàng)研究結(jié)果《Kademlia:Apeer-to-peerinformationsystembasedontheXORmetric》。Kademlia是一種分布式哈希表（DHT）技術(shù)，Kademlia通過獨(dú)特的以異或算法（XOR）為距離度量基礎(chǔ)，建立了一種全新的DHT拓?fù)浣Y(jié)構(gòu)，相比于其他算法，大大提高了路由查詢速度。41KADEMLIA簡介Kademlia協(xié)議是美國紐約大學(xué)的P41當(dāng)前應(yīng)用現(xiàn)狀在2005年5月著名的BitTorrent在4.1.0版實(shí)現(xiàn)基于Kademlia協(xié)議的DHT技術(shù)后，很快國內(nèi)的BitComet和BitSpirit也實(shí)現(xiàn)了和BitTorrent兼容的DHT技術(shù)，實(shí)現(xiàn)trackerless下載方式。另外，emule中也很早就實(shí)現(xiàn)了基于Kademlia類似的技術(shù)（BT中叫DHT，emule中也叫Kad，），和BT軟件使用的Kad技術(shù)的區(qū)別在于key、value和nodeID的計算方法不同。42當(dāng)前應(yīng)用現(xiàn)狀在2005年5月著名的BitTorrent42EMULE中KADEMLIA網(wǎng)絡(luò)部分CKademlia是整個Kademlia網(wǎng)絡(luò)的主控類，可以直接開始或者停止Kademlia網(wǎng)，并且含有Process方法來處理日常事務(wù)。CPrefs負(fù)責(zé)處理自身的Kademlia相關(guān)信息，如自身的ID等。CRoutingZone，CRoutingBin和CContact三個類組成了每個節(jié)點(diǎn)所了解的聯(lián)系信息以及由這些聯(lián)系信息所組成的數(shù)據(jù)結(jié)構(gòu)。CKademliaUDPListener負(fù)責(zé)處理網(wǎng)絡(luò)信息。CIndexed負(fù)責(zé)處理本地存儲的索引信息。CSearch，CSearchManager負(fù)責(zé)處理和搜索有關(guān)的操作，其中前者表示的是一個單一的搜索任務(wù)，后者負(fù)責(zé)對所有搜索任務(wù)進(jìn)行處理。CUInt128負(fù)責(zé)處理一個128位的長整數(shù)，并且內(nèi)置其各種運(yùn)算。43EMULE中KADEMLIA網(wǎng)絡(luò)部分CKademlia是整個43節(jié)點(diǎn)本地行為44節(jié)點(diǎn)本地行為644節(jié)點(diǎn)初始化讀取本地配置文件在emule中，配置文件比較多，用于Kademlia網(wǎng)絡(luò)的配置文件是：

src_index.datkey_index.datload_index.dat（索引Indexed.cpp）nodes.dat（上次程序啟動時連接上的節(jié)點(diǎn)RoutingZone.cpp）preferencesKad.dat(上次程序啟動時本地節(jié)點(diǎn)的IP、ID、Port信息Prefs.cpp)生成IDKad網(wǎng)絡(luò)中每個節(jié)點(diǎn)都有一個160bit的ID值作為標(biāo)志符。節(jié)點(diǎn)ID的生成，可以是根據(jù)特定信息Hash或者簡單的隨機(jī)生成（emule中ID為隨機(jī)生成）。在emule中,CUInt128類中定義了ID的生成方式,結(jié)點(diǎn)之間ID做的異或運(yùn)算也在CUInt128里;emule中定義了4個ULong的數(shù)組,總共正好是128位；在Prefs.cpp中Init函數(shù)中對m_uClientID進(jìn)行了隨機(jī)值的設(shè)置:m_uClientID.SetValueRandom();函數(shù)中調(diào)用cryptlib中的函數(shù)生成16位的數(shù)據(jù)塊,然后填充,填充8次,共128位;45節(jié)點(diǎn)初始化讀取本地配置文件745構(gòu)造本地結(jié)點(diǎn)二叉樹在Kad網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都被當(dāng)作一顆二叉樹的葉子，并且節(jié)點(diǎn)的位置都由其ID值的最短前綴唯一的確定。每一個節(jié)點(diǎn)都在本地維護(hù)一個二叉樹,來標(biāo)示網(wǎng)絡(luò)中節(jié)點(diǎn)與自己的距離遠(yuǎn)近,自己則是二叉樹的根節(jié)點(diǎn)；本地結(jié)點(diǎn)二叉樹生成規(guī)則：最高層的子樹，由整顆樹不包含自己的樹的另一半組成；下一層子樹由剩下部分不包含自己的一半組成；依此類推，直到分割完整顆樹。46構(gòu)造本地結(jié)點(diǎn)二叉樹在Kad網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都被當(dāng)作一顆二叉46EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件47EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件48每一個節(jié)點(diǎn)都在本地維護(hù)一個二叉樹,來標(biāo)示網(wǎng)絡(luò)中節(jié)點(diǎn)與自己的距離遠(yuǎn)近,自己則是二叉樹的根節(jié)點(diǎn)；否則測量自己和t的距離，并從自己對應(yīng)的K桶中選擇α個節(jié)點(diǎn)的信息給x。在emule中，配置文件比較多，用于Kademlia網(wǎng)絡(luò)的配置文件是：計算到t的距離：d(x,y)=x⊕y也就是說,每個結(jié)點(diǎn)都對自己附近的情況非常了解,而隨著距離的增大,了解的程度不斷降低降低。dat（上次程序啟動時連接上的節(jié)點(diǎn)RoutingZone.由于每次查詢都能從更接近目標(biāo)節(jié)點(diǎn)的K桶中獲取信息，這樣的機(jī)制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少1bit）的效果，從而保證整個查詢過程的收斂速度為O(logN)，這里N為網(wǎng)絡(luò)全部節(jié)點(diǎn)的數(shù)量。否則測量自己和t的距離，并從自己對應(yīng)的K桶中選擇α個節(jié)點(diǎn)的信息給x。在2005年5月著名的BitTorrent在4.需要說明的是，只有第一步查詢的節(jié)點(diǎn)101，是節(jié)點(diǎn)0011已經(jīng)知道的，后面各步查詢的節(jié)點(diǎn)，都是由上一步查詢返回的更接近目標(biāo)的節(jié)點(diǎn)，這是一個遞歸操作的過程。在Kad網(wǎng)絡(luò)中，所有節(jié)點(diǎn)都被當(dāng)作一顆二叉樹的葉子，并且節(jié)點(diǎn)的位置都由其ID值的最短前綴唯一的確定。另外，emule中也很早就實(shí)現(xiàn)了基于Kademlia類似的技術(shù)（BT中叫DHT，emule中也叫Kad，），和BT軟件使用的Kad技術(shù)的區(qū)別在于key、value和nodeID的計算方法不同。uint32CRoutingZone::GetClosestTo沒有迅速響應(yīng)的節(jié)點(diǎn)將被迅速排除出候選列表，直到其響應(yīng)。的新K桶，并對原K桶內(nèi)的節(jié)點(diǎn)信息按照新的K桶前綴值進(jìn)行重新分配Kademlia協(xié)議包括四種遠(yuǎn)程RPC操作：PING、STORE、FIND_NODE、FIND_VALUE。生成K-BUCKETK-bucket構(gòu)造了Kademlia網(wǎng)絡(luò)的路由表每個節(jié)點(diǎn)都保存和自己一定距離范圍內(nèi)的節(jié)點(diǎn)信息，k-bucket存儲這些信息——

(IPaddress,UDPport,NodeID)數(shù)據(jù)列表。K桶內(nèi)部信息存放位置是根據(jù)上次看到的時間順序排列，最近（least-recently）看到的放在頭部，最后（most-recently）看到的放在尾部。每個桶都有最大不超過k個的數(shù)據(jù)項(xiàng)，這里k是為平衡系統(tǒng)性能和網(wǎng)絡(luò)負(fù)載而設(shè)置的一個常數(shù)，但必須是偶數(shù)；在emule中k=10。49每一個節(jié)點(diǎn)都在本地維護(hù)一個二叉樹,來標(biāo)示網(wǎng)絡(luò)中節(jié)點(diǎn)與自己的距49由于每個K桶覆蓋距離的范圍呈指數(shù)關(guān)系增長，這就形成了離自己近的節(jié)點(diǎn)的信息多，離自己遠(yuǎn)的節(jié)點(diǎn)的信息少，從而可以保證路由查詢過程是收斂。也就是說,每個結(jié)點(diǎn)都對自己附近的情況非常了解,而隨著距離的增大,了解的程度不斷降低降低。經(jīng)過證明，對于一個有N個節(jié)點(diǎn)的Kad網(wǎng)絡(luò)，最多只需要經(jīng)過logN步查詢，就可以準(zhǔn)確定位到目標(biāo)節(jié)點(diǎn)。50由于每個K桶覆蓋距離的范圍呈指數(shù)關(guān)系增長，這就形成了離自己近50EMULE中生成K-BUCKET具體實(shí)現(xiàn)在RoutingBin.h中定義了一個list： ContactListm_listEntries;即為k-bucketCRoutingZone實(shí)際上是一個二叉樹，當(dāng)當(dāng)前的CRoutingZone類為整個二叉樹的葉節(jié)點(diǎn)時，這個指向CRoutingBin類型的指針才有意義。（此時CRoutingZone作為網(wǎng)絡(luò)中的節(jié)點(diǎn)應(yīng)該包含一個k-bucket），由于CRoutingBin中定義了一個ContactList，這個ContactList即為k-bucket。51EMULE中生成K-BUCKET具體實(shí)現(xiàn)在RoutingBi51節(jié)點(diǎn)間交互行為52節(jié)點(diǎn)間交互行為1452KADEMLIA協(xié)議的操作與EMULE中對應(yīng)關(guān)系Kademlia協(xié)議包括四種遠(yuǎn)程RPC操作：PING、STORE、FIND_NODE、FIND_VALUE。PING操作的作用是探測一個節(jié)點(diǎn)，用以判斷其是否仍然在線。對應(yīng)于emule中PING-PONG操作，即發(fā)送KADEMLIA_HELLO_REQ和KADEMLIA_HELLO_RES請求STORE操作的作用是通知一個節(jié)點(diǎn)存儲一個<key,value>對。對應(yīng)emule中publish操作以及Store操作FIND_NODE操作使用一個160bit的ID作為參數(shù)。本操作的接受者返回它所知道的更接近目標(biāo)ID的K個節(jié)點(diǎn)的(IPaddress,UDPport,NodeID)信息。對應(yīng)emule中查找節(jié)點(diǎn)的操作FIND_VALUE操作和FIND_NODE操作類似，不同的是它只需要返回一個節(jié)點(diǎn)的(IPaddress,UDPport,NodeID)信息。如果本操作的接受者收到同一個key的STORE操作，則會直接返回存儲的value值。對應(yīng)emule中文件檢索的操作53KADEMLIA協(xié)議的操作與EMULE中對應(yīng)關(guān)系Kademl53節(jié)點(diǎn)間距離判斷兩個節(jié)點(diǎn)x,y的距離遠(yuǎn)近是基于數(shù)學(xué)上的異或的二進(jìn)制運(yùn)算，d(x,y)=x⊕y，既對應(yīng)位相同時結(jié)果為0，不同時結(jié)果為1。異或操作具有如下性質(zhì)：非負(fù)性對稱性三角不等式單向性傳遞性異或運(yùn)算提供了一種在Kad網(wǎng)絡(luò)上進(jìn)行可靠距離度量的方法。假如Kad網(wǎng)絡(luò)上所有其他用戶都按照和你之間距離的遠(yuǎn)近而排成一條長隊(duì)，如果已知另一個結(jié)點(diǎn)的ID，那么你很容易計算出他在這條長隊(duì)中的位置；如果給定一個距離，你也能很容易從這條長隊(duì)里找出與你的距離最接近給定距離的那些結(jié)點(diǎn)。54節(jié)點(diǎn)間距離判斷兩個節(jié)點(diǎn)x,y的距離遠(yuǎn)近是基于數(shù)學(xué)上的異54EMULE中節(jié)點(diǎn)距離計算的具體實(shí)現(xiàn)CUInt128類根據(jù)128位ID值進(jìn)行異或運(yùn)算，得到節(jié)點(diǎn)之間距離CRoutingZoneuint32CRoutingZone::GetClosestToCRoutingBin節(jié)點(diǎn)之間距離具體運(yùn)算是在查找和發(fā)布時進(jìn)行的，此時CRoutingBin中的k-bucket需要計算節(jié)點(diǎn)之間的距離來確定查找的遞進(jìn)性以及應(yīng)該發(fā)布到哪些節(jié)點(diǎn)uint32CRoutingBin::GetClosestTo55EMULE中節(jié)點(diǎn)距離計算的具體實(shí)現(xiàn)CUInt128類1755節(jié)點(diǎn)加入網(wǎng)絡(luò)如果節(jié)點(diǎn)u要想加入Kad網(wǎng)絡(luò)，它必須要和一個已經(jīng)在Kad網(wǎng)絡(luò)的節(jié)點(diǎn)，比如w，取得聯(lián)系。u首先把w插入自己適當(dāng)?shù)腒桶中，然后對自己的節(jié)點(diǎn)ID執(zhí)行一次FIND_NODE操作，然后根據(jù)接收到的信息更新自己的K桶內(nèi)容。通過對自己鄰近節(jié)點(diǎn)由近及遠(yuǎn)的逐步查詢，u完成了仍然是空的K桶信息的構(gòu)建，同時也把自己的信息發(fā)布到其他節(jié)點(diǎn)的K桶中。在Kad網(wǎng)絡(luò)中，每個節(jié)點(diǎn)的路由表都表示為一顆二叉樹，葉子節(jié)點(diǎn)為K桶，K桶存放的是有相同ID前綴的節(jié)點(diǎn)信息，而這個前綴就是該K桶在二叉樹中的位置。這樣，每個K桶都覆蓋了ID空間的一部分，全部K桶的信息加起來就覆蓋了整個160bit的ID空間，而且沒有重疊。以節(jié)點(diǎn)u為例，其路由表的生成過程為：1．最初，u的路由表為一個單個的K桶，覆蓋了整個160bitID空間;2．當(dāng)學(xué)習(xí)到新的節(jié)點(diǎn)信息后，則u會嘗試把新節(jié)點(diǎn)的信息，根據(jù)其前綴值插入到對應(yīng)的K桶中：①如果該K桶沒有滿，則新節(jié)點(diǎn)直接插入到這個K桶中；②如果該K桶已經(jīng)滿了，⑴如果該K桶覆蓋范圍包含了節(jié)點(diǎn)u的ID，則把該K桶分裂為兩個大小相同的新K桶，并對原K桶內(nèi)的節(jié)點(diǎn)信息按照新的K桶前綴值進(jìn)行重新分配⑵如果該K桶覆蓋范圍沒有包節(jié)點(diǎn)u的ID，則直接丟棄該新節(jié)點(diǎn)信息3．上述過程不斷重復(fù)，最終會形成表1結(jié)構(gòu)的路由表。達(dá)到距離近的節(jié)點(diǎn)的信息多，距離遠(yuǎn)的節(jié)點(diǎn)的信息少的結(jié)果，保證了路由查詢過程能快速收斂。56節(jié)點(diǎn)加入網(wǎng)絡(luò)如果節(jié)點(diǎn)u要想加入Kad網(wǎng)絡(luò)，它必須要和一個已56節(jié)點(diǎn)000的路由表生成演化57節(jié)點(diǎn)000的路由表生成演化1957節(jié)點(diǎn)0100的K-BUCKET分裂過程58節(jié)點(diǎn)0100的K-BUCKET分裂過程2058當(dāng)K桶010滿了之后，由于其覆蓋范圍包含了節(jié)點(diǎn)0100的ID，故該K桶分裂為兩個新的K桶：0101和0100，原K桶010的信息會根據(jù)其其前綴值重新分布到這兩個新的K桶中。注意，這里并沒有使用160bit的ID值表示法，只是為了方便原理的演示，實(shí)際Kad網(wǎng)絡(luò)中的ID值都是160bit的。59當(dāng)K桶010滿了之后，由于其覆蓋范圍包含了節(jié)點(diǎn)010059節(jié)點(diǎn)加入網(wǎng)絡(luò)發(fā)送加入請求處理請求響應(yīng)采用ping-pong機(jī)制機(jī)制CKademliaUDPListener類中函數(shù)ProcessPacket處理所有類型的消息60節(jié)點(diǎn)加入網(wǎng)絡(luò)發(fā)送加入請求2260EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件61EMULE中KADEMLIA協(xié)議具體實(shí)現(xiàn)完整版資料課件62節(jié)點(diǎn)查找以及文件查找查找其他節(jié)點(diǎn)查找文件（key）對查找二叉樹的使用63節(jié)點(diǎn)查找以及文件查找查找其他節(jié)點(diǎn)2563查找其他節(jié)點(diǎn)在Kademlia網(wǎng)絡(luò)中，節(jié)點(diǎn)搜索的實(shí)現(xiàn)方式是迭代式的搜索。這種方式就是說當(dāng)開始搜索某個ID時，在本地聯(lián)系人信息列表中查找到距離最近的聯(lián)系人，然后向它們發(fā)出搜索請求，這樣通常都能夠得到一些距離更近的聯(lián)系人信息，然后再向它們發(fā)送搜索請求，通過不斷得進(jìn)行這樣的搜索查詢，就能夠得到距離目標(biāo)ID最近的那些聯(lián)系人信息。這里對應(yīng)的消息代碼是KADEMLIA_REQ和KADEMLIA_RES。由于每次查詢都能從更接近目標(biāo)節(jié)點(diǎn)的K桶中獲取信息，這樣的機(jī)制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少1bit）的效果，從而保證整個查詢過程的收斂速度為O(logN)，這里N為網(wǎng)絡(luò)全部節(jié)點(diǎn)的數(shù)量。64查找其他節(jié)點(diǎn)在Kademlia網(wǎng)絡(luò)中，節(jié)點(diǎn)搜索的實(shí)現(xiàn)方式是迭64假如節(jié)點(diǎn)x要查找ID值為t的節(jié)點(diǎn)，Kad按照如下遞歸操作步驟進(jìn)行路由查找：計算到t的距離：d(x,y)=x⊕y從x的第[㏒d]個K桶中取出α個節(jié)點(diǎn)的信息（“[]”是取整符號），同時進(jìn)行FIND_NODE操作。如果這個K桶中的信息少于α個，則從附近多個桶中選擇距離最接近d的總共α個節(jié)點(diǎn)。對接受到查詢操作的每個節(jié)點(diǎn)，如果發(fā)現(xiàn)自己就是t，則回答自己是最接近t的；否則測量自己和t的距離，并從自己對應(yīng)的K桶中選擇α個節(jié)點(diǎn)的信息給x。x對新接收到的每個節(jié)點(diǎn)都再次執(zhí)行FIND_NODE操作，此過程不斷重復(fù)執(zhí)行，直到每一個分支都有節(jié)點(diǎn)響應(yīng)自己是最接近t的。沒有迅速響應(yīng)的節(jié)點(diǎn)將被迅速排除出候選列表，直到其響應(yīng)。通過上述查找操作，x得到了k個最接近t的節(jié)點(diǎn)信息。65查找步驟假如節(jié)點(diǎn)x要查找ID值為t的節(jié)點(diǎn)，Kad按照如下遞歸操65ALPHA=1時查詢流程66ALPHA=1時查詢流程2866查找文件當(dāng)用戶使用Kademlia網(wǎng)絡(luò)來進(jìn)行搜索并且下載文件的時候，首先是對一個關(guān)鍵詞進(jìn)行搜索，由于使用的是同樣的hash算法，這樣它只要找到ID值和計算出來的hash值結(jié)果相近的聯(lián)系人信息后，它就可以直接向它們發(fā)送搜索特定關(guān)鍵詞的請求了。如果得到了返回信息，那么搜索者就知道了這個關(guān)鍵詞對應(yīng)了多少文件，然后把這些文件的信息都列出來。當(dāng)用戶決定下載某個文件的時候，針對這一特定文件的搜索過程就開始了，這一次如果搜索成功，那么返回的就是這個文件的文件源信息。這樣emule接下來就只需要按照這些信息去連接相應(yīng)的地址，并且使用傳統(tǒng)的emule協(xié)議去和它們協(xié)商下載文件了。這里對應(yīng)的消息是KADEMLIA_SEARCH_REQ和KADEMLIA_SEARCH_RES。67查找文件當(dāng)用戶使用Kademlia網(wǎng)絡(luò)來進(jìn)行搜索并且下載文件67當(dāng)節(jié)點(diǎn)x要查詢<key,value>對時，和查找節(jié)點(diǎn)的操作類似，x選擇k個ID值最接近key值的節(jié)點(diǎn)，執(zhí)行FIND_VALUE操作，并對每一個返回的新節(jié)點(diǎn)重復(fù)執(zhí)行FIND_VALUE操作，直到某個節(jié)點(diǎn)返回value值。一旦FIND_VALUE操作成功執(zhí)行，則<key,value>對數(shù)據(jù)會緩存在沒有返回value值的最接近的節(jié)點(diǎn)上。這樣下一次查詢相同的key時就會更加快速的得到結(jié)果。通過這樣的方式，熱門<key,value>對數(shù)據(jù)的緩存范圍就逐步擴(kuò)大，使系統(tǒng)具有極佳的響應(yīng)速度68當(dāng)節(jié)點(diǎn)x要查詢<key,value>對時，和查找節(jié)點(diǎn)的操作68693169二叉樹中節(jié)點(diǎn)的查找Kad協(xié)議確保每個節(jié)點(diǎn)知道其各子樹的至少一個節(jié)點(diǎn)，只要這些子樹非空。在這個前提下，每個節(jié)點(diǎn)都可以通過ID值來找到任何一個節(jié)點(diǎn)。這個路由的過程是通過所謂的XOR（異或）距離得到的。節(jié)點(diǎn)通過在逐步底層的子樹間不斷學(xué)習(xí)并查詢最佳節(jié)點(diǎn)，獲得了越來越接近的節(jié)點(diǎn)，最終收斂到目標(biāo)節(jié)點(diǎn)上。70二叉樹中節(jié)點(diǎn)的查找Kad協(xié)議確保每個節(jié)點(diǎn)知道其各子樹的至少70713371需要說明的是，只有第一步查詢的節(jié)點(diǎn)101，是節(jié)點(diǎn)0011已經(jīng)知道的，后面各步查詢的節(jié)點(diǎn)，都是由上一步查詢返回的更接近目標(biāo)的節(jié)點(diǎn)，這是一個遞歸操作的過程。由于各節(jié)點(diǎn)路由信息的不確定性（節(jié)點(diǎn)動態(tài)加入和離開引起），圖2只是展示了多種可能搜索路徑的一個具體實(shí)現(xiàn)。怎么知道的呢？協(xié)議里規(guī)定的嗎72需要說明的是，只有第一步查詢的節(jié)點(diǎn)101，是節(jié)點(diǎn)0011已72從x的第[㏒d]個K桶中取出α個節(jié)點(diǎn)的信息（“[]”是取整符號），同時進(jìn)行FIND_NODE操作。①