Network protocol: A structured approach

ABSTRACT

Network protocols are modeled by processes exchanging messages through communication channels. For finite state protocols, each process participating in the protocol can be represented by a finite state graph. In this paper, we introduce a structuring principle for finite state protocols in the form of subgraphs. By structured protocols, we mean the following. The protocol graph can be partitioned into or be constructed from subgraphs each having a unique entry node and zero or more exit nodes. The exit nodes of one subgraph can be connected only to the entry nodes of other subgraphs. Moreover, a process in one subgraph can exchange events with another process in its corresponding subgraph only, i.e. there are no 'cross interaction' between subgraphs. Finally, from the standpoint of protocol design or synthesis, we require that when one process makes a transition into another subgraph, the other process will follow suit. Protocols that satisfy the above properties are structured in the sense that their logical correctness can be inferred from the logical correctness of individual protocol subgraphs.

REFERENCES

• 1: Andrew S. Tanenbaum, Network Protocols, ACM Computing Surveys (CSUR), v.13 n.4, p.453-489, Dec. 1981 [doi>10.1145/356859.356864]
• 2: C. A. Sunshine, "Formal Modeling of Communication Protocols," University of Southern California, ISI RR-81-89, March 5, 1981 Network Architecture Format and Protocol Reference Manual: Architectural Logic, IBM, IBM Form SC 30-3112-1, 1978.
• 3: System Network Architecture Format and Protocol Reference Manual: Architectural Logic, IBM, IBM Form SC 30-3112-1, 1978.
• 4: ISO/TC 97/SC 16/537, "Reference Model of Open System Interconnection," Dec. 1980.
• 5: T. F. Piatkowski, "An Engineering Discipline for Distributed Protocol Systems," Proceedings of an INWG/NPL Workshop on Protocol Testing, Vol. 1, May 27-29, 1981, pp. 177-215.
• 6: H. Rudin and C. H. West, "Validation of Protocols Using State Enumeration: A summary of some experience," Proc. INWG/NPL Workshop on Protocol Testing, Vol. 1, May 27-29, 1981, pp. 371-375.
• 7: G. V. Bochmann, "Finite State Description of Communication Protocols," Computer Networks, Vol. 2, Oct. 1978, pp. 361-372.
• 8: P. Zafiropulo, et. al., "Towards Analyzing and Synthesizing Protocols," IEEE Transactions on Communications, Vol. COM-28, No. 4, April 1980, pp. 651-661.
• 9: D. Brand and P. Zafiropulo, "On Communicating Finite State Machines," IBM Research Report RZ 1053, Jan. 1981.
• 10: G. D. Schultz, et. al., "Executable Description and Validation of SNA," IEEE Transactions on Communications, Vol. COM-28, No. 4, April 1980, pp. 661-677.
• 11: C. H. West, "General Technique for Communication Protocol Validation," IBM J. Res. Develop., Vol. 22, No. 4, July 1978, pp. 393-404.
• 12: P. Zafiropulo, "Protocol Validation by Duologue Matrix Analysis," IEEE Transactions on Communications, Vol. COM-26, No. 8, Aug. 1978, pp. 1187-1194.
• 13: . Rudin, et. al., "Automated Protocol Validation: One chain of development," Computer Networks, Vol. 2, No. 4/5, 1978, pp. 373-380.
• 14: T. Y. Choi, "A Structured Approach to the Analysis and Design of Finite State Protocols," Ph.D. Thesis, School of Electrical Engineering, Georgia Institute of Technology, 1983 (in preparation).
• 15: J. Rubin and C. H. West, "An Improved Protocol Validation Technique," Computer Networks, Vol. 6, 1982, pp. 65-73

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory