LPM and Packet Classification References

Longest-Prefix Matching

[ASIK]

R. Ahuja, R. Illingworth, H. Kanakia, and B. Shah, System and Method for Locating a Route in a Route Table Using Hashing and Compressed Radix Tree Searching, US Patent 5946679, August 1999.

[Basu]

A. Basu and G. Narlikar, Fast Incremental Updates for Pipelined Forwarding Engines, Proc. IEEE Infocom 2003.

[Broder01]

A. Broder and M. Mitzenmacher, Using Multiple Hash Functions to Improve IP Lookups, Proc. IEEE Infocom 2001.

[BU99]

A. Belenkiy and N. Uzun, Deterministic IP Table Look-Up at Wire Speed, Proc. INET 99, June 1999.

[Crescenzi]

P. Crescenzi, L. Dardini, and R. Grossi, IP Address Lookup Made Fast and Simple, Universita di Pisa Technical Report TR-99-01, January 1999.

[Doeringer]

W. Doeringer, G. Karjoth, and M. Nassehi,, Routing on Longest-Matching Prefixes, IEEE/ACM Trans. Networking, vol. 4, no. 1, February 1996, pp. 86 - 97.

[Draves]

R. Draves, C. King, S. Venkatachary, and B. Zill, Constructing Optimal IP Routing Tables, Proc. IEEE Infocom 99, March 1999.

[Ergun01]

F. Ergun, S. Mittra, S. C. Sahinalp, J. Sharp, and R. K. Sinha, A Dynamic Lookup Scheme for Bursty Access Patterns, Proc. IEEE Infocom 2001.

[Gupta98]

P. Gupta, Fast Routing Lookup Mechanisms, presentation.

[Gupta00]

P. Gupta, B. Prabhakar, and S. Boyd, Near-Optimal Routing Lookups with Bounded Worst Case Performance, Proc. IEEE Infocom 2000. Slides.

[Huang99a]

N-F. Huang, S-M. Zhao, J-Y. Pan, and C-A. Su, A Fast IP Routing Lookup Scheme for Gigabit Switching Routers, Proc. IEEE Infocom 1999.

[Huang99b]

N-F. Huang and S-M. Zhao, A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers, IEEE JSAC, vol. 17, no. 6, pp. 1093-1104, June 1999.

[IGA]

I. Ioannidis, A. Grama, and M. Atallah, Adaptive Data Structures for IP Lookups, Proc. IEEE Infocom 2003.

[Lampson]

B. Lampson, V. Srinivasan, and G. Varghese, IP Lookups Using Multiway and Multicolumn Search, journal version of article appearing in Proc. IEEE Infocom 98, April 1998. Slides.

[Liu-HOTI9]

H. Liu, Reducing Routing Table Size Using Ternary-CAM, Proc. IEEE Hot Interconnects 9, Stanford, CA, August 2001. Slides.

[Liu-ICCCN]

H. Liu, Routing Prefix Caching in Network Processor Design, Proc. ICCCN, Phoenix, AZ, 2001.

[McKeown98]

P. Gupta, S. Lin, and N. McKeown, Routing Lookups in Hardware at Memory Access Speeds, Proc. IEEE Infocom 98, April 1998. Slides.

[Moestedt]

A. Moestedt and P. Sjodin, IP Address Lookup in Hardware for High-Speed Routing, Submitted to Hot Interconnects 2000, May 2000.

[Narlikar]

G. Narlikar and F. Zane, Performance Modeling for Fast IP Lookups, Proc. ACM SIGMETRICS 2001.

[Nilsson98]

S. Nilsson and G. Karlsson, Fast Address Lookup for Internet Routers, Proc. IFIP 4th International Conference on Broadband Communications, pp. 11-22, 1998.

[Nilsson99]

S. Nilsson and G. Karlsson, IP-Address Lookups Using LC-Tries, IEEE JSAC, vol. 17, no. 6, pp. 1083-1092, June 1999.

[Pink]

M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, Small Forwarding Tables for Fast Routing Lookups, Proc. ACM SIGCOMM 97, 1997.

[Ruiz]

M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, Survey and Taxonomy of IP Address Lookup Algorithms, IEEE Netowork, March/April 2001, pp. 8 - 23.

[Srinivasan]

V. Srinivasan and G. Varghese, Fast Address Lookups Using Controlled Prefix Expansion, Proc. ACM TOCS 99, 1999.

[Waldvogel97]

M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, Scalable High Speed IP Routing Lookups, Proc. ACM SIGCOMM 97, 1997.

[Waldvogel01]

