Cycle Avoidance in Integer Programming for Media Streams Planning
| Authors | |
|---|---|
| Year of publication | 2011 |
| Type | Appeared in Conference without Proceedings |
| MU Faculty or unit | |
| Citation | |
| Description | Remote virtual collaboration has high transmission demands these days. There are applications in, e. g., film industry or telemedicine, which transmit multiple data streams with bandwidth close to available link capacities in m:n schemes. Maximum interactivity requirements render low transmission latencies more valuable than low congestion of network links, which is frequent optimization criterion in multicast tree construction. IP multicast is also not suitable for its low availability in networks and has to be substituted with application-level data distributors. The Media Streams Planning Problem (MSPP) is a problem of placement of several data distribution trees in the network, one for each data source. Data streams of collaborative applications are routed along these streams from their roots (data producers) through internal nodes (distributor applications) to leaves (consumers). A solution of the problem has to respect link capacities while minimizing overall transmission latency. The solution also has to be found within seconds to maintain interactive behaviour of the collaborative systems. Our aim is to find a method with the fastest solving response in order to allow to solve as large inputs as possible within the given limit. Original solver of the MSPP employed a non-linear constraint programming (CP) model, solving only medium-sized topologies quickly enough. In previous work on the MSPP, we linearized the CP formulation and proposed binary integer linear programming (ILP) solver, which improved performance for most of the common input types representing applications in remote teaching, videoconferencing, or more specialized ones. Later, we have identified that the most severe negative influence on the solver performance comes from original cycle avoidance constraints. We analyzed several ILP formulations based on cycle avoidance methods for the travelling salesman problem, namely Miller-Tucker-Zemlin and subtour ones. We proposed modified solution strategy, which postpones their application and applies them only when they are needed. We have also proposed to replace the cycle avoidance constraints by a network flows formulation. This method has performed the best of all analyzed methods. |
| Related projects: |