上海交通大学学报
上海交通大學學報
상해교통대학학보
JOURNAL OF SHANGHAI JIAOTONG UNIVERSITY
2004年
1期
75-78
,共4页
分布式网络%对等网络%查找%路由%非集中式算法
分佈式網絡%對等網絡%查找%路由%非集中式算法
분포식망락%대등망락%사조%로유%비집중식산법
提出了一种适用于对等网络环境的非集中式查找算法,它具有可扩展、自组织、高容错等特性,能够自动适应网络中节点的加入、退出和失效.该算法的时间复杂度和空间复杂度均为O(logN).算法的基本思想是:将有限大小的线性空间平均划分为M等份,对每等份的子空间递归划分为M等份,直到每个子空间对应一个点;采用Hash算法将网络中的数据或节点映射为线性空间中的一点,每个节点本地存储一个路由表,其内容为其各个划分层次中的对应点所在位置信息;这样,一个节点可以在不超过O(logN)次转跳的情况下找到目的节点.仿真实验结果表明:当M增大时,算法的查找性能也会提高;当M=16,网络规模为104个节点时,算法的平均查找长度仅是Pastry、Tapestry算法的70%左右.
提齣瞭一種適用于對等網絡環境的非集中式查找算法,它具有可擴展、自組織、高容錯等特性,能夠自動適應網絡中節點的加入、退齣和失效.該算法的時間複雜度和空間複雜度均為O(logN).算法的基本思想是:將有限大小的線性空間平均劃分為M等份,對每等份的子空間遞歸劃分為M等份,直到每箇子空間對應一箇點;採用Hash算法將網絡中的數據或節點映射為線性空間中的一點,每箇節點本地存儲一箇路由錶,其內容為其各箇劃分層次中的對應點所在位置信息;這樣,一箇節點可以在不超過O(logN)次轉跳的情況下找到目的節點.倣真實驗結果錶明:噹M增大時,算法的查找性能也會提高;噹M=16,網絡規模為104箇節點時,算法的平均查找長度僅是Pastry、Tapestry算法的70%左右.
제출료일충괄용우대등망락배경적비집중식사조산법,타구유가확전、자조직、고용착등특성,능구자동괄응망락중절점적가입、퇴출화실효.해산법적시간복잡도화공간복잡도균위O(logN).산법적기본사상시:장유한대소적선성공간평균화분위M등빈,대매등빈적자공간체귀화분위M등빈,직도매개자공간대응일개점;채용Hash산법장망락중적수거혹절점영사위선성공간중적일점,매개절점본지존저일개로유표,기내용위기각개화분층차중적대응점소재위치신식;저양,일개절점가이재불초과O(logN)차전도적정황하조도목적절점.방진실험결과표명:당M증대시,산법적사조성능야회제고;당M=16,망락규모위104개절점시,산법적평균사조장도부시Pastry、Tapestry산법적70%좌우.