ILP Formulation and Exact Solution of Multicast Routing with Fairness

Abstract

Fairness is critical in delay-sensitive group applications—multiplayer online games, live collaborative editing, and distributed interactive simulations—where every participant should receive each message within a bounded delay and with minimal timing differences between recipients. We study fairness-aware multicast routing under two parameters: the maximum end-to-end delay (Δ) and the inter-destination delay variation (δ). Although several heuristics address this NP-hard problem and exact integer linear programs (ILPs) exist for the minimum-cost multi-constrained case, exact methods that directly optimize inter-destination delay variation under bounded delay remain underexplored. We present flow-based ILP formulations that treat Δ and δ as either objectives or constraints. Their feasible solutions are partial spanning hierarchies, a class that contains partial spanning trees as a special case; consequently a hierarchy optimum is, by construction, at least as good as the best tree-constrained solution. On proven-optimal instances, hierarchy optima reduce inter-destination delay variation considerably relative to the best tree-constrained solution. A sensitivity analysis, a real-topology study on the Abilene backbone, and an exact-ILP scalability study quantify and corroborate these gains.