一、P2P及DHT網(wǎng)絡(luò)簡單介紹：

P2P在思想上可以說是internet思想/精神/哲學(xué)非常集中的體現(xiàn)，共同的參與，透明的開放，平等的分享（讓我想起之前學(xué)習(xí)過的，現(xiàn)在正在瘋狂熱炒的云計算的“中央集權(quán)”制度）?；?/span>P2P技術(shù)的應(yīng)用有很多，包括文件分享，即時通信，協(xié)同處理，流媒體通信等等。通過這些應(yīng)用的接觸，分析和理解，P2P其本質(zhì)是一種新的網(wǎng)絡(luò)傳播技術(shù)，這種新的傳播技術(shù)打破了傳統(tǒng)的C/S架構(gòu)，逐步地去中心化，扁平化，這或許在一定程度上應(yīng)證了”世界是平的”趨勢，呵呵。P2P文件分享的應(yīng)用(BTs/eMules等)是P2P技術(shù)最集中的體現(xiàn)，我們這里的研究也是以P2P文件分享網(wǎng)絡(luò)作為入口，P2P文件分享網(wǎng)絡(luò)的發(fā)展大致有以下幾個階段，包含tracker服務(wù)器的網(wǎng)絡(luò)，無任何服務(wù)器的純DHT網(wǎng)絡(luò)， 混合型P2P網(wǎng)絡(luò)。DHT網(wǎng)絡(luò)發(fā)展即有“思想/文化”上的“發(fā)展”，也有一定的商業(yè)上的需求（版權(quán)管理）。

DHT全稱叫分布式哈希表(Distributed Hash Table)，是一種分布式存儲方法，一類可由鍵值來唯一標示的信息按照某種約定/協(xié)議被分散地存儲在多個節(jié)點上，這樣也可以有效地避免“中央集權(quán)式”的服務(wù)器（比如：tracker）的單一故障而帶來的整個網(wǎng)絡(luò)癱瘓。實現(xiàn)DHT的技術(shù)/算法有很多種，常用的有：Chord, Pastry, Kademlia等。我們這里要研究的是Kademlia算法，因為BT及BT的衍生派（Mainline, Btspilits, Btcomet, uTorrent…），eMule及eMule各類Mods(verycd, easy emules, xtreme…)等P2P文件分享軟件都是基于該算法來實現(xiàn)DHT網(wǎng)絡(luò)的，BT采用Python的Kademlia實現(xiàn)叫作khashmir（科什米爾，印巴沖突地帶？），有如下官網(wǎng)。eMule采用C++的Kademlia實現(xiàn)干脆就叫作Kad，當(dāng)然它們之間有些差別，但基礎(chǔ)都是Kademlia。我們這里以BT-DHT為例進行分析介紹，下面說到的DHT都可以默認是BT-Kademlia-DHT。

官方網(wǎng)站：http://www./trac/wiki/Khashmir

二、Kademlia實現(xiàn)原理

各種DHT的實現(xiàn)算法，不論是Chord, Pastry還是Kademlia，其最直接的目標就是以最快的速度來定位到期望的節(jié)點，在P2P文件分享應(yīng)用中則是以最快的速度來查找到正在分享某一文件/種子的peers列表信息。因為每個節(jié)點都是分布式存在于地球的任何角落，如果用地理距離來衡量兩節(jié)點間的距離則可能給計算帶來極大復(fù)雜性甚至不可能進行衡量，因此基本所有的DHT算法都是采用某種邏輯上的距離，在Kademlia則采用簡單的異或計算來衡量兩節(jié)點間的距離，它和地理上的距離沒有任何關(guān)系，但卻具備幾何公式的絕大特征：

（1）節(jié)點和它本身之間的異或距離是0

（2）異或距離是對稱的：即從A到B的異或距離與從B到A的異或距離是等同的

（3）異或距離符合三角形不等式：給定三個頂點A B C，假如AC之間的異或距離最大,那么AC之間的異或距離必小于或等于AB異或距離和BC異或距離之和.

（4）對于給定的一個距離，距離A只存在有唯一的一個節(jié)點B，也即單向性，在查找路徑上也是單向的，這個和地理距離不同。

