Full metadata record
DC FieldValueLanguage
dc.contributor.authorChen, Chienen_US
dc.contributor.authorHsu, Chia-Jenen_US
dc.contributor.authorHuang, Chi-Chiaen_US
dc.date.accessioned2014-12-08T15:01:13Z-
dc.date.available2014-12-08T15:01:13Z-
dc.date.issued2008-01-01en_US
dc.identifier.issn1016-2364en_US
dc.identifier.urihttp://hdl.handle.net/11536/119-
dc.description.abstractTo support applications such as Internet security, virtual private networks, and Quality of Service (QoS), Internet routers need to quickly classify incoming packets into flows. Packet classification uses information contained in the packet header and a predefined rule table in the routers. In general, packet classification on multiple fields is a difficult problem. Hence, researchers have proposed a variety of classification algorithms. This paper presents a novel packet classification algorithm, the bit compression algorithm. As with the best-known classification algorithm, bitmap intersection, bit compression is based on the multiple dimensional range lookup approach. Since bit vectors of the bitmap intersection contain many "0" bits, the bit vectors could be compressed. We compress the bit vectors by preserving only useful information and removing the redundant bits of the bit vectors. An additional index table would be created to keep track of the rule number associated with the remaining bits. Additionally, the wildcard rules enable an extensive improvement in the storage requirement. A novel Fast Boolean Expansion enables our scheme to obtain better classification speed even under a large number of wildcard rules. Compared to the bitmap intersection algorithm, the bit compression algorithm reduces the storage complexity in the average case from O(dN(2)) (for bitmap intersection) to theta(dN.log N), where d denotes the number of dimensions and N represents the number of rules. The proposed scheme cuts the cost of packet classification engine and increases classification performance by accessing less memory, which is the performance bottleneck in the packet classification engine implementation using a network processor.en_US
dc.language.isoen_USen_US
dc.subjectrouteren_US
dc.subjectpacket classificationen_US
dc.subjectbitmap intersectionen_US
dc.subjectbit compressionen_US
dc.subjectBoolean expansionen_US
dc.subjectnetwork processoren_US
dc.titleFast packet classification using bit compression with fast boolean expansionen_US
dc.typeArticle; Proceedings Paperen_US
dc.identifier.journalJOURNAL OF INFORMATION SCIENCE AND ENGINEERINGen_US
dc.citation.volume24en_US
dc.citation.issue1en_US
dc.citation.spage61en_US
dc.citation.epage81en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000253046500006-
Appears in Collections:Conferences Paper


Files in This Item:

  1. 000253046500006.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.