多單元散列表與TCAM結(jié)合的OpenFlow流表查找方法

李春強(qiáng)，董永強(qiáng),2，吳國(guó)新,2

（1.東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189；2.東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 211189）

多單元散列表與TCAM結(jié)合的OpenFlow流表查找方法

李春強(qiáng)1，董永強(qiáng)1,2，吳國(guó)新1,2

（1.東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189；2.東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 211189）

在OpenFlow網(wǎng)絡(luò)中，交換機(jī)通過(guò)標(biāo)準(zhǔn)化的接口接受基于流的規(guī)則，執(zhí)行基于流的報(bào)文處理。流表的查找是OpenFlow交換機(jī)的核心功能，TCAM以其優(yōu)異的性能廣泛用于OpenFlow流表的查找，然而基于TCAM的OpenFlow流表查找具有較高的成本與能耗。為了降低流表查找的成本與能耗，提出了多單元散列表與TCAM結(jié)合的OpenFlow流表存儲(chǔ)與查找的方法。通過(guò)理論分析與仿真測(cè)試，給出了查找結(jié)構(gòu)成本優(yōu)化后的散列表、TCAM的容量配置；在該配置下，Hash-TCAM流表查找結(jié)構(gòu)比單純使用TCAM的方案節(jié)約90%以上的成本，有效降低了能耗，同時(shí)保持了相近的查找性能。

OpenFlow；三態(tài)內(nèi)容尋址存儲(chǔ)器；散列表；流表

1 引言

為了在已有的網(wǎng)絡(luò)基礎(chǔ)設(shè)施中構(gòu)建網(wǎng)絡(luò)創(chuàng)新研究的實(shí)驗(yàn)環(huán)境，軟件定義網(wǎng)絡(luò)（SDN, software defined networking）作為一種新型的網(wǎng)絡(luò)體系結(jié)構(gòu)被提出，OpenFlow[1]技術(shù)作為實(shí)現(xiàn) SDN的一種具體方案，受到了學(xué)術(shù)界和工業(yè)界的普遍關(guān)注和廣泛研究。OpenFlow系統(tǒng)實(shí)現(xiàn)了數(shù)據(jù)轉(zhuǎn)發(fā)和控制功能的分離，通過(guò)獨(dú)立的控制器來(lái)控制網(wǎng)絡(luò)設(shè)備(稱(chēng)為OpenFlow交換機(jī))的轉(zhuǎn)發(fā)行為；OpenFlow控制器在邏輯上采用集中式的控制方式，OpenFlow交換機(jī)通過(guò)標(biāo)準(zhǔn)化的接口接收來(lái)自控制器的報(bào)文處理規(guī)則，執(zhí)行基于流的報(bào)文處理。OpenFlow機(jī)制以其良好的可編程、可控制等特性，已被應(yīng)用于數(shù)據(jù)中心、企業(yè)網(wǎng)、校園網(wǎng)中網(wǎng)絡(luò)流量的管理與控制。

流表是OpenFlow機(jī)制的核心，它是流表項(xiàng)的集合，流表項(xiàng)的基本格式如圖1所示，主要有匹配字段（Match Fields）、計(jì)數(shù)器（Counters）和操作（Instructions）等部分組成，其中，匹配字段可以包含多個(gè)匹配項(xiàng)，涵蓋了鏈路層、網(wǎng)絡(luò)層和傳輸層等層次的報(bào)文頭部字段，計(jì)數(shù)器根據(jù)匹配到的報(bào)文進(jìn)行統(tǒng)計(jì)，操作則指明匹配到該流表項(xiàng)的報(bào)文應(yīng)該執(zhí)行的操作，比如轉(zhuǎn)發(fā)、丟棄、修改等。

圖1OpenFlow流表項(xiàng)格式

隨著OpenFlow規(guī)范的不斷更新，流表項(xiàng)匹配字段從最初的十元組[1]（如圖2所示），逐步增加了VLAN優(yōu)先級(jí)等字段，后續(xù)MPLS和IPv6等協(xié)議字段也逐漸擴(kuò)展到OpenFlow標(biāo)準(zhǔn)[2～4]中，流表的匹配字段越來(lái)越長(zhǎng)，流表的規(guī)模越來(lái)越大。OpenFlow交換機(jī)收到數(shù)據(jù)報(bào)文后，提取報(bào)文的頭部信息查詢(xún)OpenFlow流表，根據(jù)流表中匹配到的規(guī)則對(duì)報(bào)文執(zhí)行相應(yīng)的操作；為了實(shí)現(xiàn)高速的流表匹配，OpenFlow交換機(jī)通常采用三重內(nèi)容可尋址存儲(chǔ)器(TCAM, ternary content addressable memory)存儲(chǔ)與查找流表[1,2,5]，這種不斷擴(kuò)展的數(shù)據(jù)轉(zhuǎn)發(fā)面抽象，需要占用大量的TCAM資源，大大增加了硬件成本。

TCAM可以完全并行地查找整個(gè)數(shù)據(jù)字段的集合，具有優(yōu)異的查找性能。然而TCAM這種高性能并行查找機(jī)制帶來(lái)了高的能耗與散熱問(wèn)題；同時(shí)TCAM的成本也非常高，TCAM單比特成本大約相當(dāng)于靜態(tài)隨機(jī)存儲(chǔ)器(SRAM, static random access memory)的30倍[6]；TCAM能耗也明顯超出SRAM數(shù)倍[6,7]，并且會(huì)隨并行匹配字段的條目數(shù)及寬度而增加[7]。設(shè)備的成本與性能決定了一項(xiàng)技術(shù)能否被推廣與普及，因此，降低OpenFlow交換機(jī)的成本與能耗是目前亟待解決的關(guān)鍵問(wèn)題。OpenFlow流表的查找是其核心功能，實(shí)現(xiàn)高性能、低成本、低能耗的流表查找成為OpenFlow交換機(jī)實(shí)現(xiàn)的基本要求。

針對(duì)基于TCAM的OpenFlow流表查找方案具有較高能耗與成本的問(wèn)題，提出了將多單元散列表與 TCAM 結(jié)合的 OpenFlow流表存儲(chǔ)與查找的方法。本文的主要貢獻(xiàn)包括以下幾點(diǎn)。

1) 提出將多單元散列表與 TCAM 結(jié)合的OpenFlow流表存儲(chǔ)與查找的方法，使用連續(xù)的存儲(chǔ)空間存儲(chǔ)位于同一散列桶中的多個(gè)查找單元，其中每個(gè)查找單元包含一個(gè)流表表項(xiàng)的索引信息。

2) 分析了散列表的沖突溢出率，根據(jù)散列沖突溢出的變化率，展示了多單元散列表—TCAM查找結(jié)構(gòu)以及二級(jí)多單元散列表—TCAM具有良好的成本優(yōu)勢(shì)。

