College of Engineering, All Events

Back to Listing

ISE Seminar - Stability Conditions for a Discrete-time Decentralised Medium Access Algorithm

Event Type
Industrial & Enterprise Systems Engineering
103 Transportation Building
Nov 10, 2017   10:00 am  
Vsevolod Shneer, Heriot-Watt University, Edinburgh, UK
Originating Calendar
ISE Seminar Calendar


We consider a stochastic queueing system modelling the behaviour of a wireless network with nodes employing a discrete-time version of the standard decentralised medium access algorithm. The system is unsaturated -- each node receives an exogenous flow of packets at the rate λ packets per time slot. Each packet takes one slot to transmit, but neighboring nodes cannot transmit simultaneously. The algorithm we study is standard in that a node with empty queue does not compete for medium access and the access procedure by a node does not depend on its queue length, as long as it is non-zero. Two system topologies are considered, with nodes arranged in a circle and in a line. We prove that, for either topology, the system is stochastically stable under condition λ<2/5. This result is intuitive for the circle topology as the throughput each node receives in a saturated system (with infinite queues) is equal to the so-called parking constant, which is larger than 2/5. (The latter fact, however, does not help to prove our result.) The result is not intuitive at all for the line topology as in a saturated system some nodes receive a throughput lower than 2/5. This is a joint work with Sasha Stolyar (UIUC).


Professor Shneer received his PhD from Heriot-Watt University, then worked as a postdoc at EURANDOM, the Netherlands and EPFL, Switzerland. He then joined Heriot-Watt University as an Assistant Professor in 2010 and promoted to Associate Professor in 2015.

link for robots only