GreedyJump: A Fast TCAM Update Algorithm
Ying Wan, Haoyu Song, Bin Liu · IEEE Networking Letters · 2021
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 letter, 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 qualifiesGreedyJumpas the default TCAM update algorithm ready for meeting the scalability challenges in various application scenarios.