Heuristic Algorithms for Real-Time Unsplittable Data Dissemination Problem

Abstract

In real-time communication, the timely delivery of the data transfer requests needs to be guaranteed. This work formally introduces the Real-Time Unsplittable Data Dissemination Problem (RTU/DDP), which is a generalization of the unsplittable flow problem (UFP). RTU/DDP problem is NP-hard. Therefore, heuristic approaches are required to acquire good solutions to the problem. The problem is divided into two sub-problems: path selection and request packing. Each of these sub-problems is formally defined and heuristic algorithms are proposed for both sub-problems. The performance of these algorithms is compared with a heuristic from the literature that can solve RTU/DDP, namely Full Path Heuristic (FPH). The results and discussions of the comparisons between the proposed heuristics and FPH are presented.