Paper List

1. T. Lakshman, D. Stiliadis, "High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching" [Bit-Parallelism]
2. F. Baboescu, G. Varghese, "Scalable Packet Classification" [ABV: Agregated Bit Vector]
3. M. Buddhikot, S. Suri, M. Waldvogel, "Space Decomposition Techniques for Fast Layer-4 Switching" [Space Decomposition]
4. V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, "Fast and Scalable Layer Four Switching" [Layer4]

1.  Bit-Parallelism

   The ability to provide differentiated services to users with widely varying requirements is becoming increasingly important, and Internet Service Providers would like to provide these differentiated services using the same shared network infrastructure. The key mechanism, that enables differentiation in a connectionless network, is the packet classification function that parses the headers of the packets, and after determining their context, classifies them based on administrative policies or real-time reservation decisions. Packet classification, however, is a complex operation that can become the bottleneck in routers that try to support gigabit link capacities.

   The presented filtering or classification schemes can be used to classify packets for security policy enforcement, applying resource management decisions, flow identification for RSVP reservations, multicast look-ups, and for source-destination and policy based routing. The scalability and performance of the algorithms have been demonstrated by implementation and testing in a prototype system.

    

2. [ABV: Agregated Bit Vector]

Hardware solutions such as TCAMs do not scale to large classifiers. However,even for large classifiers(say 100,000 rules),any packet is likely to atch a few (say 10)rules. This paper seeks to exploit this observation to produce a scalable packet classi fication scheme called Aggregated Bit Vector (ABV). This paper takes the bit vector search algorithm (BV, which takes linear time) described by Lakshman et al in the paper "High speed policy-based packet forwarding using efficient multi-dimensional range matching". They add two new ideas,recursive aggregation of bit aps and filter rearrangement,to create ABV (which can take logarithmic time for many databases).We show that ABV outperforms BV by an order of agnitude using simulations on both industrial firewall databases and synthetically generated databases.


3. Space Decomposition

   A new scheme, based on space decomposition is presented. Its search time is
   comparable to the best existing schemes, but which also offers fast worst-case filter update time. 
   The three key ideas in this algorithm are as follows: 
   (1) innovative data-structure based on quadtrees for a hierarchical representation of the recursively decomposed search space, 
   (2) fractional cascading and pre-computation to improve packet classification time, and 
   (3) prefix partitioning to improve update time. Depending on the actual requirements of the system this algorithm is deployed in, a single parameter can be used to tradeoff search time for update time. 
   
   Also, this algorithm is amenable to fast software and hardware implementation.

    

4. Layer4

3-Space Decomposition

1. Buddhikot, M., Suri, S., and Waldvogel, S., “Space Decomposition Techniques for Fast Layer-4 Switching,” Bell Labs Technical Memorandum, BL011345-990726-06TM, Lucent Bell Labs, Holmdel, NJ, 1999.
2.   Chazelle, B., and Guibas, J., L., “Fractional Cascading,” Digital Systems Research Center Technical Report, Palo Alto, June 1986.
3.  Decasper, D., Dittia, Z., Parulkar, G., and Plattner, B., “Router Plugins: A Software Architecture for Next Generation Routers,” Proceedings of ACM SIGCOMM 98, Vancouver, Canada, pp. 229-240, Sept. 1998.
4.  Kumar, V., P., Lakshman, T., V., and Stiliadis, D., “Beyond Best-Effort: Gigabit Routers for Tomorrow’s Internet,” IEEE Communications Magazine, pp. 152-164, May 1998.
5.  Samet, H., “Design and Analysis of Spatial Data Structures,” Addison Wesley, ISBN 0-201-50255-0, 1990.