Evaluation of dynamic query abolishment methods in heterogeneous networks
Elena Meshkova, Janne Riihijärvi, Petri Mähönen · RWTH Publications (RWTH Aachen) · 2006
We compare the performance of various dynamic query abolishment mechanisms in different unstructured overlay network topologies such as found in several P2P systems. We specifically focus on techniques based on iterative deepening and checking. Both unintelligent and intelligent variants of the methods are used in the study. Additionally, we propose a new mechanism called the chasing wave based on the use of increasing delays for search packets on the forwarding nodes. We show that the proposed chasing wave algorithm trades effectively the increase in propagation delay to substantially lower overhead. The performance of the methods are compared in several network configurations and using several metrics. We make concrete proposals on the suitability of the specific dynamic query abolishment methods for different search algorithms. I. INTRODUCTION Service discovery systems have become increasingly im- portant and popular in the last years. Among them are the systems built on top of unstructured overlays, such as un- structured Peer-to-Peer (P2P) systems, that have gained more and more attention due to their resistance to node failures and malicious attacks. Unstructured P2P systems also support partial-matched queries, which allows them to solve in a sense loosely formulated queries. Of course, P2P networks are not anymore confined to the research domain, as millions of people use these systems every day. This proliferation of P2P traffic has also created the need to consider the overhead introduced by search and discovery protocols. The main challenge for unstructured overlays is scalability, i.e. without imposing additional hierarchy on the network (like clustering in KaZaA (1)) it is difficult to support more than some thousands of nodes. There are basically two ways to reduce the imposed search overhead. Either one creates very precise search algorithms carefully designed to be bandwidth- efficient (2), or uses dynamic query abolishment methods (DQAM) to stop search packet propagation after the query answered. The combination of the above two methods can be very efficient (3). We will also introduce some adaptive techniques to help DQAMs to adapt to changes in the network. In our study we focus on both adaptive (or intelligent) DQAM methods, as well as their unmodified variants. These can be used with virtually any search technique. An appro- priately chosen DQAM can further improve the performance of almost any search protocol. We conduct simulations and provide detailed results for nine different protocol combina- tions: flooding, random walk (RW), iterative deepening (ITD), adaptive iterative deepening (AITD), adaptive iterative deepen- ing with RTT limit (AITD-RTT), checking, adaptive checking (ACHK), the chasing wave (CHW) and the adaptive chasing wave (ACHW). The last two are new query abolishment techniques introduced later in this paper. The rest of the paper is structured as follows. In the next section we present the methods studied in more detail. In Section III we shortly describe the chasing wave. The simulation environment and set-up are given in Section IV. Section V provides the results obtained together with the associated discussion, and the conclusions are finally drawn in Section VI.