Premium
Domain clustering for inter‐domain path computation speed‐up
Author(s) -
Maggi Lorenzo,
Leguay Jérémie,
Cohen Johanne,
Medagliani Paolo
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21800
Subject(s) - cluster analysis , computer science , domain (mathematical analysis) , computation , bottleneck , path (computing) , scalability , algorithm , computational complexity theory , theoretical computer science , mathematics , artificial intelligence , mathematical analysis , database , programming language , embedded system
We consider a multi‐domain network scenario and we study the Inter‐Domain Path Computation problem under the Domain Uniqueness constraint ( IDPC ‐ DU ), 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 IDPC ‐ DU , 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 IDPC ‐ DU with lower complexity at run‐time. More specifically, we first prove the NP ‐completeness of the feasibility problem associated with IDPC ‐ DU and the inapproximability of IDPC ‐ DU itself. Yet, we show that the number of domains is the real computational bottleneck for the solution of IDPC ‐ DU . 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.