[發(fā)明專利]基于范圍元組搜索的在線包分類方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910026522.1
• 申請(qǐng)日: 2019-01-11
• 公開（公告）號(hào): CN109754021B
• 公開（公告）日: 2022-03-18
• 發(fā)明（設(shè)計(jì)）人: 張大方;沈潼;謝高崗;張昕怡
• 申請(qǐng)（專利權(quán)）人: 湖南大學(xué)
• 主分類號(hào): G06V10/764
• 分類號(hào): G06V10/764;G06K9/62;H04L47/2441
• 代理公司: 長(zhǎng)沙正奇專利事務(wù)所有限責(zé)任公司 43113
• 代理人: 馬強(qiáng);王娟

本發(fā)明公開了一種基于范圍元組搜索的在線包分類方法，包括數(shù)據(jù)結(jié)構(gòu)構(gòu)建方法、數(shù)據(jù)包分類查找方法和分類規(guī)則更新方法；本發(fā)明利用哈希函數(shù)保證了規(guī)則更新常數(shù)級(jí)的時(shí)間復(fù)雜度，實(shí)現(xiàn)了分類規(guī)則的快速更新；本發(fā)明將規(guī)則映射到少量范圍元組上，在保證規(guī)則更新速度的同時(shí)大大提高了數(shù)據(jù)包的分類速度；本發(fā)明能夠很好的將數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)于片上存儲(chǔ)器中，從而減少片內(nèi)存儲(chǔ)內(nèi)容的切換，提高方法的性能。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)包分類技術(shù)，特別是一種基于范圍元組搜索的在線包分類方法。

背景技術(shù)

包分類是交換機(jī)、路由器和其他網(wǎng)絡(luò)設(shè)備中用于支持安全性、QoS和高級(jí)功能的基本操作之一，其中數(shù)據(jù)包在分類器中根據(jù)多字段規(guī)則集進(jìn)行匹配。在傳統(tǒng)的網(wǎng)絡(luò)應(yīng)用中，規(guī)則保持相對(duì)靜態(tài)。因此，離線構(gòu)建的分類器通常擁有設(shè)計(jì)精良的數(shù)據(jù)結(jié)構(gòu)，這類分類器可以實(shí)現(xiàn)高效的數(shù)據(jù)包分類，且由于規(guī)則更新不頻繁，分類器可以離線構(gòu)建。

軟件定義網(wǎng)絡(luò)(SDN)的出現(xiàn)為網(wǎng)絡(luò)創(chuàng)新提供了巨大的機(jī)會(huì)，以使網(wǎng)絡(luò)支持新的特性和增值功能。這些功能包括流量工程、網(wǎng)絡(luò)功能虛擬化(NFV)和高性能云計(jì)算的支持。然而，這些新功能除了依賴于基本的快速包分類外，還依賴于分類器中規(guī)則的動(dòng)態(tài)更新能力。一方面，網(wǎng)絡(luò)應(yīng)用必須對(duì)大量的用戶和請(qǐng)求進(jìn)行即時(shí)響應(yīng)，使得分類器規(guī)則必須頻繁更新，以滿足不同的需求。另一方面，網(wǎng)絡(luò)功能的常規(guī)遷移或變更總是會(huì)改變拓?fù)浣Y(jié)構(gòu)和策略，從而分類器的規(guī)則必定會(huì)有相應(yīng)的更新。因此，快速的規(guī)則更新對(duì)于當(dāng)前的分類器是絕對(duì)必要且有意義的。

盡管包分類非常重要，并且已經(jīng)吸引了很多研究者的關(guān)注，但是現(xiàn)有的算法往往不能同時(shí)滿足上述兩個(gè)要求，即快速包分類的同時(shí)支持快速規(guī)則更新。基于決策樹的算法，如HyperCuts、EffiCuts和SmartSplit，都能實(shí)現(xiàn)快速的包分類，但不能實(shí)現(xiàn)快速的規(guī)則更新。基于哈希的算法，如在Open vSwitch(OVS)中使用的元組空間搜索(TSS)，可以實(shí)現(xiàn)快速更新規(guī)則但不能實(shí)現(xiàn)高速包分類。PartitionSort(PS)和TupleMerge(TM)可以提升包分類的速度但都犧牲了規(guī)則更新的性能。同時(shí)實(shí)現(xiàn)快速的包分類和規(guī)則更新是滿足先進(jìn)的網(wǎng)絡(luò)管理和高性能云計(jì)算的新需求和基本挑戰(zhàn)之一。

現(xiàn)有的高性能數(shù)據(jù)包分類方法由于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，不利于分類規(guī)則的快速更新，從而無法滿足當(dāng)前大量網(wǎng)絡(luò)應(yīng)用在線頻繁更新策略或規(guī)則的需求。

現(xiàn)有的支持規(guī)則快速分類的數(shù)據(jù)包分類方法，雖然可以提供分類規(guī)則的在線更新，但是其數(shù)據(jù)包分類速度達(dá)不到大部分網(wǎng)絡(luò)功能的需求。

包分類模塊通常會(huì)被部署在FPGA、TCAM或其它專用芯片上。而這類芯片的片上存儲(chǔ)器大小往往比較小。現(xiàn)有包分類方法所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)占有較大的運(yùn)行內(nèi)存，或者運(yùn)行內(nèi)存非常不穩(wěn)定(隨規(guī)則的種類有較大波動(dòng))。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是，針對(duì)現(xiàn)有技術(shù)不足，提供一種基于范圍元組搜索的在線包分類方法，實(shí)現(xiàn)分類規(guī)則的快速更新，在保證規(guī)則更新速度的同時(shí)大大提高數(shù)據(jù)包的分類速度。

為解決上述技術(shù)問題，本發(fā)明所采用的技術(shù)方案是：一種基于范圍元組搜索的在線包分類方法，包括數(shù)據(jù)結(jié)構(gòu)構(gòu)建方法、數(shù)據(jù)包分類查找方法和分類規(guī)則更新方法；-

所述數(shù)據(jù)結(jié)構(gòu)構(gòu)建方法包含以下步驟：

1)按照規(guī)則的每個(gè)維度，分別計(jì)算隨著某一維度字段長(zhǎng)度的增長(zhǎng)規(guī)則數(shù)量的累計(jì)分布曲線；并根據(jù)該曲線斜率定位聚類點(diǎn)；-

2)連接每個(gè)維度中相鄰的聚類點(diǎn)，相鄰的連接聚類點(diǎn)稱為一個(gè)小范圍；若某一聚類點(diǎn)沒有相鄰的聚類點(diǎn)，則該聚類點(diǎn)自身稱為一個(gè)小范圍；

3)合并每個(gè)維度中相鄰的兩個(gè)小范圍；

4)向后對(duì)齊合并后的小范圍成為一個(gè)范圍，確保所有范圍的并集覆蓋規(guī)則集中所有的規(guī)則；