A Systolic Sieve Array for Real-time Packet Classification (特集:マルチメディアネットワークシステム)

概要

論文の詳細を見る
Packet classification, in which the packet header is analyzed and data corresponding to the header is selected, is a key function in implementing routing-table lookups, firewalls, label switching, and differentiated services. This paper presents a packet classifier that can classify packets by using 2×n memory references in the worst case, assuming the length of the header is n bytes, through a simple operation regardless of the number of classification rules(i.e., filters). packet classification is modeled as a point-location problem in computational geometry by introducing a function that sieves the filters to reduce an n-dimensional problem to an n-1 dimensional problem. A partial evaluator for the sieve function and local and global optimizations are described. A one-dimensional solution to the point location problem can be naturally expanded into a multidimensional probelm, and a real-time packet classifier can be implemented for a high-speed network with a relatively small amount of required memory. Preliminary evaluation showed that this classifier can classify packets using only 708KB of memory and an average of 16.8 memory accesses per packet for 14-byte headers and 10, 000 rules.
一般社団法人情報処理学会の論文
2001-02-15