An approach to describing a data link level protocol with a formal language

A method approaching the formal description of protocols is presented, and it is shown that the models can follow the way of avoiding the deadlock situation, and the formal grammars are more advantageous for modelling complicated systems than are automata.

Abstract

A method approaching the formal description of protocols is presented. The method -based on formal languages - utilises the relationship between the formal languages and automata and allows the dialogue between two partners/stations, units of equipments, processes, etc./ to be defined in a formal way. The paper considers a data link level protocol, the High Level Data Link Control Procedure. Two basic models are given: the first is for the description of the operation of the stations in half-duplex, the other for the full-duplex transmission mode. A number of other improved models are introduced taking into consideration the effect of time-out, unknown frame, sequence numbering and the request for retransmission frames with a sequence number. It is shown that the models can follow the way of avoiding the deadlock situation, and the formal grammars are more advantageous for modelling complicated systems than are automata. The advantages and limitations of the approach is emphasized by comparing it with approaches elaborated by other authors.