On Cooperative Inter-Domain Path Computation

Inter-domain path computation, or the ability to compute end-to-end paths across multiple domains, is the next step toward wide deployment of a distributed control plane with support for traffic engineering. A key enabler to achieve this goal is the introduction of a Path Computation Element (PCE) in each domain. There are various ways these elements can collaborate to compute an end-to-end path; of particular interest to us in this paper is cooperative path computation, a scheme where PCEs exchange path information in the context of a specific end-to-end path computation instance, often prior to signaling the path. We show that depending on the information available to each PCE, cooperation can take one of two forms, which we call model-based and ad hoc. We demonstrate that model-based cooperation is essentially a multistage decision problem, and offer a probabilistic analysis which we believe is the key to understanding the problem and developing efficient inter-domain path computation heuristics. In particular, we argue that having an estimate of the blocking probability in each domain can be helpful in determining the path computation effort needed to find an end-to-end path.