DBCAN：一種基于de Bruijn 圖的高效P2P 模型

畢海波

（中國人民銀行烏魯木齊中心支行，烏魯木齊830002）

0 引言

CAN（Content Addressable Network，內容可尋址網絡）是一個簡單、容錯的多維空間P2P 模型，采用多維空間拓撲結構。CAN 思想簡單、直觀，比其他結構化P2P 模型容易理解。CAN 每個節點占有一個屬于自己的區域并且負責該區域中所有的“點”，并由負責該點的節點來存儲數據對象。每個節點維護一個路由表，記錄它在多維空間上的鄰居信息。當每個新節點加入CAN 后，它必須擁有自己的空間。每個新節點被映射到一個點，在它加入之后，該點原來所在的區域將一分為二，一半分給新節點來負責，另一半由原來的節點負責，相應的數據對象也會重新分配。當一個節點離開CAN 后，它的某個鄰居必須接管原來由它負責的區域，相當于區域合并。隨著節點的不斷加入和離開，CAN網絡的區域將被劃分地支離破碎，而且會出現越來越多由一個節點負責多個節點的情況，直到節點的負載超過它能力的上限。為了提高CAN 的性能，本文找到一種方法來合并那些較小的區域，使它們盡量變得規整，從而使節點度、負載均衡和路由路徑長度等性能得到進一步優化。

1 de Bruijn圖及其性質

1.1 de Bruijn圖相關定義

1.1.1 de Bruijn 圖

對于兩個給定的整數d（≥2）和n（≥1），de Bruijn有向圖，記為B（d，n），它的頂點集：

它的邊集E 是由從頂點x1x2…xn到d 個x2…xnα 的所有邊組成的，其中α ∈{0，1，…，d-1}。圖1 表示d=2，n=3 的de Bruijn 圖。

圖1 de Bruijn圖B（2，3）

1.1.2 de Bruijn 串和de Bruijn 空間

de Bruijn 圖B（d，n）的頂點x1x2…xn（xi∈{0，1，…，d-1}，1≤i≤n）稱為基底為d、長度為n 的de Bruijn 串，de Bruijn 空間de Bruijn Space（d，n）是指所有基底為d、長度為n 的de Bruijn 串的集合。

1.2 de Bruijn圖的性質

對于任何d≥2 和n≥1 的de Bruijn 圖B（d，n）有以下性質：

（1）B（d，n）有dn個頂點，dn+1條邊，d 條環；

（2）B（d，n）直徑為n；

（3）B（d，n）中每個節點的出度和入度都為d，即d正則。

1.3 de Bruijn圖中最短路徑的唯一性

設x=x1x2…xn和y=y1y2…yn是B（d，n）中兩個不同的頂點。用l（x，y）表示x 的尾部和y 的首部重疊數字的最大數目，并設這些重疊的數字為z1z2…zl，即l（x，y）是最大的l 使得：

記B（d，n）中（x，y）：

則P（x，y）是B（d，n）中唯一最短（x，y）路徑，長為n-l。

B（d，n）中任何兩點之間最短路徑的唯一性非常重要，它可以保證路由的有效性和正確性，根據這個性質就可以設計B（d，n）中任何兩個頂點之間的最短路徑路由算法了。

2 DBCAN路由模型

DBCAN 使用de Bruijn 圖B（2，n）作為拓撲結構，采用B（2，n）而不是更一般的B（d，n）作為拓撲結構，是為了DBCAN 維護時更易處理。DBCAN 中每個節點都負責維護虛擬2 維笛卡爾空間中的一塊區域，節點與其所負責的區域是一一對應的，節點的標識即是它所負責區域的標識。

2.1 數據的命名與分布

2.1.1 數據的命名

DBCAN 中的標識分為數據標識和節點標識：

（1）數據標識

本文采用隨機生成的128 位二進制字符串作為數據標識。

（2）節點標識

在介紹節點標識之前首先給出“通用前綴集”的概念。

通用前綴集是一個由二進制字符串組成的集合，對于任何二進制字符串w ∈{0，1}*，集合中都有一個唯一的字符串是它的前綴。

