Multipoint-to-multipoint network communication

Abstract

We have formulated an exact ILP model for the problem of communicating on a virtual network. While this ILP model was successful in solving small problems, it is not recommended to handle larger instances, due to the fact that the number of variables in the model grows exponentially as the graph size grows. However, this ILP model can provide a benchmark for heuristic algorithms developed for this problem.

We have also described a heuristic approach, and explored several variants of the algorithm. We found a solution that seems to perform well with reasonable computation time. The heuristic is able to find solutions that respect the degree constraints, but show a small number of violations of the desired time constraints.
Tests on small problems show that heuristic is not always able to find feasible solutions, even though the exact method has shown they exist. It would be interesting in the future to look at whether insights gained by looking at exact solutions can be used to improve the heuristic.