第三阶段：转发表¶
转发表中的路由条目¶
转发表中的路由条目一般有三种来源：
- 静态路由（static route）
- 网络管理员手动配置的路由
- 不受路由协议影响
- 动态路由（dynamic route）
- 从路由协议中自动地动态地学习到的路由
- 本实验中多数条目属于此类
- 直连路由（direct route）
- 路由器直接连接了相应子网，不需要再次转发
- 直接通过目标 IP 地址查询下一跳 MAC 地址
- 不受路由协议影响
转发表设计与实现¶
IP 分组转发的依据是转发表。路由器需要使用 IP 分组头部的目标 IP 地址查询转发表，从而确定下一跳接口（出接口）以及下一跳的 IP 地址。其中，查询转发表时需要采用最长前缀匹配算法，其性能要求高，会影响转发速率，应当用硬件实现。根据计算和模拟测试，在本实验框架下，若转发引擎采用流水线设计，查询转发表为流水线的某一级，且为状态机多周期实现，那么在查询转发表的时钟周期数不超过 10 个周期时，小包转发速率才可达到线速。对于转发表的更新操作（插入、更新或删除），其性能要求相对不高，因此可以根据实验者的设计，由软件或者硬件实现。一般地，软件实现更新操作可能较为简单。此外，更新转发表时则应当按照精确匹配算法。
转发表可以采用流水线设计，也可以采用状态机多周期设计。可供参考的数据结构有如下几种：
- 模拟实现 T-CAM（Ternary Content-Addressable Memory）：FPGA 中实现大容量具有挑战，实际中较多使用 T-CAM 专用芯片，但本实验中不推荐。
- 蛮力查找：实现简单，性能不佳，本实验中不推荐。
- 基于树的数据结构
- Trie：将 IP 地址前缀视作字符串，实现最长前缀匹配。根据教学实践，对于 IPv4 转发表，32 级流水线的 Trie 树（每级恰好访问一层）似乎是一种受欢迎的设计。但请注意，本实验需要实现 IPv6 转发表。此外，实验者可以根据实际路由表前缀长度的分布，合理配置每一级的容量，以达到在该分布下，整体转发表容量的提升。
- 多叉 Trie、层压缩或路径压缩等压缩 Trie：减少树的深度，优化查询周期数。
- 其他高级数据结构与算法：Luleå、Tree Bitmap、Poptrie、……
- 基于散列表的数据结构：按照前缀长度将路由条目存放在不同散列表中，查询时按照前缀长度从大到小逐一尝试，精确匹配。
在实现转发表时，实验者可能还需要考虑以下问题：
思考
- 数据结构：蛮力查找？T-CAM？Trie？Radix Tree？散列表？其他？
- 存储位置：LUTRAM？BRAM？SRAM？DRAM？
- 接口设计：暴露存储？提供插入、删除、更新及查询接口？
- 最大容量：最大需要存储多少路由表项？
- 如何设计数据结构以及接口才能方便软件修改转发表？
在完成转发引擎的整体搭建前，实验者可以暂不过度追求转发表的大容量和高性能。此处建议实验者先设计一个基础且可以正常工作的简单模块，然后配合一个比较完善的 testbench，用以测试基本功能。
对于软件实现路由表的插入、更新、删除，在 CPU 设计完成前，可以在本地编写软件来模拟插入、更新、删除过程。这一过程中，可以用数组来模拟各种 RAM。为了方便 CPU 设计完成后的移植，在模拟时应注意不要使用库函数（包括 malloc）。
对于硬件实现路由表的查找，实验者可以通过一些方式将一些路由表项预置在转发表内，再发包上板或仿真观察转发表的表现。对于 FPGA 片内的 RAM，实验者可以用代码或 IP 核的参数配置内容；一般地，实验者可以写一段逻辑，功能为，在复位后插入几条固定的路由表项。值得说明的是，在实际工作时，实验路由器的转发表初始仅包含数条直连路由，其余路由信息由 RIPng 路由协议进行交换，并通过运行在 CPU 上的软件写入转发表。
思考
- 为什么要重视 testbench？
- 实验板上 BRAM、LUTRAM、SRAM 以及 DRAM 资源大致容量如何？
- BRAM 和 SRAM 的延迟谁更低？
- FPGA 片内都提供了哪几种 RAM？Latency 的配置会有哪些影响？
- LUTRAM 与 BRAM 的区别如何？
- 如何表示一条直连路由表项？