ISPs want to engineer how traffic flows in their core networks. One technique to do this is to
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.
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.
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.
getOptOSPFWeights. Inputs -- Topology, Traffic Matrices~(One or More) Outputs -- Optimized Weights
Usage: ./getOptOSPFWeights [-m -v] topo tmdir fileTag numTMs [outdir]
getTMs Input -- Topology, Output -- Traffic Matrices
Generates traffic matrices of two kinds.Usage: ./getTMs [-g -b] topo outdir howmany
Usage: ./getTMsInMargin [-g-b] topo tmdir whichTM margin howmany
Usage: ./sampleFailuresOfTopo topo numLinksToFail howManySamples [outdir]
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
The directory sample_topos contains ISP topologies inferred by Rocketfuel
Original code written by Srikanth Kandula. Research prototype, absolutely no warranty.