•  
  •  
 

Turkish Journal of Electrical Engineering and Computer Sciences

DOI

10.3906/elk-1508-263

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 self-adaptive 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.

Keywords

Algorithm, computer network, expected polynomial time, multi-constrained routing, pareto frontier, pareto optimisation, quality of service, routing algorithm

First Page

1211

Last Page

1222

Download

Share

COinS