Domain clustering for inter‐domain path computation speed‐up
Lorenzo Maggi, Jérémie Leguay, Johanne Cohen, Paolo Medagliani · Networks · 2017
We consider a multi‐domain network scenario and we study the Inter‐Domain Path Computation problem under the Domain Uniqueness constraint ( ‐ ), that is, a path cannot visit a domain twice. It is known that hierarchical Path Computation Element (h‐PCE) architecture, that is commonly used to solve ‐ , shows poor scalability with respect to the number of domains. For this reason, we devise a new domain clustering concept allowing one to artificially reduce the number of domains in an offline phase, in order to solve ‐ with lower complexity at run‐time. More specifically, we first prove the ‐completeness of the feasibility problem associated with ‐ and the inapproximability of ‐ itself. Yet, we show that the number of domains is the real computational bottleneck for the solution of ‐ . Then we provide a necessary and sufficient condition for a domain clustering to be proper, that is, without loss of optimality. Such a condition can be verified offline on the inter‐domain graph. We finally show via numerical experiments the impact of the inter‐domain treewidth on the computational speed‐up brought by proper clustering.