TY - GEN
T1 - Schnyder greedy routing algorithm
AU - He, Xin
AU - Zhang, Huaming
PY - 2010
Y1 - 2010
N2 - Geometric routing by using virtual locations is an elegant way for solving network routing problem. In its simplest form, greedy routing, a message is forwarded to a neighbor that is closer to the destination. One major drawback of this approach is that the virtual coordinates requires Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications. In this paper, we introduce a modified version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance for routing decision, our routing algorithms use other criterion to determine routing path, solely based on local information. We present simple generalized greedy routing algorithms based on Schnyder coordinates (consisting of three integers between 0 and 2n), which are derived from Schnyder realizer for plane triangulations and Schnyder wood for 3-connected plane graphs. The algorithms are simple and can be easily implemented in linear time.
AB - Geometric routing by using virtual locations is an elegant way for solving network routing problem. In its simplest form, greedy routing, a message is forwarded to a neighbor that is closer to the destination. One major drawback of this approach is that the virtual coordinates requires Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications. In this paper, we introduce a modified version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance for routing decision, our routing algorithms use other criterion to determine routing path, solely based on local information. We present simple generalized greedy routing algorithms based on Schnyder coordinates (consisting of three integers between 0 and 2n), which are derived from Schnyder realizer for plane triangulations and Schnyder wood for 3-connected plane graphs. The algorithms are simple and can be easily implemented in linear time.
UR - https://www.scopus.com/pages/publications/77954437448
U2 - 10.1007/978-3-642-13562-0_25
DO - 10.1007/978-3-642-13562-0_25
M3 - Conference contribution
AN - SCOPUS:77954437448
SN - 3642135617
SN - 9783642135613
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 271
EP - 283
BT - Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings
PB - Springer Verlag
T2 - 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010
Y2 - 7 June 2010 through 11 June 2010
ER -