A distributed adaptive routing algorithm

Abstract

An algorithm for minimum delay routing in packet-switched networks which is capable of adapting to changes in network input traffic, the addition of new links and nodes, and the failure of existing links and nodes is developed and illustrated. The development is based on theoretical results in Ref.[1] on distributed routing, Newton's method for convex minimization, and the formulation of two separate but cooperating distributed processes which constitute the algorithm itself. The first process, called the normal updating process, provides minimum delay routing given an initial loop-free routing assignment. The second, termed the disturbance adaptive process, generates a new loop-free routing for the first process in response to network changes. The algorithm is applied to a 10 node, 36 link network with 40 commodities, and response characteristics are presented and discussed. © 1987.