On stretch factors of greedy routing algorithms.

摘要

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.