Abstract | ||
---|---|---|
Abstract: We present a solution to the problem of quickly classifying packets. Our approach is based on techniques from logic synthesis. Specifically, we express the classification rules as Boolean logic equations, build Binary Decision Diagrams for these equations, and then map the BDDs to a logic network consisting of a pipeline of static RAM banks. We illustrate our approach by applying it to the longest prefix matching for IP forwarding, and present evidence that our scheme can perform a billion matches per second on a CAIDA backbone forwarding table containing 60,000 prefixes. We show how our approach generalizes to classifying packets on multiple fields. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1109/HIS.2001.946688 | Hot Interconnects |
Keywords | Field | DocType |
boolean logic equation,logic network,approach generalizes,present evidence,binary decision diagrams,ip forwarding,pipelined srams,classifying packet,caida backbone forwarding table,billion match,logic synthesis,oc-3072 packet classification,computer aided manufacturing,hardware,logic design,binary decision diagram,logic,associative memory,boolean functions,multiprotocol label switching,longest prefix matching,data structures | Logic synthesis,Digital electronics,Computer science,Binary decision diagram,Computer network,Theoretical computer science,IP forwarding,Routing table,Network packet,Parallel computing,Algorithm,Boolean algebra,Longest prefix match | Conference |
ISBN | Citations | PageRank |
0-7695-1357-3 | 4 | 0.91 |
References | Authors | |
5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amit Prakash | 1 | 50 | 5.97 |
Adnan Aziz | 2 | 1778 | 149.76 |