Heuristic Algorithms for Real-Time Unsplittable Data Dissemination Problem

ATANAK M. M., Dogan A.

26th Annual International Symposium on Computer and Information Science, London, Canada, 26 - 28 September 2011, pp.43-49 identifier

  • 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.