Summary of Multi-Dimensional Packet Classification.


Please see Table 49.8 for a summary of the complexities of classification algorithms described in this chapter.


[1] M. de Berg, M. van Kreveld, and M. Overmars. Computational Geometry: Algo- rithms and Applications, Springer-Verlag, 2nd rev. ed. 2000.

[2] M.M. Buddhikot, S. Suri, and M. Waldvogel. “Space decomposition techniques for fast layer-4 switching,” Proceedings of Conference on Protocols for High Speed Networks, pages 25-41, August 1999.

[3] A. Feldman and S. Muthukrishnan. “Tradeoffs for packet classification,” Proceedings

of Infocom, vol. 3, pages 1193-202, March 2000.

[4] P. Gupta and N. McKeown. “Packet Classification on Multiple Fields,” Proc. Sigcomm, Computer Communication Review, vol. 29, no. 4, pp 147-60, September 1999,

Harvard University.

[5] P. Gupta and N. McKeown. “Packet Classification using Hierarchical Intelligent Cut- tings,” Proc. Hot Interconnects VII, August 99, Stanford. This paper is also available in IEEE Micro, pp 34-41, vol. 20, no. 1, January/February 2000.

[6] P. Gupta and N. McKeown. “Dynamic Algorithms with Worst-case Performance for Packet Classification”, Proc. IFIP Networking, pp 528-39, May 2000, Paris, France.

[7] T.V. Lakshman and D. Stiliadis. “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching”, Proceedings of ACM Sigcomm, pages 191-202, September 1998.

[8] M.H. Overmars and A.F. van der Stappen. “Range searching and point location among fat objects,” Journal of Algorithms, vol. 21, no. 3, pages 629-656, November 1996.

[9] F. Preparata and M. I. Shamos. Computational geometry: an introduction, Springer-Verlag, 1985.

[10] F. Shafai, K.J. Schultz, G.F. R. Gibson, A.G. Bluschke and D.E. Somppi. “Fully parallel 30-Mhz, 2.5 Mb CAM,” IEEE Journal of Solid-State Circuits, vol. 33, no. 11, November 1998.

[11] V. Srinivasan, S. Suri, G. Varghese, and M. Waldvogel. “Fast and Scalable Layer four Switching,” Proceedings of ACM Sigcomm, pages 203-14, September 1998.

[12] V. Srinivasan, S. Suri, and G. Varghese. “Packet Classification using Tuple Space Search”, Proceedings of ACM Sigcomm, pages 135-46, September 1999.

[13] P. Tsuchiya. “A search algorithm for table entries with non-contiguous wildcarding,” unpublished report, Bellcore.

[14] F. Baboescu and G. Varghese. “Scalable packet classification,” Proc. Sigcomm, 2001.

Related posts:

Leave a comment

Your email address will not be published. Required fields are marked *