Autonomous routing algorithms for networks with wide-spread failures
We study end-to-end delay performance of different routing algorithms in networks with random failures. Specifically, we compare delay performances of differential backlog (DB) and shortest path (SP) routing algorithms and show that DB routing outperforms SP routing in terms of throughput when the n...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/59450 https://orcid.org/0000-0003-3577-6530 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826214392464670720 |
|---|---|
| author | Modiano, Eytan H. Khan, Wajahat F. Le, Long Bao |
| author2 | Massachusetts Institute of Technology. Communications and Networking Research Group |
| author_facet | Massachusetts Institute of Technology. Communications and Networking Research Group Modiano, Eytan H. Khan, Wajahat F. Le, Long Bao |
| author_sort | Modiano, Eytan H. |
| collection | MIT |
| description | We study end-to-end delay performance of different routing algorithms in networks with random failures. Specifically, we compare delay performances of differential backlog (DB) and shortest path (SP) routing algorithms and show that DB routing outperforms SP routing in terms of throughput when the network is heavily loaded and/or the failure rate is high while SP routing achieves better delay performance in the low load regime. Then, we investigate delay performance of a hybrid routing algorithm that combines principles of both SP and DB routing algorithms and show that it outperforms both of these routing algorithms. Finally, we demonstrate improvements in delay performance of DB routing through the use of a digital fountain approach which was originally proposed for multicast applications. In addition, our results show that there exists an optimal coding rate where digital fountain based DB routing achieves minimum end-to-end delay. To the best of our knowledge, this is the first work which investigates delay performance of DB routing and its enhanced versions for networks with link failures. |
| first_indexed | 2024-09-23T16:04:22Z |
| format | Article |
| id | mit-1721.1/59450 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:04:22Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/594502022-10-02T06:09:20Z Autonomous routing algorithms for networks with wide-spread failures Modiano, Eytan H. Khan, Wajahat F. Le, Long Bao Massachusetts Institute of Technology. Communications and Networking Research Group Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Modiano, Eytan H. Modiano, Eytan H. Khan, Wajahat F. Le, Long Bao Differential backlog routing digital fountain end-to-end delay shortest path routing throughput region We study end-to-end delay performance of different routing algorithms in networks with random failures. Specifically, we compare delay performances of differential backlog (DB) and shortest path (SP) routing algorithms and show that DB routing outperforms SP routing in terms of throughput when the network is heavily loaded and/or the failure rate is high while SP routing achieves better delay performance in the low load regime. Then, we investigate delay performance of a hybrid routing algorithm that combines principles of both SP and DB routing algorithms and show that it outperforms both of these routing algorithms. Finally, we demonstrate improvements in delay performance of DB routing through the use of a digital fountain approach which was originally proposed for multicast applications. In addition, our results show that there exists an optimal coding rate where digital fountain based DB routing achieves minimum end-to-end delay. To the best of our knowledge, this is the first work which investigates delay performance of DB routing and its enhanced versions for networks with link failures. United States. Army Research Office (Muri grant number W911NF-08-1-0238) United States. Defense Threat Reduction Agency (HDTRAl-07-l-0004) National Science Foundation (U.S.) (CNS-062678l) National Science Foundation (U.S.) (CNS-083096l) Natural Sciences and Engineering Research Council of Canada 2010-10-21T19:19:45Z 2010-10-21T19:19:45Z 2010-01 2009-10 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5238-5 INSPEC Accession Number: 11102030 http://hdl.handle.net/1721.1/59450 Wajahat Khan, Long Bao Le, and E. Modiano. “Autonomous routing algorithms for networks with wide-spread failures.” Military Communications Conference, 2009. MILCOM 2009. IEEE. 2009. 1-6. ©2010 Institute of Electrical and Electronics Engineers. https://orcid.org/0000-0003-3577-6530 https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/MILCOM.2009.5379792 IEEE Military Communications Conference, 2009. MILCOM 2009 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 | Differential backlog routing digital fountain end-to-end delay shortest path routing throughput region Modiano, Eytan H. Khan, Wajahat F. Le, Long Bao Autonomous routing algorithms for networks with wide-spread failures |
| title | Autonomous routing algorithms for networks with wide-spread failures |
| title_full | Autonomous routing algorithms for networks with wide-spread failures |
| title_fullStr | Autonomous routing algorithms for networks with wide-spread failures |
| title_full_unstemmed | Autonomous routing algorithms for networks with wide-spread failures |
| title_short | Autonomous routing algorithms for networks with wide-spread failures |
| title_sort | autonomous routing algorithms for networks with wide spread failures |
| topic | Differential backlog routing digital fountain end-to-end delay shortest path routing throughput region |
| url | http://hdl.handle.net/1721.1/59450 https://orcid.org/0000-0003-3577-6530 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT modianoeytanh autonomousroutingalgorithmsfornetworkswithwidespreadfailures AT khanwajahatf autonomousroutingalgorithmsfornetworkswithwidespreadfailures AT lelongbao autonomousroutingalgorithmsfornetworkswithwidespreadfailures |