Effectiveness of landmark analysis for establishing locality in p2p networks
Allan, A. and Di Fatta, G. (2010) Effectiveness of landmark analysis for establishing locality in p2p networks. In: The Second International Conference on Advances in P2P Systems (AP2PS 2010), 25-30 October 2010, Florence, Italy, pp. 88-92. (ISBN: 9781612081021)
Locality to other nodes on a peer-to-peer overlay network can be established by means of a set of landmarks shared among the participating nodes. Each node independently collects a set of latency measures to landmark nodes, which are used as a multi-dimensional feature vector. Each peer node uses the feature vector to generate a unique scalar index which is correlated to its topological locality. A popular dimensionality reduction technique is the space filling Hilbert’s curve, as it possesses good locality preserving properties. However, there exists little comparison between Hilbert’s curve and other techniques for dimensionality reduction. This work carries out a quantitative analysis of their properties. Linear and non-linear techniques for scaling the landmark vectors to a single dimension are investigated. Hilbert’s curve, Sammon’s mapping and Principal Component Analysis have been used to generate a 1d space with locality preserving properties. This work provides empirical evidence to support the use of Hilbert’s curve in the context of locality preservation when generating peer identifiers by means of landmark vector analysis. A comparative analysis is carried out with an artificial 2d network model and with a realistic network topology model with a typical power-law distribution of node connectivity in the Internet. Nearest neighbour analysis confirms Hilbert’s curve to be very effective in both artificial and realistic network topologies. Nevertheless, the results in the realistic network model show that there is scope for improvements and better techniques to preserve locality information are required.
 M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron, “Exploiting network proximity in peer-to-peer overlay networks,” Microsoft Research, Cambridge, England, Tech. Rep. MSR-TR-2002-82, May 2002.  S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, “Topologically aware overlay construction and server selection,” in Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings, New York, USA, Jun. 2002, pp. 1190–1199.  Y. Zhu and Y. Hu, “Towards efficient load balancing in structured p2p systems,” in 18th International Parallel and Distributed Processing Symposium (IPDPS’04), Santa Fe, USA, Apr. 2004, p. 20a.  H. Shen and C. Xu, “Hash-based proximity clustering for load balancing in heterogeneous dht networks,” Journal of Parallel and Distributed Computing, vol. 65, no. 5, pp. 686–702, May 2005.  Z. Xu, C. Tang, and Z. Zhang, “Building topology-aware overlays using global soft-state,” in Proceedings of the 23rd International Conference on Distributed Computing Systems, Brown University, USA, May 2003, pp. 500–508.  Z. Xu, M. Mahalingam, and M. Karlsson, “Turning heterogenity into an advantage in overlay routing,” in Proceedings of IEEE INFOCOM, San Francisco, USA, Mar. 2003, pp. 1499 – 1509.  C. Gotsman and M. Lindenbaum, “On the metric properties of discrete space-filling curves,” IEEE Transactions on Image Processing, vol. 5, no. 1, pp. 794–797, Jan. 1996.  B. Moon, H. Jagadish, C. Faloutsos, and J. Saltz, “Analysis of the clustering properties of the hilbert space-filling curve,” IEEE Transactions on Knowledge and Data Engineering, vol. 13, no. 1, pp. 124–141, Jan. 2001.  J. Alber and R. Niedermeier, “On multi-dimensional hilbert indexings,” in Computing and Combinatorics: 4th Annual International Conference, Proceedings, Taipei, Taiwan, Aug. 1998, pp. 329–338.  R. Niedermeier, K. Reinhardt, and P. Sanders, “Towards optimal locality in mesh-indexings,” in Proceedings of the 11th International Symposium on Fundamentals of Computation Theory, Krakow, Poland, Sep. 1997, pp. 364 – 375.  M. A. Carreira-Perpinan, “A review of dimension reduction techniques,” Department of Computer Science, University of Sheffield, U.K., Tech. Rep. CS-96-09, 1997.  I. K. Fodor, “A survey of dimension reduction techniques,” Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA, Tech. Rep. UCRL-ID-148494, 2002.  P. Diaconis and M. Shahshahani, “On nonlinear functions of linear combinations,” SIAM Journal on Scientific and Statistical Computing, vol. 5, pp. 175–191, Mar. 1984.  G. Eslava and F. H. C. Marriott, “Some criteria for projection pursuit,” Statistics and Computing, vol. 4, no. 1, pp. 13–20, Mar. 1994.  I. Jolliffe, Principal Component Analysis, 2nd ed., ser. Springer Series in Statistics. New York, USA: Springer, 2002, no. XXIX.  J. W. Sammon, “A nonlinear mapping for data structure analysis,” IEEE Transactions on Computers, vol. C-18, no. 5, pp. 401–409, May 1969.  G. Peano, “Sur une courbe, qui remplit toute une aire plane,” Mathematische Annalen, vol. 36, no. 1, pp. 157–460, 1890.  A. R. Butz, “Space filling curves and mathematical programming,” Information and Control, vol. 12, pp. 314–330, 1968.  D. Hilbert, “Ueber die stetige abbildung einer line auf ein flchenstck,” Mathematische Annalen, vol. 38, pp. 459–460, 1891.  C. Faloutsos and Y. Rong, “Spatial access methods using fractals: Algorithms and performance evaluation,” University of Maryland, Maryland, USA, Tech. Rep. UMIACS-TR-89-31, Mar. 1989.  H. Jagadish, “Linear clustering of objects with multiple attributes,” ACM SIGMOD Record, vol. 19, no. 2, pp. 332–342, Jun. 1990.  K. Pearson, “On lines and planes of closest fit to systems of points in space,” Philosophical Magazine, vol. 2, no. 6, pp. 559–572, Jun. 1901.  D. Marghescu, “Evaluating the effectiveness of projection techniques in visual data mining,” in Proceedings of the Sixth IASTED International Conference on Visualization, Imaging, And Image Processing, Palma de Mallorca, Spain, Aug. 2006, pp. 186–193.  A. Butz, “Alternative algorithm for hilbert’s space-filling curve,” IEEE Transactions on Computers, vol. 20, no. 4, pp. 424–426, Apr. 1971.  D. Moore. Fast hilbert curve generation and sorting and range queries. Rice University. Texas, USA. [Online]. Available: http://www.tiac.net/∼sw/2008/10/Hilbert/moore/hilbert.c (last accessed: June 2010)  M. Berthold, N. Cebron, F. Dill, G. Di Fatta, T. Gabriel, F. Georg, T. Meinl, P. Ohl, C. Sieb, and B. Wiswedel, “KNIME: The Konstanz Information Miner,” in Proceedings of the Workshop on Multi-Agent Systems and Simulation MAS&S, 4th Annual Industrial Simulation Conference (ISC), Palermo, Italy, Jun. 2006, pp. 58–61.  J. Winick and S. Jamin, “Inet-3.0: Internet topology generator,” University of Michigan, Michigan, USA, Tech. Rep. CSE-TR-456-02, Jun. 2002.  G. Di Fatta, G. L. Presti, and G. L. Re, “Computer network topologies: Models and generation tools,” Consiglio Nazionale delle Ricerche, Palermo, Italy, Tech. Rep. CERE-CNR, 5/2001, Jul. 2001.  B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman, “Planetlab: an overlay testbed for broad-coverage services,” IEEE Transactions on Computers, vol. 33, no. 3, pp. 3–12, Jul. 2003.
Centaur Editors: Update this record