路由¶
路由入网报文转发到目的网络
路由查找¶
路由表里会指定目的网段和子网掩码长度(route_prefix/prefix_length)
二进制查找¶
目的IP与子网掩码做与运算，然后比较和路由前缀是否相等
dip & mask ?= route_prefix
哈希查找¶
针对IPv4,地址长度32bit
建立32个hash桶，key = hash(route_prefix),存入prefix_length为索引的桶里
|子网掩码长度32|→|hash(route_prefix1/32)|...|
|子网掩码长度31|→|hash(route_prefix3/32)|...|
|子网掩码长度30|→|hash(route_prefix5/32)|...|
|子网掩码长度..|→|...|
|子网掩码长度2 |→|hash(route_prefix7/32)|...|
|子网掩码长度1 |→|hash(route_prefix9/32)|...|
搜寻时，目的IP依次与长度从32减小到1的掩码做运算，然后hash，去对应桶查找
256叉树¶
前缀树查找¶
路径压缩¶
在前缀树查找中，从下往下，每个节点都要比较依次，