Kademlia中規(guī)定所有的節(jié)點都具有一個節(jié)點ID，該節(jié)點ID的產(chǎn)生方法和種子文件中的info hash采用相同算法:即sha-1（安全hash算法），因此每個節(jié)點的id，以及每個共享文件/種子的info-hash都是唯一的，并且都是20個字符160bits位組成。兩個節(jié)點間的距離就是兩個節(jié)點id的異或結(jié)果，節(jié)點離鍵值（種子）的距離為該節(jié)點的id和該種子文件的info-hash的異或結(jié)果。Kademlia在異或距離度量的基礎(chǔ)上又把整個DHT網(wǎng)絡(luò)拓撲組織成一個二叉前綴樹（XuanWu系統(tǒng)中arp的實現(xiàn)則是一個例子），所有的節(jié)點(所有的正在運行的，并且開取了DHT功能的Bt,Btspilits應(yīng)用)等作為該二叉前綴樹的葉子節(jié)點，可以想象這棵二叉樹可以容納多達2128個葉子（節(jié)點），這足以組織任何規(guī)模的網(wǎng)絡(luò)了。對于每個節(jié)點來說按照離自己的遠近區(qū)域又可以把這棵樹劃分為160棵子樹，每一個子樹和該節(jié)點都有一個共同的前綴，共同前綴越少離得越遠。如下圖所示：

（注意：上圖只是一個劃分子樹的例子，節(jié)點都沒有位于同一層的葉子上面）

以上圖紅色節(jié)點位例0011位例，它可以把其他的節(jié)點劃分位4棵不同子樹，離自己越近子樹和自己有越長的公共前綴，如果節(jié)點是均勻分布則離自己越近的子樹含有的葉子節(jié)點更少（兄弟只有一個即和自己有159個共同前綴的那個）。因為節(jié)點都位于該樹最底層的葉子位置，水平看上去則所有的葉子都在一條線上，如果把這條線當(dāng)作2128空間的每一個點，則更能體現(xiàn)上面的劃分特性（折半拆分）。為了能快速到達這160棵子樹，處于DHT網(wǎng)絡(luò)中的每一個節(jié)點都記錄了每棵子樹上的k個節(jié)點的信息（ip,port,id），在BT中K固定為8，比如上圖中紅色節(jié)點就可能保存有最左邊子樹的8個葉子節(jié)點信息，當(dāng)然靠近自己的子樹可能沒有8個葉子，則把所有當(dāng)前存在的葉子記錄上去，這份記錄信息在Kademlia算法中叫作K桶，也叫作“路由表”，當(dāng)然這個“路由表”的信息和我們IP路由的含義有點不同，它代表的是為了到達處于距離自己某范圍[ 2i — 2i+1 )的節(jié)點，可以通過該范圍內(nèi)的選取的k個節(jié)點來進一步定位，下圖是一個“路由表”結(jié)構(gòu)：

.注意：這里只是一個舉例，在實際的“路有表”中可能是沒有160份，因為路由表的生成過程是對半分拆的，最初只有一個K桶（范圍為:0—2160，且只包括自己），在插如過程中當(dāng)該K桶節(jié)點大于k(8)時，則分拆成兩半，一半包括自身節(jié)點，一半不包括自身。循環(huán)往復(fù)下去，則形成一個動態(tài)的大小（1<=len(table)<=160）的“路由表”

每一個新加入到DHT網(wǎng)絡(luò)的節(jié)點最開始這些“路由表”信息都是空的，它有以下幾個方式可以來逐步生成和形成自己的“路由表”信息：

1） 如果本節(jié)點曾經(jīng)啟動過程，則從保存的“路由表”文件中直接讀取然后刷新該“路由表“

2） 如果該節(jié)點第一次啟動（比如新安裝BTSpilits然后啟動），并且該節(jié)點自帶有“超級節(jié)點“則

通過這些“超級節(jié)點“來間接地生成自己的”路由表“（在Kashmir的某個版本中有一個文件保存這些”超級接點的信息“，BTSplits, BTcomet, eMules則內(nèi)嵌有20多個）

3）如果第一次啟動的節(jié)點沒有這些所謂的“超級節(jié)點”(比如Mainline則沒有這個功能)，則它的路由表生成過程需要推遲到download文件過程。它會從它獲取到的種子文件中提取nodes字段，該字段是做種子（支持DHT網(wǎng)絡(luò)的種子）的時候生成的，一般nodes字段設(shè)置為該原始種子的ip和port，或者是做種子的節(jié)點離該種子的info-hash最近的k個節(jié)點。通過這些nodes字段中的節(jié)點通過來間接地生成自己的路由表。

