  One of the key features of small-worlds is the ability to route messages with
few hops only using local knowledge of the topology. In 2000, Kleinberg
proposed a model based on an augmented grid that asymptotically exhibits such
property. In this paper, we propose to revisit the original model from a
simulation-based perspective. Our approach is fueled by a new algorithm that
uses dynamic rejection sampling to draw augmenting links. The speed gain
offered by the algorithm enables a detailed numerical evaluation. We show for
example that in practice, the augmented scheme proposed by Kleinberg is more
robust than predicted by the asymptotic behavior, even for very large finite
grids. We also propose tighter bounds on the performance of Kleinberg's routing
algorithm. At last, we show that fed with realistic parameters, the model gives
results in line with real-life experiments.
