An Optimal MILP Formulation for the Delay-and Delay Variation-Bounded Multicast Tree Problem

Abstract

Multicast communications mean providing transmission of common messages from one source to all destinations. The multicast end-to-end delay problem explores an upper bound on the end-to-end delay from a source to each destination. It implies messages must be sent to their destinations within a strict time limit lest they be declared invalid. On the other hand, the multicast delay variation problem studies how to avoid the situation where a message fails to arrive at each destination at the same time. This paper addresses the problem of minimizing multicast delay variation under multicast end-to-end delay constraint. This problem has been proven to be NP-complete. Many heuristic algorithms have been designed for it. However, these heuristic algorithms can only generate suboptimal solutions. In this paper, we propose a mixed-integer linear programming (MILP) formulation to yield optimal solutions for this difficult problem. Computer simulations testif that compared with a known high-performance heuristic algorithm, our MILP formulation can yield solutions with smaller multicast delay variations under different multicast end-to-end delay constraints.