Optimal dynamic routing in double ring networks

The dynamic routing problem with multiple destinations on ring networks is examined. The authors discuss the peculiarities of the ring topology as well as the resulting simplification for the dynamic routing problem. The problem is transformed into a problem that minimizes link evacuation times. It involves a minimax cost and is equivalent to a linear program admitting a finite solution. A different approach is then taken: a solution based on an infinite algorithm is proposed and used to obtain a complexity of only O(|N|³) per iteration and an exponential rate of convergence to the minimal value. Several optimal routing policies are characterized and formulated. It is found that the store-and-forward feature is not necessary in order to implement a particular optimal routing. Optimality can be achieved by a relatively simple protocol reminiscent of accessing procedures in local area networks. The incorporation of external arrival rates is discussed. Examples are worked out, and suggestions for future work are given