Date of Award

2013

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

Committee Chair

Huaming Zhang

Committee Member

Peter J. Slater

Committee Member

Letha Etzkorn

Committee Member

Mary E. Weisskopf

Committee Member

Dongsheng Wu

Subject(s)

Routers (Computer networks), Optical communication, Graph theory, Neural networks (Computer science), Algorithms, Sensor networks, Wireless communication systems

Abstract

Routing aims to find a path to deliver the information from a source to the destination in the network. Routing is one of the most important algorithmic problems in networking. Our research focuses primarily on greedy routing algorithms. The greedy routing algorithms always compute a routing path by forwarding a message to a neighbor closer to the destination than itself. The closeness to the destination can be measured differently via different notions of distances. Greedy routing algorithms keep forwarding the message to a neighbor closer to the destination than itself until the distance to the destination reduces to zero. When the distance is zero, the message has reached its destination. One of the metrics used to quantitatively measure the effectiveness of the routing algorithms is a stretch factor. The stretch factor is defined as the worst ratio of the length of the routing path computed by an algorithm versus the shortest length path. The ratio equal to one is acknowledged as optimum stretch factor algorithm. An improved stretch factor reduces the overhead cost and ensures the better utilization of available resources. Ideally, one would desire to use an optimum routing algorithm, but in some cases it is not always feasible, especially in cases such as complex networks. Under such circumstances, algorithms with smaller stretch factors are preferred. To the best of our knowledge, so far adequate research has not been conducted on reducing the stretch factors of greedy routing algorithms. In this dissertation, we present two greedy routing algorithms. The first algorithm is a heuristic greedy routing algorithm for general networks. We have conducted an experimental study on the algorithm; results show that it produces a small stretch factor. We also theoretically establish the lower bound of the stretch factor for a special subcategory of networks, i.e., 2-connected outerplanar networks. The second algorithm presented in this dissertation is an optimum greedy routing algorithm for triangulated polygon networks.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.