CAN算法的分析與仿真
算法的分析與仿真組長:SC06023108 顧菁華組員:SC06023103 徐其SC06023105 周楠SC06023106 丁晟SC06023107 李理敏CAN
算法的分析與仿真
組長:SC06023108 顧菁華
組員:SC06023103 徐其
SC06023105 周楠
SC06023106 丁晟
SC06023107 李理敏CAN
,小組分工
組長 顧菁華 SC06023108 CAN算法C 語言實現(xiàn)以及負載均組員 周楠 SC06023105 CAN
丁晟 SC06023106 CAN
李理敏 SC06023107 CAN
徐其 SC06023103 衡的優(yōu)化 原理研究以及結構分析 尋路性能優(yōu)化 算法負載均衡問題研究 基于CAN 的應用層組播研究
,摘要
內(nèi)容尋址網(wǎng)絡(CAN )是一種用于結構化對等網(wǎng)絡P2P 的分布式哈希查找系統(tǒng),可以在Internet 規(guī)模的大型對等網(wǎng)絡上提供類似哈希表的功能,具有可擴展、容錯和完全自組織等特點。
本文介紹了CAN 的基本結構和工作原理,對其關鍵技術尋路性能、負載均衡作了優(yōu)化和改進。在VC 6.0中實現(xiàn)了CAN 的基本功能、負載均衡優(yōu)化。最后,介紹了基于CAN 算法的應用層組播。
【關鍵字】 CAN,尋路性能,負載均衡,組播
II
,目錄
摘要........................................................................................................................................... I 目錄.........................................................................................................................................III
1. 概述...................................................................................................................................1
1.1 CAN基礎結構.....................................................................................................1
1.1.1
1.1.2 數(shù)據(jù)模型......................................................................................................1 接入模型......................................................................................................2
1.1.3 CAN路由.....................................................................................................2
1.2 CAN構造.............................................................................................................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 多維坐標空間.......................................................................................................6 多實體(reality )結構.........................................................................................6 過載坐標區(qū)...........................................................................................................7 更好的CAN 路由metrics....................................................................................7 最大面積尋路.......................................................................................................8 修改鄰居表沿對角線尋路...................................................................................8 層次化結構...........................................................................................................8 多個哈希函數(shù).......................................................................................................9 多播發(fā)現(xiàn)(MD)算法:...........................................................................................10 梯度法(GR)........................................................................................................10 分布式堆.............................................................................................................11
3.3.1
3.3.2 堆定義........................................................................................................11 分布式堆(Distributed Heap method)算法.................................................12 負載均衡.........................................................................................................................10
4. CAN基本操作的C 語言實現(xiàn).......................................................................................14
4.1 CAN算法的基本操作.......................................................................................14
4.2
5.1
5.2
III 對CAN 算法負載均衡的優(yōu)化..........................................................................18 組播組結構.........................................................................................................21 組播消息傳遞機制.............................................................................................215. CAN在應用層組播中的應用.......................................................................................21
,1. 概述
對等網(wǎng)絡(Peer-to-Peer Network,P2P )的核心是P2P 路由算法,算法的優(yōu)劣直接關系到P2P 系統(tǒng)的性能和可擴展性。但P2P 最初設計時在擴展性方面存在重大問題,如早期Napster 使用集中目錄服務而存在單點故障問題,Gnutella 采用類似OSPF 路由協(xié)議的洪泛搜索機制,不僅造成過多的網(wǎng)絡流量,同時可擴展性也較差。為了解決P2P 系統(tǒng)可擴展性差問題,一些研究工作組提出了新一代支持分布式哈希表(DHT )技術的結構化可擴展P2P 系統(tǒng),這是一種采用純分布式的消息傳遞機制和根據(jù)關鍵字進行查找的資源定位服務,是目前擴展性最好的P2P 路由方式之一。此類路由算法主要包括加州大學伯克利分校的CAN ( Content-Addressable Network ,內(nèi)容尋址網(wǎng)絡)和Tapestry ,麻省理工學院的Chord 、IRIS ,以及微軟研究院的Pastry 。它們采用各自的DHT 算法,而不同的DHT 算法決定了P2P 網(wǎng)絡不同的邏輯拓撲,比如CAN 是一個d 維坐標空間,Chord 是一個環(huán)形拓撲,Tapestry 則是一個網(wǎng)狀的拓撲。
CAN 是一種用于結構化對等網(wǎng)絡P2P 的分布式哈希查找系統(tǒng),可以在Internet 規(guī)模的大型對等網(wǎng)絡上提供類似哈希表的功能,具有可擴展、容錯和完全自組織等特點。
1.1 CAN基礎結構
1.1.1 數(shù)據(jù)模型
在CAN 的構造中,借助于一個虛擬的d 維笛卡兒坐標空間。這是一個完全邏輯化的坐標空間,并且在每一維上都是周期循環(huán)的。舉例來說,我們假設一個一維的,[0,1]的坐標空間,這樣一個空間由一個圓圈表示,見圖1??臻g的大小等于圓的直徑。在這樣一個一維空間中,兩點之間的距離等于它們之間最短的弧長。
1
,CAN 系統(tǒng)相當于一張哈希表,它是由很多單個的節(jié)點組成,這些節(jié)點存儲了整張哈希表的一部分。在這里,一個節(jié)點并不等同于一臺對等主機,它更像是一個僅提供信息引索的服務器。在CAN 中,一塊哈希表叫做一塊空間。即CAN 的d 維笛卡兒空間中被節(jié)點劃分為若干空間,每個節(jié)點占據(jù)一塊空間。CAN 中的空間可有不同的大小。但是在二維中,這些空間必須是正方形。
1.1.2 接入模型
用戶和P2P 系統(tǒng)之間的第一步交互就是接入系統(tǒng)。CAN 提供一種使用bootstrap 的機制。假設CAN 有一個可以幫助解析CAN 中bootstrap 節(jié)點的IP 地址的DNS 域名系統(tǒng)。一個bootstrap 節(jié)點擁有一張含有部分節(jié)點信息的表。當這個模型中的一個用戶發(fā)出請求,并且使用了CAN 域名,它的客戶端就能自動的從一個bootstrap 節(jié)點那里建立起一個連接,同任意一個可連接的節(jié)點相連。
1.1.3 CAN 路由
對分布式路由表(DHT )系統(tǒng)來說,路由算法是非常重要的。因為它定義了詢問的相應時間和數(shù)據(jù)的可達性。一個不好的分布式系統(tǒng)的路由算法會降低系統(tǒng)的性能。簡單說來CAN 的路由就是由源節(jié)點向目的節(jié)點沿著笛卡兒坐標的直線前行的。一個CAN 節(jié)點維護了一張坐標路由表,這張表包含這個節(jié)點的相鄰節(jié)點的IP 地址和虛擬坐標空間。在d 維坐標空間中,兩個節(jié)點相鄰的定義就是如果它們在d-1維空間中重疊并且在一維空間中相鄰,那么它們則在d 維空間中相鄰。一個包含目的節(jié)點坐標的CAN 消息,通過它的鄰居坐標集和簡單的貪心算法(greedy forwarding)找到目的坐標。
這里還有一個錯誤忍耐路由(Fault tolerance routing)的概念。就是說如果一個節(jié)點丟
2
,失了它所有鄰居節(jié)點信息,這樣上面這個路由算法就失效了。為了避免這種情況,我們要在基礎的路由算法之上擴展下面的規(guī)則:在達到節(jié)點之前先查詢當前節(jié)點的鄰居節(jié)點是否都是可達的。在這種情況下,數(shù)據(jù)可能不是最優(yōu)的,但是所選擇的路徑都是可達的。下圖就是錯誤忍耐路由的圖示:
對一個劃分為n 等份的d 維空間來說,平均路由長度為(d /4)(n 1/d ) 跳,并且單個節(jié)點有2d 個鄰居。這樣的結果意味著對d 維空間來說,我們可以增加節(jié)點(也就是空間)的數(shù)量而不增加每個節(jié)點狀態(tài),因為平均路徑長度是成(n
1/d ) 的整數(shù)倍增長。
1.2 CAN 構造
這部分主要說明CAN 是如何構造的。我們假設在這個系統(tǒng)中原先已有起碼一個節(jié)點。 在CAN 中,信息以關鍵字-數(shù)據(jù)對(Key ,Value )的形式存儲,其中Key 通過兩個獨立的均勻哈希函數(shù)映射到CAN 空間中的一點P (x ,y ),如果P 點屬于某一節(jié)點所占的區(qū)域,則該節(jié)點實際存儲這一關鍵字的數(shù)據(jù)對。此外,每個節(jié)點都存儲了其每個鄰居節(jié)點的IP 、物理IP 等信息,并定時對這些信息進行更新以保持鄰居間的互連。
在CAN 中,主要提供三種對于(Key ,Value )的基本操作,即插入、查詢、離開或失效。下面我們介紹其中的節(jié)點插入、離開和失效,節(jié)點的查詢將在第二部分詳述。
3
,1.2.1 節(jié)點插入
一個新的節(jié)點到達之后,我們首先要給它分配一塊空間。這里要說明的是我們沒有空閑的空間可供分配,新的節(jié)點的達到我們都需要從已有的節(jié)點空間中劃分出來。最簡單的方法就是把一個節(jié)點的空間一分為二。下面就是這個新的節(jié)點要找到這塊分配給它的空間,這就需要一個尋找空間的路由算法,如下:
一個新的節(jié)點同CAN 中任意節(jié)點相連都要使用2.2中所述的接入機制。當新節(jié)點發(fā)送一個加入請求之后,CAN 節(jié)點隨機的選擇笛卡兒坐標空間中的一個點。這個點的空間就被一分為二。這個加入請求由2.3所述的普通的CAN 路由算法實現(xiàn)。
一旦新節(jié)點找到自己的坐標,下一步就是要啟動這個新節(jié)點。首先,這個新節(jié)點以及它的另一半得到它的鄰居列表,然后它要把新的系統(tǒng)狀態(tài)通知它的鄰居來修改它們的鄰居列表。這樣整個系統(tǒng)得到更新。
1.2.2 節(jié)點離開
當一個節(jié)點正常的離開系統(tǒng),它將告知系統(tǒng)它將離開。在這種情況下,很有必要保持物理完整性,替代離開節(jié)點的空間和邏輯完整性。為此,CAN 提供了如下的算法:
將要離開的節(jié)點找到這樣一個節(jié)點,這個節(jié)點首先要求合并之后面積最小,若有若干面積最小的代選節(jié)點,則選擇離開節(jié)點的空間合并之后組成一個方形空間的節(jié)點。
將離開的節(jié)點空間被已被選中的鄰居覆蓋,物理完整性得到保護。
為這個空間提供一個路由,這個系統(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é)點,這些消息包含它的空間坐標和它鄰居節(jié)點坐標的列表。如果很長時間鄰居節(jié)點沒有收到這樣的消息則表明它失效。如果某個節(jié)點判斷出它的某個鄰居節(jié)點失效它就會初始化TAKEOVER 機制。需要指出 4
,的是,幾個鄰居節(jié)點可以同時獨立的開始TAKEOVER 機制。
TAKEOVER 機制如下:
每個節(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ù)是應用層的跳數(shù),不是IP 層的跳數(shù),并且每跳的延遲是真實的。在CAN 中相鄰的節(jié)點實際上可能相隔幾里或中間經(jīng)過很多IP 跳,查找的平均總延遲是CAN 平均跳數(shù)乘以每個CAN 跳的平均延遲。我們希望能夠得到一個可以與請求者和擁有關鍵字的節(jié)點之間的真實IP 延遲相比較的查找延遲。可以用以下幾種方法進行尋路性能優(yōu)化。
2.1 多維坐標空間
改進尋路延遲的最簡單的方法是增加坐標空間的維數(shù)。平均路徑長度為O
(d ),假設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 )結構
設計多個獨立的坐標空間,系統(tǒng)中每個節(jié)點在不同的坐標空間中分配不同的區(qū)。假設將坐標空間稱為“實體”,因此對于有r 個實體的CAN ,每個節(jié)點將被分配r 個坐標區(qū),并且維護r 個獨立的鄰接表。
這樣,哈希表的內(nèi)容在每個實體上復制,提高了數(shù)據(jù)的可用性。例如,指向某個文件的指針存在坐標空間(x ,y ,z )中,對于四個實體的情況,指針會存在每個實體坐標空間(x ,y ,z )的四個不同的節(jié)點中,這樣,只有當四個節(jié)點都失效時,數(shù)據(jù)才不可用。多個實體也
6