We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region, and origin-destination node pairs correspond to pairs of points in that region. The objective is to define a routing policy that assigns a continuous path to each origin-destination pair while minimizing the traffic, or load, passing through any single point. While the average load is minimized by straight-line routing, such a routing policy distributes the load non-uniformly, resulting in higher load near the center of the region. We consider one-turn rectilinear routing policies that divert traffic away from regions of heavier load, resulting in up to a 33% reduction in the maximum load while simultaneously increasing the path lengths by an average of less than 28%. Our policies are simple to implement, being both local and oblivious. We provide a lower bound that shows that no one-turn rectilinear routing policy can reduce the maximum load by more than 39% and we give a polynomial-time procedure for approximating the optimal randomized policy.

, , , , ,
Journal of Interconnection Networks
School of Computer Science

Durocher, S. (Stephane), Kranakis, E, Krizanc, D. (Danny), & Narayanan, L. (Lata). (2009). Balancing traffic load using one-turn rectilinear routing. Journal of Interconnection Networks, 10(1-2), 93–120.