The MIIS Eprints Archive

Multipoint-to-multipoint network communication

Kilby, Philip and Lun, Desmond and Nguyen, Giang (2009) Multipoint-to-multipoint network communication. [Study Group Report]



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.

Item Type:Study Group Report
Problem Sectors:Information and communication technology
Study Groups:Australian and New Zealand Mathematics in Industry Study Group > 26th MISG [Wollongong 27/1/2009 - 31/1/2009]
Australian and New Zealand Mathematics in Industry Study Group > 26th MISG [Wollongong 27/1/2009 - 31/1/2009]
Company Name:ICT Research Institute
ID Code:278
Deposited By: Dr Kamel Bentahar
Deposited On:16 Feb 2010 16:10
Last Modified:29 May 2015 19:53

Repository Staff Only: item control page