eprintid: 110
rev_number: 4
eprint_status: archive
userid: 5
dir: disk0/00/00/01/10
datestamp: 2007-06-19
lastmod: 2015-05-29 19:47:30
status_changed: 2009-04-08 16:54:17
type: report
metadata_visibility: show
item_issues_count: 0
creators_name: Allwright, David
creators_name: Dellar, Paul
contributors_name: Briggs, Keith
contributors_name: Gravesen, Jens
contributors_name: Van Lent, Jan
contributors_name: Scheichl, Rob
contributors_name: Zyskin, Maxim
title: Sensitivity of Markov chains for wireless
protocols
ispublished: pub
subjects: telecom
studygroups: esgi56
companyname: BT
full_text_status: public
abstract: Network communication protocols such as the IEEE 802.11 wireless protocol are currently best modelled as Markov chains. In these situations we have some protocol parameters $\alpha$, and a transition matrix $P(\alpha)$ from which we can compute the steady state (equilibrium) distribution $z(\alpha)$ and hence final desired quantities $q(\alpha)$, which might be for example the throughput of the protocol. Typically the chain will have thousands of states, and a particular example of interest is the Bianchi chain defined later. Generally we want to optimise $q$, perhaps subject to some constraints that also depend on the Markov chain. To do this efficiently we need the gradient of $q$ with respect to $\alpha$, and therefore need the gradient of $z$ and other properties of the chain with respect to $\alpha$. The matrix formulas available for this involve the so-called fundamental matrix, but are there approximate gradients available which are faster and still sufficiently accurate? In some cases BT would like to do the whole calculation in computer algebra, and get a series expansion of the equilibrium $z$ with respect to a parameter in $P$. In addition to the steady state $z$, the same questions arise for the mixing time and the mean hitting times. Two qualitative features that were brought to the Study Group’s attention were:

    * the transition matrix $P$ is large, but sparse.
    * the systems of linear equations to be solved are generally singular and need some additional normalisation condition, such as is provided by using the fundamental matrix. 

We also note a third highly important property regarding applications of numerical linear algebra:

    * the transition matrix $P$ is asymmetric. 

A realistic dimension for the matrix $P$ in the Bianchi model described below is 8064×8064, but on average there are only a few nonzero entries per column. Merely storing such a large matrix in dense form would require nearly 0.5GBytes using 64-bit floating point numbers, and computing its LU factorisation takes around 80 seconds on a modern microprocessor. It is thus highly desirable to employ specialised algorithms for sparse matrices. These algorithms are generally divided between those only applicable to symmetric matrices, the most prominent being the conjugate-gradient (CG) algorithm for solving linear equations, and those applicable to general matrices. A similar division is present in the literature on numerical eigenvalue problems.
problem_statement: Many wireless network protocols lead to Markov chain models with a transition matrix $P(\alpha)$ depending on some parameters $\alpha$. From this the steady state distribution $z(\alpha)$ can be computed, and from this the final desired quantities $q(\alpha)$, which might be for example the throughput of the protocol. To optimise $q$ efficiently we wish to have its gradient with respect to $\alpha$. There are formulas for $\mathrm{d}z/\mathrm{d}\alpha$ in terms of $(I − P)#$ but what are the best numerical techniques for obtaining the derivatives, and are they stable ?

Can we also obtain the derivatives of the mixing time and mean hitting times $H$ ?

The Study Group showed that in general the techniques of sparse linear algebra and preconditioning should be used for calculating $z$, $H$ and their derivatives, and sparse eigenvalue software for mixing times, rather than any numerical computation of $(I −P)#$. For a particular example of interest (the Bianchi chain) these methods were applied and shown to be very efficient, and the same can be expected for any chain with a similar “escalator” structure.
date: 2007-04-17
date_type: published
pages: 31
citation:   Allwright, David and Dellar, Paul  (2007) Sensitivity of Markov chains for wireless
protocols.  [Study Group Report]     
document_url: http://miis.maths.ox.ac.uk/miis/110/1/BT-ProtocolReport.pdf