例如，{0，10，110，111}就是一個通用前綴集，因為對于任何二進制字符串，集合中都對應的有唯一的字符串是它的前綴。

在DBCAN 中，每個節點標識對應于通用前綴集中的一個字符串，節點標識空間就是一個通用前綴集。注意：通用前綴集中的字符串長度可能不一樣，所以在DBCAN 中，每個節點的標識長度并不一定等長，這與傳統的de Bruijn 圖中的頂點標識長度等長不同。

2.1.2 數據的分布

本文定義在DBCAN 中，數據對象K=k1k2…km由節點X=x1x2…xn負責，當且僅當x1x2…xn是k1k2…km的前綴。根據上面所述，在DBCAN 中必然有一個節點標識是數據對象K 的前綴，并且可知，標識為x1x2…xn的節點可以負責的數據個數為2m-n，即所有以x1x2…xn為前綴的數據都由它負責。

2.2 節點鄰居關系

在DBCAN 中，每個節點的標識都是一個以2 為基底的de Bruijn 串，這些節點根據它們的標識按照de Bruijn 圖的規則組織在一起，形成鄰居關系。網絡的最初狀態為空網絡，即網絡中沒有節點。隨著網絡中節點不斷的變化（加入或者退出），DBCAN 中節點維護的區域會進行相應的拆分或合并，變化的區域所對應的節點的標識也會相應的改變，當然節點的鄰居關系也會做相應的變化。但是無論網絡怎樣變化，DBCAN 的節點標識空間都是一個通用前綴集。

本文定義節點X 指向的節點稱為X 的孩子，指向X 節點的節點稱為X 的父親。

在DBCAN 中，節點的鄰居關系如下：

節點X=x1x2…xk要么只有一個形式為x2…xj的孩子，j≤k；要么有幾個形式為x2…xky1…yl的孩子，1≤l ≤m-k+1。后面這種情況，形式為y1…yl的字符串構成一個通用前綴集。相應地，節點X=x1x2…xk的父親也有兩種形式：形式為α x1…xj，α ∈{0，1}，j≤k；形式為β x1x2…xky1…yl，β ∈{0，1}，1≤l ≤m-k-1。后一種情況，形式為y1…yl的字符串構成一個通用前綴集。這兩種情況也可以共同存在，但此時α ≠β。

另外，節點如00…0 和11…1 的孩子和父親的形式與一般情況有所不同。節點U=α α…α，α ∈{0，1}，它的孩子的形式為α…α y1…yl，ι≥1，y1=αˉ，字符串y2…yl構成一個通用前綴集。

2.3 路由算法

DBCAN 的路由算法采用de Bruijn 圖的最短路徑路由算法。假設在DBCAN 中有一個節點的標識是U=u1u2…uz，X=x1x2…xk為DBCAN 中任意一個節點，現在從節點X 開始定位節點U。

在給出路由算法之前，本文首先規定字符串S 是最長的X 的節點標識的后綴并且是U 的節點標識的前綴，有可能S=Φ，因為有可能X 的節點標識的后綴和U 的節點標識的前綴沒有重合部分。

節點X 定位節點U 的路由算法如下：

（1）如果S=x1x2…xk，則說明X=U，即X 就是所要找的節點U，定位完成，否則進入（2）；

（2）如果節點X 只有一個孩子V=x2…xj，那么定位U 的過程轉向節點V；如果X 有幾個孩子，那么定位U 的過程轉向節點V=x2…xky1…yl，其中S y1…yl是u1u2…uz的一個前綴。根據通用前綴集性質，節點X 一定存在這樣一個孩子，并且是唯一的。

以下為DBCAN 的路由算法偽碼。

2.4 數據的發布

在DBCAN 中，數據的發布也是根據路由算法實現的。如果節點U（U 為DBCAN 中任意一個節點）有數據要發布，其發布過程如下：

（1）節點U 首先獲得數據標識K；

