Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2009 | DISC | simulating network size,underlying network,vrr work,medium-scale simulation,small wireless network,extensive simulation,virtual ring,small network,memory explosion,formal analysis,n-node network,2 dimensional,network routing,distributed hash table,wireless ad hoc network,random permutation,network topology,wireless network |
Field | DocType | Volume |
Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Computer network,Destination-Sequenced Distance Vector routing,Wireless Routing Protocol,Optimized Link State Routing Protocol,Wireless ad hoc network,Routing table,Distributed computing | Conference | 5805 |
ISSN | ISBN | Citations |
0302-9743 | 3-642-04354-2 | 1 |
PageRank | References | Authors |
0.35 | 12 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dahlia Malkhi | 1 | 2692 | 185.55 |
| Siddhartha Sen | 2 | 312 | 35.46 |
| Kunal Talwar | 3 | 4423 | 259.79 |
| Renato F. Werneck | 4 | 1743 | 84.33 |
| Udi Wieder | 5 | 1043 | 64.32 |