@phdthesis{oai:kyutech.repo.nii.ac.jp:00004105,
 author = {Infall, Syafalni},
 month = {2014-12-05},
 note = {1 Introduction||2 Preliminary||3 Generating Prefix Sum-of-Products Expressions for Interval Functions||4 Derivation of Head-Tail Expressions for Interval Functions||5 Head-Tail Expressions for Single-Field Classification Functions||6 Head-Tail Expressions for Multi-Field Classification Functions||7 Conclusion and Future Work||Acknowledgements||List of Publications, Packet classification is used in various network applications such as firewalls, access control lists, and network address translators. This technology uses ternary content addressable memories （TCAMs） to perform high speed packet forwarding. However, TCAMs dissipate high power and their cost are  high. Thus, reduction of TCAMs is crucial. First, this thesis derives the prefix sum-of-products expression （PreSOP） and the number of products in a PreSOP for an interval function. Second, it derives Ψ（n,τ p）, the number of n-variable interval functions that can be represented with τp products. Finally, it shows that more than 99.9% of the n-variable interval functions can be represented with ⌈3/2 n - 1⌉ products when n is sufficiently large. These results are useful for fast PreSOP generator and for estimating the size of Ternary Content Addressable Memories （TCAMs） for packet classification. Second, this thesis shows a method to represent interval functions by using head-tail expressions. The head-tail expressions represent greater-than GT（n : A） functions, lessthan LT（n : B） functions, and interval functions IN0（n : A,B） more efficiently than sum-of-products expressions, where n denotes the number of bits to represent the largest value in the interval （A,B）. This paper proves that a head-tail expression （HT） represents an interval function with at most n words in a ternary content addressable memory （TCAM） realization. It also shows the average numbers of factors to represent interval functions by HTs for up to n = 16, which were obtained by a computer simulation. It also conjectures that, for sufficiently large n, the average number of factors to represent n-variable interval functions by HTs is at most 2/3 n - 5/9. Experimental results also show that, for n ≥ 10, to represent interval functions, HTs require at least 20% fewer factors than MSOPs, on the average. Third, this thesis presents a method to generate head-tail expressions for single-field classification functions. First, it introduces a fast prefix sum-of-product （PreSOP） generator （FP） which generates products using the bit patterns of the endpoints. Next, it shows a direct head-tail expression generator （DHT）. Experimental results show that DHT generates much smaller TCAM than FP. The proposed algorithm is useful for simplified TCAM generator for packet classification.Finally, this thesis shows methods to simplify rules in TCAMs for packet classification. First method, it partitions the rules into groups so that each group has the same source address, destination address and protocol. After that, it implifies rules in each group by removing redundant rules. A computer program was developed to simplify rules among groups. Experimental results show that this  method reduces the size of rules up to 57% of the original specification for ACL5 rules, 73% for ACL3 rules, and 87% for overall rules. This algorithm is useful to reduce TCAMs for packet classification. In the second method, we reduce the number of words in TCAM for multi-field classification functions by using head-tail expressions. It presents MFHT, an O（r2）-algorithm to generate simplified TCAMs for two-field classification functions, where r is the number of rules. Experimental results show that MFHT achieves a 58% reduction of words for random rules and a 52% reduction of words for ACL and FW rules. Moreover, MFHT is fast. The methods are useful for simplifying TCAM for packet classification., 九州工業大学博士学位論文 学位記番号:情工博甲第291号　学位授与年月日:平成26年3月25日, 平成25年度},
 school = {九州工業大学},
 title = {Representation of Classification Functions by Head-Tail Expressions},
 year = {}
}