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

畢海波

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

0 引言

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

1 de Bruijn圖及其性質

1.1 de Bruijn圖相關定義

1.1.1 de Bruijn 圖

對于兩個給定的整數(shù)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 條環(huán)；

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

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

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

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

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

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

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

2 DBCAN路由模型

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

2.1 數(shù)據(jù)的命名與分布

2.1.1 數(shù)據(jù)的命名

DBCAN 中的標識分為數(shù)據(jù)標識和節(jié)點標識：

（1）數(shù)據(jù)標識

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

（2）節(jié)點標識

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

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

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

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

2.1.2 數(shù)據(jù)的分布

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

2.2 節(jié)點鄰居關系

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

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

在DBCAN 中，節(jié)點的鄰居關系如下：

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

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

2.3 路由算法

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

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

節(jié)點X 定位節(jié)點U 的路由算法如下：

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

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

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

2.4 數(shù)據(jù)的發(fā)布

在DBCAN 中，數(shù)據(jù)的發(fā)布也是根據(jù)路由算法實現(xiàn)的。如果節(jié)點U（U 為DBCAN 中任意一個節(jié)點）有數(shù)據(jù)要發(fā)布，其發(fā)布過程如下：

（1）節(jié)點U 首先獲得數(shù)據(jù)標識K；

（2）然后節(jié)點U 發(fā)起到數(shù)據(jù)標識K 的路由，最終路由會到達節(jié)點V，節(jié)點V 的標識是數(shù)據(jù)標識K 的前綴；

（3）數(shù)據(jù)的信息就發(fā)布在節(jié)點V 上。

3 實驗仿真

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

3.1 節(jié)點度數(shù)

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

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

圖2 DBCAN節(jié)點度數(shù)的分布

圖2 表明，規(guī)模不同的DBCAN，它們的節(jié)點度數(shù)分布雖然不同，但大致相仿，這表明DBCAN 中節(jié)點度數(shù)的分布不會隨著網(wǎng)絡規(guī)模的擴大而改變，是穩(wěn)定的。

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

3.2 負載均衡

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

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

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

圖3 區(qū)域面積的分布

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

3.3 路由路徑長度

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

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

圖4 路由路徑長度

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

4 結語

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