Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Congestion Control
Medium Access
Performance Guarantee
Random Access
Carrier Sense Multiple Access
Subscribe
Academic
Publications
Distributed Random Access Algorithm: Scheduling and Congestion Control
Distributed Random Access Algorithm: Scheduling and Congestion Control,10.1109/TIT.2010.2081490,IEEE Transactions on Information Theory,Libin Jiang,De
Edit
Distributed Random Access Algorithm: Scheduling and Congestion Control
(
Citations: 9
)
BibTex

RIS

RefWorks
Download
Libin Jiang
,
Devavrat Shah
,
Jinwoo Shin
,
Jean Walrand
This paper provides proofs of the rate stability, Harris recurrence, and εoptimality of
carrier sense multiple access
(CSMA) algorithms where the
random access
(or backoff) parameter of each node is adjusted dynamically. These algorithms require only local information and they 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, in terms of the rates, of the packet flows at 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 εoptimality in terms of the utilities of the allocated rates. Both algorithms are iterative and we study two versions of each of them. In the first version, both operate with strictly local information but have relatively weaker performance guarantees; under the second version, both provide stronger performance guarantees by utilizing the additional information of the number of nodes in the network.
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 56, no. 12, pp. 61826207, 2010
DOI:
10.1109/TIT.2010.2081490
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(7)
...Inspired by and similar to [22], [
46
], we also adopt the standard methods of stochastic approximation [47], [48] and Markov chain [49], [50]...
...The difference between our proof and [22], [
46
] is that, our proof studies the saddle points of Lagrangian function, while [22], [46] studies the optimal dual solutions directly...
...The difference between our proof and [22], [46] is that, our proof studies the saddle points of Lagrangian function, while [22], [
46
] studies the optimal dual solutions directly...
...Therefore, in general, our proof techniques can be applied to primaldual resource allocation algorithms, while proof techniques in [22], [
46
] can be applied only to dual resource allocation algorithms...
Ziyu Shao
,
et al.
CrossLayer Optimization for Wireless Networks With Deterministic Chan...
...This result has spurred interest among researchers in searching for other distributed throughputoptimal scheduling algorithms [7], [
8
]...
Qiao Li
,
et al.
Distributed Throughputoptimal Scheduling in Ad Hoc Wireless Networks
...The decentralized queuelength based scheduling algorithm in [14] and its variants have been shown to be throughputoptimal in [
12
], [13], [19]...
...We consider a Lyapunov function of the form, for .I n order to establish positive Harris recurrence, for any such that , we use multistep9 Lyapunov and Foster’s drift criteria to establish positive recurrence of a set of the form , for some . From the assumption on the arrival processes, it follows that is a closed petite (small) set (for definition and details see [
12
], [21])...
...The proofs given in this Appendix are generalizations of proofs in [
12
] and [13] to multistate framework...
Jubin Jose
,
et al.
Distributed Rate Allocation for Wireless Networks
...In the same spirit, several powerful algorithms have been devised for adapting the transmission lengths based on backlog information, and been shown to guarantee maximum stability [
12
], [20]...
Niek Bouman
,
et al.
Backlogbased random access in wireless networks: Fluid limits and del...
...Several authors have proposed clever backlogbased algorithms for adapting activation rates that achieve stability whenever feasible to do so at all [
6
, 7, 8, 13, 14]...
...As stated in the introduction, there are simple backlogbased algorithms for adapting activation rates that achieve stability whenever feasible at all [
6
, 7, 8, 13, 14]...
Peter M. van de Ven
,
et al.
Equalizing throughputs in randomaccess networks
References
(54)
Ultimate instability of exponential backoff protocol for acknowledgmentbased transmission control of random access communication channels
(
Citations: 80
)
David J. Aldous
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 33, no. 2, pp. 219223, 1987
Highspeed switch scheduling for localarea networks
(
Citations: 621
)
Thomas E. Anderson
,
Susan S. Owicki
,
James B. Saxe
,
Charles P. Thacker
Journal:
ACM Transactions on Computer Systems  TOCS
, vol. 11, no. 4, pp. 319352, 1993
Stochastic approximation with 'controlled Markov' noise
(
Citations: 8
)
Vivek S. Borkar
Journal:
Systems & Control Letters  SYST CONTROL LETT
, vol. 55, no. 2, pp. 139145, 2006
Convex Optimization
(
Citations: 6681
)
Stephen P. Boyd
,
Lieven Vandenberghe
Published in 2004.
Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures
(
Citations: 320
)
Mung Chiang
,
Steven H. Low
,
A. Robert Calderbank
,
John C. Doyle
Journal:
Proceedings of The IEEE  PIEEE
, vol. 95, no. 1, pp. 255312, 2007
Sort by:
Citations
(9)
CrossLayer Optimization for Wireless Networks With Deterministic Channel Models
(
Citations: 1
)
Ziyu Shao
,
Minghua Chen
,
A. Salman Avestimehr
,
ShuoYen Robert Li
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 57, no. 9, pp. 58405862, 2011
Distributed Throughputoptimal Scheduling in Ad Hoc Wireless Networks
(
Citations: 1
)
Qiao Li
,
Rohit Negi
Journal:
Computing Research Repository  CORR
, vol. abs/1102.1, pp. 15, 2011
Approaching ThroughputOptimality in Distributed CSMA Scheduling Algorithms With Collisions
Libin Jiang
,
Jean Walrand
Journal:
IEEE/ACM Transactions on Networking  TON
, vol. 19, no. 3, pp. 816829, 2011
Distributed Rate Allocation for Wireless Networks
Jubin Jose
,
Sriram Vishwanath
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 57, no. 10, pp. 65396554, 2011
Backlogbased random access in wireless networks: Fluid limits and delay issues
Niek Bouman
,
Sem Borst
,
Johan van Leeuwaarden
,
Alexandre Proutiere
Journal:
Performance Evaluation  PE
, 2011