算法的分析與仿真組長：SC06023108 顧菁華組員：SC06023103 徐其SC06023105 周楠SC06023106 丁晟SC06023107 李理敏CAN

算法的分析與仿真

組長：SC06023108 顧菁華

組員：SC06023103 徐其

SC06023105 周楠

SC06023106 丁晟

SC06023107 李理敏CAN

小組分工

組長 顧菁華 SC06023108 CAN算法C 語言實現(xiàn)以及負(fù)載均組員 周楠 SC06023105 CAN

丁晟 SC06023106 CAN

李理敏 SC06023107 CAN

徐其 SC06023103 衡的優(yōu)化 原理研究以及結(jié)構(gòu)分析 尋路性能優(yōu)化 算法負(fù)載均衡問題研究 基于CAN 的應(yīng)用層組播研究

摘要

內(nèi)容尋址網(wǎng)絡(luò)（CAN ）是一種用于結(jié)構(gòu)化對等網(wǎng)絡(luò)P2P 的分布式哈希查找系統(tǒng)，可以在Internet 規(guī)模的大型對等網(wǎng)絡(luò)上提供類似哈希表的功能，具有可擴(kuò)展、容錯和完全自組織等特點。

本文介紹了CAN 的基本結(jié)構(gòu)和工作原理，對其關(guān)鍵技術(shù)尋路性能、負(fù)載均衡作了優(yōu)化和改進(jìn)。在VC 6.0中實現(xiàn)了CAN 的基本功能、負(fù)載均衡優(yōu)化。最后，介紹了基于CAN 算法的應(yīng)用層組播。

【關(guān)鍵字】 CAN，尋路性能，負(fù)載均衡，組播

II

目錄

摘要........................................................................................................................................... I 目錄.........................................................................................................................................III

1. 概述...................................................................................................................................1

1.1 CAN基礎(chǔ)結(jié)構(gòu).....................................................................................................1

1.1.1

1.1.2 數(shù)據(jù)模型......................................................................................................1 接入模型......................................................................................................2

1.1.3 CAN路由.....................................................................................................2

1.2 CAN構(gòu)造.............................................................................................................3

1.2.1

1.2.2

1.2.3

2.

2.1

2.2

2.3

2.4

2.5

2.6

2.7

2.8

3.

3.1

3.2

3.3 節(jié)點插入......................................................................................................4 節(jié)點離開......................................................................................................4 節(jié)點失效......................................................................................................4 尋路性能優(yōu)化...................................................................................................................6 多維坐標(biāo)空間.......................................................................................................6 多實體（reality ）結(jié)構(gòu).........................................................................................6 過載坐標(biāo)區(qū)...........................................................................................................7 更好的CAN 路由metrics....................................................................................7 最大面積尋路.......................................................................................................8 修改鄰居表沿對角線尋路...................................................................................8 層次化結(jié)構(gòu)...........................................................................................................8 多個哈希函數(shù).......................................................................................................9 多播發(fā)現(xiàn)(MD)算法:...........................................................................................10 梯度法(GR)........................................................................................................10 分布式堆.............................................................................................................11

3.3.1

3.3.2 堆定義........................................................................................................11 分布式堆(Distributed Heap method)算法.................................................12 負(fù)載均衡.........................................................................................................................10

4. CAN基本操作的C 語言實現(xiàn).......................................................................................14

4.1 CAN算法的基本操作.......................................................................................14

4.2

5.1

5.2

III 對CAN 算法負(fù)載均衡的優(yōu)化..........................................................................18 組播組結(jié)構(gòu).........................................................................................................21 組播消息傳遞機(jī)制.............................................................................................215. CAN在應(yīng)用層組播中的應(yīng)用.......................................................................................21

1. 概述

