Edge-based traffic engineering for OSPF networks

This paper proposes and evaluates a novel, edge-based approach, which we call the k-set Traffic Engineering (TE) method, to perform traffic engineering in OSPF networks by partitioning traffic into uneven k-traffic sets. The traffic partitioning and splitting takes place only at network edges, leaving the core simple. We theoretically prove that if k is large enough, the k-set TE method achieves the general optimal traffic engineering where full-mesh overlaying and arbitrary traffic splitting, such as in MPLS, have to be used. We give an upper bound of the smallest k that achieves such a general optimum. In addition, we provide a constant worst case performance bound if k is smaller than the optimal k. Finding the optimal traffic splitting and routing for a given k is NP-hard. Therefore, we present a heuristic algorithm to handle the problem. The performance of the k-set TE method together with the proposed heuristic algorithm is evaluated by simulation. The results confirm that a fairly small k (2 or 4) can achieve good near-optimal traffic engineering. Overall, the k-set TE method provides a simple and efficient solution to achieve load balancing in OSPF networks. It follows the "smart edge, simple core" design rule of the Internet. It is also able to keep "the same path for the same flow," which is desirable and beneficial to TCP applications.