Measuring quality for routing problems

A lower bound for routing problems: the MCF

When we have an algorithm for a routing problem but no other algorithm for comparison, how do we know how well our algorithm is doing? Another way to deal with evaluation is lower bounding.

When we are looking at the weight-setting problem, we can only route the demands according to ECMP rules, which makes the problem hard. We are actually looking at special cases of Multi-Commodity Flow (MCF) routing, but restricted with ECMP rules. If we relax these ECMP constraints and allow any MCF to be used, then the problem becomes tractable.

Thus, we can compute an MCF optimal solution to our routing problem, and since it is a relaxation, its objective value (maximum utilization) will never be larger than the best solution that can be reached using only ECMP-constrained solutions. If the MCF objective is close enough to our algorithms’s objective, then we are assured that our algorithm has a good solution, since it is impossible to get below the MCF.

If the MCF objective is far below our algorithm’s, then we can say nothing about solution quality: the algorithm may have missed a better solution, or it might not be possible to get close to the MCF objective when we are constrained by ECMP rules.

Computing an MCF solution using Repetita

Making a program that computes MCF solutions is quite simple: once we have created an MCF instance, we can compute the lower bound by calling its computeMaxUtilization():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package be.ac.ucl.ingi.repetita.examples;

import java.io.IOException;

import be.ac.ucl.ingi.repetita.core.Demands;
import be.ac.ucl.ingi.repetita.core.Topology;
import be.ac.ucl.ingi.repetita.core.io.Parsing;
import be.ac.ucl.ingi.repetita.core.util.MCF;

public class ComputeMCF {
  public static void print_help() {
    System.out.println("Usage: ComputeMCF file.graph file.demands");
    System.exit(1);
  }
  
  public static void main(String[] args) throws IOException {
    if (args.length != 2) print_help();
    
    Topology topology = Parsing.parseTopology(args[0]);
    Demands demands = Parsing.parseDemands(args[1]);
    
    MCF mcfComputer = new MCF(topology, demands);
    double maxUtilization = mcfComputer.computeMaxUtilization();
    if (Math.abs(maxUtilization - 0.9) > 1e-3)
      System.out.printf("%s: Max utilization is %g\n", args[1], maxUtilization);
  }
}

MCF will not be affected by weights, except if a weight is equal to Topology.INFINITE_DISTANCE, which forbids the corresponding edge to be used.

Note that MCF will not work if some demand cannot be routed, for instance if source and destination are not connected.

The demands do not have to be static: a call to MCF::computeMaxUtilization will take into account the current state of the demands.

For instances up to 200 nodes, the underlying solver, Gurobi, is typically able to compute a solution under a few seconds.