Computer Science – Information Theory
Scientific paper
2009-07-07
Computer Science
Information Theory
Scientific paper
This paper provides proofs of the rate stability, Harris recurrence, and epsilon-optimality of CSMA algorithms where the backoff parameter of each node is based on its backlog. These algorithms require only local information and are easy to implement. The setup is a network of wireless nodes with a fixed conflict graph that identifies pairs of nodes whose simultaneous transmissions conflict. The paper studies two algorithms. The first algorithm schedules transmissions to keep up with given arrival rates of packets. The second algorithm controls the arrivals in addition to the scheduling and attempts to maximize the sum of the utilities of the flows of packets at the different nodes. For the first algorithm, the paper proves rate stability for strictly feasible arrival rates and also Harris recurrence of the queues. For the second algorithm, the paper proves the epsilon-optimality. Both algorithms operate with strictly local information in the case of decreasing step sizes, and operate with the additional information of the number of nodes in the network in the case of constant step size.
Jiang Libin
Shah Devavrat
Shin Jinwoo
Walrand Jean
No associations
LandOfFree
Distributed Random Access Algorithm: Scheduling and Congesion Control 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 Distributed Random Access Algorithm: Scheduling and Congesion Control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Random Access Algorithm: Scheduling and Congesion Control will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-356526