對等網(wǎng)絡(luò)（Peer-to-Peer Network，P2P ）的核心是P2P 路由算法，算法的優(yōu)劣直接關(guān)系到P2P 系統(tǒng)的性能和可擴(kuò)展性。但P2P 最初設(shè)計時在擴(kuò)展性方面存在重大問題，如早期Napster 使用集中目錄服務(wù)而存在單點故障問題，Gnutella 采用類似OSPF 路由協(xié)議的洪泛搜索機(jī)制，不僅造成過多的網(wǎng)絡(luò)流量，同時可擴(kuò)展性也較差。為了解決P2P 系統(tǒng)可擴(kuò)展性差問題，一些研究工作組提出了新一代支持分布式哈希表（DHT ）技術(shù)的結(jié)構(gòu)化可擴(kuò)展P2P 系統(tǒng)，這是一種采用純分布式的消息傳遞機(jī)制和根據(jù)關(guān)鍵字進(jìn)行查找的資源定位服務(wù)，是目前擴(kuò)展性最好的P2P 路由方式之一。此類路由算法主要包括加州大學(xué)伯克利分校的CAN （ Content-Addressable Network ，內(nèi)容尋址網(wǎng)絡(luò)）和Tapestry ，麻省理工學(xué)院的Chord 、IRIS ，以及微軟研究院的Pastry 。它們采用各自的DHT 算法，而不同的DHT 算法決定了P2P 網(wǎng)絡(luò)不同的邏輯拓?fù)洌热鏑AN 是一個d 維坐標(biāo)空間，Chord 是一個環(huán)形拓?fù)?，Tapestry 則是一個網(wǎng)狀的拓?fù)洹?/p>

CAN 是一種用于結(jié)構(gòu)化對等網(wǎng)絡(luò)P2P 的分布式哈希查找系統(tǒng)，可以在Internet 規(guī)模的大型對等網(wǎng)絡(luò)上提供類似哈希表的功能，具有可擴(kuò)展、容錯和完全自組織等特點。

1.1 CAN基礎(chǔ)結(jié)構(gòu)

1.1.1 數(shù)據(jù)模型

在CAN 的構(gòu)造中，借助于一個虛擬的d 維笛卡兒坐標(biāo)空間。這是一個完全邏輯化的坐標(biāo)空間，并且在每一維上都是周期循環(huán)的。舉例來說，我們假設(shè)一個一維的，[0,1]的坐標(biāo)空間，這樣一個空間由一個圓圈表示，見圖1?？臻g的大小等于圓的直徑。在這樣一個一維空間中，兩點之間的距離等于它們之間最短的弧長。

1

CAN 系統(tǒng)相當(dāng)于一張哈希表，它是由很多單個的節(jié)點組成，這些節(jié)點存儲了整張哈希表的一部分。在這里，一個節(jié)點并不等同于一臺對等主機(jī)，它更像是一個僅提供信息引索的服務(wù)器。在CAN 中，一塊哈希表叫做一塊空間。即CAN 的d 維笛卡兒空間中被節(jié)點劃分為若干空間，每個節(jié)點占據(jù)一塊空間。CAN 中的空間可有不同的大小。但是在二維中，這些空間必須是正方形。

1.1.2 接入模型

用戶和P2P 系統(tǒng)之間的第一步交互就是接入系統(tǒng)。CAN 提供一種使用bootstrap 的機(jī)制。假設(shè)CAN 有一個可以幫助解析CAN 中bootstrap 節(jié)點的IP 地址的DNS 域名系統(tǒng)。一個bootstrap 節(jié)點擁有一張含有部分節(jié)點信息的表。當(dāng)這個模型中的一個用戶發(fā)出請求，并且使用了CAN 域名，它的客戶端就能自動的從一個bootstrap 節(jié)點那里建立起一個連接，同任意一個可連接的節(jié)點相連。

1.1.3 CAN 路由

對分布式路由表（DHT ）系統(tǒng)來說，路由算法是非常重要的。因為它定義了詢問的相應(yīng)時間和數(shù)據(jù)的可達(dá)性。一個不好的分布式系統(tǒng)的路由算法會降低系統(tǒng)的性能。簡單說來CAN 的路由就是由源節(jié)點向目的節(jié)點沿著笛卡兒坐標(biāo)的直線前行的。一個CAN 節(jié)點維護(hù)了一張坐標(biāo)路由表，這張表包含這個節(jié)點的相鄰節(jié)點的IP 地址和虛擬坐標(biāo)空間。在d 維坐標(biāo)空間中，兩個節(jié)點相鄰的定義就是如果它們在d-1維空間中重疊并且在一維空間中相鄰，那么它們則在d 維空間中相鄰。一個包含目的節(jié)點坐標(biāo)的CAN 消息，通過它的鄰居坐標(biāo)集和簡單的貪心算法（greedy forwarding）找到目的坐標(biāo)。

