TCP/IP 詳解（第二版） 筆記 / 2 互聯網地址架構 / 2.4 CIDR 與聚合 / 2.4.2 聚合

目錄

2.4.2 聚合

取消 IP 地址分類，可以在一個更大的變化范圍內分配 IP 地址塊，但并不能減少路由表入口（Entry）的數量
路由表入口可以告訴路由器應該將流量發送到哪里
本質上，路由器會檢查到達的資料報中的目的 IP 地址，找到一個匹配的路由表入口，然后從入口中抽取出資料報的 “ 下一跳 ” 資訊
這有點像開車去某個特定的地址，在每個交叉路口都設有交通指示牌，指出能夠讓你最終到達目的地的下一個交叉路口的方向

在二十世紀九十年代早期，如果在指示牌上列出互聯網中所有可能的目的地鄰居，會發現存在一定的問題
在那個時候，在維護到所有互聯網目的地的最短路徑路由時，沒有什么技術可以顯著地減少路由表入口的數量
其中最有名的方法，是 Kleinrock 與 Kamoun 于二十世紀七十年代晚期，在一項對分層路由（hierarchical routing）[KK77] 的研究中提出的
他們發現，如果網路拓撲以樹結構①組織，并且以一種對這種拓撲結構 “ 敏感的 ” 方式來分配地址
那么即使是在維護到所有互聯網目的地的最短路徑路由時，也仍然可以使用很小的路由表

樹結構①
在圖論中，樹是一個沒有環的連通圖，對于路由器網路與連接來說，這意味著兩個路由器之間只有一條路徑

圖 2-8 中，圓圈表示路由器，直線表示路由器之間的連接
左右兩邊都是樹狀結構的網路，但它們為路由器分配地址的方式不同
左邊，地址是隨機的，地址與路由器在樹結構中的位置沒有直接關系，而右邊，地址是根據路由器在樹中的位置分配的
左右兩邊樹頂部的路由器所需要的入口數量是不同的，左邊需要 9 個，右邊只需要 3 個

圖 2-8
在一個樹結構拓撲的網路中
可以用一種特殊的方式分配網路地址，以此來限制需要存盤在路由器中的路由資訊（“ 狀態 ”）的數量
如果地址沒有按照這種方式分配（左邊），那么為了能夠進行最短路徑路由，路由器需要存盤的狀態數量就會和節點數量成正比
當用一種對樹結構拓撲敏感的方式分配地址時，如果網路拓撲發生了變化，通常需要重新分配地址

具體的，路由表就是一個映射表：入口（Entry）-> 下一跳的方向
首先根據目的地地址挨個去匹配入口，其中一個入口和目的地地址匹配上了，那么就不再繼續匹配
根據匹配上的入口 -> 下一跳的方向映射，就知道了當前目的地址的資料報應該朝哪個方向發送
對于樹狀結構來說，下一跳的方向只有 n 個，n 為直接子節點數加 2（加上父節點和自己）
對于二叉樹來說，下一跳的方向只有 4 個：

1. 自己，即自己就是目的地
2. 向左，即左子樹方向
3. 向右，即右子樹方向
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
通過這種方式，最初的三個前綴與兩個新加入的前綴被合并為了一個前綴

目錄