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

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

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

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

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

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

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

OpenFlow；三態內容尋址存儲器；散列表；流表

1 引言

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

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

圖1OpenFlow流表項格式

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

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

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

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

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

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

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

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

2 相關技術介紹

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

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

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

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

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

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

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

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

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

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

圖3Hash-TCAM混合流表查找結構

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

3.1 OpenFlow流表存儲成本優化的問題

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

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

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

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

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

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

由式(9)可得出

3.2 散列表的沖突分析

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

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

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

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

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

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

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

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

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

3.3 多單元散列表的結構及處理方法

3.3.1 存儲與查找結構

由于OpenFlow流表表項的匹配關鍵字包含的位數非常多(OpenFlow1.0規范中至少包含228 bit)，為了能夠實現多個單元的并行比較，需要對匹配關鍵字進行壓縮，可以使用具有良好隨機性的散列函數將流表的匹配關鍵字壓縮成位數較少的固定長度的指紋(fingerprint)[26]，在散列查找時通過指紋的比較發現匹配的流表表項。基于多單元散列表的OpenFlow流表結構如圖5所示，每個散列桶包含ω個查找單元，每個查找單元由標識位、指紋、流表指針3個部分組成，其中，標識位表示該查找單元中的流表條目是否有效，在刪除流表表項時只要將對應的標識位置為無效即可，表項指針指向具體的流表條目。

圖5基于多單元散列表的OpenFlow流表結構

3.3.2處理流程

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

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

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

3.4 匹配關鍵字指紋

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

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

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

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

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

3.5 兩級多單元散列表的結構及操作

3.5.1 存儲與查找結構

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

圖9兩級多單元散列表的詳細結構

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

3.5.2 處理流程

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

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

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

3.5.3 散列沖突溢出分析

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

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

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

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

4 測試與仿真分析

散列表沖突溢出率是Hash-TCAM查找結構成本計算的基礎，因此散列表沖突溢出率的理論模型的準確性，對Hash-TCAM混合查找結構的成本計算非常關鍵，通過實驗測試散列表沖突溢出率的理論值與實際數據的吻合度。流表關鍵字的指紋沖突會對查找性能產生影響，應該盡量避免指紋沖突，并通過實驗測試理論上限分析的合理性。

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

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

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

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

4.1 散列表沖突溢出測試

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

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

4.2 指紋沖突測試

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

4.3 成本與能耗分析

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

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

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

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

4.4 性能分析

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

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

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

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

圖14Hash-TCAM與純TCAM的查找次數對比

5 結束語

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

理論分析與仿真測試表明，基于多單元Hash-TCAM 混合流表查找結構，針對精確匹配的流表條目，在優化配置情況下，可以節約成本90%以上，同時有效降低了其能耗；所提出的方案非常適合流量管理或報文轉發為主要功能的 OpenFlow交換機。尤其是當執行報文處理的NP或ASIC帶有一定容量的片內TCAM時，只需要配置適當容量的SRAM或RLDRAM用作流表的散列匹配，便可以實現高性能、低成本、低能耗的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]. 清華大學學報(自然科學版), 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流表存儲與查找實現方法[J]. 中國科學:信息科學, 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

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

李春強（1975-），男，山東沾化人，東南大學博士生，主要研究方向為數據中心網絡體系結構及傳輸控制、報文轉發及查找算法等。

董永強（1973-），男，河南澠池人，博士，東南大學副研究員，主要研究方向為網絡體系結構、移動網絡計算、高效內容分發等。

吳國新（1956-），男，安徽蕪湖人，東南大學教授、博士生導師，主要研究方向為網絡協議、網絡安全和自組網等。