Fast Computation Flow Restoration with Path-Based Two-Stage Traffic Engineering

The emerging edge networks are cloud-native. Flows with computation needs are processed in-flight by compute nodes inside the network. Routing with In-Network Processing (RINP) not only has to maintain network-wide load balance on communication and computation elements, but also has to quickly restore flows upon various types of failures. In this paper, we propose a novel path-based two-stage traffic engineering scheme to trade-off between routing model complexity, network performance in the normal stage, and restoration efficiency upon failures. For the normal stage, our model jointly optimizes computation demand allocation and traffic flow routing. We further speed-up RINP calculation by controlling the path budget and decoupling computation allocation and traffic routing. For the restoration stage, we develop a fast restoration scheme that only re-routes the flows traversing the failed elements to achieve close-to-optimal network delay performance while minimizing the fraction of unrestored flows. Evaluation results on real network instances demonstrate that in the normal stage, our scheme achieves near-optimal performance with up to 50-100x speedup compared to link-based routing models. In the restoration stage, our scheme can restore most of the affected traffic with up to 10x speedup compared to globally rerouting all the flows.