ITERATIVE APPROACH TO OPTIMIZING CONVERGENCE ROUTING PRIORITIES

This paper shows how to optimize the routing decisions in a nondetermi nistic routing algorithm called convergence routing in which routes ma y change depending on the traffic conditions. The routing algorithm gu arantees a loss-free delivery of data packets from bursty sources, and a deterministic bound on the route length in arbitrary topology netwo rks. The routing decisions are based on assigning routing priorities t o the links such that a packet is forwarded to the highest priority li nk which is not blocked. Routing priorities are assigned using a local -greedy metric which minimizes the distance (number of hops) to the de stination. This work shows that routing decisions using a local-greedy metric are not optimal, and the performance of the algorithm can be i mproved substantially by using new measures. Thus, various look-ahead metrics which take into account the potential gain on the other switch ing nodes toward the destination of a packet are suggested. The contri butions of this work are: 1) a new analytical model to capture the beh avior of a switching node; 2) an iterative optimization technique to s et routing priorities according to various look-ahead measures; and 3) heuristics to ensure the stability of the routing priorities. The opt imization objective is to maximize throughput by minimizing the maximu m total flow carried on a link in the network under static traffic mod el. The performance is studied computationally on various networks and traffic matrices. It is shown that up to a 50% performance increase c an be obtained by optimizing the routing priorities.