這里還有一個錯誤忍耐路由（Fault tolerance routing）的概念。就是說如果一個節(jié)點丟

2

失了它所有鄰居節(jié)點信息，這樣上面這個路由算法就失效了。為了避免這種情況，我們要在基礎(chǔ)的路由算法之上擴(kuò)展下面的規(guī)則：在達(dá)到節(jié)點之前先查詢當(dāng)前節(jié)點的鄰居節(jié)點是否都是可達(dá)的。在這種情況下，數(shù)據(jù)可能不是最優(yōu)的，但是所選擇的路徑都是可達(dá)的。下圖就是錯誤忍耐路由的圖示：

對一個劃分為n 等份的d 維空間來說，平均路由長度為(d /4)(n 1/d ) 跳，并且單個節(jié)點有2d 個鄰居。這樣的結(jié)果意味著對d 維空間來說，我們可以增加節(jié)點（也就是空間）的數(shù)量而不增加每個節(jié)點狀態(tài)，因為平均路徑長度是成(n

1/d ) 的整數(shù)倍增長。

1.2 CAN 構(gòu)造

這部分主要說明CAN 是如何構(gòu)造的。我們假設(shè)在這個系統(tǒng)中原先已有起碼一個節(jié)點。 在CAN 中，信息以關(guān)鍵字－數(shù)據(jù)對（Key ，Value ）的形式存儲，其中Key 通過兩個獨立的均勻哈希函數(shù)映射到CAN 空間中的一點P （x ，y ），如果P 點屬于某一節(jié)點所占的區(qū)域，則該節(jié)點實際存儲這一關(guān)鍵字的數(shù)據(jù)對。此外，每個節(jié)點都存儲了其每個鄰居節(jié)點的IP 、物理IP 等信息，并定時對這些信息進(jìn)行更新以保持鄰居間的互連。

在CAN 中，主要提供三種對于（Key ，Value ）的基本操作，即插入、查詢、離開或失效。下面我們介紹其中的節(jié)點插入、離開和失效，節(jié)點的查詢將在第二部分詳述。

3

1.2.1 節(jié)點插入

一個新的節(jié)點到達(dá)之后，我們首先要給它分配一塊空間。這里要說明的是我們沒有空閑的空間可供分配，新的節(jié)點的達(dá)到我們都需要從已有的節(jié)點空間中劃分出來。最簡單的方法就是把一個節(jié)點的空間一分為二。下面就是這個新的節(jié)點要找到這塊分配給它的空間，這就需要一個尋找空間的路由算法，如下：

一個新的節(jié)點同CAN 中任意節(jié)點相連都要使用2.2中所述的接入機(jī)制。當(dāng)新節(jié)點發(fā)送一個加入請求之后，CAN 節(jié)點隨機(jī)的選擇笛卡兒坐標(biāo)空間中的一個點。這個點的空間就被一分為二。這個加入請求由2.3所述的普通的CAN 路由算法實現(xiàn)。

一旦新節(jié)點找到自己的坐標(biāo)，下一步就是要啟動這個新節(jié)點。首先，這個新節(jié)點以及它的另一半得到它的鄰居列表，然后它要把新的系統(tǒng)狀態(tài)通知它的鄰居來修改它們的鄰居列表。這樣整個系統(tǒng)得到更新。

1.2.2 節(jié)點離開

當(dāng)一個節(jié)點正常的離開系統(tǒng)，它將告知系統(tǒng)它將離開。在這種情況下，很有必要保持物理完整性，替代離開節(jié)點的空間和邏輯完整性。為此，CAN 提供了如下的算法：

將要離開的節(jié)點找到這樣一個節(jié)點，這個節(jié)點首先要求合并之后面積最小，若有若干面積最小的代選節(jié)點，則選擇離開節(jié)點的空間合并之后組成一個方形空間的節(jié)點。

將離開的節(jié)點空間被已被選中的鄰居覆蓋，物理完整性得到保護(hù)。

