Heuristic Algorithms for Real-Time Unsplittable Data Dissemination Problem

ATANAK M. M., Dogan A.

26th Annual International Symposium on Computer and Information Science, London, Kanada, 26 - 28 Eylül 2011, ss.43-49 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1007/978-1-4471-2155-8_5
  • Basıldığı Şehir: London
  • Basıldığı Ülke: Kanada
  • Sayfa Sayıları: ss.43-49
  • Anahtar Kelimeler: Real-time, Data dissemination, Unsplittable flow problem, Computer networks, Performance evaluation
  • Anadolu Üniversitesi Adresli: Evet

Özet

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.