FRFC: Fast Table Building Algorithm for Recursive Flow Classification

Abstract—Policy lookup is a very essential function in packet forwarding and network security. As it is becoming a main cause of bottleneck in many network systems, this letter introduces a new policy lookup algorithm called FRFC (Fast table building for Recursive Flow Classification). Although it is based on RFC which shows the best policy lookup speed but the worst policy table update speed, it achieves high performance in table update as well as policy lookup. FRFC divides the whole rule set into smaller sub-rule sets and by doing so, it speeds up the table building time by 50 times compared to RFC when the considered rule set size is 10,000. With the rule set size increasing, the performance gap becomes larger. Index Terms—Packet classification, recursive flow classifica-tion, table update. I