OSPF Traffic Engineering

ISPs want to engineer how traffic flows in their core networks. One technique to do this is to

  1. pick a weight for each directed link in the network
  2. use OSPF to compute the shortest-weight paths between every pair of nodes and,
  3. when multiple paths have the same "shortest weight" divide traffic evenly between the paths
It is widely believed that major ISPs, such as AT&T use OSPF Traffic Engineering. The last component is called equal-cost multi-path and is implemented widely in Cisco and Juniper routers.

Problem

Given a traffic matrix, how to pick the "optimal weights", that allow the network to achieve some objective. Example objectives may be to minimize the maximum utilization, or to minimize the sum of costs on links for some "sane" cost function.

Prior Work

Fortz and Thorup et. al., prove that computing the optimal weights is NP-hard for many objective functions. So, they have a taboo-search algorithm that searches for a good set of weights. Unfortunately, their implementation of this search algorithm is not available to public.

So, OspfOpt

OspfOpt is an open-source "best-guess" implementation of the search algorithm described in Fortz and Thorup's paper. At the basic level, given an ISP topology and a demand matrix, OspfOpt identifies a "good" set of weights. This means that if one were to use these weights, run equal-cost OSPF paths, routing traffic as per the demand matrix would lead to low "cost", or low maximum utilization.

Ofcourse, what if the weights have been optimized for one traffic matrix, but the actual traffic is governed by a different traffic matrix. Also what if some links in the network fail. In a couple of follow-up papers, Fortz and Thorup extend the above scheme to identify a set of weights that simultaneously optimizes over multiple traffic matrices and over all possible single link failures. OspfOpt also has a "best-guess" implementation of these published algorithms.

Download

OspfOpt

Install

You should have executables getOptOSPFWeights, getTMs, getTMsInMargin, sampleFailuresOfTopo.

How to?

  1. getOptOSPFWeights. Inputs -- Topology, Traffic Matrices~(One or More) Outputs -- Optimized Weights

    Usage: ./getOptOSPFWeights [-m -v] topo tmdir fileTag numTMs [outdir]

  2. getTMs Input -- Topology, Output -- Traffic Matrices

    Generates traffic matrices of two kinds. Scaling traffic to match utilizations: Given the above generative models, it is hard to guess what link utilizations caused by a TM. The code scales all the values in a TM uniformly.

    Usage: ./getTMs [-g -b] topo outdir howmany

  3. getTMsInMargin: Given a base traffic matrix, generates TMs that are off from the base by "margin". : Each entry in the TM increases or decreases with prob 0.5 : The degree of perturbation is a multiplicative factor chosen uniformly in the ranges [1, margin]

    Usage: ./getTMsInMargin [-g-b] topo tmdir whichTM margin howmany

  4. sampleFailuresOfTopo: Given a topology and a certain number of links that have to simultaneously fail. It samples the links uniformly at random and yields failure instances. For each failure instance, we run floydwarshall to make sure that the graph is not disconnected after the failure.

    Usage: ./sampleFailuresOfTopo topo numLinksToFail howManySamples [outdir]

Formats

Topology looks like NUM-NODES: 5 LINK: 0 1 10000 1.0 LINK: 0 2 2500 1.0 LINK: 0 3 10000 1.0 LINK: 1 4 10000 1.0 LINK: 2 3 10000 1.0 LINK: 3 4 2500 1.0

The first line is the number of nodes in the graph. Followed by lines that specify bi-directional links between nodes. For e.g., the first link line above means there is an edge from node 0 to node 1 with capacity 10000 units and delay 1ms.

Traffic Demands is a simple 2d array of flow from rowindex to columnindex

Demands =
0.0000 324.0880 518.5408 583.3584 324.0880 ;
720.5704 0.0000 640.5070 720.5704 400.3169 ;
603.1127 335.0626 0.0000 603.1127 335.0626 ;
428.8248 238.2360 381.1776 0.0000 238.2360 ;
391.0642 217.2579 347.6126 391.0642 0.0000

Link Weights is also a 2d array, negative weight means no edge exists between the pair 0 9 10 20 -1
18 0 -1 -1 13
15 -1 0 18 -1
10 -1 19 0 2
-1 10 -1 18 0

Sample Topologies

The directory sample_topos contains ISP topologies inferred by Rocketfuel

Credits

Srikanth Kandula

Legal et. al.

Original code written by Srikanth Kandula. Research prototype, absolutely no warranty.