Stability of the Max-Weight Protocol in Adversarial Wireless Networks

Details Stability of the Max-Weight Protocol in Adversarial Wireless Networks Stability of the Max-Weight Protocol in Adversarial Wireless Networks

2012-01-15

arxiv.org/abs/1201.3066v1

Computer Science

Networking and Internet Architecture

Accepted by IEEE INFOCOM 2012

Scientific paper

In this paper we consider the Max-Weight protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process. Such an environment appears frequently in many practical wireless scenarios when the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper we prove that even in the above adversarial setting, the Max-Weight protocol keeps the queues in the network stable (i.e. keeps the queue sizes bounded) whenever this is feasible by some routing and scheduling algorithm. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Our proof holds for any arbitrary interference relationships among edges. We also prove the stability of $\ep$-approximate Max-Weight under the adversarial model. We conclude the paper with a discussion of queue sizes in the adversarial model as well as a set of simulation results.

Affiliated with

Also associated with

No associations

Rating

Stability of the Max-Weight Protocol in Adversarial Wireless Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stability of the Max-Weight Protocol in Adversarial Wireless Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability of the Max-Weight Protocol in Adversarial Wireless Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159090