This paper presents a new efficient solution to the Dynamic Shortest Path Routing Problem, using the principles of Generalized Pursuit Learning. It proposes an efficient algorithm for maintaining shortest path routing trees in networks that undergo stochastic updates in their structure. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link-costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The proposed algorithm, referred to as the Generalized Pursuit Shortest Path Algorithm (GPSPA), will be very useful in this regard, because after convergence, it seems to be the best algorithm to-date for this purpose. Indeed, it has the advantage that it can be used to find the shortest path within the 'statistical' average network, which converges irrespective of whether there are new changes in link-costs or not. Existing algorithms are not characterized by such a behaviour inasmuch as they would recalculate the affected shortest paths after each link-cost update. The algorithm has been rigorously evaluated experimentally, and it has been found to be a few orders of magnitude superior to the algorithms available in the literature. Copyright

Additional Metadata
Keywords Algorithm, Dynamic, Generalized pursuit learning, Routing, Shortest path
Persistent URL dx.doi.org/10.1002/dac.684
Journal International Journal of Communication Systems
Citation
Misra, S. (Sudip), & Oommen, J. (2004). GPSPA: A new adaptive algorithm for maintaining shortest path routing trees in stochastic networks. International Journal of Communication Systems, 17(10), 963–984. doi:10.1002/dac.684