Virtual Ring Routing Trends
Virtual Ring Routing Trends
复制标题
虚拟环路由趋势
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Udi Wieder
中科院分区：
文献类型：
--
作者：
D. Malkhi;S. Sen;Kunal Talwar;Renato F. Werneck;Udi Wieder
虚拟环路由（VRR）方案是在无线自组织网络和互联网任播覆盖的背景下引入的。他们使用分布式哈希表设计的思想构建了一个网络路由层，利用沿着一个环的随机虚拟身份。这使得在节点可能进入或离开时维护变得实用。
此前，VRR在小型无线网络上进行了评估，并通过中等规模的模拟，表现出非常好的性能。在本文中，我们提供了一个正式的分析，一个家庭的VRRlike计划。该分析提供了对各种问题的深入了解，例如，与暴力最短路径路由相比，VRR的性能如何？底层网络拓扑的哪些属性使VRR工作良好？
我们的分析是支持广泛的模拟在各种拓扑结构。而以前的作品评估VRR在相当小的网络（高达200个节点），我们有兴趣在缩放模拟，以表现出渐近趋势。模拟超过220的网络大小会导致内存爆炸：在某些感兴趣的拓扑中，例如二维平面，对于N节点网络，路由表占用的总内存为Ω（N3/2）。我们设计了一个模拟策略，建立必要的信息上飞使用吕比和Rackoff伪随机置换，导致模拟规模为232个节点。
Virtual Ring Routing (VRR) schemes were introduced in the context of wireless ad hoc networks and Internet anycast overlays. They build a network-routing layer using ideas from distributed hash table design, utilizing randomized virtual identities along a ring. This makes maintenance practical when nodes may enter or leave.
Previously, VRR was evaluated over a small wireless network and through medium-scale simulations, exhibiting remarkably good performance. In this paper, we provide a formal analysis of a family of VRRlike schemes. The analysis provides insight into a variety of issues, e.g., how well does VRR perform compared with brute force shortest paths routing? What properties of an underlying network topology make VRR work well?
Our analysis is backed by extensive simulation over a variety of topologies. Whereas previous works evaluated VRR over fairly small networks (up to 200 nodes), we are interested in scaling the simulations so as to exhibit asymptotic trends. Simulating network sizes beyond 220 results in a memory explosion: In some of the topologies of interest, such as a 2-dimensional plane, the total memory taken up by routing tables is Ω(N3/2) for an N-node network. We devise a simulation strategy that builds necessary information on the fly using a Luby and Rackoff pseudo-random permutation, leading to simulations at a scale of 232 nodes.