Publication Type
Journal Article
Pagination
249 - 258
Abstract
We analyze here a pure greedy hot-potato routing strategy on a two-dimensional
mesh of n^2 nodes. We specifically study the case of n^
2 packets, originating one per
node, to be delivered at random uniform destinations. Each packet attempts to follow
the shortest path leading first to the destination row/column (whichever is closest) and
then to the actual destination node. A de
ection policy is adopted to solve con
icts. We prove that all packets are delivered to the destinations in average time O(nlogn). The
average is taken over all possible destination functions. No average case analysis of pure
greedy hot-potato routing was known up to now.
mesh of n^2 nodes. We specifically study the case of n^
2 packets, originating one per
node, to be delivered at random uniform destinations. Each packet attempts to follow
the shortest path leading first to the destination row/column (whichever is closest) and
then to the actual destination node. A de
ection policy is adopted to solve con
icts. We prove that all packets are delivered to the destinations in average time O(nlogn). The
average is taken over all possible destination functions. No average case analysis of pure
greedy hot-potato routing was known up to now.
Publication Links
Year of Publication
1997
