Home // AP2PS 2011, The Third International Conference on Advances in P2P Systems // View article

Virtual Landmarking for Locality Aware Peer IDs

Authors:
Alexander Allan
James Bradbury
Giuseppe Di Fatta

Keywords: Peer-to-Peer Networks; Hilbert Curve; Landmark Multidimensional Scaling; Virtual Landmarks; Network Coordinates

Abstract:
In Peer-to-Peer (P2P) networks, it is often desirable to assign node IDs which preserve locality relationships in the underlying topology. Node locality can be embedded into node IDs by utilizing a one dimensional mapping by a Hilbert space filling curve on a vector of network distances from each node to a subset of reference landmark nodes within the network. However this approach is fundamentally limited because while robustness and accuracy might be expected to improve with the number of landmarks, the effectiveness of 1 dimensional Hilbert Curve mapping falls for the curse of dimensionality. This work proposes an approach to solve this issue using Landmark Multidimensional Scaling (LMDS) to reduce a large set of landmarks to a smaller set of virtual landmarks. This smaller set of landmarks has been postulated to represent the intrinsic dimensionality of the network space and therefore a space filling curve applied to these virtual landmarks is expected to produce a better mapping of the node ID space. The proposed approach, the Virtual Landmarks Hilbert Curve (VLHC), is particularly suitable for decentralised systems like P2P networks. In the experimental simulations the effectiveness of the methods is measured by means of the locality preservation derived from node IDs in terms of latency to nearest neighbours. A variety of realistic network topologies are simulated and this work provides strong evidence to suggest that VLHC performs better than either Hilbert Curves or LMDS use independently of each other.

Pages: 7 to 12

Copyright: Copyright (c) IARIA, 2011

Publication date: November 20, 2011

Published in: conference

ISBN: 978-1-61208-173-1

Location: Lisbon, Portugal

Dates: from November 20, 2011 to November 25, 2011