ESMP: Exploring Efficient and Stable Multicast on Multiple Communication Paths

Abstract

Modern communication networks may provide several heterogeneous links between the same pair of devices, including Wi-Fi, 5G, Bluetooth, and SparkLink. Existing multicast schemes often use simple-graph abstractions and therefore cannot distinguish these parallel links. We present ESMP, a multi-graph-based heuristic framework for efficient and stable multicast construction over heterogeneous parallel communication links. ESMP represents parallel channels as edges with delay and stability attributes. We show that an aggregate-edge-delay-constrained decision variant of the formulation is NP-hard. The framework includes six polynomial-time heuristics: delay-based DMA and DSMA, stability-based SMA and SDMA, and stability-delay-ratio-based RMA and MRMA. Each algorithm derives a metric-specific graph from the original multi-graph and constructs a tree according to its delay-stability preference. We also develop local adjustment strategies for vertex joins, vertex exits, and link dynamics. Experiments on connected synthetic multi-graphs reveal distinct metric preferences. Delay-oriented methods reduce delay, stability-oriented methods improve stability, and ratio-based methods provide stability-aware trade-offs at relatively low delay. In particular, RMA favors low delay, whereas MRMA uses pair-level average stability-delay information and shows comparatively favorable stability preservation and tree compactness in the evaluated scenarios. These findings characterize heuristic behavior in the evaluated synthetic settings and do not establish general optimality.