VLS4: Valiant Load Balanced Segment Routing

With the rapid rise in the number of diverse Internetbased applications, it is to be expected that network traffic patterns will vary widely. Significant traffic fluctuations from what is predicted may require corresponding routing adaptations to avoid congestion. Valiant Load Balancing (VLB), or equivalently two-phase routing, is a scheme that can ensure congestion-free network routing despite incomplete knowledge of the current traffic matrix. By design, VLB uses only aggregate ingress and egress traffic information (i.e., it only needs the row and column sums of the traffic matrix and not the actual point-to-point traffic). The advent of segment routing provides a new mechanism for implementing VLB but a straightforward mapping of VLB to segment routed paths does not give good performance. We propose a new scheme, VLS4, that can efficiently implement VLB using segment routing. We also develop fast guaranteed approximation algorithms for determining the appropriate segment routing parameters. We experimentally compare VLS4 to VLB and show that the throughput performance is almost the same despite VLS4 being much more easy to implement.