Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Semi-automatic protocol implementation using an Estelle-C compiler, LAPB and RTS protocols as examples Lu, Jing 1990

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1990_A6_7 L82.pdf [ 4.62MB ]
Metadata
JSON: 831-1.0051972.json
JSON-LD: 831-1.0051972-ld.json
RDF/XML (Pretty): 831-1.0051972-rdf.xml
RDF/JSON: 831-1.0051972-rdf.json
Turtle: 831-1.0051972-turtle.txt
N-Triples: 831-1.0051972-rdf-ntriples.txt
Original Record: 831-1.0051972-source.json
Full Text
831-1.0051972-fulltext.txt
Citation
831-1.0051972.ris

Full Text

SEMI-AUTOMATIC P R O T O C O L IMPLEMENTATION USING A N E S T E L L E - C COMPILER, L A P B A N D RTS PROTOCOLS AS E X A M P L E S By Jing Lu B. Sc. Beijing Computer Institute, China, 1984  A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE  in THE FACULTY OF GRADUATE STUDIES COMPUTER SCIENCE  We accept this thesis as conforming to the required standard  THE UNIVERSITY OF BRITISH COLUMBIA  August, 1990 © Jing Lu, 1990  In  presenting  degree freely  at  this  the  available  copying  of  department publication  of  in  partial  fulfilment  University  of  British  Columbia,  for  this or  thesis  reference  thesis by  this  for  his thesis  and  scholarly  or  her  for  Department The University of British Columbia Vancouver, Canada  DE-6  (2/88)  ?!  .  1 ^ °  I  I further  purposes  gain  the  shall  requirements  agree  that  agree  may  representatives.  financial  permission.  Date  study.  of  be  It not  that  the  be  Library  an  advanced  shall  permission for  granted  is  for  by  understood allowed  the  make  extensive  head  that  without  it  of  copying my  my or  written  Abstract  Formal Description Techniques allow for the use of automated tools during the specification and development of communication protocols. Estelle is a standardized formal description technique developed by ISO to remove ambiguities in the specification of communication protocols and services. The UBC Estelle-C compiler automates the implementation of protocols by producing an executable C implementation directly from its Estelle specification. In this thesis, we investigate the automated protocol implementation methodology using the Estelle-C compiler. First, we describe the improvements made to the compiler to support the latest version of Estelle. Then, we present and discuss the semiautomated implementations of the LAPB protocol in the CCITT X.25 Recommendation and the RTS protocol in the CCITT X.400 MHS series using this compiler. Finally, we compare the automatic and manual protocol implementations of LAPB and RTS protocols in terms of functional coverage, development time, code size, and performance measure. The results strongly indicate the overall advantages of automatic protocol implementation method over the manual approach.  ii  Table of Contents  Abstract  ii  List of Figures  v  Acknowledgement  vi  1  Introduction 1.1 Thesis Motivations and Objectives 1.2 Thesis Contributions 1.3 Thesis Outline  1 1 2 3  2  U B C Estelle-C Compiler 2.1 General Description of Estelle Language 2.2 Overview of the UBC Estelle-C Compiler 2.3 Evolution of the UBC Estelle-C Compiler 2.4 Enhancement of the UBC Estelle-C Compiler 2.4.1 Implementation Strategy 2.4.2 Transition and Trans-Action Routines 2.4.3 Run Time Execution 2.4.4 Other Enhanced Features  6 6 8 8 9 9 10 13 15  3  L A P B Protocol Implementation 3.1 Introduction 3.2 The Background 3.3 LAPB Semi-automatic Implementation Using the Estelle-C Compiler . . 3.3.1 Introduction 3.3.2 The User Module 3.3.3 LAPB Entity Module Specification 3.3.4 Phy Module Specification 3.4 LAPB Manual Implementation 3.4.1 Introduction of Threads System 3.4.2 The User Process 3.4.3 The LAPB Process 3.4.4 Sender and Server Process  18 18 18 19 19 22 22 30 31 31 33 33 36  4  R T S Protocol Implementation 4.1 Introduction 4.2 The Background 4.3 RTS Automatic Implementation Using the Estelle-C Compiler 4.3.1 Introduction 4.3.2 The Architecture Design 4.3.3 The Connections Between Module Instances 4.3.4 Association Establishment 4.3.5 Data Transfer  37 37 37 39 39 39 40 45 47  iii  4.4  4.3.6 Turn Management 4.3.7 Connection Release 4.3.8 Recovery 4.3.9 ASN.l Encode and Decode Routines U B C J D A C O M P T E RTS Implementation  49 49 50 51 52  5 Comparison Between Semi-automatic and Manual Implementation Methods 53 5.1 Introduction 53 5.2 Modularity 53 5.3 Transition Oriented Specification 54 5.4 Message Exchange Through Communication Channel 56 5.5 Nondeterminism 58 5.6 Parallelism 58 5.7 Exceptions 59 5.8 Timer Facility 60 5.9 Debugging Facility 61 6 Comparison Between Semi-automatic and Manual Implementations for L A P B and R T S 63 6.1 Functional Coverage of LAPB Implementations 63 6.2 Functional Coverage of RTS Implementations 63 6.3 Performance Analysis of LAPB Implementations 65 6.4 Performance Analysis of RTS Implementations 66 6.5 Size of Code and Developing Time for LAPB Implementations 69 6.6 Size of Code and Developing Time for RTS Implementations 71 7  Conclusion and Future Work 7.1 Conclusion . . -.  73 73  7.2  74  Future Work  Bibliography  76  A  80  MR_Channel  B Variant Record  81  C RS.Channel  82  D The Parameters for Interactions in RS_Channel  84  E  90  Test Cases  iv  List of Figures  1.1  OSI Reference Model  5  2.2  Transition Routine  12  2.3  Trans-Action Routine  13  3.4  X.25 Introduction  20  3.5  Automatic L A P B Implementation  21  3.6  L A P B States and Transitions  23  3.7  Manual L A P B Implementation  32  4.8  R T S Implementation in Estelle  41  4.9  Round Trip of A Connection Request  44  6.10 The Execution Time for L A P B  65  6.11 The Execution Time for R T S Test Cases  68  6.12 Size and Developing Time Comparison for L A P B  70  6.13 Size and Developing Time Comparison for R T S  71  v  Acknowledgement  First of all, I would like to sincerely thank my supervisor, Dr. Son T. Vuong, for his guidance, commitment, and support throughout my graduate studies at UBC. I would also like to express my thanks to Hendra Dany, Helen See, Viola Lee, Murray Goldberg and Ann Lo, for their help and suggestion during my thesis work. Thanks to Dr. Samuel T. Chanson for being the second reader of this thesis, and also for his invaluable comment on the earlier draft of this thesis. Thanks to the Department of Computer Science for providing me with the computing equipment and financial support during my graduate studies at the University of British Columbia. At last, I am indebted to my husband and my parents for their love, patience, and encouragment.  vi  Chapter 1  Introduction  1.1  Thesis Motivations and Objectives  Communication protocols play a key role in computer networks and distributed systems. They need to be specified and implemented completely, precisely and efficiently. The real world protocols are generally very complex. The complexity is managed by structuring a communication system into a set of layers in the ISO/OSI Reference Model. Each layer of this model has well defined interfaces to layers above and below. The OSI Reference Model is shown in Figure 1.1. The protocol specification is usually realized using a suitable Formal Description Technique (FDT). Among other advantages over an informal method, the use of a formal description technique allows for automated processing using software tools for protocol verification, implementation and testing. The development of Formal Description Techniques has proceeded with research and development of the tools for the design, validation, implementation and testing of communication protocols. Based on standard FDT's such as Estelle, LOTOS and SDL, a number of compilers and interpreters have been developed to automate the process of protocol implementation. This new approach of protocol implementation has been claimed to be superior to the traditional methods that depends entirely on manual implementation [12], [14], [22].  1  C h a p t e r 1.  Introduction  2  The potential advantages of this new approach are as follows. The protocol implementations can be generated automatically to save developing time and to reduce human errors during the implementation process. The automatic generated implementation, in a standard target language, for example, C or Pascal, is always well-structured and easy to maintain. The system-dependent features of the protocol can be encapsulated into a few routines therefore the implementation is portable. Certainly the implementation should confirm to the protocol specification. The objective of this thesis is to investigate the automated protocol implementation methodology and to consolidate these findings. In the Department of Computer Science of UBC, an Estelle-C compiler has been developed to allow the automatic generation of protocol implementation. Since the UBC Estelle-C compiler became operational, it has been further enhanced many times. In this thesis work, two OSI protocols, a low level protocol LAPB and a high level protocol RTS, are implemented automatically using the UBC Estelle-C compiler. The viability of the automatic implementation method is investigated via these two protocol examples. The automatic and manual implementation methods are compared in many issues. The automatic generated implementations of LAPB and RTS have been also compared in terms of functional coverage, developing effort and performance measure.  1.2  Thesis Contributions  In this thesis work, further investigation on the automatic protocol implementation method has been performed, yielding the following contributions: • The UBC Estelle-C compiler has been enhanced to support the latest version of Estelle Formal Description Technique. It supports non-determinism properly which  Chapter 1.  Introduction  3  is needed by many protocol implementations. More Estelle features are now supported fully and successfully. • The experience of using the UBC Estelle-C compiler has been obtained by carrying out the automatic LAPB and RTS protocol implementation, which will be benefited by people who continue to work in the same area using the Estelle-C compiler. • The LAPB and RTS Estelle specifications and their compiler generated implementations have been completed. Their Estelle specifications can be useful for formal derivation of test suite for protocol conformance testing. • The coverage, development effort and performance analysis of LAPB and RTS protocol implementations for both automatic and manual implementation methods performed indicate that the automatic protocol implementation method is superior than the manual protocol implementation method.  1.3  Thesis Outline  This thesis is organized as follows: • Chapter 2 highlights the features of Estelle Formal Description Technique and describes the UBC Estelle-C compiler on its evolution and recent enhancement which is accomplished in this thesis work. • Chapter 3 presents the LAPB protocol implementation in both automatic and manual methods. In automatic method, the LAPB is specified in Estelle and submitted to the Estelle-C compiler to obtain its automatic generated C implementation. In manual method, the LAPB is implemented manually in C programming language with the help of the Threads system.  Chapter 1. Introduction  4  • Chapter 4 presents the automatic RTS protocol implementation using the UBC Estelle-C compiler and introduces the manual RTS implementation which is developed in UBC-IDACOM P T E project. • Chapter 5 describes the general comparison features of automatic and manual protocol implementation methods. These features are the advantages of employing FDT Estelle and the Estelle-C compiler, different programming styles between Estelle and C, and different execution environments in automatic and manual implementations. • Chapter 6 presents the coverage, developing time and performance analysis of LAPB and RTS implementations. The results are interpreted and discussed. • Chapter 7 is the conclusion of the thesis. Many advantages of automatic implementation method are presented in this conclusion. Suggestions for related future work are also offered.  Chapter 1.  Introduction  Application  5  application protocol  Application  ' •  presentation protocol Presentation  Session  Presentation  session protocol  Session  1  transport protocol Transpc)rt  *" Transport communication subnet boundary  Network  Data Link  Network  Network  Network  Data Link  Data Link  Data Link  Physical  Physical  Physical  •  Physical  X.25 Figure 1.1: OSI Reference Model  Chapter 2  U B C Estelle-C Compiler  2.1  General Description of Estelle Language  Estelle is a Formal Description Technique developed within ISO for use in describing OSI services and protocols. More generally, it is a technique for specifying distributed systems. It removes all the ambiguities in the specification of communication protocol. It is based on the observation that communication software is often described and implemented with an underlying finite automation model. Estelle builds on this by adding features to a simple finite automaton that facilitate writing complete descriptions of communication protocols and services. "Estelle" is derived from "ESTL" , standing for Extended State Transition Language. Modules and channels are the fundamental building blocks of Estelle. Modules communicate with each other through channels. Modules may be structured into submodules. In this section, we give a brief overview of the key ideas: module, channel, and structuring. The underlying model for an Estelle module is a finite state automaton. Finite automata is mathematical abstraction of computing devices. They are considered as machines, having a finite number of states. Transitions from state to state can be executed as consuming inputs. Finite automate comes in a number of variants and reads inputs and produces outputs as it makes transitions from state to state.  6  Chapter 2. UBC Estelle-C Compiler  7  In Estelle module, inputs and outputs, called interactions, are made through interaction points. Interactions received by one module from another are queued by the receiving module. Estelle modules act by making transitions from one state to another. The choice of which transition to take is determined by the current state and current input. Making a transition consists of consuming an input, changing state, and producing an output. Making a transition is called firing the transition. Estelle modules admit transitions that require no input, called spontaneous transitions, which may have time constraints placed on them that delay their firing. In addition, Estelle modules are non-deterministic, which means that the current state and current input determine a set of allowable actions, only one of which will be chosen. Modules are connected through channels. These channels form bindings from the output of one module to a queue associated with another module. When one module initiates an interaction, the interaction is placed in a queue of another module, as determined by the binding corresponding to the channel through which the interaction is sent. Channels do not allow arbitrary interactions to pass. Each channel has two ends, which are attached at interaction points of two modules. Each of these modules may initiate certain interactions and receive other interactions. An Estelle module may create and destroy other Estelle modules within itself, which are called children modules. The parent module may connect the interaction points of these modules to each other or to its own internal interaction points. It may attach its external interaction points to the external interaction points of its children, causing interaction point to be received by the child. It may also share its children's variables.  Chapter 2. UBC Estelle-C Compiler  2.2  8  Overview of the U B C Estelle-C Compiler.  The UBC Estelle-C compiler performs automatic protocol implementation in C from an Estelle protocol specification. Implementation dependent details in the Estelle specification are directly translated into a compilable C program. A set of pre-compiled, specification independent run-time support routines are linked to the compiled program to produce an executable program. This program becomes a dynamic implementation of a particular protocol. The UBC Estelle-C compiler has been studied for several years. It has been enhanceed for many times to support the updated Estelle features correctly and completely.  2.3  Evolution of the U B C Estelle-C Compiler  In the department of computer science of UBC, the Estelle-C compiler has been under study since 1984. A semi-automatic compiler was completed in 1985 [9]. This compiler accepts the 1984 version of Estelle [6] and with slight user-modification, produces an implementation in C. Later on an automatic Estelle-C compiler has been developed in 1987. This compiler completely automates protocol implementation by eliminating all user-modifications previously required. Run-time support routines contain only specification independent codes. The implementation details are directly translated into C programming language. This compiler accepts the 1986 Second DP version of Estelle [7]. This version has provisions for dynamic reconfiguration of the various entities in the specification. Transitions are allowed to take place in modules at any level of the module hierarchy in accordance with the Estelle language semantics. Parent modules are allowed to dynamically create and destroy child modules, as well as to dynamically connect and disconnect channels. These features are fully supported by the compiler using a tree-based data structure.  Chapter 2. UBC Estelle-C Compiler  9  Recently, a new version of the UBC Estelle-C compiler has been accomplished. It was modified and updated to accept a greater subset of the Estelle language. This latest compiler conforms to the 1989 ISO IS 9074 Estelle document [8]. The compiler has been tested on the SUN 2, SUN 3 and a micro-VAX II running the UNIX operating system and the compiled code has been successfully tested on the SUN 2, SUN 3 and VAX/750. Both the compiler and the compiler generated code should be portable to any system supporting the C language, however, with the combination of the run time support library routines.  2.4  Enhancement of the U B C Estelle-C Compiler  2.4.1  Implementation Strategy  The compilation of an Estelle specification is a two stage process. In the first stage of the translation, the Estelle-C compiler directly translates the Estelle specification into a set of compilable C functions. In the second stage, these C functions are compiled and linked together with a set of run-time library routines to produce an executable program implementing the Estelle specification. These support routines consist of a main driver, a scheduler and routines to manipulate the specification independent details. These routines cooperate with the compiled code to convert a static Estelle specification into a dynamic implementation. The translation details of the Estelle specification and the implementation details of the Estelle-C compiler can be found in [12]. This thesis will focus on the modification and enhancement of the new version UBC Estelle-C compiler. During the Estelle to C translation, each module has been translated into two routines. The initialization routine which is translated from initialization part when INIT statement has been reached. The transition routine is generated from the transition  Chapter 2.  UBC Estelle-C  Compiler  10  part of the module and implements the extended finite state automata representing the module. The primary purpose of the transition routine is the non-deterministic selection of a transition from amongst those transitions which are enabled. This transition is then returned to the scheduler which determines whether or not the transition will actually be fired in that computation step. Only one transition, either normal transition or spontaneous transition, can befiredin one computation step for each module instance. When the Estelle-C compiler generated C program first begins execution, the main driver calls the generated function from the outermost specification module FDTSPECIFICATION() to instantiate the specification module and execute the initialization transitions. Once any underlying submodules have been instantiated and connected, the main driver builds a list of all the sub-systems in the specification. The scheduler then gains control and begins a new computation step by building a list of transitions which are ready to befiredwithin a given sub-system. This is accomplished by calling the transition routines for all modules in that sub-system, bearing in mind the ancestor- descendant priority. Then all the transitions returned by the sub-system which is specified as system attribution, and only one of the transitions returned by the sub-system which is specified as activity, can be executed. The computation step then ends and the scheduler repeats this process for another sub-system. In this manner synchronization is achieved within a sub- system and asynchronization is achieve between sub-systems. 2.4.2  Transition and Trans-Action Routines  For the purpose of achieving non-determinism and also the efficiency of the execution, the transition routine has been modified from previous version and the trans-action routine has been added in. The skeleton of the transition routine for a module, which is generated from the  Chapter 2. UBC Estelle-C Compiler  transitions of the module, is illustrated in Figure 2.2.  11  Two parameters are used to  pass information to and receive information from the transition routine. The process parameter is a pointer to the FDTPCB for the module and the signal parameter is used by the transition routine to return to the scheduler any interactions which are to be processed with the transition selected to fire. Each transition in every module in the specification is assigned a unique transition number. The transition routine builds a list of those transitions which may be enabled in the current computation step and non-deterministically selects one of these as ready to fire. It then returns to the scheduler the number of the transition which is ready to fire. If no transitions are enabled, the number zero is returned. Within the routine, the local variable lvar is used to facilitate access to the module's FDTLVAR block. The arrays of actionJist and signal-list are used to build the list of enabled transitions and the interactions associated with those transitions, if any. Trans Jndex and signal index are used to access these arrays in an efficient manner and the count variable keeps track of the number of transitions in the list. The remaining variables are used in conjunction with the code generated for the WHEN clause. The body of the transition routine consists only of the code generated to check the enabling clauses of a transition. If these enabling clauses are passed, the transition's number is added to the actionJist array and any related interactions are placed in the signal-list array. After all transitions in module have been checked, the transition routine randomly selects one transition from the list and returns this to the scheduler with the associated interaction. The code generated for the body of a transition is placed into a function called the trans_action routine Figure 2.3 This routine contains as the clauses of a switch statement the code generated for all the transition bodies in the specification. These clauses are ordered by their transition numbers. The trans_action routine is passed by the scheduler  Chapter 2. UBC Estelle-C Compiler  module_name ( process, signal ) FDTPCB *process; FDTSCB **signal;  •C FDTLVAR *lvar = (FDTLVAR *) process->lvar; int action_list[COUNTmodule.name]; FDTSCB *signal_list[COUNTmodule_name]; FDTSCB *interaction, **sig_index = signal.list; FDTCCB *channel; register int count=0, cid, priority = -1, *tran_index=action_list; /* Code to implement the guard for transition no.l */ { /* Add transition no.l to the l i s t */ *tran_index++ = 1 ; count++; *sig_index++ = interaction; } /* Code to implement the guard for transition no.2 * / { /* Add transition no.2 to the l i s t */ *tran_index++ = 2 ; count++; *sig_index++ = (FDTSCB *) 0; }  \  /•Select one of the transitions at random from the l i s t i f (count) { count = r and ()'/.count; •signal = signal_list[count]; return action.list [count]; } else return 0; }  Figure 2.2: Transition Routine  Chapter 2. UBC Estelle-C Compiler  13  /* Transition action declarations. */ FDTtrans.f ire(transitions) trans_list *transitions; { FDTPCB *process; FDTSCB *signal; FDTSVAR *svar; FDTLVAR *lvar; if (transitions->trans_num) { do { CurrBlock = process = transitions->pcb; lvar = (FDTLVAR *) process->lvar; switch (transitions->trans_num) { case 1 : /*Code generated for transition no.l */ break; case 2 : /*Code generated for transition no.2 */ break; case n : /*Code generated for transition no.n */ break; > } while ((++transitions)->trans_num); } }  Figure 2.3: Trans-Action Routine a list of transitions which are ready to be fired. For each transition in the list it sets the variable process to the FDTPCB of the module containing the transition, the variable signal points to the interaction associated with the transition and then the code for the transition body is executed.  2.4.3  Run Time Execution  All the code generated by the compiler represents only a static description of the Estelle specification.  It is the run-time routines which provide the means of converting this  static picture to a dynamic entity. The first of these, the main driver begins by calling  Chapter 2. UBC Estelle-C Compiler  14  FDTSPECIFICATION() to create the initial module hierarchy for the specification. It then calls the scheduler initialization routine FDTSCHinitQ which builds as a list of all the sub-systems in the specification. This is done by checking the class of every instantiated module in the specification and adding it to the scheduler's list if the module is a systemprocess or a systemactivity module. This list maintained by the scheduler is a circular queue of FDTPCB pointers to all the sub-system root modules in the specification. Since by definition a system module has no ancestors, these root modules are static and may never be destroyed nor new ones created. Thus the sub-system list is created once and need never be updated. The scheduler also maintains two lists of enabled transitions which are ready to fire. The first list, process-transitions, is a list of those transitions from process or systemprocess modules. The second list, activity-transitions, contains those transitions from activity or systemactivity modules. For every sub-system in the list, the scheduler performs a modified pre-order traversal of the module hierarchy tree bearing in mind the ancestor-descendent priority. Thus, if a module contains a ready to fire transition, none of that module's children are checked by the scheduler for enabled transitions. At the start of each new computation step, the scheduler begins with the root of the sub-system and calls the module's transition routine to determine whether there are any transitions ready to fire. If the transition routine returns a transition number, the scheduler places it in the appropriate list and proceeds to check the module's siblings. If the module has no enabled transitions, the scheduler goes on to check the module's children or, if the module has no children, it checks the module's siblings. This process continues until all modules in the system have been checked and from the list of ready to fire transitions returned by the activity modules, the scheduler selects one at random and adds it to the process-transitions list. This list is then passed to the  Chapter 2. UBC Estelle-C Compiler  15  TransAction routine for firing of the transitions " in parallel". The computation step then ends and the scheduler continues with the next sub-system. Since this list of sub-systems is circular, this process will go on indefinitely. The cumulative effect of this process is that transitions of process and systemprocess modules are fired in parallel and transitions of activity or systemactivity modules are fired sequentially.  2.4.4  Other Enhanced Features  There are some more enhanced features in the new version of this compiler: • Internal Interaction Point: for the channel whose both end IPs can be put inside same module, the channel can be specified as the normal channel in channel declaration part and module head part. Internal interaction points may be used to exchange interactions within a module instance or to exchange interactions with a child module instance. Internal interaction points may be bound using connect operations and unbound using disconnect operations. • Pascal CASE statement: The case constants list should be declared first. On the execution of the case statement, the case index should be evaluated by the case constants list. The elements inside the case statement no matter which index should not be duplicated. The CASE statement directly translates the Pascal CASE to a C-language SWITCH statement. Each item in all the selector lists are given an individual CASE within the generated SWITCH statement. This is why problems can occur when the user's selector lists are not disjoint. If the lists had common elements, then several case statements may be duplicated: this is illegal in C. The Appendix B is also a good example for using case statement. • Pascal Variant Record and Pointers: Both variant record and pointers are fully supported in this new version compiler. The use of variant record is shown in  er 2.  UBC Estelle-C Compiler  16  Appendix B. Both variant record and pointers can be successfully passed as modifiable parameters either in procedure calling or interaction transferring through interaction point. Priority clause: A priority clause serves to order transitions with respect to priority constants , the lowest positive integer is the highest priority. It is one of the elements taken into account while selecting Arable transitions in a state from these enabled. Array type: it has been enhanced in new version compiler. Except for the normal array type, array of integer, array of character, it can also be used as array of structured record. Any type of array can be passed as modifiable parameter either in procedure calling or interaction transferring through interaction point at the end of channel. Delay clause: Both delay(timeO), and delay(timel, time2) have been implemented. Delay clause can be used to determine the starting execution time of a Arable transition. The transition should be fired as the time period timeO is over for delay(timeO), or later than timel and no later than time2 for delay(timel, time2). The delay clause can also be used to implement timer which is quite often needed in protocol implementation. Some of methods can be used, i.e having a timer module to manipulate one or more timers in a group of transitions using delay clause, or having a delay clause in the transition needs to be controlled by timer while associated with a boolean flag variable to avoid timer on and off confusing , depending on the certain requirement for protocol implementation. Release is fully supported. The result of a release statement is that first all external interaction points of the module instance identified by the module variable which have been attached or connected are detached or disconnected, and second, the  Chapter 2. UBC Estelle-C Compiler  17  module instance and all its descendent instances are released and are no longer available. • All statement: The all statement is implemented in two ways, one for ordinal types and one for module types. With ordinal types, the domain variable is generated and assigned to each ordinal value using a for loop. The statement within the all statement is then executed for each ordinal value. With module types, the domain variable is also generated and assigned to each child module of the specified module type. This is also done inside a for loop where the statement is executed for each child chosen. However, this time, the modules are determined nondeterministically. • Forone statement: The Forone statement is implemented in much the same way as the all statement except for two differences. The first is that provision is made for the optional SUCHTHAT condition. When a SUCHTHAT is found, an equivalent IF condition is generated inside the for loop. The second difference is that the for loop does not go through the entire domain -it stops as soon as it randomly finds a domain element that satisfies it's SUCHTHAT condition, if one exists. • Exist cause: The EXIST clause uses library routines written for the ALL and FORONE statements. Like other transitions, it generates an if statement to represent the guard. Before this if statement is generated, however, a FOR statement similar to the FORONE statement's loop is generated to see if there does exist a module with the given SUCHTHAT condition.  Chapter 3  L A P B Protocol Implementation  3.1  Introduction  X.25 is a set of protocols and various protocol layers making up the network access control, which has been defined to interface between a D T E (Data Terminal Equipment) and a DCE (Data-Circuit terminating Equipment). LAPB is one of the sublayers of X.25. It performs link management and data transfer between the DTE and the DCE. In this chapter, firstly LAPB is implemented in a automatic manner using the UBC Estelle-C compiler. The LAPB protocol is specified in Formal Description Technique Estelle, and then submitted to the UBC Estelle-C compiler to get the automatic generated C implementation. Secondly, the LAPB protocol is implemented manually in C programming language for the purpose of comparison between automatic and manual implementation methods.  3.2  The Background  The internationaly agreed network access protocol that has been defined to interface a D T E to a Packet-Switched Data Networks is X.25. It is in fact a set of protocols and the various protocol layers making up the network acess control. At the lowest layer, i.e. physical layer, the X.21 interface standard is used to define the physical interface between the D T E and the DCE. The data link layer protocol used with X.25 is a version of the HDLC protocol known as LAPB. The function of LAPB protocol is to provide the  18  Chapter 3. LAPB  Protocol Implementation  19  packet layer with an error-free packet transport facility over the physical link between the DTE and its local DCE. The physical interface between the D T E and the local DCE is denned in recommendation X.21. The data link layer is often referred to as layer 2 because of its position in ISO Reference Model (Figure 1.1). It is to provide the packet layer with a reliable packet transport facility across the physical link between the D T E and the DCE. In the context of the ISO Reference Model, the packet layer is the same as the network layer. Also, because of its position in the reference model, the packet layer is often referred to simply as layer 3. The transport layer thus uses the services provided by the packet layer to enable it to exchange Transport PDUs with remote transport layers. The frame structure and error and flow control procedures used by the link layer are based on the HDLC protocol. HDLC is a link-level protocol that has been defined by the ISO for use on both point-to-point and multipoint data links. It supports full-duplex, transparent-mode operation and is now extensively used in both terminal-based networks and computer networks. It uses the ABM (Asynchronous Balanced Mode) of operation, which is also referred to as LAPB in the CCITT X.25 standards documents. This stands for Link Access Procedure Version B since it superseded the earlier Version A link access procedure.  3.3 3.3.1  L A P B Semi-automatic Implementation Using the Estelle-C Compiler Introduction  The LAPB protocol is specified in FDT Estelle by building up three modules with the attribute of process (six module instances) and their connections between adjacent module instances. The LAPB entities on different machines are managed to communicate each other using a number of run-time support socket connection routines. These routines  Chapter 3. LAPB Protocol Implementation  20  Figure 3.4: X.25 Introduction have been accomplished using UNIX Inter Process Communication (IPC) facilities under Sun-4.0 system. During the run time execution, the Estelle-C compiler generated LAPB implementation in C is executed with the combination of these run-time support socket connection routines. The three process modules are : User module: stands for the upper layer entity as LAPB user to pass the user primitives through the Service Access Point to the data link layer LAPB entity. LAPB module: which is the LAPB specification itself, it takes upper layer primitives and processes them. It can send PUDs to lower layer entity and also can receive PDUs from lower layer entity which is virtually from its peer LAPB entity cross machine. Phy module: stands for physical layer entity. It transmits LAPB Protocol Data Units (PDUs) to and from remote machine. Figure 3.5 shows the structure of the general design of LAPB automatic implementation.  Chapter 3. LAPB  Protocol  21  Implementation  USER MODULE;  USER MODULE  user primitive  user primiti ves LAPB  LAPB  MODULE  MODULE  PDl s  PDUs  PDUs  PHY MODULE  PDUs  PHY MODULE  datagram  datagram  socket connection between remote host Figure 3.5: Automatic L A P B Implementation  Chapter 3. LAPB  3.3.2  Protocol Implementation  22  The User Module  The user module is designed to send following messages to LAPB entity module: host_ready : telling LAPB entity that user is ready to start using LAPB protocol. LAPB entity receives this message to reset corresponding variables, buffers and etc. to prepare transmission. However LAPB entity only accepts this message under SABM state. This message is ignored under any other state. host-busy : telling LAPB that user is busy with something else and can not handle the coming information message, but not refusing to handle the supervisory message. disc_req: telling LAPB entity that user wants to stop transmitting message. data-req : telling LAPB entity that user is ready to transmit one message through LAPB entity. Those messages are sent through the predeclared channel which connects the user module and LAPB module. The messages associated with interaction points are declared as above.  This module actually controls the protocol execution, such as how many  messages are transmitted and when the protocol stops. 3.3.3  L A P B Entity Module Specification  This LAPB is specified according to the Packet-Switch Protocol documentation. The Finite State Machine (FSM) structuring the LAPB protocol is describted in the documentation. The six states in the FSM, the state changing and transition processing are shown in the Figure 3.6.  Link Set U p The user module instance sends the host_ready primitive to the LAPB entity module instance DCE and DTE, assuming they are ready to start running LAPB protocol. DCE  Chapter 3. LAPB Protocol Implementation  sstate  INIT 1  input  SEND DM SEND SABI* [ 2 3  UA  SABM  UA *  A 4  •  A 4  DM  UA  IGNORE  IGNORE  DM  IGNORE  SABM  I  IGNORE  IGNORE  FRMR  IGNORE  SABM  IGNORE  IGNORE  IGNORE  DM  *  +- 4  3  PROCESS  2  BAD COMMAND  IGNORE  IGNORE  DM - 2  BAD RESPONSE  IGNORE  IGNORE  N2XT1  SABM *-  DM +• 2 SABM  9  SABM  UA DM  *• 2 DM *• 2  9.  DM  DM •>  DM  DM SABM  *2  4  UA  IGNORE  IGNORE  DM *• 2  *  *" 2  RR,RNR,RE. IGNORE (RESPONSE  Tl  UA  UA  DM  IGNORE  )  WAIT SAB* [ WAIT UA 5 6  ABM 4 UA  UA  DISC  RR,RNR,RE, (COMMAND  23  SABM  *2 +• 4 SABM *• 6  *3 FRMR  IGNORE  DM  IGNORE  PROCESS  FRMR  IGNORE  PROCESS  IGNORE  IGNORE  FRMR  IGNORE  IGNORE  IGNORE  FRMR  SABM  SABM »6  DM  SABM  FRMR  5  FRMR • .5 I(poll) (if any) SABM • 6  6  Figure 3.6: L A P B States and Transitions  •2  Chapter 3. LAPB Protocol Implementation  24  and D T E enter the Initial State upon receiving the host_ready primitive. After D C E enters the Initial State, it sends the "DM" primitive to the DTE. It changes the state from INITIAL to SEND-DM and starts the timerl. When timerl is out the DCE retransmits the "DM". After N2 times of timerout, D C E sends a "SABM" primitive to the D T E . It enters SABMJSENT state and starts timerl. D T E gets the "DM" N2 times but ignores them. Eventually D T E gets "SABM" under INITIAL state, it sends a "UA" to response the DCE and changes its state from INITIAL to ABM. DCE will receive that "UA" response and change its state from SEND-SABM to ABM. At this moment both DCE and D T E get in A B M state and are ready to transmit information frames. Both DCE and D T E module instances stop all the timers and reset all window variables for ending the link setup procedure. One thing should be mentioned here is that even some coming messages can be ignored (see the Figure 3.6), their transitions should be still presented in the LAPB entity module specification. When the message comes the Estelle-C compiler will pick it up from the Interaction Point of the channel connecting LAPB and its user module. For example, when D T E under INITIAL state, the "DM" can be ignored. However there should be a transition from INITIAL when r.DM begin end; Without this transition to pick up the N2 of "DM"s , all the coming messages will be jammed in the queue associated with the Interaction Point and the D T E will never get the "SABM" primitive which it is waiting for.  Chapter 3. LAPB Protocol Implementation  25  Information Frame Sending When LAPB entity module gets a Data_Req primitive from its user module, it understands that its user passes an information frame needed to be sent to remote station. It will call the procedure set_frame() to set up the Information Frame (Iframe). The LAPB entity will transmit the Iframe with setting its parameter variable ns equal to its window variable vs, and parameter variable nr equal to its window variable vr. After sending the Iframe the vs is increased by 1 with mod k. This Iframe should be buffered in retxbuffer before it is acknowledged by its peer LAPB entity. The timerl is started when an Iframe is sent out. When timerl is out the Iframe just buffered for acknowledgement should be retransmitted. And the timerl for this Iframe can be stopped by coming acknowledgement, i.e the Iframe acked will be debuffered from retxbuffer. The size of retxbuffer is equal to the MAXSEQ+1. If the number of buffered Iframes is greater than MAXSEQ+1, the Iframe sequence number will be overlaped. The Iframe sending should be stopped when the retxbuffer is full. The LAPB entity can start sending Iframe after debuffering an Iframe upon receiving the acknowledgement. Information Frame Receiving When an Iframe arrives, it is accepted if its parameter variable ns is equal to the window's vr. The window variable vr is the number of the Iframe the current LAPB waiting for. By accepting the Iframe, the vr is increased by 1 with mod k, and timer2 is started. The acknowledgement for this Iframe should not be sent at this moment, it will be piggybacked in next outsending Iframe or be sent when timer2 is out. Whenever LAPB receives the Data_Req primitive from the user module, it will check if timer2 is on or not. If timer2 is on, the outsending Iframe will piggyback the current  Chapter 3. LAPB  Protocol Implementation  26  acknowledgement which is equal to window variable vr, by setting pf = 1. If timer2 is not on, the LAPB sends an Iframe with pf = 0. When timer2 is out, it indicates there is no piggyback within the timer2 period. Then RR_cmd will be sent to acknowledge the corresponding Iframe. If the coming Iframe's ns is not equal to window's vr, it will be rejected. The REJ_cmd will be sent out by setting its nr with window's vr to inform the remote LAPB entity which number of Iframe the current station is expecting.  Receiving Acknowledgement There may be two kinds of acknowledgements: Iframe with pf = 1, or RR_cmd. When the acknowledgement is received, the Iframe buffered in retransmission buffer should be released. The corresponding action in this specification is that retxprt (retransmition buffer pointer) increases by 1 with mod k and window variable nubuffered (number of buffered Iframes in retransmission buffer) decreases by 1. When host is busy, the LAPB entity is not supposed to process the coming Iframe. It needs to check the coming Iframe. If the Iframe's parameter pf is set, it piggybacks an acknowledgement. The LAPB entity will take the acknowledgement and debuffer the acknowledged Iframe. At this moment the timerl should not be stopped because it is shared by all buffered Iframes. It can only be stopped when the nubuffered is less than 1. Receiving Reject The REJ_cmd can inform the receiving LAPB the number of Iframe which the peer LAPB in remote station is waiting for. When LAPB entity receives an REJ_cmd, it will send the Iframe that remote station requires. It calls the procedure getretxframeQ to get  Chapter 3. LAPB  Protocol Implementation  27  that Iframe in retxbuffer which sequence number should be equal to the nr associated in REJ_cmd. Host Busy Condition There are two kinds of busy conditions, current station is busy (busymyself is true) or remote station is busy (busyremote is true). If current station is busy, the user module doesn't send data_req to LAPB entity module. LAPB entity module does not send any Iframe at this moment. If current station is busy, the LAPB entity module refuses to receive any Iframes but still processes the supervisory frames. When LAPB entity module receives a host-busy from user, it changes to myself busy condition by setting myselfbusy is true. It sends an RNR_resp to remote station. The myself busy condition will be cleared when the current LAPB entity receives an clear-busy from user module. The LAPB sends a RR_resp to the remote station. After LAPB entity module receives the RNR_resp, it changes to the remotebusy condition by setting remotebusy is true. The remote busy condition is cleared by receiving a RR_resp from remote station. If remote station is busy, the current LAPB entity module stops sending the Iframes to remote until the remote busy condition is cleared. Because the remote station does not refuse to process supervisory frame even it is in busy condition, the supervisory frames i.e RR_cmd, discxmd and etc, can still be sent out. Link Disconnect Condition When LAPB entity module receives the disc_req from user module, it means that user wants to stop the transmission through LAPB protocol. LAPB entity module will start the link disconnect procedure. The entity sends discxmd to remote station and sets discmyself is true. When discmyself is true, current LAPB entity module stops sending anything out, but can not  Chapter 3. LAPB Protocol Implementation  28  refuse to receiving coming messages until receiving disc_resp. When remote station receives disc^cmd, it sends out discresp and stops running LAPB protocol. When current station receives disc_resp, it stops running LAPB protocol too. This disconnection procedure guarantees that no message has been lost during the disconnection procedure.  P D U Encoding and Decoding Every LAPB PDU contains the following items in the form of interaction parameters: • address: the address of the station the message comes from, DCE or DTE in this program. • control: type of the message, it can be INF for information frame, SUP for supervisory frame, and UNB for unnumbered frame. • ns: for information frame, it tells the receiver that sequence number of the coming information frame. This ns is assigned to be window variable vs. • nr: for information frame, it tells the receiver that acknowledgement from sender if pf is equal to 1. This ns is assigned to be window variable vr. It also includes the acknowledgement when the RRxmd is sent while pf is set. • pf: as Iframe, when it is set, it indicates the acknowledgement is piggybacked. As Uframe when pf is set, it indicates the sender site is polling for an Iframe. • udata: transmitted user data. In Estelle specification, this PUD can be implemented as structure, pointer, and variant record. Experience indicates the new Estelle-C compiler works for any type. In order to pass this kind of PDUs around module instances, the PDU components can be describted as parameters of interactions sent through the individual interaction point.  Chapter 3. LAPB Protocol Implementation  29  In this Estelle specification the interaction holding the LAPB PDU components is declared as record.  ftype = RECORD address: control: ns : pf : nr : udata : END;  addr.type; control_type; INTEGER; {sequence no of frame} bit_type; INTEGER; {expected ack no} INTEGER;  frametype = ftype; This kind of record is placed as parameter of interactions. These interactions refer to the information frame and supervisory frame.  CHANNEL link.channel (send_role,recv_role); BY send_role: DM; I(f: frametype); RR_cmd(f: frametype);  The interaction holding the LAPB PDU conponents can also be declared as pointer. As similar to above, the frametype is declared to be: frametype = A ftype. The encoding and decoding routines should be modified correspondingly. They can also be declared as variant record:  frametype =  RECORD case tag : control_type of INF: (address: addr.type; ns: integer; nr: integer; udata : INTEGER; pf: bit.type); SUP: (Saddress: addr.type; Snr: integer; Spf: bit_type); UNB: (Uaddress:integer); END;  Chapter 3. LAPB Protocol Implementation  30  then, set the interaction parameter:  CHANNEL link.channel (send_role,recv_role); BY send.role: DM; I(f: frametype); RR_cmd(f: frametype);  Before the interaction is sent to physical layer connection socket, it should be encoded as string of bits. It will be decoded when PDU is received from connection socket by remote station. There are PASCAL-liked encode and decode procedures to perform the encoding and decoding functions.  3.3.4  Phy Module Specification  This module takes responsibility to pass the local LAPB PDU to remote machine through preconnected UNIX socket, and to receive the coming PDU from the connected socket to local LAPB entity. The procedures to manage the socket connections are written in C. The Estelle-C compiler has the ability to run the automatic generated protocol implementation with the combination of C support routines. These C support routines are different from run-time library support routines. They need to be specified in the protocol Estelle specification. In this Estelle specification, a pair of sockets are connected when phy module is initiated, that is when the protocol starts execution. Whenever the socket is connected to some other machine, it will not be disconnected until the protocol stops execution. Therefore, during the protocol execution, PDUs can be sent and received through that socket at any time. This module is connected to LAPB module by predeclared Estelle communication channel. After the PHY module instance receives a message from the socket, it passes the message to its upper level LAPB module instance through the predeclared Estelle  Chapter 3. LAPB  Protocol Implementation  31  communication channel.  3.4  L A P B Manual Implementation  The LAPB protocol is implemented in C on Sunworkstation with Sun-4.0 operation system. Threads IPC environment is employed especially for process creation and inter process communication [30]. According to Estelle specification, the user, LAPB and phy Estelle module are substituted by corresponding Threads processes. User and LAPB processes are similar to Estelle module, but phy Estelle module is spilted into server and sender Threads processes to take the responsibility of transmitting PDUs. There are also two more timer processes to implement the LAPB timerl and timer2. To support cross machine message transmission, the same run time support socket connection library routines are used as in Estelle implementation for the purpose of consistency. Figure 3.7 shows the structure of the general design of LAPB Implementation in C environment. 3.4.1  Introduction of Threads System  Threads is a sub-kernel operating system, it provides efficient and convenient process creation, deletion and communication primitives which are not available in Sun-4.0. Threads provides an environment suitable for running a group of cooperating processes especially good for protocol entities to simplify the developing and testing. All threads processes run in a shared memory space. Inter process communication primitives, the sleep facility and memory management routine allow for fairly fast memory allocation resistant to fragmentation. A Threads process has access to all existing libraries and UNIX system  Chapter 3. LAPB  Protocol Implementation  USER  USER  PROCESS  PROCESS  user primitive  user primitive  LAPB  LAPB  PROCESS  PROCESS  PDUs  PDUs  RECEIVE] I  SENDER  PROCESS  PROCESS;  PDUs,  PDUs  RECEIVE!:  SENDER  PROCESS  PROCESS;  datagram  datagram socket connect between remote host  Figure 3.7: Manual L A P B Implementation  Chapter 3. LAPB Protocol Implementation  33  calls. Some of the popular blocking UNIX primitives are rewritten in Threads so that when they are called, only the calling threads process is blocked, not the entire UNIX process. Threads processes communicate via Send(), Receive() and Reply() primitives. A sending process is blocked until some other process replies to it. A receiving process is blocked until some other process sends it a message. All Threads processes share one memory space, so no copying of data is . Instead, a pointer and a length are transferred on SendQ and Reply(). 3.4.2  The User Process  The user process is designed to perform the same function as Estelle user module. It also controls the protocol execution, such as how many messages are transmitted and when the protocol stops. It acts as the upper layer network user. The difference is primitive communication. In C implementation, Threads IPC system call Send(), Receive() and Reply() are used to pass the user primitives down to the LAPB Threads process. 3.4.3  The L A P B Process  LAPB implementation in C covers the same design features to perform link set up, information frame sending and receiving, acknowledgement sending and receiving, frame reject sending and receiving, host busy condition up and clear, and link disconnection. Indeed the C implementation is fairly different from Estelle implementation due to the different programming environment and the convenience or restriction of Threads IPC system.  Chapter 3. LAPB Protocol Implementation  34  Inter Process Communication Threads system provides Inter Process Communication primitives : SendQ, Receive() and Reply(). They are very convenient to use. Send() sends a message to the destination process and then is blocked until it gets a Reply from the receiver process. Receive() firstly checks for any process blocked afrer sending to the receiving process. If one is found, the coming message is read and the sender is placed on "waiting for reply queue". Otherwise, the receiving process is blocked pending some other process sending to it. After the destination process executes the ReceiveQ, Reply() replies an acknowledgement to the sender process. Then the sender process is unblocked.  Some Restrictions of Threads Threads is not a time-slicing system, context switches are performed only when Threads call are made by a Threads process. Execution inside a critical selection will not be interrupted as long as no Threads system call is made. Knowing when a context switch is likely to occur is useful when programming a number of cooperating processes, because it may cause problem in protocol implementation, in particular inside LAPB implementation. When Threads process LAPB is looping in Threads system call Receive(), LAPB is actually expecting message sending from either Threads process server() or user(). Server() and user() perform the functions of receiving and sending message respectively. But in some case, server() is looping in a function which is waiting for message from remote peer machine. At this moment, as long as the function has not being through, the Threads system call send(), will never be reached. Meanwhile the Threads process LAPBQ will be blocked in Receive() not because of nothing is received but because in process server() no context switching can be made to any other process. Therefore process LAPBQ can NOT receive any message either from serverQ or any other processes. The  Chapter 3. LAPB Protocol Implementation  35  whole implementation stucks in a deadlock. Of course this kind of problem can be avoided by using the Threads system call properly. There are 3 choices here: Firstly, a Threads system call can be put before getting in that critical function, i.e sending a dummy message to another process, the other process just simply ignores it. However IPC overhead is increased by doing this. Second choice is to put a Threads Receive() inside the loop of the server process to cause a context switch to unblock the LAPB process. But the problem is that Receive() is a blocking Receive(), if nothing would be received the process will be blocked forever. Another alternative is to put a Thread Sleep(l) here to cause the context switch to the blocked process. Even it is the shortest time to sleep as 1 seconds for Sleep(), it is supposed to be faster than first method because a set of Send() , ReceiveQ and Reply() takes about 3 seconds. However since Threads is not a time-slicing system it can not guarantee the process sleep exactly as the time desired. Experiment shows that in this circumstance, the time consumed to transit a number of message by employing this method is similar to employingfirstmethod. Sometimes it is a little slower than it. Finally, the first method is chosen in this implementation. Timer Process There are two timer processes to implement two timers. LAPB() process call threads system call Send() to pass start-timer, stop-timer primitive to corresponding timer process. The timer process calls Threads system call Sleep() to sleep the timer process itself for period of timer interval. When timer is out, it checks if the timer is not stopped. If so, it calls Send() to send a timeout signal to LAPB process.  Chapter 3. LAPB Protocol Implementation  36  P D U Encoding and Decoding Before message is sent through socket connection , or after received from peer machine, the similar encode / decode procedures are called. The encode / decode procedures are written in PASCAL in Estelle specification and they are written in C for manual implementation. Certainly they do not make much difference either on size or difficulty.  3.4.4  Sender and Server Process  The socket connection routines were firstly implemented in 4.3BSD UNIX and then SUN 4.0 UNIX both support TCP/IP connections across machines. Thesis routines provide an easy way to transmit a single packet (PDU) to simulate the physical layer of OSI Reference Model. The sender() and server() processes basically perform the same function as PHY module does in Estelle specification. They are written in C and implemented as two Threads processes. The reason to split into 2 Threads processes is to avoid sending block since Thread system follows a blocking send and blocking receive principle. When server() process is firstly created, it calls UNIX system calls bind() and connect () with specified host name to build up the socket connection between two remote machines. After connection is build up, the sever process keeps checking the socket which connects the peer machine. If there is any PDU coming, it passes the PDU to upper layer LAPB process by calling Threads Send(). The sender() keeps looping on Threads Receive() to wait any coming PDU from upper layer. If any one comes, it sends the PUD through pre-built socket to peer machine by calling UNLX system call send() with specified socket identification.  Chapter 4  R T S Protocol Implementation  4.1  Introduction  The Reliable Transfer Server (RTS) protocol, namely X.410 is one of a set of protocols for electronic messaging, namely the CCITT Recommendations X.400 series [3], [4]. In this chapter, the RTS protocol is specified in FDT Estelle, and then implemented automatically using the UBC Estelle-C compiler. For the purpose of comparison between RTS automatic and manual implementations, the RTS manual implementation developed in the UBC-IDACOM protocol testing project is introduced briefly.  4.2  The Background  With the Red Book of 1984, CCITT has issued a series of recommendations defining message handing system (MHS) [5]. MHS is rigorously based on the OSI layered model. The 7 layer OSI reference model is designed as follows: • layers 1-3 are covered by X.25 protocol, which is present in Chapter 3; • layer 4 is specified as a class 0 transport layer; • layer 5 is a session layer offering the services of the basic activity subset; • layer 6 is, as far as protocol is concerned, implicitly defined in recommendation X.410; it implements the notation of recommendation X.509;  37  Chapter 4. RTS Protocol Implementation  38  • layer 7 is subdivided into three functional groupings, which provide services to each other or to the human user; each of the functional groupings has an own peer-to-peer protocol. In the application layer, the three functional groupings are: • The User Agent Layer, comprising a number of User Agents (UAs). A UA is the interface to the human user, i.e. it offers to the user all services of the Message Handling System (MHS). The peer-to-peer protocol between UAs (called P2) is a connectionless protocol concerned with information contained in message headings (letter-heads in conventional postal services). • The Message Transfer Layer, comprising a number of Message Transfer Agents (MTAs). An MTA offers its services to one or more UAs, not directly to the user. The services are submission, delivery and relaying of messages; the MTA peer-topeer (called pl) is a connectionless protocol concerned with information to be found on letter envelopes. Messages submitted by and to be delivered to a UA are part of pl PDUs. • The Reliable Transfer Servers (RTS), which offers to MTAs a reliable PDU transfer service. Two interconnected RTS entities maintain a virtual " association", which is mapped onto a sequence of possibly aborted and recovered sessions. An application PDU (APDU) to be transferred is mapped onto an activity, which can be resumed at some checkpoint after interruption or session abort. RTS is supported by the OSI presentation and session services. The RTS has minimal requirements on the presentation layer itself. However, it makes extensive use of the session layer services (Recommendation X.215) which are made directly available to application layer entities by the presentation layer.  Chapter 4. RTS Protocol Implementation  39  The RTS is that part of an Application Entity, that is responsible for creating and maintaining associations between the Application Entity and its peers, and for reliably transferring APDUs by means of them. The Application Entity, is referred to be RTS user. An association created by the RTS may be either monologue which means APDUs can be transferred in one direction only, or two-way alternate. In the case of a two-way alternate association, the right to transfer APDUs is governed by the turn, which can be transferred between peer RTS users.  4.3  R T S Automatic Implementation Using the Estelle-C Compiler  4.3.1  Introduction  The RTS, namely X.410 in the CCITT Recommendations X.400 series, provides a set of connection oriented transfer services to the Message Transfer Layer (MTL). The MTL is the layer immediately above the RTS. The RTS can process the M T L requests while checking the correct status. When an error occurs, the RTS will discover it and recover from it automatically. 4.3.2  The Architecture Design  According to the Message Handling System, namely the CCITT X.400 series recommendations, there are three entities involved in the RTS implementation. These three entities are specified in three Estelle modules as follows respectively. • MTL: which RTS entity provides the services to, and also gets the user requirement from. M T L is actually the RTS user which is adjacently one layer up. • RTS: which is RTS protocol itself, it behaviours as described in CCITT X.410 recommendation, and covers all the functionalities described in X.410.  Chapter 4. RTS Protocol Implementation  40  • SES: which stands for session layer, it provides services to RTS entity. RTS entity establishes its associations by using the session connection services. In this implementation, each of three entities above is specified in one Estelle system module, correspondly MTL, RTS, and SES module in Figure 4 . 8 . Each module is associated with 2 module instances which share the same Estelle module specification, and also can be identified by its module instance number. This strategy of design can make two RTS entities communicate each other and behaviour as two individual RTS entities. It also helps designer to check the functionality. Especially these two RTS instances can be simulated as conformance tester of each other, which will be described in later chapter. Seeing Figure 4 . 8 , • MTLO and MTL1 are two module instances of MTL module; • RTSO and RTS1 are two module instances of RTS module; • SESO and SES1 are two module instances of SES module. Those six module instances, seeing Figure 4 . 8 , are connected by Estelle channels. Through the individual channel, the interactions, i.e. messages in implementation, can be sent back and forth between each pair of connected module instances. 4.3.3  The Connections Between Module Instances  There are five channels in Figure 4 . 8 . • Channel 1 connects MTLO and RTSO; • Channel 1' connects MTL1 and RTS1; • Channel 2 connects RTSO and SESO;  Chapter 4. RTS Protocol Implementation  41  MTLO  MTL1  "Up "RTS_ASP_DOWN MT.ChannejI (Channel 1) "Up  "RTS-ASP-DOWN "Up MT.Channdl (Channel 1 )  "RTS^VSP-DOWN  ,,  •Up  RTSO •Sender  RS.Channel (Channel 2)  "Receive:  RTS1 •Receiver  "Sender  "Sender  RS.Channe (Channel 2'  •Receiver  •Receiver  "Sender  SES1  S E S O  "Passer  •RT5^SP_DOWN  •Accepter  "Passer  RS-Channel (Channel 3) • Interaction Point Figure 4.8: R T S Implementation in Estelle  •Accepter  Chapter 4. RTS Protocol Implementation  42  • Channel 2' connects RTS1 and SESl; • Channel 3 connects SESO and SESl; Let us look at the channel individually. Channel 1 and channel 1', namely MR.Channel in implementation: MTL sends the user requirements or responses down to RTS, and RTS sends back the indication or confirmation to M T L upon the processing of the requirement. The following messages can be sent by MTL module through the Interaction Point(IP) RTS-ASP-DWON and caught by RTS module through IP Up: R_OPEN_REQ; RJCFER-REQ; R_CLOSE_REQ; R_TURN_PLSE_REQ; R_U_ABORT_REQ; The following messages can be sent by RTS module through the Interaction Point Up and caught by M T L modules through IP RTS-ASP JDWON: R_OPEN_CFM; R_XFER_CFM; R_CLOSE_CFM; R_TURN_PLSEJND; Two ends of the channel play the role of user and provider respectively. These two ends attach the M T L and RTS module which are connected by channel 1. Both MTL and RTS module have two interaction points standing for both user role and provider role. Actually all the interactions, i.e messages listed above, are declared under user role when the MR.Channel is declared. Each interaction can be sent associated with a set of parameters through the channel. For the interactions above, Variant Record has been used for all the parameters associated with them. See Appendix A.  Chapter 4. RTS Protocol Implementation  43  Channel 2 and channel 2', namely RS-Channel in this implementation: RTS module can send the request down to SES module which simulating the session layer and all the way down to physical layer. When the peer RTS module receives the indication of that request, it sends the response along RS_Channel to its lower level SES module. The following messages can be sent as RTS request through Interaction Point Sender and caught by SES module through IP Receiver: S-CONN.REQ; S_REL_REQ; S-U_ABORT-REQ; S_CNTL_GrVE_REQ; S_ACT_STRT-REQ; S_SYN_MI_REQ; S_ACTJNT_REQ; S-ACT_RES_REQ; S_ACT_DIS-REQ; S-ACT-END-REQ; S_U_EXCEP_REQ; The following messages can be sent as peer confirmation through Interaction Point Sender in SES module and caught by RTS module through IP Receiver: S-CONN-CFM; S_REL_CFM; S_SYN_MI_CFM; S_ACTJNT_CFM; S_ACT_DIS_CFM; S_ACT_END_CFM; The corresponding indications and responses can be passed along another pair of Interaction Points through RS-Channel. Channel 3 shares the same declaration as channel 2. The reason is that SES module simulates the session layer entity and all the way down to physical layer. Channel 3  Chapter 4. RTS Protocol Implementation  44  MTLO  R_CONN_RE }  MTL1  R_CONN_CFM  R.CONNJND  RTS1  RTSO S_CONN_CFM  S_CONN_REQ  S_CONN_RStf  S.CONNJND  SES1  SESO S_CONN_RSP  S_CONN_REQ Figure 4.9: Round Trip of A Connection Request actually simulates the connection between RTS and its peer module through the points inside SES module. Therefore, when SES module receives a RTS request it will pass the exactly same thing (interaction and associated parameters) to its peer SES module. Upon receiving the request (or response), SES module will send a indication (or confirmation) to its upper level RTS module respectively. Two ends of the RS-Channel play the role of user and provider respectively. These two ends attach to the RTS and SES module which are connected by channel 2. Both RTS and SES module have two interaction points associated with channel 2 standing for both user role and provider role. SES module has another pair of interaction points standing for both user role and provider role associated with channel 3. Therefore all the  Chapter 4. RTS Protocol Implementation  45  interactions mentioned above are declared under user role of RS.Channel. Appendix C shows how the RS-Channel has been declared and how the interaction points are described in RTS and SES module heads for RS_Channel in this implementation. Because of the amount and complexity of the parameters associated with interactions, the parameter is declared as RECORD for each interaction individually. The parameters associated with interactions coming along RS-Channel are described in Appendix D.  4.3.4  Association Establishment  The RTS user, namely MTLO module, issues the R_OPEN_REQ primitive to establish or open a new association with another RTS user, namely its peer RTS user module M T L 1 . When RTS module receives the R_OPEN_REQ primitive from M T L , it will do the following things: • check the number of existing association is not over the maximum association number. • allocate a new Connection Control Block for the new association, which contains all the information needed to maintain an connection (called an association inside RTS). The first set of fields contain the entity and connection identifications of the RTS, RTS user and RTS provider. They are needed to connect the peer RTS entity. The next set of fields maintains information about the association established. The set of fields after that is used when a transfer procedure takes place, that is an RTPDU is being sent from the local entity to the peer entity and vice versa. Then two special fields are defined to contain the last secured PDU. This is specifically required by the specification to prevent duplicate PDUs from reaching the RTS user.  Chapter 4. RTS Protocol Implementation  46  • compose the S_CONN_REQ interaction to open a session connection. Which contains the information for session connection and especially the information needed to be negotiated with its peer RTS entity, i.e checkpoint size , window size. • call the ASN.l encode routine to convert the RTS data to the standard ASN.l format. • send the S_CONN_REQ associated with all the parameters down to its lower level SES module through the interaction point connected by RS_Channel, eventually to its peer RTS module. • update the status for the protocol machine. The initiating RTS will always request that the data token be available for either a one-way monologue or two-way alternate dialogue session. According to RTS user connection request, the initiating RTS specifies which RTS will initially hold the data token, including minor synch token and major activity taken, upon successful establishment of the association. The initiating RTS will assign all the tokens to the same RTS. The connection may be rejected if this rule is violated. At any particular point of time, the holder of the tokens is referred to as the sending RTS, the other as the receiving RTS. When the peer RTS module receives connection indication S.CONNJND, it will decode the RTS data, check out the negotiable information, if it is acceptable it will set up the value in local RTS, otherwise it will make its suggestions to initiating RTS. The responding RTS will also check its own status, if the coming association is acceptable, it will send a connection response S_CONN_RSP with ACCEPT. Otherwise if it is busy itself or some error occurs, a S_CONN_RSP with REJECT will be issued to initiating RTS. When the RTS initiator receives the connection request confirmation S.CONN.CFM  Chapter 4. RTS Protocol Implementation  47  with A C C E P T , it will firstly decode the RTS data, check the negotiable information, if acceptable take the value and set the corresponding status in local RTS module, otherwise the association may need to be reestablished. If the association has been established, RTS module will confirm its user MTL module. When RTS initiator receives the S-CONN_CFM with REJECT, it will firstly free the Connection Control Block for this association, update the status of local RTS module, and also inform its user M T L module.  4.3.5  Data Transfer  Each APDU Application Protocol Data Unit, conveyed in an RTS Transfer Request, constitutes a session activity. Upon receiving a RJCFER-REQ from MTL module, RTS module will start an activity to transfer it. An APDU is transferred as a single SSDU (Session Service Data Unit) if checkpointing is not used or the APDU is smaller than the checkpointsize. Otherwise, the APDU is transferred as a series of SSDUs, the maximum size of each has been negotiated in checkpointsize. Therefore the number of SSDU will be also decided. This will be used in data transfer phase to secure the acceptance of APDU. To start a new activity, the sending RTS module, which holds the tokens, issues an Activity Start Request S _ A C T J 5 T R T _ R E Q down to SES module. The sending RTS will start transmitting the APDU by issuing a Data Request S-DATA_REQ immediately after the S _ A C T J 3 T R T _ R E Q is issued. After each SSDU carried by an S_DATA_REQ, the sending RTS module will insert a checkpoint Synchronization Minor Request S J3YN_MI_REQ to track the acceptance of SSDU. Upon receiving of the Synch Minor Confirmation S-SYN-MLCFM, next SSDU carried by S-DATA-REQ will be issued. After making sure the correct number of SSDUs have been secured, the sending RTS module will indicate the end of the activity by issuing an Activity End Request S_ACT_END_REQ.  Chapter 4. RTS Protocol Implementation  48  The Checkpoint may only be inserted if a checkpointsize is greater than zero which was negotiated during the connection phase. The sending RTS will interpret a confirmed checkpoint to make sure the data has been secured by the receiver, otherwise the data need to be retransmitted. In abnormal circumstances, such as upon receipt of an exception report indication S-U-EXCEP_REP J N D from the receiving RTS or detection of a local system problem, the sending RTS will take one of the following actions: • Interrupt the current activity by issuing an Activity Interrupt Request S_ACT JNT-REQ. • discard the current activity by issuing an Activity Discard Request S_ACT_DIS_REQ. • even abort the current session connection by issuing a Abort Request S_U-ABORT_REQ. The interrupted activity can be recovered when abnormal circumstance is fixed, because all its information associated with current APDU has been saved when interruption occurred. The abortion of the session connection has the same effect of interrupting the current activity. The discarded activity can not be resume. The receiver RTS will delete all the knowledge and contents of the associated APDU , upon receiving the Activity Discard Indication. If the sending RTS wished to retransmit a previously discarded activity, it must reintroduce it as a new activity by issuing an S_ACT_STRT_REQ. If the receiving RTS detects some problem either inside or outside of an activity, it may issue either an S_U-ABORT.request or an S_U_EXCEPTION_request. Aborting the session connection is the most severe action, it will provide the reason parameter for diagnostic purposes. By issuing S_U-EXCEPTION-request, the receiving RTS indicates a less severe problem which it anticipates the sending RTS can overcome, and allows the sending RTS to take the some appropriate action.  Chapter 4. RTS Protocol Implementation  4.3.6  49  Turn Management  When the RTS user issues a Turn Please Request to RTS module, the RTS will send an Token Please Request S_TOKEN_PLSE_REQ to its peer. Upon receipt of the S_TOKEN_PLSEind , the sending RTS issues a Turn Please Indication to the RTS user. When the RTS user issues a Turn Give Request R_TURN_GrVE_REQ, the sending RTS will give control of the session to its peer RTS by issuing the S_CONTL_GrVE_REQ primitive. The data, minor-synch, and major-activity tokens are also passed to the peer RTS module. Upon receiving the S_CONTL_GIVE_ind , the receiving RTS will realize it becomes the sender and holds all the tokens. If the turn exchange is happened in session abortion-reconnection period, some primitive may be lost. An RTS that has issued an S-TOKEN_PLSE_REQ but not received an S-CONTL_GrVE Jnd, it should re-issue the S_TOKEN_PLSE_REQ after session recovery.  4.3.7  Connection Release  For normal releasing, the sending RTS issues an Session Connection Release Request S-REL-REQ upon receiving CLOSE.REQ from RTS user. When receiving RTS receives the S-RELJndication, it will issue an S_REL.response to it peer and a CLOSEJndication to its RTS user. When an RTS detects a serious problem, it may issue an S_U.ABORT.request. Upon receiving this primitive, RTS module will abort the current session connection. The session provider can also abort a session connection for a variety of reasons, i.e. transport connection failure , or local provider problem.  Chapter 4. RTS Protocol Implementation  4.3.8  50  Recovery  The sending RTS may continue an APDU transferring that was previously interrupted by an Activity Interrupt Request or user or provider initiated session abort. The Activity Resume Request primitive S_ACT_RES_REQ will be issued to resume the aborted activity. Parameters are supplied to link the continued activity with the previously interrupted part (see Appendix D). Following by S^.CT_RES_REQ, the last secured SSDU will be restored, and then the data transferring will be processed since then. It is possible for the sending RTS to try to resume an activity that the receiving RTS believes to be complete. This happens when the session connection is aborted after the receiving RTS has confirmed the activity end, and the confirmation is lost. To overcome this, the following things will be done: • As the first activity started on a new connection, the sending RTS attempts to resume the last interrupted activity, i.e. the one that was current when the connection was aborted. • The receiving RTS always records the connection ID and activity ID of the last APDU which is completely secured. • The receiving RTS checks the details of each resumed activity to see if it coincides with the last APDU the RTS secured. If it does, the receiving RTS responds correctly to the sending RTS but discard the data it receives. Since the APDU might be completely received by the other RTS, the sending RTS will retain the APDU until the activity is successfully secured, resumed or discarded. This avoids the possibility of generating duplicate APDUs.  Chapter 4. RTS Protocol Implementation  4.3.9  51  A S N . l Encode and Decode Routines  One of the fundamental problems in data communications is dealing with the diverse formats used to represent information in different systems. Abstract Syntax Notation One (ASN.l) is a powerful mechanism to describe data in a representation independent way. A S N . l is a language for describing data types and values, and as its name implies, it can be used to define an Abstract Syntax, a formal description of data types and values, without specifying any particular representation for the data being described. Representing information abstractly is not enough.  Transferring that information  requires an encoded, bit level representation. One method for creating that representation is to apply a set of encoding rules to a given abstract syntax, theses rules generate an unambiguous bit level representation of the data being described.  When such a  representation is used for information passed between application entities in two different systems, it is called a transfer syntax. The Basic Encoding Rules (BER), can be used to derive a transfer syntax for data described using A S N . l . In fact , the term " A S N . l " is often used to mean the combination of A S N . l and B E R , of both abstract and transfer syntax [25]. According to RTS C C I T T X.410 Recommendation, the following RTS PDUs need to be encoded and decoded. The corresponding data structures are also provided in X.410. • RTS Open Request • RTS Open Accept • RTS Open Reject • RTS Turn Please Request • RTS Transfer Request  Chapter 4.  RTS Protocol Implementation  52  • RTS Abort Request Encode and decode routines , which follow the Basic Encode Rules, are manually written in C language, and can be combined with Estelle specification generated C code during the run time execution. Before one of the above PDUs is sent, the encode routine is called to convert the corresponding information from Buffer Area, which holds the all the information possible to be converted, to the ASN.l format. Upon receiving one of above PDUs, the decode routine is called to convert reversely.  4.4  U B C J D A C O M P T E R T S Implementation  The UBC J D A C O M P T E environment is endeavoring to develop a portable OSI (Open Systems Interconnection) protocol testing system. The system is capable of formal conformance testing and performance testing for protocol implementation at any OSI protocol layer. In their environment, OSI protocol implementations have been completed up to session layer. A set of Message Handling System protocols, namely X.400 series, have been implemented recently. In this thesis, interest focus on their RTS sublayer implementation which is manually implemented in C programming language. Some comparison on automatic and manual RTS implementation will be presented in later chapter. UBC J D A C O M P T E RTS Package realizes the CCITT X.410 Recommendation, covers the same RTS features and functionality as the RTS implementation presented in this chapter. Therefore the comparison and coverage features between manual and automatic protocol implementation method can be discussed in later chapter based on the same fundamental design.  Chapter 5  Comparison Between Semi-automatic and Manual Implementation Methods  5.1  Introduction  Both CCITT and ISO are working on the standardization of Formal Description Techniques (FDT), such as Estelle, Lotos, SDL, and etc, which are intended for writing complete formal descriptions of OSI protocols and services. The possibility of automated generation of implementation code is definitely a major advantage for the use of formal specification. It seems that there is presently some hesitation among non-FDT specialists to use the FDT's. One of these reasons is that they are not acquainted with FDT Estelle and automatic protocol implementation method. There are however many advantages in working at a more abstract highlevel language such as Estelle. In this chapter, from the protocol implementation point of view, the advanced features of Estelle as a protocol specification language versus C as a protocol implementation language are discussed. This is followed by a presentation of our experience in performing some automatic protocol implementations using the UBC Estelle-C compiler. The basic understanding of the FDT Estelle and the C programming language is assumed in the following discussion.  5.2  Modularity  A distributed system specified in Estlle is composed of several communicating components. Each component is specified in Estelle by a module definition. Since in a system there may be more than one components defined by the same module definition, it is  53  Chapter 5. Comparison Between Semi-automatic and Manual Implementation MethodsbA  appropriate to call system components module instances. The module definition consists of a set of transactions for a state transition system. The module may perform the definition of its submodules together with their interconnections. A module may have the attribute of process or activity. There is a synchronous parallelism among activities and asynchronous parallelism among processes. A systemprocess (or a systemactivity) is the root module with the attribute of process (or activity). The hierarchy of the module instance system determines the Estelle structuring principles. Each module instance represents a particular implementation scheme. Therefore the Estelle system is structured into asynchronous systems with the attribute of systemactivity or systemprocess. Within a specified system, a fixed number of subsystems are distinguished. Each subsystem is a subtree of module instances rooted from a system module instance, i.e. attributed systemprocess or systemactivity. In particular, the whole specified system may consist of only one subsystem. In such a case, the specification itself, the outmost module, has the attribute systemprocess or systemactivity. Therefore many kinds of system design can be configured by employing the concept of Estelle module system, that is particularly suitable for the OSI multi layer protocol entities reference model.  5.3  Transition Oriented Specification  Estelle as a Formal Description Technique, its transition oriented programming style is suitable for protocol specification since communication protocol can be described as an extended Finite State Machine. The transition styled specification which can be event driven or state driven is easy to read and understand. Adding, deleting or changing some number of transitions can be easily achieved if any changes need to be made to the  Chapter 5. Comparison Between Semi-automatic and Manual Implementation Methods55  protocol specification. Although C is a powerful and efficient programming language, however it does not support this kind of transition oriented programming style. The transition oriented specification defines the behaviour of a particular module as a flat automaton, i.e. a list of all possible transitions. The state of the automaton is defined by the value of different variables within the program, and is used in the guard parts of the transitions for defining which transition can occur in which state, while the body of the transition indicates the new sate which is reached. Such a program does not impose any kind of ordering as regards to the execution of the different transitions. At each moment there is an undeterministic choice among all enabled possible transitions. Such a programming style is quite natural for specifying systems which are initially designed as finite state automata, since the translation is trivial. In each computation step, each module can have only one transition to be fired and executed even though there are several Arable transitions at this computation step. The enhanced version of the compiler employs a new scheduler to pick up the fired transition randomly in equal probability. It is good to support the nondeterminism and to give every Arable transition some chance to fire theoretically. Due to this nondeterministic behavior, the protocol execution may be hard to trace. One possible solution is to limit the number of Arable transitions at each computation step and also to assign different priority levels to different transitions. However, some readability problems may appear if the size of the module is too big: for instance LAPB module includes 101 transitions, and RTS module includes 8 5 transitions. If there is no additional documentation to outline the structure of the design, it is difficult to understand at a first glance on the specification.  Chapter 5. Comparison Between Semi-automatic and Manual Implementation MethodsbQ  5.4  Message Exchange Through Communication Channel  Communication channel is one of major Estelle components which benefits protocol implementation. It makes the message exchange more convenient and efficient than any general purpose programming language, i.e. Pascal or C. This mechanism is intended to be the basic communication mechanism of Estelle, it allows interaction points of module instances to be directly or indirectly connected through several attachments for message exchange. In Estelle, the convenient define and maintenance of communication channel and signals give user a clear impression of the behaviour of message exchange. The channel interaction primitives have the property that the receiving module may determine if and when a particular interaction may be executed. This power is essential for many protocol implementations. It allows the protocol specification to be well structured. However care must be taken to avoid the possibility of deadlocks, as mentioned before in LAPB implementation. A module instance can send an interaction to another module instance through a preestablished communication channel between their two interaction points. An interaction received by a module instance at its interaction point is appended to an unbounded FIFO queue associated with this interaction point. The channel can be declared as : channel User.Channel(sender, receiver) ; by user : host.ready; data_req(f: frametype);  The channel connects the user module and LAPB module, the module heads should be written as follows: module e n t i t y . u s e r PROCESS ; ip Uu : User.Channel(sender) end ; { e n t i t y . u s e r }  i n d i v i d u a l queue ;  Chapter 5. Comparison Between Semi-au tomatic and Manual Implementation Methods^!  MODULE entity.module PROCESS; IP Up : User_Channel(receiver) i n d i v i d u a l queue ; END; ity.module}  -Cent  The two modules should be initialized, the two interaction points inside individual module should be connected in the initialization part of outmost module: MODVAR DCE: entity.module; USER : e n t i t y . u s e r ; INITIALIZE {LAPB.protocol} BEGIN INIT DCE WITH entity.body; INIT USER WITH user.body; CONNECT END;  DCE.Up  TO userO.Uu ;  After the channels and interaction points are arranged properly, an OUTPUT Estelle statement in transition action part can be easily used to pass the interactions through proper interaction point to desired module. A WHEN statement in transition guard part can be easily used to accept the coming message through the proper interaction point. To pass a message through Estelle communication channel, the Estelle compiler just puts the address of the message to the end of queue associated to the other interaction point along the same channel. In C programming environment, in order to achieve the message exchange, a number of linked message queues and procedures need to be manipulated in a fairly complex manner. By looking at the manual C implementation code of LAPB and RTS protocol carefully, we can find that lots of effort needs to be made on message exchanging.  And also  the C code is much longer and complicated than Estelle specification. No matter from which point of view among programming complexity, read ability, or the complexity of  Chapter 5. Comparison Between Semi-automatic and Manual Implementation Methods58  maintenance, we can see the specifying in Estelle is superior than programming in C. That is one of reasons we develop the Estelle-C compiler to automate Estelle specification to C implementation. People can easily finish the protocol Estelle specification and submit it to the Estelle-C compiler to get the automatically generated C implementation.  5.5  Nondeterminism  For a specification language, the possibility of leaving certain properties of the specified system to be undetermined seems important. It is especially ture for the requirement of sophisticated protocol development. It brings theflexibilityfor protocol implementation. In Estelle, nondeterminism can be introduced by using the transition guard to allow several transitions are Arable at the same time. However only one transition can be fired actually in each computation step. The current compiler manages to execute one transition from those Arable ones with equal chance, to achieve nondeterminism feature properly. Nondeterminism within transitions bring the flexibility for protocol implementation, sometime it might be harmful if it is out of control. For instance, it is very hard to accomplish the protocol functional testing with the existing of nondeterminism within transitions, according to the experience of LAPB and RTS implementation. Priority is imperative feature in an implementation. Priority can be set among transitions to regulate the fire of transitions. It is a proper compromise for nondeterminism.  5.6  Parallelism  Certain languages allow for the expression of processes or sequences of statements which are executed in parallel and share some common data. Two kinds of parallelism among  Chapter 5.  Comparison Between Semi-automatic  and Manual Implementation  Methods59  modules can be expressed in Estelle: asynchronous parallelism and synchronous parallelism. Asynchronous parallelism is permitted only among subsystems, or more precisely, among actions of different module instances belonging to the different subsystem. Synchronous parallelism is permitted only within s subsystem, or more precisely, among actions of different modules instances belonging to the same subsystem. Parallelism can be achieved using automatic protocol implementation method. For instance in RTS implementation, there are three modules refer to three ISO layer entities, and each module has two module instances. At each computation step, there are six module instances involved. None or one transition from each module instance will be chosen to fire. Maximum six transition one from each module instance can be executed at the same computation step. The parallelism is implemented into C code through the Estelle-C compiler. Again we can see the heavy effort and complexity to achieve the parallelism in the C implementation code. The Estelle-C compiler automatically converts the parallelism in Estelle into C implementation, it reduces the human effort and performs the function of parallelism properly.  5.7  Exceptions  In Estelle, a transition can be presented as: TRANS FROM statel TO s t a t e 2 PROVIDED "some exceptions" BEGIN actions. END;  Chapter 5. Comparison Between Semi-automatic and Manual Implementation Methods60  which will be executed in any circumstances when the specified exception occurs. This approach is straightforward and easy to use. In the example above, the occurrence of a failure during the holding of a privilege may require a different processing than in other circumstances.  5.8  Timer Facility  In Estelle, timer can be easily installed by using delay clause, because the compiler does the real timer control but not the user in specification. For example: FROM INITIAL TO SEND_DM provided ((timerlon = true) and (n2 < N2MAX)) delay(Timerl) BEGIN •(time out action} END; The timer can be started when the transition Arable condition is true. It can be stopped by setting timerlon if the condition is false. The compiler checks if the delay time is over and if the timer has been stopped. If the timer is over and the timer has not yet been stopped, the compiler starts to execute the timeout action part. Timer facility is convenient but may not as accurate as UNIX system timer facility. In C environment, there are some ways to manage timer facility. The UNIX system call alarm() and signal() can be used to implemented timer is a example of using this method to implement timer. In LAPB manual implementation, a timer is implemented as one Threads process. LAPB() process sends a start-timer primitive to timer process to start the timer. When timer process gets start-timer primitive, it starts to Sleep as period of timer interval.  Chapter 5. Comparison Between Semi-automatic and Manual Implementation Methods61  LAPB process can also send stop-timer primitive to timer process. When timer process gets stop-timer primitive, it changes the stop flag into true. When sleeping time interval is over, the timer process checks if the stop flag is false. It sends a timeout primitive with specified timer number to LAPB process. LAPB() process takes the proper reaction for it.  5.9  Debugging Facility  It is obvious that manual implementation can take a good advantage of C developing tools on UNIX environment, such as dbx debugger, etc. Estelle compiler has its own debugging facility. It is possible to visually trace the execution of any Estelle module entity. In a Estelle specification, every module, transition, channel and signal is assigned a unique integer identifier. Details can be found in [13]. In each computation step, the compiler debugging facility will print out a list of all modules being checked. These are the transition which is selected for each module as ready to fire, interactions and channels associated with the transition. The following figure is a fictitious example of the output for one computation step. BEGIN Computation step Module = 0 Module = 3 Transition =2 No interactions. Module = 2 Transition = 10 Module = 1 Transition = 101 EXECUTING Transitions: 2, 10, 101, END Computation step  Channel = 3  Signal = 1  No interactions.  Chapter 5. Comparison Between Semi-automatic and Manual Implementation Methods62  According to this example, at this computation step, module 3 has transition 2 executed without any interaction; the module 2 has transition 10 executed with the reception of the signal 1 through channel 3; and module 1 has transition 2 executed without any interaction. Module numbers are assigned sequentially beginning with the outmost module, it is the sequence number when you initial the Estelle program initialization part. Channel numbers are assigned sequentially in the order which the interaction points are connected Signal numbers. Transition numbers are assigned sequentially in the order which the compiler encounters them from the source specification. Signal number is the sequence number when you declare the signals associated with the proper channel.  Chapter 6  Comparison Between Semi-automatic and Manual Implementations for L A P B and R T S  6.1  Functional Coverage of L A P B Implementations  Both LAPB automatic and manual implementations are developed in this thesis work. They are based on the same LAPB protocol standard document, and the same Finite State Machine and the state transition of the LAPB protocol (seeing Figure 3.6). They follow the same architecture design and functional coverage. Both implementations cover the same functionalities which include link set up, information frame sending and receiving, acknowledgement sending and receiving, frame rejecting, host busy condition, link disconnecting and PDU encoding and decoding. These functionalities are used as the base set for comparison.  6.2  Functional Coverage of R T S Implementations  The RTS automatic implementation is developed in this thesis work, whereas the RTS manual implementation is developed by the people working in the UBC-IDACOM project. The description and the source code of the RTS manual implementation are referenced to specify the RTS automatic implementation in Estelle. This ensures that both implementations cover the same functionality. The test cases specified in X.403 Conformance Testing Specification Manual [2] have been used as the base set for testing both the automatic and manual implementations of  63  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB and RTS  64  RTS. This ensures that both implementations are tested on the same basis of functionality. The RTS manual implementation is developed within the OSI PTE testing environment [29]. The OSI P T E is a realization of the OSI Reference Model that has been designed to support general protocol testing. Within the environment, a protocol implementation executes as an entity that passes events back and forth to other entities. The implementation code of RTS, generated by the Estelle-C compiler, does not incorporate the necessary testing functions, ( such as data bufferring, timer management, etc.), which are supported by the OSI PTE. Therefore, a less rigorous test approach has been employed in testing the automatic RTS implementation. According to the X.403, the test cases should be tested by observing the behaviour of a pair of tester and IUT (Implementation Under Testing). In this automatic implementation, without having any interface to the OSI PTE, the pair of RTS module instances can be modified to be the tester for each other in testing individual abstract test case. Each abstract X.403 test case is manually translated into the specification and observed in the implementation. MTL module instances invoke the RTS module instances using the service primitives provided to carry out the testing functions. The RTS test cases are composed of several test groups: • The connection (association) establishment and negotiation phase. • The orderly release of the connection (association). • The data transfer phase with turn exchange. • Recovery Each test group contains two or three test subgroups for initiator, responder and token exchange respectively. Each test case is designed for testing a particular case under an  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB and RTS  L A P B Implementation  Automatic  Manual  link set up: from upper layer ready to L A P B gets in A B M state  1.9 sec  3.4 sec  2.5 sec  3 sec  machine from D C E to DTE  80 sec  102 sec  link disconnect  2 sec  transmitting 1 message across machine from D C E to D T E transmitting 20 message across  3.2 sec  Figure 6.10: The Execution Time for L A P B unique circumstance. The summary of the test cases can be found in Appendix E.  6.3  Performance Analysis of L A P B Implementations  Figure 6.10 shows the different execution times of individual part for both automatic and manual implementations. First column indicates the timing of the execution period, second and third columns indicate the time consumed in that period for automatic and manual implementation respectively. The UBC Estelle-C compiler manages to manipulate all the Estelle asynchronous module instances into a single UNIX process. All the executions and communications through the channels between pairs of module instances are processed within that single UNIX process. In the manual implementation, there are several UNIX processes involved. Even the Threads system as an improved Inter Process Communication system, the  65  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB  and RTS  66  overhead in IPC is still fairly heavy. For the purpose of making the comparison of execution time on the same basis, the IPC has been involved into automatic LAPB implementation and execution.  In the  LAPB specification, the DCE module instance is designed to be connected with DTE module instance through PHY module instance (Figure 3.7).  The two PHY module  instances are connected using the UNLX IPC system calls across machine. For instance, to measure the execution time of transmitting one PDU, the timer starts when DCE sends a PDU. The PDU is transmitted to its peer DTE through PHY module instance. The timer stops when the peer D T E on the other machine accepts that PDU. From Figure 6.10, we can see that execution time of Estelle implementation is slightly faster than that of the C implementation. However, considering the overhead incurred by the Threads system as mentioned before, we expect that the execution time in manual C implementation to be slightly faster than those obtained in Figure 6.10. Therefore the execution times of both implementations are expected to be close.  6.4  Performance Analysis of RTS Implementations  Six test cases, one from each test group, are selected from the X.403 test cases group. They are used as the base test set for both automatic and manual implementations. The execution times of these test cases are collected for the purpose of performance analysis. The purpose of these selected test cases are briefly described as follows: 1. This test shows that the IUT is able to establish an association as an initiator. The IUT receives an OPENJlequest from its user, issues the corresponding S-CONNJlequest, receives an S_CONN_Confirm and issues an OPEN_Confirm to its user. The tester receives an S.CON Jndication and issues a positive S-CON.Response.  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB and RTS  67  2. This test shows that the IUT correctly reacts when it tries to establish an association and the peer RTS does not use the correct set of Session Functional Units. The IUT receives an OPEN_req from its user, issues an S_C ON .request, receives an S.CON jconfirm with invalid FU combination, aborts or releases the session connection and issues a negative OPENxonfirm to its user. The tester receives an S.CON indication and issues an S-CON-response with an invalid combination of FU. 3. This test shows that the IUT is able to send APDU when transfer is governed by the checkpointsize and the windowsize proposed by itself. The IUT opens an association as initiator, transfers an APDU. The tester accepts an association, receives an APDU. Additionally, this APDU is designed to be 10 of SSDUs as size of lk in implementation. 4. This test shows that the IUT can give control to its peer, receive an APDU and accept the session release. Checkpointing is not used during transfers. The IUT opens an association, sends an APDU, gives control to its peer, receives an APDUand accepts the session release. The tester receives an APDU, asks for session control, receives it, sends an APDU and releases the session connection. 5. The tester issues an user exception report with the reason "local ssuer error", The activity is interrupted and then resumed by the IUT. The IUT initiates an association with checkpointsize > 0 and windowsize > 0. It then starts an activity. In the middle of the activity , the tester issues an exception report . The IUT interrupts and then resumes the activity. 6. The tester does not confirm any checkpoint but issues an User Exception Report with the reason "local ssuser error". The IUT opens an association and starts an  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB  and RTS  68  Execution Time in  Test Cases  Automatic Implementation  Test Cases  1  50 ms  Test Cases  2  100 ms  Test Cases  3  1,040 ms  Test Cases  4  20 ms  Test Cases  5  40 ms  Test Cases  6  20 ms  Figure 6.11: The Execution Time for R T S Test Cases  activity. In the middle of the activity which has not had any data checkpointed, the IUT receives an exception report. The activity is discarded by the IUT and restarted a new one. Figure 6.11 shows the execution times obtained for the RTS automatic implementation. In the automatic implementation, a dummy module has been developed to simulate a session module. The dummy session module is designed as a simple passer or receiver to pass the RTS PDU between communicating entities. Unfortunately, due to the closing of UBC-IDACOM project, it is not possible to get the accurate execution time for the manual implementation. However, it is expected that the RTS manual implementation should yield a slightly better performance.  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB and RTS  6.5  69  Size of Code and Developing Time for L A P B Implementations  Figure 6.12 shows the size and developing time of individual part of LAPB implementation in both automatic and manual methods. The man-write code in automatic implementation, which is 2100 lines, comes from the summary of LAPB protocol specification, socket connection routines and run time C support routines. The man-write code in manual implementation, which is 3050 lines, comes from the summary of LAPB protocol C programming code, Threads IPC source code and socket connection routines. It is not surprising the Estelle code is shorter than C code, and also the developing time of Estelle specification is shorter than manually written C program. The results confirm the advantages described in Chapter 5. The Estelle specification is easy to write and the Estelle-C compiler is convenient to use for automatic protocol implementation. There are 1750 lines of Estelle specification for LAPB automatic implementation and 1400 lines of C program for LAPB manual implementation. Some C code to performance IPC in Threads system is written for LAPB manual implementation. To make the automatically generated implementation executed properly, some socket connection routines are manually written for connecting of 2 PHY module instances across machine, some run time C support routines are written to cover the functions Estelle can not handle which are mainly printing statements. It turns out that there are in total 2100 lines of manual written code for automatic LAPB implementation compare to 3050 lines of manual written code for manual LAPB implementation. However the Estelle-C compiler generated implementation in C code and machine object code in automatic LAPB implementation are larger than in manual LAPB implementation. More memory space will be needed for automatic protocol implementation.  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB and RTS  Developing Automatic LAPB protocol  1750 lines  specification  38 K bytes  Time  6 weeks *  Threads IPC source code  Developing Manual  Time  1400 lines 36 K bytes  6 weeks  1400 fines  N/A  38 K bytes  Socket Connection Routines Run Time C Support Routines Comipler Generated C-code  70  250 lines 4 K bytes 150 lines 2.7 K bytes  3400 lines  v g  Man-write C code  86 K bytes  Machine Executable Code  130 K bytes  Man-write code  2100 lines  Estelle vs C  42 K bytes  2 weeks **  250 lines  2 weeks  4 K bytes  ***  N/A  Automatically  3000 fines  8 weeks +  78 K bytes  N/A  90 K bytes  8 weeks  3050 lines  8 weeks +  78 K bytes  N/A  * including solving problem with Estelle-C compiler ** including integrating with Estelle code *** including integrating with LAPB C code Figure 6.12: Size and Developing Time Comparison for L A P B  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB and RTS  Developing Automtic RTS protocol specification run time C support routine compiler generated C code vs man-write C code machine executable code man-write code Estelle vs C  3000 lines  time  Manual  14 weeks  5000 lines  4200  automa-  5000  lines  tically  lines  71  Developing time 6 month appro.  500 lines  150 K byte 3500 lines  6 month appro.  100 K byte 14 weeks  5000 lines  6 month appro.  Figure 6.13: Size and Developing Time Comparison for R T S 6.6  Size of Code and Developing Time for R T S Implementations  From Figure 6.13, we can get the same conclusion as we get from previous section. There are approximately 5000 lines C code for RTS manual implementation, including 10 functional modules, all the header files, the event handling routines and the interfaces to its upper and lower layers in its PT Environment. Abort 3500 lines Estelle specification and C supporting routines have been written for RTS automatic implementation. These 3500 lines do not include the Estelle-C compiler generated C code and its run time support routines. The manual written code for RTS automatic implementation is shorter than for manual implementation. Since RTS manual implementation is programmed by the people working in the UBCIDACOM P T E project and the project is closed recently, there is not too much detail information for the developing time. It is said the whole RTS implementation was finished  Chapter 6. Comparison Between Semi-auto and Manual Impl. for LAPB and RTS  72  in approximately 6 month, including the set up of PT Environment components for RTS implementation, and RTS conformance testing. It took about 14 weeks to finish the whole RTS implementation: • 3 weeks for background preparation; • 2 weeks for architecture design, and prototype; • 6 weeks for covering RTS functionalities; • 1 week for ASN.l encoding and decoding routines; • 2 weeks for testing the RTS test cases; The developing time of RTS automatic implementation is shorter than its manual implementation. However some other components need to be concerned. The manual RTS implementation wasfinishedin advance and all the related documentations are ready to be referenced by automatic RTS implementation work. The manual implementation is designed in UBC-IDACOM P T Environment for the purpose of protocol testing, and some of its protocol testing features are not covered by automatic RTS implementation.  Chapter 7  Conclusion and Future Work  7.1  Conclusion  In this thesis we have developed a new version of UBC Estelle-C compiler to support the latest Estelle language specification . This compiler automates the implementation of protocols by producing an executable C implementation directly from its Estelle specification. The implementation can be run with the combination of a group of predefined run-time support routine at real execution time. The new version of this compiler has been enhanced to support the latest Estelle features more successfully and efficiently. It is also being modified to support non-determinism which is needed in most protocol implementations. By using the new version of UBC Estelle-C compiler, a lower layer protocol LAPB and a higher layer protocol RTS, have been implemented. Both LAPB and RTS protocols were first specified in Estelle. A small amount of C support routines were also written manually. Those LAPB and RTS specifications were submitted to the new version of the Estell-C compiler to obtain the automatic generated C implementations, whose object code can run together with the precompiled protocol independent run-time support library routines. We have compared the automatic generated LAPB and RTS implementations with the manual implementations in three major areas: functional coverage and development time, code size, and execution time. From the result of comparison between the automatic  73  Chapter 7. Conclusion and Future Work  74  and manual implementations, we note that UBC Estelle-C compiler provides an easy and reliable approach to protocol implementation. With the support of the comparison results, we can expect that automatic implementation generated by the Estelle-C compiler achieves the comparable performance, if not better than, the manual C implementation. There are many advantages offered by the automatic protocol implementation method. First, the executable C implementation of a protocol is generated automatically from its specification. This reduces the development effort required as compared to the manual implementation. From the Figure 6.13, we note that automatic implementation achieves about 32 percent saving of development time, and man-write code size is about 30 percent short than manual implementation. Second, since the protocol is formally specified in Estelle, i.e.  using the Formal  Description Techniques, the possibility of misinterpretation of protocol is therefore minimized. Third, the implementation code generated by the Estelle-C compiler is wellstructured and easy to maintain, whereas the modularity and readability of the manual implementation depends heavily upon the programming style of the individual. Fourth, since the executable C implementation is generated automatically through the Estelle-C compiler, this eliminates the program syntax errors. Fifth, since the system dependent features of a protocol are encapsulated into a set of modules, this enhances the portability of the protocol implementation.  7.2  Future Work  There are many areas still remain open for future study to investigate and improve the automatic protocol implementation methodology. More communication protocols can be implemented in automatic way to evaluate the automatic implementation method. For the new implementations, the detailed performance analysis should be considered  Chapter 7. Conclusion and Future Work  75  in the first stage of protocol implementation design. The automatic generated protocol implementation should be able to be tested in the OSI protocol testing environment. The test suite generator can be built for individual protocol implementation for protocol conformance testing. The interface to OSI protocol testing environment can also be built to enable a protocol to be tested in a OSI PTE. Since Abstract Syntax Notation One (ASN.l) is designed to be independent of any programming language, it would be very useful to incorporate ASN.l into Estelle to allow both the protcol behaviour and complex data structure to be specified more precisely. In addition, an ASN.l compiler can be developed and interpreted with the Estelle-C compiler in order to provide a complete coverage of the automatic protocol implementation.  Bibliography  [1] CCITT Recommendation X.25, "Interface between Data Terminal Equipment (DTE) and Data Circuit termination Equipment (DCE) for Terminals Operating in the Packet Mode on Public Data Networks" 1984 [2] Message Handling Systems Conformance Testing Specification Manual X.403/CTSM.3 for Reliable Transfer Server X.410 (1984) (The Red Book) [3] CCITT Recommendation , Message Handling System , Reliable Transfer Server X.410 (1984) (The Red Book) [4] P. Schicker, "Message Handling Systems, X.400", in Message Handling Systems and Distributed Applications, North-Holland, IFIP, 1989 [5] Data Communication Networks - Message Handling Systems - Recommendations X.400-X.430, Red Book, Volume VIII, Fascicle VIII.7, CCITT, Geneva 1986 [6] ISO/TC97/SC21/WGl/Subgroup B. "Estelle - A Formal Description Technique Based on an Extended State Transition Model". DP 9074, 1984 [7] ISO/TC97/SC21/WGl/Subgroup B. "Estelle - A Formal Description Technique Based on an Extended State Transition Model". DP 9074, 1986 [8] ISO/TC97/SC21/WGl/Subgroup B. "Estelle - A Formal Description Technique Based on an Extended State Transition Model". IS 9074, 1989  76  Chapter 7. Conclusion and Future Work  77  [9] D.A.Ford, "Semi-automatic Implementation of Network Protocols", Master Thesis, University of British Columbia, 1985 [10] Vuong, S.T. and A. Lau, "A semi-automatic approach to protocol implementation - The ISO class 2 transport protocol as an example", presented as INFOCOM'87, San Francisco, CA, Apr, 1987 [11] S.T .Vuong, A.C.LAU and R.I.Chan "Semiautomatic Implementation of Protocols Using an Estelle-C Compiler" IEEE Trans. Software Engineering, vol.14, no.3. March,1988 [12] S.T.Vuong,R.I.Chan and W.Y.L.Chan "An Estelle-C Compiler for Automatic Protocol Implementation" Protocol Specification, Testing and Verification VIII, NorthHolland , IFIP, 1988 [13] S.T.Vuong, T.Paterson, J.Lu, J.Ng and K.L.Hui, "UBC Estelle-C compiler version 2.3 user's manual and internal guide" Technical Report TR90-2, in Center for Integrated Computer System Research and Dept. of Computer Science, University of British Columbia, 1990 [14] G.V.Bochmann, G.W.Gerber, and J.M. Serre "Semiautomatic Implementation of Communication Protocols" IEEE Trans. Software Engineering, vol.se-13, no.9, sept,1987 [15] G.V.Bochmann, J.P.Versus "Some comments on Transition-Oriented versus Structured Specification of Distributed Algorithms and Protocols", IEEE Trans. Software Engineering, vol.se-13, no.4, April,1987 [16] J.P.Anasart, P.Amer, and etc, " Software tools for Estelle", in Protocol Specification  Chapter 7. Conclusion and Future Work  78  , Testing and Verification, VI, IFIP/WG6.1, Amsterdam, The Netherlands: NorthHolland, 1987 [17] G.V.Bochmann, and C.Sunshine, "Formal methods in communication protocol design", IEEE, Trans, commun., Vol.COM2-28, no.2, PP. 624-631, Apr.1980 [18] R.J.Linn, "The features and facilities of Estelle", in Protocol Specification , Testing and Verification, V IFIP/WG6.1, Amsterdam, The Netherlands: North-Holland, 1986 [19] G.V.Bochmann, "Usage of Protocol Development Tools: The Results of a Survey" , in Protocol Specification , Testing and Verification, VI, IFIP/WG6.1, Amsterdam, The Netherlands: North-Holland, 1987 [20] Budiowski, Stanislaw, and Piotr Dembinski, "An Introduction to Estelle: A Specification language for Distributed Systems". Computer Networks and ISDN systems, vol 14. 1987, pp3-23. [21] L.Kovacs and A.Ercsenyl, "Specification versus implementation based on Estelle", A C M Comput,Commun.Rev., vol,16, no.4, pp4-22, July 1986 [22] D.P.Sidhu, and T.P,Blumer, "Semi-automatic Implementation of OSI Protocols", in Computer Networks and ISDN Systems 18, pp.221-238, April, 1990 [23] Courtiat, J.P., "Introducing a rendez-vous mechanism in Estelle: Estelle*", in M.Diaz, J.P. Ansart, J.P. Courtiat, P.Azema, and V. Chari (eds.), The Formal Description Technique Estelle- Results of the ESPRIT/SEDOS Project. North-Holland, 1989. [24] F. Caneschi and E. Merelli , "An Architecture for an ASN.l Encoder/Decoder ", Computer Networks and ISDN Systems 14 pp 297-303, North-Holland 1987.  Chapter 7. Conclusion and Future Work  79  [25] A.Group, "A Tutorial on Abstract Systax Notation One (ASN.l)" in Open Systems DATA TRANSFER ISSN 0741-286X, Dec, 1986 [26] G. T'Hooft, "Formal Description Techniques: Communication Tools for Data Communication Specialists", Computer Networks and ISDN Systems 14 pp 311-321, North-Holland 1987. [27] D. Rayner , "OSI Conformance Testing", Computer Networks and ISDN Systems 14 pp 79-98, North-Holland 1987. [28] Jeroen Bruijning and The SPECS Consortium , " Evaluation and Integration of Specification Languages", Computer Networks and ISDN Systems 13 pp 75-89, NorthHolland 1987. [29] R.I.Chan, B.R. Smith, etc, "A Software Environment for OSI Protocol Testing Systems", Ninth IFIP WG6.1 International Symposium on Protocol specification, Testing, and Verification, June 6-9, 1989 [30] Murray W. Goldberg, "A Request/Response Protocol to Support ISO Remote Operations", M.Sc. Thesis, Dept. of Computer Science, Unversity of British Columbia, 1989  Appendix A MR_Channel  This is how the MR_Channel is declared in this implementation:  CHANNEL MR_Channel(user, provider) ; by user : {for event RTS.ASP.DOWN: } R_OPEN_REQ(rts_down_para: rts_down_para_type); R_OPEN_RSP(rts_down_para: rts_down_para_type) ; R_TURN_PLSE_REQ(rts_down_para: rts_down_para_type) ; R_XFER_REQ(rts_down_para: rts_down_para_type) ; R_U_ABORT_REQ(rts_down_para: rts.down.para.type) ; R_CLOSE_REQ(rts_down_para: rts_down_para_type) ; R_OPEN_CFM(rts_down_para: rts_down_para_type); R_XFER_CFM(rts_down_para: rts_down_para_type); R_TURN_PLSE_IND; This is how the interaction points are described in M T L and RTS module head for MR-Channel:  MODULE entity.MTL PROCESS (MTLnu: integer); IP RTS_ASP_DOWN : MR_Channel(user) individual queue ; Up ' : MR.Channel(provider) individual queue ; END; { entity.user } MODULE entity.RTS PROCESS(RTSnu: INTEGER); IP RTS.ASP.DOWN : MR_Channel(user) individual queue ; {sender role} Up : MR.Channel(provider) individual queue ; {receiver role} END; {RTS.module}  80  Appendix B Variant Record  This is how the VARIANT RECORD has been used for the declaration of interactions coming along MR.Channel, and their associated parameters: rts_down_type = (R_0PEN_REQ, R_0PEN_RSP, R_TURN_PLSE_REQ, R.XFER.REQ, R_U_ABORT_REQ, R_CLOSE_REQ, R OPEN CFM, R.OPEN.IND, R_XFER_CFM); rts_down_para_type = RECORD case tag : rts_down_type of R_0PEN_REQ: (R_OPEN_REQ_EID: INTEGER; {connection id} resp.addr: INTEGER; {session addr} diag.md: INTEGER; {monologue, two way} i n i t . t u r n : INTEGER; {initiator, responder} udatal: datatype); {any data} R_0PEN_RSP: (R_OPEN_RSP_EID: INTEGER; {connection id} disp: INTEGER; {accepted or refused} rfse.reason: INTEGER; {refuse reason} udata2: datatype); {any data} R_TURN_PLSE_REQ: (R_TURN_PLSE_REQ_EID: INTEGER; { } prio: INTEGER); { } R.XFER.REQ: (R_XFER.REQ.EID: INTEGER; t . l i m i t : INTEGER; {max time of xfer data} udata3: datatype); R.U.ABORT.REQ: (R_U.ABORT_REQ.EID: INTEGER; reason: INTEGER); R.CLOSE.REQ: (R_CL0SE_REQ_EID: INTEGER; udata4 : datatype); {any data} R.OPEN.CFM: (R.OPEN.CFM.EID: INTEGER; refuse : integer) {negative conf} R.OPEN.IND: (R_0PEN.IND.EID: INTEGER) R.XFER.CFM: (R_XFER_CFM_EID: INTEGER) END;  81  Appendix C RS-Channel  This is how the RS-Channel has been declared: CHANNEL RS_Channel(user, provider) ; by user : { for event SESSION_ASP_UP:} S_CONN_IND(s_conn_ind_p: s_conn_ind_p_type); {1} S_CONN_CFM(s_conn_cfm_p: s_conn_cfm_p_type); {2} S_REL_IND(s_rel_ind_p: s_rel_ind_p_type); {3} S_REL_CFM(s_rel_cfm_p: s_rel_cfm_p_type); {4} S_U_ABORT_IND(s_u_abort_ind_p: s_u_abort_ind_p_type); {5} S_P_ABORT_IND(s_p_abort_ind_p: s_p_abort_ind_p_type); {6} S_TK_PLSE_IND(s_tk_plse_ind_p: s_tk_plse_ind_p_type); {7} S_CNTL_GIVE_IND(s_cntl_give_ind_p: s_cntl_give_ind_p_type); {8} S_DATA_IND(s_data_ind_p: s_data_ind_p_type); {9} S_ACT_STRT_IND(s_act_strt_ind_p: s_act_strt_ind_p_type); {10} S_SYN_MI_IND(s_syn_mi_ind_p: s_syn_mi_ind_p_type;; {11} S_SYN_MI_CFM(s_syn_mi_cfm_p: s_syn_mi_cfm_p_type); {12} S_ACT_INT_IND(s_act_int_ind_p: s_act_int_ind_p_type); {13} S_ACT_INT_CFM(s_act_int_cfm_p: s_act_int_cfm_p_type); {14} S_ACT_RES_IND(s_act_res_ind_p: s_act_res_ind_p_type); {15} S_ACT_DIS_IND(s_act_dis_ind_p: s_act_dis_ind_p_type); {16} S_ACT_DIS_CFM(s_act_dis_cfm_p: s_act_dis_cfm_p_type); {17} S_ACT_END_IND(s_act_end_ind_p: s_act_end_ind_p_type); {18} S_ACT_END_CFM(s_act_end_cfm_p: s_act_end_cfm_p_type); {19} S_U_EXCEP_IND(s_u_excep_ind_p: s_u_excep_ind_p_type); {20} S_P_EXCEP_IND(s_p_excep_ind_p: s_p_excep_ind_p_type); {21}  {28}  { for event SESSI0N_ASP_D0WN:} S_CONN_REQ(s_conn_req_p: s_conn_req_p_type); {22} S_CONN_RSP(s_conn_rsp_p: s_conn_rsp_p_type); {23} S_REL_REQ(s_rel_req_p: s_rel_req_p_type); {24} S_REL_RSP(s_rel_rsp_p: s_rel_rsp_p_type); {25} S_U_ABORT_REQ(s_u_abort_req_p: s_u_abort_req_p_type); {26} S_TK_PLSE_REQ(s_tk_plse_req_p: s_tk_plse_req_p_type); {27} S_CNTL_GIVE_REQ(s_cntl_give_req_p: s_cntl_give_req_p_type); S_DATA_REQ(s_data_req_p: s_data_req_p_type); {29} S_ACT_STRT_REQ(s_act_strt_req_p: s_act_strt_req_p_type); {30} S_SYN_MI_REQ(s_syn_mi_req_p: s_syn_mi_req_p_type); {31} S_SYN_MI_RSP(s_syn_mi_rsp_p: s_syn_mi_rsp_p_type); {32} S_ACT_INT_REQ(s_act_int_req_p: s_act_int_req_p_type); {33} S_ACT_INT_RSP(s_act_int_rsp_p: s_act_int_rsp_p_type); {34} S_ACT_RES_REQ(s_act_res_req_p: s_act_res_req_p_type); {35} 82  Appendix C.  RS.Channel  S_ACT_DIS_REQ(s_act_dis_req_p S_ACT_DIS_RSP(s_act_dis_rsp_p S_ACT_END_REQ(s_act_end_req_p S_ACT_END_RSP(s_act_end_rsp_p S_U_EXCEP_REQ(s_u_excep_req_p  83  s_act_dis_req_p_type); s_act.dis_rsp_p.type); s_act_end_req_p_type); s_act_end_rsp_p_type); s_u.excep_req_p.type);  {36} {37} {38} {39} {40}  This is how the interaction points are described in RTS and SES module head for RS-Channel: MODULE entity.RTS PROCESS(RTSnu: INTEGER); IP Sender: RS_Channel(user) INDIVIDUAL QUEUE; Receiver : RS.Channel(provider) INDIVIDUAL QUEUE ; END; {RTS.module} MODULE entity.SES PROCESS(SESnu: INTEGER); IP Sender: RS.Channel(user) INDIVIDUAL qUEUE; Receiver : RS.Channel(provider) INDIVIDUAL qUEUE ; Passer : RS.Channel(user) individual queue ; Accepter : RS.Channel(provider) individual queue ; END; {SES.module}  Appendix D The Parameters for Interactions in RS_Channel  This is how the parameters assocated with interactions coming along RS-Channel are described: {=====================f event SESSION_ASP_DQWN= s_conn_req_p_type = RECORD S_CONN.REQ_EID integer {connection id} ss_id integer {session conn id} calling_ssap integer {calling user id} called_ssap integer {called user id} qos integer {quality of service *} fu integer {functional unit *} sn integer {synch no.} tk_set integer { *} ssdu datatype; {any data} END;{22} 0 r  s_conn_rsp_p_type = RECORD S_CONN_RSP_EID integer; ss_id integer; called_ssap integer; result integer; qos integer; fu integer; sn integer; tk.set integer; ssdu datatype; END; {23} s_rel_req_p_type = RECORD S_REL_REQ_EID: integer; ssdu : datatype; END; {24} s_rel_rsp_p_type = RECORD S_REL_RSP_EID integer; result integer; ssdu datatype; END; {25} s_u_abort_req_p_type = RECORD S_U_ABORT_REQ_EID: integer; reason : integer; ssdu : datatype; 84  Appendix D. The Parameters for Interactions in RS.Channel  END;  {26}  s_tk_plse_req_p_type = RECORD S_TK_PLSE_REQ_EID: integer; token : integer; END; {27} s_cntl_give_req_p_type = RECORD S_CNTL_GIVE_REQ_EID: integer; END; {28} s_data_req_p_type = RECORD S_DATA_REQ_EID: integer; ssdu : datatype; END; {29} s_act_strt_req_p_type = RECORD S_ACT_STRT_REQ_EID: integer; act_id : integer; ssdu : datatype; END; {30} s_syn_mi_req_p_type = RECORD S_SYN_MI_REQ_EID: integer; sync.type : integer; { } sn : integer; {synch no.} ssdu : datatype; END; {31} s_syn_mi_rsp_p_type = RECORD S_SYN_MI_RSP_EID: integer; sync_type : integer; sn : integer; ssdu : datatype; END; {32} s_act_int_req_p_type = RECORD S_ACT_INT_REQ_EID: integer; reason : integer; END; {33} s_act_int_rsp_p_type = RECORD S_ACT_INT_RSP_EID: integer; reason : integer; END; {34} s_act_res_req_p_type S_ACT_RES_REQ_EID: new_act_id : old_act_id : sn :  = RECORD integer; integer; {next act id for current session integer; {interrupted act id} integer; {last confirmed checkpoint no}  Appendix D. The Parameters for Interactions in RS.Channel  old_ss_id ssdu END; {35}  : integer; {if interrupted act is on other session} : datatype;  s_act_dis_req_p_type = RECORD S_ACT_DIS_REQ_EID: integer; reason : integer; END; {36} s_act_dis_rsp_p_type = RECORD S_ACT_DIS_RSP_EID: integer; END; {37} s_act_end_req_p_type = RECORD S_ACT_END_REQ_EID: integer; sn : integer; ssdu : datatype; END; {38} s_act_end_rsp_p_type = RECORD S_ACT_END_RSP_EID: integer; result : integer; ssdu : datatype; END; {39} s_u_excep_req_p_type = RECORD S_U_EXCEP.REQ_EID: integer; END; {40} {=============f event SESSION_ASP_UP= s_conn_ind_p_type = RECORD S_CONN_IND_EID integer; ss_id integer; calling.ssap integer; called.ssap integer; qos integer; fu integer; sn integer; tk.set integer; ssdu datatype; END; {1} 0r  s_conn_cfm_p_type S_CONN_CFM_EID ss.id called_ssap result qos fu sn  = RECORD integer; integer; integer; integer; integer; integer; integer;  86  Appendix D. The Parameters for Interactions in RS-Channel  tk_set ssdu END; {2}  integer; datatype;  s_rel_ind_p_type = RECORD S_REL_IND_EID: integer; ssdu : datatype; END; {3} s_rel_cfm_p_type S_REL_CFM_EID result ssdu END; {4}  = RECORD integer; integer; datatype;  s_u_abort_ind_p_type S_U_ABORT_IND_EID: reason : ssdu : END; {5}  = RECORD integer; integer; datatype;  s_p_abort_ind_p_type = RECORD S_P_ABORT_IND.EID: integer; reason : integer; END; {6} s_tk_plse_ind_p_type = RECORD S_TK_PLSE_IND_EID: integer; token : integer; datatype; ssdu END; {7} s_cntl_give_ind_p_type = RECORD S_CNTL_GIVE_IND_EID: integer; END; {8} s_data_ind_p_type = RECORD S_DATA_IND_EID: integer; ssdu : datatype; END; {9} s_act_strt_ind_p_type S_ACT_STRT_IND_EID act_id ssdu END; {10} s_syn_mi_ind_p_type S_SYN_MI_IND_EID sync_type sn  = RECORD integer; integer; datatype;  = RECORD integer; integer; integer;  Appendix D. The Parameters for Interactions in RS-Channel  ssdu END; {11} s_syn_mi_cfm_p_type S_SYN_MI_CFM_EID sn ssdu END; {12}  datatype; = RECORD integer; integer; datatype;  s_act_int_ind_p_type = RECORD S_ACT_INT_IND_EID: integer; reason : integer; END; {13} s_act_int_cfm_p_type = RECORD S_ACT_INT_CFM_EID: integer; reason : integer; END; {14} s_act_res_ind_p_type S_ACT_RES_IND_EID: new_act_id old_act_id sn old_ss_id ssdu END; {15}  = RECORD integer; integer; integer; integer; integer; datatype;  s_act_dis_ind_p_type = RECORD S_ACT_DIS_IND_EID: integer; reason : integer; END; {16} s_act_dis_cfm_p_type = RECORD S_ACT_DIS_CFM_EID: integer; END; {17} s_act_end_ind_p_type = RECORD S_ACT_END_IND_EID: integer; sn : integer; END; {18} s_act_end_cfm_p_type = RECORD S_ACT_END_CFM_EID: integer; ssdu : datatype; END; {19} s_u_excep_ind_p_type = RECORD S_U_EXCEP_IND_EID: integer; END; { 2 0 }  Appendix D. The Parameters for Interactions in RS.Channel  s_p_excep_ind_p_type = RECORD S_P_EXCEP_IND_EID: integer; END; {21}  89  Appendix E Test Cases  The summary of the test cases submitted to RTS with their identification number: In Association Establishment Phase: 1.1.1.1 IUT (Implementation Under Test) can establish an association. 1.1.1.2 IUT reacts correctly on attempt to establish association with a peer busy RTS. 1.1.1.3 IUT reacts correctly on attempt to establish association with a peer RTS which does not validate password and MTA name. 1.1.1.4 IUT reacts correctly on attempt to establish association in TWA mode with peer RTS which does not accept TWA. 1.2.1.1 IUT can establish association as a responder in monologue mode. 1.2.1.2 IUT cab establish association as a responder in TWA mode. 1.2.1.3 IUT can establish association when choosing token assignment. 1.2.1.4 IUT can refuse association when it is busy. 1.2.1.5 IUT can refuse association when validation failure detected. 1.2.1.6 IUT can refuse TWA association. In Association Release Phase: 2.2.1.1 IUT can receive orderly release request and release correctly. In Data Transfer Phase: 3.1.1.1 IUT can send APDUs using checkpoint and window size that it proposed. 3.1.1.2 IUT can send APDUs when checkpointsize that it proposed are modified by the tester. 3.1.1.3 IUT can send APDUs when windowsize that it proposed are modified by the tester. 3.1.1.4 IUT can send APDUs when tester modifies the checkpointsize. 3.1.1.5 IUT can send APDUs without checkpointing. 3.2.1.1 IUT can receive APDUs if null checkpointsize is proposed at association establishment. 3.2.1.2 IUT can receive APDUs if windowsize = 1 and checkpointsize = 1 have been proposed at association establishment. 3.2.1.3 IUT can receive APDUs if windowsize = 100 and checkpointsize = 100 have been proposed at association establishment. In Turn Exchange Phase: 90  Appendix E. Test Cases  3.3.1.1 IUT can give control to peer, receive an APDU and accept session release. Checkpointing is used. 3.3.1.2 IUT can five control to peer, receive an APDU and accept session release. No checkpointing is used. 3.3.1.3 IUT can five control to peer, receive an APDU, receive control again and send an APDU or release session connection. Checkpointing is used. 3.3.1.4 IUT can perform as in 3.3.1.3. No check pointing is used. 3.3.1.5 IUT ask and receive tokens, checkpointing is used. 3.3.1.6 IUT can ask and receive tokens. No check pointing is used. 3.3.1.7 The tester establishes an association, sends an APDU and passes the control to the IUT. The IUT receives the APDU, gets control and may send an APDU to the tester. Then the IUTfivescontrol back to the tester. In Association Recovery Phase: When IUT as a Sender: 4.1.1.1 Tester issues User Exception Report with reason of :local SSuser Error" . Activity is interrupted and resumed by IUT. 4.1.1.2 Tester does not confirm any checkpoint but issues User Exception Report with reason of "local SSuser error". Activity is discarded and restarted by IUT. 4.1.1.3 Tester issues User Exception Report with reason of "unrecoverable procedure error" after confirming a checkpoint. The Activity is discarded and restarted by IUT. 4.1.1.4 IUT aborts session connection outside an activity. IUT has data token and has outstanding APDUs. Recovery: must retain tokens and send unsent APDUs. 4.1.1.5 session provider aborts session connection outside an activity. IUT has data tokens and has outstanding APUDs, Recovery: must retain tokens and send unset APDUS. 4.1.1.6 IUT aborts session connection outside an activity. IUT has issued and S-Control-Give Request with no confirmation that tokens were received. Recover: tokens must be given to tester. 4.1.1.7 Session provider aborts session connection outside an activity. IUT has issued S-ControlGive Request with no confirmation that tokens were received. Recovery: token must be given to tester. 4.1.1.8 IUT aborts session connection outside an activity. IUT has given the tokens to tester with already-sent APDUs. Recovery: tokens are assigned as acceptor chooses. 4.1.1.9 Session provider aborts session connection outside an activity. Recovery IUT performs recovery and resumes current activity. 4.1.1.10 IUT aborts session connection inside an activity. Recovery: IUT performs recovery and resumes current activity. 4.1.1.11 Session provider aborts session connection inside an activity. Recover IUT performs recovery and resumes current activity.  Appendix E. Test Cases  4.1.1.12 Tester aborts session connection outside an Activity. IUT had data token and still has APDUs to send. Recovery: IUT specifies that it retains the tokens and sends remaining APDUs. 4.1.1.13 Tester aborts session connection outside an activity. IUT has issued a Turn-Give Request with no confirmation that tokens were received. Recovery: IUT specifies that it gives tokens to tester. 4.1.1.14 Tester aborts session connection outside an activity. IUT has given tokens to tester which has already sent APDUs. Recovery: tokens are assigned as the " acceptor chooses". 4.1.1.15 Tester aborts session connection inside an activity. Recovery: IUT performs recovery and resumes current activity. 4.1.1.16 The tester aborts the session connection inside an activity. The IUT performs a recovery, resumes and discards the activity. Checkpointing is not used. 4.1.1.17 The tester issues an exception report inside an activity. The IUT discards the activity and issues an Exception Indication to its RTS-user. Checkpointing is not used. When IUT as a Responder: 4.2.1.1 Tester resumes previously interrupted activity in same session connection. 4.2.1.2 Tester restarts previously discarded activity in same session connection. 4.2.1.3 IUT requests user abort outside an activity. Tester has data tokens and has APDUs to send. Recovery: tester specifies that it retains the tokens and sends remaining APDUs. 4.2.1.4 Session provider aborts association outside activity. Tester has data token and still has APDUs to send. Recovery: tester specifies that it retains the token sends the remaining APDUs. 4.2.1.5 IUT requests user abort inside an activity. Recovery : tester performs a recovery and resumes current activity. 4.2.1.6 Session provider aborts associations inside an activity. Tester has data token and has APDUs to send. Recovery : tester performs a recovery and resumes current activity. 4.2.1.7 Tester requests a userabort outside an activity. Tester has data token and still has APDUs to send. Recovery: tester specifies that it retains the tokens and sends remaining APDUs. 4.2.1.8 Tester requests a userabort outside an activity. Recovery : tester performs a recovery and resumes current activity. 4.2.1.9 S-Activity-End-Confirmation and S-U-Abort collide inside tester activity. Recovery : tester performs a recovery and resumes current activity. 4.2.1.10 Tester requests for an userabort outside an activity. It performs a recovery, resumes and discards the current activity and sends the APDU in a new activity.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051972/manifest

Comment

Related Items