A generalized greedy routing algorithm for 2-connected graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. One main drawback of this approach is that the coordinates of the virtual locations require Ω ( n log n ) bits to represent, which makes this scheme infeasible in some applications. The essence of the geometric routing is the following: When an origin vertex u wants to send a message to a destination vertex w, it forwards the message to a neighbor t, solely based on the location information of u, w and all neighbors of u. In the greedy routing scheme, the decision is based on decreasing distance. For this idea to work, however, the decision needs not be based on decreasing distance. As long as the decision is made locally, this scheme will work fine. In this paper, we introduce a version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance, a generalized greedy routing algorithm uses other criteria to determine routing paths, solely based on local information. We present simple generalized greedy routing algorithms based on s t -coordinates (consisting of two integers between 0 and n − 1 ), which are derived from an s t -orientation of a 2-connected plane graph. We also generalize this result to arbitrary trees. Both algorithms are natural and simple to be implemented.

Authors

• Huaming Zhang
• Xin He

Keywords

• Network routing
• Greedy routing
• Plane graph