Heuristic Algorithms for Real-Time Unsplittable Data Dissemination Problem
26th Annual International Symposium on Computer and Information Science, London, Canada, 26 - 28 September 2011, pp.43-49, (Full Text)
- Publication Type: Conference Paper / Full Text
- Doi Number: 10.1007/978-1-4471-2155-8_5
- City: London
- Country: Canada
- Page Numbers: pp.43-49
- Keywords: Real-time, Data dissemination, Unsplittable flow problem, Computer networks, Performance evaluation
- Anadolu University Affiliated: Yes
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.