Toronto Networking Seminar


Organized by Department of Computer Science and
Department of Electrical and Computer Engineering, University of Toronto







Distributed CSMA/CA Algorithms for Achieving Maximum Throughput in Wireless Networks





R. Srikant


Department of Electrical and Computer Engineering


University of Illinois at Urbana-Champaign




Date: Thursday, April 9, 2009, 3pm

Location: BA 1130 



Abstract:




Recently, it has been shown that random access algorithms can achieve the
maximum possible throughput in wireless ad hoc networks. Central to these
results is a distributed randomized algorithm which selects schedules according
to a product-form distribution. The product-form distribution is achieved by
considering a continuous-time Markov model of an idealized algorithm under
which collisions cannot occur. We present an algorithm which achieves the same
product-form distribution in a discrete-time setting where collisions of data
packets are avoided through the exchange of control messages. However, the
control messages are allowed to collide as in today's protocols. In our
discrete-time model, each time slot consists of a few control mini-slots
followed by a data slot. We show that even one control mini-slot is sufficient
for our distributed scheduling algorithm to realize the same steady-state
distribution as in the continuous-time case. Under some assumptions, the
scheduling algorithm can be made throughput optimal by appropriately choosing
the parameters of the distributed algorithm as functions of the queue lengths.
Joint work with Jian Ni and Bo Tan.




Bio:



R. Srikant is with the University of Illinois at Urbana-Champaign, where he is
a Professor in the Department of Electrical and Computer Engineering and a
Research Professor in the Coordinated Science Lab. His research interests
include communication networks, stochastic processes, queueing theory,
information theory, control theory and game theory.




Host of the talk



Yashar Ganjali (yganjali@cs.toronto.edu)