Two-Tier Load Balancing in OSPF Wireless Back-Hauls

High-speed wireless communication technology (e.g. WiMAX) makes it feasible and cost-effective to build wireless back-hauls for Internet access. Compared to wired counterparts, it is challenging to optimize the performance of wireless backhaul due to the dynamic nature of wireless channels. In this paper, we propose a two-tier optimization scheme for load balancing objective. We use linear programming techniques to find the optimal routing policy for load balancing of each source-destination traffic by setting an appropriate weight to each link. Since current OSPF routers only support discrete traffic splitting, we propose a greedy min-max congestion algorithm to find a shortest-path set in order to approximate the optimal routing policy within a certain bound. Due to the impact of dynamic channel conditions, we propose the second tier adaptation scheme which runs frequently enough to refine the routing policy to balance the overall traffic according to the channel condition. We conduct thorough theoretical analysis to show the correctness of our design and give the properties of our scheme. Our solution is also evaluated via simulations and the simulation results show that our work can effectively lower maximum congestion level of the network to a near-optimal value.