Decentralizing a global naming service for improved performance and fault tolerance

ABSTRACT

Naming is an important aspect of distributed system design. A naming system allows users and programs to assign character-string names to objects, and subsequently use the names to refer to those objects. With the interconnection of clusters of computers by wide-area networks and internetworks, the domain over which naming systems must function is growing to encompass the entire world. In this paper we address the problem of a global naming system, proposing a three-level naming architecture that consists of global, administrational, and managerial naming mechanisms, each optimized to meet the performance, reliability, and security requirements at its own level. We focus in particular on a decentralized approach to the lower levels, in which naming is handled directly by the managers of the named objects. Client-name caching and multicast are exploited to implement name mapping with almost optimum performance and fault tolerance. We also show how the naming system can be made secure. Our conclusions are bolstered by experience with an implementation in the V distributed operating system.

REFERENCES

• 1: BIRRELL, A. D., LAMPSON, B. W., NEEDHAM, R. M., AND SCHROEDER, M. D. A global authentication service without global trust. In Proceedings of 1986 IEEE Symposium on Security and Privacy (Oakland, Calif., April 1986) IEEE, New York, 1986, pp. 223-230.
• 2: Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
• 3: BOGGS, D.R. Internet broadcasting. Tech. Rep. CSL-83-3, Xerox, Oct. 1983.
• 4: RROWNBRtDGE, D. R., MARSHALL, L. F., AND RANDELL, B. The Newcastle Connection--or UNIXes of the world unite! So/tw. Pract. Exper. 12, 12 (Dec. 1982), 1147-1162.
• 5: David R. Cheriton, UIO: a uniform I/O system interface for distributed systems, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.12-46, Feb. 1987 [doi>10.1145/7351.7353]
• 6: David Cheriton, The V distributed system, Communications of the ACM, v.31 n.3, p.314-333, March 1988 [doi>10.1145/42392.42400]
• 7: D Cheriton, VMTP: a transport protocol for the next generation of communication systems, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, p.406-415, August 05-07, 1986, Stowe, Vermont, United States
• 8: David R. Cheriton , Stephen E. Deering, Host groups: a multicast extension for datagram internetworks, ACM SIGCOMM Computer Communication Review, v.15 n.4, p.172-179, Sept. 1985
• 9: CHERITON, D. R., AND MANN, T.P. Uniform access to distributed name interpretation in the V-System. In Proceedings of the Fourth International Conference on Distributed Computing Systems (San Francisco, May 1984). IEEE, New York, 1984, pp. 290-297.
• 10: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• 11: DEERING, S.E. Host extensions for IP multicasting. Tech. Rep. RFC 988, Network Information Center, SRI International, July 1986.
• 12: DEER1NG, S. E., AND CHERITON, D. R. Host groups: A multicast extension to the Internet protocol. Tech. Rep. RFC 966, Network Information Center, SRI International, Dec. 1985.
• 13: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 14: DIGITAL EQUIPMENT CORPORATION, INTEL CORPORATION, AND XEROX CORPORATION. The Ethernet: A local area network--data link layer and physical layer specifications, Version 1.0. Sept. 1980.
• 15: David Kenneth Gifford, Information storage in a decentralized computer system, 1981
• 16: Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
• 17: LEFFLER, S., KARELS, M., AND McKUSlCK, M. Measuring and improving the performance of 4.2BSD. In I984 USENIX Summer Conference Proceedings (Pittsburgh, Pa., June 1984). USENIX, pp. 237-252.
• 18: T. P. Mann, Decentralized naming in distributed computer systems, Stanford University, Stanford, CA, 1987
• 19: MOCKAPETRIS, P. Domain names: Concepts and facilities. Tech. Rep. RFC 882, Network information Center, SRI International, Sept. 1983.
• 20: MOCKAPETRIS, P. Domain names: Implementation and specification. Tech. Rep. RFC 883, Network Information Center, SRI International, Sept. 1983.
• 21: Jeffrey C Mogull, Representing information about files, Stanford University, Stanford, CA, 1986
• 22: Derek C. Oppen , Yogen K. Dalal, The clearinghouse: a decentralized agent for locating named objects in a distributed environment, ACM Transactions on Information Systems (TOIS), v.1 n.3, p.230-253, July 1983 [doi>10.1145/357436.357439]
• 23: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 24: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 25: RowE, L. A., AND BIRMAN, K.P. A local network based on the UNIX operating system. IEEE Trans. Softw. Eng. SE-8, 2 (March 1982), 137-146.
• 26: SANDBERG, R., GOLDBERG, D., KLEIMAN, S., WALSH, D., AND LYON, B. Design and implementation of the Sun network filesystem. Tech. Rep. Sun Microsystems, Inc., 1985.
• 27: Michael D. Schroeder , Andrew D. Birrell , Roger M. Needham, Experience with Grapevine: the growth of a distributed system, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.3-23, February 1984 [doi>10.1145/2080.2081]
• 28: Alan Brian Sheltzer, Network transparency in an internetwork environment, 1985
• 29: STRONG, H. R., AND DOLEV, D. Byzantine Agreement. Res. Rep. RJ 3714 (42930), IBM Research Division, Dec. 1982.
• 30: Douglas Brian Terry, Distributed name servers: naming and caching in large distributed computing environments, 1985
• 31: Marvin M. Theimer , Keith A. Lantz , David R. Cheriton, Preemptable remote execution facilities for the V-system, Proceedings of the tenth ACM symposium on Operating systems principles, p.2-12, December 1985, Orcas Island, Washington, United States
• 32: Bruce Walker , Gerald Popek , Robert English , Charles Kline , Greg Thiel, The LOCUS distributed operating system, Proceedings of the ninth ACM symposium on Operating systems principles, p.49-70, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 33: WALL, D.W. Mechanisms for broadcast and selective broadcast. Tech. Report 190, Computer Systems Laboratory, Stanford Univ., June 1980.
• 34: Brent B Welch , John K. Ousterhout, Prefix Tables: A Simple Mechanism for Locating Files, University of California at Berkeley, Berkeley, CA, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Experimentation, Measurement, Performance, Reliability