（2）然后節點U 發起到數據標識K 的路由，最終路由會到達節點V，節點V 的標識是數據標識K 的前綴；

（3）數據的信息就發布在節點V 上。

3 實驗仿真

對P2P 網絡來說，由于其規模巨大，實際構建大規模的分布式網絡帶來的硬件、軟件開銷通常是難以付出的，因此對P2P 網絡來說，實驗仿真是非常重要的。本文采用P2Psim 對DBCAN 進行實驗仿真。

3.1 節點度數

節點度數是指網絡中節點的“連接數”，即邏輯上與其他節點連接的個數。在結構化P2P 網絡中則體現在路由表的表項數目上。路由表越小，查詢的效率越高，維護的開銷越小，網絡性能也就越好。

本文分別仿真了節點規模為1 千、1 萬和10 萬的DBCAN，它們的節點度的分布如圖2 所示。

圖2 DBCAN節點度數的分布

圖2 表明，規模不同的DBCAN，它們的節點度數分布雖然不同，但大致相仿，這表明DBCAN 中節點度數的分布不會隨著網絡規模的擴大而改變，是穩定的。

通過統計得知，DBCAN 的節點度數平均為2，這與de Bruijn 圖的頂點度相吻合。對一個d 維CAN 來說，它的節點度數為2d，所以對于2 維CAN，它的節點度數為4；在Koorde 中，每個節點度為4。可以看出，DBCAN 的節點度是三者中最優的。

3.2 負載均衡

良好的“負載均衡”是所有基于分布式散列表的P2P 網絡都希望具有的屬性，因為它能使得整個網絡更高效地工作，更充分地利用每個網絡成員的資源。

由于CAN 中的節點也是維護空間中的一塊區域，所以本文對DBCAN 負載均衡性能的評測是將它與CAN 進行比較，對比兩者不同面積的區域的分布情況。

本文對負載均衡實驗仿真的節點規模為5 萬，并與相同規模的CAN 進行了比較。網絡中數目最多的區域面積用S 表示，面積是它的1/2 的用S/2 表示，面積是它的2 倍的用2S 表示，其他的以此類推，它們的分布如圖3 所示。

圖3 區域面積的分布

如圖3 所示，DBCAN 的面積分布在4 個區域，面積為S 和2S 的區域占93%；CAN 的面積分布在7 個區域，各區域分布較分散不集中，且存在碎片區域。從而可以看出DBCAN 的負載均衡性能優于CAN。

3.3 路由路徑長度

“路由路徑長度”是指網絡中節點定位時，路由過程中所需要完成的路由跳數。它是衡量P2P 網絡性能最重要的指標之一，因為定位是網絡中最基本、最常用，同時也是最重要的部分。

本文對DBCAN 的路由路徑長度（路由跳數）進行了仿真實驗，并將結果與CAN（d=2），CAN（d=3）和Koorde 進行了比較。實驗中節點的規模分別為256、512、1024、2K、4K、8K、16K、32K 和64K。對每種規模的網絡本文分別進行了100 次實驗，然后計算這100次路由的平均路由路徑長度，實驗結果如圖4 所示。

圖4 路由路徑長度

如圖4 所示，在任何規模的網絡中，CAN（d=2）和Koorde 的路由跳數都要高于DBCAN。當網絡中的節點數在256 至4K 時，CAN（d=3）的路由跳數要小于DBCAN，而當網絡中的節點數大于4K 后，CAN（d=3）的路由跳數就都高于DBCAN。從而可以看出，DBCAN總體上的路由路徑長度指標要優于其他三者，特別是隨著網絡規模的不斷擴大。

4 結語

本文通過對de Bruijn 圖和CAN 等網絡模型的研究，提出了一種節點度數、負載均衡和路由路徑長度等性能均更優的DBCAN 模型。本文沒有采用計算機的IP 地址直接作為P2P 覆蓋網上節點的標識，而是采用通用前綴集來實現將物理網上的計算機映射到覆蓋網。如何在不損失物理網上節點之間的鄰近關系基礎上實現物理網到覆蓋網映射將是下一步的工作。