一種高速並行的無鎖流表路由查找方法

2024-02-16 09:07:15 1

專利名稱：：一種高速並行的無鎖流表路由查找方法
技術領域：
：本發明涉及路由查找算法，具體說是一種高速並行的無鎖流表路由查找方法，尤指多核處理器高速並行的無鎖流表路由查找方法。
背景技術：
：隨著網絡帶寬的急劇增加，使得網絡的鏈路速率發展到lOGb/s，甚至更高，應用高性能的多核處理器硬體平臺和高速的路由查找算法，設計出滿足網絡性能要求的路由器顯得非常必要。傳統的單核處理器的處理能力受到主頻和功耗等因素的制約，在性能上難以滿足日益增長的網絡數據處理任務要求。高性能的多核處理器在數據處理過程中能夠實現並行處理，網絡延時小，數據吞吐量大，在當前的高端路由器中有著一定的應用範圍。但是，傳統的基於基數排序樹(RadixTrie)、多分支Trie樹(MultibitTrie,多分支查找樹)、分段地址等路由查找算法多應用在串行數據流處理的單核處理器中，這些算法在多核處理器中，由於多核並行執行數據處理導致的路由資源競爭，易造成數據瓶頸，使得多核處理器的並行處理能力不能完全得以發揮，造成極大的資源浪費。路由查找的專用晶片TCAM(TernaryContentAddressableMemory,三態內容尋址存儲器)，由於其價格高昂，不適合在一些對成本敏感的路由器設計中廣泛採用，而SDRAM(同步動態隨機存儲器)價格低廉，因此開展基於SDRAM的快速路由查找算法的應用研究顯得異常重要。高端路由器進行路由轉發時其轉發條目可達到百萬之上，在眾多的路由條目中匹配一條路由所消耗的時間主要取決於查找算法的性能。為了提高路由性能，在路由表設計過程中，基於原有路由表上再增加一張表，形成兩層路由表的結構設計。第一層表是總表，保存著所有的路由條目和信息；新增的第二層表為流表，保存一定時間段下的常用路由的路由表項信息(Entry)。每次數據包轉發過程中，先去流表中進行查找，如果在流表中查找到匹配的路由表項信息，則數據包直接根據匹配的路由表項信息中的路由信息輸出到出埠；如果查詢不成功，則再進入總表中查找，在總表中查找到匹配的路由條目和信息後，將數據轉發出去的同時並將該匹配的路由條目和信息添加到流表中，方便同一數據流的下一個數據包在流表中查找。之所以採用流表的查找策略可以提高路由查找的效率，是因為流表中維護的路由條目遠遠小於總表，在流表中進行一次路由匹配與在總表中去匹配所需要的平均時間要小，並且，一般在路由表設計的時候，將流表置於處理器內部的Cache(高速緩衝存儲器)中，使得基於流表的路由查找方式在性能上有更大的提升。上述基於流表的路由查找策略在單核串行處理方式上的確可以優化性能，提高路由查找的性能。為了提高多核處理器查找的性能，同樣引入了流表的設計思想，但是由於多核處理器並行處理的特點，表項資源的共享和互斥問題給流表的設計提出了新的挑戰。一般常用的方法是在系統的Cache上創建一張多個核(處理器的核)共享的流表，但是多個核共同使用一張表必定造成資源的競爭，為了保證數據處理的安全性通常的解決辦法就是採用資源鎖，這在並行處理上容易造成數據處理瓶頸。同時每個核上處理的數據各不一樣，倉Ij建的表項形成的流表表項數目較多，對於基於流表的遍歷查找效率有所打折。另一種方法是在系統的Cache上創建與核數相對應數目的流表，每個核維護一張流表，這種方式對於多核系統中同一個流的數據包送往同一個核處理的核間調度機制來說不會存在流表的競爭關係。因為相同的數據流在同一個核上進行處理，建立的流表的表項不會被其它核所用，此時這個流表只屬於這個核所私有，數據包路由查找在該核上串行實現，多核間對於流表不會存在競爭的關係，如圖I所示的核I上處理數據流「A」。但流分類一般採用Hash算法(哈希算法)，因Hash衝突的存在，導致Hash值相同但對應轉發表不在流表中的數據流會進入同一個核進行處理，由於查表失敗而只能進入總表中進行第二次查找，從而對系統性能產生一定影響。對於多核數據流無序調度機制來講，也會產生問題，同一個數據流的數據包可能會發送到幾個不同的核上去處理，在處理的過程中它們共享一張流表，因此存在相互競爭的關係。如圖I所示核2、核3和核4處理數據流「O」時所示，三個核處理的數據包都需要用到同一張流表，此時就會發生假如一個核上的數據包正在查詢該數據包流對應的流表的某一個表項時，另一個核正對該表項進行刪除，此時就會造成衝突，出現數據丟包等錯誤現象。常用的解決辦法就是對流表增加資源鎖，在無序的並行處理機制中，同一時間只允許一個核對其某一流表進行操作。採用流表設計的路由查找策略可以提升路由查找的性能，當前在單核處理中存在廣泛的應用，但是在多核處理器執行並行查找的特殊環境下，對流表資源存在競爭的關係，上述方法依舊會產生路由過程中的數據處理瓶頸，對多核的並行處理效率的較大影響，並造成數據處理延時加大。
發明內容針對現有技術中存在的缺陷，本發明的目的在於提供一種高速並行的無鎖流表路由查找方法，解決多核處理器並行執行過程中，現有流表設計方法造成的數據處理瓶頸問題，實現了多核並行執行過程中數據轉發的安全性和快速性，提高大容量系統路由查找速度和並行路由查找的性能。為達到以上目的，本發明採取的技術方案是一種高速並行的無鎖流表路由查找方法，其特徵在於，包括以下步驟步驟I:控制平面定期分別對初始化創建的N個流表g_flow_table[i]中的表項進行遍歷，0=〈i〈N，N值等於多核處理器的核數且N大於等於2，每遍歷一個表項的同時對表項的創建時間進行檢測；步驟2:控制平面執行表項時間檢測函數，如果當前時間time_info.current_time〉表項的創建時間flow_entry.create_time+生存周期時間time_info.expired_time,表明該表項已經超期，則通過消息發送函數向表項對應的核發送超期消息FL0W_INVALID,同時,將該表項通過鍊表添加函數添加到超期池g_expired_flow_pool對應的鍊表中；步驟3:控制平面對超期池g_expired_flow_pool對應的鍊表進行遍歷,如果當前時間time_info.current_time>表項的創建時間flow_entry.create_time+2*生存周期時間time_info.expired_time,表明該表項需要從內存中刪除,貝U通過消息發送函數向表項對應的核發送釋放內存消息FL0W_DELETE。在上述技術方案的基礎上，步驟4:數據平面通過接收函數接收控制平面通過消息發送函數發送過來的消息，並對消息的種類進行分析；如果控制平面通過消息發送函數發送過來的消息是超期消息FL0W_INVALID，表明需要將對應的表項從流表中移出，則數據平面調用移出函數，通過雙向鍊表中表項結點的操作(例如next->prev=prev,prev_>next=next)將該表項從流表的鍊表中移出，並將該表項通過鍊表添加函數添加到超期池g_expired_flow_pool對應的鍊表中,此時並未釋放表項內存，因此可以保證可能正在利用該表項進行轉發操作的其它核，將數據包順利轉發出去；如果控制平面通過消息發送函數發送過來的消息是釋放內存消息FL0W_DELETE，表明需要將該表項從流表中刪除，並釋放內存空間，則數據平面調用刪除函數，將該表項從流表中刪除並釋放內存空間。在上述技術方案的基礎上，還包括以下步驟步驟5:當數據平面執行完消息處理後，進入待轉發數據包的路由查找處理，調用流表查找函數flowjookup在對應的流表中進行路由查找，如果在對應的流表中沒有查找到匹配的表項，則通過流表增加函數flow_add在流表中創建新表項flow_entry,此時新表項flow_entry中的有效標誌位action_num置O,用表項添加函數list_add將表項添加到該流表數據鏈的頭部，並把待轉發數據包的路由信息指針flow_info指向該新表項flow_entry,以便通過該指針獲得路由表項信息，完成後進入步驟6;如果在對應的流表中查找到匹配的表項，通過待轉發數據包的路由信息指針flow_info返回得到路由表項信息，然後進入步驟7；步驟6:通過路由查找函數rt_lookUp在總表中進行路由查找，如果沒有查找到匹配的表項，則依照配置規則對數據包做相應的處理，可按現有技術實施，不再詳述；如果查找到匹配的表項，將該表項的內容複製到上一步(步驟5)創建的新表項flow_entry中，並將該新表項的有效標誌位action_num置I,加上表項的創建時間,然後進入步驟7；步驟7:根據待轉發數據包查表返回得到的路由表項信息將待轉發數據包發送到對應的出埠。本發明所述的高速並行的無鎖流表路由查找方法，解決多核處理器並行執行過程中，現有流表設計方法造成的數據處理瓶頸問題，實現了多核並行執行過程中數據轉發的安全性和快速性，提高大容量系統路由查找速度和並行路由查找的性能。本發明有如下附圖圖I多核並行調度環境下流表、總表與核之間的關係圖，圖2多核並行執行環境流表原理圖，圖3初期的流和超期池表項結構圖，圖4第一階段流表和超期池表項結構圖，圖5第二階段流表和超期池表項結構圖。具體實施方式以下結合附圖對本發明作進一步詳細說明。通過對現有的採用流表設計的路由查找策略進行分析，我們可知多核處理器中採用流表的路由查找策略，在一定程度上提高了路由查找的效率，但是由於多核處理器具有的並行執行的特點，使得無論是多核共享同一張流表的設計架構，還是每個核各自維護一張流表的設計架構，都會產生表項資源的競爭。為了系統的安全性和可靠性，在一定範圍內都需要採用資源鎖的形式解決流表表項的競爭問題，這種採用資源鎖的解決方法對多核處理器的並行執行效率有所折損，在一定程度上容易產生數據瓶頸，不利於多核處理器硬體性能的完全發揮。以下對現有的多核並行執行環境中流表原理進行分析。在多核處理器的多核並行執行環境中，根據核完成的任務不同，分為數據平面(DataPlane)和控制平面(ControlPlane)。數據平面主要實現數據包數據的接收、數據頭分析、流表和總表的查詢、數據的轉發等。控制平面主要實現將各種路由協議中學習的路由信息，下發到數據平面的轉發表中，並對處於數據平面的總表和流表進行管理與維護。一般來講總表和流表是建立在一段系統共享內存上，可以確保控制平面和數據平面對其都可見，便於數據平面對路由表項數據的查詢和讀取，便於控制平面對路由表項數據的管理與維護。在多核並行執行環境中採用流表的方式加快路由查找的速率，系統通常在Cache中申請與處理器的核數N(N大於等於2)相等的用來存放流表的空間塊。每個流表內的路由表項集合是總表的一個子集，流表(FlowTable)與總表(GlobalRouterTable)之間的關係如圖2所示，在路由初始化後隨著數據流轉發過程一步步建立。處理器的核每次進行路由查找時，先去對應的流表中進行查找，如果找到則數據直接根據路由信息轉發到出埠，如果查詢不到，則再進入總表中查找，在總表中查找到路由後，將該條路由添加到流表中。多核處理器在並行執行的任務調度上分為有序調度模式(staticaffinitymode)和無序調度模式(round-robinmode)。有序調度模式下相同Hash值的數據流發往同一個核進行處理；無序調度模式下相同Hash值的數據流可能發往不同的核進行處理，多核並行執行系統中流表的設計需要兼顧到這兩種調度方式的區別。設計過程中為了同時實現上述兩個執行模式下流表工作的高效性和內存消耗的合理性，在有序調度模式上，流表屬於核所私有，因為同一數據流在同一核上處理，可以確保其它的核不來競爭該流表資源；在無序調度模式上，流表屬於同一數據流所共享，但是同一數據流的數據包會發往不同的核進行處理，核在處理該流的數據包時，根據數據包信息哈希到該流對應的同一個流表上，因此流表此時為核間所共享。雖然系統為數據平面的每個核創建了一個屬於自己的流表，但是在多核無序調度過程中，本屬於該核處理的數據流可能會發送到其它的核上去處理，其它核處理該數據過程中，通過數據任務本身攜帶的信息可以哈希到該核的流表上，因此還是會形成多個核使用相同的一張流表的現象，例如當同流的數據包在一個核上的正在查詢對應的流表的某一個表項同時，另一個核此時正對該表項進行刪除，一定程度上還是會造成數據轉發的不確定性。以下對本發明的多核並行執行環境中無鎖流表原理進行分析。為了完全解決上述問題，實現真正意義上的無鎖流表設計，本發明在設計中將表項的刪除過程劃分為兩個階段，第一階段將需要刪除的表項從流表的鍊表中剝離，第二階段是在一段一定周期(生存周期)時間後，通過釋放第一階段中剝離的表項內存空間來刪除表項。第一階段中表項雖然已經從流表的鍊表中剝離，但是不刪除，這樣做可以保證核在刪除表項操作過程時，其它核上處於使用該表項的數據仍能正確轉發出去。流表中的表項生存周期是根據時間來設定的，如果生存周期已到需要對表項進行相應的刪除操作。初期的流表(g_flow_table)和超期池(g_expired_flow_pool)表項結構圖如圖3所示,流表g_flow_table[i](0=〈i〈N,N為處理器核數)中的每個表項flow_entry在創建時有一個時間標籤flow_entry.create_time,表項的生存周期時間為time_info.expired_time,當前時間為time_info.current_time。控制平面對於流表中表項的刪除過程的兩個階段按照時間來劃分，控制平面負責定期對所有流表進行遍歷，當發現表項的當前時間time_info.current_time大於表項的創建時間flow_entry.create_time與生存周期時間time_info.expired_time之和，表明表項已經超期,進入第一階段,將該表項從流表中移出，並將超期的表項添加到g_expired_flow_pool鍊表後,第一階段流表(g_flow_table)和超期池(g_expired_flow_pool)表項結構圖如圖4所示。當控制平面定期對添加了超期鍊表g_expired_flow_pool中的表項進行遍歷時,如果表項的當前時間大於表項的創建時間與2倍的生存周期時間之和時，表項操作進入第二階段，表明超期的表項需要釋放內存空間，進行真正的刪除，第二階段流表(g_flow_table)和超期池(g_expired_flow_pool)表項結構圖如圖5所示。控制平面負責所有流表的表項的時間檢測和超期表項鍊表g_expired_flow_pool的維護管理，並通過消息隊列的方式將需要移出和需要釋放空間的表項信息發送到對應所屬的數據平面核上，該核接收到控制平面的隊列消息(FL0W_INVALID或FL0W_DELETE)，分別對該表項進行相應的操作。本發明所述的高速並行的無鎖流表路由查找方法，包括以下步驟A)控制平面實現步驟步驟I:控制平面定期分別對初始化創建的N個流表g_flow_table[i]中的表項進行遍歷，0=〈i〈N，N值等於多核處理器的核數且N大於等於2，每遍歷一個表項的同時對表項的創建時間進行檢測；步驟2:控制平面執行表項時間檢測函數，如果當前時間time_info.current_time〉表項的創建時間flow_entry.create_time+生存周期時間time_info.expired_time,表明該表項已經超期，則通過消息發送函數向表項對應的核發送超期消息FL0W_INVALID,同時,將該表項通過鍊表添加函數添加到超期池g_expired_flow_pool對應的鍊表中；步驟3:控制平面對超期池g_expired_flow_pool對應的鍊表進行遍歷,如果當前時間time_info.current_time>表項的創建時間flow_entry.create_time+2*生存周期時間time_info.expired_time,表明該表項需要從內存中刪除,貝U通過消息發送函數向表項對應的核發送釋放內存消息FL0W_DELETE；B)數據平面實現步驟步驟4:數據平面通過接收函數接收控制平面通過消息發送函數發送過來的消息，並對消息的種類進行分析；如果控制平面通過消息發送函數發送過來的消息是超期消息FL0W_INVALID，表明需要將對應的表項從流表中移出，則數據平面調用移出函數，通過雙向鍊表中表項結點的操作(例如next->prev=prev,prev_>next=next)將該表項從流表的鍊表中移出，並將該表項通過鍊表添加函數添加到超期池g_expired_flow_pool對應的鍊表中,此時並未釋放表項內存，因此可以保證可能正在利用該表項進行轉發操作的其它核，將數據包順利轉發出去；如果控制平面通過消息發送函數發送過來的消息是釋放內存消息FL0W_DELETE，表明需要將該表項從流表中刪除，並釋放內存空間，則數據平面調用刪除函數，將該表項從流表中刪除並釋放內存空間。在上述技術方案的基礎上，還包括以下步驟步驟5:當數據平面執行完消息處理後，進入待轉發數據包的路由查找處理，調用流表查找函數flowjookup在對應的流表中進行路由查找，如果在對應的流表中沒有查找到匹配的表項，則通過流表增加函數flow_add在流表中創建新表項flow_entry,此時新表項flow_entry中的有效標誌位action_num置O,用表項添加函數list_add將表項添加到該流表數據鏈的頭部，並把待轉發數據包的路由信息指針flow_info指向該新表項flow_entry,以便通過該指針獲得路由表項信息，完成後進入步驟6;如果在對應的流表中查找到匹配的表項，通過待轉發數據包的路由信息指針flow_info返回得到路由表項信息，然後進入步驟7；步驟6:通過路由查找函數rt_lookUp在總表中進行路由查找，如果沒有查找到匹配的表項，則依照配置規則對數據包做相應的處理，可按現有技術實施，不再詳述；如果查找到匹配的表項，將該表項的內容複製到上一步(步驟5)創建的新表項flow_entry中，並將該新表項的有效標誌位action_num置I,加上表項的創建時間,然後進入步驟7；步驟7:根據待轉發數據包查表返回得到的路由表項信息將待轉發數據包發送到對應的出埠。本發明的關鍵點多核處理器並行執行的環境中，採用與核數相對應數目流表的設計結構提高路由查找效率，並用多核中的控制平面與數據平面相結合，將流表中表項的刪除操作分割成兩個相對獨立的FL0W_INVALID(失效)和FL0W_DELETE(刪除)階段，用無鎖流表(流表無資源鎖)的方式解決了多核並行執行過程中，多個核同時共享(讀寫)同一張流表造成的數據轉發不安全問題，避免了採用資源鎖對流表進行管理而降低路由查找的效率問題，實現多核並行執行各模式(無序調度和有序調度模式)下的無鎖流表路由查找方法。特別說明無序調度和有序調度模式對於無鎖流表的上述步驟是沒有影響的，本發明能夠支持多核下兩種調度模式，兩種調度方式的不同只會影響到數據包發往處理的核有所差別，但是對於數據包hash到的流表則不會產生影響。本發明通過設計方法將對流表表項的刪除操作分成兩個階段，第一階段是讓表項失效，但是不刪除表項；第二階段再去釋放表項資源空間。使得並行路由查找過程中，多個核在同一時刻對同一表項進行的刪除和查找操作，可以並行執行而不影響效率，並且可以保證在表項失效的時，其它核上正在利用該表項的數據包，依舊可以利用該表項的路由信息將數據發送出去，保障了數據處理的安全性和可靠性。本發明避免了採用資源鎖造成對流表的執行只能串行執行，使得並行路由查找產生數據處理瓶頸，而降低並行查找的效率。特別說明失效的表項加入超期池是為了便於控制平面對表項的生存周期進行管理，系統並不根據超期池中的表項進行數據轉發。本發明中對一個表項刪除劃分為失效和刪除兩個操作的根本原因在於無序調度下可能存在的多個核共用一個表項，但是此時有核對表項進行刪除操作，如果此時進行表項的內存釋放，面臨的問題是其它核正在利用該表項進行轉發的操作是不安全的。因此劃分為FL0W_INVALID(失效)和FL0W_DELETE(刪除)兩個階段，失效但是內存不釋放，因此其它核(在該時刻)依舊可以利用其表項進行安全的數據轉發。由於失效操作，該表項從鍊表中已經移除，以後的流表查找操作也不會查找到該表項。需要理解的是，我們設計該發明保護數據的安全性，就是要保護刪除表項的這個時間點(這個點可能有多個核都在用同一個表項)，而不是第一個階段。本說明書中未作詳細描述的內容屬於本領域專業技術人員公知的現有技術。權利要求1.一種高速並行的無鎖流表路由查找方法，其特徵在於，包括以下步驟步驟I:控制平面定期分別對初始化創建的N個流表g_flow_table[i]中的表項進行遍歷，0=〈i〈N，N值等於多核處理器的核數且N大於等於2，每遍歷一個表項的同時對表項的創建時間進行檢測；步驟2:控制平面執行表項時間檢測函數,如果當前時間time_info.current_time>表項的創建時間flow_entry.create_time+生存周期時間time_info.expired_time,表明該表項已經超期，則通過消息發送函數向表項對應的核發送超期消息FL0W_INVALID，同時，將該表項通過鍊表添加函數添加到超期池g_expired_flow_pool對應的鍊表中；步驟3:控制平面對超期池g_expired_flow_pool對應的鍊表進行遍歷，如果當前時間time_info.current_time>表項的創建時間flow_entry.create_time+2*生存周期時間time_info.expired_time,表明該表項需要從內存中刪除,貝U通過消息發送函數向表項對應的核發送釋放內存消息FL0W_DELETE。2.如權利要求I所述的高速並行的無鎖流表路由查找方法，其特徵在於，步驟4:數據平面通過接收函數接收控制平面通過消息發送函數發送過來的消息，並對消息的種類進行分析；如果控制平面通過消息發送函數發送過來的消息是超期消息FL0W_INVALID，表明需要將對應的表項從流表中移出，則數據平面調用移出函數，通過雙向鍊表中表項結點的操作將該表項從流表的鍊表中移出，並將該表項通過鍊表添加函數添加到超期池g_expired_flow_pool對應的鍊表中，此時並未釋放表項內存，因此可以保證可能正在利用該表項進行轉發操作的其它核，將數據包順利轉發出去；如果控制平面通過消息發送函數發送過來的消息是釋放內存消息FL0W_DELETE，表明需要將該表項從流表中刪除，並釋放內存空間，則數據平面調用刪除函數，將該表項從流表中刪除並釋放內存空間。3.如權利要求2所述的高速並行的無鎖流表路由查找方法，其特徵在於，還包括以下步驟步驟5:當數據平面執行完消息處理後，進入待轉發數據包的路由查找處理，調用流表查找函數flowjookup在對應的流表中進行路由查找，如果在對應的流表中沒有查找到匹配的表項，則通過流表增加函數flow_add在流表中創建新表項flow_entry,此時新表項flow_entry中的有效標誌位action_num置O,用表項添加函數list_add將表項添加到該流表數據鏈的頭部，並把待轉發數據包的路由信息指針flow_info指向該新表項flow_entry,以便通過該指針獲得路由表項信息，完成後進入步驟6;如果在對應的流表中查找到匹配的表項，通過待轉發數據包的路由信息指針flow_info返回得到路由表項信息，然後進入步驟7；步驟6:通過路由查找函數rt_l00kup在總表中進行路由查找，如果沒有查找到匹配的表項，則依照配置規則對數據包做相應的處理，可按現有技術實施，不再詳述；如果查找到匹配的表項，將該表項的內容複製到上一步創建的新表項flow_entry中，並將該新表項的有效標誌位action_num置I,加上表項的創建時間,然後進入步驟7；步驟7:根據待轉發數據包查表返回得到的路由表項信息將待轉發數據包發送到對應的出埠。全文摘要本發明涉及路由查找算法，具體說是一種多核處理器高速並行的無鎖流表路由查找方法。多核處理器並行執行環境中，採用與核數相對應數目流表的設計結構，並用多核中控制平面與數據平面相結合的方式，將流表中表項的刪除操作分割成兩個相對獨立的FLOW_INVALID(失效)和FLOW_DELETE(刪除)階段，使得多個核對一張流表同時進行讀寫操作而無需依賴資源鎖的控制。本發明所述的高速並行的無鎖流表路由查找方法，解決多核處理器並行執行過程中，現有流表設計方法造成的數據處理瓶頸問題，實現了多核並行執行過程中數據轉發的安全性和快速性，提高大容量系統路由查找速度和並行路由查找的性能。文檔編號G06F17/30GK102938000SQ20121052027公開日2013年2月20日申請日期2012年12月6日優先權日2012年12月6日發明者範富明,李念軍申請人:武漢烽火網絡有限責任公司