On self adaptive routing in dynamic environments - an evaluation and design using a simple, probabilistic scheme
On self adaptive routing in dynamic environments - an evaluation and design using a simple, probabilistic scheme
复制标题
关于动态环境中的自适应路由 - 使用简单的概率方案进行评估和设计
DOI：
10.1109/icnp.2004.1348074
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Haiyong Xie
中科院分区：
文献类型：
--
作者：
L. Qiu;Y. Yang;Yin Zhang;Haiyong Xie
近年来，在Internet和无线自组织网络中出现了自适应路由的新趋势。虽然以前有计算自适应路由（如自适应路由）的流量平衡的方法，但这些方法使用计算要求很高的算法，并且要求给出网络的精确分析模型。同时，如何设计一种自适应路由方案，在实际应用中保证收敛到流量均衡，仍然是一个有待解决的问题。本文提出了一种简单、高效的分布式概率路由方案，用于动态、现实环境中的自适应路由。通过分析和广泛的模拟，我们表明我们的方案可以非常快速地收敛到期望的流量均衡（用户最优或网络最优）。我们发现，在动态环境中，用户最优路由可以实现非常接近最优平均延迟，但这样的性能往往是以严重超载某些链路为代价的。为了避免链路过载，我们通过同时优化平均用户延迟和链路利用率来改进自适应路由。我们的评估表明，在优化双重目标之间存在权衡，但是对于典型的链路利用率需求，平均延迟的降低只是边际的。
Recently we have seen an emergent trend of self adaptive routing in both Internet and wireless ad hoc networks. Although there are previous methods for computing the traffic equilibria of self adaptive routing (e.g., selfish routing), these methods use computationally demanding algorithms and require that a precise analytical model of the network be given. Also, it remains an open question how to design an adaptive routing scheme which ensures convergence to traffic equilibria in practice. In this paper we propose a simple, efficient, distributed probabilistic routing scheme for self adaptive routing in dynamic, realistic environments. Using both analysis and extensive simulations, we show that our scheme can converge to the desired traffic equilibrium (either user-optimal or network-optimal) very quickly. We find that user-optimal routing can achieve very close to optimal average latency in dynamic environments, but such performance often comes at the cost of seriously overloading certain links. To avoid link overloads, we improve adaptive routing by optimizing average user latency and link utilization simultaneously. Our evaluation shows that there is a trade-off between optimizing dual objectives, but the degradation in average latency is only marginal for typical link utilization requirements.
DOI：
10.1145/781027.781053
发表时间：
2003-06
期刊：
--
影响因子：
--
作者：
Yin Zhang;M. Roughan;N. Duffield;A. Greenberg
通讯作者：
Yin Zhang;M. Roughan;N. Duffield;A. Greenberg