Path computation in multi-layer networks: Complexity and algorithms

Carrier-grade networks comprise several layers where different protocols coexist. Nowadays, most of these networks have different control planes to manage routing on different layers, leading to suboptimal use of the network resources and additional operational costs. However, some routers are able to encapsulate, decapsulate and convert protocols and act as a liaison between these layers. Having a unified control plane would be useful to optimize the use of the network resources and automate the routing configurations. SDN based architectures, such as OpenFlow, offers a chance to design such a control plane. One of the most important problem to deal with in this design is the path computation process. Classical path computation algorithms cannot resolve the problem as they do not take into account encapsulations and conversions of protocols. In this paper, we propose path computation algorithms to solve this problem in several cases: With and without bandwidth constraint, and under other Quality of Service constraints. We study the complexity and the scalability of our algorithms and simulate them on real topologies. We show that they outperform the previous ones proposed in the literature.