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

算法的分析與仿真

組長：SC06023108 顧菁華

組員：SC06023103 徐其

SC06023105 周楠

SC06023106 丁晟

SC06023107 李理敏CAN

小組分工

組長 顧菁華 SC06023108 CAN算法C 語言實(shí)現(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ò)展、容錯(cuò)和完全自組織等特點(diǎn)。

本文介紹了CAN 的基本結(jié)構(gòu)和工作原理，對其關(guān)鍵技術(shù)尋路性能、負(fù)載均衡作了優(yōu)化和改進(jìn)。在VC 6.0中實(shí)現(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é)點(diǎn)插入......................................................................................................4 節(jié)點(diǎn)離開......................................................................................................4 節(jié)點(diǎn)失效......................................................................................................4 尋路性能優(yōu)化...................................................................................................................6 多維坐標(biāo)空間.......................................................................................................6 多實(shí)體（reality ）結(jié)構(gòu).........................................................................................6 過載坐標(biāo)區(qū)...........................................................................................................7 更好的CAN 路由metrics....................................................................................7 最大面積尋路.......................................................................................................8 修改鄰居表沿對角線尋路...................................................................................8 層次化結(jié)構(gòu)...........................................................................................................8 多個(gè)哈希函數(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 語言實(shí)現(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è)計(jì)時(shí)在擴(kuò)展性方面存在重大問題，如早期Napster 使用集中目錄服務(wù)而存在單點(diǎn)故障問題，Gnutella 采用類似OSPF 路由協(xié)議的洪泛搜索機(jī)制，不僅造成過多的網(wǎng)絡(luò)流量，同時(shí)可擴(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ù)?，比如CAN 是一個(gè)d 維坐標(biāo)空間，Chord 是一個(gè)環(huán)形拓?fù)?，Tapestry 則是一個(gè)網(wǎng)狀的拓?fù)洹?/p>

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

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

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

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

1

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

1.1.2 接入模型

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

1.1.3 CAN 路由

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

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

2

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

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

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

1.2 CAN 構(gòu)造

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

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

3

1.2.1 節(jié)點(diǎn)插入

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

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

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

1.2.2 節(jié)點(diǎn)離開

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

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

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

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

1.2.3 節(jié)點(diǎn)失效

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

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

的是，幾個(gè)鄰居節(jié)點(diǎn)可以同時(shí)獨(dú)立的開始TAKEOVER 機(jī)制。

TAKEOVER 機(jī)制如下：

每個(gè)節(jié)點(diǎn)初始化一個(gè)正比于它的空間大小的計(jì)時(shí)器。

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

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

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

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

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

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

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

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

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

2

3

6

7

8

10

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

表2-1 1000個(gè)節(jié)點(diǎn)時(shí)維數(shù)最優(yōu)值

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

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

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

6