目录

一、基于终点的转发

1、理解

2、IP数据报转发过程

二、最长前缀匹配

1、理解

2、主机路由

3、默认路由

三、二叉线索查找

---

一、基于终点的转发

1、理解

理解什么叫终点转发
IP数据报的传递，交给路由器后
可不可以做到直接发送给目的主机呢？
可以，直接将目的主机的IP地址存放在路由表即可
技术上是可行的
但是，成本太大
为什么？什么成本？
中国有20亿个主机，包括手机和PC端，不过分吧
我现在在北京，我要向任何一个人发送消息
而且要只经过一个路由器
那么，这个路由器就必须存放全中国所有的IP地址才可以，即存20亿个IP地址，
存的成本、查找的成本很大
所以，需要多个路由器分摊，对应的，网络需要划分
这就是为什么网络采用如今设计构架的本质原因
纯粹就是因为跨区域太大，需要进行多层级的资源整合和设计
用合理的构架适当降低成本，以技术成本换取经济成本
再高明的技术，如果经济成本过高，那么规模势必不会大
一个最简单的例子就是航天
所以，
IP层数据的转发，并不是直接发给目的主机，而是以终点网络为目的。
一个IP数据报：有源主机IP地址、目的主机IP地址
路由器根据目的主机的IP地址所在的网络地址，发送给对应网络
路由表只需存放各个网络号地址即可
这就大大缩小了转发表的负担
这就是基于终点的转发

2、IP数据报转发过程

首先看，目的主机是否在本网络
怎么看？
路由器的转发表的第一个网络号就是本网络
用目的主机IP地址和转发表第一个网络号的地址掩码进行计算
得到目的主机IP地址的网络号，如果匹配，相等
那很简单，直接交付
直接在本网络广播，找到主机，目的主机返回MAC地址，发送端封装MAC帧，发送

如果不在本网络
依次顺着路由器的转发表
逐个计算网络号，直到匹配，
而后路由器根据目的网络转发

查找转发表的过程，叫做寻找网络前缀匹配

二、最长前缀匹配

1、理解

最长前缀匹配：谁的网络号长，就匹配谁
什么意思？
举个例子，下面有一个场景：

有一个分组，128.1.24.1到达一个路由器
路由器连接2个网络，分别是A公司和B公司
A公司的网络号是：128.1.24.0/24 
B公司的网络号是：128.1.25.0/24
                               128.1.26.0/24
                               128.1.26.0/24
B公司将25、26、27进行聚合，形成：
                               128.1.24.0/22
于是，路由器的路由表存放两个网络号：
                               128.1.24.0/22
                               128.1.24.0/24
但是，经过计算，你会发现：

128.1.24.1两个网络号都匹配！
但是，很明显，该IP地址是不属于B公司的
所以，给谁？
给A
虽然网络前缀都一样，但是A的网络前缀有24位，B只有22位
这就是最长前缀匹配

为什么？
因为网络前缀越长，说明越具体
于是，在安排网络号前缀在路由表的顺序时
可以将最长的放前面，依次往后

2、主机路由

对特定主机，专门给出一个单独的路由
就是把主机的IP地址直接写在转发表中
该网络号前缀为32位
此时，只要目的地址是该特定主机，
目的IP地址和网络前缀32个1做与
结果一定匹配，直接转发

特定主机路由放在路由器的第一行

用处？
检查网络连接 / 转发表

例如，我要检查A->B主机的某个特定路线
我就可以主机路由，进行特定路线转发
然后逐个排查

3、默认路由

0.0.0.0/0
网络号全0，网络前缀为0，所以地址掩码为32位全0
此时，任何IP目的地址和32位全0做与运算
结果必定是0，于是匹配

综上，一个转发表的内容，有如下：
第一行：特定主机路由（可有可无）
第二行之后：前缀最长的网络号
最后一行：默认路由

一个IP数据报在路由器的查找表过程：
1、拿到目的主机IP地址
2、从上到下，逐个匹配网络号

注意：最长前缀匹配问题，只会发生在CIRD网络分配
而不会在分类地址中发生
同时，在转发表中，不会出现两行或两行以上都匹配的情况

上述的查找转发表的过程，是顺序查找
从上往下逐个进行
最坏结果是从上到下一个都没有查找
效率很低
于是，为了提高转发表的查询效率，
需要借助新的数据结构
支撑新的查找算法
下面介绍基于二叉树结构的前缀二分查找

三、二叉线索查找

二叉树，左边为0，右边为1

一个IP地址32位，从上到下，即使网络前缀有32位，最多也就是查询32次
效率很高，首位为1 ，往右边；为0，往左边
直接砍一半减少了 2^31次比较

每一个节点代表一个唯一的前缀