A Systolic Sieve Array for Real-time Packet Classification

• Item type: Journal(1)
• 公開日: 2001-02-15
• タイトル: A Systolic Sieve Array for Real-time Packet Classification
• タイトル / 言語: en
• タイトル: A Systolic Sieve Array for Real-time Packet Classification
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：マルチメディアネットワークシステム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: マルチメディア通信
• 著者所属: NTT Network Innovation Laboratories
• 著者所属(英): en
• 著者所属(英): NTT Network Innovation Laboratories
• 著者名: Naohisa, Takahashi
• 著者名(英): Naohisa, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Packet classification in which the packet header is analyzed and data corresponding to the header is selected is a key function inimplementing routing-table lookups firewalls label switching and differentiated services.This paper presents a packet classifier that can classify packets by using $2 ?times n$ memory references in the worst case assuming the length of the header is $n$? bytes through a simple operationregardless of the number of classification rules (i.e. filters). Packet classification is modeled as a point-location problem incomputational geometry by introducing a function that sieves the filtersto reduce an $n$-dimensional problem to an $n-1$ dimensional problem.A partial evaluator for the sieve functionand local and global optimizations are described.A one-dimensional solution to the point location problem can be naturally expanded into a multidimensional problem and a real-time packet classifier can be implemented for a high-speed networkwith a relatively small amount of required memory.Preliminary evaluation showed that this classifiercan classify packets using only 708? KB of memory and an average of 16.8 memory accessesper packet for 14-byte headers and 10 000 rules.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Packet classification, in which the packet header is analyzed and data corresponding to the header is selected, is a key function inimplementing routing-table lookups, firewalls, label switching, and differentiated services.This paper presents a packet classifier that can classify packets by using $2 \times n$ memory references in the worst case,assuming the length of the header is $n$\,bytes,through a simple operationregardless of the number of classification rules (i.e., filters). Packet classification is modeled as a point-location problem incomputational geometry by introducing a function that sieves the filtersto reduce an $n$-dimensional problem to an $n-1$ dimensional problem.A partial evaluator for the sieve functionand local and global optimizations are described.A one-dimensional solution to the point location problem can be naturally expanded into a multidimensional problem, and a real-time packet classifier can be implemented for a high-speed networkwith a relatively small amount of required memory.Preliminary evaluation showed that this classifiercan classify packets using only 708\,KB of memory and an average of 16.8 memory accessesper packet for 14-byte headers and 10,000 rules.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 42, 号 2, p. 166-177, 発行日 2001-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764