Iterative Approach to Optimize Convergence Routing Priorities

In convergence routing successive packets of the same session are routed towards their destinations, but not necessarily on the same path (i.e., it is a dynamic routing technique). More specifically, at every intermediate switching node a packet can be forwarded towards its destination over one or more out-going links. The routing decision, over which link to forward the packet, is based on a simple metric, which ensures that each packet will converge to or reach its destination. When there are multiple routing choices the simplest routing strategy is local-greedy, namely, to minimize the distance to the destination as much as possible at every intermediate node. In this work we show that the local-greedy strategy is not necessarily the best one. We develop an iterative optimization technique which sets routing priorities and takes into account the potential gain on other switching nodes along the route. The optimization objective is to maximize throughput by minimizing the maximum total flow on a link in the network under uniform traffic model. The flow values are computed by formulating the convergence routing as a multicommodity flow problem, and solving it as an instance of linear programming by Simplex algorithm. Flow assignments over the links are input to a new analytical model to update the routing probabilities for the next iteration of the optimization algorithm. The stability of the routing tables are studied computationally on various networks and traffic matrices. Five heuristics are examined to find an efficient bias factor to prevent the oscillation problem.