Protocol Specification and Testing

The increasing number of computer networks has aroused users' interest in many and various fields of applications, in how a computer network can be built, and in how it may be used. The fundamental rules of computer networks are the protocols. "A protocol is a set of rules that governs the operation of functional units to achieve communication" [STA-86}. The book follows a practical approach to protocol speci­ fication and testing, but at the same time it introduces clearly and precisely the relevant theoretical fundamentals. The principal objectives of this work are: to familiarize readers with communication protocols, to present the main, formal description techniques, to apply various formal description techniques to protocol specification and testing. It is considered that the readership will primarily consist of protocol developers, protocol users, and all who utilize protocol testers. Secondly the book is suggested for postgraduate courses or other university courses dealing with communication networks and data communication. A large part of the book provides a comprehensive overview for managers; some parts are of especial interest to postal organizations. The book consists of three parts: the first part introduces the OS! Reference Model, it provides an overview of the most frequently used protocols and explains the fundamentals of protocol testing. The second part familiarizes readers with the methods used for protocol 5pecification, generation, and testing. Finite-state machines, formal grammars, Petri nets and some speCification languages (SDL, ESTELLE, LOTOS) are discussed in a pragmatic style. The third part deals with applications.

I Communication Protocols Overview.- 1. The Reference Model And Its Layers.- 1.1 Computer Networks, Open Systems.- The concept of computer networks.- The origins of computer networks.- The operation of computer networks.- The beginnings of the Reference Model.- 1.2 The Reference Model.- The essence of the Reference Model.- The elements of the Reference Model.- Functional division of the distributed system.- Management in open system interconnection.- 1.3 Layers, Layer Terms and Layer Elements.- The general principles of layering.- Layer elements.- Identifiers. Naming and addressing.- 1.4 Layer Functions.- The general layer functions.- Connection establishment and release.- Data transfer. Data units.- Error handling.- 1.5 Layer Conventions.- The model of the layer services.- Service primitives.- Time sequence diagrams.- 1.6 Protocols.- The basic communication concept of Open Systems: the protocol.- Protocol features and their control.- The protocol and its environment.- 2. The Seven Layers.- 2.1 About the Seven Layers.- The seven layers.- The functions of the seven layers.- 2.2 The Physical Layer and Its Protocols.- The physical layer and its services.- The data transfer.- Mechanical, electrical, procedural and functional characteristics of the physical layer.- 2.3 The Data Link Layer and Its Protocols.- The data link layer and its services.- Data link functions.- Classification of the data link protocols.- 2.4 Binary Synchronous Communication (BSC) Protocol.- The main feature of BSC.- The character set of BSC.- Time-out.- 2.5 High-level Data Link Control (HDLC) Protocol.- The fundamental concept of HDLC.- Frame types.- Error-free operation of the HDLC.- Erroneous operation of the HDLC.- 2.6 The Network Layer and Its Protocols.- The network layer services.- X.25 packet level procedure.- Packet formats.- Routing.- 2.7 The Transport Layer and Its Protocols.- The transport layer and the transport services.- Transport protocol classes.- 2.8 The Session Layer and Its Protocols.- The session layer.- Session layer functions.- Operation of the session layer.- 2.9 The Presentation Layer and Its Protocols.- The presentation layer and its services.- Transfer syntax and presentation context.- 2.10 The Application Layer and Its Protocols.- The application layer services and functions.- The application process.- General application layer protocols.- Application layer structure.- 3. Abstract Model Of Testing.- 3.1 Purpose of Testing.- Specification, verification and testing.- Conformance testing.- Performance measurement.- 3.2 Network Environment.- Characteristics of the network.- Queues in the network.- The traffic.- 3.3 Error Generators.- Relationship between the network topology and the errors.- Relationship between the layered structure and the errors.- Error generators of the protocol testers.- 3.4 Conformance Testing.- Requirements.- The classification of conformance testing.- 3.5 The Abstract Model of Conformance Testing.- The fundamental concept of abstract testing.- Methods of conformance testing.- The general logical architecture of conformance testers.- The physical architecture of conformance testers.- An example on conformance testing.- 3.6 Performance Testing.- Requirements.- The schedule of performance testing.- Parameters of performance testing in the OSI model.- II Formal Description Techniques.- 4. State-Transition Based Models.- 4.1 Overview of Finite-state Machines.- Basic set theory.- Computability. Turing machines.- Finite-state machines.- State-transition tables and graphs.- 4.2 Examination of Finite-state Machines.- The properties of finite-state machines.- Equivalence of finite-state machines.- State identification with successor tree.- 5. Graph Models.- 5.1 Petri Nets.- Fundamental concepts of Petri nets.- Petri net features.- The subgraphs of the Petri net.- Mathematical description of Petri nets.- 5.2 Modified Petri Nets.- Classification of modified Petri nets.- Time Petri nets.- E-nets.- Numerical Petri nets.- 5.3 Data Flow Graphs.- Graph model of behaviour.- Data flow graph models.- 5.4 Examples of Graph Models.- Examples of Petri nets.- Graph models of protocol components.- 6. Algebras And Formal Languages.- 6.1 Calculus of Communicating Systems.- Basic ideas.- The syntax and semantics of CCS.- Equivalences.- Example.- 6.2 A Specification Language for Abstract Data Types.- Abstract data types.- Language concepts of ACT ONE.- Abstract data types of ACT ONE.- Atomic specification.- Complex specification.- 6.3 Formal Languages.- to formal languages.- Classification of grammars.- 7. Specification Languages For Communication.- 7.1 Specification and Description Language (SDL).- Overview of SDL.- General definition of SDL.- Basic concepts.- SDL process diagram.- From the basic concepts to the structuring concepts.- Partitioning.- Refinement.- Data concepts in SDL.- Operators.- Axioms.- Inheritance.- Tools for SDL.- 7.2 Architectural Specification Concept.- 7.3 ESTELLE, an Extended Finite-state Machine Specification Language.- Overview of ESTELLE.- Transitions.- Modules.- Interaction points and channel type.- Specification.- Example.- Software tools for ESTELLE.- 7.4 LOTOS, a Language of Temporal Ordering Specification.- Overview of LOTOS.- Interactions between processes.- Behaviour expressions.- LOTOS data types.- Recursion and nondeterminism.- III Applications.- 8. Alternating-Bit Protocol Specification.- 8.1 State-transition Graph of the Alternating-bit Protocol.- 8.2 Alternating-bit Protocol Description with Petri Net.- A Petri net specification complemented with variables.- 8.3 ESTELLE Specification of the Alternating-bit Protocol.- The modules.- Declaration of the data transfer submodule.- Transitions.- 9. Protocol Specifications In The Data Link Layer.- 9.1 The Hybrid HDLC Model.- 9.2 A Formal Grammar Description of HDLC.- Essence of the method.- Half-duplex models.- Improved model with sequence numbering.- Full-duplex models.- Conclusions.- 9.3 Formal Description of LAPB with SDL/GR.- The structure of LAPB description.- The processes.- Signals.- The data of the SDL processes.- The process diagrams: the SDL-graphs.- 10. Formal Description Of Transport Protocols.- 10.1 Transport Protocol Description with Finite-state Machine.- 10.2 Transport Protocol Description with SDL-graph.- Extended state-transition graph of the transport protocol.- SDL/GR description of the transport protocol.- 10.3 Numerical Petri Nets of the Transport Protocol.- Transitions.- Enabling conditions for input arcs.- Firing rules.- Conclusions.- 10.4 Data Flow Graph for Transport Protocol Description.- 10.5 LOTOS Specification of the Transport Protocol.- Structure of the specification.- Data type definitions.- Specification of the transport connection in LOTOS.- 11. Conformance Testers.- 11.1 Initial Protocol Testing.- 11.2 Conformance Test Centre in the National Bureau of Standards.- Requirements.- The test system.- Test strategy.- 11.3 A Conformance Tester.- Objectives.- Manual conformance tester.- State-transition table controlled conformance tester.- 11.4 Testing and Diagnosis Aids for Higher Level Protocols.- 11.5 AT&T Protocol Test Centre.- Requirements.- Test centre architecture.- Test sequences.- 12. Test Sequences.- 12.1 Test Sequence Generation.- Transition tour method.- 12.2 W-method.- 12.3 Gönenc Method.- 12.4 Testing the NATHAN Application Protocol.- 12.5 Automatic Test Sequence Generation.- Automatic testing.- The model used.- The tools.- References.- Standards.- Abbreviations.