A distributed algorithm for throughput optimal routing in overlay networks
We address the problem of optimal routing in overlay networks. An overlay network is constructed by adding new overlay nodes on top of a legacy network. The overlay nodes are capable of implementing any dynamic routing policy, however, the legacy underlay has a fixed, single path routing scheme and...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020
|
| Online Access: | https://hdl.handle.net/1721.1/126219 |
| _version_ | 1826199121274339328 |
|---|---|
| author | Rai, Anurag Singh, Rahul Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Rai, Anurag Singh, Rahul Modiano, Eytan H |
| author_sort | Rai, Anurag |
| collection | MIT |
| description | We address the problem of optimal routing in overlay networks. An overlay network is constructed by adding new overlay nodes on top of a legacy network. The overlay nodes are capable of implementing any dynamic routing policy, however, the legacy underlay has a fixed, single path routing scheme and uses a simple work-conserving forwarding policy. Moreover, the underlay routes are pre-determined and unknown to the overlay network. The overlay network can increase the achievable throughput of the legacy network by using multiple routes, which consist of direct routes and indirect routes through other overlay nodes. We develop an optimal dynamic routing algorithm for such overlay networks called the Optimal Overlay Routing Policy (OORP). OORP is derived using the classical dual subgradient descent method, and it can be implemented in a distributed manner. We show that the queue-lengths can be used as a substitute for the dual variables in the algorithm. However, the underlay queue-lengths are unknown to the overlay, so we propose two regression based schemes that learn simplified models of the backlog in the underlay using historical data and use them to estimate the queue-lengths in real time. Simulation results show that near-optimal performance can be achieved without any knowledge of the underlay. |
| first_indexed | 2024-09-23T11:15:04Z |
| format | Article |
| id | mit-1721.1/126219 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:15:04Z |
| publishDate | 2020 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1262192022-09-27T18:10:15Z A distributed algorithm for throughput optimal routing in overlay networks Rai, Anurag Singh, Rahul Modiano, Eytan H Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Aeronautics and Astronautics We address the problem of optimal routing in overlay networks. An overlay network is constructed by adding new overlay nodes on top of a legacy network. The overlay nodes are capable of implementing any dynamic routing policy, however, the legacy underlay has a fixed, single path routing scheme and uses a simple work-conserving forwarding policy. Moreover, the underlay routes are pre-determined and unknown to the overlay network. The overlay network can increase the achievable throughput of the legacy network by using multiple routes, which consist of direct routes and indirect routes through other overlay nodes. We develop an optimal dynamic routing algorithm for such overlay networks called the Optimal Overlay Routing Policy (OORP). OORP is derived using the classical dual subgradient descent method, and it can be implemented in a distributed manner. We show that the queue-lengths can be used as a substitute for the dual variables in the algorithm. However, the underlay queue-lengths are unknown to the overlay, so we propose two regression based schemes that learn simplified models of the backlog in the underlay using historical data and use them to estimate the queue-lengths in real time. Simulation results show that near-optimal performance can be achieved without any knowledge of the underlay. 2020-07-16T14:00:56Z 2020-07-16T14:00:56Z 2019-05 2019-10-30T16:55:34Z Article http://purl.org/eprint/type/ConferencePaper 978-3-903176-16-4 https://hdl.handle.net/1721.1/126219 Rai, Anurag, Rahul Singh and Eytan Modiano. “A distributed algorithm for throughput optimal routing in overlay networks.” 2019 IFIP Networking Conference (IFIP Networking), Warsaw, Poland, 20-22 May 2019, IEEE © 2019 The Author(s) en 10.23919/IFIPNetworking.2019.8816834 2019 IFIP Networking Conference (IFIP Networking) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE MIT web domain |
| spellingShingle | Rai, Anurag Singh, Rahul Modiano, Eytan H A distributed algorithm for throughput optimal routing in overlay networks |
| title | A distributed algorithm for throughput optimal routing in overlay networks |
| title_full | A distributed algorithm for throughput optimal routing in overlay networks |
| title_fullStr | A distributed algorithm for throughput optimal routing in overlay networks |
| title_full_unstemmed | A distributed algorithm for throughput optimal routing in overlay networks |
| title_short | A distributed algorithm for throughput optimal routing in overlay networks |
| title_sort | distributed algorithm for throughput optimal routing in overlay networks |
| url | https://hdl.handle.net/1721.1/126219 |
| work_keys_str_mv | AT raianurag adistributedalgorithmforthroughputoptimalroutinginoverlaynetworks AT singhrahul adistributedalgorithmforthroughputoptimalroutinginoverlaynetworks AT modianoeytanh adistributedalgorithmforthroughputoptimalroutinginoverlaynetworks AT raianurag distributedalgorithmforthroughputoptimalroutinginoverlaynetworks AT singhrahul distributedalgorithmforthroughputoptimalroutinginoverlaynetworks AT modianoeytanh distributedalgorithmforthroughputoptimalroutinginoverlaynetworks |