4）動態(tài)建立過程，該過程為節(jié)點經(jīng)過上面的初始化后，在下載或者上傳或者無任務(wù)過程中有收到任何節(jié)點發(fā)送的任何消息，都會去檢查當(dāng)前的“路由表”并嘗試按照一定的規(guī)則去建立/刷新路由表。

我們知道DHT網(wǎng)絡(luò)最主要的目標是替代Tracker（純P2P網(wǎng)絡(luò)，無traker）或者說作為Tracker的一個備份（混合型P2P網(wǎng)絡(luò)，當(dāng)前基本所有主流文件分享的應(yīng)用都是該類型）。而Tracker最主要功能就是對每一個分享文件（種子）維護一個peers列表，然后告訴需要下載的詢問者Client。實現(xiàn)的方法就是把Tracker集中維護的所有種子的peers-list信息利用DHT的方法散列并保存到所有的DHT網(wǎng)絡(luò)中的節(jié)點上去，然后在此基礎(chǔ)上提供查找的方法。“路有表”作用就是為了加速這個查找的過程的。在DHT實現(xiàn)中包括兩種類型的查找，一種是查找nodes(find_nodes)，另一種是查找peers（get_peers）。查找nodes的過程主要是為了建立本地的“路由表”，它的最終目的是后面查找peers。查找節(jié)點的過程大概是這樣，如果節(jié)點x需要查找節(jié)點y，則x首先從xor(x,y)對應(yīng)的本地K桶中得到k個比較closer的節(jié)點，然后向這些比較close的k個節(jié)點繼續(xù)詢問它是否有離y更近的節(jié)點，這些k個節(jié)點當(dāng)然也從自己的對應(yīng)的K桶中返回k個更近的節(jié)點給x，x然后再從返回結(jié)果中選取k個更more closer節(jié)點重復(fù)上面的動作，直到不能返回更近的節(jié)點為止，則最后找到的k個節(jié)點即為the most closest nodes，在這個過程中返回的任何k個close的節(jié)點都會嘗試去插到自己的路由表中去。而x查找peers-list的方法則和上面查找節(jié)點的方法類似，不同的是它是以info-hash作為參數(shù)進行查找，并且如果在查找過程中有任何一個節(jié)點返回了(info-hash, peers-list)對則提前結(jié)束查找。當(dāng)一個節(jié)點通過上面方法得到了peers-list后，則會試圖對每個peers主動發(fā)起TCP的連接繼續(xù)后面真實的下載過程（該過程由peer-peer protocol協(xié)議規(guī)定），同時會把自己的peer信息發(fā)送給先前的告訴者和自己K桶中的k個最近的節(jié)點存儲該peer-list信息。該信息在該k個節(jié)點上可以保存24個小時，24小時后如果沒有收到x發(fā)送的更新消息則失效。因此一個活動的節(jié)點存儲有兩部份的信息，一部分是本地的“路由表”，另一部分則是(info-hash, peers-list)列表信息（可有多個）。Info-hash的值當(dāng)然也屬于(0-2160)空間的一部分，但是它和節(jié)點id不同，節(jié)點ID是可以作為那棵無形的二叉前綴樹的葉子（為什么是無形的，因為每個節(jié)點其實是沒有用數(shù)據(jù)結(jié)構(gòu)來存儲這個棵的樹的），而info-hash則只能附著在離它的值最近的node id上面。

三、kademlia的消息：

為了實現(xiàn)上面的“路由表”建立，刷新，獲取peers-list,保存peers-list這些功能，kademlia定義四個最基本的KRPC操作:

（１）ping操作，作用是探測一個節(jié)點，用以判斷該節(jié)點是否仍然在線。

（２）store操作，作用是通知一個節(jié)點存儲一個<key,value>對，以便以后查詢需要。

（３）find_node操作，作用是從自己的“路由表”對應(yīng)的K桶中返回k個節(jié)點信息(IP address,UDP port,Node ID)給發(fā)送者

（４）faind_value 操作，作用是把info-hash作為參數(shù)，如果本操作接收者正好存儲了info-hash的peers則返回peers list，否則從自己的“路由表“中返回離info-hash更近的k個節(jié)點信息（同find_node過程）。

上面只是最基本的操作，一次nodes或者info-hash的查找lookup過程則需要節(jié)點進行若干次上面的find操作的，一個遞歸查找的過程。利用上面的操作更精確的描述一次一個節(jié)點x要查找ID值為t 的節(jié)點， 過程如下：

