AS-level source routing for multi-provider connection-oriented services

In this paper, we study the inter-domain Autonomous System (AS)-level routing problem 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 adopt an abstract representation of domain relationships 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 point-to-point and multipoint AS-level routing problems that arise in such an architecture. We propose an original approach that reaches near optimal solutions with tractable computation times. A further contribution of this paper is that a heavy step in the proposed heuristic can be precomputed, independently of the service demands. Moreover, we describe how in this context AS-level path diversity can be considered, and present the related extension of our heuristic. By extensive tests on AS graphs 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 with other well-known algorithms.