LOBS: Load Balancing for Similarity Peer-to-Peer Structures

NOVÁK, David and Pavel ZEZULA. LOBS: Load Balancing for Similarity Peer-to-Peer Structures. Brno, Czech Republic: Faculty of Informatics, Masaryk University, 2007. Technical report FIMU-RS-2007-04.

Basic information

• Original name: LOBS: Load Balancing for Similarity Peer-to-Peer Structures
• Name in Czech: LOBS: Vyrovnávání zátěže pro podobnostní peer-to-peer struktury
• Authors: NOVÁK, David (203 Czech Republic, guarantor, belonging to the institution) and Pavel ZEZULA (203 Czech Republic).
• Edition: Brno, Czech Republic, Technical report FIMU-RS-2007-04, 2007.
• Publisher: Faculty of Informatics, Masaryk University

Other information

• Original language: English
• Type of outcome: Audiovisual works
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Czech Republic
• Confidentiality degree: is not subject to a state or trade secret
• WWW: PDF file
• RIV identification code: RIV/00216224:14330/07:00019433
• Organization unit: Faculty of Informatics
• Keywords in English: peer-to-peer; load-balancing; similarity search
• Tags: DISA, load-balancing, Peer-to-Peer, similarity search
• Tags: International impact

Abstract

The real-life experience with the similarity search shows that this task is both difficult and very expensive in terms of processing time. The peer-to-peer structures seem to be a suitable solution for content-based retrieval in huge data collections. In these systems, the computational load generated by a query traffic is highly skewed which degrades the searching performance. Since no current load-balancing techniques are designed for this task, we propose LOBS -- a novel and general system for load-balancing in peer-to-peer structures with time-consuming searching. LOBS is based on the following principles: measuring the computational load of the peers, separation of the logical and the physical level of the system, and detailed analysis of the load source to exploit either data relocation or data replication. This report contains detailed description of the fundamentals and specific algorithms of LOBS, a theoretical analysis of its behaviour, and results of extensive experiments we conducted using a prototype implementation of LOBS. We tested LOBS with the peer-to-peer structure M-Chord having a various number of peers. We used a real-life dataset and query sets of various distributions. The results show that LOBS is able to cope with any query-distribution and that it improves both the utilization of resources and the system performance of query processing. The costs of balancing are reasonable compared to the level of imbalance and are very small if the system has time to adapt to a query-traffic. The behaviour of LOBS is independent of the size of the network.

Abstract (in Czech)

Zpráva obsahuje popis obecného systému pro vyrovnávání zátěže ve strukturovaných peer-to-peer sítích pro časově náročné vyhledávání. Dále také výsledky experimentů aplikujících systém na strukturu M-Chord.

Links

• GD102/05/H050, research and development project: Name: Integrovaný přístup k výchově studentů DSP v oblasti paralelních a distribuovaných systémů

Investor: Czech Science Foundation, Integrated approach to education of PhD students in the area of parallel and distributed systems

• 1ET100300419, research and development project: Name: Inteligentní modely, algoritmy, metody a nástroje pro vytváření sémantického webu

Investor: Academy of Sciences of the Czech Republic, Intelligent Models, Algorithms, Methods and Tools for the Semantic Web (realization)