COSTA: Cross-layer optimization for sketch-based software defined measurement task assignment

Sketch-based measurement provides traffic data summary in a memory-efficient way with provable accuracy bound. Recent advances in software defined networking (SDN) facilitate the development and implementation of sketch-based measurement applications. However, sketch-based measurement usually requires TCAMs which are precious resource in switch to match packet fields. The key challenge for sketch-based measurement is how to accept more concurrent measurement tasks with minimum resource usage. Existing proposals attempt to achieve this goal by exploring different task assignment algorithms. We argue that by sacrificing a small amount of accuracy, the resource usage can be decreased dramatically. In this paper, we propose COSTA, a novel system to improve the performance of the task assignment for sketch-based measurement. We utilize the cross-layer information between the application and the task assignment layers to formulate the problem as a mixed integer nonlinear programming problem. Due to its high computational complexity, we divide the initial problem into two stages and develop a two-stage heuristic to produce task assignment efficiently. In particular, we present an algorithm which guarantees (1 + α) approximation ratio to solve the second stage task assignment. Extensive experiments with three different measurement tasks and real packet traces demonstrate that COSTA significantly reduces the resource usage by up to 40% and accepts 30% more tasks.