Multi-link-speed network topology design

Abstract

We consider the problem of selecting a link topology and sizing the link given a point to point traffic matrix and a cost matrix. Different speed links are permitted in the topology. We present an algorithm for the solution to this problem and compare its performance, both in terms of running time and the quality of the networks produced, with an algorithm which only considers a single speed link. We show that the new algorithm is a sigdicant improvement, reducing cost by as much as 6% while increasing running time by only a constant factor.