| Lower Bound on de Bruijn Graphs Out-degree for Lower Traffic Load in Peer-to-peer Networks |
| |
| 作者姓名： | 王凯 左敏 潘理 李建华 |
| |
| 作者单位： | Department of Electronic Engineering, Shanghai Jiaotong University, Shanghai 200240 |
| |
| 摘 要： | Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase. Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O（1） but should satisfy a lower bound described by an inequality κ^κ≥N^2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system.
|
| 关 键 词： | de Bruijn图 流量负载 平均载荷 平均距离 |
| 收稿时间： | 2005-05-09 |
Lower Bound on de Bruijn Graphs Out-degree for Lower Traffic Load in Peer-to-peer Networks |
| |
| WANG Kai,ZUO Min,PAN Li,LI Jian-hua.Lower Bound on de Bruijn Graphs Out-degree for Lower Traffic Load in Peer-to-peer Networks[J].Journal of Donghua University,2006,23(2):99-102. |
| |
| Authors: | WANG Kai ZUO Min PAN Li LI Jian-hua |
| |
| Abstract: | Designers search for N-nodes peer-to-peer networks that can have O(1) out-degree with O(log2 N) average distance.Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase.Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O(1) but should satisfy a lower bound described by an inequality kk≥ N2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system. |
| |
| Keywords: | Peer-to-peer de Bruijn graphs traffic load average load out-degree average distance |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
