Case study of the evolution of routing algorithms in a network planning tool

Traffic routing is a key component in a network planning system. This paper concentrates on the routing algorithms and follows their evolution over mu ltiple releases of a planning tool during a period of six years. The algori thms have grown from the initial stage of finding shortest paths with Dijks tra's algorithm to cover more complex routing tasks such as finding protect ed and unprotected routes and capacity limited routing. We present the algo rithms and in particular emphasize the practical aspects: how previous algo rithms were reused and what were the practical experiences of using the alg orithms. A conclusion of the study is that algorithms should be considered with an engineering attitude. It is not enough to focus on selecting the mo st sophisticated state-of-the-art algorithm for a given problem. Evolution capability, potential for reuse, and the development cost over the system l ifetime are equally important aspects. (C) 2001 Elsevier Science Inc. All r ights reserved.