1、 計算到t 的距離：d(x,y) = x⊕y

2、 從x 的第[㏒ d]個K 桶中取出α 個節(jié)點的信息（各個實現(xiàn)α值不一樣，有些是3有些則等于k值），同時進行FIND_NODE 操作。如果這個K 桶中的信息少于α 個，則從附近多個桶中選擇距離最

接近d 的總共α個節(jié)點。

3、 對接受到查詢操作的每個節(jié)點，如果發(fā)現(xiàn)自己就是t，則回答自己是最接近t 的。否則測量自己和t 的距離，并從自己對應(yīng)的K 桶中選擇α 個節(jié)點的信息給x。

4、 X 對新接受到的每個節(jié)點都再次執(zhí)行FIND_NODE 操作，此過程不斷重復(fù)執(zhí)行，直到

每一個分支都有節(jié)點響應(yīng)自己是最接近t 的，或者說FIND_NODE操作返回的節(jié)點值沒有都已經(jīng)被查找過了，即找不到更近的節(jié)點了。

5、 通過上述查找操作，x 得到了k 個最接近t 的節(jié)點信息。

注意：這里用“最接近”這個說法，是因為ID 值為t 的節(jié)點不一定存在網(wǎng)絡(luò)中，也就是說t 沒有分配給任何一臺電腦。

查找peers-list的過程則換成find_value動作，但注意前文提到的區(qū)別即可以有類似的描述。

上面的四個原始在BT-DHT的實現(xiàn)上則進行了重命名，定義了如下四類信息，它們叫作KRPC（K代表Khashmila/Kademlia），通過udp進行發(fā)送，一個請求一個響應(yīng)或者錯誤。

（1） Ping（和Kademlia同名同功能）

Beconded（以BitSprits為例）:

Ping Request格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxxxxe1:q4:ping1:t4:tttt1:y1:qe

表示的含義：此操作為ping操作請求，參數(shù)為發(fā)送者的id是：xxxxxxxxxxxxxxxxxx

Ping Reponse格式:

d1:rd2:id20:yyyyyyyyyyyyyyyyyy e1:t4:1:y1:re

返回的數(shù)據(jù)中只包括有一個響應(yīng)者的id信息。

（2） find_node（和Kademlia同名同功能）

Beconded（以BitSprits為例）:

find_node Request格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxxxxx6:target20:yyyyyyyyyyyyyyyyyyyy1:q9:find_node1:t4:1:y1:qe

表示的含義：此操作為find_node請求，參數(shù)為發(fā)送者id及目標節(jié)點的id

find_node Reponse格式：

d1:rd2:id20:xxxxxxxxxxxxxxxxxxxx5:nodes208:nnnnnnnnnnnnn5:token20:ooooooooooooo1:t4:ttt 1:y1:re

表示的含義是：找到了8個最近的節(jié)點，nodes208表示8個node信息（ip,port,id）共208Bytes

（3） get_peers（對應(yīng)Kademlia中的find_value消息）

Beconded（以BitSprits為例）:

Get_peers請求格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxxxxx9:info_hash20:zzzzzzzzzzzzzzzzzzzze1:q9:get_peers1:t4:tttt1:y1:qe

表示的含義：此操作為get_peers操作請求，參數(shù)為：發(fā)送者的id和要查詢種子的info-hash。

Get_peers響應(yīng)格式有兩種，一種是找到了節(jié)點含有該info-hash的peers列表信息，如下格式：

表示的含義：

d1:rd2:id20:xxxxxxxxxxxxxxxxxxx5:token20:ooooooooooooooooooo6:valuesl6:(ip1,port1)+(ip2,port2)+(ipi,porti)…e1:t4:tttt1:y1:re

(values后面跟上的則是peers列表，ip, port)

另一種是沒有找到列表信息，如下格式：

d1:rd2:id20:xxxxxxxxxxxxxxxx5:nodes208:nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 5:token20:ooooooooooooooo1:t4:tttt1:y1:re

表示的含義為：

沒有找到存有info-hash的節(jié)點，但找到了離該info-hash更近的8個節(jié)點，nodes208表示8個node信息（ip,port,id）共208bytes

（4） announce_peer（對應(yīng)Kademlia中的store消息）

Beconded（以BitSprits為例）:

announce _peers請求格式：

