Information entropy based match field cutting algorithm
With the increasing diversity of network functions,packet classification had a higher demand on the number of match fields and depth of match table,which placed a severe burden on the storage capacity of hardware.To ensure the efficiency of matching process while at the same time improve the usage o...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2017-05-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017048/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539501430669312 |
|---|---|
| author | Peng-hao SUN Ju-long LAN Shao-jun ZHANG Jun-fei LI |
| author_facet | Peng-hao SUN Ju-long LAN Shao-jun ZHANG Jun-fei LI |
| author_sort | Peng-hao SUN |
| collection | DOAJ |
| description | With the increasing diversity of network functions,packet classification had a higher demand on the number of match fields and depth of match table,which placed a severe burden on the storage capacity of hardware.To ensure the efficiency of matching process while at the same time improve the usage of storage devices,an information entropy based cutting algorithm on match fields was proposed.By the analysis on the redundancy of match fields and distribution pattern in a rule set,a match field cutting model was proposed.With the mapping of matching process to the process of entropy reduction,the complexity of optimal match field cutting was reduced from NP-hard to linear complexity.Experiment results show that compared to existing schemes,this scheme can need 40% less TCAM storage space,and on the other side,with the growing of table size,the time complexity of this algorithm is also far less than other algorithms. |
| format | Article |
| id | doaj-art-49513e250497420385e6aa18d64fe446 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2017-05-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-49513e250497420385e6aa18d64fe4462025-01-14T07:12:28ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2017-05-013818218959710587Information entropy based match field cutting algorithmPeng-hao SUNJu-long LANShao-jun ZHANGJun-fei LIWith the increasing diversity of network functions,packet classification had a higher demand on the number of match fields and depth of match table,which placed a severe burden on the storage capacity of hardware.To ensure the efficiency of matching process while at the same time improve the usage of storage devices,an information entropy based cutting algorithm on match fields was proposed.By the analysis on the redundancy of match fields and distribution pattern in a rule set,a match field cutting model was proposed.With the mapping of matching process to the process of entropy reduction,the complexity of optimal match field cutting was reduced from NP-hard to linear complexity.Experiment results show that compared to existing schemes,this scheme can need 40% less TCAM storage space,and on the other side,with the growing of table size,the time complexity of this algorithm is also far less than other algorithms.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017048/packet classificationTCAMOpenFlowinformation entropy |
| spellingShingle | Peng-hao SUN Ju-long LAN Shao-jun ZHANG Jun-fei LI Information entropy based match field cutting algorithm Tongxin xuebao packet classification TCAM OpenFlow information entropy |
| title | Information entropy based match field cutting algorithm |
| title_full | Information entropy based match field cutting algorithm |
| title_fullStr | Information entropy based match field cutting algorithm |
| title_full_unstemmed | Information entropy based match field cutting algorithm |
| title_short | Information entropy based match field cutting algorithm |
| title_sort | information entropy based match field cutting algorithm |
| topic | packet classification TCAM OpenFlow information entropy |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2017048/ |
| work_keys_str_mv | AT penghaosun informationentropybasedmatchfieldcuttingalgorithm AT julonglan informationentropybasedmatchfieldcuttingalgorithm AT shaojunzhang informationentropybasedmatchfieldcuttingalgorithm AT junfeili informationentropybasedmatchfieldcuttingalgorithm |