Packet Classification Using Two-Dimensional Multibit Tries

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Wencheng Lu Articles by Sartaj Sahni

10th IEEE Symposium on Computers and Communications (ISCC'05)

Cartagena, Murcia, Spain

June 27-June 30

ISBN: 0-7695-2373-0

	ASCII Text	x
	Wencheng Lu, Sartaj Sahni, "Packet Classification Using Two-Dimensional Multibit Tries," Computers and Communications, IEEE Symposium on, pp. 849-854, 10th IEEE Symposium on Computers and Communications (ISCC'05), 2005.

	BibTex	x
	@article{ 10.1109/ISCC.2005.118, author = {Wencheng Lu and Sartaj Sahni}, title = {Packet Classification Using Two-Dimensional Multibit Tries}, journal ={Computers and Communications, IEEE Symposium on}, volume = {0}, year = {2005}, issn = {1530-1346}, pages = {849-854}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISCC.2005.118}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computers and Communications, IEEE Symposium on TI - Packet Classification Using Two-Dimensional Multibit Tries SN - 1530-1346 SP849 EP854 A1 - Wencheng Lu, A1 - Sartaj Sahni, PY - 2005 KW - Packet classification KW - two-dimensional tries KW - multibit tries KW - prefix expansion KW - dynamic programming VL - 0 JA - Computers and Communications, IEEE Symposium on ER -

Wencheng Lu, University of Florida

Sartaj Sahni, University of Florida

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISCC.2005.118

We develop fast algorithms to construct space-optimal constrained two-dimensional multibit tries for Internet packet classifier applications. Experimental evidence suggests that using the same memory budget, space-optimal two-dimensional multibit tries require 1/4 to 1/3 the memory accesses required by two-dimensional one-bit tries for table lookup.

Index Terms:

Packet classification, two-dimensional tries, multibit tries, prefix expansion, dynamic programming

Citation:

Wencheng Lu, Sartaj Sahni, "Packet Classification Using Two-Dimensional Multibit Tries," iscc, pp.849-854, 10th IEEE Symposium on Computers and Communications (ISCC'05), 2005

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.