Dynamic load balancing for WDM-based packet networks
Dynamic load balancing for WDM-based packet networks
复制标题
基于 WDM 的分组网络的动态负载平衡
DOI：
10.1109/infcom.2000.832276
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
E. Modiano
中科院分区：
文献类型：
--
作者：
A. Narula;E. Modiano
我们开发的WDM为基础的分组网络中，节点之间的平均流量是动态变化的负载平衡算法。在基于WDM的分组网络中，路由器使用波长（光路）彼此连接以形成逻辑网络拓扑。可以通过重新布置连接路由器的光路来重新配置该逻辑拓扑。我们的负载平衡算法的目标是通过重新配置逻辑拓扑结构，以最大限度地减少网络延迟。由于延迟成为无界的负载接近链路容量，延迟通常是由负载最重的链路。因此，我们的算法试图最大限度地减少最大链路负载。即使流量是静态的，推导出一个给定的流量模式的最佳逻辑拓扑是NP完全的。之前关于重新配置的工作提出了启发式算法来确定给定流量模式的“最佳”逻辑拓扑，并使用一系列重新配置步骤迁移到该拓扑。然而，当流量模式快速变化时，随着流量的每次变化重新配置整个网络可能会造成极大的破坏。在本文中，我们开发迭代重新配置算法的负载平衡，跟踪快速变化的交通模式。在每个重构步骤中，我们的算法只对网络拓扑结构进行很小的改变，从而最大限度地减少了对网络的破坏。我们研究了我们的算法的性能在几个动态的交通情况下，我们的算法表现接近最佳。
We develop load balancing algorithms for WDM-based packet networks in which the average traffic between nodes is dynamically changing. In WDM-based packet networks, routers are connected to each other using wavelengths (lightpaths) to form a logical network topology. This logical topology may be reconfigured by rearranging the lightpaths connecting the routers. The goal of our load balancing algorithms is to minimize network delay by reconfiguring the logical topology. Since delay becomes unbounded as the load approaches the link capacity, delay is usually dominated by the most heavily loaded link. Therefore, our algorithms attempt to minimize the maximum link load. Even when traffic is static, deriving the optimal logical topology for a given traffic pattern is known to be NP-complete. Previous work on reconfiguration proposed heuristic algorithms to determine the "best" logical topology for the given traffic pattern and migrated to that topology using a series of reconfiguration steps. However, when traffic patterns are changing rapidly, reconfiguring the full network with every change in the traffic may be extremely disruptive. In this paper, we develop iterative reconfiguration algorithms for load balancing that track rapid changes in the traffic pattern. At each reconfiguration step, our algorithms make only a small change to the network topology, hence, minimizing the disruption to the network. We study the performance of our algorithms under several dynamic traffic scenarios and show that our algorithms perform near optimally.