3) 在散列表中，通過(guò)流表表項(xiàng)關(guān)鍵字指紋代替關(guān)鍵字的匹配減少單次存儲(chǔ)器讀操作的數(shù)據(jù)位數(shù)，并進(jìn)一步降低了散列表的成本。

4) 通過(guò)理論分析有效配置TCAM與散列表的容量，優(yōu)化了OpenFlow流表的存儲(chǔ)與查找的成本及能耗，并通過(guò)仿真測(cè)試進(jìn)行了驗(yàn)證。

圖2十元組格式的流表項(xiàng)匹配字段

2 相關(guān)技術(shù)介紹

2.1 降低流表存儲(chǔ)開(kāi)銷(xiāo)及能耗的研究

隨著OpenFlow應(yīng)用范圍的擴(kuò)大，OpenFlow流表的規(guī)模越來(lái)越大，匹配字段的位數(shù)越來(lái)越多，從OpenFlow1.1版[2]開(kāi)始提出了通過(guò)多級(jí)流表和流水線查找結(jié)構(gòu)來(lái)壓縮流表存儲(chǔ)空間，但其壓縮效果與流表表項(xiàng)匹配字段的具體內(nèi)容密切相關(guān)。當(dāng)級(jí)數(shù)較多時(shí)會(huì)顯著增加報(bào)文處理的時(shí)延，同時(shí)增加了OpenFlow交換機(jī)硬件設(shè)計(jì)的復(fù)雜度。文獻(xiàn)[8～12]提出了基于分解的OpenFlow流表匹配方法，按照流表匹配字段在報(bào)文頭部的協(xié)議層次，將OpenFlow流表劃分成多個(gè)子表；進(jìn)行規(guī)則匹配時(shí)，報(bào)文頭被分割成多個(gè)字段，每個(gè)字段獨(dú)立地執(zhí)行查找操作；根據(jù)每個(gè)查找操作的返回結(jié)果合并后，再執(zhí)行一次查找獲得匹配的流表規(guī)則。該類(lèi)方案的主要問(wèn)題在于流表一個(gè)條目的更新可能會(huì)涉及子表中的多個(gè)條目，更新過(guò)程較為復(fù)雜。

文獻(xiàn)[13,14]提出了通過(guò)壓縮流表減少 TCAM使用的方案，采用啟發(fā)式方法，求解語(yǔ)義等同的流表集合，結(jié)果導(dǎo)致壓縮的效果與流表的內(nèi)容密切相關(guān)，壓縮比不確定，而且無(wú)法支持實(shí)時(shí)更新流表的條目。文獻(xiàn)[15,16]提出了基于決策樹(shù)的 OpenFlow流表匹配方案，同樣采用啟發(fā)式算法構(gòu)建匹配規(guī)則的決策樹(shù)，需要多次查表才能確定匹配的流表?xiàng)l目；匹配字段位數(shù)越多，查找的時(shí)延越高，查找的性能受到限制。

為了降低OpenFlow流表匹配的能耗，文獻(xiàn)[5]根據(jù)數(shù)據(jù)報(bào)文的局部性，通過(guò)增加報(bào)文預(yù)測(cè)電路，通過(guò)緩存某段時(shí)間內(nèi)頻繁訪問(wèn)的流表?xiàng)l目來(lái)嘗試減少與TCAM中流表進(jìn)行匹配的操作。該方案雖然考慮了降低OpenFlow交換機(jī)功耗與時(shí)延的問(wèn)題，但并未降低基于TCAM的OpenFlow流表存儲(chǔ)與查找的成本。

2.2 基于散列表的存儲(chǔ)與查找

散列表具有良好的平均查找性能且易于實(shí)現(xiàn)，因此將散列表應(yīng)用到網(wǎng)絡(luò)報(bào)文處理上得到了廣泛的研究[17]。當(dāng)多個(gè)關(guān)鍵字通過(guò)散列運(yùn)算映射到同一個(gè)散列桶，稱(chēng)為散列沖突，散列沖突是影響散列查找性能的主要因素，如何有效處理散列沖突是散列表實(shí)現(xiàn)高效查找的關(guān)鍵。通常，借助于鏈表（拉鏈法）或開(kāi)放地址探測(cè)（開(kāi)放定址法）等方式解決散列沖突。但無(wú)論是拉鏈法還是開(kāi)放定址法，當(dāng)待查找的條目存在散列沖突時(shí)，需要多次存儲(chǔ)器訪問(wèn)才能獲得查找結(jié)果，因此不能確保最差情形下的查找性能。

文獻(xiàn)[18]提出一種基于開(kāi)放地址探測(cè)的散列沖突處理方案，該方案中使用2個(gè)子散列表，每個(gè)條目插入時(shí)在2個(gè)子表中各有一個(gè)候選的位置，但只插入到其中一個(gè)。當(dāng)插入一個(gè)新條目時(shí)，根據(jù)關(guān)鍵字使用不同的散列函數(shù)計(jì)算在2個(gè)子表中的位置，只要任意一個(gè)位置為空則可以將該條目插入該空位置；當(dāng)2個(gè)位置均非空時(shí)，選擇一個(gè)子表的位置將新條目插入，并將被替換的條目插入到另一表中的候選位置，如果另一表中的相應(yīng)位置非空，繼續(xù)進(jìn)行迭代，直到找到一個(gè)空閑的位置；如果經(jīng)過(guò)一定的迭代次數(shù)仍無(wú)法找到空閑位置，則需要執(zhí)行rehash操作或者將被替代的條目放入TCAM[19]。對(duì)于該方案而言，通過(guò)并行地查找2個(gè)子散列表，可以確保查找的性能；然而在插入新條目時(shí)，可能需要多次移動(dòng)表中的條目，插入的性能是不確定的，無(wú)法滿(mǎn)足流表的實(shí)時(shí)更新要求。

基于散列表的存儲(chǔ)與查找方案雖然可以使用SRAM、短時(shí)延動(dòng)態(tài)隨機(jī)存儲(chǔ)器(RLDRAM, reduced-latency dynamic random access memory)等功耗、成本相對(duì)較低的存儲(chǔ)器，但隨著散列表利用率的增加，散列沖突出現(xiàn)的概率也會(huì)增加，從而會(huì)導(dǎo)致散列表處理性能下降、查找性能不確定的問(wèn)題，這對(duì)高速網(wǎng)絡(luò)報(bào)文處理是難以容忍的；基于TCAM的OpenFlow流表存儲(chǔ)與查找方案，可以實(shí)現(xiàn)高效確保的查找性能，但其成本與功耗相對(duì)較高，這會(huì)影響OpenFlow技術(shù)的普及與推廣。因此，本文將這2種方案進(jìn)行結(jié)合，對(duì)以流量管理[20,21]或報(bào)文轉(zhuǎn)發(fā)[22]為主要功能的OpenFlow交換機(jī)，降低其流表存儲(chǔ)與查找的成本及能耗。

