Cowen presented a universal compact routing algorithm with a stretch factor of three and a table-size of O(n 2/3  log 4/3  n), based on a simple and practical model [1]. (The table-size is later improved to O(n log3 n) [2].) This stretch factor of three matches a general lower bound given in [3] and also matches a much tighter lower bound if we restrict the model to the Cowen's [4]. Thus it seems quite hard to improve the stretch factor. However, her analysis is of course for the worst case; the situation might differ if we assume some desirable property that average-case networks often possess. As such a property, we consider the notion of flatness in this paper and it is shown that the stretch factor can be significantly improved if the given network is almost flat. Our new algorithm achieves a stretch factor of s < 3 and a table size of O(n log n).
['Kazuo Iwama', 'Masaki Okita']
Compact Routing for Flat Networks