Herding packets: Properties needed of metrics for loop-free & best forwarding paths

The distributed, hop-by-hop routing architecture used in the Internet depends on algebraic properties of routing metrics to ensure traffic is forwarded over loop-free and best (LFB) paths. As the Internet evolves to serve as the converged communication infrastructure for the 21st century, the need for new metrics that violate these properties ([5], [9]) has been identified. Until recently, the behavior of routing metrics had not been studied. Recent work ([5], [9]) has presented some results identifying the requirements of metrics to ensure LFB paths, however they have not been fully characterized. Building on this work, this paper presents the necessary and sufficient conditions for routing metrics to ensure LFB paths in an Internet environment. Specifically, a metric must be strictly bounded (a <; a+b) and monotonic (a ≤ b ⇒ a+c ≤ b+c) to ensure LFB forwarding paths. This paper presents the first comprehensive statement of the properties required to ensure LFB forwarding paths in the Internet.