home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Internet Info 1997 December
/
Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso
/
drafts
/
draft_ietf_i
/
draft-ietf-ids-inp-00.txt
< prev
next >
Wrap
Text File
|
1996-09-25
|
34KB
|
783 lines
INTERNET-DRAFT Joann J. Ordille
draft-ietf-ids-inp-00.txt Bell Labs, Lucent Technologies
Expires in six months
Internet Nomenclator Project
Filename: draft-ietf-ids-inp-00.txt
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups. Note that other groups may also
distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-
Drafts as reference material or to cite them other than as ``work
in progress.''
To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the Internet-
Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net
(Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East
Coast), or ftp.isi.edu (US West Coast).
Abstract
The goal of the Internet Nomenclator Project is to integrate the
hundreds of publicly available CCSO servers from around the world.
Each CCSO server has a database schema that is tailored to the needs
of the organization that owns it. The project is integrating the
different database schema into one query service. The Internet
Nomenclator Project will provide fast cross-server searches for
locating people on the Internet. It augments existing CCSO services
by supplying schema integration, more extensive indexing, and two
kinds of caching -- all this in a system that scales as the number
of CCSO servers grows. One of the best things about the system is
that administrators can incorporate their CCSO servers into
Nomenclator without changing the servers. All Nomenclator needs is
basic information about the server.
This document provides an overview of the Nomenclator system,
describes how to register a CCSO server in the Internet Nomenclator
Project, and how to use the Nomenclator search engine to find people
[Page 1]
INTERNET-DRAFT September 1996
on the Internet.
Distribution of this document is unlimited. Comments should be sent
to the author.
1. Introduction
Hundreds of organizations provide directory information through the
CCSO name service protocol [3]. Although the organizations provide a
wealth of information about people, finding any one person can be
difficult because each organization's server is independent. The
different servers have different database schemas (attribute names
and data formats). The 300+ CCSO servers have more than 900
different attributes to describe information about people. Very few
common attributes exist. Only name and email occur in more than 90%
of the servers [4]. No special support exists for cross-server
searches, so searching can be slow and expensive.
The goal of the Internet Nomenclator Project is to provide fast,
integrated access to the information in the CCSO servers. The
project is the first large-scale use of the Nomenclator system.
Nomenclator is a more general system than a white pages directory
service. It is a scalable, extensible information system for the
Internet.
Nomenclator answers descriptive (i.e. relational) queries. Users
can locate information about people, organizations, hosts, services,
publications, and other objects by describing their attributes.
Nomenclator achieves fast descriptive query processing through an
active catalog, and extensive meta-data and data caching. The
active catalog constrains the search space for a query by returning
a list of data repositories where the answer to the query is likely
to be found. Meta-data and data caching keep frequently used query
processing resources close to the user, thus reducing communication
and processing cause.
Through the Internet Nomenclator Project, users can query any CCSO
server, regardless of its attribute names or data formats, by
specifying the query to Nomenclator. Nomenclator provides a world
view of the data in the different servers. Users express their
queries in this world view. Nomenclator returns the answer
immediately if it has been cached by a previous query. If not,
Nomenclator uses its active catalog to constrain the query to the
subset of relevant CCSO servers. The speed of the query is
increased, because only relevant servers are contacted. Nomenclator
translates the global query into local queries for each relevant
CCSO server. It then translates the responses into the format of
the world view. See Figure 1.
[Page 2]
INTERNET-DRAFT September 1996
--------------------------------------------------------------------
+-------------+ +-------------+
| | | |
World View | | Local View | |
Query | | Query | Relevant |
----------->| |------------>| |
| Nomenclator | | CCSO |
| | | |
<-----------| |<------------| Server |
World View | | Local View | |
Response | | Response | |
+-------------+ +-------------+
Figure 1: A Nomenclator Query
Nomenclator translates queries to and from
the language of the relevant CCSO servers.
--------------------------------------------------------------------
The Internet Nomenclator Project makes it easier for users to find a
CCSO server, but it does not send all queries to that server. When
Nomenclator constrains the search for a query answer, it screens out
irrelevant queries from ever reaching the server. When Nomenclator
finds an answer in its cache, it screens out redundant queries from
reaching the server. The server becomes easier to find and use
without experiencing the high loads caused by exhaustive and
redundant searches.
The Internet Nomenclator Project creates the foundation for a much
broader heterogeneous directory service for the Internet. The
current version of Nomenclator provides integrated access to CCSO
and relational database services. The Nomenclator System
Architecture supports fast, integrated searches of any collection of
heterogeneous directories. The Internet Nomenclator Project can be
enhanced to support additional name services, or provide intergated
query services for other application domains. The project is
starting with CCSO services, because the CCSO services are widely
available and successful.
Section 2 describes the Nomenclator system in more detail. Section
3 explains how to register a CCSO server as part of the project.
Section 4 briefly describes how to use Nomenclator. Section 5
provides a summary.
[Page 3]
INTERNET-DRAFT September 1996
2. Nomenclator System
Nomenclator is a scalable, extensible information system for the
Internet. It supports descriptive (i.e. relational) queries. Users
locate information about people, organizations, hosts, services,
publications, and other objects by describing their attributes.
Nomenclator achieves fast descriptive query processing through an
active catalog, and extensive meta-data and data caching.
The active catalog constrains the search space for a query by
returning a list of data repositories where the answer to the query
is likely to be found. Components of the catalog are distributed
indices that isolate queries to parts of the network, and smart
algorithms for limiting the search space by using semantic,
syntactic, or structural constraints. Meta-data caching improves
performance by keeping frequently used characterizations of the
search space close to the user, thus reducing active catalog
communication and processing costs. When searching for query
responses, these techniques improve query performance by contacting
only the data repositories likely to have actual responses,
resulting in acceptable search times.
Administrators make their data available in Nomenclator by supplying
information about the location, format, contents, and protocols of
their data repositories. Experience with Nomenclator shows that
gathering a small amount of information from data owners can have a
substantial positive impact on the ability of users to retrieve
information. For example, each CCSO administrator provides a
mapping from the local view of data (or schema) at the CCSO server
to Nomenclator's world view. The administrator also supplies
possible values for any attributes with small domains at the data
repository (such as the "city" or "state_or_province" attributes).
With this information, Nomenclator can isolate queries to a small
percentage of the CCSO data repositories, and provide an integrated
view of their data. Nomenclator provides tools that minimize the
effort that administrators expend in characterizing their data
repositories. Nomenclator does not require administrators to change
the format of their data or the access protocol for their database.
2.1 Components of a Nomenclator System
A Nomenclator system is comprised of a distributed catalog service
and a query resolver (see Figure 2). The distributed catalog
service gathers meta-data about data repositories and makes it
available to the query resolver. Meta-data includes constraints on
[Page 4]
INTERNET-DRAFT September 1996
attribute values at a data repository, known patterns of data
distribution across several data repositories, search and navigation
techniques, schema and protocol translation techniques, and the
differing schema at data repositories.
--------------------------------------------------------------------
+-------------+ +-------------+
| | | |
World View | | Meta Data | |
Query | | Request | Distributed |
----------->| Query | ----------->| |
| Resolver | | Catalog |
| | | |
<-----------| (caches) | <-----------| Service |
World View | | Meta Data | |
Response | | Response | |
+-------------+ +-------------+
Figure 2: Components of a Nomenclator System
--------------------------------------------------------------------
Query resolvers at the user sites retrieve, use, cache, and re-use
this meta-data in answering user queries. The catalog is "active"
in two ways. First, some meta-data moves from the distributed
catalog service to each query resolver during query processing.
Second, the query resolver uses the initial meta-data, in particular
the search and navigation techniques, to generate additional meta-
data that guides query processing. Typically, one resolver process
serves a few hundred users in an organization, so users can benefit
from larger resolver caches.
Query resolvers cache techniques for constraining the search space
and the results of previously constrained searches (meta-data), and
past query answers (data) to speed future query processing. Meta-
data and data caching tailor the query resolver to the specific
needs of the users at the query site. They also increase the scale
of a Nomenclator system by reducing the load from repeated searches
or queries on the distributed catalog service, data repositories,
and communications network.
The distributed catalog service is logically one network service,
but it can be divided into pieces that are distributed and/or
replicated. Query resolvers access this distributed, replicated
[Page 5]
INTERNET-DRAFT September 1996
service using the same techniques that work for multiple data
repositories.
A Nomenclator system naturally includes many query resolvers.
Resolvers are independent, but renewable, query agents that can be
as powerful as the resources available at the user site. Caching
decreases the dependence of the resolver on the distributed catalog
service for frequently used meta-data, and on data repositories for
frequently used data. Caching thus improves the number of users
that can be supported and the local availability of the query
service.
2.2 Meta-Data Techniques
The active catalog structures the information space into a
collection of relations about people, hosts, organizations, services
and other objects. It collects meta-data for each relation and
structures it into "access functions" for locating and retrieving
data. Access functions respond to the question: "Where is data to
answer this query?" There are two types of responses corresponding
to the two types of access functions. The first type of response
is: "Look over there." "Catalog functions" return this response;
they constrain the query search by limiting the data repositories
contacted to those having data relevant to the query. Catalog
functions return a referral to data access functions that will
answer the query or to additional catalog functions to contact for
more detailed information. The second response to "Where?" is:
"Here it is!" "Data access functions" return this response; they
understand how to obtain query answers from specific data
repositories. They return tuples that answer the query.
Nomenclator supplies access functions for common name services, such
as the CCSO service, and organizations can write and supply access
functions for data on their repositories.
Access functions are implemented as remote or local services.
Remote access functions are services that are available through a
standard remote procedure call interface. Local access functions
are functions that are supplied with the query resolver. Local
access functions can be applied to a variety of indexing and data
retrieval tasks by loading them with meta-data stored in distributed
catalog service. Remote access functions are preferred over local
ones when the resources of the query resolver are inadequate to
support the access function. The owners of data may also choose to
supply remote access functions for privacy reasons if their access
functions use proprietary information or algorithms. Local
functions are preferred whenever possible, because they are highly
[Page 6]
INTERNET-DRAFT September 1996
replicated in resolver caches. They can reduce system and network
load by bringing the resources of the active catalog directly to the
users.
Remote access functions are simple to add to Nomenclator and local
access functions are simple to apply to new data repositories,
because the active catalog provides "referrals" that describe the
conditions for using access functions. Each referral contains a
template and a list of references to access functions. The template
is a conjunctive selection predicate that describes the scope of the
access functions. Conjunctive queries that are within the scope of
the template can be answered with the referral. When a template
contains a wildcard value ("*") for an attribute, the attribute must
be present in any queries that are processed by the referral. The
system follows the following rule:
Query Coverage Rule:
If the set of tuples satisfying the selection predicate in a query
is covered by (is a subset of) the set of tuples satisfying the
template, then the query can be answered by the access functions
in the reference list of the referral.
For example, the query below:
select * from People where country = "US" and surname = "Ordille";
is covered by the following templates in Lines (1) through (3), but
not by the templates in Lines (4) and (5):
(1) country = "US" and surname = "*"
(2) country = "US" and surname = "Ordille"
(3) country = "US"
(4) organization = "*"
(5) country = "US" and surname = "Inners"
Referrals form a generalization/specialization graph for a relation
called a "referral graph." Referral graphs are a conceptual tool
that guides the integration of different catalog functions into our
system and that supplies a basis for catalog function construction
and query processing. A "referral graph" is a partial ordering of
[Page 7]
INTERNET-DRAFT September 1996
the referrals for a relation. It is constructed using the
subset/superset relationship: "S is a subset of G." A referral S is
a subset of referral G if the set of queries covered by the template
of S is a subset of the set of queries covered by the template of G.
S is considered a more specific referral than G; G is considered a
more general referral than S. For example, the subset relationship
exists between the pairs of referrals with the templates listed
below:
(1) country = "US" and surname = "Ordille"
is a subset of
country = "US"
(2) country = "US" and surname = "Ordille"
is a subset of
country = "US" and surname = "*"
(3) country = "US" and surname = "*"
is a subset of
country ="US"
(4) country = "US"
is a subset
"empty template"
but it does not exist between the pairs of referrals with the
following templates:
(5) country = "US"
is not a subset of
department = "CS"
(6) country = "US" and name = "Ordille"
is not a subset of
country = "US" and name = "Inners"
In Lines (1) and (2), the more general referral covers more queries,
because it covers queries that list different values for surname.
In Line (3), the more general referral covers more queries, because
it covers queries that do not constrain surname to a value. In Line
(4), the specific referral covers only those queries that constrain
the country to "US" while the empty template covers all queries.
During query processing, wildcards in a template are replaced with
the value of the corresponding attribute in the query. For any
query covered by two referrals S and G such that S is a subset of G,
the set of tuples satisfying the template in S is covered by the set
[Page 8]
INTERNET-DRAFT September 1996
of tuples satisfying the template in G. S is used to process the
query, because it provides the more constrained (and faster) search
space. The referral S has a more constrained logical search space
than G, because the set of tuples in the scope of S is no larger,
and often smaller, than the set in the scope of G. Moreover, S has a
more constrained physical search space than G, because the data
repositories that must contacted for answers to S must also be
contacted for answers to G, but additional data repositories may
need to be contacted to answer G.
In constraining a query, a catalog function always produces a
referral that is more specific than the referral containing the
catalog function. Wildcards ("*") in a template indicate which
attribute values are used by the associated catalog function to
generate a more specific referral. In other words, catalog
functions always follow the rule:
Catalog Function Constrained Search Rule:
Given a referral R with a template t and a catalog function cf,
and a query q covered by t, the result of using cf to process q,
cf(q), is a referral R' with template t' such that q is covered
by t' and R' is more specific than R.
Catalog functions make it possible to import a portion of the
indices for the information space into the query resolver. Since
they generate referrals, the resolver can cache the most useful
referrals for a relation and call the catalog function as needed to
generate new referrals.
The resolver query processing algorithm obtains an initial set of
referrals from the distributed catalog service. It then navigates
the referral graph, calling catalog functions as necessary to obtain
additional referrals that narrow the search space. Sometimes, two
referrals that cover the query have the relationship of general to
specific to each other. The resolver eliminates unnecessary access
function processing by using only the most specific referral along
each path of the referral graph.
The search space for the query is initially set to all the data
repositories in the relation. As the resolver obtains referrals to
sets of relevant data repositories (and their associated data access
functions) it forms the intersection of the referrals to constrain
the search space further. The intersection of the referrals
includes only those data repositories listed in all the referrals.
Intersection combines independent paths through the referral graph
to derive benefit from indices on different attributes.
[Page 9]
INTERNET-DRAFT September 1996
2.3 Meta-Data and Data Caching
A Nomenclator query resolver caches the meta-data that result from
calling catalog functions. It also caches the responses for
queries. If the predicate of a new query is covered by the
predicate of a previous query, Nomenclator calculates the response
for the new query from the cached response of the old query.
Nomenclator timestamps its cache entries to provide measures of the
currentness of query responses and selective cache refresh. The
timestamps are used to calculate a t-bound on query responses
[5][1]. A t-bound is the time after which changes may have occurred
to the data that are not reflected in the query response. It is the
time of the oldest cache entry used to calculate the response.
Nomenclator returns a t-bound with each query response. Users can
request more current data by asking for responses that are more
recent than this t-bound. Making such a request flushes older items
from the cache if more recent items are available. Query resolvers
calculate a minimum t-bound that is some refresh interval earlier
than the current time. Resolvers keep themselves current by
replacing items in the cache that are earlier than the minimum t-
bound.
2.4 Scale and Performance
Three performance studies of active catalog and meta-data caching
techniques are available [5]. The first study shows that the active
catalog and meta-data caching can constrain the search effectively
in a real environment, the X.500 name space. The second study
examined the performance of an active catalog and meta-data caching
for single users on a local area network. The experiments showed
that the techniques to eliminate data repositories from the search
space can dramatically improve response time. Response times
improve, because latency is reduced. The reduction of latency in
communications and processing is critical to large-scale descriptive
query optimization. The experiments also showed that an active
catalog is the most significant contributor to better response time
in a system with low load, and that meta-data caching functions to
reduce the load on the system. The third study used an analytical
model to evaluate the performance and scaling of these techniques
for a large Internet environment. It showed that meta-data caching
plays an essential role in scaling the distributed catalog service
to millions of users. It also showed that constraining the search
space with an active catalog contributes significantly to scaling
data repositories to millions of users. Replication and data
caching also contribute to the scale of the system in a large
Internet environment.
[Page 10]
INTERNET-DRAFT September 1996
3. Registering a CCSO Server
The Internet Nomenclator Project supports the following home page:
http://cm.bell-labs.com/cs/what/nomenclator
The home page provides a variety of information and services.
Administrators can register their CCSO servers through services on
this home page. The registration service collects CCSO server
location information, contact information for the administrator of
the CCSO server, implicit and explicit constraints on entries in the
server's database, and a mapping from the local schema of the CCSO
server to the schema of the world view.
The implicit and explicit constraints on the server's database are
the fuel for Nomenclator's catalog functions. The registration
center currently collects constraints on organization name,
department, city, state or province name, country, phone number,
postal code, and email address. These constraints are automatically
incorporated into Nomenclator's distributed catalog service. They
are used by catalog functions in query resolvers to constrain
searches to relevant CCSO servers. For example, a database only
contains information about the computer science and electrical
engineering departments at a French university. The department,
organization and country attributes are constrained. Nomenclator
uses these constraints to prevent queries about other departments,
organizations or countries from being sent to this CCSO server.
The mapping from the local schema of the CCSO server to the schema
of the world view allows Nomenclator to translate queries and
responses for the CCSO server. The registration center currently
collects this mapping by requesting an example of how to translate a
typical entry in the CCSO server into the world view schema and,
optionally, an example of how to translate a canonical entry in the
world view schema into the local schema of the CCSO server [4].
These examples are then used to generate a mapping program that is
stored in the distributed catalog service. The CCSO data access
function in the query resolver interprets these programs to
translate queries and responses communicated with that CCSO server.
We plan to release the mapping language to CCSO server
administrators, so administrators can write and maintain the mapping
for their servers. We have experimented with more than 20 mapping
programs. They are seldom more than 50 lines, and are often
shorter. It typically takes one or two lines to map an attribute.
[Page 11]
INTERNET-DRAFT September 1996
4. Using Nomenclator
The Internet Nomenclator Project will provide Nomenclator query
services in phases. The first phase, to be completed soon, will
provide a centralized query service on the Internet. The project
will run a Nomenclator query resolver that will be accessible
through a Web page and the Simple Nomenclator Query Protocol (SNQP)
[2].
During the first phase of the project, users can find the query
service at Nomenclator's home page (see the URL in Section 3). The
service answers queries that are a conjunction of string values for
attributes. A variety of matching techniques are supported
including exact string matching, matching with wildcards, and word-
based matching in the style of the CCSO service. The service also
provides advice about the cost of queries and ways to constrain
queries further to produce faster response times. Our web interface
uses the Simple Nomenclator Query Protocol (SNQP) [2]. Programmers
can create their own interfaces by using this protocol to
communicate with the Nomenclator query resolver. They will require
the host name and port number for the query resolver which they can
obtain from the Nomenclator home page.
The second phase of the query service will distribute query
resolvers, so users can benefit from running query resolvers
locally. Local query resolvers reduce latency for the user, and
distribute query processing load throughout the network.
5. Summary
The Internet Nomenclator Project augments existing CCSO services by
supplying schema integration and fast cross-server searches. The key
to speed in descriptive query processing is an active catalog, and
extensive meta-data and data caching. The Nomenclator system is the
result of research in distributed systems [5][6][7][4]. It can be
extended to incorporate other name servers, besides the CCSO
servers, and to address distributed search and retrieval challenges
in other application domains. In addition to providing a white pages
service, the Internet Nomenclator Project will evaluate how an
active catalog, meta-data caching and data caching perform in very
large global information system. The ultimate goal of the project
is to refine these techniques to provide the best possible global
information systems.
[Page 12]
INTERNET-DRAFT September 1996
6. Security Considerations
Security considerations are not discussed in this document.
7. Acknowledgements
Thanks to <<your name here!!>> for their comments on earlier drafts
of this document.
8. References
[1] H. Garcia-Molina, G. Wiederhold. "Read-Only Transactions in
a Distributed Database," ACM Transactions on Database Sys-
tems 7(2), pp. 209-234. June 1982.
[2] J. Elliott, J. Ordille. "The Simple Nomenclator Query Proto-
col (SNQP)," Internet Draft.
<URL:ftp://ftp.internic.net/internet-drafts/draft-ietf-ids-
snqp-01.txt>
[3] R. Hedberg, S. Dorner, P. Pomes. "The CCSO Nameserver (Ph)
Architecture," Internet Draft. December 1995.
<URL:ftp://ftp.internic.net/internet-drafts/draft-ietf-ids-
ph-00.txt>
[4] A. Levy, J. Ordille. "An Experiment in Integrating Internet
Information Sources," AAAI Fall Symposium on AI Applications
in Knowledge Navigation and Retrieval, November 1995.
<URL:http://cm.bell-labs.com/cm/cs/doc/95/11-01.ps.gz>
[5] J. Ordille. "Descriptive Name Services for Large Internets,"
Ph. D. Dissertation. University of Wisconsin. 1993.
<URL:http://cm.bell-labs.com/cm/cs/doc/93/12-01.ps.gz>
[6] J. Ordille, B. Miller. "Distributed Active Catalogs and
Meta-Data Caching in Descriptive Name Services," Thirteenth
International IEEE Conference on Distributed Computing Sys-
tems, pp. 120-129. May 1993. <URL:http://cm.bell-
labs.com/cm/cs/doc/93/5-01.ps.gz>
[7] J. Ordille, B. Miller. "Nomenclator Descriptive Query Opti-
mization in Large X.500 Environments," ACM SIGCOMM Symposium
[Page 13]
INTERNET-DRAFT September 1996
on Communications Architectures and Protocols, pp. 185-196,
September 1991. <URL:http://cm.bell-
labs.com/cm/cs/doc/91/9-01.ps.gz>
9. Author's address:
Joann J. Ordille
Bell Labs, Lucent Technologies
Computing Sciences Research Center
700 Mountain Avenue, Rm 2C-301
Murray Hill, NJ 07974 USA
Email: joann@bell-labs.com
This Internet Draft expires March 31, 1997.
[Page 14]
