Maximum size of the pareto cost sets for multi-constrained optimal routing
Yükleniyor...
Dosyalar
Tarih
2017
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Turkish Journal of Electrical Engineering and Computer Sciences
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Abstract: Routing under multiple independent constrains in point-to-point networks has been studied for over 10 years. Its NP-hardness keeps pushing researchers to study approximate algorithms and heuristics, and many results have been published in these years. To the best of our knowledge, the nature of its average case has been explored only for the selfadaptive multiple constraints routing algorithm (SAMCRA), which is an algorithm about multiple constraints routing. In this paper, we simplify SAMCRA into a format that is convenient for our average case analysis. This variant algorithm gives optimal solutions also for very large dimensional networks such as with more than 1000 nodes. Although it runs in exponential time in the worst case, we prove that its average case time complexity is bounded by a polynomial function of the number of nodes in the network. Lastly, we give empirical results that align with our theoretical work.
Açıklama
Anahtar Kelimeler
Algorithm, computer network, expected polynomial time, multi-constrained routing, pareto frontier, pareto optimisation, quality of service, routing algorithm
Kaynak
Turkish Journal of Electrical Engineering and Computer Sciences
