Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/net.21800 | NETWORKS |
Keywords | Field | DocType |
domain clustering,domain re-entry,domain uniqueness,hierarchical PCE,inter-domain path computation,semi-hierarchical PCE | Inter-domain,Mathematical optimization,Algorithm,Cluster analysis,Mathematics,Speedup,Computation | Journal |
Volume | Issue | ISSN |
71.0 | 3.0 | 0028-3045 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lorenzo Maggi | 1 | 52 | 11.55 |
| Jérémie Leguay | 2 | 450 | 30.87 |
| Johanne Cohen | 3 | 4 | 1.77 |
| Paolo Medagliani | 4 | 80 | 12.94 |