Reduced Base Model Construction Methods for Stochastic Activity Networks

William H. Sanders, John F. Meyer

Research output: Contribution to journalArticlepeer-review

Abstract

Computer-aided modeling has become an accepted technique for predicting the performance and dependability of computer-communication networks. Many model formalisms have been proposed for this purpose, and have achieved varying degrees of success. One particular model type, stochastic Petri nets, has received considerable attention during the last ten years. Several classes of models of this type now exist and, as evidenced by their use in specific evaluation studies, they are capable of representing the kind of complex behavior exhibited by computer-communication networks. However, a number of problems remain open, particularly those associated with the evaluation of large-scale systems. Specifically, the issue here is the size and complexity of the stochastic process, derived from the underlying net model, which serves as a “base model” for subsequent solution of the measures in question. If this base model is constructed by standard means, e.g., it is identified with the marking behavior of the net, traditional methods of solution quickly become intractable for large systems, limiting their application to systems of only moderate complexity. This problem is addressed in the context of a particular class of stochastic Petri nets, stochastic activity networks (SAN's), by developing base model construction methods that account for symmetries in SAN structure and are tailored to the variable (e.g., response time, time to failure, etc.) in question. We find that such a technique can yield dramatic reductions in state-space size while preserving stochastic properties required for practical means of solution. Moreover, unlike state aggregation methods that rely on explicit knowledge the more detailed the state space, this technique permits direct construction of a reduced base model, thus avoiding size limitations associated with more traditional approaches to model simplification. The presentation includes both the theory required to establish the technique's validity and an illustration of its effectiveness in the evaluation of a CSMA/CD computer network.

Original languageEnglish (US)
Pages (from-to)25-36
Number of pages12
JournalIEEE Journal on Selected Areas in Communications
Volume9
Issue number1
DOIs
StatePublished - Jan 1991
Externally publishedYes

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Reduced Base Model Construction Methods for Stochastic Activity Networks'. Together they form a unique fingerprint.

Cite this