CIDR地址结构与路由查找算法详解

"这篇文档主要讨论了互联网地址结构的发展以及路由查找算法的相关知识，包括基于类的地址结构、CIDR无类域间路由、路由查找算法的评价以及各种路由查找方法。" 在互联网地址结构的发展中，最初的设计是基于类的，即A、B、C三类地址，分别用于单播，D类地址用于组播，E类地址则预留未来使用。然而，这种基于类的地址结构存在灵活性不足和地址空间浪费的问题，导致路由表规模持续增长。为了解决这些问题，引入了CIDR（Classless Inter-Domain Routing）无类域间路由地址结构。CIDR允许任意长度的网络地址部分，提高了地址空间的利用率，但同时也带来了路由查找的复杂性，因为地址前缀的长度不再是固定的。 路由查找算法的核心在于找到与目标地址匹配的最长地址前缀，这被称为最长匹配原则。当路由表中有多个匹配项时，选择网络前缀最长的那个，因为它指示了更具体的路由。路由查找算法按照依据和实现方式可以分为多种类型： 1. **基于地址前缀值的查找**：侧重于比较地址前缀的值来寻找匹配项。 2. **基于地址前缀长度的查找**：关注前缀的长度，寻找最长匹配。 3. **基于检索树（Trie）查找**：通过构建Trie树来快速查找，外部节点要求完全匹配。 4. **基于硬件TCAM查找**：利用特殊的硬件，如TCAM（Ternary Content-Addressable Memory），进行高速查找。 5. **分段查找**：将路由表分割为多个部分，分别查找。 6. **哈希表查找**：利用哈希函数加速查找过程。 7. **Cache命中查找**：通过缓存最近使用的路由条目，减少查找时间。 基本的二叉检索树（Trie）是一种常用的路由查找数据结构，它遵循唯一前缀原则，将路由表组织成一棵树，外部节点要求整个网络前缀与目标地址匹配。为了正确转发数据报，通常需要在外部节点增加网络地址和地址掩码的信息。 路由查找算法是互联网通信中的关键技术，随着地址结构的演变和网络规模的扩大，高效的查找策略变得至关重要。这些算法和数据结构的选择直接影响到网络性能和路由查找效率。