On the Complexity of Classification Functions

Author

Sasao, Tsutomu

Author_Institution

Dept. of Comput. Sci. & Electron., Kyushu Inst. of Technol., Iizuka

fYear

2008

Firstpage

57

Lastpage

63

Abstract

A classification function is a multiple-valued input function specified by a set of rules, where each rule is a conjunction of range functions. The function is useful for packet classification for internet, network intrusion detection system, etc. This paper considers the complexity of range functions and classification functions represented by sum-of-products expressions of binary variables. It gives tighter upper bounds on the number of products for range functions.

Keywords

Internet; computational complexity; content-addressable storage; multivalued logic circuits; telecommunication security; ternary logic; Internet; multiple-valued input function; network intrusion detection system; packet classification function complexity; range function complexity; sum-of-products binary variable expression; ternary content-addressable memory; Cams; Computer science; Hardware; IP networks; Intrusion detection; Minimization; Multivalued logic; Table lookup; Upper bound; Web and internet services; CAM; Internet; packet classification; sum-of-products expression;

fLanguage

English

Publisher

ieee

Conference_Titel

Multiple Valued Logic, 2008. ISMVL 2008. 38th International Symposium on

Conference_Location

Dallas, TX

ISSN

0195-623X

Print_ISBN

978-0-7695-3155-7

Type

conf

DOI

10.1109/ISMVL.2008.18

Filename

4539402