TAMCRA: a tunable accuracy multiple constraints routing algorithm

Routing with more than one additive constraint is known to be an NP-complete problem, and hence considered as intractable. We present a new QoS routing algorithm, called the Tunable Accuracy Multiple Constraints Routing Algorithm (TAMCRA), which can solve multiple constraints problems with a finite but small probability of missing a path that satisfies all constraints while the probability of missing such a path is tunable with a single parameter k. We demonstrate that this algorithm scales very well as the size of the graph increases or as the number of constraints increases. (C) 2000 Elsevier Science B.V. All rights reserved.