Some recent developments in the theory of DEDS and its applications
by Wang Junjie
M.Phil. Electrical and Electronic Engineering
vi, 83 leaves : ill. ; 30 cm
In recent years, the theory of discrete event dynamic systems (DEDS) has been extensively explored and widely applied to communications, computer networks, and manufacturing systems, etc....[ Read more ]
In recent years, the theory of discrete event dynamic systems (DEDS) has been extensively explored and widely applied to communications, computer networks, and manufacturing systems, etc.
In this study, we will first focus on the theory of Markov decision processes (MDP) and its application to the communication networks that is a typical DEDS. There are several difficulties inherent in the traditional MDP theory to be resolved before it can be successfully applied to real world systems. First, the state space in real systems is always very large, thereby leading to a prohibitive computational cost. Second, the dynamic system characteristics add to the complexity, that is, the system parameters are usually unavailable or time-varying, which even makes the computation-based approach more formidable, if not impossible.
In this research, we develop some techniques to tackle the above difficulties, special concerns are given to the issue of reducing computational complexity. Different from the conventional computation-based approaches that involve large recursive equations or huge matrix inverse, we will investigate the single-sample-path-based potential theory, where the "potentials" can be estimated during the system evolution. Motivated by the newly emerging control schemes, we extend the potential theory to the system where the traditional approaches cannot be directed applied. Specifically, we first investigate the Markovian systems with transition-dependent cost functions. We also propose a new control infrastructure in distributed controlled Markov chain. To deal with the unmanageable state space encountered in practical systems, we propose the technique of "state aggre-gation" and apply it in the cost computation in routing applications.
Finally, we discuss the topic of performance analysis of nonblocking ATM switches. We apply two methods, namely power series algorithm and rational approximation, to the packet delay analysis. This approach offers an appealing alternative to the traditional simulation-based approaches in terms of its computational complexity.