Loop-Free Backpressure Routing Using Link-Reversal Algorithms
The backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand in data networks, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free backpressure routing policies that forward packets...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/97572 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0002-7034-0110 |
| _version_ | 1826200491194843136 |
|---|---|
| author | Rai, Anurag Li, Chih-ping Paschos, Georgios Modiano, Eytan H. |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Rai, Anurag Li, Chih-ping Paschos, Georgios Modiano, Eytan H. |
| author_sort | Rai, Anurag |
| collection | MIT |
| description | The backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand in data networks, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand.
For a network with a single commodity, we show that a DAG that supports a given traffic demand can be found after a finite number of iterations of the link-reversal process. We use this to develop a joint link-reversal and backpressure routing policy, called the loop free backpressure (LFBP) algorithm. This algorithm forwards packets on the DAG, while the DAG is dynamically updated based on the growth of the queue backlogs. We show by simulations that such a DAG-based policy improves the delay over the classical backpressure routing policy. We also propose a multicommodity version of the LFBP algorithm, and via simulation we show that its delay performance is better than that of backpressure. |
| first_indexed | 2024-09-23T11:37:17Z |
| format | Article |
| id | mit-1721.1/97572 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:37:17Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/975722022-10-01T04:48:31Z Loop-Free Backpressure Routing Using Link-Reversal Algorithms Rai, Anurag Li, Chih-ping Paschos, Georgios Modiano, Eytan H. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Modiano, Eytan H. Rai, Anurag Modiano, Eytan H. The backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand in data networks, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand. For a network with a single commodity, we show that a DAG that supports a given traffic demand can be found after a finite number of iterations of the link-reversal process. We use this to develop a joint link-reversal and backpressure routing policy, called the loop free backpressure (LFBP) algorithm. This algorithm forwards packets on the DAG, while the DAG is dynamically updated based on the growth of the queue backlogs. We show by simulations that such a DAG-based policy improves the delay over the classical backpressure routing policy. We also propose a multicommodity version of the LFBP algorithm, and via simulation we show that its delay performance is better than that of backpressure. National Science Foundation (U.S.) (Grant CNS-1116209) United States. Office of Naval Research (Grant N00014-12-1-0064) 2015-06-29T18:55:33Z 2015-06-29T18:55:33Z 2015-06 Article http://purl.org/eprint/type/ConferencePaper 9781450334891 http://hdl.handle.net/1721.1/97572 Anurag Rai, Chih-ping Li, Georgios Paschos, and Eytan Modiano. 2015. Loop-Free Backpressure Routing Using Link-Reversal Algorithms. In Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '15). ACM, New York, NY, USA, 87-96. https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0002-7034-0110 en_US http://dx.doi.org/10.1145/2746285.2746304 Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '15) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) Prof. Modiano via Barbara Williams |
| spellingShingle | Rai, Anurag Li, Chih-ping Paschos, Georgios Modiano, Eytan H. Loop-Free Backpressure Routing Using Link-Reversal Algorithms |
| title | Loop-Free Backpressure Routing Using Link-Reversal Algorithms |
| title_full | Loop-Free Backpressure Routing Using Link-Reversal Algorithms |
| title_fullStr | Loop-Free Backpressure Routing Using Link-Reversal Algorithms |
| title_full_unstemmed | Loop-Free Backpressure Routing Using Link-Reversal Algorithms |
| title_short | Loop-Free Backpressure Routing Using Link-Reversal Algorithms |
| title_sort | loop free backpressure routing using link reversal algorithms |
| url | http://hdl.handle.net/1721.1/97572 https://orcid.org/0000-0001-8238-8130 https://orcid.org/0000-0002-7034-0110 |
| work_keys_str_mv | AT raianurag loopfreebackpressureroutingusinglinkreversalalgorithms AT lichihping loopfreebackpressureroutingusinglinkreversalalgorithms AT paschosgeorgios loopfreebackpressureroutingusinglinkreversalalgorithms AT modianoeytanh loopfreebackpressureroutingusinglinkreversalalgorithms |