An optimal range matching algorithm for TCAM software simulation

This paper presents an algorithm for matching a search key against multiple entries with arbitrary ranges. These entries are referred as range fields of rules. The range matching is an important feature required in routers or gateways to implement policy based routing or firewall. This feature is usually provided by TCAM which can be implemented either in H/W or S/W. This paper presents an algorithm to simulate S/W TCAM. The algorithm can match a 16-bit or bigger search key against multiple range fields by decomposing the key and range field in 8-bit sub-fields. The paper explains an application of this algorithm using Lucent Bit Vector to heavily optimize memory consumption. The algorithm proposes to expand a range field into maximum 3 range fields for 16-bit range matching. Similarly, worst case expansion for 24-bit range field and 32-bit range field is 5 and 7 respectively.