Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Formal specification, simulation, and performance evaluation of a mobile data link protocol using Estelle Chen, Ted Y. G. 1993

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

Item Metadata


831-ubc_1994-0073.pdf [ 1.41MB ]
JSON: 831-1.0064801.json
JSON-LD: 831-1.0064801-ld.json
RDF/XML (Pretty): 831-1.0064801-rdf.xml
RDF/JSON: 831-1.0064801-rdf.json
Turtle: 831-1.0064801-turtle.txt
N-Triples: 831-1.0064801-rdf-ntriples.txt
Original Record: 831-1.0064801-source.json
Full Text

Full Text

FORMAL SPECIFICATION, SIMULATION,AND PERFORMANCE EVALUATION OFA MOBILE DATA LINK PROTOCOLUSING ESTELLEbyTED Y. G. CHENB. A. Sc., University of British Columbia, 1991A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENT FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF ELECTRICAL ENGINEERINGWe accept this thesis as conformingto the required standardUNIVERSITY OF BR TISH COLUMBIADecember 1993© Ted Y. G. Chen, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenperm ISSI Ofl.(Signature)___________________Department of L&T1?2’L 96.rThe University of British ColumbiaVancouver, CanadaDate__________________DE-6 (2/88)AbstractCommunication protocols consists of a set of distributed algorithms which allow two ormore communicating entities to exchange information. Typically, these protocols represent oneof the seven layers in the Open Systems Interconnection (OSI) Reference Model. Traditionally,protocols approved by international standards organizations, such as the ISO or CCITf, havebeen defined by a combination of English prose, state tables, and state diagrams. These informalmethods, although useful, are imprecise and can lead to ambiguities. Using Estelle, a formaldescription technique (FDT), protocol specifications can be made clear and free from anyambiguities and provide a standardized manner in which to document protocol operations. Formalmethods also provide a foundation for performing protocol validation and implementation, andevaluating protocol efficiency.A brief summary of Estelle constructs and its application in modelling communicationprotocol elements is presented, and a data link layer protocol, representing layer two of theOSI model, is introduced. This protocol is based on a Type-IT Hybrid ARQ scheme and wasdesigned to provide reliable communications in a mobile radio environment. The mobile datalink protocol (MDLP) is formally specified using Estelle. In addition, the MDLP specification istested for conformance to the informal prose description. Finally, the operation of the MDLP issimulated and a throughput evaluation is performed using a statistical channel model. Moreover,for comparison purposes, throughput results are also obtained for a selective repeat ARQ scheme.The protocol design, testing, and simulation was performed using the Estelle DevelopmentToolset (EDT).11Table of ContentsAbstractList of TablesList of FiguresAcknowledgments xIntroduction1.1 Formal Methods and Estelle1.2 Data Link Layer Services1.3 Objectives1.4 Thesis OrganizationEstelle 62.1 Introduction2.2 Estelle Constructs2.3 SummarySpecification of the MDLP3.1 Introduction3.2 Service Primitives and Frame Types3.3 Informal Description of the MDLP111IIviviiChapter 1Chapter 2Chapter 31..31111• 11• 133.4 Frame Structure.3.5 Module Structure3.6 State Diagram for Protocol Logic3.7 Protocol Logic — Estelle Specification3.7.1 Support Subroutines3.7.2 Link Connection3.7.3 Link Disconnection3.7.4 Flow Control3.7.5 Data Transfer3.7.6 Timers3.8 Summary1920232526313436374749Chapter 4 Testing the MDLP4.1 Introduction4.2 Simulation Tools and Testing Methods4.3 Testing Operations4.4 Summary5151525356MDLP Simulation and Performance Evaluation5.1 Introduction5.2 Abstraction5.3 Using Channel StatisticsivChapter 5 575758595. Module ConnectionChannel Simulator ModuleSimulation ResultsSummary61636569SupportBibliographyAppendix A: Estelle Code Listing7680Chapter 6 Conclusions 726.1 Conclusions 726.2 Suggestions for Future Research 736.2.1 Robust Link Management 736.2.2 Explicit Data Link Flow Control 736.2.3 Extension to Multiple Access 746.2.4 Time in Estelle 746.2.5 Estelle Channel Model . . 756.2.6 Soft Decoding and Bit Level 75VList of Tables1 MDLP Service Primitives 122 MDLP Frame Types 123 Protocol Field Sizes 214 Channel Statistics 60vi2. 1720222425262727282930313335List of Figures1.1 Network, Data Link, and Physical Layer connections and Service PrimitivesEstelle Module HierarchyEstelle Module RepresentationTransition SyntaxLink Establishment — Flow diagramLink Disconnection — Flow diagramFlow Control — Flow diagram, 1(n) = Information frame withFrame Structure of the MDLPHierarchy of the MDLP moduleMDLP Estelle OverviewState Diagram of Protocol Logic (PrL) ModuleProtocol Logic Module — Estelle overviewProcedure Clear — EstelleProcedure inc and Function between — EstelleProcedure PrepareFrame EstelleProcedure UpdateSenderWindow — EstelleProcedures TimeCount and TimeCount2 — EstelleFunctions Combine 1 and Combine2 — EstelleLink Establishment — EstelleLink Disconnection — EstelleVII3. SREJ frame received — Estelle3.253.263.273,283.293.304. Normal Module ConnectionConnection for Performance Simulation.Channel Simulator Module Code. .VII’frame withack#m... 464848495454556162626437384041424243444445Flow Control EstelleReceiving data packets from the Network Layer — EstelleI frame received — EstelleCase 1: No previous copies — EstelleCase 2: P1 and P1 (or P2 and P2) — EstelleCase 3: P1 and P2 (or P2 and P1) EstelleSend ordered data to the Network layer — EstelleRR frame received EstelleInvalid frame received — EstelleRetransmission using SREJ — Flow diagram, I(n, P) = Informationseq# n and Indicator bit P; SREJ(m) = Selective Reject frame withTimer T1 — EstelleIdle timer tick — EstelleTimer T2 — EstelleWindow Variable ObserverFireable Transition ObserverRandom Execution MacroPlot of Channel Statistics vs. SNR5,35.45.5 Throughput for Selective Repeat ARQ Scheme 675.6 Throughput for Type-IT ARQ Scheme 685.7 SR vs. Type-TI 696.1 Data Link Module structure for Multiple Access 74ixAcknowledgmentsI would like to express my sincere gratitude to my supervisors Dr. Samir Kallel and Dr.Victor Leung for their proposition of this research topic, financial subsidization, guidance, andencouragement.I am greatly indebted to Dr. Son Vuong for his useful discussions and explanations. I alsoextend my thanks to Sattar Bakhtiyari for generously providing his computer simulation data.As well, I wish to express my gratitude to the B. C. Science Council for their financial support.I would like to thank my parents, Amy and Stewart Chen, for their love, care, guidance, andsupport which has encouraged me in reaching this point. My loving thanks to them can only beexpressed by the hope that this thesis will make them proud of my accomplishments.x1Chapter 1 Introduction1.1 Formal Methods and EstelleEstelle, an International Standard defined by ISO 9074, is a formal description technique(FDT) for specifying distributed and concurrent information processing systems [1]. It isparticularly suited to describing communications protocols and services of the Open SystemsInterconnection (OSI) model. Estelle (Extended State Transition Language) is a techniquebased on an extended state transition model, and can be viewed as a set of extensions to theprogramming language Pascal.Traditional ISO protocol standards are usually defined by a combination of natural languageprose, state tables, and state diagrams. Although these methods are useful, they can leadto ambiguities and are often prone to misinterpretation [2]. Using formal methods, protocolspecifications can be made clear and free from any ambiguities, providing a standardized mannerin which to document protocol operation. In addition, the modular structure of Estelle providesa flexible way to make updates and improvements to the protocol.The design of communications protocols can be separated into three areas: specification,testing and verification, and implementation. A formalized description method provides anexcellent basis for performing all of these major functions and results in quicker and moreefficient protocol development.A number of other standardized formal description methods have appeared over the past fewyears, including LOTOS (Language Of Temporal Ordering Specification) [3], SDL (Specificationand Description Language) [4], ASN.l (Abstract Syntax Notation One) [5] and TTCN (Tree andChapter 1. Introduction 2Tabular Combined Notation) [61. Of the FDT’s currently in use, LOTOS and Estelle haveattracted the most research and development attention. One of the most extensive industrialapplications of LOTOS was the specification and implementation of ISDN Q.931 [7, 8]. Othersare planning how LOTOS can be transferred from research to commercial development [9], orlooking for methods for specifying and validating protocols in LOTOS [10]. There has also beena significant interest in using Estelle, both theoretically [11, 12], and practically [13, 14]. Ofparticular interest is the use of Estelle in the specification, validation, and performance evaluationof the XTP (Xpress Transfer Protocol) used in high performance real-time applications such asmultimedia [15].1.2 Data Link Layer ServicesIn a data communications system, the function of the data link layer is to provide highlyreliable data services both to the network layer above and to the interfaces of the physical layeror medium access control (MAC) sub-layer below. The major role of a data link protocol (DLP)is to provide a virtually error-free logical link over an unreliable physical link. This is achievedby grouping the data to be transmitted into frames, adding redundancy for the purpose of errordetection and correction, sequencing the frames, and providing a set of distributed algorithms bywhich the nodes at either end of the link initiate data recovery through retransmissions. CurrentDLP’s, such as LAPB, which is used by X.25 [16], tend to assume a relatively error-free channeland cannot provide robust communications over a mobile radio link characterized by Rayleighfading. In addition, LAPB uses the relatively inefficient Go-Back-N automatic-repeat-request(ARQ) scheme, and would not be suitable for this protocol. The High-Level Data link Control(HDLC) [17, 18] protocol, upon which LAPB is based, supports both Go-Back-N and selectiveChapter 1. introduction 3reject ARQ schemes. A mobile data link protocol (MDLP) based on an efficient and reliableType-Il Hybrid ARQ scheme using convolutional coding has been proposed [19, 20, 21], andwill be the subject of this thesis. The MDLP will use a modified version of the HDLC frame,as well as adopting many of HDLC’ s operational procedures.Each layer in the OSI Basic Reference Model [22] provides services to the layer locatedabove by drawing upon resources of the layer below. These services are accessed throughcommand messages, called service primitives, which are exchanged between adjacent layers.These primitives provide a means to setup, maintain, and tear down data connections, as wellas transfer data. The lower three OSI layers, the network, data link, and physical, are shown inFigure 1.1 with a list of the service primitives supported by the MDLP.1.3 ObjectivesBased on the previous discussions, this thesis deals with the use of Estelle in communicationsprotocol design, and in particular, the investigation of the advantages of using such a formalizedlanguage in designing a Type-IT Hybrid ARQ scheme for mobile radio. The research contributionof this thesis can be summarized as follows:1. Investigation of how Estelle can be used in the design of communications protocols, inparticular, the MDLP.2. Presentation of a formalized specification of the MDLP in Estelle.3. Execution of tests to examine the logical correctness of the specification.4. Simulation of the operation of the MDLP in software and evaluate the throughput performance of the specification using a statistical channel model.Chapter 1. Introduction 4CONI’.TReqCONNRespDISCReqDISCRespFLOWSTARTReqFLOWSTOPReqDATAReq(Data)‘-,NL NetworkProcess LayerN..DL Dl DataLinkProcess LayerD2CONNIndCONNConfDISCIndDISCConIFLOWSTARTIndFLOWSTOPJndDATAInd(Data)DATAInd(Data Frame)wDATAReq(Data Frame)PL p PhysicalProcess Layer )Figure 1.1 Network, Data Link, and Physical Layer connections and Service PrimitivesChapter 1. Introduction 51.4 Thesis OrganizationIncluding this introductory chapter, the thesis consists of a total of six chapters and isorganized as follows:Chapter 2 is a review of Estelle concepts with an introduction to constructs used in assemblingprotocol specifications. In Chapter 3, an informal description of the MDLP is presented. Theservice primitives provided by the MDLP and the types of frames exchanged by the MDLP arealso included in this chapter. As well, the data frame and Estelle module structures are discussedand a state diagram of the protocol logic is introduced. To complete the chapter, portions ofthe formal Estelle specification are presented grouped by protocol function. Chapter 4 discussessome procedures used to test the MDLP for conformance to the informal prose description. InChapter 5, the protocol specification is executed and the throughput performance of the MDLPis obtained using a statistical model of a Rayleigh faded mobile radio channel. For comparisonpurposes, the performance of a selective repeat protocol is also presented. Finally, Chapter 6completes the thesis with conclusions and a discussion of topics for future research.6Chapter 2 Estelle2.1 IntroductionDistributed systems, in which several components may be cooperating and executing inparallel, are much more difficult to describe than the classical sequential systems. Estelle is alanguage for specifying distributed systems, particularly those of communications protocols andservices. It includes numerous features related to communications protocols such as processhierarchy, message passing, FIFO queues, time constraints and synchronous/asynchronous parallelism. Protocol specifications can benefit from a clear and precise formalized descriptionmethod by adopting Estelle.Although Estelle is an internationally accepted FDT, it is of limited use by itself, withouttools to exploit its inherent advantages. A number of Estelle tools have been developed sinceits definition [23, 24, 25]. For this thesis, the Estelle Development Toolset (EDT) [26] is used,which consists of two tools, an Estelle-C compiler (Ec) and an Estelle simulator/debugger (Edb).A description of these two tools is presented in later chapters.2.2 Estelle ConstructsThe framework of an Estelle specification is a set of cooperating entities called modules,interacting with each other by exchanging information through channels. The behaviour ofthese modules is described in terms of a non-deterministic communicating state transition systemwhose transition actions are given in the form of Pascal statements (with some restrictions andextensions). These modules, which are represented graphically as rectangles, may be nested,Chapter 2. Estelle 7forming a parent/child relationship as shown in Figure or Figure The root of thetree or the largest enclosing box (module A in this case) represents the main module of thespecification.AB CID I IGIE IIF I IHFigure 2.1 Estelle Module HierarchyThe communications interface of a module is defined using three concepts: (1) interactionpoints; (2) interactions; and (3) channels. Each module has a number of input/output accesspoints, called interaction points, which are abstract interfaces used by the module to interactwith other connected modules. A channel is associated with each interaction point, whichdefines two sets of interactions, or messages, which can be sent over the channel. Thesetwo sets are a list of interactions which are allowed to enter and exit, respectively, through aparticular interaction point. A channel is a hi-directional link that connects interaction pointsbetween communicating modules. An interaction received by a module at an interaction point isappended to an unbounded first-in-first-out (FIFO) queue associated with that point. The modulename and class, the name and location of the interaction points, and their associated interactionsb)Chapter 2. Estelle 8of a generic module are shown in Figure 2.2. Arrows indicating the names and directions ofinteractions through their respective points are also shown.The behaviour of each module is described by a set of reachable states and a numberof transition statements which depicts an extended finite state machine (EFSM). A transitionconsists of two parts: a conditional part which lists the events which must occur to enable thetransition, and an action part which lists a sequence of Pascal statements and Estelle commandsto be executed when the transition is fired. A general transition statement is shown in Figure2.3. The transition enables a change of state from state_i to state_2 under the conditionsspecified in the WHEN, PROVIDED, and PRIORITY statements. The WHEN condition is enabledwhen a particular interaction has arrived at an interaction point, the PROVIDED condition isenabled when the given predicate statement is satisfied and the PRIORITY condition is used toprioritize transitions when more than one is enabled. A DEIAY clause may also be included todelay the execution of the transition. The body of the transition can be used to examine or setFigure 2.2 Estelle Module RepresentationChapter 2. Estelle 9TRANSFROM st:at:e_lWHEN event:PROVIDED predicat:ePRIORITY expressionDELAY(t:ime)TO state_2BEGINENO;Figure 2.3 Transition Syntaxinternal state variables, output frames, perform interactions with other modules, and to set orrelease timers. A subset of Pascal statements is used to perform these functions in the actionpart of the transition.The module specification also includes any constant, type, variable, function, or proceduredefinitions as well as a list of all interaction points and their associated channels. Once allmodules and channels have been defined, they may be interconnected using the CONNECT andATTACH commands. Estelle, and its application in specifying distributed systems, is discussedin further detail in [27].2.3 SummaryThe basic Estelle constructs have been presented, and even complex communications protocols can be constructed using these elements. Each module can be assigned a specific task, beit encoding data frames, routing messages, or performing calculations. The channel and interaction concept is particularly suited to handle inter-layer service primitives, as well as to passinformation between modules lower in the hierarchy structure. The parallel module executionpossible with Estelle allows the realistic modelling of the two independently running stations inChapter 2. Estelle 10the MDLP. These Estelle structures and transition rules provide a clear and precise manner inwhich to document a protocol. Conformance testing, implementation, and determination of protocol efficiency can all be accomplished, with the appropriate software tools, from this commonformal specification.11Chapter 3 Specification of the MDLP3.1 IntroductionA framework for overall development using Estelle was presented in [28]. In this chapter,the specification of the mobile data link protocol is discussed in detail, beginning with the serviceprimitives supported by the MDLP and the frame types used by the protocol in Section 3.2. Adetailed informal description of the MDLP is presented in Section 3.3. In addition to providing aformalized notation for documenting protocol operations, the Estelle specification also providesa foundation for testing and simulation which will be discussed in Chapters 4 and 5. The framestructure used by the protocol is discussed in Section 3.4 and the MDLP module construction ispresented in Section 3.5. A state diagram, with transition I/O conditions, is shown in Section 3.6.In Section 3.7, portions of the formal Estelle specification of the MDLP are presented groupedby function. Finally, the chapter contents are summarized in Section Service Primitives and Frame TypesThe data link layer provides services to the network layer above through a set of serviceprimitives which are passed between the two adjacent layers. These primitives allow the networklayer to initiate a connection or disconnection and pass data which is to be transferred over thecommunications channel. Similarly, the data link layer draws upon the resources provided by thephysical layer located below to fulfill these services. The fourteen service primitives providedby the MDLP are listed in Table 1,Chapter 3. Specification of the MDLP 12Table 1. MDLP Service PrimitivesPrimitive Label(Parameters)Connection Request CONNReq(Called address, Calling Address)Connection Response CONNResp(Responding Address)Connection Indication CONNInd(Called Address, Calling Address)Connection Confirm CONNConf(Responding Address)Disconnect Request DISCReqDisconnect Response DISCRespDisconnect Indication DISCIndDisconnect Confirm DISCConfFlow Start Request FLOWSTARTReqFlow Stop Request FLOWSTOPReqFlow Start Indication FLOWSTARTIndFlow Stop Indication FLOWSTOPIndData Request DATAReq(Data)Data Indication DATAInd(Data)Peer MDLP layers communicate, over the physical channel, by assembling control information and data into frames. Each frame has a specific function, be it to set up the link, send data, orto send an acknowledgment. The MDLP uses six different frames and they are listed in Table 2.Table 2. MDLP Frame TypesFrame Type LabelSet Asynchronous Balanced Mode SABMUnnumbered Acknowledgment UADisconnect DISCReceiver Ready RRSelective Reject SREJInformation IChapter 3. Specification of the MDLP 133.3 Informal Description of the MDLPThe MDLP is a point-to-point full-duplex connection oriented protocol using a TypeII Hybrid ARQ scheme representing the data link layer in the OSI Reference Model. Ituses a modified version of the selective repeat protocol found in [29]. The user of theMDLP, the network layer, accesses services provided by the MDLP through service primitiveswhich are command messages exchanged between the network and data link layers of the twocommunicating stations. For example, a Connection Request primitive is used to instruct theMDLP to initiate a data link connection. Similarly, other primitives are used to exchange thedata that the network layer will be transmitting over the channel. The tasks that the MDLPwill be required to perform can be grouped into 3 areas: link connection, data transfer, andlink disconnection.The link connection and disconnection features are similar and relatively straightforward.There are eight service primitives and three MDLP frame types used to support these twofunctions, and they are listed as the foremost entries in Table 1 and Table 2, respectively.These primitives usually occur in the order Request, Response, Indication, and Confirm, withthe MDLP acting as an intermediary to service these commands between the two stations. ASet Asynchronous Balanced Mode (SABM) frame is transmitted in response to a ConnectionRequest primitive, and a Disconnect (DISC) frame is transmitted in response to a DisconnectRequest primitive. The remote station is notified through a Connection/Disconnection Indicationprimitive and responds with a Connection/Disconnection Response. For this protocol, it isassumed that the remote station always accepts the Indication primitive with a Response primitive,and cannot reject the link setup or disconnection. The link connection and disconnectionChapter 3. Specification of the MDLP 14phases are completed with the return of an Unnumbered Acknowledgment (UA) frame andsubsequent Connection/Disconnection Confirm primitive. The Connection primitives are alsoused to exchange addressing information. Flow diagrams of these 2—way handshake proceduresfor link connection and link disconnection can be seen in Figure 3.1 and Figure 3.2, respectively.At this time there are no error recovery procedures for link management, and this is noted inSection 6.2.1 as a topic for future research.Base Station Remote StationNetwork Data Link Data Link NetworkCONNReqSABM— CONNIndONNConf - - - - - --CONNRespFigure 3.1 Link Establishment Flow diagramThe data transfer phase forms the core of the protocol, and includes both the exchange of datapackets and flow control mechanisms. Both stations incorporate sliding window mechanisms tomanage their data packets. In sliding window protocols, each transmitted frame is sequencedwith a number ranging from 0 to some maximum. For convenience, this number is usually2 — 1 so that it can fit exactly within a n-bit field within the frame header. At any one time, thetransmitter maintains a list, called the sending window, of sequence numbers that it is allowed tosend. Similarly, the receiver maintains a receiving window, which is a list of sequence numbersthat the receiver is allowed to accept. When a data packet arrives from the network layer in aChapter 3. Specification of the MDLP 15Base Station Remote StationNetwork Data Link Data Link Networkcz:z:zzzzFigure 3.2 Link Disconnection — Flow diagramData Request primitive, it is assigned the next higher sequence number and the upper edge ofthe sending window is increased by one. Likewise, when an acknowledgment is received, thelower edge of the sending window is advanced by one. The sending window, in effect, keepstrack of all unacknowledged frames and is used to initiate retransmissions through timer expiry.The receiving window lists the frames which may be accepted by the receiver. Frames whichdo not fall into the window are discarded. When the frame corresponding to the lower edgeof the receiving window is received without error, it is passed to the network layer in a DataIndication Primitive and the window is advanced by one, provided that the data link layer is notbeing flow controlled by the network layer. Note that the receiving window always remains thesame size and can accept frames falling within the window in any order. Although it need notbe, the receiving window of the MDLP is the same size as the sending window for reasons offlow control discussed below. To avoid the problem of the receiver overlapping old sequencenumbers after advancement, the sending and receiving window sizes are limited to half of theChapter 3. Specification of the MDLP 16maximum sequence number.Flow control mechanisms are required in order to prevent either the data link layer or thenetwork layer from sending data at too high a rate for the other layer to process or buffer. Again,these functions are accessed through four service primitives, Flow Start Request and Indication,and Flow Stop Request and Indication, and are listed in Table 1. Figure 3.3 is a flow diagramof the case where the network layer is providing the data link layer with information at too higha rate, and flow control must be exercised. In this case, the network layer has totally filled thesending window of the data link layer and the data link is forced to assert a Flow Stop Indicationprimitive to cease the transmission of any further data packets from the network layer. Whenan acknowledgment advances the sending window to make room for further data packets, thedata link asserts a Flow Start Indication primitive to resume data flow. Flow Stop Request andFlow Start Request are used similarly to stop and start the flow of data packets being acceptedby the network layer from the data link layer. Pausing the flow of data to the network layerposes another flow control problem. Data packets are buffered in the receiving window untilthe network layer is ready to continue accepting further packets, but this buffer is limited andthere needs some method to prevent overflow. The receiver window can implicitly stop theflow of data coming from the transmitter by withholding acknowledgments while network flowcontrol is in effect. Since the sending and receiving windows are the same size, the transmittercan never send more than the receiver is willing to accept. This, of course, leads to multipleretransmissions, due to timer expiry, for these unacknowledged frames by the transmitter. Theseunneeded transmissions are simply discarded by the receiver. Once network flow is resumedall data in the receiving window is sent to the network layer, and operation continues normally.Chapter 3. Specification of the MDLP 17Explicit flow control between the peer data link layers is possible with the use of a ReceiverNot Ready (RNR) frame, and this is noted in Section 6.2.2 as a topic for future research.Base Station Remote StationNetwork Data Link Data Link NetworkDATAReq1(3)DATAReq -— — — — — —— 1(4) — — — DATAIndOWSTOPIn - - DATAIndRR --LOWSTARTI - — - - - - - - - -DATAReq — — 1(0)Figure 3.3 Flow Control — Flow diagram, 1(n) = Information frame with seq# nUnfortunately, the exchange of data between two stations is not error-free, and a retransmission algorithm is required for error recovery. The two primitives, Data Request and DataIndication, listed in Table 1, and three MDLP frame types, listed in Table 2, Receiver Ready,Selective Reject, and Information are used in the data transfer phase. The two primitives areused to exchange data packets with the network layer (see Figure 1.1). All three frame typescontain an acknowledgment number, used to acknowledge outstanding frames being held by thetransmitter with sequence numbers up to and including the acknowledgment number containedwithin. The Receiver Ready frame is used as an explicit acknowledgment, and the SelectiveReject frame is used to request the retransmission of the next outstanding sending sequenceChapter 3. Specification of the MDLP 18number (acknowledgment number + 1). Note that this is in contrast to the HDLC conventionwhere the acknowledgment number represents the next outstanding sequence number.The data field is encoded with a rate 1/2 convolutional code in which the two outputsequences are denoted P1 and P2. Data packets received from the network layer are placed intoa transmit buffer from which they can be extracted and encoded into either P1 or P2. Duringdata transfer, the transmitter calculates P1 for each successive packet placed in the buffer andassembles the encoded data into an Information frame. The assembled frame, which consistsof a flag, a header, a header checksum, the encoded data and a data checksum field, is thensent to the physical layer for transmission over the mobile link. The sizes of each field in theframe is shown in Figure 3.4. Upon acknowledgment of correct reception, either by an explicitor piggybacked acknowledgment, the data packet is removed from the transmit buffer and thetransmitter window is advanced. If a retransmission is required, either by a Selective Rejectframe or a timer expiry, the transmitter assembles a new data frame using the second encoderoutput sequence P2. This alternating procedure between P1 and P2 is repeated, for that datapacket, until an acknowledgment is received, indicating that the receiver has been able to decodethe data without error. Note that there is a timer, T1, placed on each outgoing data frame. Thistimer is used to initiate retransmissions when either the data or its corresponding acknowledgmenthas been lost. A second timer, T2, is also required to update window information during lowreturn channel utilization. The receiver does not discard incoming data frames which embeddedpackets have been damaged, but stores them for use in subsequent decoding attempts. In thisARQ scheme the receiver has a memory of one, meaning that only one previous copy is stored.When retransmissions are received, they are first checked for validity. If it is invalid, it isChapter 3. Specification of the MDLP 19combined with the previous copy, and another decoding attempt is performed. If decoding isstill not successful, the oldest copy of the data is discarded, the newest copy is placed in thereceiver buffer, and a Selective Reject frame is returned. Frames that are successfully decodedare returned, in their sequenced order, to the network layer of the receiving station. Note thatthe header portion of the frame must be decodable without error before the rest of the framecan be processed.3.4 Frame StructureThe frame structure used by the MDLP is shown in Figure 3.4. A three byte sequence,represented as 2941B3 in hexadecimal, is used as the flag at the beginning of the frame. Incontrast, the HDLC frame uses a one byte flag, 01111110, to delimit the frame and performsbit-stuffing to obtain flag transparency. The header contains important control information suchas frame type (listed in Table 2), data packet length, sequence and acknowledgment numbers, aP1/P2 indicator bit, and addresses, and is protected by a two byte cyclic redundancy code (CRC)for the purpose of error detection. Since the length of the data field is carried within the header,no end flag is required to signify the end of the frame. In addition, no bit-stuffing is performedas the probability of the 24 bit flag sequence appearing within the frame is significantly lowerthan that of the 8 bit HDLC flag. The authenticity of a flag sequence is determined by examiningthe header. Using this method, a frame with a damaged header is equivalent to losing the flag.Due to the importance of the header, the header and its corresponding checksum is encoded witha rate 1/2 convolutional code. This was required to provide an extremely robust header whichis essential for any processing of a received frame.Chapter 3. Specification of the MDLP 20FLAG HEADER HEADER CRC DATA DATA CRC24 bits 41 bits 16 bits 1024 bits 32 bitsFigure 3.4 Frame Structure of the MDLPThe data field contains either the P1 or P2 output sequence of the rate 1/2 encoder, whichcan be up to 1024 bits in length and is protected by a 32 bit CRC. Currently, the MDLP does notsupport any splitting or concatenating of packets. The data packets are passed to the receivingnetwork layer in the identical order sent by the transmitting network layer. In performancesimulations presented in Chapter 5, the assumption is made that the packet size is always 900bits in length. Note that this is a simulation limitation only. The sizes of each individual field islisted in Table 3. The miscellaneous field in the header would be used in enhancements to theprotocol. In an adaptive code rate scheme, such as the one presented in [301, this field couldbe used to indicate the coding rate of the data. After the frame has been assembled, all fields,except for the flag, are also bit interleaved. This process rearranges the relative bit positions toprovide resistance to burst channel errors. For example, the bit pattern 1111100000 interleavedwith a depth of 1 would result in 1010101010. The effect of interleaving is to “spread out” bursterrors over the entire frame, rather than in one specific area.3.5 Module StructureThe MDLP module representing the data link layer of Figure 1.1 can be seen in Figure 3.5.As shown, the root MDLP module contains two child modules, Protocol Logic (PrL) and FrameCodec (FC). The PrL module operates using a logical frame, which is an internal representationof an actual physical frame. For example, in a physical frame, the first 4 bits, say 1011, ofChapter 3. Spectjl cation of the MDLP 21Table 3. Protocol Field SizesField Size (in bits)Flag 24Header Frame Type 4Addresses 14Sequence Number 4Acknowledgment Number 4P1P2 Indicator Bit 1Length of Data 10Miscellaneous 9 41Header CRC 16Data (P1 or P2) 1024Data CRC 32TOTAL: ll37the header may represent the frame type. The FC module decodes these raw bit patterns intotheir logical representation, such as decoding 1011 into denoting an information frame. The PrLmodule is not concerned with the position or manner in which the logical frame is transformedinto a physical frame. It is the responsibility of the PC module to perform this operation. Allof the encoding, decoding, bit interleaving, CRC generation and checking and other bit leveloperations performed on the frame are contained in the PC module. The advantages to thismethod include cleaner code, simplified testing, and the ability to substitute alternative encodingroutines as well as to provide a level of abstraction to the PrL module. The module shown inFigure 3.5 interfaces to the network layer through interaction point Dl and to the physical layerthrough D2. It represents the data link layer for one station in the point-to-point communicationslink. For clarity purposes, the interactions are not listed and channels are represented by a singleChapter 3. Specification of the MDLP 22‘L1Protocol LogicFrame CODEC‘C2D2Figure 3.5 Hierarchy of the MDLP moduleline.An overview of the Estelle code structure for the entire MDLP is shown in Figure 3.6. Afterthe specification title and type are entered in the first line, all global constant or type definitionsare declared. Next, the channels and modules are declared with nesting occurring as moduleslower in the module hierarchy are introduced. The two channels connecting the data link tothe surrounding network and physical layers, NetworkLink and PhysicalLink, respectively,are declared, along with modules representing both of these layers. Protocol Logic and FrameCodec are placed within the Data Link module, connected by the Convert channel. Now thatall channels and modules have been defined, they are initialized and joined with the rniT,CONNECT, and ATTACH commands, starting at the lowest level in the module hierarchy. Theinternal operation of the data link module, particularly of the PrL submodule, will be formallyChapter 3. Specification of the MDLP 23presented in Section State Diagram for Protocol LogicAlthough a state diagram cannot include all the information of an EFSM, it provides agraphical overview to supplement the formal specification. A state diagram of the PrL moduleis shown in Figure 3.7. It consists of four states: IDLE, SETUP_READY, ABM, and DISC_READY.These four states are connected by 23 transition paths which are labelled with their input conditionand output result. For example, if the current state is IDLE, an incoming CONNReq primitiveallows a change of state to SETUP_READY, and a SABM frame is outputted. Communicatingstations are initialized to the IDLE or disconnected state. SETUP_READY and DISC_READY arestates used in establishing and disconnecting the link. All data transfer is accomplished in the ABMstate. Due to the many transitions occurring in ABM, they have not been explicitly included in thisdiagram but are listed in the MDLP specification in Appendix A, and discussed in Section 3.7.5.Chapter 3. Specification of the MDLP 24SPECIFICATION MDLP SYSTEIYIPROCESS;CONSTTYPECHANNEL NetworkLink(Upper, Lower);CHANNEL PhysicalLink(Upper, Lower);MODULE Physical_Layer PROCESS;BODY Physical_Body FOR Physical_Layer;MODULE Network Layer PROCESS;BODY Network_Body FOR Network_Layer;MODULE Data_Link_Layer PROCESS;CHANNEL Convert(Upper, Lower);MODULE Protocol_Logic;BODY Protocol_Logic;MODULE FrarneCODEC;BODY Frame_CODEC;MODVARPrL: Protocol_Logic;FC: Frame CODEC;INITIALIZEBEGININIT PrL WITH Protocol_Logic_Body;INIT FC WITH Frame_CODEC_Body;CONNECT PrL.L2 TO FC.Cl;ATTACH Dl TO PrL.Ll;ATTACH D2 TO FC.C2;END;MODVARPL: Physical_Layer;DL: Data_Link_Layer;NL: Network_Layer;INITIALIZEBEGININIT PL WITH Physical_Body;INIT DL WITH Data_Link_Body;INIT NL WITH Network_Body;CONNECT NL,N TO DL,Dl;CONNECT DL.D2 TO PL.P;END;END.Figure 3.6 MDLP Estelle OverviewChapter 3. Specification of the MDLP 25SABM/CONNIndFigure 3.7 State Diagram of Protocol Logic (PrL) Module3.7 Protocol Logic — Estelle SpecificationThe Protocol Logic module forms the heart of the MDLP, incorporating the Type-TI HybridARQ logic. An outline of this module is shown in Figure 3.8. The interaction point definitionsare made first, Li connecting through to the network layer, and L2 connecting to the FC modulebelow. The main body contains a list of traversable states, type definitions, internal variables,procedure and function declarations, transitions, and an initialization statement. The PrL modulesubroutines and transition statements, grouped by task, are introduced in 3.6.1 through 3.6.6.CONNReq/SABM UA/DISCConfSABMIUADISCRespIUADISCIUADISCReq/DISCDISC/DISCInd+ all data transfer transitions (13)Chapter 3. Specification of the MDLP 26MODULE Protocol_Logic;IP Li: NetworkLink(Lower): individual queue;L2: Convert (Upper) : individual queue;END;BODY Logic_Body for Protocol_Logic;STATETYPEVARPROCEDUREFUNCTIONINITIALIZETRANSEND;Figure 3.8 Protocol Logic Module — Estelle overview3.7.1 Support SubroutinesThe Protocol Logic Module defines a number of procedures and functions, each of whichcan be called from any of the 23 transition statements. For example, Procedure Inc can becalled by the transition incrementing the sending window variables as well as the transitionincrementing the receiving window variables, Procedure PrepareFrame is called from a largenumber of transitions to assemble a frame. These subroutines are declared after the local variabledeclarations and make the transition statements much cleaner by reducing the many repetitivetasks required. This also eases enhancements to the specification as these subroutines can easilybe modified. A description of each subroutine is briefly discussed below.Procedure Clear resets all transmit and receive window variables and turns off all flowcontrol measures. The data buffers are cleared and both the retransmission timers and piggyback timer are turned off. All other counters are initialized to 0.Chapter 3. Specification of the MDLP 27PROCEDURE Clear;VAR j: Integer;BEGINNextFrarneToSend 0;AckExpected := 0;FrameExpected 0;TooFar NrBufs;nhuffered 0; NoNak true; DataLinkBusy false;NetworkBusy := false; PlggyBackAckT±mer true;PiggyBackCount := 0; ValidFrameCount 0;TotalFrameCount 0; th = 0.0;FOR j := 0 TO MaxBuf DOBEGINReceivedOK[j] false;END;FOR j 0 to MaxSeq DOBEGINOutMap.timer{j] := false;OutMap.count{j] 0;OutMap.IndBit[j] P1;END;END;Figure 3.9 Procedure Clear — EstellePROCEDURE inc(var k: SequenceNr);BEGINIF (k < MaxSeq) THEN k k + 1 ELSE k 0;END;FUNCTION between(a,b,c: SequenceNr) : boolean;BEGINIF ((a<=b) AND (b<c)) OR ((c<a) AND (a<=b)) OR ((b<c) AND (c<a))THEN between := trueELSE between false;END;Figure 3.10 Procedure inc and Function between — EstelleThe procedure in Figure 3.10 increments a sequence number modulo MaxSeq, the maximumsequence number. Function between is passed three sequence numbers a, b, and c, and checksChapter 3. Specification of the MDLP 28PROCEDURE PrepareFrame(fk: Frame_kind; FrameNr: SequenceNr);BEGINs.F_type := fk;s.address := RemoteAddress;CASE fk OFI: BEGINs.seq := FrameNr;s.ack := (FrameExpeced + MaxSeq) MOD Modulus; := OutBuf[FrameNr MOD NrBufs];s.IndBit := OutMap.IndBifr[FrameNr];OutMapJimer[FrameNr] := true;END;RR: BEGINs.ack := (FrameExpeced + MaxSeq) MOD Modulus;END;SREJ: BEGINs,ack := (FrameExpecled + MaxSeq) MOD Modulus;NoNak := false;END;SABM: BEGIN END;UA: BEGINs.address := BaseAddress;END;DISC: BEGIN END;END;END;Figure 3.11 Procedure PrepareFrame — Estelleto see if a <= b < c circularly. It is used for checking the validity of arriving sequencenumbers at the receiver.Procedure PrepareFrame, in Figure 3.11, accepts a frame type and transmit sequencenumber, FrameNr, as input. Since only I frames are sequenced, FrameNr is ignored for otherframe types. Every frame includes the frame type and destination (remote) address. If aninformation frame is requested, the data packet is obtained from the transmitter buffer, theacknowledgment number is taken, the indicator bit is set, and the timer associated with thesequence number is activated. The RR and SREJ frames also contain the acknowledgmentnumber. If a selective reject frame is requested, the variable NoNak is set to false to permit onlyChapter 3. Specification of the MDLP 29one outstanding SREJ frame. In this protocol, only one request for reiiansmission is allowed atany one time. This sequence number must be acknowledged before any other SREJ frames aresent. The UA frame, used to confirm link connections and disconnection, also contains returnsthe originator (base) address and the remaining frame types SABM and DISC do not contain anyother fields.PROCEDURE UpdateSenderWindow;BEGINWHILE between(AckExpeced, r,ack, NextFrameToSend) DOBEGINnbuffered nbuffered - 1;OuMap.timer[AckExpecIed] false;OutMap.count[AckExpected] 0;OutMap.IndBi[AckExpeced] P1;inc (AckExpected);END;END;Figure 3.12 Procedure UpdateSenderWindow — EstelleProcedure UpdateS enderWindow, in Figure 3.12, is called after receiving an I, RR, or SREJframe. The sending window is updated according to the acknowledgment number containedwithin these frames. The timer is disabled, time count reset to zero, and the indicator bit isreturned to P1 for acknowledged frames.Chapter 3. Specification of the MDLP 30PROCEDURE TimeCount;VAR x: SequenceNr;BEGINFOR x 0 to MaxSeq DOBEGINIF OutMap.timer[x] true THENOutMap.count[x] := OutMap.count[x] + 1;END;END;PROCEDURE TimeCount2;BEGINIF PiggyBackAckTimer = true THEN PiggyBackAckCount := PiggyBackAckCount + 1;END;Figure 3.13 Procedures TimeCount and TimeCount2 — EstelleThe two procedures in Figure 3.13 advance the timer Count Ofl outstanding frames and thepiggy-back time counter. If after a predetermined length of time without an I, RR, or SREJframe being sent, PiggyBackAckTimer times out and sends a RR frame to update the currentwindow status.Chapter 3. Specification of the MDLP 31FUNCTION Combinel: boolean;BEGINP4 := Random;IF (P4 <= P1P1) THENBEGINInBuf[r.seq MOD NrBufs] .rawinfo := 0;Combinel := Lrue;ENDELSE combinel := false;END;FUNCTION Combine2: boolean;BEGINP5 := Random;IF (P5 <= P1P2) THENBEGINInBuf[r.seq MOD NrBufs] .rawdata := 0;combine2 := lrue;ENDELSE Combine2 := false;END;Figure 3.14 Functions Combinel and Combine2 EstelleFunctions Combinel and Combine2 are called to decode two received copies of a packet,either two copies of P1 or one each of P1 and P2, respectively. In a full implementation, these twofunctions would explicity perform the combining and decoding operations. As shown, the twofunctions are currently configured for throughput simulations using a statistical channel model.In a full implementation, these operations would require bit level computations. The performanceof these two functions is determined by a statistical model discussed further in Chapter 5. Ifdecoding is successful, the function returns a true value and places the decoded data in a buffer.3.7.2 Link ConnectionThe MDLP is a connection oriented protocol for point-to-point data communications betweena base station and a remote mobile station. A data link layer connection is established using aChapter 3. Specification of the MDLP 322—way handshake mechanism in which the addresses of both stations are exchanged. Althoughaddressing seems superfluous in a point-to-point link, it leaves room for expansion to other typesof connection. Initially, both communicating stations are waiting in the IDLE state, The linkconnection is initiated when the network layer of either station asserts the CONNReq primitivemoving the base station to the SETup_READY state. A SABM frame is transmitted by the data linklayer over the channel, resulting in a CONNInd primitive being asserted to the receiving networklayer. It responds with CONNResp, moving the remote station into the ABM state, and an UAframe is returned over the channel. Finally, the link connection is confirmed with a CONNConfprimitive, moving the base station into the AEM state. These steps can be followed in the statediagram shown in Figure 3.7. The addresses are passed as parameters in the CONNxxxx primitivesas listed in Table 1. This handshaking procedure is shown in Figure 3,1. The correspondingEstelle code is shown in Figure 3.15. For convenience, the initiating station is assigned addressO and the responding station address 1. Note that either station may initiate the connection inthis balanced configuration.Chapter 3. Specification of the MDLP 33TRANS (* 1 *)FROM IDLEWHEN L1.CONNReqTO SETUP_READYBEGINBaseAddress : 0; RemoteAddress 1;PrepareFrame(SABM, 0);OUTPUT L2 ENCODEReq (s);END;TRANS (* 2 *)FROM IDLEWHEN L2.DECODEIndPROVIDED (Inp.F_type = SABM)TO SAMEBEGINOUTPUT L1.CONNInd;END;TRANS (* 3 *)FROM IDLEWHEN L1.CONNRespTO ABMBEGINBaseAddress 1; RemofreAddress := 0;PrepareFrarne(UA, 0);OUTPUT L2 .ENCODEReq(s);END;TRANS (* 4 *)FROM SETUP_READYWHEN L2.DECODEIndPROVIDED (Inp.F_ype = UA)TO ABMBEGINOUTPUT Li CONNConf;END;TRANS (* 5 *)FROM SETUP_READYWHEN L2.DECODEIndPROVIDED (Inp,F_type = SABM)TO SAMEBEGINPrepareFrame(UA, 0);OUTPUT L2 .ENCOOEReq(s);END;Figure 3.15 Link Establishment EstelleChapter 3. Specification of the MDLP 343.7.3 Link DisconnectionAs in the link connection phase, the data connection is concluded using a 2—way handshakingroutine, When data transfer is complete, the network layer asserts a DI SCReq primitive to thedata link layer, exiting the ABM state and entering DISC_READY. In turn, the data link sends aDISC frame over the channel, where DISCInd is returned to the peer network layer. In reply,it responds with DI SCResp, moving into the IDLE state, and an UA frame is returned over thechannel. To complete the disconnection, a DISCConf primitive is asserted, moving the basestation into the IDLE state. These changes of state can be traced in the state diagram of Figure3.7. This exchange is shown in a flow diagram in Figure 3.2 and formally in Figure 3.16.Data packets that are unacknowledged when the DISC frame is transmitted are discarded. Thenetwork layer is responsible for recovery of these lost frames [18]. Again, either station mayinitiate disconnection in this balanced configuration.Chapter 3. Specification of the MDLP 35TRANS (* 6 *)PROM ABMWHEN Ll.DISCReqTO DISC_READYBED INPreparePrame(DISC, 0);OUTPUT L2 .ENCODEReq(s);END;TRANS (* 7 *)PROM AHMWREN L2.DECODEInOPROVIDED (Inp.P_type = DISC)TO SAMEBEGINOUTPUT Li ,DISCInd;END;TRANS ( 8 *)PROM ABMWHEN Ll.DISCRespTO IDLEBEGINPreparePrame)UA, 0);OUTPUT L2 .ENCODEReq)s);END;TRANS )* 9 *)PROM DISC_READYWHEN L2.DECODEInOPROVIDED )Inp.P_type = UA)TO IDLEBEGINOUTPUT Li .DISCConI;END;TRANS (* 10 *)PROM DISC_READYWHEN L2.DECODEIndPROVIDED )Inp.P_ftype = DISC)TO SANEBEGINPreparePrame(UA, 0);OUTPUT L2 .ENCODEReq)s);END;Figure 3.16 Link Disconnection — EstelleChapter 3. Specification of the MDLP 363.7.4 Flow ControlOne of the functions of the data link layer is to regulate the flow of data being received bythe network layer. In addition, the link layer must also have a way to direct the amount of databeing received from the network layer. When the data link transmit buffers have been filledwith data from the network layer, it asserts the FLOWSTOPInd primitive. After a buffer has beencleared by an acknowledgment, the condition is cleared with a FLOWSTARTInd primitive. Theseevents are shown in Figure 3.3. A similar operation occurs when the network layer data buffershave been filled. Note that in this selective repeat ARQ scheme, the windowing mechanismprovides inherent flow control between the communicating data link layers. Since both stationshave identical window sizes, one station cannot transmit more than the other station is willingto accept. A Receiver Not Ready (RNR) frame would increase complexity and is not supported.The Estelle flow control statements are shown in Figure 3.17.Chapter 3. Spectjl cation of the MDLP 37TRANS (* 12 *)FROM ABMPROVIDED (nbuffered >= NrBufs) AND (OaaLinkBusy = FALSE)PRIORITY criticalTO SAMEBEGINDataLinkBusy := true;OUTPUT Li .FLOWSTOPInd;END;TRANS (* 13 *)FROM ABMPROVIDED (nbuffered < NrBufs) AND (DafraLinkBusy = TRUE)PRIORITY criticalTO SAMEBEGINDaaLinkBusy := false;OUTPUT Li .FLOWSTARTInO;END;TRANS (* 14 *)FROM ABMWHEN Li . FLOWSTOPReqPRIORITY criticalTO SAMEBEGINNeworkBusy true;END;TRANS (* 15 *)FROM ABMWHEN Li . FLOWSTARTReqPRIORITY criticalTO SAMEBEGINNeworkBusy false;END;Figure 3.17 Flow Control — Estelle3.7.5 Data TransferThe main purpose of the MDLP is to provide reliable full-duplex data transfers over a mobileradio channel. To combat the fading characteristics of such a physical medium, each mobilestation will incorporate the Type-IT Hybrid ARQ scheme presented. Using these algorithmsstations can request the retransmission of lost or damaged frames while still maintainingacceptable performance.Chapter 3. Specification of the MDLP 38Data transfer occurs in the ABM state of the Estelle specification and consists of 6 transitionstatements. Data packets are received from the network layer through interaction point Li viaDATAReq primitives. These packets are buffered, sequenced, assembled into information (I)frames, and then sent to the FC module for encoding. This transition is given a low priority,and is shown in Figure 3.18.TRANS (* 11 *)FROM ABMWHEN Ll.DATAReqPROVIDED (DataLinkBusy = false)PRIORITY lowTO SAMEBEGINnbuffered := nbuffered + 1;OutBuf[NexframeToSend MOD NrBufs] Sentpacket;PrepareFrame(I, NextFrameToSend)OUTPUT L2 . EN000EReq (s);TimeCount;PiggyBackAckTirner false;inc (NextFrameToSend);END;Figure 3.18 Receiving data packets from the Network Layer — EstelleAfter I frames arrive at the receiver and are decoded, each field is examined by thetransition in Figure 3.19. Any frames which contain an invalid header, wrong address, or aduplicate sequence number are rejected. If the frame does not contain the expected sequencenumber a SREJ frame is returned. As previously mentioned, the protocol allows retransmissionthrough SREJ frames for only one sequence number, FrameExpected. SREJ frames to requestretransmission of multiple sequence numbers is not permitted. This means that frames are alwaysacknowledged in their sequenced order. If the sequence number lies within the receiver windowlimits, the data field may be used for decoding. Otherwise, the frame is discarded. Next, theValidData flag, which is set by the FC module, is checked, If true, the data field is decodedChapter 3. Specification of the MDLP 39and placed in the receiver buffer, ready to be sent up to the network layer. If the flag is false,further retransmissions will be required to provide additional redundancy. The actions to betaken next are grouped into three categories: Cases 1, 2 and 3.Chapter 3. Specification of the MDLP 40TRANS (* 16 *)PROM ABMWHEN L2.DECOOEIndPROVIDED (Vat idFlag = true) AND(ValidHeader = true) AND (Inp.eddress = BaseAddress) AND(Inp.F_type = I) AND (ReceivedOK[Inp.seq MOD NrBufs] = false)PRIORITY highTO SAMEBEGINr Inp;UpdateSenderWlndow;TetalFrarneCeunt TetalPrameccunt + 1;TimeCeunt2;IF (r.seq <> FrameExpected) AND (NeNak = true) THENBEGINPrepareFreme(SREJ, 0);OUTPUT L2 .ENCODEReq;PlggyBackCeunt 0;END;IF between(FrameExpected, r.seq, ConFer) THEN BEGINIF (ValidDeta = true) THENBEGINReceivedOk(r.seq MOD NrBufs) true;InBuf[r.seq MOD NrBufs) .rawinfe = Dataoecede(r,infe);IF (ReceivedOK[FrameExpected MOD NrBufs]) AND(NetwerkBusY = false) THENBEGINReceivedOK(FrameExpected MOD NrBufs] := false;Inc (FrameExpected);Inc (TeeFar);ValIdFrameCeunt ValldFrameCeunt + 1;PrepareFrame (ER, NextFrameTeSend)OUTPUT L2 .ENCOUEReq(s);InBuf[FrameExpected MOD NrBufs] .IndBIt := None;NnNak true;PiggyBackAckTlrner true;PiggyBackCeunt 0;END;ENDELSE (* ValidData = false *)BEGINIF (r.seq = FrameExpected) THEN NoNak true;(* Case 1: Ne previous copies *)(* Case 2: P1 and P1 or P2 and P2 *)(* Case 3: P1 and P2 or P2 and P1 *)END;END;END;Figure 3.19 I frame received — EstelleChapter 3. Specification of the MDLP 41When no copies of a particular sequence number have been previously received, the datafield is stored in the receiver buffer, along with its encoder sequence indicator (P1 or P2). ASREJ frame is returned to request a retransmission. The corresponding Estelle statements aresummarized in Figure 3.20.IF InBuf[r.seq MOD NrBufs] .IndBit = None THENBEGINInBuf[r.seq MOD NrBufs] .IndBit r.IndBit;InBuf[r.seq MOD NrBufs] .±nfo;IF (NoNak = true) THENBEGINPrepareFrame(SREJ, 0);OUTPUT L2 . ENCODEReq (s);END;ENDFigure 3.20 Case 1: No previous copies — EstelleIf an intermediate frame is lost, two copies of either P1 or P2 may be received. The functionCornb±nel attempts to decode the data using these two copies. If successful, the decoded datais buffered, ready for transfer to the network layer, otherwise the oldest copy is discarded anda SREJ frame is returned. The SREJ frame does not specify which encoder sequence (P1 orP2) is requested, as the transmitter keeps track of this information. Figure 3.21 presents thecorresponding Estelle statements.Chapter 3. Specification of the MDLP 42ELSEIF InBuf[r.seq MOD NrBufs] .IndBit = r.IndBit THENBEGINIF (Combinel = true) THEN ReceivedOK[r.seq MOD NrBus] trueELSEBEGINInBuf[r.seq MOD NrBufs] .info;InBuf[r.seq MOD NrBufs] .IndBit r.IndBit;IF (NoNak = true) THENBEGINPrepareFrame(SREJ, 0);OUTPUT L2 .ENCODEReq(s);END;END;ENDFigure 3.21 Case 2: P1 and P1 (or P2 and P2) — EstelleWhen frames of different encoder outputs, either P1 and P2 or P2 and P1, are received theycan be combined and sent through the Viterbi decoder in procedure Cornbine2. If decoding isnot successful, the oldest copy is discarded and a REJ frame is returned.ELSEIF InBuf[r.seq MOD NrBufs] .IridBit <> r.IndBIt THENBEGINIF (Combine2 true) THEN ReceivedOK[r,seq MOD NrBufs] trueELSEBEGINInHuf[r.seq MOD NrBufs] •±nfo;InBuf[r.seq MOD NrBufs] .IndBit r.IndBit;IF (NoNak = true) THENBEGINPrepareFrame(SREJ, 0);OUTPUT L2 .ENCODEReq(s);END;END;END;Figure 3.22 Case 3: P1 and P2 (or P2 and P1) — EstelleAfter data frames have been decoded successfully they are placed in the receiver buffer.The transition shown in Figure 3.23 examines the receiver window and sends the data packets tothe network layer in the appropriate order. The variable FrameExpected indicates the trailingChapter 3. Specification of the MDLP 43edge of the receiver window and ReceivedOK an inbound boolean array which indicates whichsequence numbers have been successfully decoded without error. FrameExpected is used asan index into this array and is progressively incremented in the WHILE loop until an unreceivedsequence number is reached. In turn, packets, in their correct sequence, are returned to thenetwork layer in a DATAInd primitive.TRANS (* 17 *)FROM ABMPROVIDED (ReceIvedOK[FrameExpected MOD NrBufsl = true) AND(NetworkBusy = false)PRIORITY mediumTO SAMEBEGINWHILE (ReceivedOK[FrameExpected MOD NrBufs = true) DOBEGINOUTPUT L1.DATAInd(InBuf[FrarneExpected MOD NrBufs] .rawinfo);ReceivedOK[FrameExpected MOD NrBufs] false;InBuf[FrameExpected MOD NrBufs] ,IndBit None;inc (FrameExpected);inc (TooFar)ValidFrameCount := ValidFrameCount + 1;END;NoNak true;PiggyBackAckTirner true;PiggyBackCount 0;END;Figure 3.23 Send ordered data to the Network layer — EstelleTransition 18, shown in Figure 3.24, accepts valid SREJ frames. The acknowledgmentnumber contained in the frame must fall between the transmitter window boundaries. If thenumber is valid, a new I frame is assembled with the alternate encoder sequence, the timer isreset, and the frame is retransmitted.Chapter 3. Specification of the MDLP 44Figure 3.24 SREJ frame received — EstelleA RR frame is used to acknowledge frames explicitly. The transmitter window is updatedwith a call to the UpdateSenderWindow procedure.TRANS (* 18 *)FROM ABMWHEN L2.DECODEIndPROVIDED (ValidFlag = true) AND(ValidHeader = true) AND(Inp.address = BaseAddress) AND(Inp.F_type = SREJ) ANDbefrween(AckExpecled, (Inp.ack+1) MOD Modulus, NextFrameToSend)PRIORITY highTO SAMEBEGINr Irip;Upda LeSenderWi ndow;OuLMap.counL[(r.ack + 1) MODIF OuLMap.IndBiL[(r.ack + 1)OutMap.IndBiL[ (r.ack +ELSE OuLMap.IndBiL[(r.ack +PrepareFrame(I, (r,ack + 1)OUTPUT L2 .EN000EReq(s);TimeCount;PiggyBackAckTimer := false;Modulus] 0;MOD Modulus] = P1 THEN1) MOD Modulus] P21) MOD Modulus] P1;MOD Modulus);END;TRANS (* 19 *)FROM ABMWHEN L2,DECODEIndPROVIDED (ValidFlag = Lrue) AND(ValidHeader = Lrue) AND(Inp.address = BaseAddress) AND(Inp.F_Lype = RR)PRIORITY highTO SAMEBEGINr Inp;UpdateSenderWindow;END;Figure 3.25 RR frame received — EstelleChapter 3. Specification of the MDLP 45Any frames that do not satisfy the conditions of the previous 5 transition statements areaccepted by transition 20 (see Figure 3.26). This would be caused by missed frames, corruptedheaders, wrong address, extra retransmissions, or SREJ frame with an invalid acknowledgmentfield. In effect, this transition discards all invalid frames.TRANS (* 20 *)FROM ABMWHEN L2,DECODEIndPROVIDED (ValidFlag = false) OR(ValidHeader = false) OR(ReceivedOK[Inp.seq MOD NrBufs] = true) OR(Inp.address <> BaseAddress) DR(Inp.F_Iype = SREJ) AND NOT(beween(AckExpecIed, (Inp.acki-l) MOO Modulus, NexLFrameToSend)))TO SAMEBEGINToa1FrameCount ToalFrameCount + 1;TirneCounfr; TimeCounfr2;END;Figure 3.26 Invalid frame received — EstelleAlthough these six transitions have been listed formally, a flow diagram example willillustrate operations much more clearly. In Figure 3.27, retransmissions using SREJ framesare shown. As mentioned previously, data packets are accepted from the network layer inDATAReq and sent to the network layer in DATAInd primitives. Frames 0 and 1, containingencoder sequences P1, arrive unmolested at the receiver and are immediately sent to the networklayer. Frame 2 is damaged in transit and a request for retransmission is made using a SREJframe. Note that the SREJ frame acknowledges frames up to the last correctly received sequencenumber, 1 in this case. Meanwhile, frame 3 has been transmitted and accepted by the receiverwindow, Upon reception of the SREJ frame, the transmitter resends frame 2, with encodersequence P2. Unfortunately, the second copy of frame 2 is also damaged and a decoding attemptChapter 3. Specification of the MDLP 46with a combination of the previous copy containing P1 is also unsuccessful. Another SREJ frameis returned to request another transmission. Frames 4 and 5 have been transmitted before theSREJ is received by the transmitter. The transmitter assembles another frame 2 with encodersequence P1 and sends it over the channel. This time frame 2 remains undamaged and is decodedsuccessfully by the receiver. Data packets 2, 3, 4, and 5 are sent, in order, to the network layerin DATAInd primitives.Base Station Remote StationNetwork Data Link Data Link NetworkDATAReqI(O,P1)DATAReq ---_....I(1,P1) —--—. DATAIndDATAReq ----.-._1(2 P1) — — — — DATAIndDATAReq -__...SREJ(1)DATAReq-DATAReq - - J(4,P15 - - -SREJ(1)IEl15------:::::-- DATAIndDATAIndDATAIndATAIndFigure 3.27 Retransmission using SREJ Flow diagram, I(n, P) = Information framewith seq# n and Indicator bit P; SREJ(m) = Selective Reject frame with ack# mChapter 3. Specification of the MDLP 473.7.6 TimersTwo different timers are used in the MDLP. T1 handles the retransmissions of lost frames ortheir corresponding acknowledgment. Each outgoing information frame has an associated timerT1. If the timer expires, that particular frame is retransmitted. Note that the alternating P1 andP2 sequences are maintained. Only one transition statement, shown in Figure 3.28, is neededto maintain all of the T1 timers. Using the Estelle DELAY command would be the most elegantway of implementing the timers, but unfortunately it was not working correctly in the EDTcompiler. A software timer with a simple counter proved to be just as effective. This counteris incremented by the T±meCounft procedure which is called in each transition which containseither an input or an output of a frame and in an idle timer transition seen in Figure 3.29. TimerT1 was set “loose” since retransmissions were accomplished more effectively with SREJ framesrather than timer expiries due to the robust header. In addition, a mobile link often has highlyvariable round-trip delays, making retransmissions via SREJ much more efficient. Using thismethod, only a relative time scale is achieved (ie. an integer multiple of the time it takes totransmit or receive one frame). An absolute time scale, such as the ability to set timer T1 to 5msec, for example, is implementation dependent.Chapter 3. Specijl cation of the MDLP 48TRANS (* 21 *)FROM ABMANY 1:0. .MaxSeq DOPROVIDED (OutMap.timer[1] = true) AND (OutMap.count[1] >= 4NrBufs)TO SAMEBEGINOutMap.timer[1] := false;OutMap.count[l] := 0;IF OutMap.IndBit[l] = P1 THEN OutMap.IndBit:[l) := P2ELSE OutMap.IndBit[1] := P1;PrepareFrame(I, 1);OUTPUT L2 .ENCODEReq(s);TimeCount;PiggyBackAckTimer := false;END;Figure 3.28 Timer T1 — EstelleTRANS (* 22 *)FROM ABMANY 1:0, .MaxSeq DOPROVIDED (OutMap.timer[l] = true)TO SAMEBEGINTimeCount;END;Figure 3.29 Idle timer tick — EstelleA second timer, T2, is used to return acknowledgment information when the return channelhas been quiet for a set period of time. T2 is implemented in a similar fashion as T1 and isseen in Figure 3.30. The importance of these two timers cannot be stressed enough, for withoutthem, the protocol would readily find itself in a deadlocked situation. These timers are used asa recovery mechanism in the event that an excessive number of frames have been lost. In ahardware implementation, timers and the corresponding Estelle DELAY clause would be drivenby an interrupt signal derived from a hardware clock.Chapter 3. Specification of the MDLP 49TRANS (* 23 *)FROM ABMPROVIDED (PiggyBackAckTimer = true) AND (PiggyBackAckcount. > 4*jjf)TO SAMEPRIORITY veryhighBEGINPrepareFrame(RR, 0);OUTPUT L2 . EN000EReq (s);PigqyBackCounfr 0;END;Figure 3.30 Timer T2 Estelle3.8 SummaryThis chapter has presented the formal specification of the MDLP in Estelle. The protocolframe structure, frame types, and supported service primitives have also been presented. Thetransition statements of the Protocol Logic module, which forms the core of the MDLP, formallydetailed the operations of the Type-IT Hybrid ARQ scheme discussed in Section 3.3.When two or more transition statements become fireable simultaneously, the PRIORITYclause enables the protocol designer to assign higher relative priorities to important transitions.In the MDLP, there are four priority classes: critical, high, medium, and low. Each classrepresents a positive integer value; 0 indicates the highest priority and values greater than 0indicate progressively lower priorities. Many of the transitions in the specification include thisPRIORITY clause. The transitions involved with flow control are assigned a crit ical prioritysince buffer limits are to be strictly enforced to avoid overruns. The transitions which accept i,SREJ, or RR frames are assigned a high priority and the transition that passes the ordered datato the network layer has a medium priority. A low priority is given to accepting data packetsfrom the network layer. All other transitions have no priority and, by default, are classified asthe lowest priority.Chapter 3. Specification of the MDLP 50Estelle and the MDLP specification are both quite flexible and enhancements to the protocolare straightforward. The MDLP currently only supports a point-to-point link. By extending thisprotocol specification, other types of connections can be supported, such as multiple networkusers (discussed in Section 6.2.3) and multicast or broadcast connections. The MDLP alsouses a very rudimentary link connection and disconnection mechanism since greater emphasiswas placed on the data transfer phase. The flag and header are very robust and, under normalcircumstances, would be adequate to provide link connection and disconnection services. Amore robust mechanism can be found in [31]. The MDLP also does not support splitting orconcatenating of data packets received from the network layer. Finally, the link RESET functionand explicit flow control using the Receiver Not Ready (RNR) frame is not supported.The formal specification of the MDLP was straightforward using the Estelle constructs, andeven complex communications protocols can be specified using this FDT. Such a standardizeddescription language leads to the possibility of common module or subroutine libraries which canbe used as ‘building-blocks’ in more involved protocols. For example, encoding, concatenating,or standard I/O routines could be made readily available. The modular structure of Estelle alsoallows modifications or enhancements to be made easily.The complete Estelle specification of the MDLP is included in Appendix A.51Chapter 4 Testing the MDLP4.1 IntroductionAlthough no software tools are currently available to perform automated validation ofEstelle specifications, there are some tools that are available to assist in debugging, testing,and simulation. Validation of a protocol consists of two related steps:• validation of the MDLP Estelle specification and,• validation of the MDLP, that is, verification that the MDLP has a correct behaviour.A validated Estelle specification means that it is:1. statically correct (no syntax and static semantic errors),2. free of some run-time errors (non-initialized variables, deadlocks) and,3. conformant to the informal specification — English prose.The first two items are verified by the EDT using the complier and executing the protocol withrun-time error detection. Since Estelle is a strongly typed language, all static errors can bedetected during compilation. Verification of the third item is performed by a combination ofinspection and simulation.Complete validation, in principle, considers all of the possible situations the specificationmay encounter during actual operation. This would require the generation and examination of allpossible test cases (in itself not trivial) and is not practical due to time limitations. The manualmethods presented in this chapter do not form a complete validation, but do confirm the correctoperation of many of the major functions of the protocol. With a combination of manual testingChapter 4. Testing the MDLP 52and corroborating results from the performance simulations in Chapter 5, the logical correctnessof the MDLP can be strongly supported.4.2 Simulation Tools and Testing MethodsEdb, one of the tools in EDT, is a symbolic and interactive simulator/debugger for Estelle[32]. It is used as a tool to assist the protocol developer discover and process errors that occurduring the execution of an Estelle specification. Edb takes as input the Intermediate Form(discussed in Section 5.1) and several C files generated by the Estelle compiler (Ec). Thesefiles are linked with an Estelle Simulation Kernel (also called a Simulation Motor) to provide ameans of controlling, observing, and tracing the execution of the specification using user-definedsimulation commands. Edb has three simulation modes:• Step-by-step simulation, in which the user selects a transition to be executed froma set of fireable transitions. The user can interactively examine and modify aspectsof the specification including states, variables, FIFO queue contents, and more.• Random simulation, in which the simulation executes automatically for a selectablenumber of transitions or for a predefined period of time. A transition is randomlyselected from the set of allowable transitions at each step in the simulation.• Extensive simulation, in which a prewritten simulation scenario is automaticallyexecuted.The command language of Edb provides two powerful features: macros and observers, TheEdb macro allows the grouping of several simulation commands under a given name. Thesesimulation commands and macros can be used to construct elaborate observers which describeChapter 4. Testing the MDLP 53situations the user wants to analyze and perform an associated action. For example, an observermay be programmed to display the sequence numbers of all arriving packets at a station or toend the simulation after a predetermined number of data frames have been sent. The MDLP willbe tested using all these simulation modes assisted by a number of macros and observers.4.3 Testing OperationsEdb assigns a reference number to each module during compilation. In this case, the twocommunicating stations are assigned numbers 2 and 3 and the root module (encompassing theentire simulation specification) is labelled number 1. A fourth module, which exchanges the dataframes being passed between stations, connects the two stations. These module connections canbe seen in Figure 5.2. While in the Edb simulation environment, access is allowed to internalEdb objects (most begin with a $ symbol) through predefined function calls, as well as objectsrelated to the Estelle specification, such as variables and queue contents. These Edb objectsallow the user to monitor, modify, and record virtually any aspect of an executing protocol, anda complete list of these functions can be found in [32].During the initial stages of development it was useful to observe the windowing action ofthe transmitting and receiving buffers. The observer shown in Figure 4.1 records the last firedmodule instance, the last fired transition number, and all eight window variables (4 from eachstation) into a file. After each transition execution, this information is stored in an output filecalled outi. The information contained in this file was valuable for sequence number and flowcontrol debugging, since many protocol actions are reflected in one of the window variables.For example, Next FrameToSend is incremented after each transmission of an I-frame, andAckExpected is updated upon the reception of an I, RR or SREJ frame.Chapter 4. Testing the MDLP 54% simulation outputs: transition information and window variablesset observer { file-display outl $last_instance;\file—display outl $lasttransitionid;\IF ($last_instance = 2) THEN file-display outl 2 -> AckExpected;\file-display outl 2 -> NextFrameToSend;\file-display outl 2 -> FrameExpected;\file-display outl 2 -> TooFar FI;\IF ($last_instance = 3) THEN file-display outi 3 -> AckExpected;\file-display outi 3 -> NextFrameToSend;\file-display outi 3 -> FrarneExpected;\file-display outl 3 -> TooFar FI;\Figure 4.1 Window Variable ObserverAnother useful observer is shown in Figure 4.2, which records a list of fireable transitions,in output file out 2, at each execution step. It was particularly helpful in debugging transitionconditional clauses and was a motivating factor in assigning PRIORITY clauses to the MDLPtransitions. For example, it was necessary to assign the network flow control transitions acritical priority. When the situation that network buffers is full and transition #16 (high)or #17 (medium) is ready to send data up to the network layer, the flow control mechanismsmust be executed first.% trace transitions which may execute in the next stepset_observer { file-display out2 $last_instance;\file—display out2 $last_transition_id;\file-display out2 $executable_transitions;\Figure 4.2 Fireable Transition ObserverThe step-by-step simulation method proved most useful when testing the ARQ mechanism.By using the Edb command that allows the deletion of queue contents, the loss of I-framesin the channel could be simulated by removing entries from interaction points Ki and K2 inChapter 4. Testing the MDLP 55Figure 5.2. In this way, the operation of the retransmission algorithm and the correct orderingof packets can be observed. It was also straightforward to test both the network and data linkflow control mechanisms.To provide a more comprehensive exercise, a macro was programmed to execute theprotocol for 250 (randomly chosen) transitions, stop, reinitialize, and restart, providing a randomsimulation scenario. This macro is seen in Figure 4.3. If a run-time error is detected or adeadlocked situation is reached, the simulation is stopped. Using this test, a significant bugwas found and corrected. As mentioned previously, interactions arriving at an interaction pointare appended to a unbounded FIFO queue. If there is no transition statement to accept aninteraction, the interaction will never be released from the queue and will therefore block thequeue permanently. Edb was not able to detect this run-time error, and this problem was correctedby including transition #20, seen in Figure 3.26, which accepts extraneous frames.% executes the protocol 5 times for 250 randomly chosen transitions each pass.macro LOOP \{\*count =0; \do if *count=5\then display *count;\print Simulation ended successfully. ;\exit \else $firing_steps := 250;\continue; \if $total_firing_steps = 250 then display icount;\restart; \*count := *count + l;\else display *count;\display $current_firing_step; \if $is_deadlock then print Deadlock reached fi;\if $is_error then print “Run-Time Error fi;\exit \fi\fi\odFigure 4.3 Random Execution MacroChapter 4. Testing the MDLP 564.4 SummaryThese observers, as well as a number of other macros, were employed to examine theoperation of the MDLP. The protocol was steadily refined and tested using Edb assisted by somewell-placed qualifying comments inserted in the Estelle code. Qualifying comments, which aredelimited by { $C$. . . }, contain C commands that are passed directly into the resulting C sourcefiles, bypassing any Estelle translation. These qualifying comments were placed at various pointsin the Estelle code (see Appendix A) to provide a visual record of what operations the protocolwas performing during execution. The manual validation techniques described here, as well asthe results from the performance simulations in Chapter 5, provide significant confirmation thatthe protocol is operating correctly.While this thesis was being written, a new component to EDT was developed called theUniversal Test Drivers Generator (UTDG) which allows the automatic generation of simulationenvironments [33]. The UTDG facilitates the validation of a module or sections of thespecification. When simulating a protocol layer, it is usually complemented with modules thatrepresent the surrounding upper and lower layers. In the case of the MDLP, the UTDG wouldgenerate the network and physical layers. The test driver modules produced by UTDG stimulatethe protocol under test by sending arbitrary sequences of interactions, representing the serviceprimitives, spontaneously or in response to the received requests. The UTDG helps, in part,to verify the robustness of the proposed protocol. Unfortunately, the UTDG program was notavailable to further test the MDLP. There has also been work on developing standard test suitesfor OSI conformance testing [34].57Chapter 5 MDLP Simulation and Performance Evaluation5.1 IntroductionImplementation was performed using the Estelle-C (Ec) compiler of EDT [35], whichtranslates the Estelle specification into C language source code. The compiler consists of twotools:1. a translator, which, given an Estelle specification, produces a representation,independent of the target programming language, called the Intermediate Form(IF). The translator also performs a complete lexical, syntactical, and semanticalanalysis of the specification.2. a C code generator, which, given the Intermediate Form, returns C code of thespecification.The purpose of the Intermediate Form is to enable other application oriented tools, such asthe associated Edb Simulator package or an alternate code generator, to work from a commonspecification format. This option leads to a number of possibilities, including the potential for adirect Estelle to assembler code generator, which would simplify DSP hardware implementation.The resulting files of the C code generator contain a portable, operating system independent, Crepresentation of components of the source Estelle specification. These files are supplementedwith the Estelle Implementation Kernel (also called an Implementation Motor), which consistsof system-dependent and run-time support routines, to generate a complete executable program.The resulting protocol implementation is guaranteed to conform to the specification due to thedirect automatic translation into C code. The implementation is easy to produce, maintain andChapter 5. MDLP Simulation and Performance Evaluation 58enhance. It is also portable to other operating systems and platforms. Development of the MDLPwas performed on Sun workstations running the UNIX operating system. This new approach toprotocol implementation can lead to a reduction in development time because a large amount ofcode is translated automatically from the specification.Section 5.2 discusses how the logic of the ARQ scheme is abstracted from the low levelcoding routines. In Section 5.3, a statistical model of a Rayleigh faded mobile radio channelis presented. The throughput simulation module interconnection and channel simulator moduleare introduced in Section 5.4 and 5.5, respectively. The expected throughput, calculated fromthe channel statistics, as well as the results obtained directly from Estelle simulation, for botha generic selective repeat and the Type-IT Hybrid ARQ schemes, are presented in Section 5.6.Finally, Section 5.7 summarizes the contents of the chapter.5.2 AbstractionAs mentioned in Section 3.5, this Estelle specification of the MDLP does not detail the downto the bit level operations of the protocol. The frame structure is stored as a RECORD datatype, and includes a field for the flag, frame type, sequence number, acknowledgment number,P1/P2 indicator bit, address, header CRC, data field, and data CRC. For the size of each field,please refer to Section 3.4. Each field represents an abstracted view of the actual bits containedwithin a frame. For example, the sequence number, acknowledgment number and address arestored as integers, and the frame type and P1/P2 indicator bit are stored as ordinal types. Theflag and two CRC fields, although specified as an ARRAY of 0’s and l’s, are important onlyinsofar as confirming synchronization to the frame or checking the validity of the header or data.It is only the performance of the flag and checksums that is of importance in this particularChapter 5. MDLP Simulation and Performance Evaluation 59specification, and these issues are discussed in the next section. Oniy the information mostessential to operating the protocol is stored in this RECORD. To keep the specification flexibleand to ease further development, functions which require bit manipulation, such as DataDecodeand ViterbiDecode, are included and defined as EXTERNAL, meaning that their operation canbe included, when required, at a later date. The operation of the MDLP can be presented moreclearly at this level of abstraction.5.3 Using Channel StatisticsIn order to provide an environment to fully exercise the MDLP, a model of a Rayleigh fadedmobile radio channel is required. This model would need to provide information regarding theperformance of the selected flag on frame synchronization and of the encoding routines on theheader and data. Using results obtained from [20] and [30], an accurate statistical model of aRayleigh faded channel can be determined. The relevant statistics are:• Probability of frame synchronization success (Pframe),• Probability of header success (Fheader),• Probability of receiving data successfully (Pdata = P1 = F2), and• Probabilities of success after combining two received copies; either P1 and P1 orP1 and P2 (P11 = P22,P1 = P21).These statistics, which represent the ability of the flag and encoding algorithm to resist the errorsintroduced by the channel, are listed in Table 4 and plotted in Figure 5.1. Due to the importanceof synchronizing to the frame and successfully decoding the header, both the Pframe and headercurves maintain a high probability of success until low SNR values. Note that the header can beChapter 5. MDLP Simulation and Performance Evaluation 60Table 4. Channel StatisticsSNR(clB) Pframe Pheader Pdata = P1 P2 P11 = P22 P12 = P212 0.2186 0.0000 0.0000 0.0000 0.00004 0.4311 0.0000 0.0000 0.0000 0.00006 0.6785 0.1844 0.0000 0.0000 0.00008 0.8638 0.8937 0.0000 0.0000 0.14249 0.9197 0.9732 0.0000 0.0000 0.624210 0.9552 0.9936 0.0000 0.0000 0.894412 0.9876 0.9997 0.0000 0.0002 0.994014 0.9968 1.0000 0.0000 0.0259 0.999716 0.9991 1.0000 0.0000 0.2126 1.000018 0.9997 1.0000 0.0000 0.5262 1.000020 0.9999 1.0000 0.0001 0.7692 1.000022 1.0000 1.0000 0.0032 0.8992 1.000024 1.0000 1.0000 0.0262 0.9581 1.000026 1.0000 1.0000 0.1000 0.9830 1.000028 1.0000 1.0000 0.2335 0.9932 1.000030 1.0000 1.0000 0.3991 0.9973 1.000032 1.0000 1.0000 0.5599 0.9989 1.000034 1.0000 1.0000 0.6935 0.9996 1.000036 1.0000 1.0000 0.7937 0.9998 1.000038 1.0000 1.0000 0.8644 0.9999 1.000040 1.0000 1.0000 0.9121 1.0000 1.0000received without error down to 10dB. The success rate of one rate 1/2 encoded data packet, Pdata,is greater than 50% only when the signal—to—noise ratio stays above 33dB, and is reduced to zerounder 20dB. As expected, using multiple copies to assist in decoding significantly increases theprobability of success. Using two copies of P1 reduces the 50th percentile of success to 17dB,while using one copy each of P1 and P2 gives excellent performance even down to 10dB,Chapter 5. MDLP Simulation and Performance Evaluation 61ci)C-)C-)CFigure 5.1 Plot of Channel Statistics vs. SNR5.4 Simulation Module ConnectionUnder normal operation, the modules that have been discussed would be connected as shownin Figure 5.2, but, for simulation and throughput measurement purposes, the base and remotelogic modules are connected through a channel simulator module, as seen in Figure 5.3. Thechannel simulator replaces the physical layer and Frame Codec modules of both the base andremote sites. This module uses Fframe, Pheader, and Pdata to selectively tag these three fields asChapter 5. MDLP Simulation and Performance Evaluation 62valid or invalid. The remaining channel statistics, P and F12, are used by the Protocol Logicmodules when combining received copies.Base StationBase StationRemote StationRemote StationDataLinkLayerPhysicalLayerDataLinkLayerMobile RadioChannelFigure 5.2 Normal Module ConnectionPhysicalLayerL2Figure 5.3 Connection for Performance SimulationChapter 5. MDLP Simulation and Performance Evaluation 635.5 Channel Simulator ModuleThe Estelle code for the BlackBox (channel simulator) Module is shown in Figure 5.4. Itspurpose is to intercept all frames being passed in either direction and, using the data in Table4, determine the validity of the frame, header, and data fields. The function Random is usedto generate a real number between 0 and 1, which is then compared to Pframe, Pheader, or‘3data Note that the function Random calls the C system library function drand48 () whichgenerates non-negative double-precision floating-point numbers uniformly distributed over theinterval [0.0, 1.0). If the generated value is less than or equal to the supplied parameter, then thatfield is tagged as valid and this information is passed along with the entire frame to the receivingstation. The interaction points of BlackBox, Ki and K2, are denoted as common queues toensure that frames being sent in both directions are assembled in one common FIFO queue andare processed in that manner. BlackBox consists of one state, Nowhere, and two transitionstatements. Transition 1 handles frames going from the Base to Remote Station, entering at IPKl and exiting through K2, while Transition 2 accepts frames going in the opposite direction,entering at K2 and exiting through Kl. In addition, since BlackBox replaces the Frame CodecModule of both stations, the ENCODEReq primitives sent by the Protocol Logic modules areconverted to DECODEInd primitives. Four printf statements have been included in qualifyingcomments to provide visual feedback while running the simulation. The simulation was executed,for each SNR value listed in Table 4, until at least 1500 data packets had been transmitted andacknowledged.Chapter 5. MDLP Simulation and Peiformance Evaluation 64MODULE BlackBox PROCESS;IP Ki: StraightLink(Receiver) common queue;K2: StraightLink(Receiver) common queue;END; (* BlackBox *)BODY Black_Body FOR BlackBox;VARP1,P2,P3: real;ft: Frame_kind;BadData: integer;FUNCTION Random: real;BEGINRandom := 0;($C$ _rll5_random = drand48O/65536; )END;STATENowhere;INITIALIZE TO NowhereBEGINBadData := 0;END;TRANS ( 1FROM NowhereWHEN IK1.ENCODEReqTO NowhereBEGINft := Out.F_type; P1 := Random; P2 := Random; P3 := Random;IF (P3 > Pdata) THEN BadData := BadData + 1;OUTPUT K2.DECODEInd(Out, (Pl<=Pframe), (P2<=Pheader), (P3<=Pdata));IF (P1 <= Pframe) AND (P2<=Pheader) THEN {$C$ printf(---->); }ELSE {$C$ printf(’—//—>); }END;TRANS f 2 }FROM NowhereWHEN K2.ENCODEReqTO NowhereBEGINft := Out.F_type; P1 := Random; P2 := Random; P3 := Random;OUTPUT K1.DECODEInd(Out, (P1<=Pframe), (P2<=Pheader), (P3<=Pdata));IF (P1 <= Pframe) AND (P2<=Pheader) THEN ($C$ printf(<----);ELSE ($C$ printf(<-//-); )END;END; (* Black_Body *)Figure 5.4 Channel Simulator Module CodeChapter 5. MDLP Simulation and Performance Evaluation 655.6 Simulation ResultsThe maximum throughput using this ARQ scheme is given by:Data Size Data SizeTota Frame Szze Data Szze + Overheadwhere Overhead Flag + Header + DataCRC. yielding,900 bitsUMAX= 24 + 2 x 57 + 900 + 32 bits= 0.8411. (2)Note that the header length is multiplied by two since it has been encoded with a rate 1/2convolutional code.We let 7sent denote the number of data packets sent, and let Titotal denote the total numberof data frames transmitted over the channel. The value of Titotal would include valid data framesand their retransmissions as well as frames lost due to non-synchronization and corrupt headers.The throughput is calculated in the simulations using the following formula:lls e ni77= X?1MAX. (3)7toalFor comparison purposes, and also to demonstrate the flexibility of Estelle, the performance of a normal selective repeat protocol is now discussed. The throughput can becalculated directly from the channel statistics in Table 4. A frame is successful if boththe data and its corresponding acknowledgment are correctly received. This probability ofsuccess is FframePheaderPdataPframeFheader. Therefore, the probability of failure is L =1—The probability that exactly i attempts are requiredis (1 — L)L’. From this the expected number of transmissions per frame can be calculatedChapter 5. MDLP Simulation and Performance Evaluation 66as 1/(l — L). For a selective repeat protocol, with a window size large enough to continuouslystream data, the throughput is given by,= 7MAX X (1 — L). (4)As we can see, the regular selective repeat protocol will only be effective for SNR valuesgreater than approximately 20dB, since 1data is zero for smaller values. In this range, bothPframe and 13header are essentially equal to one, yielding L = 1 — data. Therefore, Equation4 reduces to = T1MAX X 1daa The results obtained through the Estelle simulation are anexcellent match to the expected results and can be seen in Figure 5.5.The throughput results for the Type-TI Hybrid scheme can also be calculated from Table 4.In general, the expected number of transmissions per frame isE(X) = (n x P(n)), (5)where P(n) is the probability of successful reception of data and return of a valid acknowledgment after ri. transmissions.For convenience, the throughput analysis is grouped into three SNR ranges. For 22dB andgreater, Equation 5 can be reduced toE(X) = 1 X 13data + 2 X (1 — Pdata)P12 = 2 — ciata, (6)yieldingTIMAX (7)—rdataAlthough, for 16 to 20dB, Pframe and Pheader are less than one, they are close enough to providean upper bound using Equation 7. For channel conditions 14dB and lower, 1data has dropped toChapter 5. MDLP Simulation and Performance Evaluation 67Figure 5.5 Throughput for Selective Repeat ARQ Schemezero. Data packets are decodable only after two or more copies of P1 or P2 have been received.Using Equation 5, the expected number of transmissions per frame is 1 + 1/F2, yieldingP12T1T1MAXXffl (8)r12 + 1)as an upper bound. The results from the Estelle simulation match very closely to those calculatedfrom Table 4, and can be seen in Figure 5.6. Note that the throughput curve exhibits the classicType-TI shape with a plateau at one half of the maximum throughput (‘--‘ 7MAX/2 = 0.42),Chapter 5. MDLP Simulation and Petformance Evaluation 68This corresponds to the situation where two copies of the data need to be received beforedecoding is successful. Reasonable performance is retained until approximately 10dB, uponwhich throughput drops rapidly to zero. 5.6 Throughput for T’pe-II ARQ SchemeFigure 5.7 shows the performance improvement of a Type-TI Hybrid ARQ scheme over aclassic selective repeat retransmission algorithm. For extremely good channel conditions, suchas at a SNR of 40dB and greater, both schemes perform similarly, The Type-TI scheme is clearly7/IEstelie simulationCalculated from Stats5 10 15 20 25 30 35 40SNR [dB]Chapter 5. MDLP Simulation and Performance Evaluation 69superior for lesser channel conditions, particularly at 25dB and lower. In this range, reasonablethroughput is still obtained using the Type-TI scheme of the MDLP, while the selective repeatprotocol can no longer provide any significant throughput. With only a small increase in protocolcomplexity, acceptable throughput can be maintained even at very high channel error rates.5.7 SummaryFigure 5.7 SR vs. Type-TIUsing an Estelle-C compiler, a Type-TI Hybrid ARQ scheme has been implemented in Estelle.Chapter 5. MDLP Simulation and Performance Evaluation 70The results from the Estelle simulations correspond very closely to expected values, providingadditional reassurance that the protocol is operating properly. Upon closer examination of Table4, and while running the simulations, two observations can be made. First, combining two copiesof Pi rarely occurs, and when it does occur, it has a negligible effect on the throughput. This canbe seen as follows: for two copies of P1 to arrive at the receiver, an intermediate P2 frame musthave been lost, either through a missed frame synchronization or an invalid header. These twopossibilities only become significant at 14dB or lower, but the probability of decoding successwith two copies of P1 , F11 in this range has already dropped to zero. Similarly, this occurs whentwo copies of P2 are received since these two encoder output sequences are denoted arbitrarily.Second, low SNR performance (10dB and lower) could be further increased by storing morethan the two most recent copies at the receiver. In this range, both Pframe and Pheader are stillrelatively high, with P12 limiting the overall throughput. Using more than two copies to assistin decoding could significantly increase throughput at this high error rate. Results obtained fora regular selective repeat ARQ scheme also match the expected values.The Estelle code could easily be extended to support an arbitrary number of convolutionalencoder generators (P1 . . . P) or buffering of more than two copies at the receiver for increasedcombining power at low SNR. The modular nature of Estelle provides a straightforward way tomodify the ARQ scheme or frame coding technique. This specification could also be extendedto support complementary punctured convolutional codes as discussed in [36]. One significantstatistic which was not included in the simulations or in the expected numerical results was thefalse alarm probability of the flag. Since the flag is being searched on a bit-by-bit basis, theEstelle specification, as it is, cannot take into account the affect of a false frame synchronization.Chapter 5. MDLP Simulation and Peiformance Evaluation 71This false alarm probability will decrease the overall throughput, particularly at low SNR. Usingthe data in Table 4, introduces a number of limitations. The statistics are directly related to thecontent and size of each field. Currently, in the simulations, the data field is limited to 900 bitsin length. These restrictions can be removed with real-time channel model as discussed in 6.2.5.As an aside, when setting up the link, an optional quality-of-service (QOS) parameter is allowedin the CONNReq primitive. This parameter could be used to correspond to different encodingroutines, each of which would exhibit certain performance characteristics. For example, the QOSparameter may represent a request for an encoding scheme with a high maximum throughput ora particularly powerful code when channel error rates are expected to be extremely high.72Chapter 6 Conclusions6.1 ConclusionsData communications protocols are traditionally defined informally, with a combinationof English prose, state tables and state diagrams. ‘While these methods are useful, they areprone to different interpretations and can be vague, leading to ambiguities. A number of formaldescription languages have recently been accepted by ISO, among them Estelle and LOTOS, andare beginning to be used for specifying communication protocols. These languages have rigidlydefined structures and procedures to represent protocol operations in a clear and precise manner.A mobile data link protocol using a Type-IT Hybrid ARQ scheme has been documented inEstelle. Ambiguities have been minimized through a complete description of protocol operationsand the specification is easily extensible. The Estelle specification provided a foundationfor testing, simulation, and performance evaluation. This protocol was tested using the Edbdebugger and performance simulations were obtained using the Ec compiler complemented witha statistical channel model. Manual validation of the MDLP was performed using a combinationof observers, macros, and step-by-step execution of the specification To provide a realisticsimulation environment to execute the protocol, a channel simulator module was developed usingsuccess probabilities of the flag, header, and data fields. The throughput measurements obtainedfrom these simulations are in close agreement with the calculated results. For comparisonpurposes, the throughput of a simple selective repeat ARQ scheme was also presented. Theseperformance results combined with thorough manual testing provide strong corroboration for thecorrectness of the specification.Chapter 6. Conclusions 73The progressive development of tools for Estelle, and, in general, for other FDT’s, is essentialto exploit the advantages of formal methods. Currently, Estelle software development tools areprimitive compared to more mature programming languages such as C. The modular nature ofEstelle may lead to pre-built functions, forming libraries of commonly used modules such asencoders, decoders, and standard I/O functions. Protocol designers would then be able to usethese libraries in constructing their own protocols.Both Edb and Ec are part of the Estelle Development Toolset. EDT provided a satisfactorydevelopment tool with many useful features and an extensive simulation environment. Althoughnot particularly user-friendly, Edb, supplemented with complete documentation, was efficientand functional.The potential of Estelle has yet to be fully realized, both in terms of support software anduse in protocol specification. For future research, the following topics are suggested.6.2 Suggestions for Future Research6.2.1 Robust Link ManagementThe MDLP currently uses a rudimentary 2—way handshake mechanism for link connectionand disconnection, with no provision for error-recovery. Further work could be done in improvingthe robustness of these link management features by incorporating timers in order to recover fromframes lost during connection or disconnection negotiation.6.2.2 Explicit Data Link Flow ControlFlow control between peer MDLP stations is accomplished implicitly through the withholdingof acknowledgments. This results in extra retransmissions, due to timer expiry, that are discardedChapter 6. Conclusions 74at the receiver. A more efficient method would be to use a frame, Receiver Not Ready (RNR),to explicitly initiate flow control. This would eliminate unneeded retransmissions.6.2.3 Extension to Multiple AccessEstelle allows the dynamic creation and destruction of child modules of a subsystem. Thisfeature can be used to extend the point-to-point MDLP into supporting multiple access. Whensetting up new links, the DLL will spawn off new child modules, A, which are copies (instances)of the Protocol Logic and Frame Codec modules. Two additional modules need to be included tomultiplex the multiple data streams by examining the frame address and diverting that frame tothe appropriate A module. The module structure for this proposal is seen in Figure 6.1. When aparticular data connection is completed, the DLL can destroy the A module associated with thatconnection. Although the maximum number of simultaneous connections would be processorand memory dependent, this dynamic module allocation would provide efficient memory usage.Figure 6.1 Data Link Module structure for Multiple Access6.2.4 Time in EstelleEstelle has provision for expressing time using the DELAY and TIMESCALE clause. But,during simulation and software implementation of the MDLP, this command was not usedI Address Multiplexer II Address Multiplexer IChapter 6. Conclusions 75because of problems discovered in EDT. Better timer management is required to provide amore realistic simulation environment.6.2.5 Estelle Channel ModelThe channel simulator module used in this thesis relied on an external source to providethe necessary probabilities to form a statistical model of a Rayleigh faded channel with AWGN.This reliance is clearly restrictive when exploring extensions to the Type-TI Hybrid ARQ schemepresented. An Estelle module which provides a real-time channel simulator would be valuablein any further development. Such a simulator has already been written in C to support workin [21] and [301.6.2.6 Soft Decoding and Bit Level SupportWhen using a real-time channel simulator, it will be necessary to use soft decoding, whichwill require modification of the Frame Codec module, as well as a number of functions in theProtocol Logic module. The present integer type used for the data field in the logical framewill be replaced with real numbers, and functions that deal with combining and decoding willalso need to be written to support soft decoding. This would provide low level support routinesfor any extensions to the MDLP.76Bibliography[1] Iso 9074, Information Processing Systems — Open Systems Interconnection — Estelle: AFormal Description Technique Based on an Extended State Transition Model. InternationalStandards Organization, 1989.[21 G. Bochmann and C. Sunshine, “Formal Methods in Communications Protocol Design,”IEEE Trans. Commun., vol. COM-28, pp. 624—631, Apr. 1980.[3] ISO 8807, Information Processing Systems Open Systems Interconnection — LOTOS: AFormal Description Technique based on the Temporal Ordering ofObservational Behaviour.International Standards Organization, 1988.[4] Z. 100, Specification and Description Language (SDL). CCITT, 1992.[5] ISO 8824, Information Processing Systems Open Systems Interconnection Specificationof Abstract Syntax Notation One (ASN.1). International Standards Organization, 1987.[6] ISO 9646, Information Processing Systems — Open Systems Interconnection — Tree andTabular Combined Notation (TTCN). International Standards Organization, 1991.[7] P. Ernberg, T. Hovander, and F. Monfort, “Specification and Implementation of an ISDNTelephone System Using LOTOS,” in Formal Description Techniques, V—Proceedings ofthe IFIP TC6/WG6.1 Fifth International Conference on Formal Description Techniques forDistributed Systems and Communications Protocols — FORTE ‘92 (M. Diaz and R, Groz,eds.), pp. 171—186, North-Holland, 1993.[8] A. Azcorra, E. Vázquez, M. Alvarez-Campana, and J. Vinyes, “Formal DescriptionTechniques at Work: An ISDN Q.931 Implementation Using LOTOS,” in Proceedings ofthe 13th IFIP Symposium on Protocol Specification, Testing, and Verification (A. Danthine,G. Leduc, and P. Wolper, eds.), pp. Dl—l to Dl—l5, 1993.[9] H. Hirschl, J. Blanchard, and B. Loyer, “LOTOS in Alcatel,” in Formal DescriptionTechniques, V — Proceedings of the IFIP TC6IWG6.1 Fifth International Conference onFormal Description Techniques for Distributed Systems and Communications Protocols —FORTE ‘92 (M. Diaz and R. Groz, eds.), pp. 15—22, North-Holland, 1993.[10] F. Carrasco and J. Gil, “A Method for Specifying and Validating Communication Protocolsin LOTOS,” in Formal Description Techniques, V — Proceedings of the IFIP TC6IWG6.1Bibliography 77Fifth International Conference on Formal Description Techniques for Distributed Systemsand Communications Protocols FORTE ‘92 (M. Diaz and R. Groz, eds.), pp. 247—262,North-Holland, 1993.[11] J. Bredereke, R. Gotzhein, and F. Vogt, “Design of a Formal Estelle Semantics forVerification,” in Formal Description Techniques, V — Proceedings of the IFIP TC6IWG6.]Fifth International Conference on Formal Description Techniques for Distributed Systemsand Communications Protocols — FORTE ‘92 (M. Diaz and R. Groz, eds.), pp. 153—168,North-Holland, 1993.[121 P. Dembinski, “Queuing Network Model for Estelle,” in Formal Description Techniques,V — Proceedings of the IFIP TC6/WG6.1 Fifth International Conference on FormalDescription Techniques for Distributed Systems and Communications Protocols FORTE‘92 (M, Diaz and R. Groz, eds.), pp. 73—86, North-Holland, 1993.[13] L. Doldi and P. Gauthier, “VEDA 2: Power to the Protocol Designers,” in FormalDescription Techniques, V — Proceedings of the IFIP TC6/WG6.1 Fifth InternationalConference on FormalDescription Techniquesfor Distributed Systems and CommunicationsProtocols — FORTE ‘92 (M. Diaz and R. Groz, eds.), pp. 3—13, North-Holland, 1993.[14] S. Haddad, M. Taghelit, and B. Zouari, “Assessment of Estelle and EDT through Real CaseStudies,” in Proceedings of the 13th IFIP Symposium on Protocol Specification, Testing,and Venfication (A. Danthine, G. Leduc, and P. Wolper, eds.), pp. D4—l to D4—l6, 1993.[15] 5. Budkowski, B. Alkhechi, M. Benalycherif, P. Dembinski, M. Gardi, and E. Lallet,“Formal Specification, Validation, and Performance Evaluation of the Xpress TransferProtocol,” in Proceedings of the 13th IFIP Symposium on Protocol Specification, Testing,and Verification (A. Danthine, G. Leduc, and P. Wolper, eds.), pp. D2—l to D2—16, 1993.[16] X.25, Interface between Data Terminal equipment (DTE) and Data Circuit-TerminatingEquipment (DCE) for terminals operating in the packet mode on Public Data Networks.CCITT, 1977.[17] ISO 3309, Information Technology — Telecommunications and Information exchangebetween systems — High-Level Data Link Control Procedures (HDLC) — Frame Structure.International Standards Organization, 1991.[18] ISO 4335, Information Technology — Telecommunications and Information exchangebetween systems — High-Level Data Link Control Procedures (HDLC) — Elements ofBibliography 78Procedures. International Standards Organization, 1991.[19] S. Kallel, “Analysis of a Type II Hybrid ARQ scheme with Code Combining,” IEEE Trans.Commun., vol. COM-38, pp. 1133—1137, Aug. 1990.[20] S. Bakhtiyari, S. Kallel, and V. Leung, “A Robust Type II Hybrid ARQ Scheme withCode Combining for Mobile Communications,” in Proceedings of the IEEE Pacific RimConference on Communications, Computers and Signal Processing, vol. 1, (Victoria,Canada), pp. 214—217, May 1993.[21] S. Bakhtiyari, T. Chen, S. Kallel, and V. Leung, “Practical Implementation of a Mobile DataLink Protocol with a Type II Hybrid ARQ Scheme and Code Combining,” in Proceedingsof the IEEE Conference on Vehicular Technology, (New Jersey, U.S.A.), pp. 774—777, May1993.[22] ISO 7498, Information Processing Systems — Open Systems Interconnection BasicReference Model. International Standards Organization, 1984.[23] G. Bochmann, “Usage of Protocol Development Tools: The results of a survey,” in ProtocolSpecification, Testing, and Verification VII (C. Rudin, ed.), North-Holland, 1987.[24] A. Loureiro, S. Chanson, and S. Vuong, “FDT Tools for Protocol Development,” in 5thInternational Conference on Formal Description Techniques, (Lannion, France), pp. 38—78, Oct. 1992.[25] S. Vuong, A. Lau, and R. Chan, “Semi-automatic Implementation of Protocols Using anEstelle-C Compiler,” IEEE Trans. on Software Eng., vol. 14, pp. 384—393, Mar. 1988.[26] 5. Budkowski, “Estelle Development Toolset (EDT),” Computer Networks and JSDNSystems, vol. 25, pp. 63—82, Aug. 1992.[27] S. Budkowski and P. Dembinski, “An Introduction to Estelle: A Specification Languagefor Distributed Systems,” Computer Networks and ISDN Systems, vol. 14, no, 1, pp. 3—23,1987.[281 T. Chen, S. Kallel, and V. Leung, “Formal Description of a Mobile Data Link Protocol,”in Proceedings of the IEEE Pacific Rim Conference on Communications, Computers andSignal Processing, vol. 2, (Victoria, Canada), pp. 427—430, May 1993.Bibliography 79[29] A. Tanenbaum, Computer Networks. Prentice Hall, 2nd ed., 1988.[30] S. Bakhtiyari, “Performance Evaluation of Adaptive ARQ Schemes,” Master’s thesis,University of British Columbia, Oct. 1993.[31] ISO 8886, information Processing Systems —Data Communications —Data Link ServiceDefinition for Open Systems Interconnection. International Standards Organization, 1988.[32] S. Budkowski, Estelle Simulator/Debugger — Edb: User Reference Manual. BULL S.A.,1992.[33] E. Lallet, C. Lebrun, J. Martin, and S. Budkowski, “Un outils de génération automatiquede l’environment d’exécution de specifications Estelle,” in Actes du Colloque Francophonesur l’Ingénierie des Protocoles (CF1P ‘91) (0. Rafiq, ed.), 1991.[34] D. Rayner, “OSI Conformance Testing,” Computer Networks and ISDN Systems, vol. 14,no. 1, pp. 79—98, 1987.[35] S. Budkowski, Estelle-To-C Compiler — Ec: User Reference Manual. BULL S.A., 1992.[36] S. Kallel, “Complementary Punctured Convolutional (CPC) Codes and their use in HybridARQ Schemes,” in Proceedings of the IEEE Pacific Rim Conference on Communications,Computers and Signal Processing, vol. 1, (Victoria, Canada), pp. 186—189, May 1993,[37] ISO 10022, information Processing Systems — Open Systems interconnection — PhysicalService Definition. International Standards Organization, 1988.[38] R. Sijelmassi and R. Linn, “Guidelines for using Estelle to specify OSI services andprotocols,” Computer Networks and ISDN Systems, vol. 23, pp. 343—362, Feb. 1992.[39] J. Lu, “Semi-automatic Protocol Implementation Using an Estelle-C Compiler, LAPB andRTS Protocols as Examples,” Master’s thesis, University of British Columbia, Aug. 1990.[40] W. Stallings, Data and Computer Communications. Macmillan Publishing Company,3rd ed., 1991.Appendix A: Estelle Code Listing80Dec10199312:18:08mdlp..stlPage1SPECIFICATIONMDLPSYSTEMPROCESS;DEFAULTindividualqueue;CONSTMaxSeq=15;(*MaxSeqhighestseqnumber2n-l*)Modulus=16;NrBufs=8;(*sizeofxmitter&receiverwindow(MaxSeq.l(/2*)MaxBuf=7;(*MaxBuf=t4rBufs-l*(DataSize=900;FrameSize=1013;critical=0;high=1;medium=2;(*priorityclasses*)low3;Pframe=0.8638;Pheader=0.8937;(5channelstatistics*)Pdata=0.0000;P1P2=0.1424;9191=0.0000;l4axTh=0.8411215;(*Maximumthroughput*(TYPEbit=0..1;SequenceNr=integer;NPDU_type=integer;DLSDU_type=ARRAYI1..FrameSizelofbit;Info_typeinteger;Frame_kind=(I,RR,SREJ,SARM,VA,DISC);Indtype=(None,P1,92);CRCl6typ.e=ARRAY(1..16)ofbit;CRC32typ%=ARRAYI1..32)ofbit;flagtype=ARRAYL1..24)ofbit;addresstype=integer;Fraw.e_struct=RECORDflag:flagtype;F_type:Frame_kind;seq:SequenceNr;ack:SequenceNr;address:addresstype;IndSit:Indtype;HeaderCRC:CRCl6type;info:Info_type;DataCRC:CRC32type;END;CHANNELNetworkLink(Upper,Lower);BYUpper: CONNReq(Called:addresstype;Calling:addresstype);CONNReSp(Respoflding:addresstype(;DISCReq;DISCResp;FLOWSTARTReq;FLOWSTOPReq;DATAReg(Sent_packet:NPDU_type);BYLower: CONNInd(Called:addresstype;Calling:addresstype);CONNC0nf(Responding:addresstype);DISCInd;DISCC0nf;FLOWSTARTInd;FLOWSTOPInd;DATAInd(Recvd_packet:NPDU_type);CHANNELPhyeicalLink(Upper,Lower);BYUpper:Dec10199312:18:08mdlp.stlPage2DATAReq(Raw:DLSDU_type);BYLower: DATAInd(Raw:DLSDU_type);(*5****************************YSIcALLAYER********5*55****5*55***5)MODULEPhysical_LayerPROCESS;19P:PhysicalLink(Lower)individualqueue;END;(*Physical_Layer*(BODYPhysical_BodyFORPhysical_Layer;(*EXTERNAL*)END;(*Physical_Body*((******************************NETWORKLAYER**********************************)MODULENetwork_LayerPROCESS;19N:NetworkLink(Upper)individualqueue;END;(*Network_Layer*)BODYNetwork_BodyFORNetwork_Layer;(*EXTERNAL*(END;(5Network_Body*)(*****************************DATALINKLAYER*******************************)MODULEData_Link_LayerPROCESS;IPDl:NetworkLink(Lower)individualqueue;D2:PhysicalLink(Upper)individualqueue;END;(*Data_Link_Layer*(CHANNELConvert(Upper,Lower);BYUpper: ENCODEReq(Out:Frame_struct);BYLower: DECODEInd(Inp:Frame_struct;ValidFiag:boolean;ValidHeader:boolean;VelidData:boolean);BODYData_Link_BodyFORData_Link_Layer;MODULEProtocol_LogicPROCESS;19Li:NetworkLink(Lower)individualqueue;L2:Convert(Upper(individualqueue;END;(*Logic5)BODYProtocol_Logic_BodyFORProtocol_Logic;51’ATEIDLE,SETUP_READY,ABM,DISC_READY;Out_etruct=RECORDo1Dec10199312:18:08mdlp.stlPage3timer:ARRAYLO..Maxseg)ofbooleen;count:ARRAYED..l4axSeq(ofinteger;IndBit:ARRAYEO..MaxSeqlofIndtype;END;Buf_type=RECORDIndBit:tndtype;info:Info_type;rawinfo:NPDU_type;END;VARAckExpected:SeguenceNr;(*loweredgeofsenderwindow*)NextFrameToSend:SequenceNr;(*upperedgeofsenderwindow+l*)FrameExpected:SequenceNr;(*loweredgeofreceiverwindow*)TooFar:SequenceNr;(*upperedgeofreceiverwindow÷l*)j:integer;(*indexintobufferpool*)r:Frame_struct;(*workvariables*)s:Frame_struct;t:Frame_struct;DataPl:Info_type;DataP2;Info_type;1:integer;BaseAddress:addresstype;RemoteAddress:addresstype;tmpaddress:addresstype;OutBuf:ARRAYEO..MaxBufofNPDU_type;(*outputbuffer*)InBuf;ARRAYIO..MaxBufjofBuf_type;(*inputbuffer*)ReceivedOK:ARRAY[O. .MaxBuf}ofboolean;(*inboundbitmap*)OutMap:Out_struct;(outboundbitmap)nbuffered:SequenceNr;(*numberofoutputbufferscurrentlyused*)NoNak:boolean;(*settofalsewhen-nakissent*)/PiggyBackAckTimer:boolean;(*piggybackedACKtimer*)PiggyBamkCount:integer;DataLinkBusy:boolean;(settoTRUEwhenDLbuffersfull*)NetworkBusy:boolean;(*settoTRUEwhenNetbuffersfull*)ValidFrameCount:integer;TotaiFrameCount:integer;Seed:integer;P4,P5:real;th:real;(*throughput*)PROCEDUREClear;(*zerosallvariables)VAR1:integer;BEGINNextFrameToSend:=0;AckExpected:=0;FrameExpected:=0,TooFar:NrBufs;nbuffered:=0;NoNak:=true;FORj:=0TOMaxBufDOBEGINReceivedOKfj]:=false;OutMap.timer[jj:=false;OutMap.IndBittj):=P1;END;FOR:=0TOt4axSeqDOBEGINOutMap.timerlj);=false;OutMap.count(j):=0,OutNap.IndBit(j):=P1;END;Dec10199312:18:08mdlp.StIPage4DataLinkBusy:=false;NetworkBusy:=false;PiggyBackAckTimer:=true;PiggyBeckCount:=0;ValidFrameCount:=0;TotalFrameCount:=0;th:=0.0;END;(*Clear*)PROCEDUREinc(vark:SeguenceNr);(*incrementkcircularly*)BEGINIFk<MaxSeqTHENk:=k+1ELSEk:=0;END;(*inc)FUNCTIONbetween(a,b,c:SequenceNr):boolean;(*checkstoseeifa<=b<=ccircularly*)BEGINIF((a<=b)AND(b<c)OR(c<a)AND(a<=b)OR(b<c)AND(C<=a))THENbetween:=trueELSEbetween:=falseEND;(*between*)FUNCTIONRandom:real;BEGINRandom:=0;($C$_rl97_random=drand48O/(double)(6S536);END;PROCEDUREPrepareFrame(fk:Frame_kind;FrameNr:SequenceNr);(*ConstructandsendanI:RR,SRE3,SABM,UA:orDISCframe*)BEGINs.F_type:=fk;s.address:=RemoteAddress;CASEfkOF I:BEGIN s.seq:=FrameNr;C.ack:=(FrameExpected+MaxSeq)NODModulus;;s.IndBit:=OutMap.IndBit[FrameNr);OutMap.timer[FrameNr):=true;END;RR:BEGIN s.ack:=(FrameExpected+NaxSeq)MODModulus;END;SREJ:BEGIN s.ack:=(FrameExpected+MBxSeq)NODModulus;NoNak:=false;END;SABM:BEGINEND;UA:BEGIN s.address:=BaseAddress;END;DISC:BEGINEND;END;END,(*Data_Link...Body)•0.Dec10199312:18:08mdlp.sttPage6Dec10199312:18:08mdlp.stIPage5PROCEDUREUpdsteSenderWindow;(stopstimersonacknowledgedframes*)BEGINWHILEbetween(AckExpected,r.ack,NextFrameToSend)DOBEGINnbuffered:=nbuffered-1;OutMap.timer)AckExpectedj:false;OutNap.countAckExpected]:=0;.OutMap.IndBit[AckExpected}:*P1;inc(AckExpected);END;END;(*UpdateSenderWindow*3PROCEDURETimeCount;(*advancestimeoroutstandingframes*)VARx-SequenceNr;BEGINFORx0TOZ4axSeqDOBEGINIFOutMap.timerxJ=trueThENOutMap.countrxl:=OutMap.count(xJ+1;END;END;PROCEDURETimeCount2;(*timecounter,orPiggyBackAckTimer*)BEGINIFPiggyaackAckTimer=trueTHENPiggyBackCount:*PiggyBackCount+1;END;FUNCTIONCombinel:boolean;(5receivedP1andPt(orP2andP2),ifdecodablethenreturnresultinInBuf[r.seqNODNrBufs).rawinfo)BEGINP4:=Random;($C$printf(”P4:%f\n,_adctx—>p4);IF(P4<=P1P1)THENBEGIN InBuf[r.seqNODNrBufsJrawinfo:=0;Combinel:=true;ENDELSECombinel:=false,END,FUNCTIONCombitie2:boolean;(*receivedPtandP2.ifdecodablethenreturnresultinInBuf(r.seqMODNrButsl.rawinfo)BEGINPS:*Random;($C$printf(PS%f\n...adctx—>p5);IF(PS<=P1P2)THEN.BEGIN InBuf[r.seqMODNrBufs).rawinfo:=0;Combine2=trueENDELSECombine2;=false;END;FUNCTIONDataDecode(n:Info_type):NPIJV_type;BEGIN3*EXTERNAL*)DateDecode:=0;END;FUNCTIONViterbiCheck(a:Info_type;b:Info_type):boolean;3*CheckstoseeifdatacanberetrievedusingViterbidecoder*)BEGIN3*EXTERNAL*)ViterbiCheck:=true;END;3*ViterbiCheck*3FUNCTIONViterbiDecode)a:Info_type;b:Info_type):NPDU_type;(*retrievesdatausingViterbidecoder)BEGIN(*EXTERNAL*)ViterbiDecode:=0;END;(*ViterbiDecode5)PROCEDUREPrintThroughput;BEGINth:=Maxph*(ValidFrameCount/TotalFrameCount);($C$printf)°Valid:%d,Total:%d,n%f\n”,_adctx->validframecount,_adctx->totalframecount,_adctx->th);END;(*****************************LDOICTRANSITIONS*******************************)INITIALIZE TOIDLEBEGINClear;END;(5*******************LinkSetup*************************3TRANS(51*)FROMIDLEWHENL1.CONNRegTOSETUP_READYBEGINBaseAddress:=0;RemoteAddress1;PrepareFrame(SABM,0);OUTPUTL2.ENCODEReg(s);END;TRANS3*2*3FROMIDLEWHENL2.DECODEIndPROVIDED(Inp.F_type=SABM)Dec10199312:18:08mdlp.stlPage7TOSANEBEGINtmpaddress:=Inp.address;OUTPUTLi.CONNInd)tmpeddress,0);END;TRANS)*3*)FROMIDLEWHENLi.CONNRespTOABMBEGINBeseAddress:=1;RemoteAddress:=0;PrepareFreme)UA,0);OUTPUTL2.ENCODEReq(a);END;TRANS(*4*)FROMSETUP_READYWHENL2.DECODEIndPROVIDED)Inp.F_type=UA)TOABMBEGINtmpaddressInp.addrese;OUTPUTL1.CONNConf(tmpaddress);END;TRANS)*5*)FROMSETUP_READYWHENL2.DECODEIndPROVIDED(Ing.F_type=SABM)TOSAME BEGINPrepereFrame)UA,0);OUTPUTL2.ENCODEReq)s);END;(********************LinkDieconnect*****TRANS)*6*)FROMABMWHENLi.DISCReqTODISC_READYBEGINPrepareFreme)DISC,0);OUTPUTL2.ENCODEReq(s);END;TRANS(*7*)FROMABMWHENL2.DECODEIn8PROVIDED)Inp.F_type=DISC)TOSAMEBEGINOUTPUTLi.DISCInd;END;TRANS(*8*)FROMANNWHENLl.DISCReapTOIDLEBEGINPrepareFrame)UA,0);OUTPUTL2.ENCODEReq)s);END;TRANS(*9*)Dec10199312:18:08mdlp.stlPage8FROMDISC_READYWHENL2.DECODEIndPROVIDED)Inp.F_type*UA)TOIDLEBEGINOUTPUTLi.DISCConf;END;TRANS(*10*)FROMDISC_READYWHENL2.DECODEIndPROVIDED(Inp.F_type=DISC)TOSAMEBEGINPrepareFrama)UA,0);OUTPUTL2.ENCODEReq)s);END;DataTransfer*************************)TRANS)*ii:dataracaivedfromnatworklayar,bufferthantransmit*)FROMABMWHENLi.DATAReqPROVIDED)DataLinkBusy=falsa)PRIORITYlowTOSAMEBEGINnbuffared:=nbuffared+1;OutBuf[MextFrameToSandMODNrBufsl:=Sent_packet;PraparaFrame(I,NaxtFrameToSend);OUTPUTL2.ENCODEReq)s);TimaCount;IF(s.IndBit=Pl)THEM{$C$printf)”Iframesent,\n’,_adctx->.naxtframetosend);ELSE)$C$grintf(”Iframesent,,P2\n,_adctx->nextfremetosend););PiGgyBeckAckTimer:=false;inc)NextFremeToSend);END;TRANS(*12:transmitbufferhas/isgoingtooverflow,initstelinklayerflowcontrol*)FROMABMPROVIDED)nbuffered>=NrBufs)AND)DataLinkBusy*true)PRIORITYcriticalTOSAMEBEGINDataLinkBusy:=true;-)$C$printf(”LinkLayerFlowControlON\n’);OUTPUTLi.FLONSTOPInd;END;TRANS)*13:transmitbufferhasroom,enableflowfromnetworklayer*)FROMABMPROVIDED)nbuffered<NrBufs)AND(DetaLinkBusy=false)PRIORITYcriticalTOSAMEBEGINDataLinkBuey:=false;($C$printf(*LinkLayerFlowControlOFF\n);OUTPUTLi.FLONSTARTInd;END;TRANS)*14:Networklayerbufferbeingoverflowed,stopsendingdetetonetworklayer*)END;SendingIt’saDec10199312:18:08mdlp.stlPage9FROMABMWNENLi.FLOWSTOPReqPRIORITYcriticalTOSAMEBEGINNetworkBusy:=true;END;TRANS(15:Networkbuffernowhasroomformoredata*)FROMABMWNENL1.FLOWSTARTReqPRIORITYcriticalTOSAMEBEGINNetworkBusy:=false;END;TRANS(*16:validIframereceived,placedatainreceivebufferandtrytodecode.Ifnotdecodeable,sendSREJ*)FROMABMMNENL2.DECODEIndPROVIDED)NetworkBusy=false)AND(ValidFlag=true)AND(ValidNeader=true)AND(Inp.F_type=I)AND(Inp.address=BaseAddress)AND(ReceivadOx)Inp.seqMODNrBufs)=false)PRIORITYhighTOSAMEBEGIN.r:=Inp;UpdateSenderMindow;TotalFrameCount:=TotalFrameCount+1;TimeCount2;IF(r.seq<>FrameExpected)AND(NoNak=true)TNENBEGIN PrepareFrame(SREJ,0);OUTPUTL2.ENCODEReq)s);{$C$printf)’SREJfor:%d\n”,_adctx->frameexpected);PiggyBackCount:=0;END;IFbetween(FrameExpected,r.seq,TooFar)=falseTNENBEGIN{$C$printfl”lostcopy;\n”);IFbetween)FrameExpected.r.seg,TooFar)=trueThENBEGIN IFr.IndBit=PlTNEN($C$printf(Receiveddata:%d,Pl\n”,_adctx—>r.r92_seq);ELSE($C$printf(”Receiveddata:%d,P2\n”,_adctx->r.r92eq););IF)ValidData=true)TNENBEGIN ReceivedOKLr.seqMODNrBufs):=true;InBuf[r.seqMODNrBufsj.rawinfo:=Dataoecode(;IF)ReceivedOR(FrameExpectedMODNrBufs))AND(NetworkBusy=false)TNENBEGIN ($C$printf)”Sending%dtoNetworkLayer\n”,_.adctx->r.rP2...seg);OUTPUTLl.DATAInd(InBuf(FrameExpectedMODNrBuf5).rawinfo);ReceivedOK(FrameExpectedMODNrBufs]:cfalse;Dec10199312:18:08mdlp.stlPage10fnc)FrameExpected);inc)TooFer)ValjdFrameCcunt:=ValidFrameCount+l;PrepareFreme(RR,NextFrameToSend);OUTPUTL2.ENCODEReq(s);InBuf)FremeExpectedMODNrBufs).IndBit:=None;PrintThroughput;NoNak:=true;PiggyBackAckTimer:=true;PiggyBackCount:=0;END;ENDELSEBEGIN IF)r.seq=FrameExpected)TNENNoNak:=true;)*Case1:nopreviouscopies*)IFInBuf)r.segMODNrBufs).IndBit=NoneTNENBEGIN InBuf)r.seqMODNrBufs).IndBit:=r.Indbit;InBuf(;($C$printf)”Cannotdecodewithsinglecopy\n”);IF)NoNak=true)TNENBEGINPrepareFrame)SREJ,0)OUTPUTL2.ENCODEReq(s);END;END(*Case2:P1andP1,orP2andP2)ELSEIFInBuf)r.segMODNrBufs).IndBit=r.IndBitThENBEGINIF(Combinel=true)TNENReceivedOK)r.seqMODNrBufs):=trueELSEBEGIN InBuf);InBuf)r.seqMODNrBufs).IndBit:=r.Indbit;)$C$printf(”Cannotdecodewithtwocopies\n’) IF)NoNak=true)TNENBEGINPrepareFrame)SREJ,0)OUTPUTL2.ENCODEReq)s);END;END;END)*Case3:P1andP2,orP2endP1)ELSEIFInBuf)r.seqMODNrBufs).IndBitor.IndBitThENBEGINIF)Combinei=true)TNENReceivedOx)r.seqMODNrBufs):=trueELSEBEGIN InBuf)r.seqMODNrBufs);In8uf)r.seqMODNrBufs).IndBit:=r.IndBit;)$C$printfV’Cannotdecodewithtwocopies\n”);IF)NoNak=true)TNENBEGINPrepareFrame)SREJ,D);OUTPUTL2.ENCODEReq)s);END;END;END;END;VIDec10199312:18:08mdlp.stlPage11END;END;TRANS(*17:looksatreceivedatabuffer,InBuf,andpassesvalidordereddatatonetworklayer*)FROMARMPROVIDED(ReceivedOK(FremeExpectedMODNrBus)=true)AND(NetworkBusy=false)PRIORITYmediumTOSAMEBEGIN WHILE(ReceivedOK[FrameExpectedMODNrBufs)=true)DOBEGIN OUTPUTL1.DATAInd(InBuf[FrameExpectedMODNrBufs]rawinfo);($C$printf(’Sending%dtoNetworkLayer\n”,_adctx->frameexpected);ReceivedOK)FrameExpectedMODNrButs):=false;InBuf)FrameExpectedMODNrBufs).IndBit:=None;inc(FrameExpected);inc(TooFar);ValidFrameCount,=ValidFraxneCount+1;END; PrintThroughput;NoNak;=true;PiggyBackAckTimer:=true;PiggyBackCount:=0;END;TRANS(*18:SREJreceived,resendrequestedframe*)FROMARMWHENL2.DECODEIndPROVIDED(ValidFlag=true)AND(ValidHeadertrue)AND(Inp.F_type=SREJ)AND(Inp.address=BaseAddress)ANDbetween(AckExpected,(Inp.ack+l)MODModulus,NextFrameToSend)PRIORITYhighTOSAMEBEGINr:=Inp;UpdateSenderWindow;IFOutMap.count)(r.ack+1)MODModulus)>=2THENBEGINOutMap.count[(r.ack+1)MODModulus):=0;IFOutMap.IndBit[(r.ack+l)MODModulus)=P1THENOutMap.IndBit)(r.ack+1)MODModulus):=P2ELSEOutMap.IndBitHr.ack+l)HODModulus]:=P1;PrepareF.rame(I,(r.ack+1)HODModulus);OUTPUTL2.ENCODEReq(s);IF(s.IndBit=Pl)THEN($C$printf(’SREJreceived,resend%d,Pl\n,mod()int)_adctx->r.r93_ack÷l,(int)r52juodulusH;ELSE($C$printf(”SREJreceived,resend%d,P2\n”,mod)(int)_adctx—>r.r93_ack+l,(int)r52jnodulus));)PiggyBackAckTimer:=false;END;TimeCount;END;TRANS(‘19:RRframereceived*)FROMABMWHENL2.DECODEIndPROVIDED(ValidFlag=true)AND(ValidHeader=true)AND(Inp.F_type=RR)AND(Inp.address=BaseAddress)PRIORITYhighTOSAMEBEGINr:=Inp;($C$printf)”RRreceived,updatingwindow\n);Dec10199312:18:08mdlp.stlPage12TimeCount;UpdateSenderWindow;END;TRANS(*20;didnotsynchtoframe,invalidheader,duplicateIframe,wrongaddress,orinvalidSREJframe*)FROMARMWHENL2.DECODEIndPROVIDED(VelidFlag=false)OR(ValidHeader=false)OR(ReceivedOK)Inp.seqMODNrBufs)=true)OR(Inp.address<>BaseAddress)OR((Inp.F_type=SRE3)ANDNOT(between(AckExpected,(Inp.ack÷l)MODModulus,NextFrameToSend)))TOSAMEBEGIN($C$printf(”Invalidframe\n”);TotaiFrameCountTotaiFrameCount+1;TimeCount;TimeCount2;END;TRANS(*21:retransmissiontimers*)FROMABMANY1:0..MaxSeqDOPROVIDED)OutMap.timer)l)=true)AND(OutMap.count)1)>=4*jf)TOSANEBEGINOutMap.timer[1):=false;OutMap.count)l):=0;IFOutMap.IndBit[1)=P1THENOutMap.IndBit)1]:=P2ELSEOutMep.IndBit]1]:=P1;PrepareFrame(I,1);OUTPUTL2.ENCODEReq(s);IF(s.IndBit=P1)THEN{$C$prjntf(”Resending%d,Pl\n”,adctx—>_any22_l);ELSE($C$printf)”Resending%d,P2\n’,_adctx->any22_1););TimeCount;PiggyBackAckTimer,=false;END;TRANS(22:idletimertick*)FROMABMANY1:0..MaxSeqDOPROVIDED(OutMap.timer)l)=true)TOSAMEBEGIN($C$printf)IdleTimeTick\n’)TimeCount;END;TRANS(*23:PiggyBackAckTimer*)FROMABMPROVIDED(PiggyBackAckTimertrue)AND(PiggyBackCount>=8)TOSAMEPRIORITYcriticalBEGINPrepareFrame(RR,0);OUTPUTL2.ENCODEReq(s);($C$printf(PiggyBackTimerexpired,sendRR\n”);PiggyBackCount:=0;END;END;)*Data_link.Boay*)GODec10199312:18:08mdlp.stlPage13MODULEFrame_CODECPROCESS;IPCl:Convert(Lower)individualqueue;C2:PhysicalLink(Upper)individualqueue;END;(*Bit_Operations*)BODYFrame_CODEC_BodyFORFrame_CODEC;ATENOWHERE,VARu:Frame_struct;w:Frame_struct;v:DLSDU_type;zerol6CRC:CRCl6type;zero32CRC:CRC32type;zerobitpacket:DLSDU_type;PROCEDUREClear;VARj:integer;BEGINFORj:=1TO16DOzerol6CRC(jl:=0;FORj:=1TO32DOzero32CRCtj]0;FORj:=1TOFrameSizeDOzerobitpacket[jl:=0;END;(*Clear*)FUNCTIONCalculateHeaderCRC(a:Frame_kind;b:SequenceNr;C:SequenceNr;d:Indtype):CRCl6type;BEGIN(*EXTERNAL)CalculateHeaderCRC:=zerol6CRC;END;(*CalculateHeaderCRC*)FUNCTIONCalculateDataCRC(a:Info_type);CRC32type;BEGIN(*EXTERNAL*)CalculateDataCRC:=zero32CRC;END;(*CalculateDataCRC*)FUNCTIONCheckHeaderCRC(m:Frame_struct):boolean,BEGIN)*EXTERNAL)CheckHeaderCRC:=TRUE;END;FUNCTIONCheckDataCRC(a:Frame_struct):boolean;BEGIN(*EXTERNAL*)CheckDataCRC:=TRUE;END,FUNCTIONFrameEncodeta:Frame_struct)DLSDU_type;(*Encode8ndInterleavetheframe*)BEGIN(*EXTERNAL*)Dec10199312:18:08mdlp.stlPage14FremeEricode:zerobjtpacket;END;(*Encode*)FUNCTIONFraoeDecode(a:DLSDU_type)Frame_struct;(*DecodeandDeinterleavethebitpacket*)VARt:Frame_struct;BEGIN(*EXTERNAL*)t.F_typeI;t.seq0;t.ack:=0;t.IndBjt,=P1;t.HeaderCRCzerol6CRC;,=0;t.DataCRC:=zero32CRC;FrameDecode:=END;(*Decode*)(********************************CODECTRANSITIONS********************INITIALIZE TONOWHEREBEGINClear;END;TRANSFROMNOWHEREWHENCl.ENCODEReqTOSAMEBEGINu:=Out;VFrameEncode(u);OUTPUTC2.DATAReq(v);END;TRANSFROMNOWHEREWHENC2.DATAIndTOSAMEBEGINV:=Raw;w:=FrameDecode(Raw);OUTPUTCl.DECODEInd(w,true,CheckHeaderCRC(w),CheckOataCRC(wH;END;END;(*Bit_Body*)**************DATALINKINITIALIZATION***************MODVARPrL;Protocol_Logic;FC:Frame_CODEC;INITIALIZE BEGININITPrLWITHProtocol_Logic_Body;fNITFCWITHFrame_CODEC_Body;CONNECTPrL.L2TOEC.C1;A’rIACHDlTOPrL.Ll;ATTACH02TOFc.c2;END;CoDec10199312:18:08mdlp.stlPge15END;(*Data_Link_Body*)(*******************************BLACKCHANNELStraightLink(Sender,Receiver);BYSender;ENCODEReq(Out:Frame_struct);BYReceiver:DECODEInd(Inp:Frame_struct;ValidFlag:boolean;ValidHeader:boolean;ValidData:boolean);MODULEBlackBoxPROCESS;IPXl:Straightbink(Receiver)commonqueue;1(2:StraightLink(Receiver)commonqueue;END;(5BlackBox*)BODYBlack_BodyFORBlackBox;VARPl,P2,P3:real;ftFrame_kind;Seed:integer;BadData:integer;FUNCTIONRandom:real;BEGINRandom:=0;($C$_r13.$_random=drand48()/(double)(65536);END;STATENowhere;INITIALIZE TONowhere BEGINEND;TRANSFROMNowhereWHENKl.ENCODEReqTONowhere BEGINDec10199312:18:08mdlp.stlPage16OUTPUTKl.I2ECODEInd(Out,(Pl<=Pframe)(P2<=Pheader},(P3<=Pdata))IF(P1<=Pframe)THEN($C$printf(”%d<\n,_adctx->ft)ELSE($C$printf(”,_adctx—>ft)END;END;(5Black_Body*)(*****************************ALLLAYERINITIALIZATION*****************)MODVARPL:Physical_Layer;DL;Data_Link_Layer;NL:Network_Layer;Gateway:BlackBox;INITIALIZE BEGININITFLWITHPhysical_Body;INITDLWITHData_Link_Body;INITNLWITHNetwork_Body;CONNECTNL.NTODL.D1;CONNECTDL.D2TOPL.P;END;END.(5MDLP5)ft:=Out.F_type;P1:=Random;P2:=Random;P3:=Random;IF(P3>Pdata)THENBadData:=BadData÷1;OUTPUTK2.DECODEInd(Out,(Pl<=Pframe),(P2<=Pheader),(P3.<=Pdata));($C$printf(P3:%f,Bad:%d\n,_adctx->p3,_adctx->baddata);IF(P1<=Pframe)THEN($C$printf(”\n,_adctx->ft);ELSE($C$printf(”\n”,_adctx->ft);END;TRANSFROMNowhereWHENK2.ENCODEReqToNowhere BEGINft:=Out.F_type;P1:=Random;P2:=Random;P3;=Random;


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items