為這個空間提供一個路由，這個系統(tǒng)需要更新它的狀態(tài)。離開節(jié)點的鄰居節(jié)點將得到通知，另外一個節(jié)點現(xiàn)在開始變?yōu)樗鼈兊泥従庸?jié)點。接受這個空間的節(jié)點也將改變自己的鄰居列表并通知它的鄰居節(jié)點。

1.2.3 節(jié)點失效

在這種情況下，節(jié)點離開之前不通知系統(tǒng)。這將通過一個接管算法來處理，這個接管算法將保證失效節(jié)點的一個鄰居節(jié)點接管這塊空間。然而失效節(jié)點包含的（Key ，Value ）對就會丟失直到數(shù)據(jù)擁有者刷新狀態(tài)，在這種情況下，P2P 文件分布系統(tǒng)的用戶將會再次連接CAN 并且共享他們的文件。

在一般情況下，普通節(jié)點發(fā)送周期性的更新消息給它的鄰居節(jié)點，這些消息包含它的空間坐標(biāo)和它鄰居節(jié)點坐標(biāo)的列表。如果很長時間鄰居節(jié)點沒有收到這樣的消息則表明它失效。如果某個節(jié)點判斷出它的某個鄰居節(jié)點失效它就會初始化TAKEOVER 機(jī)制。需要指出 4

的是，幾個鄰居節(jié)點可以同時獨立的開始TAKEOVER 機(jī)制。

TAKEOVER 機(jī)制如下：

每個節(jié)點初始化一個正比于它的空間大小的計時器。

如果一個計時器到期了，它就會發(fā)送TAKEOVER 信息給所有失效的鄰居節(jié)點。

收到TAKEOVER 信息的鄰居節(jié)點和它自己的空間大小比較，如果發(fā)送TAKEOVER 的空間比自己的空間小，則發(fā)送新的TAKEOVER 消息。

一個沒有收到一個較小空間的TAKEOVER 消息的失效節(jié)點將會接管離開節(jié)點的空間。 5

2. 尋路性能優(yōu)化

前面描述的CAN 的基本算法提供了低節(jié)點狀態(tài)（d 維空間為O （d ））和最短路徑長度（d 維空間n 個節(jié)點為O

（d ）跳）之間的平衡。這里所說的跳數(shù)是應(yīng)用層的跳數(shù)，不是IP 層的跳數(shù)，并且每跳的延遲是真實的。在CAN 中相鄰的節(jié)點實際上可能相隔幾里或中間經(jīng)過很多IP 跳，查找的平均總延遲是CAN 平均跳數(shù)乘以每個CAN 跳的平均延遲。我們希望能夠得到一個可以與請求者和擁有關(guān)鍵字的節(jié)點之間的真實IP 延遲相比較的查找延遲。可以用以下幾種方法進(jìn)行尋路性能優(yōu)化。

2.1 多維坐標(biāo)空間

改進(jìn)尋路延遲的最簡單的方法是增加坐標(biāo)空間的維數(shù)。平均路徑長度為O

（d ），假設(shè)n 為常數(shù)，很容易找到一個最優(yōu)的維數(shù)值d 使平均路徑長度最小。表2-1是節(jié)點數(shù)為1000時的一個例子。 d

2

3

6

7

8

10

20平均路徑長度200 30 18.973 18.778 18.970 19.952 28.250

表2-1 1000個節(jié)點時維數(shù)最優(yōu)值

2.2 多實體（reality ）結(jié)構(gòu)

設(shè)計多個獨立的坐標(biāo)空間，系統(tǒng)中每個節(jié)點在不同的坐標(biāo)空間中分配不同的區(qū)。假設(shè)將坐標(biāo)空間稱為“實體”，因此對于有r 個實體的CAN ，每個節(jié)點將被分配r 個坐標(biāo)區(qū)，并且維護(hù)r 個獨立的鄰接表。

這樣，哈希表的內(nèi)容在每個實體上復(fù)制，提高了數(shù)據(jù)的可用性。例如，指向某個文件的指針存在坐標(biāo)空間（x ，y ，z ）中，對于四個實體的情況，指針會存在每個實體坐標(biāo)空間（x ，y ，z ）的四個不同的節(jié)點中，這樣，只有當(dāng)四個節(jié)點都失效時，數(shù)據(jù)才不可用。多個實體也

6