Representation of Classification Functions by Head-Tail Expressions

Infall, Syafalni

WEKO3

lat lon distance

[[sub_check.contents]]

[[sub_radio.contents]]

Field does not validate

[[sub_attr.contents]]　

インデックスツリー

アイテム

Representation of Classification Functions by Head-Tail Expressions

https://doi.org/10.18997/00004099

名前 / ファイル	ライセンス	アクション
D-195_jou_k_291.pdf (1.9 MB)

Item type

学位論文 = Thesis or Dissertation(1)

公開日

2014-12-05

資源タイプ

資源タイプ識別子

http://purl.org/coar/resource_type/c_db06

資源タイプ

doctoral thesis

タイトル

Representation of Classification Functions by Head-Tail Expressions

言語

eng

著者

Infall, Syafalni

抄録

内容記述タイプ

Abstract

内容記述

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.

内容記述タイプ

TableOfContents

内容記述

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

備考

内容記述タイプ

Other

内容記述

九州工業大学博士学位論文学位記番号:情工博甲第291号　学位授与年月日:平成26年3月25日

キーワード

主題Scheme

Other

主題

Logic Design

キーワード

主題Scheme

Other

主題

Prefix SOP

キーワード

主題Scheme

Other

主題

Head-Tail Expression

キーワード

主題Scheme

Other

主題

Classification Func.

キーワード

主題Scheme

Other

主題

TCAM

キーワード

主題Scheme

Other

主題

Reduction

アドバイザー

梶原, 誠司

学位授与番号

甲第291号

学位名

博士（情報工学）

学位授与年月日

2014-03-25

学位授与機関

学位授与機関識別子Scheme

kakenhi

学位授与機関識別子

17104

学位授与機関名

九州工業大学

学位授与年度

内容記述タイプ

Other

内容記述

平成25年度

出版タイプ

VoR

出版タイプResource

http://purl.org/coar/version/c_970fb48d4fbd8a85

アクセス権

open access

アクセス権URI

http://purl.org/coar/access_right/c_abf2

ID登録

10.18997/00004099

ID登録タイプ

JaLC

戻る

views

See details

	Views

Versions

Ver.1

2023-05-15 12:45:40.867268

Show All versions

Cite as

エクスポート

OAI-PMH

JPCOAR 2.0
JPCOAR 1.0
DublinCore
DDI

Other Formats

JSON
BIBTEX

インデックスリンク

インデックスツリー

アイテム

Representation of Classification Functions by Head-Tail Expressions

× Infall, Syafalni

Versions

Share

Cite as

エクスポート