We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region and origin and destination nodes 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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-540-79228-4-41
Citation
Durocher, S. (Stephane), Kranakis, E, Krizanc, D. (Danny), & Narayanan, L. (Lata). (2008). Balancing traffic load using one-turn rectilinear routing. doi:10.1007/978-3-540-79228-4-41