On direct routing in the Valiant Load-Balancing architecture

It is very hard to design a network with performance guarantees, partly because it is hard to estimate the future traffic matrix. With no knowledge of the traffic matrix, one can use the Valiant Load-balancing (VLB) architecture which can support any traffic satisfying the node capacity constraints. To interconnect N nodes of capacity r, the VLB architecture requires a logical full mesh of link capacity c = (2r)/(N). Uniform load-balancing can guarantee throughput, but is not necessary if the traffic matrix is known, in which case the amount of load-balancing can be reduced. In this paper we study adaptive load-balancing in two cases: when only local traffic information is known to a node, and when the network traffic matrix is known. We give linear programming formulations to maximize directly routed traffic in both cases, so as to reduce the average hop count of packets. In the case when the traffic matrix is known, we show that direct routing is not always feasible with c = (2r)/(N), but c = (3r)/(N) is sufficient.