3 Hash-TCAM混合流表存儲(chǔ)與查找方案

圖3(a)給出了常規(guī)的Hash-TCAM混合流表查找結(jié)構(gòu)。由于使用網(wǎng)絡(luò)處理器(NP, network processor)[23,24]、專(zhuān)用集成電路(ASIC, application specific integrated circuits)執(zhí)行報(bào)文處理是OpenFlow交換機(jī)常見(jiàn)的實(shí)現(xiàn)方式，如果NP或ASIC帶有一定容量的片內(nèi)TCAM[25]，則流表的查找結(jié)構(gòu)如圖3(b)所示。

圖3Hash-TCAM混合流表查找結(jié)構(gòu)

方案的基本思路是將散列表作為OpenFlow流表的精確匹配與存儲(chǔ)的主要措施，用TCAM處理散列表的沖突溢出。通常，TCAM每個(gè)時(shí)鐘周期都可以執(zhí)行一次查找，SRAM每個(gè)時(shí)鐘周期也可以執(zhí)行一次讀操作，在沒(méi)有散列沖突溢出的情況下，散列查找只需要執(zhí)行一次 SRAM 讀操作就可以查到對(duì)應(yīng)條目，因此將沖突溢出的條目存儲(chǔ)到TCAM中，避免因多次SRAM讀操作導(dǎo)致的查找性能下降，于是每個(gè)時(shí)鐘周期均可以執(zhí)行一次OpenFlow流表的查找操作，確保了流表的查找性能。

3.1 OpenFlow流表存儲(chǔ)成本優(yōu)化的問(wèn)題

Hash-TCAM 混合流表方案的目標(biāo)是通過(guò)合理分配散列表與TCAM的容量，優(yōu)化Hash-TCAM混合流表查找結(jié)構(gòu)的成本，降低其能耗，實(shí)現(xiàn)高性能的流表存儲(chǔ)與查找。由于混合查找結(jié)構(gòu)的成本由散列表與 TCAM 2部分組成，設(shè)散列表的總成本為CH，TCAM表的總成本為CT，總的流表?xiàng)l目數(shù)為N，散列表容量為 H個(gè)散列桶，散列表的負(fù)載系數(shù)單個(gè)散列桶容納的關(guān)鍵字條目數(shù)為ω，單個(gè)散列條目的成本為Ch，散列表沖突溢出的條目數(shù)為Θ，TCAM的容量為T(mén)個(gè)條目，單個(gè)TCAM條目的成本為Ct，則Hash-TCAM混合流表查找結(jié)構(gòu)的成本優(yōu)化問(wèn)題可以記為

其中，式(1)中 Ctotal表示整個(gè)存儲(chǔ)與查找結(jié)構(gòu)的總成本，為優(yōu)化的目標(biāo)函數(shù)；式(2)的不等式是約束條件，表示 TCAM 的容量不少于散列沖突溢出的條目數(shù)；式(3)和式(4)分別表示散列表和 TCAM 的成本。取TCAM的容量恰好可容納散列表沖突溢出的條目數(shù)

對(duì)于容量為 H個(gè)散列桶、單散列桶容量為 ω條目的散列表，散列表容量為h個(gè)條目，則

記單個(gè) TCAM 條目的成本為散列條目成本的m倍，即

將式(5)～式(7)代入式(1)得

由于散列表的成本CH是散列表容量的增函數(shù)；TCAM的成本由散列沖突溢出的條目數(shù)Θ決定，對(duì)于相同結(jié)構(gòu)的散列表，散列沖突溢出的條目數(shù)Θ隨散列表容量增加而減少，是散列表容量h的減函數(shù)，記 Θ=Θ(h)。通過(guò)分析散列容量 h的變化對(duì)總成本Ctotal的影響，可以得出 OpenFlow流表存儲(chǔ)與查找結(jié)構(gòu)最優(yōu)成本下的散列表及TCAM各自的容量配置。記 Δh為散列表?xiàng)l目數(shù)的增量，散列表容量 h+Δh下的混合存儲(chǔ)與查找結(jié)構(gòu)的成本為則

由式(9)可得出

3.2 散列表的沖突分析

對(duì)于散列查找而言，當(dāng)出現(xiàn)散列沖突時(shí)，可能需要多次訪問(wèn)存儲(chǔ)器，而存儲(chǔ)器的訪問(wèn)是影響查找性能的關(guān)鍵因素。為了減少查找過(guò)程中存儲(chǔ)器的訪問(wèn)次數(shù)、保持高的查找性能，本文采用多單元散列表，即單個(gè)散列桶使用連續(xù)的存儲(chǔ)空間容納多個(gè)查找單元，其中，每個(gè)查找單元包含一個(gè)散列條目。通過(guò)這樣的設(shè)計(jì)，一次存儲(chǔ)器讀操作可以讀取多個(gè)散列條目。

散列表的沖突溢出條目數(shù)跟散列表的負(fù)載系數(shù)及結(jié)構(gòu)密切相關(guān)，不同的散列表結(jié)構(gòu)在使用相同容量存儲(chǔ)器的情形下，沖突溢出條目數(shù)不同，稱(chēng)為散列表的沖突溢出率。下面分析不同結(jié)構(gòu)及負(fù)載系數(shù)下的沖突溢出率。采用具有良好隨機(jī)性的循環(huán)冗余校驗(yàn)(CRC, cyclic redundancy check)作為散列函數(shù)，N個(gè)數(shù)據(jù)隨機(jī)分布在H個(gè)鍵值中，對(duì)于任意一個(gè)特定的鍵值，每個(gè)數(shù)據(jù)進(jìn)入這一鍵值的概率為，N個(gè)數(shù)據(jù)中恰好有k個(gè)進(jìn)入這一鍵值的概率服從二項(xiàng)分布，其中，；即散列桶中恰好有k 個(gè)條目的概率其中

對(duì)于單條目散列桶的普通散列表，負(fù)載系數(shù)為λ時(shí)，沖突溢出率可按式(11)計(jì)算。

對(duì)于散列桶容量為ω的多單元散列表，負(fù)載系數(shù)為λ時(shí)，沖突溢出率可按式(12)計(jì)算。

為了比較多單元散列表與普通散列表在相同容量下的沖突溢出率，取散列桶數(shù)目為N、負(fù)載系數(shù)為1的多單元散列表與散列桶容量為1、負(fù)載系數(shù)為的普通散列表進(jìn)行分析。根據(jù)式(11)和式(12)可得出兩者的沖突溢出率隨散列表容量的變化趨勢(shì)，如圖4所示。

