GreedyJump: A Fast TCAM Update Algorithm

TCAM is widely used for rule tables in network switches. An efficient update scheme, which requires as few rule moves as possible, is often time-consuming to compute, while the fast computation likely yields a mediocre update scheme. We studied the existing algorithms and found none is satisfactory to the emerging applications. In this paper, we present a simple greedy algorithm, GreedyJump, which achieves fast computation and efficient update scheme at the same time, both with the best-in-class performance. The evaluation qualifies GreedyJump as the default TCAM update algorithm ready for meeting the scalability challenges in various application scenarios.