[發(fā)明專利]一種OpenFlow流表存儲(chǔ)空間壓縮方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310581078.2
• 申請(qǐng)日: 2013-11-18
• 公開（公告）號(hào): CN103560963A
• 公開（公告）日: 2014-02-05
• 發(fā)明（設(shè)計(jì)）人: 葛敬國;吳玉磊;鄂躍鵬;游軍玲;陳智;李佟;韓春靜
• 申請(qǐng)（專利權(quán)）人: 中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心
• 主分類號(hào): H04L12/741
• 分類號(hào): H04L12/741;G06F12/02;G06F12/08
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長江

1.一種OpenFlow流表存儲(chǔ)空間壓縮方法，其步驟包括：

1）根據(jù)OpenFlow流表的結(jié)構(gòu)，確定同一傳輸單元中流表項(xiàng)字段之間的沖突關(guān)系與共存關(guān)系；

2）利用所述沖突關(guān)系與共存關(guān)系對(duì)OpenFlow流表進(jìn)行分類，將字段可共存的流表項(xiàng)劃分到一個(gè)類中、字段不可共存的流表項(xiàng)劃分到不同類中進(jìn)行存儲(chǔ)；

3）將初始流表項(xiàng)添加到劃分好的OpenFlow流表類中；

4）根據(jù)OpenFlow流表的頻繁、快速更新特性設(shè)定動(dòng)態(tài)調(diào)整閥值，當(dāng)新加入的流表項(xiàng)條數(shù)超過限定的閥值時(shí)，對(duì)現(xiàn)有的類進(jìn)行分裂操作，當(dāng)類的個(gè)數(shù)超過限定的閥值時(shí)，對(duì)現(xiàn)有的類進(jìn)行合并操作，以優(yōu)化流表存儲(chǔ)空間。

2.如權(quán)利要求1所述的方法，其特征在于：步驟1）所述沖突關(guān)系是指不能在同一傳輸單元中同時(shí)出現(xiàn)的字段，所述共存關(guān)系是指能夠在同一傳輸單元中同時(shí)出現(xiàn)的字段。

3.如權(quán)利要求1所述的方法，其特征在于：步驟2）對(duì)流表進(jìn)行劃分的具體方法為：利用所述沖突關(guān)系與共存關(guān)系，將初始流表劃分成兩個(gè)類，在所劃分的兩個(gè)類中選擇出可以再進(jìn)行分裂且存儲(chǔ)代價(jià)最大的類，再利用所述沖突關(guān)系與共存關(guān)系劃分成兩個(gè)類，以此類推；如果所有的類都已進(jìn)行過分裂或類的分裂個(gè)數(shù)大于類的限定閥值時(shí)，結(jié)束分裂操作；其中存儲(chǔ)代價(jià)表示該類存儲(chǔ)的有效字段所占用的字節(jié)數(shù)。

4.如權(quán)利要求1所述的方法，其特征在于：步驟3）通過迭代步驟2）已經(jīng)劃分的所有類，把每個(gè)類的有效字段集合所對(duì)應(yīng)向量中的每一位減去流表項(xiàng)中對(duì)應(yīng)的向量位，得到向量位差值絕對(duì)值之和以及向量位差值之和；比較這兩個(gè)值，當(dāng)二者相等時(shí)，則該流表項(xiàng)可以加入到該類中；在所有可能加入的類中選擇存儲(chǔ)代價(jià)增加最小的類完成加入。

5.如權(quán)利要求1所述的方法，其特征在于：步驟4）中當(dāng)新加入的流表項(xiàng)條數(shù)超過限定的閥值時(shí)，對(duì)現(xiàn)有的類進(jìn)行分裂操作的方法為：將下一條新流表項(xiàng)加入到某個(gè)類中，列舉所有對(duì)該類進(jìn)行預(yù)分裂成兩個(gè)類的可能的操作，并計(jì)算每種可能的分裂情況下的存儲(chǔ)空間大小；通過比較所有可能的分裂情況下所計(jì)算出的存儲(chǔ)空間大小，選擇存儲(chǔ)空間減少最多的一個(gè)分裂情況；將該類按照這種方式進(jìn)行分裂成兩個(gè)類，并刪除原類。

6.如權(quán)利要求5所述的方法，其特征在于，進(jìn)行所述分裂操作時(shí)計(jì)算減小的存儲(chǔ)空間的方法為：假設(shè)選擇類A進(jìn)行預(yù)分裂計(jì)算，將其分裂成類A1和類A2，則遍歷類A中的所有流表項(xiàng)，分別預(yù)加入到類A1和類A2中，減少的存儲(chǔ)空間為：類A存儲(chǔ)代價(jià)*類A流表項(xiàng)條數(shù)–類A1存儲(chǔ)代價(jià)*類A1流表項(xiàng)條數(shù)-類A2存儲(chǔ)代價(jià)*類A2流表項(xiàng)條數(shù)。

7.如權(quán)利要求1所述的方法，其特征在于：步驟4）中當(dāng)類的個(gè)數(shù)超過限定的閥值時(shí)，對(duì)現(xiàn)有的類進(jìn)行合并操作的方法為：列舉所有選擇任意兩個(gè)類進(jìn)行預(yù)合并成一個(gè)類的可能情況，并計(jì)算每種可能的合并情況下的存儲(chǔ)空間大小；通過比較所有可能的合并情況下計(jì)算出的存儲(chǔ)空間大小，選擇存儲(chǔ)空間增加最少的一個(gè)合并可能；合并這兩個(gè)類產(chǎn)生一個(gè)新類。

8.如權(quán)利要求7所述的方法，其特征在于：進(jìn)行所述合并操作時(shí)計(jì)算增加的存儲(chǔ)空間的方法為：假設(shè)選擇類B和類C進(jìn)行合并，合并后增加的存儲(chǔ)空間為：合并后的類存儲(chǔ)代價(jià)*合并后的類中流表項(xiàng)條數(shù)–類B的存儲(chǔ)代價(jià)*類B的流表項(xiàng)條數(shù)–類C的存儲(chǔ)代價(jià)*類C的流表項(xiàng)條數(shù)。

9.如權(quán)利要求1所述的方法，其特征在于：OpenFlow流表項(xiàng)字段采用OpenFlow1.3標(biāo)準(zhǔn)支持的所有字段。

10.如權(quán)利要求1所述的方法，其特征在于：對(duì)類的分裂個(gè)數(shù)限定的閥值不小于4。