Michael Moore: mikemo@ics.uci.edu
Distributing network objects across a dynamic mobile environment produces the need for a mechanism that is capable of locating network objects (e.g. information, applications, and users). One potential method of discovering a network object is to have each network object contain links (also called relationships) to, and information about, several other network objects. As we explain below, this extra layer of links and information provides an adaptable, self-organizing and decentralized mechanism, addressing the issues of adaptability, robustness, and scalability in the dynamic mobile environment we consider.
Distributing network objects across the dynamic mobile environment considered in this proposal produces the need for a mechanism that is capable of locating network objects (e.g. information, applications, and users). One potential method of discovering a network object is to have each network object contain links (also called relationships) to, and information about, several other network objects, and to use the relationships and information effectively in discovering network objects. As we explain below, this extra layer of links and information provides an adaptable, self-organizing and decentralized mechanism, addressing the issues of adaptability, robustness, and scalability in the dynamic mobile environment we consider.
In the proposed discovery mechanisms, we assume that the discovery mechanisms abstract information, applications and users as network objects, located in the network. Each network object is capable of moving from one network node to another. Each network object also contains descriptive information about itself, such as keywords describing its content.
A relationship represents knowledge that a network object has about another network object. Each network object maintains a list of relationships to other network objects (relationship partners) and stores information about each of the network objects (e.g., keywords describing the network object, and location of the other network object) that it has relationships to. Relationships among network objects represent discovery-layer routing connectivity among network objects and provide a method to exchange discovery queries between network objects.
A network object may establish a relationship with another network object through actively searching for other network objects nearby, through introduction via other network objects, and passively through discovery related interactions. Actively searching for other network objects involves broadcasting an inquiry message using a mobile network node’s network connectivity to learn about nearby network objects. (Once a nearby network object is found, a relationship can be established.) Network objects with two or more relationship partners may introduce relationship partners to one another by having the relationship partners exchange information for establishing a relationship. Discovery related interactions occur when network objects communicate during the discovery process, and can be used to introduce other network objects. In this manner, relationships are built and adjusted to form a network of relationships over all network objects. As more relationships are acquired between the network objects, the relationships together form a network with various emergent properties. For example, this relationship network may contain redundant discovery routes for reaching a target network object or a target group of network objects, and thus, communication failure or network object loss is not likely to impact the reachability of network objects during discovery.
In this proposal, the relationship network is applied in two different discovery mechanisms. The first discovery mechanism supports the discovery of any relevant network object, whereas the second discovery mechanism supports the discovery of network objects that provide discovery hits more relevant and/or more preferred by discovery originators.
In the first discovery mechanism, we probe into understanding choices for the discovery mechanism and the impact of adaptability, robustness, and scalability. Our design of the first discovery mechanism addresses what properties to store in relationships and how to use the relationship properties in organizing the relationship network and in forwarding discovery queries. In this first discovery mechanism, we propose relationship properties that include keyword similarity and relationship history.
As described in E.1.1, relationships are acquired through several mechanisms. A network object applies localized policies to choose which network objects (from available network objects) to add to its relationships, forming an emergent relationship network.
One goal of the emergent relationship network is to form clustering in which network objects with similar keywords are nearby one another so that they can be reached in a small number of hops. Keyword similarity is defined as the ratio of keywords that are in common between a network object and its relationship partner, and is introduced as a clustering metric that measures how near two network objects should be in the relationship network.
Another goal of the emergent relationship network is to ensure that these clusters also contain a small number of relationships to some clusters containing objects with dissimilar keywords so that all clusters can reach all other clusters in a small number of hops, forming small-world clustering [Wat99].
An additional goal of the emergent relationship network is to filter relationships that have relatively weaker relationship history. Relationship history summarizes information about how a relationship partner has performed in past discoveries and is defined as the ration of successful discovery queries relative to all the discovery queries forwarded on the relationship. Maintaining relationships to network objects with stronger history ensures that relationship partners are more available, perform more reliable discovery, and return more relevant discovery hits (i.e. hits with more keywords that match the discovery query). In the first discovery mechanism, relationship history is weakened for network objects that provide no discovery hits to a discovery, and when history decreases below a certain threshold, the relationship is removed.
In the discovery query forwarding phase of the first discovery mechanism, keyword similarity and relationship history are used at each network object to determine which relationships have priority in forwarding discovery queries. Since network objects have relationships to network objects with similar keywords in the first discovery mechanism, locating one network object relevant (containing similar keywords) to a discovery query is likely to lead to many other network objects relevant (also containing similar keywords) to the discovery query. Relationship history records performance of past discoveries. A network object that has returned relevant discovery hits in the past is more likely to provide relevant discovery hits, and therefore, during discovery query forwarding, priority is given to relationships with relatively stronger history.
In the first discovery mechanism, keyword similarity is used as the primary guideline for forwarding discovery queries, and relationship history is used as the secondary guideline. Accordingly, discovery queries are forwarded to relationship partners that are most similar to the discovery, with relationship history being used to select between the relationship partners that are both equally similar to the discovery.
In addition to the use of keyword similarity and relationship history, the first discovery mechanism uses a timeout in discovery query forwarding. A network object may be waiting for discovery hits that are never received (e.g. as the result of object removal, incorrect information in discovery queries, or incorrect information in discovery hits), and thus a network object starts a timeout for each relationship that a discovery query is forwarded to. If the relationship partner does not respond before the timeout expires, the network object will try another relationship or return discovery hits if no other relationships are available for forwarding. The forwarding timeout ensures that discovery processing proceeds even when relationship partners do not respond as the result of removal from the network or incorrect information contained in discovery queries or discovery hits.
In the discovery hit backtracking phase, discovery hits are returned back towards the discovery originator along the path used for discovery query forwarding. During discovery hit backtracking, relationship history is updated based on the discovery hits a network object has received from a relationship partner. If a relationship partner is unavailable, then the history is weakened as if the relationship partner had returned no discovery hits. If a relationship partner cannot return discovery hits to a relationship partner (e.g. as the result of object removal, incorrect information in discovery queries), then the same timeout mechanism as used in discovery query forwarding ensures that discovery processing proceeds.
In the first discovery mechanism, discovery query forwarding may consume large amounts of resource if no bound is placed on the total amount of resource that discovery query forwarding and discovery hit backtracking may use. To bound the total amount of resource that discovery query forwarding and discovery hit backtracking may use, the discovery originator, in a discovery query, includes information about when discovery hits must be received.
Publications:
AINS Symposium
DARPA NGI bi-weekly reports:
report #2
report #8
report #10
Presentations:
MURI poster
Generic 5 minute version
Generic 15 minute version
Simulator Code:
Simulator source and compiled and configuration files
Database of generated simulation data (35 Mb)
Michael Moore: mikemo@ics.uci.edu
edited: Aug 2003