JOTA: Joint optimization for the task assignment of sketch-based measurement

Sketch-based measurement provides traffic data summary in a memory-efficient way with provable accuracy bound. Recent advances in software defined networking facilitate the development and implementation of sketch-based measurement applications. However, sketch-based measurement usually requires TCAMs and SRAMs 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 JOTA, a novel system to improve the performance of the task assignment for sketch-based measurement. By considering both TCAM and SRAM capacities, we 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 efficiently produce task assignment. 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 JOTA significantly reduces the resource usage and accepts 33% more tasks compared with the first fit approach.