圖4散列沖突溢出率隨散列表的容量增加的變化趨勢(shì)

從圖4可以看出，在相同散列表容量情形下，多單元散列表的沖突溢出率明顯低于普通散列表的沖突溢出率；而且隨著散列表容量增加，多單元散列表的沖突溢出率下降幅度也明顯大于普通散列表。因此，在數(shù)據(jù)總線寬度允許的條件下，應(yīng)盡可能選擇單元數(shù)多的多單元散列表存儲(chǔ)與查找OpenFlow流表，以?xún)?yōu)化流表的存儲(chǔ)與查找成本。

表1多單元散列表沖突溢出率

根據(jù)式(12)，表 1給出了多單元散列表不同的散列桶單元數(shù)目、負(fù)載系數(shù)λ下的沖突溢出率。對(duì)于表1中散列桶單元數(shù)為ω、負(fù)載系數(shù)為λ的散列表，散列桶的數(shù)目為，表的容量為；散列桶單元數(shù)同為 ω，負(fù)載系數(shù)分別為 λ、λ+1相鄰的 2個(gè)表格單元，其容量差為，根據(jù)式(10)可知，當(dāng)兩者的沖突溢出率差值接近時(shí)，其存儲(chǔ)與查找結(jié)構(gòu)的成本接近最優(yōu)值。

3.3 多單元散列表的結(jié)構(gòu)及處理方法

3.3.1 存儲(chǔ)與查找結(jié)構(gòu)

由于OpenFlow流表表項(xiàng)的匹配關(guān)鍵字包含的位數(shù)非常多(OpenFlow1.0規(guī)范中至少包含228 bit)，為了能夠?qū)崿F(xiàn)多個(gè)單元的并行比較，需要對(duì)匹配關(guān)鍵字進(jìn)行壓縮，可以使用具有良好隨機(jī)性的散列函數(shù)將流表的匹配關(guān)鍵字壓縮成位數(shù)較少的固定長(zhǎng)度的指紋(fingerprint)[26]，在散列查找時(shí)通過(guò)指紋的比較發(fā)現(xiàn)匹配的流表表項(xiàng)?；诙鄦卧⒘斜淼腛penFlow流表結(jié)構(gòu)如圖5所示，每個(gè)散列桶包含ω個(gè)查找單元，每個(gè)查找單元由標(biāo)識(shí)位、指紋、流表指針3個(gè)部分組成，其中，標(biāo)識(shí)位表示該查找單元中的流表?xiàng)l目是否有效，在刪除流表表項(xiàng)時(shí)只要將對(duì)應(yīng)的標(biāo)識(shí)位置為無(wú)效即可，表項(xiàng)指針指向具體的流表?xiàng)l目。

圖5基于多單元散列表的OpenFlow流表結(jié)構(gòu)

3.3.2處理流程

圖6是Hash-TCAM OpenFlow流表查找的處理流程，其輸入為匹配關(guān)鍵字key。TCAM的查找操作與SRAM的讀操作可以并行的執(zhí)行，當(dāng)TCAM查找操作返回的流表項(xiàng)指針有效時(shí)，直接根據(jù)該流表指針讀取流表?xiàng)l目，不必再判斷寄存器Registers中的內(nèi)容及后續(xù)操作。當(dāng)TCAM查找操作返回的流表指針無(wú)效時(shí)，則需要根據(jù)寄存器中的指紋判斷散列表中是否存在匹配的流表表項(xiàng)，如果存在匹配的指紋，則根據(jù)對(duì)應(yīng)的流表指針讀取相應(yīng)的流表?xiàng)l目，并比較流表?xiàng)l目中的關(guān)鍵字與查找使用的關(guān)鍵字是否一致，如果不一致，則說(shuō)明存在指紋沖突需要插入新的流表?xiàng)l目。當(dāng)在TCAM與散列表中均未查找到匹配的流表?xiàng)l目，則請(qǐng)求插入新的流表?xiàng)l目。

圖6Hash-TCAM OpenFlow流表查找流程

圖7是Hash-TCAM OpenFlow流表表項(xiàng)插入的處理流程，其輸入為流表關(guān)鍵字key及流表?xiàng)l目，在當(dāng)前流表中未發(fā)現(xiàn)流表關(guān)鍵字key對(duì)應(yīng)的流表?xiàng)l目時(shí)，則執(zhí)行流表表項(xiàng)的插入。插入新的流表?xiàng)l目時(shí)，首先嘗試向散列表中插入，如果由于散列沖突溢出或指紋沖突，則插入到TCAM 中。在刪除散列表中的流表?xiàng)l目時(shí)，只需要將標(biāo)識(shí)位置為無(wú)效即可。

3.4 匹配關(guān)鍵字指紋

將取值范圍較大的匹配關(guān)鍵字映射到取值范圍較小的指紋，可能會(huì)發(fā)生不同的匹配關(guān)鍵字映射到同一個(gè)指紋的現(xiàn)象，稱(chēng)之為指紋沖突。為了確保查找的性能，需要將發(fā)生指紋沖突的匹配關(guān)鍵字存儲(chǔ)在TCAM中。較少位數(shù)的指紋意味著散列表的容量小、成本低；但位數(shù)越少，指紋沖突的概率就越大，增加TCAM的成本，同時(shí)影響查找結(jié)構(gòu)的性能。下面分析指紋沖突的發(fā)生率與指紋位數(shù)的關(guān)系。記位于同一散列桶的n個(gè)單元的指紋不出現(xiàn)沖突的概率為 Pnc(n)，指紋的位數(shù)為 w，任意關(guān)鍵字映射到指紋后隨機(jī)地分布在[0, 2w?1]的范圍內(nèi)，n個(gè)單元均不存在指紋沖突的概率為

圖7Hash-TCAM OpenFlow流表表項(xiàng)插入處理流程

式(13)中 U=2w，指紋沖突率 Pc≤1?Pnc(n)，即

根據(jù)式(14)，圖8給出了2單元至8單元散列表的指紋沖突率上限與指紋位數(shù)的關(guān)系，從圖8可以看出，當(dāng)指紋的位數(shù)越多，沖突率的上限越小，對(duì)于多單元散列表，單元數(shù)目越多指紋沖突率上限越大；當(dāng)指紋位數(shù)超過(guò)21 bit時(shí)，沖突溢出率的上限低于10?5。指紋發(fā)生沖突的概率上限與指紋的位數(shù)相關(guān)，而與匹配關(guān)鍵字的原始位數(shù)無(wú)關(guān)。

圖8多單元散列表的指紋沖突率上限

3.5 兩級(jí)多單元散列表的結(jié)構(gòu)及操作

3.5.1 存儲(chǔ)與查找結(jié)構(gòu)

