Amit Kumar Saha Title: High Speed Policy-Based Packet Forwarding using Efficient Multi-Dimensional Range Matching Authors: Lakshman and Stiliadis Conference: Sigcomm 1998 Abstract: --------- The packet classification algorithms present at the time of writing this paper were theoretically very impressive i.e. had very low asymptotic bounds in the number of classification rules (filters). However, since a core router has to manage thousands or rules and each rule is almost always multidimensional, the space and time bounds for the theoretically impressive algorithms were still too high in absolute numbers. The proposed algorithm uses a linear time algorithm and theoretically pales in comparision to existing poly-logarithmic algorithms but the proposed algorithms can be implemented in a very fast manner using bit level parallelism. The proposed approach considers worst-case performance unlike previous approaches which consider average-case performance. Also, the proposed algorithm (the second one in particular) can exploit on-chip memory in a traffic-independent (again unlike previous approaches based on average-case traffic-dependent) manner to speed up worst-case performance. To my mind the biggest advantage is that the algorithm is very simple and they have shown the implementation in a real router. Assumptions: ------------ 1. Cost of accessing a word is the same as cost of accessing a bit in the word - very reasonable assuming current day memory access techniques. 2. Filtering rules are changed very infrequently in comparision to the frequency of search operation. 3. Simple hardware operations required to allow for hardware implementation. Rebuttal: --------- 1. They way they have portrayed that their algorithm is better than the previous algorithms is unfair because essentially the proposed algorithm is a parallel algorithm which has the advantage of multiple processors whereas the earlier algorithms were uniprocessor algorithms. 2. Since there are hardware changes required it might be very difficult deploy this solution since it would require hardware changes on core routers. A simple software or firmware upgrade will not work in this case. Amit ****************************************************************************** Dan Sandler: Packet classification, a task increasingly performed by high-speed core routers in order to provide differentiated services, requires tremendous space and time efficiency to be performed at wire speed. Previous approaches rely on caching, which provides variably under different traffic loads, or prohibitively high processing complexity. Lakshman and Stiliadis have developed algorithms inspired by computational geometry that rapidly match packets against a number of range-based rules. Each of K matchable properties is represented by an axis in K-dimensional space. A packet's particular configuration may match any number of rules; this is represented by the packet as a K-dimensional point, residing inside any number of K-dimensional rectangloids (formed by the regions along each axis which match a given rule). The algorithm further preprocesses this space into the intervals along each axis between rule boundaries; rule membership in each interval can now be represented by a bitmap. These bitmaps (representing the rules which a packet may match for a single attribute) can be computed in parallel, and intersected bitwise to determine which rules match the packet for ALL attributes. The authors offer an incremental modification to this algorithm which reduces memory usage, and a further specialization of the algorithm for the case of two-attribute rules: those matching both a prefix-based source address range and an arbitrary destination address range. My concern with the proposed solution is the following: the authors are clearly most optimistic about the applicability of their two-input algorithm. Does this match the packet-classification needs of DiffServ providers? Additionally, the preprocessing required for operation of this algorithm is significant. Does this allow for rapid and efficient changes to policy? Finally, the range-based approach shown is reasonably efficient for rules which consist of a single contiguous range. If the classification is more subtle, including perhaps the pathological case of a simple list of addresses (arguably relevant for an ISP with many customers with a single point of ingress), the number of actual rules required increases with the number of individual ranges in the classification. ********************************************************************* Andreas Haeberlen: The authors present three variants of a new algorithm for packet classification that can perform range matching on multiple header fields. The algorithm has been implemented in a router prototype, which has a worst-case performance of one million packets/s for up to 512 rules. This is an excellent piece of engineering that will allow router manufacturers to handle the traffic demands of the next decade. However, the memory requirements is quadratic in the size of the classifier, so I doubt that the technique would be practical for very complex classification tasks. Also, many elements of the algorithm, such as the bit mask compression technique, are clever but not particularly novel; see for example guarded page tables (Liedtke 1994). ************************************************************************