|
Peer-to-Peer
Discovery |
|
[Home | Research | Publications | Resources | People | Undergraduate Research Opportunities | Related Sites/Papers] |
The dynamic and ad-hoc network produces the need for a method to search for network objects (data, applications, and users). The discovery mechanism is targeted at providing a method to locate objects in a network, while remaining decentralized and adaptive to the network environment. One potential method of searching for 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 such links and information effectively in searching for network objects. As we explain below, this extra layer of links and information provides a highly decentralized mechanism to discover other network objects and yet remain adaptive to a dynamic network environment. We are investigating and developing the following key mechanisms:
Relationships
In the proposed discovery mechanism, we assume that the
discovery mechanism abstracts data, applications and users as network objects,
locatable on the network. Each network object is created with a globally unique
identifier (GUID) and is capable of moving from one network node to another.
Each network object also contains descriptive information about itself, such as
information describing whether it is data or an application. Some objects may
have additional information. For example, an application may provide its type
of service or additional keywords describing the service. Keywords allow
searches to distinguish between applications of the same type.
In the proposed discovery mechanism, each network
object has a list of relationships to other network objects. A network object
has a relationship with another network object when it knows about the other
network object (i.e., when it knows the identifier, address and location of the
other network object). A relationship may also contain descriptive information
about the network object that it knows.
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 through
discovery-related interactions. Actively searching for other network objects
involves broadcasting an inquiry message using the network?s node level connectivity to learn about nearby
network objects. (Once a nearby network object is found, a relationship can be
established.) A network object can introduce two network objects that it has
relationships with to each other by having one network object
pass knowledge about itself to the other network object. Discovery
related interactions occur when network objects communicate during the
discovery process, and can be used to introduce other network objects. Through
these mechanisms a set of relationships is built and adjusted to form a network
of relationship over all network objects.
Using relationships among network objects provides an
adaptive and decentralized mechanism for searches .
Searches originate from a network object and travel from object to object based
upon relationships. Even when network objects migrate, relationships are
maintained, as network objects are aware of which other network objects they
have relationships with, and the migrating object can update the other objects?
relationships when it changes location on the network.
This provides a robust environment for the movement of network objects. Since
each network object only uses its own relationships to perform searches, the
search method based on relationships is entirely decentralized.
Search Forwarding
A search request contains parameters indicating the
type of search, namely, if a search is for a particular network object, for a
certain class of network objects (such as certain types of applications), or
perhaps for network objects (data) related to some topic [HKB99]. When a
network object receives a search request, it first compares itself to the
search, and if it matches, it responds to the search. When the network object
itself does not satisfy the search, it uses its relationships to forward the
search request to other network objects. Searching is improved by using the
additional relationship information (i.e., descriptive information about other
network objects such as service type and keywords). Based on the parameters of
the search and the descriptive information contained in a relationship, a
decision can be made regarding which relationship is more likely to lead
towards a network object that meets the search parameters, and a search request
may only be forwarded to such network objects. (The other relationships can be
tried after these likely network objects have been tried.)
The network object may forward a search request in a
sequential manner, trying a new network object after the search based on a
network object failed, or in parallel to more than one network object at a
time. Sequential searching minimizes the overhead due to search request
packets, whereas a parallel search minimizes the amount of time required to
find the network object(s) being sought for [PGHRRGKP98]. The overall search
process can be limited by hop count (of the path that a search request takes),
search time, or by path cost.
Search
Backtracking
The network object that matches a given search request
may respond either directly back to the origin of the search, or back through
the chain of network objects that a search request followed to the match
(backtracking). To respond directly to the origin, the search request must
include the network address of the search origin. Response through backtracking the chain of network objects leading to the
match provides a certain amount of anonymity. Anonymity results since the
matching network object does not have any information about the origin. Note
that the address of the search origin is not required in a search request in
backtracking. Instead, the search origin assigns a globally unique identifier
(GUID) to a search request, and each forwarding network object records the GUID
of the search request it receives, from which node the search request came, and
to which node the search request was forwarded. Once the network object that
matches the search is found, the information stored at each relationship hop
has adequate information to backtrack through the path of network objects
leading to the matching network object.
Some of the key research issues to be addressed in our
project are listed below:
Efficiency: The proposed discovery mechanism produces a
certain amount of overhead. Overhead takes the form of data storage for
relationships, processing to prioritize relationships in search, and network
usage to propagate search requests. An additional overhead is also required to
establish the network of relationships among network objects. In the proposed
project, we investigate efficiency of the proposed discovery mechanism through
extensive simulations.
Scalability: Scalability in networking environments deals with concerns that arise when certain parameters of the network increase; the number of network nodes, the network usage, the number of users, the number of applications, or the amount of data. In the proposed project, we investigate the scalability of the proposed discovery mechanism through simulations where these network parameters are varied.
Adaptability: In assumed dynamic network environments, losses
of network nodes or objects may affect the properties of the proposed discovery
mechanism. In the proposed project, we take into consideration the dynamic
nature of the environment (e.g., movement of network objects) and investigate
adaptability of the proposed discovery mechanisms to network dynamics through
simulations.
Usability: The proposed discovery mechanism is useful
if it returns meaningful results within an acceptable amount of time. The
dynamic environment (where network objects migrate) also adds the need for the
search to find network objects that are relatively close to the user. An
additional usability concern is related to how the discovery mechanism performs
when no matches to a search exist. In the proposed project, we consider these
usability factors and investigate the quality of search results returned by the
proposed discovery mechanism.
We have developed two distinct discovery mechanisms.
This research is supported by the NSF through grants ANI-0083074, ANI-9903427 and ANI-0508506, by DARPA through grant MDA972-99-1-0007, by AFOSR through grant MURI F49620-00-1-0330, and by grants from the California MICRO and CoRe programs, Hitachi, Hitachi America, Hitachi CRL, Hitachi SDL, DENSO IT Laboratory, NICT (National Institute of Communication Technology, Japan), Nippon Telegraph and Telephone (NTT), NTT Docomo, NS Solutions Corporation, Fujitsu and Novell.