Distributed Discovery Using Preference for Query Hits

Distributed discovery using preference for query hits

Distributed discovery using preference for query hits

We propose another discovery mechanism that guides discovery queries using the preference of discovery hits by discovery originators. In the proposed discovery mechanism, each of the relationships of a network object contains the keyword(s) of its relationship. Each keyword is associated with the keyword strength, which indicates the usefulness of the relationship in discovering a network object that both contains the keyword and is considered preferable by the discovery originator. In the proposed discovery mechanism, relationships contain keywords of network objects that the relationship partner knows about (in addition to the keywords of the relationship partner), unlike the other discovery mechanism where relationships only contain the keywords of the relationship partner. Since they include not only the keywords of the relationship partner, but also the keywords of the network objects that are accessible/reachable through the relationship, keywords of a relationship may change representing other preferable network objects that the relationship partner can reach through relationships. The proposed discovery mechanism includes a rewarding phase that allows a discovery originator to return the degree of its preference of a received discovery hit to the network objects that participated in locating a target network object. During the rewarding phase, keyword strengths of relationships used to forward the discovery query to the network object returned as a discovery hit are adjusted based on the degree of a discovery originator's preference of the received discovery hit as explained below. Thus, through many discovery iterations, keyword strengths of relationships reflect the general preference of discovery hits. Keyword strengths of relationships are used in subsequent discoveries to guide discovery queries so that the discovery can return more preferable discovery hits. Each phase of the proposed discovery mechanism (discovery query forwarding, discovery hit backtracking and rewarding) is described below.
Discovery Query Forwarding
As described above, each relationship is associated with keywords, and each keyword has a corresponding strength value that represents the usefulness of the relationship through which a discovery originator locates a preferred network object that contains the keyword. In the proposed discovery mechanism, upon receiving a discovery query, a network object probabilistically forwards a discovery query to a relationship partner in proportion to the keyword strength. Thus, a discovery query is more likely to be forwarded to a relationship partner with larger keyword strength, while a relationship with smaller keyword strength is less likely to be chosen.
Discovery Hit Backtracking
In the discovery hit backtracking phase, discovery hits are returned back towards the discovery originator along the path used for discovery query forwarding.
Rewarding
Upon receiving a discovery hit, a discovery originator returns a reward message indicating the degree of its preference of the received discovery hit. A reward message is propagated through the same path where the discovery query was originally forwarded. When an intermediate network object on the path receives a reward message, it adjusts the keyword strength of the relationship which was used to forward the original discovery query. The keyword strength is increased for a positive reward (i.e., high degree of the discovery originator's preference), and is decreased for a negative reward (i.e., low degree of the discovery originator's preference). If the relationship does not contain the corresponding keyword, the keyword and the initial keyword strength is added to the relationship.
Addressing of Adaptability, Robustness and Scalability Issues
The following discussion describes the features of the proposed discovery mechanism that address the issues related to adaptability, robustness, and scalability of a mobile environment. The proposed discovery mechanism adapts to a dynamically changing network environment by probabilistically forwarding a discovery query. In the mobile environment, network objects may dynamically move or become unavailable either temporarily or permanently due to removal or powering-off of a network node. New objects may also be introduced into the network. In the proposed discovery mechanism, even when intermediate network objects with high keyword strength move or become unavailable, it is still possible to probabilistically forward a discovery query to a relationship with small keyword strength and eventually to a preferred network object, allowing the small keyword strength to increase. Issues related to the robustness of discovery in the environment considered in this proposal include robustness to incorrect information during discovery query forwarding and discovery hit backtracking. Through adjusting keyword strengths based on a discovery originator's preference of the received discovery hit, the proposed discovery mechanism avoids returning irrelevant discovery hits and also prevents forwarding a discovery query to network objects that provide incorrect information. Since keyword strength guides a discovery query to be forwarded to the network objects that are preferred by many other discovery originators, the proposed discovery mechanism avoids returning the discovery hits containing less preferred information. In addition, the proposed discovery mechanism reduces keyword strengths of the relationships that lead to network objects that provide incorrect information, and thus it is unlikely to forward discovery queries to network object that provide incorrect information. Issues related to the scalability of discovery in the environment considered in this proposal include limiting the number of discovery queries generated. The proposed discovery mechanism addresses this issue by probabilistically forwarding a discovery query based on keyword strengths. In the proposed discovery mechanism, network objects probabilistically choose useful relationships to forward a discovery query based on keyword strengths, therefore the total number of discovery queries generated is limited.

Simulator of Distributed discovery using preference for query hits

Distributed discovery simulator ver1.0

You can also find several papers about Distributed discovery usign preference for query hits at publications page.

Network Research Group
Dept. of Information and Computer Science
University of California, Irvine