计算机网络-书面作业2

下表是一个使用CIDR（无类域间路由）的路由表，为了计算方便，IP地址使用十六进制表示。针对下面每个目的地址给出路由器所选择的下一步跳的标号，即A、B、C、D和E，并给出计算过程。

1. C4.5E.13.87

2. C4.5E.22.09

3. C3.41.80.02

4. 5E.43.91.12

5. C4.6D.31.2E

6. C4.6B.31.2E

网络地址/前缀长度	下一步跳
C4.50.0.0/12	A
C4.5E.10.0/20	B
C4.60.0.0/12	C
C4.68.0.0/14	D
0.0.0.0	E

首先方便最长匹配,将路由表重新排序:

网络地址/前缀长度	下一步跳
C4.5E.10.0/20	B
C4.68.0.0/14	D
C4.60.0.0/12	C
C4.50.0.0/12	A
0.0.0.0	E

1. C4.5E.13.87 前20位和第一条路由匹配，下一跳是B

2. C4.5E.22.09 前20位和第一条路由不匹配，但与第四条路由前12位匹配，下一跳是A

3. C3.41.80.02 前四条路由都不匹配，选择默认路由 0.0.0.0 ，下一跳是E

4. 5E.43.91.12 和(3)类似，下一跳是E

5. C4.6D.31.2E 8是1000，D是1101，对于第二条路由第14位不匹配，因此只能匹配第三条路由，下一跳是C

6. C4.6B.31.2E 8是1000，B是1011，前十四位与第二条路由匹配，下一跳是D

事实上，为了更加有效地查找最长前缀匹配，通常将无分类编址的路由表存放在一种层次式数据结构中，然后自上而下地按层次进行查找。这里最常用的数据结构就是二叉线索。所以以2为例真实的查找方式是发现 C4.50.0.0/12 匹配，查看孩子节点是否匹配，发现没有匹配的，则下一跳为A