An algorithm for the optimization of nonbifurcated flows in computer communication networks

For practical reasons, many computer communications networks currently in operation use single path routing, also called nonbifurcated routing: the traffic of every end to end communication is constrained to follow at most one single path at a time. The determination of optimal nonbifurcated flows is therefore a problem which confronts many network designers. In this paper, two important features of the classical nonbifurcated flow deviation algorithm, originally proposed by Fratta et al. are improved: the path length metric and the starting flow calculation. Tested on different examples, the essential gain is brought by a heuristic which provides a starting flow which is already a reasonable approximation of the global nonbifurcated optimum. Compared with the initial algorithm, this starting flow leads, with less computing time, to solutions which are closer to the optimum.