① ip 地址的演算法
IP地址是32位的二進制數值,用於在TCP/IP通訊協議中標記每台計算機的地址。通常我們使用點式十進制來表示,如192.168.0.5等等。
每個IP地址又可分為兩部分。即網路號部分和主機號部分:網路號表示其所屬的網路段編號,主機號則表示該網段中該主機的地址編號。按照網路規模的大小,IP地址可以分為A、B、C、D、E五類,其中A、B、C類是三種主要的類型地址,D類專供多目傳送用的多目地址,E類用於擴展備用地址。A、B、C三類IP地址有效范圍如下表:
類別 網路號 /佔位數 主機號 /佔位數 用途
A 1~126 / 8 0~255 0~255 1~254 / 24 國家級
B 128~191 0~255 / 16 0~255 1~254 / 16 跨過組織
C 192~223 0~255 0~255 / 24 1~254 / 8 企業組織
隨著互連網應用的不斷擴大,原先的IPv4的弊端也逐漸暴露出來,即網路號佔位太多,而主機號位太少,所以其能提供的主機地址也越來越稀缺,目前除了使用NAT在企業內部利用保留地址自行分配以外,通常都對一個高類別的IP地址進行再劃分,以形成多個子網,提供給不同規模的用戶群使用。
這里主要是為了在網路分段情況下有效地利用IP地址,通過對主機號的高位部分取作為子網號,從通常的網路位界限中擴展或壓縮子網掩碼,用來創建某類地址的更多子網。但創建更多的子網時,在每個子網上的可用主機地址數目會比原先減少。
子網掩碼是標志兩個IP地址是否同屬於一個子網的,也是32位二進制地址,其每一個為1代表該位是網路位,為0代表主機位。它和IP地址一樣也是使用點式十進制來表示的。如果兩個IP地址在子網掩碼的按位與的計算下所得結果相同,即表明它們共屬於同一子網中。
在計運算元網掩碼時,我們要注意IP地址中的保留地址,即「 0」地址和廣播地址,它們是指主機地址或網路地址全為「 0」或「 1」時的IP地址,它們代表著本網路地址和廣播地址,一般是不能被計算在內的。
下面就來以實例來說明子網掩碼的演算法:
對於無須再劃分成子網的IP地址來說,其子網掩碼非常簡單,即按照其定義即可寫出:如某B類IP地址為 10.12.3.0,無須再分割子網,則該IP地址的子網掩碼為255.255.0.0。如果它是一個C類地址,則其子網掩碼為 255.255.255.0。其它類推,不再詳述。下面我們關鍵要介紹的是一個IP地址,還需要將其高位主機位再作為劃分出的子網網路號,剩下的是每個子網的主機號,這時該如何進行每個子網的掩碼計算。
一、利用子網數來計算
在求子網掩碼之前必須先搞清楚要劃分的子網數目,以及每個子網內的所需主機數目。
1)將子網數目轉化為二進制來表示
2)取得該二進制的位數,為 N
3)取得該IP地址的類子網掩碼,將其主機地址部分的的前N位置 1 即得出該IP地址劃分子網的子網掩碼。
如欲將B類IP地址168.195.0.0劃分成27個子網:
1)27=11011
2)該二進制為五位數,N = 5
3)將B類地址的子網掩碼255.255.0.0的主機地址前5位置 1,得到 255.255.248.0
即為劃分成 27個子網的B類IP地址 168.195.0.0的子網掩碼。
二、利用主機數來計算
1)將主機數目轉化為二進制來表示
2)如果主機數小於或等於254(注意去掉保留的兩個IP地址),則取得該主機的二進制位數,為 N,這里肯定 N<8。如果大於254,則 N>8,這就是說主機地址將占據不止8位。
3)使用255.255.255.255來將該類IP地址的主機地址位數全部置1,然後從後向前的將N位全部置為 0,即為子網掩碼值。
如欲將B類IP地址168.195.0.0劃分成若乾子網,每個子網內有主機700台:
1) 700=1010111100
2)該二進制為十位數,N = 10
3)將該B類地址的子網掩碼255.255.0.0的主機地址全部置 1,得到255.255.255.255
然後再從後向前將後 10位置0,即為: 11111111.11111111.11111100.00000000
即255.255.252.0。這就是該欲劃分成主機為700台的B類IP地址 168.195.0.0的子網掩碼。
下面列出各類IP地址所能劃分出的所有子網,其劃分後的主機和子網佔位數,以及主機和子網的(最大)數目,注意要去掉保留的IP地址(即劃分後有主機位或子網位全為「0」或全為「1」的):
A類IP地址:
子網位 /主機位 子網掩碼 子網最大數 /主機最大數
2/22 255.192.0.0 2/4194302
3/21 255.224.0.0 6/2097150
4/20 255.240.0.0 14/1048574
5/19 255.248.0.0 30/524286
6/18 255.252.0.0 62/262142
7/17 255.254.0.0 126/131070
8/16 255.255.0.0 254/65536
9/15 255.255.128.0 510/32766
10/14 255.255.192.0 1022/16382
11/13 255.255.224.0 2046/8190
12/12 255.255.240.0 4094/4094
13/11 255.255.248.0 8190/2046
14/10 255.255.252.0 16382/1022
15/9 255.255.254.0 32766/510
16/8 255.255.255.0 65536/254
17/7 255.255.255.128 131070/126
18/6 255.255.255.192 262142/62
19/5 255.255.255.224 524286/30
20/4 255.255.255.240 1048574/14
21/3 255.255.255.248 2097150/6
22/2 255.255.255.252 4194302/2
B類IP地址:
子網位 /主機位 子網掩碼 子網最大數 /主機最大數
2/14 255.255.192.0 2/16382
3/13 255.255.224.0 6/8190
4/12 255.255.240.0 14/4094
5/11 255.255.248.0 30/2046
6/10 255.255.252.0 62/1022
7/9 255.255.254.0 126/510
8/8 255.255.255.0 254/254
9/7 255.255.255.128 510/126
10/6 255.255.255.192 1022/62
11/5 255.255.255.224 2046/30
12/4 255.255.255.240 4094/14
13/3 255.255.255.248 8190/6
14/2 255.255.255.252 16382/2
C類IP地址:
子網位 /主機位 子網掩碼 子網最大數 /主機最大數
2/6 255.255.255.192 2/62
3/5 255.255.255.224 6/30
4/4 255.255.255.240 14/14
5/3 255.255.255.248 30/6
6/2 255.255.255.252 62/2
② IP的演算法
有34台機器.
就是和掩碼與運算
③ 寫出網際網路(使用子網掩碼)的IP層查找路由的演算法
(1) 從收到的分組的首部提取目的 IP 地址 D。
(2) 先用各網路的子網掩碼和 D 逐位相「與」,看是否和
相應的網路地址匹配。若匹配,則將分組直接交付。
否則就是間接交付,執行(3)。
(3) 若路由表中有目的地址為 D 的特定主機路由,則將
分組傳送給指明的下一跳路由器;否則,執行(4)。
(4) 對路由表中的每一行的子網掩碼和 D 逐位相「與」,
若其結果與該行的目的網路地址匹配,則將分組傳送
給該行指明的下一跳路由器;否則,執行(5)。
(5) 若路由表中有一個默認路由,則將分組傳送給路由表
中所指明的默認路由器;否則,執行(6)。
(6) 報告轉發分組出錯。
④ DPDK ACL演算法介紹
DPDK提供了三種classify演算法:最長匹配LPM、精確匹配(Exact Match)和通配符匹配(ACL)。
其中的ACL演算法,本質是步長為8的Multi-Bit Trie,即每次可匹配一個位元組。一般來說步長為n時,Trie中每個節點的出邊為2^n,但DPDK在生成run-time structures時,採用DFA/QRANGE/SINGLE這幾種不同的方式進行數據結構的壓縮,有效去除了冗餘的出邊。本文將為大家介紹ACL演算法的基本原理,主要內容包括:trie樹的構造、運行時的node array生成和匹配原理。對於ACL介面的使用,參考DPDK的官方文檔即可。
ACL規則主要面向的是IP流量中的五元組信息,即IP/PORT/PROTO,演算法在這個基礎上進行了抽象,提供了三種類型的匹配區域:
熟悉這三種類型的使用後,完全可以用它們去匹配網路報文的其它區域,甚至將其應用到其它場景中。
具體來說,rte_acl_field_def有5個成員:type、size、field_index、input_index、offset。
如果要深入理解演算法,可以思考這幾個欄位的意義,或者換個角度來看:
對於規則的定義,要注意如下兩點:
比如定義了5個field,那麼請給出每一個的具體定義:
像field[1]中IP和mask都為0,表示匹配所有的IP地址;field[3]中range由0到65535,表示匹配所有。類似這樣的全匹配一定要顯示的定義出來,因為如果不明確定義,這些欄位的值取決於編譯器的,最後編譯的ACL規則很可能與原有設想存在偏差。
如果在規則中,對於某個field不進行限制,對於不同type的field,規則書寫時有一定差異:
對於BITMASK和MASK類型,全0代表匹配所有,如上例中的field[0]、field[1];
對於RANGE,則按照上述field[3]中的形式定義。
規則定義好後,會轉換為trie樹並最終合並到一起。
實際處理過程中,build_trie函數會自底向上的將rule中的每個field轉換為node,然後將這些node合並生成這條rule的trie,最後將這個trie與已有的trie進行merge,最終生成整個rule set的trie。
tire由node組成,其主要數據成員如下:
node中values成員用於記錄匹配信息,ptrs則用於描述node的出邊,用於指向轉換後的node。
values採用bitmap進行壓縮,其數據結構為struct rte_acl_bitset values; 一個byte取值范圍是[0,255],可通過256個bit位來進行對應,並實現byte值的快速查找:即通過第x位的bit值是否為1來判斷是否包含數值x(0 <= x < 256)。
num_ptrs用於描述出邊數目,ptrs即為實際的出邊,它記錄了其匹配值values和匹配後的節點指針。
match_flag和mrt則用於記錄匹配結果,trie樹中葉子節點一定是記錄匹配結果的節點。
trie樹其詳細結構比較復雜,這里將其結構進行簡化,如下所示:
上圖的trie樹有4個node,通過ptrs進行指向,values欄位為匹配值的bitmap表示,為了表述的簡潔,後續會採用simple的方式進行描述。
在trie simple中,實心節點表示匹配節點,邊上的數字代表匹配值(為便於閱讀,採用實際值而不再是bitmap形式),…代表其它匹配值。
不同type的field,轉換為node的方式會有所不同。
目前提供的3種類型:BITMASK描述一個byte的匹配,支持mask模式;MASK用於描述4個byte的匹配,支持mask模式;RANGE描述2個byte的匹配,此時mask表示上限。
field到node的轉換,見build_trie中的for循環,具體轉換函數則參考:
對於BITMASK,如{.value.u8 = 6, .mask_range.u8 = 0xff,},它最後的轉換形式如下:
構造field的node時,總會在結尾添加一個空的end節點,最後一個field除外(它是match node)。在for循環中每完成了一個field的解析後,會將其合並到root中,從而生成這個rule的trie。
合並前,也會先構造一個空的end node(見build_trie函數中,while循環下的root創建),讓它與field構成的node頭合並,因為不相交,所以merge時會將匹配信息合並到end node並釋放原有的頭,並將field鏈的end節點返回(保存到end_prev中),下次合並時,就用此end節點與新的node頭合並。
循環遍歷完所有的field後,這些node就串聯起來了,構成這個rule的trie。
對於多個rule,每次構造完成後會merge到整體的trie中。
這里詳細介紹下merge演算法原理,其實仔細閱讀acl_merge_trie函數的注釋即可。
對於node A和node B的merge, acl_merge_trie函數返回一個節點,這個節點指向它們路徑的交集。
這里給出三個例子用於展示merge前後的變化。為了減少狀態點,構造rte_acl_field_def如下:
示例1:
acl_rules[1]為trie A,acl_rules[0]對應trie B,最終trie B合並到trie A上,具體如下:
1和1』合並時,因為level為0,所以1』直接合並到1中;
4和4』合並時,因為節點無交集,所以創建新節點c1(node 4的拷貝),並將4'上的邊拷貝到c1中。
示例2,rule類別相同,但優先順序不同:
acl_rules[1]為trie A,acl_rules[0]對應trie B,最終trie B合並到trie A上,具體如下:
6和6』是match node,類別相同,且6的優先順序為2大於6』的優先順序。
6和6』合並時,直接返回6。而前面創建的新節點,如d1,已包含5』的所有邊(非ACL_INTERSECT_B),所以最終返回5,free d1。
同理依次往上回溯,a4,b3,c2,也依次被釋放,最終merge的trie即為原來的trie A。
示例3,rule類別不同,優先順序相同:
acl_rules[1]為trie A,acl_rules[0]對應trie B,最終trie B合並到trie A上,具體如下:
6和6』是match node,因為類別不同,所以最終創建了新node e1,這也導致示例3和示例2最終merge結果的不同。
合並是一個遞歸的過程,逆向思考構造過程會有助於理解演算法。另外,在build_trie之前會sort_rule,匹配范圍更大的rule會放到前面優先構造trie,個人為這樣node A包含node B的概率更大,這可能也是merge時創建的node C是A的拷貝而不是B的拷貝的原因,因為這樣出現ACL_INTERSECT_B的概率相對較低。
一些說明:
trie樹構造完成後,會將其由指針跳轉的形式轉換為等效的數組索引形式,即node array,既可讓匹配數據更緊湊,也可提高匹配演算法的效率。
採用node array的方式進行狀態點的壓縮是很常見的優化方式,比如snort裡面的ac演算法(acsmx.c):
筆者也曾經做過類似的優化,通過將出邊由指針方式修改為索引方式,整個匹配tree的內存佔用只需要原來的1/5。
將指針方式轉換為node array形式是優化的第一步,對於Next[256]出邊又可以採用多種壓縮方式,比如snort中新的ac演算法(acsmx2.c),就採用了Sparse rows和Banded rows等多種壓縮方式,但其原理是將出邊進行映射轉換,本質上還是做DFA狀態跳轉。
DPDK對邊的壓縮方式與上述類似,不過它優化的粒度更細,不同type的node有不同的壓縮方式:
比如在示例三中,node 1為DFA節點(根節點強制使用DFA方式),2、3、a5、b4、c3、d2為QRANGE,4、5為SINGLE,6、e1為MATCH。
2、3、a5、b4雖然在圖上僅有一條有效邊,但它不為SINGLE,因為對於無效的匹配其實也會有出邊,所以它的真實出邊數目並不唯一,只有像4、5這類全匹配節點才是真正的SINGLE節點。
在構造node array前,會調用acl_calc_counts_indices函數更新node的node type,fanout等信息。
node type依據其fanout值決定,fanout計算見acl_count_fanout函數,其原理是:
比如對於示例3中的d2節點:
fanout計算完成後,若其值為1則為SINGLE節點,(1, 5]為QRANGE節點,(5, 256]為DFA節點。
注意:對於trie樹的root節點,不論fanout值為多少,會強制將其構造為DFA節點,且其fanout值會重新計算。
type和fanout計算完成後,會統計各類節點數目,信息保存在acl_calc_counts_indices傳入的counts參數中,隨後rte_acl_gen依據這些信息將整塊的node array內存分配出來,其布局大致如下:
Data indexes中用於保存在rte_acl_field_def中定義的offset;
Results對應match node,用於保存匹配結果。
Trans table包含整個匹配過程中的跳轉點:
靜態將整塊node array分配完成後,就需要依據trie 樹的node信息填充Trans table和Results了,具體過程見acl_gen_node函數;Data indexes的填充則在acl_set_data_indexes中完成。
2.2中的內存布局大致描繪了各種類型節點的分布情況,DFAs內部由一個一個的DFA節點組成,QUADs和SINGLEs也一樣,都是由相同類型的節點構成。
對於每一個節點,其結構則類似如下形式:
DFA節點的fanout一般為4,出邊數為fanout*RTE_ACL_DFA_GR64_SIZE;(圖中畫的為fanout為4的情況,256條出邊)
QUAD節點的fanout不超過5,即為節點的出邊數不超過5;(圖中畫的為fanout為4的情況)
SINGLE節點只有一個出邊;
圖中的trans即為這個節點的出邊,它本質是一個uint64的數據結構,通過trans和input信息即可計算得到下一個節點的index,從而實現匹配跳轉。trans中不同bit位包含著豐富的信息,具體見acl.h中的說明即可。
高32位對於不同類型的節點有不同的解釋:
低32位:
在實際處理過程中,通過高32位與input_byte計算得到index,與低32位中的addr,即可快速定位到下一個trans:trans_table + (addr+index)。
這里的處理其實與傳統的DFA跳轉差別很大,傳統處理時,next = node[『input』],跳轉到下一個節點,然後採用next[『input』]進行跳轉和匹配,即使有數據結構的壓縮,跳轉目標仍是狀態點。但DPDK中,跳轉時直接採用trans_table + (addr+index),直接找到了狀態點的邊(trans),而不是到狀態點。
跳轉表具體構建時,採用acl_gen_node函數完成:
匹配的過程與跳轉表的構建其實是互為一體的,如何構建跳轉表就決定了如何進行匹配。
在2.3節,對於跳轉的形式已進行了說明,具體可閱讀rte_acl_classify_scalar函數:跳轉時直接採用trans_table + (addr+index),直接找到了狀態點的邊(trans),而不是到狀態點。
對於具體的匹配過程,還有一點需要注意,即GET_NEXT_4BYTES的使用,每次匹配時候都會去4BTYTES進行匹配,這也是為什麼定義input fields時要求4位元組連續。比如我在dpdk-dev郵件組中問的這個 問題 。
解決4位元組連續,可以通過定義相同的input_index來解決,比如像郵件中提到的設置sport/dport的input_index相同,這是因為data indexes的構造取決於input_index,見acl_build_index函數;同時field_index不同、input_index相同時可避免對field區間的優化(如果優化,將某個field去掉了,這時4位元組匹配會失效)。郵件中的問題,正是因為field[3]被優化掉後,4位元組連續匹配出現問題。
在特定的場合還必須通過指定.size為32來解決,即使type類型為BITMASK,見DPDK的ACL文檔中關於 tos示例的說明 。
另外再說下field_index,前面提出一個問題:field_index是否多餘?
答案是不多餘,因為演算法中會對field進行優化,如果不指定field_index欄位,這個優化就無法進行了,具體的優化處理見acl_rule_stats函數。
優化過程中要進行input_index的判斷,這是因為相同的input_index可以有多個field,但其中只有某個field是completely wild時應避免進行優化。只有相同input_index的所有field都是completely wild時,才應該將這個field優化掉。
上面的一系列說明,都是針對GET_NEXT_4BYTES每次匹配四個位元組的匹配進行的補充說明。
匹配的具體過程,這里用圖形的方式進行簡要說明,為了能有多種類型的node,這里構造規則如下:
trie樹如下所述:
對應的node array如下圖所示:
假設輸入數據為:proto 16, ip 192.12.8.8,則transition跳轉方式如上圖紅線所示:
注意:node array中indexes、DFA0和idle省略了。
關於trie樹相關的理論知識參考 這里 。
本文主要介紹了DPDK的ACL演算法,詳細描述了如何由規則生成trie,並將trie轉換為node array的過程,在文末通過示例介紹了具體的匹配過程。文章旨在介紹ACL演算法的基本思路,希望對大家能有所幫助。