ISO/IEC TR 10167:1991

Information technology — Open Systems Interconnection — Guidelines for the application of Estelle, LOTOS and SDL

Technologies de l'information — Interconnexion de systèmes ouverts — Principes directeurs pour l'application d'Estelle, LOTOS et SDL

General Information

• Status: Withdrawn
• Publication Date: 06-Nov-1991
• Withdrawal Date: 06-Nov-1991
• ICS: 35.100.01 - Open systems interconnection in general
• Technical Committee: ISO/IEC JTC 1 - Information technology
• Drafting Committee: ISO/IEC JTC 1 - Information technology
• Current Stage: 9599 - Withdrawal of International Standard
• Start Date: 06-May-1999
• Completion Date: 12-Feb-2026

Standards Content (Sample)

TECH NICAL
ISO/IEC
REPORT
?R 10167
First edition
1991-11-15
Information technology - Open Systems
Interconnection - Guidelines for the application
of Estelle, LOGOS and SDL
Technologies de l'information - Interconnexion de systèmes ouverts -
Principes directeurs pour l'application d'lfstelle, LOTOS et SDL
Reference number
IÇOiIEC TR 10167:1991(E)
ISO/IEC TR 10167 : 1991 (E)
Contents
List of Figures ix
Foreword xi
Introduction xiii
1 scope 1
2 References 1
3 Terminology 1
3.1 Architectural Terms . .
3.2 FDTTerms .
................... 2
4 FDT General Characteristics 2
4.1 Introduction .
4.2 The Nature and Purpose of FDTs .
4.2.1 The Purpose of FDTs . 2
4.2.2 Use in Development .
4.2.3 Assessment of FDTs .
4.3 Estelle .
4.4 LOTOS .
4.5 SDL .
4.6 Benefits of FDTs .
4.7 Tools for FDTs .
5 Guide to the Examples 5
5.1 Explanation of the Examples .
5.1.1 Examples of Basic FDT Concepts .
5.1.2 Examples of Basic Architectural Concepts .
5.1.3 Daemon Game .
5.1.4 Sliding Window Protocol . 5
5.1.5 Abracadabra Service and Protocol . 5
5.1.6 A Transport Protocol .
5.2 How to read the Examples .
O ISOllEC 1991
All rlghts reserved . No part of !his publication may be reproduced or utilized in any form
or by any means. electronic or mechanical. including photocopying and microfilm. without
permission in writing from the publisher .
ISOIIEC Copyright Office 0 Case Postale 56 CH-1211 Genève 20 Swi!zerland
Printed in Switzerland
ii
ISO/IE@ TR 10167 : 1991 (E)
6 Examples of Basic FDT Concepts
6.1 Abstraction
..............................
6.1.1 Estelle Representation .
6.1.2 LOTOS Representation .
6.1.3 SDL Representation .
6.2 Information . .
6.2.1 Estelle Representation . 7
6.2.2 LOTOS Representation .
6.2.3 SDL Representation .
6.3 Action
..................................
6.3.1 Estelle Representation . .
6.3.2 LOTOS Representation . 7
6.3.3 SDL Representation . .
6.4 Interaction
................................
6.4.1 Estelle Representation . 8
6.4.2 LOTOS Representation .
6.4.3 SDL Representation . 8
6.5 Interaction Point . .
6.5.1 Estelle Representation . .
6.5.2 LOTOS Representation .
6.5.3 SDL Representation . 9
7 Examples of Basic Architectural Concepts
7.1 Service Access Point
..........................
7.1.1 Estelle Representation .
7.1.2 LOTOS Representation .
7.1.3 SDL Representation .
7.2 Endpoint .
....................
7.2.1 Estelle Representation . . 10
7.2.2 LOTOS Representation .
7.2.3 SDL Representation .
7.3 Service Primitive Parameter .
7.3.1 Estelle Representation . 11
7.3.2 LOTOS Representation . 11
7.3.3 SDL Representation . 11
7.4 Service Data Unit 11
............................
7.4.1 Estelle Representation . 11
7.4.2 LOTOS Representation . 12
7.4.3 SDL Representation . 12
7.5 Service Primitive 12
............................
7.5.1 Estelle Representation . 12
7.5.2 LOTOS Representation . 12
7.5.3 SDL Representation . . 12
7.6 Frotocol Entity 12
..............................
iii
ISO/IEC Ti? 10167 : 1991 (E)
7.6.1 Estelle Representation .
7.6.2 LOTOS Representation .
7.6.3 SDL Representation .
.................................
7.7 Protocol 13
7.7.1 Estelle Representation .
7.7.2 LOTOS Representation .
7.7.3 SDL Representation .
7.8 Protocol Data Unit .
7.8.1 Estelle Representation .
7.8.2 LOTOS Representation .
7.8.3 SDL Representation .
...............................
7.9 Connection
7.9.1 Estelle Representation .
7.9.2 LOTOS Representation .
7.9.3 SDL Representation .
7.1 O Multiplexing .
7.10.1 Estelle Representation .
7.10.2 LOTOS Representation .
7.10.3 SDL Representation .
.................................
7.1 1 Splitting
7.1 1.1 Estelle Representation .
7.1 1.2 LOTOS Representation .
7.1 1.3 SDL Representation .
7.12 Concatenation .
7.12.1 Estelle Representation .
7.12.2 LOTOS Representation .
7.12.3 SDL Representation .
7.1 3 Segmentation .
7.13.1 Estelle Representation .
7.13.2 LOTOS Representation .
7.1 3.3 SDL Representation .
7.14Service. .
7.14.1 Estelle Representation .
7.14.2 LOTOS Representation .
7.14.3 SDL Representation .
8 Daemon Game Example
8.1 Informal Description .
8.2 Deficiencies in the Informal Description .
8.2.1 Presence of Daemon .
....................
I 8.2.2 Login to a Current Game
8.2.3 Attempt to play before Login . 22
8.2.4 Identification of Players and Games .
8.2.5 Player Use of System Signals .
iv
8.2.7 Counting of ‘Bump’ Signals . 23
8.3 Estelle Description . 23
8.3.1 Architecture of the Formal Description . 23
8.3.2 Explanation of Approach . 23
8.3.3 Formal Description . 23
8.3.4 Alternative Formal Description . 25
8.3.5 Subjective Assessment . 26
8.4 LOTOS Description . 26
8.4.1 Architecture of the Formal Description . 27
8.4.2 Explanation of Approach . 27
8.4.3 Formal Description . 27
8.4.4 Alternative Formal Description . 29
8.4.5 Subjective Assessment . 31
I
8.5 SDL Description . 31
8.5.1 Architecture of the Formal Description . 31
8.5.2 Explanation of Approach . 31
8.5.3 Formal Description . 32
8.5.4 Subjective Assessment . 33
8.6 Assessment of the Application of the FDTs . 33
9 Sliding Window Protocol Example 38
9.1 Informal Description . 38
9.1.1 Overview . 38
9.1.2 Sequence Numbering . 38
9.1.3 Transmitter Behaviour . 38
9.1.4 Receiver Behaviour . 38
9.2 Deficiencies in the Informal Description . 39
9.2.1 Underlying Medium . 39
9.2.2 Window Size . 39
9.2.3 Flow Control . 39
9.2.4 Delivery of Corrupted Messages . 39
9.2.5 Value of Time-out Period . 39
9.2.6 Consistent Use of NextRequired . 39
9.2.7 Receive Window Size . 39
9.2.8 Sequence of Operations . 39
9.2.9 Transmit Window Size . 39
9.2.1 O Receive Window Size . 39
9.2.1 1 Corruption of Messages . 40
9.2.12 Transfer of Data and Acknowledgements . 40
9.2.13 Retransmission on Timeout . 40
9.3 Estelle Description . 40
9.3.1 Architecture of the Formal Descriptions . 40
9.3.2 Explanation of Approach . 40
V
ISO/IEC Ti? 10167 : 1991 (E)
9.3.3 Formal Description of the Protocol . 40
9.3.4 Formal Description of the Medium . 43
9.3.5 Subjective Assessment . 44
9.4 LOTOS Description . 44
9.4.1 Architecture of the Formal Descriptions . 44
9.4.2 Explanation of Approach . 47
9.4.3 Formal Description of the Protocol . 47
9.4.4 Formal Description of the Medium . 54
9.4.5 Subjective Assessment . 56
9.5 SDL Description . 56
9.5.1 Architecture of the Formal Descriptions . 56
9.5.2 Explanation of Approach . 56
9.5.3 Formal Description of the Protocol . 57
9.5.4 Formal Description of the Medium . 57
9.5.5 Subjective Assessment . 57
9.6 Assessment of the Application of the FDTs . 57
10 Abracadabra Service and Protocol Example
10.1 Informal Description . 72
10.1.1 Introduction . 72
10.1.2 Service Description . 72
1 O . 1.3 Protocol Description .
10.1.4 Communications Medium Service Description . 73
10.1.5 Model . 73
10.2 Deficiencies in the Informal Description . 73
10.2.1 Flow Control . 73
10.2.2 Premature Transmission of DT .
10.2.3 Stopping Retransmission on Error . 74
10.2.4 Retransmission Limit and Period . 74
10.2.5 Repeated ConReq . 74
10.2.6 DR when Disconnected . 74
10.2.7 Connection Refusal . 74
10.2.8 Connection Refusal . 75
10.2.9 Ignoring Out-of-sequence Data . 75
10.3 Estelle Description . 75
10.3.1 Architecture of the Formal Descriptions . 75
10.3.2 Explanation of Approach . 76
10.3.3 Formal Description of the Service . 77
10.3.4 Formal Description of the Protocol . 79
10.3.5 Subjective Assessment . 85
10.4 LOTOS description . 85
10.4.1 Architecture of the Formal Descriptions . 85
10.4.2 Explanation of Approach .
10.4.3 Formal Description of the Service . 86
vi
ISO/IEC Ti? 10167 : 1991 (E)
10.4.4 Formal Description of the Protocol . 91
10.4.5 Subjective Assessment . 98
10.5 SDL Description . 98
10.5.1 Architecture of the Formal Descriptions . 98
10.5.2 Explanation of Approach . 99
10.5.3 Formal Description of the Service . 99
10.5.4 Formal Description of the Protocol . 99
10.5.5 Subjective Assessment . 99
10.6 Assessment of the Application of the FDTs . 116
11 A Transport Protocol Example 117
11.1 Informal Description . 117
11.1.1 Origins . 117
1 1.1.2 Transport Functions . 117
11.1.3 Connection Establishment and Termination Procedures . 118
11.1.4 Description of Data Transfer Procedures . 118
1 1.1.5 Treatment of Procedure Errors . 119
11.1.6 Formats . 119
11.1.7 Invalid TPDUs . 124
11.2 Deficiencies in the Informal Description . 125
11.2.1 Service Definitions . 125
11.2.2 Description of Procedures . 126
11.2.3 Protocol Classes . 126
11.2.4 Missing Definitions . 126
11.2.5 Unspecified Functions . 127
1 1.2.6 Non-use of Concatenation . 127
1 1.2.7 Responding Address . 127
11.2.8 Multiple SAP Connections . 127
1 1.2.9 Reaction to Incorrect TCA . 127
11.3 Estelle Description . 127
11.3.1 Architecture of the Formal Description . 127
1 1.3.2 Explanation of Approach . 128
11.3.3 Formal Description . 129
11.3.4 Subjective Assessment . 138
1 1.4 LOTOS Description . 138
1 1.4.1 Structure of the Formal Description . 138
11.4.2 Explanation of Approach . 139
1 1.4.3 Formal Description . 140
11.4.4 Subjective Assessment . 171
1 1.5 SDL Description . 171
11 5.1 Architecture of the Formal Description . 171
.................... 172
11.5.2 Explanation of Approach
11 5.3 Formal Description . 172
1 1.5.4 Subjective Assessment . 172
vii
ISO/IEC TR 10167 : 1997 (E)
11.6 Assessment of the Application of FDTs . 172
Annexes 196
A Bibliography 196
A.l International Standards . 196
A.2 Documents . 196
I
B FDT Characteristics 196
B . 1 Specifications and Implementations . 196
8.2 Formal Specifications . 196
8.3 Levels of Abstraction . 196
8.4 FDTTerms . 197
8.4.1 Formalisation . 197
8.4.2 Abstraction . 197
19V
........
8.4.3 Specification, Description. and Implementation
8.4.4 Model . 197
8.4.5 Interpretation . 198
8.4.6 Constructive . 198
8.4.7 Information . 198
8.4.8 Action . 198
8.4.9 Interaction . 198
8.4.1 O Composition . 198
8.4.1 1 Non-Determinism . 198
C FDT Objectives 198
C.l Scope of Application . 198
C.2 General Requirements . 198
C.3 Appropriate Level of Abstraction .
C.4 Design Support . 199
C.5 Implementation Support . 199
D Evaluating Formal Descriptions 200
D.l Layer-Independent Checklists . 200
D.l.l General . 200
D.1.2 Service Descriptions . 200
D.1.3 Protocol Descriptions . 200
D.2 Layer-Independent and FDT-Dependent Checklists .
D.2.1 General . 200
D.2.2 Description of a Single Object . 200
0.2.3 Description of Several InterconnectedObjects . 200
D.2.4 Different Descriptions of Same Object . 200
Verification Methods and Tools . 201
D.3
D.4 Validation Methods and Tools . 201
viii
4.1 Development through Refinement . 3
5.1 Typical Layout of an Example . 6
8.1 Architecture of the Daemon Game in Estelle . 23
8.2 Alternative Architecture of the Daemon Game in Estelle . 25
8.3 SDL Specification of Daemon Game . 34
9.1 Transmitter Window Parameters . 38
9.2 Receiver Window Parameters . 38
9.3 Architecture of the Sliding Window Protocol in Estelle . 40
9.4 Architecture of the Sliding Window Protocol in LOTOS . 45
9.5 Outline Decomposition of the Sliding Window Protocol in LOTOS . 45
9.6 Processes of the Sliding Window Protocol in LOTOS . 46
9.7 Outline Decomposition of Sliding Window Medium in LOTOS . 46
9.8 Processes of Sliding Window Medium in LOTOS . 46
9.9 SDL Specification of Sliding Window Protocol . 58
9.1 O SDL Specification of Sliding Window Medium . 69
10.1 Relationship between AbracadabraService Primitives . 72
10.2 Abracadabra Protocol Data Units . 72
10.3 Communications Medium Service Primitives . 73
10.4 Abracadabra Service and Protocol Model . 74
10.5 Architecture of the Abracadabra Service in Estelle . 75
10.6 Architecture of the Abracadabra Protocol in Estelle . 75
10.7 Outline Decomposition of the Abracadabra Service in LOTOS . 85
10.8 Outline Decomposition of the Abracadabra Protocol in LOTOS .
10.9 SDL Specification of Abracadabra Service . 100
1 O . 1 O SDL Specification of Abracadabra Protocol . 107
1 1.1 Receiving Terminal Reaction to TCR Addressing Options . 119
11.2 Calling Terminal Reaction to TCA Addressing Options . 119
11.3 Parameter Element Coding Structure . 120
11.4 General Block Structure . 120
11.6 Transport Connection Request Block . 120
1 1.5 Transport Layer Block Types . 121
1 1.7 Extended Addressing . 122
11.8 Transport Data Block Size Parameter . 122
1 1.9 Transport Connection Accept Block . 122
11 . 10Transport Connection Clear Block . 123
11.1 1 Additional Clearing Information Parameter . 123
11.12 Transport Block Reject Block . 123
1 1.13 Rejected Block Parameter . 123
ix
ISO/iEC TR 10167 : 1991 (E)
1 1.1 4 Transport Data Block . 124
11.1 5 Architecture of A Transport Protocol in Estelle .
11.16 Constraint-Oriented Decomposition of a Transport Protocol Entity . 139
1 1.17 Decomposition of Process TPEConnection . 139
11.18 SDL Specification of A Transport Protocol .
8.1 Domain of Applicability of an FDT . 197
a
ISO/IEC Ti? 10167 : 1991 (E)
Foreword
IS0 (the International Organization for Standardization) and IEC (the
International Electrotechnical Commission) form the specialized system
for worldwide standardization. National bodies that are members of IS0
or IEC participate in the development of international Standards through
technical committees established by the respective organization to deal
with particular fields of technical activity. IS0 and IEC technical com-
mittees collaborate in fields of mutual interest. Other international or-
ganizations, governmental and non-governmental, in liaison with IS0
and IEC, also take part in the work.
In the field of information technology, IS0 and IEC have established a
joint technical committee, ISO/IEC JTC 1.
The main task of technical committees is to prepare International Stan-
dards, but in exceptional circumstances a technical committee may
propose the publication of a Technical Report of one of the following
types:
- type 1, when the required support cannot be obtained for the publi-
cation of an International Standard, despite repeated efforts;
,>
- type 2, when the subject is still
under technical development or
where for any other reason there is the future but not immediate
possibility of an agreement on an International Standard;
- type 3, when a technical committee has collected data of a different
kind from that which is normally published as an International Stan-
dard (“state of the art”. for example).
Technical Reports of types 1 and 2 are subject to review within three
years of publication, to decide whether they can be transformed into
International Standards. Technical Reports of type 3 do not necessarily
have to be reviewed until the data they provide are considered to be no
longer valid or useful.
ISO/IEC TR 10167, which is a Technical Report of type 3, was prepared
by Joint Technical Committee ISO/IEC JTC 1, Information technology.
Annexes A, B, C and D of this Technical Report are for information only.
The formal descriptions in this Technical Report have been prepared
with care, and have been checked by tools wherever practicable. How-
ever, the aim of this Technical Report is to be tutorial rather than defin-
xi
ISO/IEC TR 10167 : 1991 (E)
itive in nature. The emphasis has therefore been on giving timely
guidance on the use of FDTs.
It is therefore possible that some errors remain in the formal de-
scriptions. Readers are encouraged to report these. Errors in SOL de-
scriptions should be reported to:
CCITT Secretariat
(SG X Question X/1 - FDT)
Rue Varembé 2
GENEVA
Switzerland
Errors in Estelle or LOTOS descriptions should be reported to:
ISO/IEC JTC 1/SC 21 Secretariat
(Project 1.21.45)
1430 Broadway
NEW YORK
NY 10018
USA
via the appropriate National Standards Body.
xii
ISO/IEC TR 10167 : 1991 (E)
Introduction
Formal Description Techniques have been developed to be used in the formal spec-
ification of OS1 and other telecommunications services and protocols. SDL in par-
ticular has been developed for application in the wider field of telecommunications
systems, but in this Technical Report the focus is on the specification of OS1 services
and protocols.
The purpose of this Technical Report is:
a) to aid the users of the FDTs (Formal Description Techniques) Estelle, LOTOS,
and SDL; and
b) to assist and encourage the use of the FDTs for specifying OS1 services and
protocols; and
c) to introduce the FDTs through a carefully chosen set of graded examples; and
d) to assist and encourage the use of the FDTs for defining unambiguous require-
ments for implementation and conformance testing; and
e) to illustrate the errors and ambiguities which can arise with natural language
descriptions; and
f) to illustrate how basic architectural ideas may be represented using FDTs.
xiii
ISO/IEC TR 10167 : 1991 (E)
TECHNICAL REPORT
Information technology - Open Systems Interconnection -
Guidelines for the application of Estelle, LOTOS and SDL
1 Scope of IEC and IS0 maintain registers of currently valid Interna-
tional Standards.
This Technical Report provides: A bibliography of related documents is given in Annex A.
IS0 7498 : 1987, information processing systems - Open
a) an introduction to the nature and purpose of FDTs; and
Systems Interconnection - Basic Reference Model.
b) formal descriptions in each of the FDTs for selected
ISOKR 8509 : 1987, Information processing systems -
examples described in natural language; and
Open Systems Interconnection - Service conventions.
c) guidance to the FDT users as to how to judge and im-
IS0 8807 : 1989, information processing systems - Open
prove the quality of formal descriptions: and
Systems interconnection - LOTOS - A formal description
d) management guidance to FDT users as to how to han-
technique based on the temporal ordering of observational
dle the relationship between informal and formal de-
behaviour.
scriptions, and between formal descriptions; and
IS0 9074 : 1989, Information processing systems - Open
e) an implicit basis for comparison of the FDTs.
Systems Interconnection - Estelle - A formal description
technique based on an extended state transition model.
This Technical Report does not provide:
ISOKR 10023 : -' , Information processing systems -
Open Systems interconnection - Formal description of IS0
a) tutorials on the FDTs and the OS1 architecture; and
8072 (transport service definition) in LOTOS.
b) a means of formally mapping between descriptions pro-
CCllT T.70, Network-Independent Basic Transport Service
duced using different FDTs; and
for the Telematic Services (Red Book).
c) an explicit comparison of the FDTs.
CCllT Z. 100, SDL, Specification and Description L anguage
a
-
(Blue Book).
The definition of each FDT, a tutorial on its usage, and the
definition of the OS1 architecture are indicated in clause 2.
CCllT Z. 1 O0 Annex D, SDL User Guidelines (Blue Book).
The intended audience for this Technical Report is those
CCllT Z, 1 O0 Annex F, SOL Formal Definition (Blue Book).
who require to develop formal descriptions, and those who
CCllT 2.200, Open Systems Interconnection Basic Refer-
require to use FDTs generally.
ence Model(Red Book).
2 References
3 Terminology
The following standards contain provisions that, through
The following terms are referenced within the Technical Re-
reference in this text, constitute provisions of this Technical
port. Where a term is used with a particular meaning (e.g.
Report. At the time of publication, the editions indicated
an FDT concept, keyword, or variable) it is given in bold
were valid. All standards are subject to revision, so parties
face type.
to agreements based on this Technical Report are encour-
aged to investigate the possibility of applying the most re-
cent editions of the standards indicated below. Members
'To be published
ISO/IEC TR 10167 : 1991 (E)
3.1 Architectural Terms j) interpretation
k) model
The following terms are used in accordance with the defini-
I) non-determinism
tions in IS0 7498 and CClT X.200:
m) specification.
a) (N)-association
b) concatenation
c) (N)-connection
d) (N)-connection-endpoint
4 FDT General Characteristics
e) (N)-entity
f) (N)-facility
4.1 Introduction
g) flow-control
Formal Description Techniques exhibit different strengths
h) (N)-funbtion
with respect to their location on the range from abstract
i) multiplexing
to implementation-oriented descriptions. All FDTs offer the
means for producing unambiguous descriptions of OS1 Ser-
j) (N)-protocol
vices and Protocols in a more precise and comprehensive
k) (N)-protocol-data-unit
way than natural language descriptions.
I) segmentation
FDTs provide a foundation for analysis and verification of
m) (N)-service
a description. The target of analysis and verification may
vary from abstract properties to concrete properties.
n) (N)-sepice-access-point
Natural language descriptions remain an essential adjunct
O) (N)-setvice-data-unit
to formal descriptions, enabling an unfamiliar reader to gain
p) splitting.
rapid insight into the structure and function of Services and
Protocols.
The following terms are used in accordance with the defini-
tions in ISO/TR 8509:
4.2 The Nature and Purpose of FDTs
q) confirm
4.2.1 The Purpose of FDTs
r) indication
ISO/TC97/SC21 has developed International Standards for
s) request
two FDTs:
t) response
U) (N)-primitive
a) Estelle (based on Pascal, with extensions to describe
finite state machines); and
v) (N)-service-provider
b) LOTOS (based on the mathematical techniques CCS
w) (N)-service-user.
(Calculus of Communicating systems), CSP (Com-
For brevity, the above terms are referred to in this Technical municating Sequential Processes), and ACT ONE).
Report without the (N)- prefix (e.g. Service Access Point).
CCITT/SGB( has already developed and issued a Recom-
mendation for the FDT
3.2 FbTTerms
c) SDL (based on an extended finite state machine mo-
The following FDT terms are referenced within this Tech-
del with two concrete syntaxes, one graphical and one
nical Report. For those unfamiliar with FDT terminology, a
textual).
tutorial introduction is given in Annex B.
All three FDTs share a common basis, namely labelled tran-
a) abstract, abstraction
sition systems, for expressing dynamic behaviour. Estelle
b) action
uses Pascal data types for data description, while LOTOS
c) complosition, decomposition and SDL use Abstract Data Types.
d) constructive, non-constructive The objectives of FDTs are (in brief):
e) description
a) unambiguous, clear and concise specifications; and
1) formal, formalisation
b) a basis for determining completeness of specifications;
g) implementation
and
h) information
c) a foundation for anaiysing specifications for correct-
i) interaction ness, efficiency, etc.; and
EC TR 10167 : 1991 (E)
ISO/
more abstract
..
C) criteria for evaluating FDTs; and
-----
I I I
D) criteria for evaluating formal descriptions.
I I ,v --------
I check I 1 SPEC i 1
I consistency I I __________ I
4.3 Estelle
I l I I-
Estelle is a formally-defined specification language for de-
I l__-__l I I
scribing distributed or concurrent processing systems, in
I II
I refine I I check properties particular those which implement OS1 Services and Pro-
I ____ I I are preserved tocols. The language is based on widely used and ac-
I I I II cepted concepts of communicating non-deterministic state
machines (automata). An Estelle specification defines a
I I -v-_-v-l_-
I check I I SPEC i+l I
system of hierarchically-structured state machines. The
machines communicate by exchanging messages through
I consistency I I __________ I
I II bi-directional channels that connect their communication
I I ____ I ports. These messages are queued at either end of the
V channel. The actions of machines are specified in (ex-
more concrete tended) Pascal, hence familiarity with Pascal makes Estelle
specifications easily readable.
Estelle mechanisms allow modelling of synchronous and
Figure 4.1 : Development through Refinement
asynchronous parallelism between the state machines of a
specified system. They also permit dynamic development
of the system configuration.
Estelle specifications can be prepared at different levels of
d) a basis for determining conformanceof implementations
abstraction, from abstract to quite implementation-oriented.
to specifications; and
The latter may be derived from the former with the aid of
e) a basis for determining consistencyof specifications rel-
supporting tools. Since all Estelle concepts are rigorously
ative to each other: and
defined, Estelle tools which accurately reflect the language
1) a basis for implementation support
can be developed.
The use of an FDT imposes a discipline of attending to rel-
4.4 LOTOS
evant details, thus increasing confidence in the resultant
description. Although the development of tools was not
LOTOS is a mathematically-defined FDT, d
an explicit objective of FDTs, the rigorous nature of FDTs
large, well-established body of theory base
makes it possible to develop tools which assist in the cre-
and ACT ONE.
ation, analysis, and refinement of formal descriptions.
Having a well-defined mathematical foundation, it provides
a solid basis for both analysis and development of reliable
4.2.2 Use in Development
tools, including simulation, compilation, and test sequence
Each stage in the software (or hardware) development pro-
derivation.
cess can be pictured as in Figure 4.1.
The basic constructs of LOTOS allow modelling of sequenc-
The development process is a succession of such activities,
ing, choice, concurrency, and non-determinism in an en-
beginning with informal requirements and ending up with an
tirely unambiguous way. In addition, LOTOS permits mod-
implementation. Different languages, appearing at different
elling of both synchronous and asynchronous communica-
points in the specification-implementation spectrum, may
tion.
therefore be appropriate at different stages in the develop-
LOTOS may be applied to produce a specification of the
ment process.
allowed behaviours of a system, i.e the set of all behaviours
which may be observed of a conforming implementation.
4.2.3 Assessment of FDTs
Furthermore, LOTOS permits the description of allowed be-
FDTs are used to represent basic concepts such as ab-
haviours without describing how this may be achieved, or
straction, modularity, information-hiding, structuring, and
by describing particular mechanisms which achieve the re-
synchronisation, as well as more complex architectural con-
quired behaviour.
cepts. Later clauses illustrate these.
It is difficult to assess FDTs, since they differ in their techni-
4.5 SDL
cal aspects and in the goals of their application. However,
tutorial Annexes are provided to assist in this:
SDL is based on the extended finite state machine model
supplemented by capabilities for Abstract Data Types based
A) bibliography: and
on the initial algebra model (the same as used in the ACT
6) characteristics of FDTs; and ONE part of LOTOS). This combination is supported by a
ISO/IEC Ti? 10167 : 1991 (E)
not agree on a formal description: they may interpret the
well-defined formal semantics.
informal description differently.
SDL provides constructs for representing structures, be-
A high-level description is the basis for further develop-
haviours, interfaces, and communication links. In addition,
ment of the system. An advantage of using an FDT is that,
it provides constructs for abstraction, module encapsula-
since the specification language is defined exactly, com-
tion, and refinement. All of these constructs were designed
puters can be used in the development process. From the
to assist the representation of a variety of telecommunica-
high-level description more detailed descriptions can be de-
tions system specifications, including aspects of protocols
rived, leading finally to an implementation. At each step in
and services.
the design process, implementation decisions and restric-
SDL is quite widely used in the telecommunications com-
tions are made more explicit, being postponed as late as
munity, and is well supported by a variety of tools, some of
possible.
which are generally available.
Each detailed description or the implementation can be ver-
ified (with computer assistance) for conformance to the
4.6 Benefits of FDTs
specification it is derived from. A further advantage is
the possibility of deriving test sequences with expected re-
With a specification written in an FDT, an accurate descrip-
sponses for the final implementation; in principle, these can
tion of (system) behaviour can be given. Descriptions writ-
be derived from the original specification automatically.
ten so far with the FDTs mostly deal with the behaviour
A formal description gives the precise relationship between
of data communications services and protocols, and with
telecommunications switching systems. Other kinds of be- components of a system. If it is a description of a system
to be built, the formal description is a good basis for project
haviour can be considered for specification, for instance the
planning (allocation of resources, scheduling of component
description of the dialogue between a user and a system.
design, unit and integration tests, etc.).
A high-level description says exactly how a system should
An advantage of using FDTs is that the appropriate level
behave. It describesonly its behaviour, not the realisation of
of abstraction may be used. For example, a high-level de-
that behaviour (implementation details are excluded). The
scription may be given of what a system should do (its func-
description is also exact: there are no loose ends or spec-
tionality); such an implementation-independent description
ification gaps, and behaviour is described for all possible
would be appropriate in a definitive International Standard.
system inputs. When an input should give an undefined
Implementation-independence can also make descriptions
behaviour, this should be described as well.
re-usable for future systems (in a different environment or
The use of an FDT enforces a discipline on the specifier as
with different constraints) and can facilitate description of
to what information should be given and how it should be
re-usable software components. However, it may also be
presented. Although it might be felt by the specifier that this
advantageous to give a more implementation-oriented de-
discipline is very strict, the result is a much better quality
scription so as to assist the production of conforming imple-
description than would have resulted if natural language
mentations.
had been used. This benefit is obtained in addition to the
More detailed tutorial guidance on FDTs and their applica-
benefits from using automated analysis tools.
tion can be found in the Annexes.
Another problem with natural language descriptions is that
they often jump from one abstraction level to another. An
FDT gives better possibilities for structuring descriptions, 4.7 Tools for FDTs
and distinguishing between different abstraction levels.
The availability of tools for FDTs can be an important fac- 0
In a development process which uses a (formal) specifi-
tor in their application. The nature of these tools follows
cation language, several specification levels are generally
from the aspects of the application of FDTs described in the
used. Usually, the starting point is a rough idea of what a
previous section.
system should do. This idea is then written down in natural
There have to exist good tools for writing and changing
language. From this informal functional description a formal
descriptions. These tools could incorporate some kind of
description is derived (written in a specification language).
source version-control system to keep track of different ver-
In this process, exact requirements must be captured, and
sions. Furthermore, there should exist verification tools:
loose ends or fuzzy areas must be detected and resolved.
a description which is not checked for correctness loses
The resulting high-level description is an accurate repre-
much of its value as an exact description of a system or
sentation of the functions of the system.
an International Standard. When descriptions are written
Getting a complete and unambiguous high-level descrip-
using a computer system, it would be a waste not to use
tion before most of the design decisions are made is one
that computer system for verification of correctness.
of the most important benefits of using an FDT. Even if the
Several tools for FDTs can be considered. These tools can
natural language requirements are written very carefully, as
be divided into two categories, static and dynamic.
for the examples in this Technical Report, errors and omis-
sions are found. The problems with the ambiguity of natural
Static tools deal only with language aspects of the FDT
language descriptions is best illustrated by the fact that spe-
used for a description. Into this category fall (graphical)
cialists who agree on the natural language description may
(syntax-driven) editors, checkers for correct use of the FDT,
ISO/IEC TR 10167 : 1991 (E)
teaching tools, and static report-generators (reporting on The benefits of using such tools fall into three categories:
increasing confidence in the description of a system, reduc-
use of language constructs).
ing the costs of implementing a formally-described system,
When descriptions are written, a style must be chosen that
and producing an implementation in a systematic way.
is appropriate for the system to be described. The ‘best’
The current trend in tools development for FDTs shows that
style is rarely found at the first attempt. Static tools fa-
particular kinds of tools are likely to be developed for each
cilitate modifications of style, as well as modifications and
FDT. For example, the emphasis with Estelle has been on
extensions of the description.
the early development of compilers. In the case of LOTOS,
Dynamic tools deal with the behaviour of the specified sys-
simulators have been developed first. For SDL, graphical
tem. They can be used to verity whether the specified sys-
editors and top-down design aids have received priority.
tem will behave as the specifier wants (e.g. freedom from
(unwanted) deadlock or livelock). Useful tools in this area
are simulators, prototype generators, symbolic executors,
and tools for computer-assisted proving of properties like
absence of deadlock and livelock.
5 Guide to the Examples
The benefit of these tools is that it is possible, at an early
stage, to experiment with the system, thus giving confidence
5.1 Explanation of the Examples
in the correct behaviour of the system. If the description
is of a system to be built, dynamic tools help to discover
A careful choice has been made of a graded series of exam-
misunderstandings between the client and the specifier.
ples, given in each FDT. The examples have been chosen
with the following aims.
There should also be tools to verify whether the implemen-
tation conforms to the specification. It is hard to take large
steps in the design process (e.g. deriving a low-level imple- 5.1.1 Examples of Basic FDT Concepts
mentation from a high-level specification), but when step-
These are examples of concepts which are represented by
wise refinement techniques are used in the process of going
all FDTs. They are neutral with respect to any particular
from the specification to an implementation, verification can
FDT and to architectural concepts. They illustrate how the
be done for each refinement step. The tools in this cate-
FDTs capture some basic ideas of Information Theory.
gory include interpreters, simulators/animators, validators,
and test sequence generators. The benefit of these tools is
5.1.2 Examples of Basic Architectural Concepts
that they help to avoid the introduction of errors during the
design process.
These are more complex examples, drawn from concepts
Other possible tools include (interactive) generators of an defined in the OS1 Basic Reference Model and elsewhere.
implementation or prototype of the specified system. These They illustrate more specifically how FDTs can be used to
tools ease the burden of straightforward but error-prone represent OS1 concepts.
coding, giving the opportunity to concentrate on important
implementation decisions.
5.1.3 Daemon Game
The kinds of prototype tools for FDTs that are available or
This illustrates a small self-contained system. Although not
are being developed include:
presented as a Service or Protocol example, this is a gentle
lead-in to later, more realistic examples.
a) specialised editors to help produce or modify formal de-
scriptions; and
5.1.4 Sliding Window Protocol
b) formatters to produce pretty-printed text or graphical
This illustrates an important fiow-control and error-recovery
representations of formal descriptions; and
technique which is present in many real Protocols. In addi-
tion, it illustrates the description of a Protocol in relation to
c) verifiers and theorem-provers to analyse specification
its underlying Medium.
properties; and
d) parsers to detect lexical and syntactic errors, and to per-
5.1.5 Abracadabra Service and Protocol
form checks on static semantics (e.g. type-checking);
and
This illustrates the familiar Alternating Bit Protocol, which
is a precursor to some real Protocols. It also illustrates
e) simulators to aid interactive analysis of formal d
...