A Distributed Algorithm for Throughput Optimal Routing in Overlay Networks
A Distributed Algorithm for Throughput Optimal Routing in Overlay Networks
复制标题
覆盖网络中吞吐量最优路由的分布式算法
DOI：
10.23919/ifipnetworking.2019.8816834
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
E. Modiano
中科院分区：
文献类型：
--
作者：
Anurag Rai;Rahul Singh;E. Modiano
我们解决的问题，在覆盖网络的最佳路由。通过在传统网络的顶部添加新的覆盖节点来构建覆盖网络。覆盖节点能够实现任何动态路由策略，然而，传统的TCP/IP具有固定的单路径路由方案，并使用简单的工作保存转发策略。此外，这些路由是预先确定的，并且对于覆盖网络是未知的。覆盖网络可以通过使用多个路由来增加传统网络的可实现的吞吐量，所述多个路由包括直接路由和通过其他覆盖节点的间接路由。我们开发了一个最佳的动态路由算法，这样的覆盖网络称为最佳覆盖路由策略（OORP）。OORP是使用经典的对偶次梯度下降法推导出来的，它可以以分布式的方式实现。我们表明，在算法中的对偶变量的替代品，可以使用的长度。然而，积压长度是未知的覆盖，所以我们提出了两个基于回归的计划，学习简化模型的积压在积压使用历史数据，并使用它们来估计积压长度在真实的时间。仿真结果表明，在不了解系统性能的情况下，该算法可以获得接近最优的性能。
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.