多級(jí)散列表[27,28]在實(shí)現(xiàn)散列表高利用率的同時(shí)，可以有效降低散列沖突的溢出率。然而如果散列表的級(jí)數(shù)較多，當(dāng)執(zhí)行刪除操作時(shí)，則需要在不同級(jí)的子表之間執(zhí)行散列條目的移動(dòng)，才能保持低的沖突溢出概率[29]；而散列條目的移動(dòng)會(huì)影響整個(gè)散列表的操作性能，而且散列表的級(jí)數(shù)過(guò)多，也會(huì)增加電路設(shè)計(jì)的復(fù)雜度，增加查找的成本與能耗。因此，為了進(jìn)一步降低 OpenFlow流表的查找成本，提出了兩級(jí)多單元散列表的OpenFlow流表查找結(jié)構(gòu)，如圖9所示。該結(jié)構(gòu)使用了主表與輔表兩級(jí)子表，每個(gè)子表都使用多單元散列表；為了便于實(shí)現(xiàn)，每個(gè)子表的散列桶的單元數(shù)也相同，每個(gè)查找單元的格式與 3.3節(jié)中的相同。

圖9兩級(jí)多單元散列表的詳細(xì)結(jié)構(gòu)

圖10兩級(jí)多單元Hash-TCAM OpenFlow流表查找處理流程

3.5.2 處理流程

圖 10是兩級(jí)多單元 Hash-TCAM OpenFlow流表查找的處理流程，其輸入為匹配關(guān)鍵字key。在執(zhí)行關(guān)鍵字查找時(shí)，TCAM查找與散列查找并行執(zhí)行；對(duì)于散列查找，主表與輔表SRAM的讀操作也并行地執(zhí)行；當(dāng)TCAM查找操作返回的流表項(xiàng)指針無(wú)效時(shí)，需要根據(jù) Register1、Register2中的內(nèi)容判斷散列表中是否存在匹配的流表項(xiàng)，否則直接根據(jù)TCAM中返回的流表項(xiàng)指針讀取流表?xiàng)l目，不必再判斷 Register中的內(nèi)容及其后續(xù)操作。

圖11是兩級(jí)多單元Hash-TCAM OpenFlow流表表項(xiàng)插入的處理流程，其輸入為：流表關(guān)鍵字key及流表?xiàng)l目。在流表中未查找到流表關(guān)鍵字key對(duì)應(yīng)的流表?xiàng)l目時(shí)，則執(zhí)行流表表項(xiàng)的插入。插入新的流表?xiàng)l目時(shí)，首先嘗試向散列表的主表中插入，如果由于散列沖突溢出或指紋沖突，則嘗試向散列表的輔表中插入，如果仍然存在散列沖突溢出或指紋沖突，則插入到TCAM中。

圖11兩級(jí)多單元Hash-TCAM OpenFlow流表插入處理流程

3.5.3 散列沖突溢出分析

下面分析散列桶單元數(shù)相同，兩級(jí)多單元散列表與單級(jí)多單元散列表的沖突溢出率。設(shè)單級(jí)多單元散列表容量為H個(gè)散列桶，單個(gè)散列桶的容量為2ω個(gè)查找單元，負(fù)載系數(shù)為 2λ，沖突溢出率可按式(15)計(jì)算

設(shè)兩級(jí)多單元散列表主表容量為H個(gè)散列桶，單個(gè)散列桶的容量為ω個(gè)查找單元，主表的沖突溢出率ε可按式(16)計(jì)算。

輔表容量為ε(ω, λ)的H個(gè)散列桶，單個(gè)散列桶的容量同樣為ω個(gè)查找單元，負(fù)載系數(shù)為λ，則兩級(jí)多單元散列表的沖突溢出率可按式(17)計(jì)算。

兩級(jí)多單元散列表的總?cè)萘繛?1+ε(ω,λ))Hω 個(gè)查找單元，其沖突溢出率為ε2(ω,λ)；單級(jí)多單元散列表的容量為 H·2ω個(gè)查找單元，其沖突溢出率為ε(2ω,2λ)；在 1≤ω≤40, 1≤λ≤ω 的條件下，通過(guò)計(jì)算可以得出 ε2(ω,λ)＜ε(2ω,2λ)，即與單級(jí)多單元散列表相比，兩級(jí)多單元散列表在使用更少的存儲(chǔ)空間的條件下，可以實(shí)現(xiàn)更低的沖突溢出率。

4 測(cè)試與仿真分析

散列表沖突溢出率是Hash-TCAM查找結(jié)構(gòu)成本計(jì)算的基礎(chǔ)，因此散列表沖突溢出率的理論模型的準(zhǔn)確性，對(duì)Hash-TCAM混合查找結(jié)構(gòu)的成本計(jì)算非常關(guān)鍵，通過(guò)實(shí)驗(yàn)測(cè)試散列表沖突溢出率的理論值與實(shí)際數(shù)據(jù)的吻合度。流表關(guān)鍵字的指紋沖突會(huì)對(duì)查找性能產(chǎn)生影響，應(yīng)該盡量避免指紋沖突，并通過(guò)實(shí)驗(yàn)測(cè)試?yán)碚撋舷薹治龅暮侠硇浴?/p>

本節(jié)使用自生成的偽隨機(jī)數(shù)與 2所大學(xué)的數(shù)據(jù)中心報(bào)文Trace[30]數(shù)據(jù)對(duì)流表Hash-TCAM混合存儲(chǔ)與查找結(jié)構(gòu)中的散列表的沖突溢出率、指紋沖突率進(jìn)行測(cè)試，對(duì)散列表與TCAM容量配置的有效性進(jìn)行了分析，考察了混合存儲(chǔ)查找結(jié)構(gòu)的成本與能耗。

為了驗(yàn)證散列表的沖突溢出率理論分析的準(zhǔn)確性，分別生成了64K、128K、256K、512K、1M、2M、4M、8M個(gè)偽隨機(jī)數(shù)（其中，K=1024，M=1024×1024），每個(gè)偽隨機(jī)數(shù)96 bit，作為關(guān)鍵字存儲(chǔ)到散列表中。

為了驗(yàn)證方案針對(duì)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)的適用性，將 Trace數(shù)據(jù)集[30]中的報(bào)文頭部作為流表中的匹配字段存儲(chǔ)到散列表中。由于通過(guò)報(bào)文頭部的＜IP源地址、IP目的地址、傳輸層源端口號(hào)、傳輸層目的端口號(hào)＞便可以唯一地標(biāo)識(shí)一個(gè)數(shù)據(jù)流，因此測(cè)試中只取了報(bào)文頭的這4個(gè)部分作為流表的匹配字段。提取UNV1中的20個(gè)文件、UNV2中的8個(gè)文件，將報(bào)文頭四元組作為流表的匹配字段，2個(gè)數(shù)據(jù)集分別包含556601個(gè)條目和191474個(gè)條目。

