Abstract
Much research has been devoted to developing efficient routing algorithms for data networks, particularly those referred to as packet switching, distributed networks. More recent developments have led to algorithms which are shown to produce optimum routes with non-looping characteristics. Several of these algorithms have been applied and are currently being used in operational networks. They are, however, restricted to use in small-to-medium scale networks because of excessive overhead which impacts both circuit bandwidth and nodal storage. This research investigates algorithms which function relatively independent of storage and bandwidth and are therefore adaptable to any size network. The primary tool for demonstrating efficient algorithms lies with simulation. The importance of mathematical techniques, however, cannot be overlooked. Therefore, the initial phase of the research involves the investigation and development of abstract analytical concepts which provide an impetus to the design of the simulator. The approach employs a heuristic searching mechanism which requires that a network be described as a graph using the root-node-leaf notation. The level of the tree is equivalent to the known delay about a network at any particular node. The algorithm searches the tree down each leg, evaluating the path from each leaf to the destination node using heuristic information to determine the optimum path. This approach is combined with the classical decomposition-synthesis network evaluation technique to derive a formula for the delay. Several heuristic measures applicable to this formula are evaluated by the simulator.
Greene, William Howard (1978). Optimal routing within large scale distributed computer-communications networks. Texas A&M University. Texas A&M University. Libraries. Available electronically from
https : / /hdl .handle .net /1969 .1 /DISSERTATIONS -636864.