A grammar-based methodology for protocol specification and implementation

ABSTRACT

A new methodology for specifying and implementing communication protocols is presented. This methodology is based on a formalism called “Real-Time Asynchronous Grammars” (RTAG), which uses a syntax similar to that of attribute grammars to specify allowable message sequences. In addition RTAG provides mechanisms for specifying data-dependent protocol activities, real-time constraints, and concurrent activities within a protocol entity. RTAG encourages a top-down approach to protocol design that can be of significant benefit in expressing and reasoning about highly complex protocols. As an example, an RTAG specification is given for part of the Class 4 ISO Transport Protocol (TP-4). Because RTAG allows protocols to be specified at a highly detailed level, major parts of an implementation can be automatically generated from a specification. An RTAG parser can be written which, when combined with an RTAG specification of a protocol and a set of interface and utility routines, constitutes an implementation of the protocol. To demonstrate the viability of RTAG for implementation generation, an RTAG parser has been integrated into the kernel of the 4.2 BSD UNIX operating system, and has been used in conjunction with the RTAG TP-4 specification to obtain an RTAG-based TP-4 implementation in the DoD Internet domain.

REFERENCES

• Blu82: Blumer, T.P. and Tenncy, R.L., A formal specification technique and implementation method for protocols, Computer Networks 6,3 (Ju~y 1982), 201-217.
• Bri85: Ed Brinksma, A tutorial on LOTOS, Proceedings of the IFIP WG6.1 Fifth International Conference on Protocol Specification, Testing and Verification V, p.171-194, June 10-13, 1985
• Har78: Harangozo, J. Protocol definitions with formal grammars, Proceedings Symposium on Computer Network Protocols, Liege, Belgium (Feb. 1978), F6.1-F6.10.
• Mil80: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• Nas83: Nash, S.C. Automated implementation of SNA communication protocols. IEEE international Conference on Communication. Boston, MA., (june 19-22, 1983), 1316-1322.
• Poz82: Pozefsky, D.P. and Smith, F.D. A recta-implementation for Systems Network Architecture, IEEE Trans. Commun., vol. COM- 30 (June 1982), 1348-1355.
• Sch80: Schultz, G.D., Rose, D.B., West, C.H and Gray, J.P. Executable Description and Validation of SNA, IEEE Trans. Commun., vol COM-28 (Apr. 1980), 661-677.
• Sid83b: Sidhu, D.P. and Blumer, T.P. Verification of NBS class 4 transport protocol. SDC Report (Sept. 1983).
• Sun81: Sunshine, C.A. Formal modeling of communication protocols. USC/ISI report IS1/RR-8.1-89.
• Ten78: Teng, A.Y. and Liu, M.T., A formal approach to the design and implementation of network communication protocols, Proc. COMPSAC 78, Chicago (Nov. 1978), 722-727.
• Yem83: Yemini, Y. and Nounou, N. CUPID: a protocol development environment. Proc. 3th iFIP Workshop on Protocol Specification, Testing, and Verification. May 1983.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Asynchronous Transfer Mode (ATM)

General Terms:
Design, Theory