Typical routing algorithms use a single criterion, such as hop count or link weight, to calculate paths. As the requirement of flexible routing arises, there are circumstances where multiple criteria are needed for routing. Though there are proposed solutions to the multi-criteria optimal path selection problem for quality-of-service routing, they usually combine all criteria into a single path optimization metric a priori. However, this approach is not feasible in scenarios where the path consumers' weightings of criteria is not known at compute time. Such circumstances require finding all the Pareto-optimal paths, i.e., all the paths that are not dominated by other paths. In this paper, we present the algorithmic foundations for efficiently computing Pareto-optimal paths. We present ParetoBFS, a variant of a breadth-first search that uses branch-and-bound techniques to find all the Pareto-optimal paths while effectively limiting the potentially very large search space. We present several sampling techniques to further increase the speed of the search while degrading the quality of the results only marginally. Our simulation results show that existing multi-criteria combinatorial optimization approaches can only search a small fraction of all the Pareto-optimal paths while ParetoBFS can obtain the whole path set in shorter time. We also present results from an implementation of ParetoBFS on a software-defined network prototype.
展开▼
