Методи аналізу та синтезу моделей телекомунікаційних систем на основі функціональних сіток Петрі

Ключевые слова: телекоммуникационная система, телекоммуникационный протокол, функциональная сеть Петри, клан, анализ, синтез.

Zaitsev D.A. Methods of analyses and synthesis of telecommunication systems models on the base of functional Petri nets. - The manuscript.

The dissertation is competing for the degree of Dr. Sci. Tech. on a speciality 05.12.02 - telecommunication systems and networks. - Odessa National Telecommunication Academy named after A.S.Popov, Odessa, 2006.

Petri net models of real-life telecommunication protocols have a large scale but all known algebraic methods of Petri net analysis possess an exponential computation complexity. There is a problem of large-scale Petri nets analysis. To solve this problem the basis of functional Petri nets theory has been developed. Functional net has strongest restrictions on incidental arcs of contact places: input places have only output arcs and output places have only input acrs. Functional subnet is introduced in symmetric way. It was proved that: set of minimal functional subnet defines a partition of transitions' set; each functional subnet of a given Petri net may be obtained as composition (union) of finite number of minimal functional subnets; each contact place has no more than one incidental input functional subnet and not more than one output functional subnet; the net of functional subnets is a marked graph. For the representation of decomposition the net of functional subnets and graphs of decomposition (directed and undirected) were used. Two ways of decomposition were suggested: via logical equations solution and via ah-hoc algorithm of linear complexity. The software for decomposition named Deborah was developed.

The transmission function of functional net was studied for the class of timed Petri nets with multiply arcs. On the base of state equation the representation of transmission function was obtained. The transmission function was written as an expression in the special algebra, which contains arithmetic, logic operations and operation of timed delay. Weak functional equivalence of nets was introduced and studied with respect to special types of input sequences and moments of observation. The equivalent transformations of nets were implemented on the base of algebraic transformations of transmission function formulae. It allows the reduction of large-scale Petri nets. The task of continuous logic function given by choice table synthesis was solved. Special concepts of constituents of maximum and minimum were introduced and applied.

It was shown that the majority of tasks of Petri nets analyses may be reduced to solution of linear Diophantine equations in nonnegative integer numbers. The methods for speed-up of solution of an arbitrary linear algebraic system of equation under ring with sign were developed. The concept of functional subnet was generalized for linear systems on the base of clan concept. Clan was introduced as a subset of equations united with a transitive closure of closeness relation consisting in possessing a variable with a coefficient of the same sign. Clans define the specific block structure of system's matrix and provide the system's solving via composition of clans' general solutions. Speed-up of computation is guaranteed in the case the system is decomposed in more than one clan and at the usage of basic solution method with complexity larger than cube.

For the additional speed-up in the case the number of contact variables is greater than the maximal size of clans the sequential way of decomposition was proposed. The speed-up is obtained at the expense of solution of a series of composition systems with lesser dimension. For implementation of sequential composition the undirected graph of decomposition was considered. Two ways of sequential composition were studied: via contracting subgraphs and via contracting of edges. The corresponding optimization task was named an optimal collapse of weighted graph. For solution of edge collapse task by the method of branches and bounds the estimations of upper and lower bound for the width of collapse were obtained. A heuristic algorithm of optimal collapse on the base of one-step strategy of maximal weight edge contracting was introduced and statistically grounded. The software for compositional solution of systems named Adriana was developed. As an auxiliary task the formal grounding and detailed estimation of computation complexity for Toudic method were obtained.

The specification languages of telecommunication protocols were studied. It was proposed to use Petri net as a universal language of protocols specification. To control the level of models abstraction it was proposed to represent either the whole message or headers' fields by separate tokens. The models of protocols BGP and TCP were constructed and verified using composition of functional subnets.

With the growth of protocols number and their complexity the construction of Petri net model on a given standard specification of a protocol becomes most laborious. To solve this problem the usage of intermediate language of Hoare's communicating sequential processes (CSP) was suggested. Then the task of Petri net synthesis on a given CSP formulae was solved. This approach was illustrated on the example of Petri net synthesis for electronic commerce protocol IOTP. The verification of protocol was implemented via developed compositional methods.

The model-driven development of telecommunication systems becomes a prospective direction. It was suggested to compose colored Petri net models of telecommunication systems and networks via the composition of components' models represented with functional subnets and subnets with contact places. The library of components for switched Ethernet, MPLS and Bluetooth was constructed. For express estimation of functional characteristics the method of measuring fragments was introduced. With such fragments the tasks of switched Ethernet response time, MPLS effectiveness and Bluetooth address space usage effectiveness estimation were solved.

For analysis of infinite Petri nets with regular structure the method of compositional calculation of invariants in parametric form was developed. The method was illustrated on the example of Ethernet with bus topology verification. The invariance of the protocol was proved for an arbitrary number of workstations on the bus.

Keywords: telecommunication system, telecommunication protocol, functional Petri net, clan, analysis, synthesis.

Размещено на Allbest.ru