使用cidr的ip查找路由的算法

在计算机网络中，尤其是互联网中，路由器是起着链接不同网络的重要设备。对于一个路由器（或交换机），如何快速地查找目标IP地址对应的路由是一项必要的技术。正是这项技术支持了我们今天使用互联网的便利。

CIDR是表示IP地址范围的一种方式。CIDR（Classless Inter-Domain Routing）有时也称为CID（Classless Inter-Domain）或CIDR记数法，它是一个用于表示IP地址的方法，允许将单个地址块的地址集合表示为更小的地址块。它还使用了网络前缀，这是一种在IP地址中标识网络子网的方法。

查找目标IP地址对应的路由，可以分为两个步骤：

第一步，需要将路由器中存储的路由表（Routing Table）与目标IP地址进行比对，并找到最长匹配的路由表项（Routing Table Entry）。最长匹配指的是，匹配路由项的子网前缀长度越长，表示它越匹配目标地址，所以它也是最适合的。

第二步，根据最长匹配的路由表项找到对应的出接口（Outgoing Interface），即该路由表项的下一跳（Next Hop）。下一跳指的是将数据报转发到哪个路由器。

以下是一些常见的CIDR算法：

1. 前缀匹配法

采用最简单直接的方式，即比较目标IP地址的子网前缀与路由表项的子网前缀。当子网前缀相同时，则表示匹配成功，返回找到的路由表项及其对应的出接口。

该方法的优点是实现简单，速度快。但是，它要求路由表中的子网前缀不能重复，否则将会出现错误的路由表项匹配。实际上，网络中可能会出现路由表项重复的情况，因为不同的AS（Autonomous System 自治系统）内部可以使用相同的子网前缀。

2. 前缀树法

采用二叉树的结构，将一个IP地址段的前缀按位分开，每个二叉树节点代表一个前缀位（1或0），从而形成一棵树。该树通常被称为路由前缀树（Trie Tree），是一种前缀编码树。

在路由前缀树中查找目标IP地址的过程，就是从根节点出发，一路向下按位寻找目标IP地址对应的子节点。当找到叶子节点时，该叶子节点的父节点所对应的路由表项就是最长匹配项。

优点是可以处理有重复子网前缀的情况，并且不需要对整个IP地址进行对比，可以通过前缀位来快速处理。缺点是实现较为复杂，要求额外的空间来存储树结构。

3. 编址排序法

将路由表中的所有地址按照网络前缀排序，然后采用二分查找算法进行查找。由于排序后，具有相同网络前缀的路由表项一定是相邻的，因此可以采用二分查找进行快速查找。

该算法的优点是实现简单，并且对于大规模路由表也有较好的性能。缺点是要求将整个路由表进行排序，所以对于动态变化的路由表来说，实时排序是一项非常消耗资源的操作。

综上所述，CIDR算法根据不同的实现方式，各有优缺点。路由器中的查找算法需要根据需要平衡时间和空间的开销，并考虑到路由表的特点和实际应用场景。