AS Tree Selection for Inter-Domain Multipoint MPLS Tunnels

In this paper, we study the problem of inter-domain AS tree selection for multipoint tunnel set-up within an alliance of ASs. We first describe the framework of our work, based on the introduction of a service plane for automatic multi-domain service provisioning. We introduce an abstract representation of domain relationship by means of directional metrics which are applied to a triplet (ingress point, transit AS, egress point) where the ingress and egress points can be ASs or routers. Then, we focus on the multipoint AS Selection problem that arises in such an architecture. The corresponding constrained Steiner problem is known to be a hard problem, and the introduction of directional metrics increases its complexity. We propose an original approach that allows one to reach almost optimal solutions with tractable computation times. Besides its performance, one contribution of this paper is that some steps of the proposed heuristic can be precomputed, independently of the tunnel demands. By extensive tests on random topologies derived from the Internet, we show that our heuristic is often equal or a few percent close to the optimal, and that, in the case of precomputation, its time consumption can be much lower than other well-known algorithms.