d1:ad2:id20:xxxxxxxxxxxxxxxxx9:info_hash20:zzzzzzzzzzzzzzzzzz4:porti10756e5:token20:ooooooooooooooooo1:q13:announce_peer1:t4:tttt1:y1:qe

表示的含義是：此操作為announce_peer請求操作，告訴對端我這邊對info-hash文件上傳和下載，可以成為peers list中的一員，端口號是10756.

Announce_peer Reponse格式

d1:rd2:id20:xxxxxxxxxxxxxxxxxxxx2:ip4:pppp1:t4:tttt1:v4:UTb*1:y1:re

附件為抓取的分別為為一簡單下載過程/一初始初始化路由表的數(shù)據(jù)包：可以對照進行分析

四、Bttorent DHT實現(xiàn)幾個重要過程

種子制作：

1）./maketorrent-console參數(shù)use_tracker設(shè)置為false，則不會產(chǎn)生announce tracker字段

2） 讀取本地“路由表”文件，并從中找出k個離info-hash最近的節(jié)點，作為nodes字段

啟動過程：

1） 從routing_table文件中裝載之前保存的”路由表”K桶信息，初始化內(nèi)存“路由表”信息

2） 強制刷新“路由表“中的每一個K桶，刷新過程是隨機產(chǎn)生一id進行findNode查找。

刷新路由表的過程：

1） 啟動的時候進行強制刷新

2） 每15分鐘如果K桶中的信息沒有進行更新的話，則進行刷新一次K桶，即refreshTable

3） 每5分鐘進行一次checkpoint操作，以把當(dāng)前的路由表存放到routing_table文件中

routing_table文件的格式：

{'id':node.id, 'host':node.host, 'port':node.port, 'age':int(node.age)}

有些實現(xiàn)是用SQLite數(shù)據(jù)庫來實現(xiàn)這部分功能的。

每一個“路由表”的K桶都有一個“最近更新時間“屬性，當(dāng)收到該桶中任何節(jié)點的ping響應(yīng)，或者有任何節(jié)點被加入或者被替換，則該屬性都需保持更新，并且重啟一個15分鐘的定時器，如果定時器超時（15分鐘內(nèi)該K桶節(jié)點沒有任何更新操作），則會對該K桶進行一次refresh操作，操作的過程是從該K桶范圍選出一隨機的ID，然后對該ID進行find_node操作。“路由表”中的節(jié)點需要保持live狀態(tài)，即得保證沒有離線，如果向路由表中的一節(jié)點發(fā)出的連續(xù)3次請求都沒有收到響應(yīng)，則認為該節(jié)點失效。

refreshTable（force=1）過程：

（1） 如果force=1，則對當(dāng)前每個K桶都進行刷新

（2） 如果K桶當(dāng)前nodes數(shù)小于k（8），則也進行刷新

（3） 如果K桶中存在無效的節(jié)點，即連續(xù)三個消息沒有收到響應(yīng)的節(jié)點

（4） 如果K桶中所有節(jié)點沒有交互的時間超過15分鐘，則也進行刷新

當(dāng)一個節(jié)點收到任何一個RPC消息（請求和響應(yīng)）后（ping/find/getPeers/announce_peer）都會去檢查一下該消息的發(fā)送者是否在本地的“路由表“中，如果該發(fā)送者已經(jīng)存在節(jié)點的本地“路由表”中，則會把該發(fā)送者從其對應(yīng)的K桶移動到該K桶的末尾。如果該發(fā)送者不在節(jié)點的“路由表”中則會去嘗試插入到本地”路由表“K桶中，這也是“路由表”的動態(tài)建立過程的一種，過程如下：

（0）  找到該發(fā)送者的對應(yīng)的K桶

（1） 如果該節(jié)點是響應(yīng)消息中發(fā)現(xiàn)的，則更新該節(jié)點lastSeen = time()時間

（2） 如果該K桶大小小于k（8）則直接插到該K桶后面

（3） 如果該K桶已經(jīng)滿了，則檢查是否有無效的節(jié)點，如果有則把這些無效節(jié)點刪除，并把該節(jié)點放入K桶末尾。（但后面會對這些早已經(jīng)存在的節(jié)點進行再一次的ping操作，來進一步確定是否無效了，如果收到響應(yīng)，則把這些節(jié)點重新放如K桶）

