目录
2.4.2 聚合
取消 IP 地址分类，可以在一个更大的变化范围内分配 IP 地址块，但并不能减少路由表入口（Entry）的数量
路由表入口可以告诉路由器应该将流量发送到哪里
本质上，路由器会检查到达的数据报中的目的 IP 地址，找到一个匹配的路由表入口，然后从入口中抽取出数据报的 “ 下一跳 ” 信息
这有点像开车去某个特定的地址，在每个交叉路口都设有交通指示牌，指出能够让你最终到达目的地的下一个交叉路口的方向
在二十世纪九十年代早期，如果在指示牌上列出互联网中所有可能的目的地邻居，会发现存在一定的问题
在那个时候，在维护到所有互联网目的地的最短路径路由时，没有什么技术可以显著地减少路由表入口的数量
其中最有名的方法，是 Kleinrock 与 Kamoun 于二十世纪七十年代晚期，在一项对分层路由（hierarchical routing）[KK77] 的研究中提出的
他们发现，如果网络拓扑以树结构①组织，并且以一种对这种拓扑结构 “ 敏感的 ” 方式来分配地址
那么即使是在维护到所有互联网目的地的最短路径路由时，也仍然可以使用很小的路由表
树结构①
在图论中，树是一个没有环的连通图，对于路由器网络与连接来说，这意味着两个路由器之间只有一条路径
图 2-8 中，圆圈表示路由器，直线表示路由器之间的连接
左右两边都是树状结构的网络，但它们为路由器分配地址的方式不同
左边，地址是随机的，地址与路由器在树结构中的位置没有直接关系，而右边，地址是根据路由器在树中的位置分配的
左右两边树顶部的路由器所需要的入口数量是不同的，左边需要 9 个，右边只需要 3 个
图 2-8
在一个树结构拓扑的网络中
可以用一种特殊的方式分配网络地址，以此来限制需要存储在路由器中的路由信息（“ 状态 ”）的数量
如果地址没有按照这种方式分配（左边），那么为了能够进行最短路径路由，路由器需要存储的状态数量就会和节点数量成正比
当用一种对树结构拓扑敏感的方式分配地址时，如果网络拓扑发生了变化，通常需要重新分配地址
具体的，路由表就是一个映射表：入口（Entry）-> 下一跳的方向
首先根据目的地地址挨个去匹配入口，其中一个入口和目的地地址匹配上了，那么就不再继续匹配
根据匹配上的入口 -> 下一跳的方向映射，就知道了当前目的地址的数据报应该朝哪个方向发送
对于树状结构来说，下一跳的方向只有 n 个，n 为直接子节点数加 2（加上父节点和自己）
对于二叉树来说，下一跳的方向只有 4 个：
- 自己，即自己就是目的地
- 向左，即左子树方向
- 向右，即右子树方向
- 向上，即父节点方向
路由器只是个十字路口，自己不一定有 IP
如果严格地将所有主机 IP 都按照相同前缀连接到一个路由器的话
那么形成的拓扑树一定是二叉树，因为前缀是二进制表示方式的前缀
而同一个二进制前缀（A 节点）向下分叉，只能分出 0 和 1 两个分支（B、C 节点）
其它所有以 A 节点为前缀的 IP，一定都挂在 B 或 C 节点下
除非，有若干个以 B（或 C）为前缀的 IP 都直接挂在路由器 A 上，这样路由器 A 就有多于 2 个的分支
这就是 A 下边的 IP 没有充分聚合的结果，好处是路由器少了，坏处是路由表入口多了
入口可以是完整的 IP，也可以是通配符，如图 2-8 中
# 左子树根节点路由器的路由表，9 个入口（Entry），自己那个不算
19.12.4.8 -> 自己
190.16.11.2 -> 向左
86.12.0.112 -> 向左
159.66.2.231 -> 向左
133.17.97.12 -> 向右
66.103.2.19 -> 向右
18.1.1.1 -> 向右
19.12.4.9 -> 向右
203.44.23.198 -> 向右
其它（上边都没匹配上）-> 向上
# 右子树根节点路由器的路由表，3 个入口（Entry），自己那个不算：
19.0.0.1 -> 自己
19.1.* -> 向左
19.2.* -> 向左
其它（上边都没匹配上）-> 向上
图 2-8 中右子树的地址分配方式，在互联网中会被递归地应用在树中的每个节点上
每个路由器上路由表的入口（Entry）数量都等于与路由器直接连接的邻居数量
只要保持这个地址分配原则，无论有多少节点加入某个子树，都不会增加根节点路由器的路由表入口数量
这是 [KK77] 中分层路由思想的本质
类似【190.16.11.2 -> 向左】这样的映射，本质上是网络层到链路层的映射
意思是通过网络层的 IP 信息来确定下一跳的链路层地址，即【向左】就是链路层的地址
这也是为什么路由器自己不一定需要 IP，因为只需要通过路由器节点下边子树的公共前缀通配符，就能映射到这个路由器的链路层地址
如：【19.1.* -> 向左】，这里的【向左】链路层地址对应的路由器，自己不一定非要占用一个 IP，它只负责中转就可以了
现在很多路由器有一个 IP 地址，是为了更好的用户体验，把一个路由器做成了一个主机，上边还挂了一个网页服务用来方便用户配置
在真正的互联网中，采用了一种特殊的方式来应用分层路由思想
这种特殊方式被称为路由聚合（route aggregation）
将多个数字上相邻的 IP 前缀合并为一个更短的包含了更多地址空间的前缀（称为聚合（aggregate）或汇总（summary））
如图 2-9
图 2-9
箭头表示将两个地址前缀合并为一个前缀的过程
有下划线的前缀是每一步新增的
图 2-9 的二进制模式如下：
10111110，10011010，00011011，00|000000/26（190.154.27.0）
10111110，10011010，00011011，01|000000/26（190.154.27.64）
=>
10111110，10011010，00011011，0|0000000/25（190.154.27.0）
10111110，10011010，00011011，11|000000/26（190.154.27.192）
10111110，10011010，00011011，10|000000/26（190.154.27.128）
=>
10111110，10011010，00011011，1|0000000/25（190.154.27.128）
10111110，10011010，00011011，0|0000000/25（190.154.27.0）
10111110，10011010，00011011，1|0000000/25（190.154.27.128）
=>
10111110，10011010，00011011，|00000000/24（190.154.27.0）
10111110，10011010，00011010，|00000000/24（190.154.26.0）
10111110，10011010，00011011，|00000000/24（190.154.27.0）
=>
10111110，10011010，0001101|0，00000000/23（190.154.26.0）
即找到了 190.154.27.0、190.154.27.64、190.154.27.192 的共同前缀 190.154.26.0
这种方式就是要保证一棵树上的 IP 前缀都相同，且任何前缀相同的 IP 都在同一棵树下
图 2-9 的 IP 聚合过程，就是找到这几个 IP 前缀的公共前缀，也就是它们在树中的公共父节点
在图 2-9 的左侧有 3 个地址前缀
前两个 190.154.27.0/26 和 190.154.27.64/26 在数字上是相邻的，可以直接聚合，如箭头所示
190.154.27.192/26 前缀无法在第一步中聚合，因为它在数字上不是相邻的
当加入新的前缀 190.154.27.128/26 后（图中下划线）
将 190.154.27.192/26 与 190.154.27.128/26 前缀合并，得到 190.154.27.128/25 前缀
此时，190.154.27.128/25 与 190.154.27.0/25 相邻，可以将它们合并为 190.154.27.0/24
当加入新的前缀 190.154.26.0/24 后（图中下划线），两个 C 类前缀可以合并为 190.154.26.0/23
通过这种方式，最初的三个前缀与两个新加入的前缀被合并为了一个前缀
目录