Degree Type


Date of Award


Degree Name

Doctor of Philosophy


Computer Science

First Advisor

Deepinder P. Sidhu


The routing is one very important function implemented in computer communication networks. It collects information about optimal paths within a network;The purpose of this dissertation is to study the routing function in large networks which are characterized by frequent topological changes. The study focuses on constructing routing protocols with some desirable properties such as distributed computation, adaptation to flow variations within the network, failsafe against arbitrary topological changes, loop-free route tables for all destinations at all times, bounded values for variables, and fast recovery from topological changes;At present, most routing protocols use the next-node routing technique, a technique in which each node keeps only the next node identification for a particular destination. A different type of routing scheme provided in some protocol standards is called source routing. A source routing protocol builds complete paths from a source to all destinations in the network. Several source routing algorithms are derived with desirable properties;Most distributed routing algorithms use one or more variables to store unbounded values such as update cycle numbers. Distributed routing protocols with bounded update cycle numbers are proposed. The proposed protocols possess desirable properties and are obtained by applying the sliding window idea for flow control in networks to the routing protocols which employ unbounded update cycle numbers;How fast an algorithm provides optimal paths from every node to every other node in a network after a topological change is an important consideration in the design of routing algorithms. Several algorithms for achieving shortest paths to all destinations in the network with improved recovery speed from topological changes are presented.



Digital Repository @ Iowa State University,

Copyright Owner

Ta Wen Lin



Proquest ID


File Format


File Size

186 pages