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.
展开▼
