CTHp1-5: Optimal Routing in the Worst-Case-Error Metric

This paper considers the problem of finding the path with minimum (zero) worst possible number of errors in a network with V nodes where (1) some nodes are capable of correcting up to a maximum number of x_max errors, (2) the nodes are connected by q-ary Symmetric channels a parametrized by their bit error ratios (BER) p_i. We introduce (1) the BER and worst-case error (WCE) metrics and (2) an algebra that allows us to compute the path BER length from its edge lengths, and use them to measure network QoS. The WCE and BER metrics can be used with a generalized Dijkstra´s algorithm to compute the path of minimum WCE length. Finally, we present an algorithm that solves the above problem in the worst-case time complexity of O(V³).