測(cè)試過(guò)程中，使用 CRC-32[31]算法生成散列查找的索引，計(jì)算匹配關(guān)鍵字指紋使用的函數(shù)為Jenkins Hash[32]。

4.1 散列表沖突溢出測(cè)試

圖12給出了2單元至8單元散列表的沖突溢出率，圖中的縱坐標(biāo)為百分比，橫坐標(biāo)為散列表的負(fù)載系數(shù)λ。從圖中可以看出，無(wú)論是使用隨機(jī)數(shù)據(jù)作為關(guān)鍵字存儲(chǔ)在散列表中，還是數(shù)據(jù)中心Trace數(shù)據(jù)提取出的報(bào)文頭作為關(guān)鍵字存儲(chǔ)在散列表中，實(shí)驗(yàn)得出的沖突溢出率與理論值均非常吻合。

圖 12中的理論值是散列表沖突溢出率的理論期望值，由于散列桶中表項(xiàng)的條目數(shù)服從二項(xiàng)分布，散列沖突的溢出條目數(shù)的期望值也服從二項(xiàng)分布，根據(jù)棣莫弗—拉普拉斯中心極限定理可知，當(dāng)流表的條目數(shù)很大時(shí)，沖突溢出的概率非常接近其期望值，因此，散列沖突溢出率實(shí)驗(yàn)值與其理論期望值非常接近。

4.2 指紋沖突測(cè)試

圖13給出了2單元至8單元散列表的指紋沖突率，圖中的橫坐標(biāo)為匹配關(guān)鍵字指紋的位數(shù)，縱坐標(biāo)為沖突率，即發(fā)生指紋沖突的數(shù)目與總條目數(shù)之比，其中的指紋沖突率的理論值是沖突率的上限。從圖中可以看出，無(wú)論是使用隨機(jī)數(shù)據(jù)生成的指紋存儲(chǔ)在散列表中，還是Trace數(shù)據(jù)集中的報(bào)文頭計(jì)算出的指紋存儲(chǔ)在散列表中，指紋沖突率均不超過(guò)理論值給出的上限。隨著單元數(shù)的增加，指紋沖突率呈現(xiàn)增長(zhǎng)的趨勢(shì)。由于發(fā)生指紋沖突的概率非常小，幾個(gè)指紋沖突就會(huì)導(dǎo)致測(cè)試結(jié)果呈現(xiàn)出較大的波動(dòng)，但總的來(lái)看指紋的沖突率均不高于其理論上限。

4.3 成本與能耗分析

對(duì)于散列查找而言，需要存儲(chǔ)內(nèi)容包括：匹配關(guān)鍵字，匹配關(guān)鍵字的指紋、有效標(biāo)識(shí)位、流表指針。根據(jù)3.2節(jié)的理論分析與4.2節(jié)的仿真測(cè)試，匹配關(guān)鍵字的指紋長(zhǎng)度取21 bit以上時(shí)，其指紋沖突率低于10?5，與散列沖突溢出率相比可以忽略不計(jì)；有效標(biāo)識(shí)位為1 bit，流表指針的位數(shù)為lb N，N為流表?xiàng)l目數(shù)。這樣，當(dāng)流表的條目數(shù)不超過(guò)8 M的情況下，對(duì)于散列查找，除了匹配關(guān)鍵字以外每個(gè)條目還需要不超過(guò)45 bit的存儲(chǔ)開(kāi)銷(xiāo)。OpenFlow流表匹配關(guān)鍵字的位數(shù)通常超過(guò)228 bit，所以單個(gè)散列條目的容量不超過(guò)TCAM條目的倍。假定TCAM的單比特成本是SRAM的30倍[6]，則單個(gè) TCAM 條目成本是散列條目的 25倍以上。OpenFlow交換機(jī)的報(bào)文處理芯片對(duì)外接口等實(shí)現(xiàn)因素限制了散列桶的單元數(shù)，表2給出了散列桶單元數(shù)為2～8時(shí)成本最優(yōu)的Hash-TCAM存儲(chǔ)與查找結(jié)構(gòu)中散列表、TCAM的配置，以及整個(gè)查找結(jié)構(gòu)的成本。其中，N為總的流表?xiàng)l目數(shù)，散列表的主表、輔表以及TCAM 配置是根據(jù)散列沖突溢出率的理論值計(jì)算出的。其中UNV1與UNV2的TCAM條目數(shù)是由3.1節(jié)中的測(cè)試得出，N1=556601，N2=191474；UNV1與UNV2的成本是歸一化的成本。

從表2的數(shù)據(jù)可以看出，隨著散列桶單元數(shù)的增加，Hash-TCAM 流表存儲(chǔ)與查找結(jié)構(gòu)的成本逐漸降低，即使散列桶為 2單元的情形下，，Hash-TCAM 存儲(chǔ)與查找結(jié)構(gòu)的最優(yōu)成本可以比只使用 TCAM的方案節(jié)約 90%以上的成本。

圖12多單元散列表沖突溢出率

為了確保Hash-TCAM混合結(jié)構(gòu)的查找性能，當(dāng)執(zhí)行查找時(shí)并行地查找散列表的主表、輔表以及TCAM，因此其能耗包括這3部分的查找能耗。在0.18 μm生產(chǎn)工藝、工作電壓為1.8 V的情況下，當(dāng)TCAM容量超過(guò)256 Kbit情形，其能耗相當(dāng)于相同容量SRAM訪問(wèn)能耗的15倍以上[7]，且TCAM的能耗隨并行匹配字段條目數(shù)及寬度增加[6,7]；即使1K條目的OpenFlow流表，占用的TCAM也超過(guò)256 Kbit，因此計(jì)算時(shí)取TCAM的能耗是相同容量SRAM的15倍。為了方便計(jì)算，記容量為N個(gè)流表?xiàng)l目的TCAM能耗為15，表2中UNV1與UNV2的能耗是歸一化后的能耗。仍以散列桶為2單元的散列表為例，Hash-TCAM 存儲(chǔ)與查找結(jié)構(gòu)成本最優(yōu)條件下，其能耗與只使用 TCAM 的方案相比可以節(jié)約85%以上。

4.4 性能分析

圖13多單元散列表指紋沖突率

