home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / isoc / pub / isoc_news / 1-3 / n-1-3-040.31.1a < prev    next >
Text File  |  1994-03-26  |  5KB  |  85 lines
  1.  
  2.  
  3. N-1-3-040.31.1, Attribute Distribution and Search for Internet
  4. Resource Discovery, by Michael F. Schwartz*,
  5. <schwartz@latour.cs.colorado.edu>
  6.  
  7.  
  8. In the previous issue of Internet Society News, I pointed out that
  9. resource discovery involves two basic problems: characterizing the
  10. resources of interest using name/attribute descriptions, and
  11. distributing this information so it can be searched flexibly and
  12. efficiently.  I also discussed a number of approaches to the
  13. characterization problem.  The current article considers attribute
  14. distribution and search.
  15.  
  16. The most straightforward solution to the distribution/search problem
  17. is to centralize resource information.  This approach is taken by
  18. archie, which stores anonymous FTP directory listings on a central
  19. server.  WAIS uses a centralized server to maintain a directory of
  20. WAIS servers.  To date, centralized information has worked quite well
  21. in archie and WAIS.  Archie maintains information about nearly 1,000
  22. Internet archive sites, and handles thousands of queries per day.
  23. There are hundreds of WAIS servers registered in the top-level
  24. directory, and new servers are added often.
  25.  
  26. The problem with a centralized solution, of course, is that the
  27. central server can become a performance bottleneck and a critical
  28. point of failure, particularly as the scale of the system increases.
  29. The difficulty in sustaining reasonable response times in the face of
  30. tremendous popular demand for archie has moved the community to create
  31. replica servers.  Doing so distributes the load, yet creates auxiliary
  32. problems of distributing the data and maintaining consistency between
  33. replicas.  A future version of archie will address these problems
  34. using "lazy" update semantics to distribute data among replicas.
  35.  
  36. To reduce the scalability and consistency problems of a fully
  37. replicated directory, one can chose a solution where only parts of the
  38. resource data are maintained on any particular server.  A common
  39. approach is to impose some organizational properties on the data, and
  40. distribute data according to these properties.  For example, the X.500
  41. directory service standard divides information hierarchically.  The
  42. tree is divided by country at the top level, and by administrative
  43. organization (company, university, etc.) at the next level down.
  44. Since the information in a hierarchy can be divided into arbitrarily
  45. many pieces, hierarchical directories scale well.  Yet, it is only
  46. efficient to search hierarchical information according to the one way
  47. it is organized.  For example, in X.500 it is efficient to find
  48. information about a person from a known country and organization, but
  49. it would be infeasible to find people according to their technical
  50. interests or other criteria that exist in the individual resource
  51. records, but that are not represented in the tree structure.
  52.  
  53. One can mimic the effect of representing multiple search criteria in a
  54. hierarchy by maintaining separate structures with symbolic links to
  55. the "main" data, but searches still require expensive distributed
  56. operations.  If, on the other hand, one does not support search
  57. operations, symbolic linking can provide an acceptable mechanism.  For
  58. example, the Prospero file system uses symbolic links to provide views
  59. of information in anonymous FTP and other Internet file systems.
  60. Users can browse the information, but search operations are not
  61. supported.
  62.  
  63. There are other ways to partially replicate resource attribute data
  64. beyond hierarchical distribution.  One approach is to distribute
  65. information randomly among a set of servers, and cache the most
  66. popular information at each server.  This approach requires that one
  67. sacrifice the ability to perform exhaustive searches.  I experimented
  68. with one such protocol, optimized for locating a subset of the
  69. available copies of popular resources.
  70.  
  71. Another approach is to construct records describing particular
  72. collections of information available in a structured information space
  73. (such as a hierarchical file system) and register these records into
  74. auxiliary indices that can be searched with "flat" search operations.
  75. For example, one could register particularly important/popular
  76. directories in a large file system into indices focused on particular
  77. technical topics, so that users can search for information about these
  78. topics without regard to the organization in the main file system.
  79. This approach is used by the perspective discovery paradigm discussed
  80. in the previous issue of this newsletter.
  81.  
  82.  
  83. *Assistant Professor, Department of Computer Science, University of
  84. Colorado - Boulder
  85.