Flow inspection router assignment (FIRA) in access/aggregation network clouds

Sufficient computing resources available at future generation routers in the access/aggregation networks can be pooled to form a cloud at edge, which we call Access/Aggregation Network Cloud (or ANC). An ANC can be used to handle some of the information processing conventionally done inside the enterprise networks. ANC computing can also result in a much less delay and more flexibility than if such information processing is done centrally in a data center in the core. In this paper, we formulate two representative optimization problems related to Flow Inspection Router Assignment (FIRA) in ANCs. Their objectives are to minimize the (weighted) number of flows that still need to be inspected inside the enterprise network when only some flows can be assigned to the ANC due to the additional flow inspection delay in the ANC, and when all the flows can be assigned to the ANC, to minimize the additional flow inspection delay, respectively. We prove the NP-hardness of these two new problems, study their performance bounds and propose efficient heuristics. We further extend the formulation and solution to support multicast flows. Simulation shows that our heuristic algorithms can perform close to their performance bounds, implying their near optimality and the tightness of the bounds. In addition, simulation also demonstrates how inspection computing resources can be reduced for multicast flows.