基于兩級(jí)多單元散列表與TCAM的OpenFlow流表查找，需要同時(shí)并行地查找TCAM、主表與輔表，包含的操作有：散列表索引的計(jì)算、指紋的計(jì)算、寄存器內(nèi)容與指紋的比較、一次 TCAM 查找、一次主表SRAM讀操作、一次輔表SRAM讀操作。對(duì)報(bào)文處理器而言，SRAM的讀寫(xiě)操作以及TCAM查找是報(bào)文處理器的性能瓶頸；衡量報(bào)文處理器查表性能的指標(biāo)是單位時(shí)間的查找次數(shù)；對(duì) SRAM 每個(gè)時(shí)鐘周期都可以執(zhí)行一次讀取操作[33]；當(dāng)OpenFlow交換機(jī)收到報(bào)文執(zhí)行OpenFlow流表查找時(shí)，其中，TCAM查找、主表SRAM的讀操作、輔表SRAM的讀操作均可以并行地執(zhí)行，即每個(gè)時(shí)鐘周期都可以執(zhí)行一次TCAM查找、主表SRAM的讀取以及輔表SRAM的讀?。灰虼嘶趦杉?jí)多單元散列表的OpenFlow流表查找的性能與基于TCAM的流表查找性能是相當(dāng)?shù)摹?/p>

SystemC[34]一種應(yīng)用廣泛的系統(tǒng)級(jí)建模與仿真的語(yǔ)言，能夠完成對(duì)電子系統(tǒng)從軟件到硬件的全部過(guò)程進(jìn)行建模，因此本節(jié)使用SystemC對(duì)兩級(jí)多單元Hash-TCAM混合OpenFlow流表存儲(chǔ)與查找結(jié)構(gòu)進(jìn)行了建模與仿真(具體的軟件仿真環(huán)境為SystemC2.1與Microsoft VC++6.0)。仿真模型中以數(shù)據(jù)中心報(bào)文 Trace數(shù)據(jù)[30]中提取的報(bào)文流作為輸入數(shù)據(jù)執(zhí)行流表的查找與插入；其中，SRAM與 TCAM 采用相同的時(shí)鐘頻率，目前，常見(jiàn)的SRAM及TCAM時(shí)鐘頻率有250 MHz、333 MHz、450 MHz，即TCAM可以實(shí)現(xiàn)每秒250M、333M、450M次的查找，SRAM可以實(shí)現(xiàn)每秒250M、333M、450M 次的讀寫(xiě)操作，因此，仿真時(shí)分別采用這些時(shí)鐘頻率，仿真過(guò)程中關(guān)鍵字的指紋采用了23 bit。分別對(duì)2～8單元的兩級(jí)多單元Hash-TCAM混合查找結(jié)構(gòu)和純 TCAM 查找結(jié)構(gòu)的查找性能進(jìn)行了測(cè)試，圖 14所示的仿真結(jié)果表明，兩級(jí)多單元Hash-TCAM 混合查找結(jié)構(gòu)在相同時(shí)鐘頻率的情況下，與純TCAM查找方案具有相近的查找性能。

表2Hash-TCAM表的配置與成本及能耗

圖14Hash-TCAM與純TCAM的查找次數(shù)對(duì)比

5 結(jié)束語(yǔ)

針對(duì)基于TCAM的OpenFlow流表存儲(chǔ)與查找機(jī)制存在的高成本、高能耗問(wèn)題，提出了基于多單元 Hash-TCAM 的混合流表查找機(jī)制。為了優(yōu)化OpenFlow流表存儲(chǔ)與查找的成本與能耗，進(jìn)一步采用兩級(jí)多單元散列表機(jī)制，在確保流表查找性能的同時(shí)，降低散列表的成本。

理論分析與仿真測(cè)試表明，基于多單元Hash-TCAM 混合流表查找結(jié)構(gòu)，針對(duì)精確匹配的流表?xiàng)l目，在優(yōu)化配置情況下，可以節(jié)約成本90%以上，同時(shí)有效降低了其能耗；所提出的方案非常適合流量管理或報(bào)文轉(zhuǎn)發(fā)為主要功能的 OpenFlow交換機(jī)。尤其是當(dāng)執(zhí)行報(bào)文處理的NP或ASIC帶有一定容量的片內(nèi)TCAM時(shí)，只需要配置適當(dāng)容量的SRAM或RLDRAM用作流表的散列匹配，便可以實(shí)現(xiàn)高性能、低成本、低能耗的OpenFlow流表查找。

