Small-World Networks: From Theoretical Bounds to Practical Systems
Small-World Networks: From Theoretical Bounds to Practical Systems
复制标题
小世界网络：从理论界限到实际系统
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Raynal
中科院分区：
文献类型：
--
作者：
François Bonnet;Anne;M. Raynal
在小世界网络中，每个节点都连接到网络拓扑中最近的邻居，以及额外的长距离联系人，也称为捷径。在2000年，Kleinberg给出了路由性能的渐近下界，并证明了当到捷径的距离是随机均匀选择时，n个节点的小世界网络中的贪婪路由性能为Ω（n1/3）步，而当到捷径的距离是根据d维网格中的谐波分布选择时，贪婪路由性能为Θ（log 2 n）步。然而，我们通过实验结果观察到，对等的八卦为基础的协议实现小世界拓扑的捷径是随机选择的，在实践中表现相当不错。
Kleinberg的结果是相关的非常大的系统，而在实践中考虑的系统通常是较小的规模（他们通常是由不到一百万的同行）。本文探讨了Kleinberg结果在实际系统和小世界网络中的影响。更确切地说，基于这样的观察，尽管基于流言的小世界覆盖网络的路由复杂度不是多对数的（如Kleinberg所证明的），但这种类型的网络最终在实践中提供了合理的结果。这使我们认为，仅凭渐近大O（）复杂度可能并不总是足以评估一个系统的实用性，该系统的大小通常小于一个理论的目标。因此，本文提出了一种改进的小世界网络的路由复杂性度量（即，一个递归公式，可以很容易地计算）。然而，由于Kleinberg证明了捷径的分布对路由复杂性有很大的影响（当考虑非常大的网络时），因此出现了利用这一结果来改进当前基于流言的协议的问题。我们表明，基于流言的协议（设计少于一百万的同行）可以受益于一个很好的近似Kleinberg的小世界拓扑结构（设计用于非常大的网络）。沿着，提出了仿真结果，证明了所提出的方法的相关性。
In small-world networks, each peer is connected to its closest neighbors in the network topology, as well as to additional long-range contact(s), also called shortcut(s). In 2000, Kleinberg provided asymptotic lower bounds on routing performances and showed that greedy routing in an n-peer small-world network performs in Ω(n1/3) steps when the distance to shortcuts is chosen uniformly at random, and in Θ(log2 n) when the distance to shortcuts is chosen according to a harmonic distribution in a d-dimensional mesh. Yet, we observe through experimental results that peer to peer gossip-based protocols achieving small-world topologies where shortcuts are randomly chosen, perform reasonably well in practice.
Kleinberg results are relevant for extremely large systems while systems considered in practice are usually of smaller size (they are typically made up of less than one million of peers). This paper explores the impact of Kleinberg results in the context of practical systems and small-world networks. More precisely, based on the observation that, despite the fact that the routing complexity of gossipbased small-world overlay networks is not polylogarithmic (as proved by Kleinberg), this type of networks ultimately provide reasonable results in practice. This leads us to think that the asymptotic big O() complexity alone might not always be sufficient to assess the practicality of a system whose size is typically smaller that what the one theory targets. The paper consequently proposes a refined routing complexity measure for small-world networks (namely, a recurrence formula that can be easily computed). Yet, given that Kleinberg proved that the distribution of shortcuts has a strong impact on the routing complexity (when extremely large networks are considered), arises the question of leveraging this result to improve upon current gossip-based protocols. We show that gossip-based protocols (designed for less than one million of peers) can benefit from a good approximation of Kleinberg-like small-world topologies (designed for extremely large networks). Along, are presented simulation results that demonstrate the relevance of the proposed approach.