M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, Scalable High-Speed Prefix Matching, to appear in ACM Transactions on Computer Systems, 2001.

[Wang00]

P-C. Wang, C-T. Chan, and Y-C. Chen, A Fast IP Routing Lookup Scheme, Proc. ICC 2000, vol. 2, pp. 1140-1144.

[Warkhede99]

S. Suri, G. Varghese, and P. Warkhede, Multiway Range Trees: Scalable IP Lookup with Fast Updates, Washington Univ. Technical Report TR 99-28, 1999.

[WVP]

H. Wilkinson III, G. Varghese, and N. Poole, Compressed Prefix Matching Database Searching, US Patent 5781772, July 1998.

Multi-field Packet Classification

[ASPsub]

H. Adiseshu, S. Suri, and G. Parulkar, Packet Filter Management in Layer 4 Switching, submitted to IEEE Infocom.

[ASPpub]

A. Hari, S. Suri, and G. Parulkar, Detecting and Resolving Packet Filter Conflicts, Proc. IEEE Infocom 2000.

[Attwood02]

K. Attwood, J. Godwin, L. Overby, B. Perry, and D. Wierbowski, Security Rule Database Searching in a Network Security Environment, US Patent 6347376, February 2002.

[Baboescu01a]

F. Baboescu and G. Varghese, Scalable Packet Classification, Proc. ACM SIGCOMM 2001, August 2001.

[Baboescu01b]

F. Baboescu and G. Varghese, Aggregated Bit Vector Search Algorithms for Packet Filter Lookups, 2001.

[Baboescu03]

F. Baboescu, S. Singh, and G. Varghese, Packet Classification for Core Routers: Is there an alternative to CAMs?">, Proc. IEEE Infocom 2003.

[Bailey94]

M. Bailey, B. Gopal, M. Pagels L. Peterson, and P. Sarkar, PathFinder: A Pattern-Based Packet Classifier, Proc. First Symposium on Operating System Design and Implementation, November 1994.

[Begel99]

A. Begel, S. McCanne, and S. Graham, BPF+: Exploiting Global Data-flow Optimization in a Generalized Packet Filter Architecture, to appear in Proc. ACM SIGCOMM 99, September 1999. Slides.

[Borg99]

N. Borg, E. Svanberg, and O. Schelen, Efficient Multi-field Packet Classification for QoS Purposes, Proc. IEEE IwQoS 99, 1999.

[BSW99]

M. Buddhikot, S. Suri, and M. Waldvogel, Space Decomposition Techniques for Fast Layer-4 Switching, Proc. Sixth International Workshop on Protocols for High Speed Networks (PfHSN99), 1999.

[Calvingac01]

J. Calvignac, E. Corl, A. Gallo, M. Heddes, C. Jeffries, P. Patel, M, Rinaldi, and C. Verrilli, System and Method and Computer Program for Filtering Using Tree Structure, US Patent 6298340, October 2001.

[DDPP98]

D. Decasper, Z. Dittia, G. Parulkar, and B. Plattner, Router Plugins: A Modular and Extensible Software Framework for Modern High Performance Integrated Services Routers, Washington University Technical Report WUCS-98-08, 1998.

[Engler96]

D. Engler and M. Kaashoek, DPF: Fast, Flexible Message Demultiplexing using Dynamic Code Generation, Proc. ACM SIGCOMM 96, August 1996.

[Eppstein01]

D. Eppstein and S. Muthukrishnan, Internet Packet Filter Management and Rectangle Geometry, Proc. 12th ACM-SIAM Symposium Discrete Algorithms, Washington, pp. 827-835, 2001.

[Feldman00]

A. Feldmann and S. Muthukrishnan, Tradeoffs for Packet Classification, Proc. IEEE Infocom 2000.

[Gupta99]

P. Gupta and N. McKeown, Packet Classification on Multiple Fields, Proc. ACM SIGCOMM 99, September 1999. Slides.

[Gupta01]

P. Gupta and N. McKeown, Algorithms for Packet Classification, IEEE Network March/April 2001, pp. 24 - 32.

[Hartmeier]

D. Hartmeier, Design and Performance of the OpenBSD Stateful Packet Filter (pf), Proc. IEEE Infocom 2003.

[Iyer01]

S. Iyer, R. Kompella, and A. Shelat, ClassiPI: An Architecture for Fast and Flexibe Packet Classification, IEEE Network March/April 2001, pp. 33 - 41.

[Lidl]

K. Lidl, D. Lidl, and P. Borman Flexible Packet Filtering: Providing a Rich Toolbox, Proc. Usenix BSDCon 2002.

