USE OF PETRI NET IN PROTOCOL SPECIFICATION

Abstract

This project work is concerned with application of Petri Net in protocol specification. In this project work, definition of Petri Nets and Protocols are given. The role and importance of formal specification techniques are also discussed. Petri Nets are a graphical tool and could be used for the formal description of the flow of activities in complex systems like protocol. It is gaining popularity in recent years as a tool for the representation of complex logical interactions like synchronization, sequence, concurrency and conflict among physical components or activities in the system. This project work presents a specification of a chosen protocol using Petri Net and implemented the specification using JAVA programming language.  Conclusively, Petri net is shown to be 70% better than other formal protocol specification methods. 

CHAPTER ONE

INTRODUCTION

1.           BACKGROUND OF THE STUDY

The importance of protocol arises from the fact that protocols form the nervous system of teleprocessing networks and as such are responsible for ensuring that the pieces of the system work as a harmonious whole. The complexity and size of today’s systems and the fact that they are put together from subsystem components manufactured in different locations and even by different companies, virtually demand formal specification and there are many side benefits. And so, as open systems and standard network architectures encompass an ever growing segment of the computing industry, the need for clear and precise protocol specification becomes more important. Traditional methods of informal narrative specifications and ad hoc validation have demonstrated their shortcomings as protocol bugs and incompatible implementations crop up. Problems of ambiguous and incomplete specifications are particularly severe for the ever growing number of protocol standards that must be implemented by a wide community of users with diverse equipment (Rudin, 2003).            

There has been recent work on formal protocol specification and verification. In addition to individual researchers, several national and international standards organizations have become active in this area.  These include the International Standard Organization (ISO) TC16/1 working group on Formal Definition Technique (FDT), the Consultative Committee for International Telegraphy and Telephony (CCITT) SG VII special report on question 39-System Description Techniques (SDT), and major protocol development projects by the National Bureau of Standards (NBS) and Defense Communication Engineering Center (DCEC) in the US. It is pertinent to note that good protocol specification methods or languages provide precise notations to facilitate implementation of standard and enhance technical quality. As their syntax and semantics are precisely specified, every word and symbol has a well-defined meaning and its use must follow exact rules. This makes standardized specifications unambiguous while improving intuitiveness, increasing consistency and making it possible to detect errors during standardization rather than implementation (ETSI, 2013). Thus to make protocol specification less complex, the use of Petri net as a modeling tool, graphical notation as well as a compact way to specify behaviour (protocol) has been employed. Most modeling languages have graphical notations, and these have good reasons. Models are used as a means to specify concept and ideas, and to communicate them between humans. Nearly everybody would use some kind of graphics to express his or her understanding of a system, even without using any explicit modeling languages. It does not need psychological research to state that graphics employing two dimensions allow for a better understanding of complex structures than one dimensional text. Since specification of systems and communication of models are the main application of Petri net in practice, understandability for human is among the most crucial quality criteria for modeling languages. Petri nets have nice graphical representation using only very few different types of elements, which is good basis for an easy understandability of a model and for the learnability of the language. These two criteria for modeling languages belong to the most important ones recognized in the “Guidelines of Modeling” (Desel and Juhas, 2001).          

Manufacturers who use precise and graphical languages report good results and considerable productivity gains. Their use within standardization increased along with the general increased acceptance of such techniques (ETSI, 2013). The most core issue of Petri nets is that they model behavioral aspects of distributed systems, i.e., systems with components that are locally separated and communicate which each other (Desel and Juhas, 2001). Since its invention by Carl Petri (Murata, 1989), Petri nets have been found useful in modeling systems with distributed states such as concurrency, synchronization, conflict(choice or decision) etc.

1.2     STATEMENT OF PROBLEM

• Traditional methods of informal narrative specifications and ad hoc validation have demonstrated their shortcomings as protocol bugs and incompatible implementations crop up. Problems of ambiguous and incomplete specifications are particularly severe for the ever growing number of protocol standards that must be implemented by a wide community of users with diverse equipment. Poor Protocol specification languages provide imprecise notations. This reduces implementation of standard and does not enhance technical quality.
• Poor Protocol specification languages makes standardized specifications ambiguous thereby degrading intuitiveness, decreasing consistency and making it impossible to detect errors during standardization rather than implementation.

Thus the project seek to answer the question

• Are there advantages of using Petri net over other protocol specification methods?

1.3              OBJECTIVES OF THE STUDY

          The main objective of this study is to use Colored Petri nets in connection establishment protocol specification.

          Specific objectives include:

• To investigate relevant literature on Communication Protocols and Petri nets.
• To investigate formal protocol specifications methods/techniques.
• To use Colored Petri net in modeling connection establishment protocol.
• To develop a piece of software for modeling connection establishment protocol using Java Programming.

1.4     SCOPE AND LIMITATIONS OF THE STUDY

This project work generally investigated Petri nets concept with the aim of adopting a type of Petri nets called Coloured Petri net (CPN). CPN was further applied to communication protocol i.e. its specification. Different types of Petri nets exist; such as high level, Timed Petri nets etc but they were not looked at. There are many areas of applications of Petri nets but this work centers only on communication protocol.

1.5     SIGNIFICANCE OF THE STUDY

The significance of the study includes the following:

• It exposes the use of Petri Nets to some applications in communication and network protocol specification.
• It demonstrates the feasibility of using Petri Net in Protocol specifications.
• It facilitates implementation of standard and enhances technical quality. This makes standardized specifications unambiguous while improving intuitiveness.
• Standard Organizations can use it as a springboard for specification of systems.

1.6     DEFINITIONS OF TERMS

Specification – a detailed description, especially one providing information needed to make, build or produce something.

Concurrency – taking place, existing or running parallel at the same time

Client – a computer program that request or obtains data from a program from another computer

Server – a computer that stores data that are accessed by other computers in a network

FDM – Frequency-division multiplexing has the frequency spectrum of a link divided up among the connections established across the link. Specifically the link dedicates a frequency band to each connection for the duration of the connection.

TDM – Time-division multiplexing: For a TDM link, time is divided into frames of fixed duration, and each frame is divided into a fixed number of time slots. When the network establishes a connection across a link, the network dedicates one time slot in every frame to this connection.