creators_name: Kilby, Philip
creators_name: Lun, Desmond
creators_name: Nguyen, Giang
type: report
datestamp: 2010-02-16 16:10:24
lastmod: 2010-02-16 16:10:24
metadata_visibility: show
corp_creators: Farzad Safaei
title: Multipoint-to-multipoint network communication
ispublished: pub
subjects: telecom
full_text_status: public
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.
date: 2009
citation: Kilby, Philip and Lun, Desmond and Nguyen, Giang (2009) Multipoint-to-multipoint network communication. [Study Group Report]
document_url: http://www.maths-in-industry.org/miis/278/1/ictrmisg2009.pdf