[Lin]

Y-D. Lin, Y. Neng, S-C. Yang, and Y-S. Lin, DiffServ over Network Processors: Implementation and Evaluation, Proc. IEEE Hot Interconnects 10, 2002. Slides.

[Lui2002]

H. Liu, Efficient Mapping of Range Classifier into Ternary-CAM, Proc. IEEE Hot Interconnects 10, 2002. Slides.

[LS98]

T. V. Lakshman and D. Stiliadis, High-Speed Policy-based Packet Forwarding Using Efficient Multi- dimensional Range Matching, Proc. ACM SIGCOMM 98, September 1998.

[Mahmud00]

M. O'Connor and S. Mahmud, Address Processor and Classifier Co-Processors from Silicon Access Networks: A Family of Search Coprocessors for Terabit Routers with OC192 Blades, Proc. Hot Interconnects VIII, August 2000.

[McCanne93]

S. McCanne and V. Jacobson, The BSD Packet Filter: A New Architecture for User-level Packet Capture, Proc. Winter USENIX Conference, San Diego, CA, January 25-29, 1993.

[McKeown99]

P. Gupta and N. McKeown, Packet Classification Using Hierarchical Intelligent Cuttings, Proc. Hot Interconnects VII, August 1999. Slides.

[McKeown00]

P. Gupta and N. McKeown, Dynamic Algorithms with Worst-case Performance for Packet Classification, Proc. IFIP Networking, May 2000. Slides.

[Overmars]

M. Overmars and A. F. van der Stappen, Range Searching and Point Location among Fat Objects, European Symposium on Algorithms, 1994.

[Panigrahy]

R. Panigrahy and S. Sharma, Reducing TCAM Power Consumption and Increasing Throughput, Proc. IEEE Hot Interconnects 10, 2002. Slides.

[Prakash]

A. Prakash and A. Aziz, A Middle Ground Between CAMs and DAGs for High-Speed Packet Classification, Proc. IEEE Hot Interconnects 10, 2002. Slides.

[Qiu01]

L. Qiu, G. Varghese, and S. Suri, Fast Firewall Implementations for Software and Hardware-based Routers, Proc. ICNP 2001.

[SSV99]

V. Srinivasan, S. Suri, and G. Varghese, Packet Classification using Tuple Space Search, to appear in Proc. ACM SIGCOMM 99, September 1999.

[Shah00]

D. Shah and P, Gupta, Fast Incremental Updates on Ternary-CAMs for Routing Lookups and Packet Classification, Proc. IEEE Hot Interconnects VIII, August 2000. Slides.

[Sharma]

S. Sharma and R. Panigrahy, Sorting and Searching using Ternary CAMs, Proc. IEEE Hot Interconnects 10, 2002. Slides.

[Sikka00]

S. Sikka and G. Varghese, Memory-Efficient State Lookups with Fast Updates, Proc. ACM SIGCOMM 2000, September 2000.

[Srinivasan01]

V. Srinivasan, A Packet Classification and Filter Management System, Proc. IEEE Infocom 2001.

[SuriA]

S. Suri and G. Varghese, Packet Filtering in High Speed Networks, abstract.

[Suri98]

S. Suri, Fast and Scalable Layer 4 Switching, presentation to Lucent Technologies, November 1998.

[Tsuchiya92]

P. Tsuchiya, A Search Algorithm for Table Entries with Non-contiguous Wildcarding, unpublished manuscript, 1992.

[VVSW98]

V. Srinivasan, G. Varghese, S. Suri, and W. Waldvogel, Fast and Scalable Layer Four Switching, Proc. ACM SIGCOMM 98, September 1998. Slides.

[Waldvogel00]

M. Waldvogel, Multi-Dimensional Prefix Matching Using Line Search, Proc. IEEE LCN 2000, Tampa, November 2000. Slides.

[Warkhede01]

P. Warkhede, S. Suri, and G. Varghese, Fast Packet Classification for Two-Dimensional Conflict-Free Filters, Proc. IEEE Infocom 2001.

[Woo00]

T. Y. C. Woo, A Modular Approach to Packet Classification: Algorithms and Results, Proc. IEEE Infocom 2000.

[Xu00]

J. Xu, M. Singhal, and J. Degroat, A Novel Cache Architecture to Support Layer-Four Packet Classification at Memory Access Speeds, Proc. IEEE Infocom 2000.

[Zane]

F. Zane, G. Narlikar, and A. Basu, CoolCAMs: Power-Efficient TCAMs for Forwarding Engines, Proc. IEEE Infocom 2003.