Markov chain models for all-optical shared memory packet switches

In this thesis, Markov chains are developed for accurate analysis of the all-optical (or just optical) shared-memory packet switch architecture. Shared-memory packet switching architectures have been analyzed before because of their benefit in minimizing the amount of memory needed by the packet switch. Minimizing optical memory is desirable because of its great expense and the complexity that is associated with integrating large amounts of memory with the switch. Not all shared-memory architectures are suitable for optical implementation. Accurate analysis of shared-memory architectures is also difficult to achieve because of correlations between packet destination addresses in the shared-memory. Markov chains have been previously used for analysis, but have been applied to the nonoptical shared-memory architectures and, because of tractability concerns, were based on approximations that yielded inaccurate results. Analysis of the optical shared-memory architectures also made approximations that were unrealistic for optical implementation. Simulations of the optical shared-memory packet switch yielded accurate packet loss results, but only in regions where the packet loss is relatively high. Therefore, this research makes the following original contributions: (1) development of a Markov chain that accurately models the optical shared-memory architecture, called a full Markov chain (FMC); (2) a computationally feasible construction method for determining a tractable Markov chain, called a reduced Markov chain (RMC), which is capable of providing accurate results in any packet loss region; (3) equations to determine exactly the number of states of both Markov chains, and hence the exact level of state reduction; (4) proofs that the RMC yields exact results like the FMC; and (5) an extension of the RMC to model a variation of the optical shared-memory switch architecture, called channel grouping.