Abstract: TZ compact routing algorithm guarantees the scalability of routing system by the mechanism of selecting landmarks, but though it does not limit the coverage of landmark or analyse whether the landmarks with small coverage are beneficial for the message transfer. It was found that the landmarks with small coverage go against the performance of compact routing, so landmarks were deleted whose coverage was less than the threshold to keep the coverage of landmarks. Also, its relationships with the average stretch and the average routing table size were analyzed systematically. Applying TZ compact routing algorithm to the snapshots of the AS graph spanning a 10 year period, it was found the average stretch decreases first and then increases gradually, the average routing table size decreases first and then keeps invariant. When choosing an approximate threshold, the improved algorithm shows lower average stretch, lower average routing table size and which effectively improves the performance of TZ compact routing.

Key words: compact routing, TZ algorithm, Internet as graph, landmark, coverage