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

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

• tar zxvf ospf_wt_optimizer.tgz
• cd ospf_wt_optimizer
• export PATH=${PATH}:.
• make

How to?

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

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

   • topo is a generic topo file
   • tmdir is location of tms
   • will optimize over TMs in tmdir/fileTag*
   • for 1, ..., numTMs
   • output goes into outdir if present, else currentDirectory
   • outputfile(s) will be tagged
     • fileTag_d.weights for individual TMs
     • fileTag_d_d.weights for multiple TMs at the same time
     • fileTag_d_d.failweights for indiv, when also optimized over failures
   • use -m to yield a single weight-set over all TMs
   • use -v to simultaneously optimize over all single-link failures

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

   Generates traffic matrices of two kinds.
   • Generalized Gravity: The proportion of node x's traffic that goes towards another node y depends on the popularity of node y; the more popular nodes get more traffic. True in predicting transportation volumes and traffic. Use sum of capacities of edges incident on a node to measure popularity.
   • Bimodal: The traffic between two nodes is either "high" or "low"
   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

   • topo is a generic topo file
   • will create "howmany" tms in files "outdir"/gengrav_%d.m, "outdir"/bimodal_%d.m
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

   • topo is a generic topo file
   • tmdir is a name like directory
   • whichTM is a number say 1 to mean gengrav1 or bimodal1 in that directory
   • margin is a float >= 1.0 say 1.1, 2.0
   • howmany sample TMs to create off the base TM in that margin range?
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]

   • topo is a generic topo file
   • numLinksToFail is the # of links that simultaneously fail
   • howManySamples is the # of failure samples
   • output gets a file called "fail_%d", where %d is numLinksToFail

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.