A system for constructing configurable high-level protocols

ABSTRACT

New distributed computing applications are driving the development of more specialized protocols, as well as demanding greater control over the communication substrate. Here, a network subsystem that supports modular, fine-grained construction of high-level protocols such as atomic multicast and group RPC is described. The approach is based on extending the standard hierarchical model of the x-kernel with composite protocols in which micro-protocol objects are composed within a standard runtime framework. Each micro-protocol realizes a separate semantic property, leading to a highly modular and configurable implementation. In contrast with similar systems, this approach provides finer granularity and more flexible inter-object communication. The design and prototype implementation runing on Mach are described. Performance results are also given for a micro-protocol suite implementing variants of group RPC.

REFERENCES

• 1: Mark B. Abbott , Larry L. Peterson, Increasing network throughput by integrating protocol layers, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.600-610, Oct. 1993 [doi>10.1109/90.251918]
• 2: David Edward Bakken , Richard D. Schlichting, Supporting Fault-Tolerant Parallel Programming in Linda, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.287-302, March 1995 [doi>10.1109/71.372777]
• 3: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 4: Brian N. Bershad , Craig Chambers , Susan Eggers , Chris Maeda , Dylan McNamee , Przemysław Pardyak , Stefan Savage , Emin Gün Sirer, SPIN—an extensible microkernel for application-specific operating system services, ACM SIGOPS Operating Systems Review, v.29 n.1, p.74-77, Jan. 1995 [doi>10.1145/202453.202472]
• 5: Thomas E. Bihari , Karsten Schwan, Dynamic adaptation of real-time software, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.143-174, May 1991 [doi>10.1145/103720.103723]
• 6: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 7: Andrew P. Black, Understanding transactions in the operating system context, ACM SIGOPS Operating Systems Review, v.25 n.1, p.73-76, Jan. 1991 [doi>10.1145/122140.122149]
• 8: 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
• 9: R. Cmelik, N. Gehani, and W. D. Roome. Fault Tolerant Concurrent C: A tool for writing fault tolerant distributed programs. In Proceedings of the 18th IEEE Symp. on Fault- Tolerant Computing, pages 55-61, Tokyo, June 1988.
• 10: E. C. Cooper. Programming language support for multicast communication in distributed systems. In Proceedings ofthe lOth IEEE Conf. on Distr. Computing Syst., pages 450-457, Pads, France, 1990.
• 11: F. Cristian. Reaching agreement on processor-group membership in synchronous distributed systems. Distributed Computing, 4:175-187, 1991.
• 12: F. Cristian, H. Aghili, R. Strong, and D. Dolev. Atomic broadcast: From simple message diffusion to Byzantine agreement. In Proceedings of the 15th IEEE Symp. on Fault- Tolerant Computing, pages 200--206, Ann Arbor, MI, Jun 1985.
• 13: H. J. F. Fonseca. Support environments for the modularizafion, implementation and execution of communication protocols. Master's thesis, Instituto Superior T~cnico, Lisboa, Portugal, June 1994. In Portuguese.
• 14: J. Goldberg, I. Greenberg, and T. Lawrence. Adaptive fault tolerance. In Proceedings of the IEEE Workshop on Advances in Parallel and Distributed Systems, pages 127-132, Princeton, NJ, Oct 1993.
• 15: Murray W. Goldberg , Gerald W. Neufeld , Mabo R. Ito, The Parallel Protocol Framework, University of British Columbia, Vancouver, BC, Canada, 1992
• 16: Richard Andrew Golding, Weak-consistency group communication and membership, University of California at Santa Cruz, Santa Cruz, CA, 1992
• 17: D. Guedes, D. Bakken, N. Bhatti, M. Hiltunen, and R. D. Schlichting. A customized communication subsystem for FT-Linda. In Proceedings of the 13th Brazilian Symposium on Computer Networks, Belo Horizonte, MG, Brazil, May 1995. To appear.
• 18: Graham Hamilton , Michael L. Powell , James G. Mitchell, Subcontract: a flexible base for distributed programming, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.69-79, December 05-08, 1993, Asheville, North Carolina, United States
• 19: M. Hiltunen and R. D. Schlichting. An approach to constmcting modular fault-tolerant protocols. In Proceedings of the 12th IEEE Symp. on Reliable Distributed Systems, pages 105-114, Princeton, NJ, Oct 1993.
• 20: Matti A. Hiltunen , Richard D. Schlichting, A Model for Adaptive Fault-Tolerant Systems, Proceedings of the First European Dependable Computing Conference on Dependable Computing, p.3-20, October 04-06, 1994
• 21: M. A. Hiltunen , R. D. Schlichting, Constructing a configurable group RPC service, Proceedings of the 15th International Conference on Distributed Computing Systems, p.288, May 30-June 02, 1995
• 22: M. Hilmnen and R. D. Schlichting. Properties of membership services. In Proceedings of the Second IEEE Syrup. on Autonomous Decentralized Systems, pages 200-207, Phoenix, AZ, April 1995.
• 23: Norman C. Hutchinson , Larry L. Peterson, The X-Kernel: An Architecture for Implementing Network Protocols, IEEE Transactions on Software Engineering, v.17 n.1, p.64-76, January 1991 [doi>10.1109/32.67579]
• 24: Ralf Keller , Wolfgang Effelsberg, MCAM: an application layer protocol for movie control, access, and management, Proceedings of the first ACM international conference on Multimedia, p.21-29, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.166268]
• 25: H. Kopetz, G. Grunsteidl, and J. Reisinger. Fault-tolerant membership service in a synchronous distributed real-time system. In A. Avizienis and J. Laprie, editors, Dependable Computing for Critical Applications, pages 411-429. Spfinger-Vefiag, Wien, 1991.
• 26: B. Lindgren, M. Ammar, B. Krupczak, and K. Schwan. Paranel and configurable protocols: Experiences with a prototype and an architectural framework. Technical Report G1T-CC-93/22, College of Computing, Georgia Institute of Technology, Atlanta, Georgia, March 1993.
• 27: P. M. Melliar-Smith , L. E. Moser , V. Agrawala, Broadcast Protocols for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.17-25, January 1990 [doi>10.1109/71.80121]
• 28: S. Mishra, L. L. Peterson, and R. D. Schlichting. A membership protocol based on partial order. In J. E Meyer and R. D. Schlichting, editors, Dependable Computing for CriticalAppIications 2, pages 309-331. Springer-Vefiag, Vienna, 1992.
• 29: S. Mishra, L. L. Peterson, and R. D. Schlichfing. Consul: A communication substrate for fault-tolerant distributed programs. Distributed Systems Engineering, 1(3):87-103, Dec 1993.
• 30: Shivakant Mishra , Larry L. Peterson , Richard D. Schlichting, Experience with modularity in consul, Software—Practice & Experience, v.23 n.10, p.1059-1075, Oct. 1993 [doi>10.1002/spe.4380231002]
• 31: A. B. Montz, D. Mosberger, S. W. O'Malley, L. L. Peterson, T. A. Proebsting, and J. H. Hartman. Scout: A communications-oriented operating system. Technical Report 94-20, Dept. of Comp. Sci., Univ. of Arizona, June 1994.
• 32: M. Olsen, E. Oskiewicz, and J. Wame. A model for interface groups. In Proceedings of the 10th IEEE Symp. on Reliable Distributed Systems, pages 98-107, Pisa, Italy, Sep 1991.
• 33: Sean W. O'Malley , Larry L. Peterson, A dynamic network architecture, ACM Transactions on Computer Systems (TOCS), v.10 n.2, p.110-143, May 1992 [doi>10.1145/128899.128901]
• 34: F. Panzieri , S. K. Shrivastava, Rajdoot: A Remote Procedure Call Mechanism Supporting Orphan Detection and Killing, IEEE Transactions on Software Engineering, v.14 n.1, p.30-37, January 1988 [doi>10.1109/32.4620]
• 35: Larry L. Peterson , Nick C. Buchholz , Richard D. Schlichting, Preserving and using context information in interprocess communication, ACM Transactions on Computer Systems (TOCS), v.7 n.3, p.217-246, Aug. 1989 [doi>10.1145/65000.65001]
• 36: D. M. Ritchie. A stream input-output system. AT&T Bell Laboratories Technical Journal, 63(8):311-324, Oct. 1984.
• 37: D. Schmidt, D. Box, and T. Suda. ADAPTIVE: A dynamically assembled protocol transformation, integration, and evaluation environment. Concurrency: Practice and Experience, 5(4):269-286, June 1993.
• 38: Robbert Van Renesse , Takako M. Hickey , Kenneth P. Birman, Design and Performance of Horus: A Lightweight Group Communications System, Cornell University, Ithaca, NY, 1994
• 39: P. Veríssimo , L. Rodrigues , M. Baptista, AMp: a highly parallel atomic multicast protocol, Symposium proceedings on Communications architectures & protocols, p.83-93, September 25-27, 1989, Austin, Texas, United States
• 40: R. Yavantkar. MCP: A protocol for coordination and temporal synchronization in multimedia collaborative applications. In Proc. of the 12th IEEE Conf. on Distr. Computing Syst., page 606, Yokohama, Japan, June 1992.

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance