Following up on the technical report, today Dimitar and myself gave a 70min presentation on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation. It finished my work for the NetFundamentals seminar, which was organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. The seminar was very profound and extensively dug into the mathematics of six fundamental networking papers. Besides that it was great fun and opened some new horizons.

Our presentation can be downloaded as PDF (553 KB), with two slides per page or even with four per page.

Furthermore our listeners were given an equation sheet (139 KB) to aid them in following the many formulas.

Today the technical report on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation was finished. It is part of my work for the NetFundamentals seminar organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. In the seminar six of the computer science papers most worth reading are reviewed and presented. The technical report was written by Dimitar Yordanov and myself and a presentation will follow.

The technical report can be downloaded as PDF (470 KB)

## Abstract

One of the computer science papers most worth reading is Gallager's algorithm for minimum 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 detail that the algorithm achieves total minimum delay routing. Algorithm and model are reviewed and illustrated in detail in this technical report.