Edge-based traffic engineering for OSPF networks

Jun Wang, Yaling Yang, Li Xiao, Klara Nahrstedt

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)605-625
Number of pages21
JournalComputer Networks
Issue number4
StatePublished - Jul 15 2005


  • Edge-based
  • Mathematical programming/optimization
  • OSPF
  • Traffic engineering
  • Traffic set

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Edge-based traffic engineering for OSPF networks'. Together they form a unique fingerprint.

Cite this