GPSPA: a new adaptive algorithm for maintaining shortest path routing trees in stochastic networks

Abstract 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 © 2004 John Wiley & Sons, Ltd.