On de Bruijn routing in distributed hash tables: there and back again
On de Bruijn routing in distributed hash tables: there and back again
复制标题
关于分布式哈希表中的 de Bruijn 路由：往返
DOI：
10.1109/ptp.2004.1334943
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
K. Aberer
中科院分区：
文献类型：
--
作者：
Anwitaman Datta;Sarunas Girdzijauskas;K. Aberer
在本文中，我们表明，德布鲁因网络，尽管提供了有效的搜索，同时使用恒定的路由表大小，以及简单的理解和实现这样的网络，是不适合的密钥分布将是不均匀的，最实际的应用程序的一个现实的情况。在存在任意偏斜的数据分布，它最近才被证明，一些传统的P2P覆盖网络与非常数（通常是对数），而不是恒定的路由表大小可以满足存储负载平衡以及搜索效率的冲突目标。因此，本文，虽然德布鲁因网络无法满足这些双重目标，开辟了一个更普遍的问题，研究界是否P2P系统与恒定的路由表可以在所有实现冲突的目标，保留搜索效率以及存储负载平衡，同时保持键排序（这导致不均匀的密钥分布）。
We show in this paper that de Bruijn networks, despite providing efficient search while using constant routing table size, as well as simplicity of the understanding and implementation of such networks, are unsuitable where key distribution will be uneven, a realistic scenario for most practical applications. In presence of arbitrarily skewed data distribution, it has only recently been shown that some traditional P2P overlay networks with non-constant (typically logarithmic) instead of constant routing table size can meet conflicting objectives of storage load balancing as well as search efficiency. So this paper, while showing that de Bruijn networks fail to meet these dual objectives, opens up a more general problem for the research community as to whether P2P systems with constant routing table can at all achieve the conflicting objectives of retaining search efficiency as well as storage load balancing, while preserving key ordering (which leads to uneven key distribution).