Network : 路由查找算法笔记

路由查找 -> 报文转发速度 -> 路由器性能

路由查找算法的几个指标：

• 查找速度：软件实现，查找过程中需要访问存储器的次数；转发速度，线速转发；报文丢失
• 存储容量：存储空间小的算法可在cache或on-chip SRAM提高运行速度
• 路由波动更新速度：

• • 静态算法：完全重构，预处理速度？
  • 动态算法：在原有基础上做更新

• 实现的灵活性：软硬件均可实现
• 可扩展性：支持IPv6？

路由查找算法测试：

Internet地址前缀分布(IPMA项目提供Internet五大骨干路由器中路由表的实时统计数据)

目的地址序列

一些查找算法：

• hash链式表查找：表项少，查找快
• 动态前缀树查找：表项增多时，查找性能差不多，整体较慢
• RAM快速查找：查找很快，算法使用的存储空间较大，适用于高速骨干路由器，高速转发

牺牲更新速度，换更快的查找速度？

骨干网使用MPLS

区别服务、策略路由支持？

最长前缀匹配不同于完全匹配，许多适用于完全匹配的算法，例如散列表，不适于最长前缀匹配。

基于树？

基于硬件？

内容可寻址存储器CAM，给出内容->返回地址

缓存CACHE，给出数据地址->返回内容

CAM在一个时钟周期内完全查找，O(1)完成最长前缀查找。

增加用于存放路由表的RAM用量=>提高查找速度

针对大量前缀 >8，<24 -> 算法优化