5.4 Computational efficiency

In the previous section, we argue using $O$-notation about the the computational and storage efficiency of ETAQA-M/G/1. Here, we present further numerical evidence that ETAQA-M/G/1 is more efficient than other methods. For our comparisons, we use the classic Ramaswami's formula and the fast FFT implementation of Ramaswami's formula, the most efficient known algorithm for solving M/G/1-type processes [58]. We used Meini's implementation^5.1for the cyclic reduction for the computation of ${\mathbf{G}}$ that is required in all three solution algorithms. We also used Meini's code for the fast FFT implementation of Ramaswami's formula that was made available to us via a personal communication [57]. We implemented the ETAQA-M/G/1 method and the classic Ramaswami's formula in C. All experiments were conducted on a 450 MHz Sun Enterprise 420R server with 4 GB memory.

The chain we selected for our experiments represents a general BMAP/M/1 queue. Recall that in practice, it is not possible to store an infinite number of $\widehat{{\mathbf{F}}}^{(i)}$ and ${\mathbf{F}}^{(i)}$ matrices, $1 < i < \infty$. One should stop storing when all entries of $\widehat{{\mathbf{F}}}^{(i)}$ and ${\mathbf{F}}^{(i)}$ for $i > p$ are below a sufficient threshold (i.e., very close to zero in a practical implementation) [47]. As illustrated in the previous section, computation time does depend on the size (i.e., parameters $m$ and $n$) and the number (of stored) matrices (i.e., parameter $p$) that define the infinitesimal generator ${\mathbf{Q}}$. Finally, one last parameter that affects computation time is the number $s$ of vector probabilities that should be computed so as the normalization condition $\sum_{i=1}^s \mbox{\boldmath {$\pi$}}^{(i)} = 1.0$ is reached (again, within a sufficient numerical threshold).

Figure 5.3: Execution time (in seconds) for ETAQA-M/G/1, the classic implementation of Ramaswami's formula, and the fast FFT implementation of Ramaswami's formula. The figure illustrates timings for the computation of the stationary probability vector (left column) and the computation of the queue length (right column).

In our experiments, we vary the parameters $n$, $p$, and $s$ (for the case of BMAP/M/1 queue $m=n$) and provide timing results for the computation of the stationary vector $\mbox{\boldmath {$\pi$}}$ using the classic Ramaswami implementation and the fast FFT implementation, and the computation of $(\mbox{\boldmath {$\pi$}}^{(0)},\mbox{\boldmath {$\pi$}}^{(1)},\mbox{\boldmath {$\pi$}}^{(*)})$ using ETAQA-M/G/1. We also provide timings for the computation of the queue length for both methods. Results are presented in Figure 5.3.

The first experiment, considers a BMAP/M/1 queue with $n=16$ and $p=32$, a relatively small case. The timings^5.2 of the three algorithms are shown as a function of $s$. Figure 5.3(a) depicts the computation cost of the probability vector and Figure 5.3(b) illustrates the computation cost the queue length. Observe that the $y$-axis is in log-scale. Note that the value of $s$ does affect the execution time of both Matrix-analytic approaches, but does not have any affect on ETAQA-M/G/1. As expected, for the computation of the stationary vector, the FFT implementation is superior to the classic Ramaswami formula, behavior that persists when we increase $p$ and $n$ (see Figures 5.3(c) and 5.3(e)). ETAQA-M/G/1 consistently outperforms the other two methods, plus its performance is insensitive to $s$ (see figures Figures 5.3(a), 5.3(c) and 5.3(e)).

Figures 5.3(b), 5.3(d) and 5.3(f) illustrate the computation cost of the queue length for the three algorithms for various values of $n$, $p$, and $s$. Note that the two implementations of Ramaswami's formula have the same cost, since the same classic formula is used for the computation of queue length: first weight appropriately and then sum the probability vector which is already computed. The figures further confirm that the cost of solving a small system of linear equations that ETAQA-M/G/1 requires for the computations of queue length is in many cases preferable to the classic methods. If this linear system increases and $s$ is also small, then the classic methods may offer better performance.