Verification of hypercube communication structures via parametric Petri nets 1
- PDF / 346,123 Bytes
- 10 Pages / 595.205 x 793.701 pts Page_size
- 90 Downloads / 162 Views
VERIFICATION OF HYPERCUBE COMMUNICATION STRUCTURES VIA PARAMETRIC PETRI NETS1 D. A. Zaitseva† and T. R. Shmelevaa‡
UDC 621.39, 004.7
A model of a hypercube communication structure of arbitrary size with an arbitrary number of dimensions is constructed in the form of a parametric Petri net. A technique for calculating linear invariants of parametric Petri nets is developed that allows one to analyze information transmission processes in such a hypercube. The structure of complicated deadlocks caused by a path (loop) of blockings and the isolation of devices is investigated. In real-life networks, the described deadlocks lead to a considerable decrease in performance and can be induced by some ill-intentioned traffic. Keywords: communication structure, hypercube, router, parametric Petri net, linear invariant, deadlock. INTRODUCTION Since the number of communication devices and the topology of a net considerably vary in real telecommunication networks, a methodology is required that can be applied to an arbitrary number of devices that form some arbitrary structure. A. Marsan [1] began the investigation of Petri nets constructed by repeating a base component for estimation of the performance of CSMA/CD common-bus networks. He constructed a linear structure, but any methodology of analysis of an arbitrary number of components was not presented. In [2], a parametric composition of functional Petri nets [3] is applied to the analysis of linear structures of interacting devices. A simpler approach [4] is applied to treelike structures with a view to verifying protocols of switched Ethernet networks. The objective of this article is the generalization of the approach from [4] to communication structures of a hypercube of an arbitrary size with an arbitrary number of dimensions. In [4], a typical model of an Ethernet switch with the store-and-forward technology of buffering frames is constructed that is used to compose treelike structures. Since commutation (routing) tables are not presented in the model [4], the same model can describe switches and routers. In the present article, its modification is used as a generalized model of a communication device for the composition of a communication hypercube structure (CHCS). A distinction consists of the number of ports and distribution of ports among faces of a hypercube for the subsequent composition of communication structures of the hypercube. A line of further investigations is the generalization of the obtained results to arbitrary structures and modeling of devices with the cut-through mode of frame transmission between ports. An application domain of these results consists of computations on grids. The obtained results have been preliminarily presented at the seminar UKPEW2008 [5]. To analyze properties of parametric Petri nets, linear invariants [6] are used. In compliance with [7, 8], an ideal model of a telecommunication system must be a bounded, live, and conservative Petri net. However, t-invariants do not allow one to prove the liveness of such a net. Therefore,
Data Loading...
