Markov chains and decision processes for congestion avoidance and power control

Balakrishna Prabhu

INRIA Sophia Antipolis


This thesis is based on some applications of Markov chains and decision processes for congestion and power control. First, we study the behaviour of the window size of an MIMD congestion control algorithm when subject to different loss processes. We show that the logarithm of the window size follows an additive recursive equation, which can be modelled as a Markov chain. We also show that the throughput is inversely proportional to the packet loss probability. Next, we study a continuous time model for the window size of a general increase and instantaneous decrease congestion control algorithm. We provide conditions under which two congestion control algorithms have related window size behaviour. Next, we model the ratio of the instantaneous rates of two competing MIMD sessions. For heterogeneous sources, we show that the fairness index can be improved by introducing rate-dependent losses at an intensity which is greater than a threshold. We also study the bandwidth sharing between AIMD and MIMD sources under synchronous losses. Next, we model the instantaneous and the average queue sizes of a RED enabled queue as a non-homogeneous Quasi-Birth-Death process. In the limit when the averaging parameter goes to zero, we use singular perturbation find the joint distribution of the average and the instantaneousqueue sizes. A problem related to energy-delay tradeoff in a wireless device is studied next. In each slot, the device has to decide whether to transmit data or to leave the battery idle in order to increase the battery lifetime. Finally, through simulations we study the effect of two threshold based channel switching policies in UMTS.

[Balakrishna Prabhu]
[INRIA Sophia Antipolis]