Distributed Random Access Algorithm: Scheduling and Congesion Control
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61979 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1811078684918939648 |
|---|---|
| author | Jiang, Libin Shah, Devavrat Shin, Jinwoo Walrand, Jean |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jiang, Libin Shah, Devavrat Shin, Jinwoo Walrand, Jean |
| author_sort | Jiang, Libin |
| collection | MIT |
| description | 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 ε [epsilon]-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 |
| first_indexed | 2024-09-23T11:03:51Z |
| format | Article |
| id | mit-1721.1/61979 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:03:51Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/619792022-10-01T00:53:43Z Distributed Random Access Algorithm: Scheduling and Congesion Control Jiang, Libin Shah, Devavrat Shin, Jinwoo Walrand, Jean Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Shah, Devavrat Shah, Devavrat Shin, Jinwoo 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 ε [epsilon]-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 National Science Foundation (U.S.) (Project CNS 0546590) (Project TF 0728554) United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program United States. Air Force Office of Scientific Research. Complex Networks Project United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (Grant BAA 07-036.18) 2011-03-25T22:04:37Z 2011-03-25T22:04:37Z 2010-11 2010-05 Article http://purl.org/eprint/type/JournalArticle 0018-9448 INSPEC Accession Number: 11661298 http://hdl.handle.net/1721.1/61979 Walrand, J., with Libin Jiang and Shah, D., Jinwoo Shin. “Distributed Random Access Algorithm: Scheduling and Congestion Control.” Information Theory, IEEE Transactions On 56.12 (2010) : 6182-6207. Copyright © 2010, IEEE https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1109/TIT.2010.2081490 IEEE transactions on information theory Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Jiang, Libin Shah, Devavrat Shin, Jinwoo Walrand, Jean Distributed Random Access Algorithm: Scheduling and Congesion Control |
| title | Distributed Random Access Algorithm: Scheduling and Congesion Control |
| title_full | Distributed Random Access Algorithm: Scheduling and Congesion Control |
| title_fullStr | Distributed Random Access Algorithm: Scheduling and Congesion Control |
| title_full_unstemmed | Distributed Random Access Algorithm: Scheduling and Congesion Control |
| title_short | Distributed Random Access Algorithm: Scheduling and Congesion Control |
| title_sort | distributed random access algorithm scheduling and congesion control |
| url | http://hdl.handle.net/1721.1/61979 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT jianglibin distributedrandomaccessalgorithmschedulingandcongesioncontrol AT shahdevavrat distributedrandomaccessalgorithmschedulingandcongesioncontrol AT shinjinwoo distributedrandomaccessalgorithmschedulingandcongesioncontrol AT walrandjean distributedrandomaccessalgorithmschedulingandcongesioncontrol |