A general distributed approach to slice embedding with guarantees

Abstract

The challenge of deploying and managing virtualization based network services (slices) recently spurred interest in both the business and the research communities. To provide wide-area network services, resources from different infrastructure providers are needed. Leveraging the consensus-based task allocation algorithms from the robotics literature, we propose a general distributed auction mechanism for the (NPhard) slice embedding problem. Under reasonable assumptions on the bidding scheme, the proposed mechanism is proven to converge, and it is shown that the solutions guarantee a worst-case efficiency of (1 - 1/e) w.r.t. the optimal. Using extensive simulations, we confirm superior convergence properties and resource utilization when compared with existing distributed slice embedding solutions, and we show how by appropriate policy design, our mechanism can be instantiated to accommodate the embedding goals of different service and infrastructure providers.