[1]MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. Open-Flow: enabling innovation in campus networks [J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[2]Open Networking Foundation. OpenFlow switch specification Version 1.1.0 (Wire Protocol 0x02)[S/OL].https://www. opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-spec-v1.1.0.pdf, 2011.

[3]Open Networking Foundation. OpenFlow switch specification Version 1.3.0 (Wire Protocol 0x04) [S/OL]. https://www. opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-spec-v1.3.0.pdf, 2012.

[4]Open Networking Foundation. OpenFlow switch specification Version 1.5.0 (Protocol version 0x06) [S/OL]. https://www. opennetwork-ing.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-switch-v1.5.0.pdf, 2014.

[5]CONGDON P T, MOHAPATRA P, FARRENS M, et al. Simultaneously reducing latency and power consumption in OpenFlow switches[J].IEEE/ACM Transactions on Networking, 2014, 22(3): 1007-1020.

[6]TAYLOR D E. Survey and taxonomy of packet classification techniques [J]. ACM Computing Surveys, 2005, 37(3): 238-275.

[7]AGRAWAL B, SHERWOOD T. Modeling ternary CAM power and delay model: extensions and uses[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2008, 16(5): 554-564.

[8]劉中金, 李勇, 蘇厲, 等. TCAM 存儲(chǔ)高效的 OpenFlow多級(jí)流表映射機(jī)制[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 54: 437-442.LIU Z J, LI Y, SU L, et al. TCAM-efficient flow table mapping scheme for OpenFlow multiple-table pipelines[J]. Journal of Tsinghua Univ Sciamp;Technol, 2014, 54: 437-442.

[9]GE J, CHEN Z, WU Y, et al. H-SOFT: a heuristic storage space optimization algorithm for flow table of OpenFlow [J]. Concurrency and Computation: Practice and Experience, 2015, 27(13):3497-3509.

[10]CHEN Z, WU Y, GE J, et al. A new lookup model for multiple flow tables of OpenFlow with implementation and optimization considerations [C]//IEEE International Conference on Computer and Information Technology (CIT). Xi’an, IEEE, 2014:528-532.

[11]鄂躍鵬, 陳智, 葛敬國(guó),等. 一種高效的OpenFlow流表存儲(chǔ)與查找實(shí)現(xiàn)方法[J]. 中國(guó)科學(xué):信息科學(xué), 2015, 45(10): 1280-1288.E Y P, CHEN Z, GE J, et al. An efficient implementation of storage and lookup for flow tables in OpenFlow [J]. Scientia Sinica Informationis, 2015, 45(10): 1280-1288.

[12]SUN H, SUN Y, VALGENTI V C, et al. OpenFlow accelerator: a decomposition-based hashing approach for flow processing[C]//24th International Conference on Computer Communication and Networks(ICCCN). Las Vegas: IEEE, 2015: 1-10.

[13]ZHU H, XU M, LI Q, et al. MDTC: An efficient approach to TCAM-based multidimensional table compression[C]//IFIP Networking Conference. Toulouse, IFIP, 2015:1- 9.

[14]MCGEER R, YALAGANDULA P. Minimizing rule sets for TCAM implementation[C]//IEEE INFOCOM. Rio de Janeiro, IEEE, 2009:1314-1322.

[15]VEERAMANI S, KUMAR M M, NOOR S K. Hybrid trie based partitioning of TCAM based openflow switches[C]//IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS). Chennai, IEEE, 2013: 1-5.

[16]LIM H, LEE S, SWARTZLANDER E E J. A new hierarchical packet classification algorithm [J]. Computer Networks, 2012, 56(13):3010-3022.

[17]CORMODE G, THOTTAN M. Algorithms for next generation networks [M]. London: Springer, 2010: 181-218.

[18]PAGH R, RODLER F. Cuckoo hashing[J]. Journal of Algorithms,2004, 51(2): 122-144.

[19]KIRSCH A, MITZENMACHER M, WIEDER U. More robust hashing:cuckoo hashing with a stash[C]//16th Annual European Symposium on Algorithms, Karlsruhe (L). Springer Verlag, Heidelberg, 2008: 611-622.

[20]CURTIS A R, KIM W, YALAGANDULA P. Mahout: low overhead datacenter traffic management using end-host-based elephant detection[C]//IEEE INFOCOM. Shanghai, 2011: 1629-1637.

[21]MOHAMMAD A F, RADHAKRISHNAN S, RAGHAVAN B, et al.Hedera: dynamic flow scheduling for datacenter networks[C]//USENIX Association NSDI. San Jose: USENIX, 2010: 281-296.

[22]LI D, SHANG Y, CHEN C. Software defined green data center network with exclusive routing[C]//IEEE INFOCOM. Toronto, IEEE,2014: 1743-1751.

[23]FERKOUSS O E, SNAIKI I, MOUNAOUARO, et al. A 100Gig network processor platform for OpenFlow[C]//Conf Network and Service Management (CNSM), Paris: IEEE, 2011.

[24]LUO Y,CASCON P, MURRAY E, et al. Accelerating OpenFlow switching with network processors[C]//ACM/IEEE Symposium on Architecture for Networking and Communications Systems(ANCS).Princeton, ACM, 2009: 70-71.

[25]RECEP O. Intel? Ethernet Switch FM6000: SDN with Open-Flow[EB/OL].http://www.intel.com/content/www/us/en/switch-silicon/ethernet-switch-fm6000-sdn-paper.html, 2014.

[26]MICHAEL O R. Fingerprinting by random polynomials[R]. Center for Research in Computing Technology Harvard University Report TR-15-81, 1981.

[27]BRODER A Z, KARLIN A R. Multilevel adaptive hashing[C]//ACM-SIAM Symposium on Discrete Algorithm. San Francisco,ASSOC COMP MACHINERY, 1990: 43-53.

[28]KUMAR S, TURNER J, CROWLEY P. Peacock hashing: deterministic and updatable hashing for high performance networking[C]//IEEE INFOCOM. Phoenix, IEEE, 2008: 101-105.

[29]KIRSCH A, MICHAEL M. On the Performance of multiple choice hash tables with moves on deletes and inserts[C]//46th Annual Allerton Conference on Communication, Control, and Computing, 2008:1285-1290.

[30]THEOPHILUS B. Data set for IMC 2010 data center measurement[EB/OL]. http://pages.cs.wisc.edu/～tbenson/IMC10_Data.html, 2010.

[31]BRAYER K, HAMMOND J L. Evaluation of error detection polynomial performance on the AUTOVON channel[C]//National Telecommunications Conference. New Orleans, IEEE, 1975: 21-25.

[32]https://en.wikipedia.org/wiki/Jenkins_hash_function[EB/OL].

[33]GIRISH K. QDR?-II, QDR-II+, DDR-II, and DDR-II+ Design Guide[EB/OL].http://www.cypress.com/file/38596/download, 2015.

[34]http://accellera.org/downloads/standards/systemc[EB/OL].

OpenFlow table lookup scheme integrating multiple-cell Hash table with TCAM

LI Chun-qiang1, DONG Yong-qiang1,2, WU Guo-xin1,2
(1.School of Computer Science and Engineering, Southeast University, Nanjing 211189, China;2.Key Laboratory of Computer Network and Information Integration, Ministry of Education, Southeast University, Nanjing 211189, China)

In OpenFlow networks, switches accept flow rules through standardized interfaces, and perform flow-based packet processing. To facilitate the lookup of flow tables, TCAM has been widely used in OpenFlow switches. However,TCAM is expensive and consumes a large amount of power. A hybrid lookup scheme integrating multiple-cell Hash table with TCAM was proposed for flow table matching to simultaneously reduce the cost and power consumption of lookup structure without sacrificing the lookup performance. By theoretical analysis and extensive experiments, optimal capacity configuration of Hash table and TCAM was achieved with the optimized cost of flow table lookup. The experiment results also show that the proposed lookup scheme can save over 90% cost and the power consumption of flow table matching can be reduced significantly compared with the pure TCAM scheme while keeping the similar lookup performance.

OpenFlow, ternary content addressable memory, Hash table, flow table

s:The National High Technology Research and Development Program of China (863 Program) (No.2013AA013503),The National Natural Science Foundation of China (No.61272532, No.61370209), The Future Networks Prospective Research Program of Jiangsu Province (No.BY2013095-2-06)

TP393

A

10.11959/j.issn.1000-436x.2016204

2016-01-25；

2016-08-30

吳國(guó)新，gwu@seu.edu.cn

國(guó)家高技術(shù)研究發(fā)展計(jì)劃(“863”計(jì)劃)基金資助項(xiàng)目(No.2013AA013503)；國(guó)家自然科學(xué)基金資助項(xiàng)目(No.61272532,No.61370209)；江蘇省未來(lái)網(wǎng)絡(luò)前瞻性研究基金資助項(xiàng)目(No.BY2013095-2-06)

李春強(qiáng)（1975-），男，山東沾化人，東南大學(xué)博士生，主要研究方向?yàn)閿?shù)據(jù)中心網(wǎng)絡(luò)體系結(jié)構(gòu)及傳輸控制、報(bào)文轉(zhuǎn)發(fā)及查找算法等。

董永強(qiáng)（1973-），男，河南澠池人，博士，東南大學(xué)副研究員，主要研究方向?yàn)榫W(wǎng)絡(luò)體系結(jié)構(gòu)、移動(dòng)網(wǎng)絡(luò)計(jì)算、高效內(nèi)容分發(fā)等。

吳國(guó)新（1956-），男，安徽蕪湖人，東南大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)協(xié)議、網(wǎng)絡(luò)安全和自組網(wǎng)等。