تعیین مکان منابع بر پایه گام های تصادفی نسبی در شبکه های پویا بصورت از پیش محاسبه شده

ABSTRACT Resource location based on precomputed partial random walks in dynamic networks

Random walks are network routing mechanisms which have been extensively studied and used in a wide range of applications: physics, mathematics, population dynamics, bioinformatics, etc. [11,18,24]. Roughly speaking, they choose, at each point of the route, the next node uniformly at random among the neighbors of the current node.

Among the advantages of random walks when applied to communication networks is the fact they need only local information, avoiding the bandwidth overhead necessary in other routing mechanisms to communicate with other nodes. This is especially useful when there is no knowledge on the structure of the whole network, or when the network structure changes frequently. For these reasons, random walks have been proposed as a base mechanism for multiple network applications, including network sampling [9,16], network resource location [1,10,28,33], network construction [5,15,19–21], and network characterization [8,29,32].

The emergence of the peer-to-peer (P2P) architecture model has been proven useful in many applications in recent years. While structured P2P systems (e.g., Chord [31], CAN [27] –ContentAddressable Network–, Kademlia [23], etc.) provide efficient search mechanisms, they introduce a significant management overhead.

In turn, unstructured systems have little management overhead and, consequently, have been considered in several scenarios (e.g., Gnutella [5,20], CAP [14] –Cluster-based Architecture for P2P–, etc.). For such systems, searching techniques based on flooding, supernodes and random walks have been used. However, it is known that flooding mechanisms do not scale well [13], and supernode systems are vulnerable to supernodes failures (technical problems, attacks, censorship, etc.). Therefore, random walks have been used to search for resources held in the nodes of a network (e.g., [5,22]), a problem usually known as resource location. The problem consists of finding a node that holds a given resource, the target node, starting at some source node. The source node is checked for the resource: if it is not found locally, the search hops to a random neighbor, checking that node for the resource. The search proceeds through the network in this way, until the target node is reached.

Nevertheless, by using random walks, some nodes may be (unnecessarily) visited more than once, while other nodes may remain unvisited for a long time. Avoiding this problem is the main objective of our study.