Policy-based routing with non-strict preferences

Traditional studies of routing problems often assumed strict preferences on paths, by eliminating ambiguity in path comparisons, or imposing a priori deterministic tie-breaking. Such an assumption is outpaced by today's common practice of non-deterministic,multi-path routing, which is crucial to traffic engineering, QoS routing, multicasting and virtual private networking. A pair of paths may be incomparable or equally preferred. In the presence of ambiguous preferences at pairs, or even multiple collections of paths, a challenge is to ensure robustness in the complex and sophisticated situations of policy-based routing where heterogeneous routing policies are allowed among routing systems. This paper presents an extensive study of policy-based routing with non-strict preferences, deriving sufficient conditions that ensure the existence, optimality and asynchronous convergence of stable routings.