Selective Randomized Load Balancing and Mesh Networks with Changing Demands

We consider the problem of building cost-effective network architectures, which are robust to dynamic changes in demand patterns, and are thus highly suitable for emerging services such as virtual private networks (VPNs) or distributed storage and computing. Applying previous research on randomized load balancing and VPN-Tree network design, we explore ways to embed demand-oblivious routing strategies within a static circuit-switched network. In particular, we benchmark randomized load balancing against traditional circuit-switched networks as well as packet-switched networks. Our empirical analysis uses three representative carrier networks to account for the cost relations of different types of switching, routing, and transport equipment needed to implement each architecture. We demonstrate the trade-offs between the studied network architectures in terms of deployment cost, resource utilization, and demand blocking probabilities. We see that a blend of dual-hop hub routing with randomized load balancing yields an oblivious strategy that combines the advantages of the two approaches. In particular, the studied networks exhibit several nodes which act almost as effectively as the optimal hub. Load balancing across the selected subset achieves near-optimal usage of resources yet alleviates the single point of failure present in hub routing.