, , . . , , Routing Information Base (RIB) Forwarding Information Base (FIB). RIB FIB ip-, .
Routing Information Base (RIB)
: , OSPF, BGP .. - . - FIB. RIB. . , - . . , 10.0.0.0/8 10.0.0.0/16 FIB . , RIB . RIB , .
Forwarding Information Base (FIB)
FIB ip-. , ip-. RIB FIB :
1. RIB FIB. RIB . FIB .
FIB ip-. , FIB . FIB . FIB , . . , FIB linux.
IP- ip- , : 10.0.0.0/8. , , : 00001010. - (.. *. . : *, 00, 10, 0000, 1000, 1001, 1010, 10111. , , , : 1010110001110100010001000010111. , .. , . 1010. ip- (next-hop), , . , , 6. ip- 32. FIB ( ) .
, , , linux.
. , . FIB 500000 , .
, . , , .
(trie). *, 00, 10, 0000, 1000, 1001, 1010, 10111 :
1. . 101100.
. (next-hop ..). . 0.0.0.0/0. . 0, , 1, . .., . , , . , 101100 *, 1, 10, 101, 1011. 10, .
, , ipv4 32.
, . , . (Path compression) — Path compressed trie (PC-trie).
2. Path compressed trie 101100.
. 101100 1- . 1, 10. , 10 . 3- , 101, 4- , 10111. 10111 , , 10.
. , (Level Compression). , , , 4, 8, 16 .. . Level and Path Compressed Trie (LPC-Trie).
3. Level and Path compressed trie 101100.
10 , . : 3- 4-, . , 101100 11 ( 3), .. 10 3, .. 10111. , 10.
, . .
linux
linux 4.4.60. linux LPC-Trie. , .
, . . , , .., : 1, 10, 1000, :
4. trie Linux 101100.
LPC-. , . , (backtracking). , 101100 10111. , 1010 ( 101), 1000 10. , backtracking , - .
, , , , - .
linux FIB. cat /proc/net/fib_trie. - :
5. cat /proc/net/fib_trie
+--, |--. , .
DIR-24-8
? , . , , . , , . :
6. .
101100 101100 , .. 44, , 10.
2 , .. 6 64 , ip- 32 4 . .
, 4 . . :
7. .
. ( 16- ), . , 1011 ( ) . ( 4- ). , 101100 10. , , .
ip- . FIB 24 . , 24- (16 777 216 ). , 24, , 8- (256 ).
( ) DIR-24-8 , , DPDK.