Robert Gallager’s Minimum Delay Routing Algorithm Using Distributed Computation

One of the computer science papers most worth reading is Gallager’s algorithm for mini-mum delay routing. The merit of Gallager’s paper is its rigorous mathematical approach to a problem, which is more often taken care of using heuristics. The approach is founded on a well designed mathematical network model, which is custom-tailored to describe the minimum total delay routing problem. Mathematical observations on the model lead to two conditions for achieving global optimization, which are based on the marginal delay of links and neighbors. From these observations and conditions an iterative, distributed routing algorithm is naturally derived. Gallager finishes his analysis by proving in de-tail that the algorithm achieves total minimum delay routing. Algorithm and model are reviewed and illustrated in detail in this technical report.