Cost of not arbitrarily splitting in routing
Yingjie Bi, Ao Tang · 2017
This paper studies routing performance loss due to traffic split ratio granularity constraints. For any given fineness of traffic splitting capability, we provide upper bounds on the loss of performance. Based on tight convex relaxation, we further develop an efficient approximation algorithm to compute a good routing solution that satisfies given constraints on traffic splitting. The results can be useful for network operators to trade-off between attainable performance and implementation overhead. Some of the mathematical techniques developed here can be of independent interest for studying other similar nonconvex optimization problems.