除了要考虑算法检索效率问题,还需要考虑是否可以借助硬件实现查找加速。
典型的算法有:
➢ 以 Linux 的路由查找算法为代表的的哈希(桶)算法
➢ Linux 的 LC-Trie 树查找算法
➢ BSD/Cisco 的 Radix 查找算法
➢ BSD/Cisco 的 256 叉树查找算法
➢ DPDK 中采用的分段查找算法(类似多级页表查询方式)
1.2 Mac 表(Media Access Control Table)
从 ISO 网络模型上划分来说,路由表位于网络层,它用来进行路由和寻址功能。而 Mac
表则维护数据链路层,用来记录 MAC 地址-->端口之间的映射。说道 MAC 表,虽然每一台网
络设备商都存在,但是更多的是在交换机中进行详细介绍。
MAC 表中包括的内容有:
➢ MAC 地址
➢ 物理接口
➢ Mac 条目类型(可能)
➢ 老化时间
➢ VLAN-ID(可能)
因为 MAC 表项也存在动态 Mac 和静态 Mac 之分,因此在 Mac 表中会有老化时间、类型。
静态 MAC 地址与静态路由一样,有管理员负责管理维护;而动态 Mac 表项则是通过学习
而来。在交换机中一般存在两个重要线程:地址学习线程、报文转发线程。
1.2.1 地址学习线程:
➢ 源 MAC 学习法: 交换机从网络上收到报文后,利用数据包的源 MAC 地址进行学习,
并建立 MAC 表项。
➢ 端口移动机制:交换机收到报文后,如果发现报文接收端口与 MAC 表中对应的端口
不一致时,进行端口移动,将 Mac 地址重新学习到新的端口上。
➢ 地址老化机制:如果长时间没有收到某 Mac 表项对应的报文,则删除此表项。等下次
报文来时重新进行学习。
1.2.2 报文转发线程:
➢ 交换机收到报文后,根据报文中的目的 Mac 查询 Mac 表。如果找到,则从相应的端口
发出;如果没有找到,则向除入端口以外的所有端口发送(即传说中的泛洪);
➢ 如果交换机收到的报文目的 Mac 和源 Mac 所在端口相同,则丢弃此报文;
➢ 交换机收到的目的 Mac 为广播报文时,则向除入端口以外的所有端口转发广播报文。
评论0