李春強，董永強,2，吳國新,2

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

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

李春強1，董永強1,2，吳國新1,2

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

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

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

1 引言

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

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

圖1OpenFlow流表項格式

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

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

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

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

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

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

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

圖2十元組格式的流表項匹配字段

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

2.1 降低流表存儲開銷及能耗的研究

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

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

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

2.2 基于散列表的存儲與查找

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

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

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

3 Hash-TCAM混合流表存儲與查找方案

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

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

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

3.1 OpenFlow流表存儲成本優(yōu)化的問題

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

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

對于容量為 H個散列桶、單散列桶容量為 ω條目的散列表，散列表容量為h個條目，則

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

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

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

由式(9)可得出

3.2 散列表的沖突分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.2處理流程

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

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

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

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

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

圖7Hash-TCAM OpenFlow流表表項插入處理流程

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

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

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

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

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

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

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

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

3.5.2 處理流程

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

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

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

3.5.3 散列沖突溢出分析

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

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

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

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

4 測試與仿真分析

散列表沖突溢出率是Hash-TCAM查找結(jié)構(gòu)成本計算的基礎(chǔ)，因此散列表沖突溢出率的理論模型的準確性，對Hash-TCAM混合查找結(jié)構(gòu)的成本計算非常關(guān)鍵，通過實驗測試散列表沖突溢出率的理論值與實際數(shù)據(jù)的吻合度。流表關(guān)鍵字的指紋沖突會對查找性能產(chǎn)生影響，應(yīng)該盡量避免指紋沖突，并通過實驗測試理論上限分析的合理性。

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

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

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

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

4.1 散列表沖突溢出測試

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

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

4.2 指紋沖突測試

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

4.3 成本與能耗分析

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

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

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

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

4.4 性能分析

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

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

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

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

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

5 結(jié)束語

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

理論分析與仿真測試表明，基于多單元Hash-TCAM 混合流表查找結(jié)構(gòu)，針對精確匹配的流表條目，在優(yōu)化配置情況下，可以節(jié)約成本90%以上，同時有效降低了其能耗；所提出的方案非常適合流量管理或報文轉(zhuǎn)發(fā)為主要功能的 OpenFlow交換機。尤其是當(dāng)執(zhí)行報文處理的NP或ASIC帶有一定容量的片內(nèi)TCAM時，只需要配置適當(dāng)容量的SRAM或RLDRAM用作流表的散列匹配，便可以實現(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 存儲高效的 OpenFlow多級流表映射機制[J]. 清華大學(xué)學(xué)報(自然科學(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]鄂躍鵬, 陳智, 葛敬國,等. 一種高效的OpenFlow流表存儲與查找實現(xiàn)方法[J]. 中國科學(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

吳國新，gwu@seu.edu.cn

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

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

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

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