Univers: The construction of an internet-wide descriptive naming system.

摘要

This thesis describes the construction of a descriptive naming system for an internet environment. Descriptive naming systems allow clients to identify a set objects by description. In a world where information is perfect, this amounts to a simple database query. However, descriptive naming systems operate in an imperfect world: clients may provide inaccurate descriptions, the database may contain out-of-date or incomplete information, the database may be highly distributed, and so on. Traditional strategies for handling imperfect information approach the problem from the database's perspective; i.e., queries are resolved according to a method determined by the database designer. This thesis presents a model, called a preference hierarchy, that allows the client to define the meaning of a preferred answer. A preferred answer is computed using knowledge about the quality of information in the database and in the query. Specifically, clients provide the naming system with a description of an object and some meta-information that describes the client's beliefs about the query and the naming system. This meta-information is an ordering on a set of perfect-world approximations and it describes the preferred methods for accommodating imperfect information. The description is then resolved in a way that respects the preferred approximations. The preference hierarchy may be used to solve problems associated with some forms of imperfect information that exist in descriptive naming systems. It also provides a foundation for designing and comparing various naming systems. For example, the preference hierarchy allows us to compare naming systems based on how discriminating they are, and to identify the class of names for which a given naming system is sound and complete. A study of several example naming systems demonstrates how the preference hierarchy can be used as a formal tool for designing naming systems. Univers is a generic attribute-based name server that implements the preference hierarchy model. It provides a foundation upon which a variety of high-level naming services can be built. It is a platform for constructing an internet-wide descriptive naming system. This thesis describes several aspects of its implementation and demonstrates how various descriptive naming services--including a global white-pages service, a local yellow-pages services, and a conventional name-to-address mapper--can be built on top of Univers.