Online Orchestration of Cross-Edge Service Function Chaining for Cost-Efficient Edge Computing

Edge computing (EC) has quickly ascended to be the de-facto standard for hosting emerging low-latency applications, as exemplified by intelligent video surveillance, Internet of Vehicles, and augmented reality. For EC, service function chaining is envisioned as a promising approach to configure various services in an agile, flexible, and cost-efficient manner. When running on top of geographically dispersed edge clouds, fully unleashing the benefits of service function chaining is, however, by no means trivial. In this paper, we propose an online orchestration framework for cross-edge service function chaining, which aims to maximize the holistic cost efficiency, via jointly optimizing the resource provisioning and traffic routing on-the-fly. This long-term cost minimization problem is difficult since it is NP-hard and involves future uncertain information. To simultaneously address these dual challenges, we carefully combine an online optimization technique with an approximate optimization method in a joint optimization framework, through: 1) decomposing the long-term problem into a series of one-shot fractional problem with a regularization technique and 2) rounding the fractional solution to a near-optimal integral solution with a randomized dependent scheme that preserves the solution feasibility. The resulting online algorithm achieves an outstanding performance guarantee, as verified by both rigorous theoretical analysis and extensive trace-driven simulations.