Comparative Analysis of Routing Algorithms for Computer Networks.

摘要

The routing problem in a computer-communication network is modeled as a multicommodity flow problem. Two generalizations of the EF algorithm of Cantor and Gerla for solving the nonlinear multicommodity flow problem are presented. These generalizations are of interest because they retain identity of the components of the solution in an implicit and compact manner. A mini-max routing problem is defined as a linear program, and a methodology for its solution as both a linear and nonlinear program is presented. The two approaches are compared with each other, and a lower bound on the solution is developed for the nonlinear approach. Two shortest route algorithms which are very efficient for classes of topologies likely to be considered in routing problems are introduced. The shortest route problem is a subproblem of all of the routing algorithms mentioned above. The computer load sharing problem is formulated as a multicommodity flow problem. An algorithm is presented to solve the load sharing problem which exploits the special structure of the problem. (Author)