查看文章

Intradomain routing in IP networks follows shortest paths according to administrative link costs. When several equal-cost shortest paths exist, routers that use equal-cost multipath (ECMP) distribute the traffic over all of them. To produce single-shortest path (SSP) routing, a selection mechanism (tie-breaker) chooses just one of the equal-cost paths. Tie-breakers are poorly standardized and use information that may change over time, which makes SSP routing unpredictable. Therefore, link costs producing unique shortest paths (USP) are preferred. In this paper, we show that optimized SSP routing can lead to significantly higher link utilization than expected in case of non-deterministic tie-breakers. We investigate the impact of the allowed link cost range on the general availability of USP routing. We use a heuristic algorithm to generate link costs for USP routing and to minimize the maximum link utilization in networks …