（4） 如果該K桶已經(jīng)滿了，并且所有的節(jié)點都是有效的，則需要查看自身（本客戶短）是否在該K桶中（即該K桶是否是自己所在的K桶），如果不是則直接丟棄該節(jié)點

（5） 如果該K桶不是自身所在的K桶，則需要進行K桶分拆。拆分的方法即是一個變?yōu)閮蓚€等長K桶，一個包括自身，一個不包括。

（6） 對該節(jié)點添加到分拆后的一個K桶中去。

findNodes(id, invalid=True)的過程是：//該過程是內(nèi)部過程，給下面findNode(

（0） 如果該節(jié)點在自己的K桶中，則直接返回，結(jié)束該過程

（1） 如果invalid=True，則需要排除當(dāng)前無效的節(jié)點

（2） 如果上面選取該K桶中的所有節(jié)點小于K(8)，則需要從其他桶中補充，如下

（3） 把左右相鄰的兩個K桶中的節(jié)點補充進去，然后把所有這些節(jié)點按照離id距離遠近進行排序，選取最近的K(8)個節(jié)點

（4） 返回最后得到的最近的K個節(jié)點。

findNode(id)的過程是：

（1） 從自己本地的“路由表“取離id最近的K桶，返回k(8)個nodes信息

（2） 從上面k個信息中選取a個（3）個，然后發(fā)送findNode消息給這3個節(jié)點

（3） 該3個節(jié)點查找自己的“路由表“同時返回k個nodes信息

（4） 從上面得到的3*k個節(jié)點在重復(fù)

Keyexpired過程：

1） 節(jié)點存放的（info-hash，peers-list）如果24小時沒有收到原節(jié)點的更新則視作無效

2） 當(dāng)前仍然活動的peer-lists中的節(jié)點需要24小時向其close節(jié)點進行刷新info-hash，peers-list。

3）當(dāng)前仍然活動的peer-lists中的節(jié)點如果在自己的路由表中發(fā)現(xiàn)有離info-hash更近的節(jié)點，則會把自（info-hash，peers-list）announce給它們。

在BT程序中，對外只有一個過程，那就是下面的getPeersAndAnnounce過程，該過程的作用就是對提供的info-hash找到一個peers list表，并且把自己作為一個peer告訴給別人：

getPeersAndAnnounce過程：

（0） 該過程包括了getPeers和Announce_peer兩個過程

（1） getPeers的過程首先是在自己的本地的（info-hash, peers-list）表中進行查找，如果查找到則直接進行連接

（2） 如果本地沒有info-hash的key,values，則需要進行遠程查找，查找的過程是

（3） 先從info-hash對應(yīng)的K桶中找k個節(jié)點，然后分別向它們發(fā)送getpeers原始RPC消息

（4） 分析上面k個節(jié)點的響應(yīng)信息，如果響應(yīng)信息中存在values字段，則說明命中一個節(jié)點，該節(jié)點保存有info-hash的peers-list信息，保存起來。如果響應(yīng)消息中只有nodes字段，則該字段后面跟上的是k（8）個更接近于info-hash的節(jié)點，判斷這些節(jié)點是否發(fā)送過，如果沒有則把這些節(jié)點保存起來繼續(xù)發(fā)送getPeers RPC消息，直到收到響應(yīng)消息中帶有values字段，或者響應(yīng)消息中所有的節(jié)點都發(fā)送過了（沒有更接近info-hash的節(jié)點了）

（5） 當(dāng)收到節(jié)點對get_peers響應(yīng)包中包括有(info-hash,peers-list)后，則首先向響應(yīng)者發(fā)送announce，然后向自己K桶中離info-hash最近的k個節(jié)點發(fā)送announce_peer消息

Ping消息的發(fā)送過程：

1） 對于DHT種子文件中nodes逐個節(jié)點發(fā)送ping消息，有響應(yīng)者則添加到“路由表”中去   

2） 當(dāng)插入新節(jié)點到“路由表”中時，如果該“路由表”K桶已滿，則會選擇K桶的頭部節(jié)點進行ping操作，如果該頭節(jié)點仍然在線，則直接丟棄該節(jié)點（這是基于一種越長時間在線則可能以后越長在線的概率統(tǒng)計），否則刪除頭節(jié)點，并把新節(jié)點插到K桶尾。

五、參考資料：

１）Kademlia-A-P2P-Information-System.pdf

２）http://www./trac/wiki/Khashmir

3）http://www./beps/bep_0005.html

4）BitTorrent-4.4.0代碼