第六章
路由协议
TCP/IP详解卷 1,CH9,CH10
主要内容
? 6.1 IP选路
? 6.2 动态选路协议（路由协议）
? RIP
? OSPF
? BGP
? 6.3 无类路由选择 CIDR
? 课下作业
6.1 IP选路
为数据包选路的可以是路由器，
也可以是主机（该主机被配置为路由器）
生成静态路由的方法
? 配置接口 IP地址时生成直连表项
? 路由守护程序
? 用 route配置静态路由
? ICMP重定向报文
配置接口 IP地址
? 在接口配置模式下
? ip address ip地址 子网掩码
路由守护程序
? 通常这是一个用户进程。
? 在 U n i x系统中，大多数普通的守护程序
都是路由程序和网关程序。
? 可以更新路由表
Defines a path to an IP destination network or subnet
Router(config)#ip route network [mask]
{address | interface}[distance] [permanent]
用 route配置静态路由
ip route 172.16.1.0 255.255.255.0 172.16.2.1
172.16.2.1
SO
静态路由举例
172.16.1.0
B172.16.2.2
Network
A10.0.0.0
桩网络
ip route 0.0.0.0 0.0.0.0 172.16.2.2
缺 省 路由
172.16.2.1
SO
172.16.1.0
B172.16.2.2
Network
A B10.0.0.0
桩网络
ICMP重定向举例
ICMP重定向报文格式
四种类型的重定向报文
I C M P重定向报文的接收者必须查看三个 I P地址
? 导致重定向的 I P地址
? 发送重定向报文的路由器的 I P地址
? 应该采用的路由器 I P地址
关于 I C M P重定向报文有很多规则
? 重定向报文只能由路由器生成，而不能由主机生
成。
? 重定向报文是为主机而不是为路由器使用的。
? 假定路由器和其他一些路由器共同参与某一种选
路协议，则该协议就能消除重定向的需要。
ICMP路由器发现报文
? RFC1256
? 主机在引导以后要广播或多播传送一份 路由器请求报文 。
? 一台或更多台路由器响应一份 路由器通告报文 。
? 另外，路由器定期地广播或多播传送它们的路由器通告报
文，允许每个正在监听的主机相应地更新它们的路由表。
I C M P路由器请求报文的格式
ICMP路由器通告报文格式
? 地址数 指的是报文中所含的地址数。
? 地址项大小 指的是每个路由器地址 4字节的数目，
始终为 2。
? 生存期 指的是通告地址有效的时间（秒数）。
? I P地址 必须是发送路由器的某个地址。
? 优先级 是一个有符号的 32 bit整数，指出该 I P地址
作为默认路由器地址的优先等级，值越大说明优先
级越高，优先级的默认值一般为 0。
路由器操作
? 当路由器启动时，它定期在所有广播或多播传送
接口上发送通告报文。
? 路由器还要监听来自主机的请求报文，并发送路
由器通告报文以响应这些请求报文。
? 如果子网上有多台路由器，由系统管理员为每个
路由器设置优先等级。
主机操作
? 主机在引导期间一般发送三份路由器请求报文，每三秒钟
发送一次。
? 主机也监听来自相邻路由器的请求报文，这些通告报文可
以改变主机的默认路由器。
? 如果没有接收到来自当前默认路由器的通告报文，那么默
认路由器会超时。
? 只要有一般的默认路由器，该路由器就会每隔 1 0分钟发
送通告报文，报文的生命周期是 3 0分钟。这说明主机的
默认表项是不会超时的，即使错过一份或两份通告报文。
路由器发现报文的实现
? 路由器发现报文一般由用户进程（守护程序）创
建和处理。
? I C M P路由器请求报文和 I C M P路由器通告报
文是新加的，不是所有的系统都支持它们。
? 路由器发现还可以利用广播报文来实现。
6.2 动态选路协议（路由协议）
? 路 由器上有一个进程称为路由守护程序（
routing daemon），它运行选路协议，并
与相邻的一些路由器进行通信。
? 路由守护程序根据它从相邻路由器接收到的
信息，更新内核中的路由表。
? 路由守护程序将选路策略加入到系统中，选择路由并加入
到内核的路由表中。
? 如果守护程序发现前往同一信宿存在多条路由，那么它
（以某种方法）将选择最佳路由并加入内核路由表中。
? 如果路由守护程序发现一条链路已经断开（可能是路由器
崩溃或电话线路不好），它可以删除受影响的路由或增加
另一条路由以绕过该问题。
动态路由协议的类型
自治系统 AS
内部网关协议 IGP
外部网关协议 EGP,BGP
基于距离向量的 RIP,IGRP
基于链路状态数据库的 OSPF
r o u t e d 和 g a t e d 所支持的选路协议
Unix选路守护程序
? U n i x系统上常常运行名为 r o u t e d路由守护程序，几
乎在所有的 T C P / I P实现中都提供该程序，该程序只使
用 R I P进行通信。
? 另一个程序是 g a t e d,I G P和 E G P都支持它。
? 大多数运行路由守护程序的系统都可以运行 r o u t e d，
除非它们需要支持 g a t e d所支持的其他协议。
一、路由信息协议 RIP
? RFC 1058
是一个基于距离向量的路由协议
?路由器之间周期性地交换路由信息，并重新计算路由表。
C
D
B
A
C B AD
Routing
Table
Routing
Table
Routing
Table
Routing
Table
距离 — 多远
向量 — 在哪个方向
RIP基于跳数选路
? 基于距离向量的分布式路由选择协议
? 距离 —— 跳数
? RIP认为：好路由就是跳数最小的路由
规定：跳数 ≤15
? RIP只适合于小型互连网
RIP的工作原理
? 每隔 30秒，每个路由器向其相邻路由器广播其路由表
? 所有路由器更新其路由表（距离向量算法）
? 一段时间后，所有路由器都建立起自己的路由表。
? 每条路由都有与之相关的定时器。如果运行 R I P的系统发
现一条路由在 3分钟内未更新，就将该路由的度量设置成无
穷大（ 1 6），并标注为删除。再过 6 0秒，将从本地路由
表中删除该路由，以保证该路由的失效已被传播开。
? RIP使用 UDP进行传送，其 常用的 U D P端口号是 5 2 0。
RIPV1的报文格式
IP首部 UDP首部 RIP报文
IP数据报
UDP数据报
命令 版本 必为 0
地址类别 必为 0
某个网络的 32位 IP地址
必为 0
必为 0
到此网络的距离（ 1-16）
可增加不超过 24个路由格式同上的 20字节
20字节
的路由
4字节的首部
? 命令字段：
? 1表示请求
? 2表示应答。
? 3和 4已经舍弃不用的命令
? 5表示轮询,6表示轮询表项，是两个非正式的命令。
请求表示要求其他系统发送其全部或部分路由表，
应答则包含发送者全部或部分路由表。
? 版本 RIP为 1,RIPV2为 2。
? 地址类别 0—— 请求报文（距离置为 16）
2—— 采用 IP地址
? I P地址以及相应的度量,RIP的度量是跳数。
? 必为 0字段在 RIPV2中是子网掩码和下站 IP
RIP报文的最大长度 =4+20× 25=504字节
采用 RIP协议的 routed程序正常运行的情况
? 初始化：在启动一个路由守护程序时，它先判断
启动了哪些接口，并在每个接口上发送一个请求
报文，要求其他路由器发送完整路由表。
? 接收到请求：如果这个请求是刚才提到的特殊请
求，那么路由器就将完整的路由表发送给请求者。
否则，就处理请求中的每一个表项然后发回响应。
? 接收到响应：使响应生效，可能会更新路由表。
可能会增加新表项，对已有的表项进行修改，或
是将已有表项删除。
? 定期选路更新：每过 3 0秒，所有或部分路由器会
将其完整路由表发送给相邻路由器。
? 触发更新：每当一条路由的度量发生变化时，就
对它进行更新。不需要发送完整路由表，而只需
要发送那些发生变化的表项。
RIP的缺陷
? RIPV1没 有子网地址的概念，即：它不支持无类 IP。
? 好消息传得快，坏消息传得慢。在路由器或链路发生故障
后，需要很长的一段时间才能稳定下来。这段时间通常需
要几分钟。在这段建立时间里，可能会发生循环路由。在
实现 R I P时，必须采用很多措施来防止路由环路的出现，
并使其尽快建立。
? 采用跳数作为路由度量忽略了其他一些应该考虑的因素。
? 跳数最大值为 1 5限制了可以使用 R I P的网络的大小。
维护路由信息的问题 —— 路由循环
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0
Routing Table
10.3.0.0 S0
E0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
0
Routing Table
10.1.0.0 E0
S0
S0
S0
1
210.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
10.2.0.0 S0
S1
S1
S0
1
110.1.0.0
10.4.0.0
10.3.0.0
0
0
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
E0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
Down
Routing Table
10.1.0.0 E0
S0
S0
S0
1
210.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
10.2.0.0 S0
S1
S1
S0
1
110.1.0.0
10.4.0.0
10.3.0.0
0
0
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
2
Routing Table
10.1.0.0 E0
S0
S0
S0
1
210.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
10.2.0.0 S0
S1
S1
S1
1
110.1.0.0
10.4.0.0
10.3.0.0
0
0
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
S0
S0
S0
S0
1
2
10.3.0.0
10.1.0.0
10.2.0.0
10.4.0.0
0
2
Routing Table
E0
S0
S0
S0
1
4
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
S0
3
1
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
症状, 距离计数到无限
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
4
Routing Table
E0
S0
S0
S0
1
6
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
S0
5
1
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
解决办法 1,定义一个最大值
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
16
Routing Table
E0
S0
S0
S0
1
16
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
S0
16
1
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
解决办法 2,水平分割
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 XXX
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
0
Routing Table
E0
S0
S0
S0
1
2
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
E1
1
2
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
解决办法 3,计时器
网络 10.4.0.0 时好时坏
到达计时器的
规定值再更新
网络 10.4.0.0
不通
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
到达计时器的
规定值再更新
解决办法 4,触发更新
A B C
10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
10.1.0.0
网络 10.4.0.0
不通
网络 10.4.0.0
不通
网络 10.4.0.0
不通
RIPV2 RFC1388
? 路由域是一个选路守护程序的标识符，它指出了
这个数据报的所有者。在一个 U n i x实现中，它
可以是选路守护程序的进程号。该域允许管理者
在单个路由器上运行多个 R I P实例，每个实例在
一个选路域内运行。
? 路由标记是为了支持外部网关协议而存在的，它
携带着一个 E G P和 B G P的自治系统号。
RIPV2的优越之处
? 支持无类 IP
? 提供了一种简单的鉴别机制。可以指定 RIP报文
的前 2 0字节表项地址系列为 0 x ffff，
? 路由标记为 2，表项中的其余 16字节包含一个明
文口令。
? RIPV2除了广播外，还支持多播。
? 路由器配置
? 选择路由协议
? 指定网络或接口 Network160.89.0.0
Network 172.30.0.0
IGRP,
RIP
Network 172.16.0.0
RIP
RIP
IGRP
IP 路由配置任务
? 定义一个 IP 路由协议
Router(config)#router protocol [keyword]
Router(config-router)#network network-number
动态路由配置
? Starts the RIP routing process
Router(config)#router rip
Router(config-router)#network network-number
RIP 配置
2.3.0.0router rip
network 172.16.1.0
network 10.1.0.0
RIP 配置举例
router rip
network 10.0.0.0
2.3.0.0router rip
network 192.168.1.0
network 10.2.0.0
172.16.1.1
S2E0 S3
192.168.1.110.1.1.1 10.2.2.210.1.1.2
S2 S3
10.2.2.3
172.16.1.0
A B C 192.168.1.0
E0
验证路由协议 — RIP
RouterA#sh ip protocols
Routing Protocol is "rip"
Sending updates every 30 seconds,next due in 0 seconds
Invalid after 180 seconds,hold down 180,flushed after 240
Outgoing update filter list for all interfaces is
Incoming update filter list for all interfaces is
Redistributing,rip
Default version control,send version 1,receive any version
Interface Send Recv Key-chain
Ethernet0 1 1 2
Serial2 1 1 2
Routing for Networks:
10.0.0.0
172.16.0.0
Routing Information Sources:
Gateway Distance Last Update
10.1.1.2 120 00:00:10
Distance,(default is 120)
172.16.1.1
S2E0 S3
192.168.1.110.1.1.1 10.2.2.210.1.1.2
S2 S3
10.2.2.3
172.16.1.0 A B C 192.168.1.0
E0
查 看 IP 路 由 表
RouterA#sh ip route
Codes,C - connected,S - static,I - IGRP,R - RIP,M - mobile,B -
BGP
D - EIGRP,EX - EIGRP external,O - OSPF,IA - OSPF inter area
N1 - OSPF NSSA external type 1,N2 - OSPF NSSA external type 2
E1 - OSPF external type 1,E2 - OSPF external type 2,E - EGP
i - IS-IS,L1 - IS-IS level-1,L2 - IS-IS level-2,* - candidate
default
U - per-user static route,o - ODR
T - traffic engineered route
Gateway of last resort is not set
172.16.0.0/24 is subnetted,1 subnets
C 172.16.1.0 is directly connected,Ethernet0
10.0.0.0/24 is subnetted,2 subnets
R 10.2.2.0 [120/1] via 10.1.1.2,00:00:07,Serial2
C 10.1.1.0 is directly connected,Serial2
R 192.168.1.0/24 [120/2] via 10.1.1.2,00:00:07,Serial2
172.16.1.1
S2
E0
S3
192.168.1.110.1.1.1 10.2.2.210.1.1.2
S2 S3
10.2.2.3
172.16.1.0 A B C 192.168.1.0
E0
? 收敛快
? 支持无类 IP
? 更新效率高
? 基于带宽选路
? 支持多条开销相同的路径
二,开放最短通路优先 OSPF
Open Shortest Path First
是一个基于链路状态数据库的路由协议
Link-State Packets
SPF
Algorithm
Topological
Database
Shortest Path First Tree
Routing
Table
C A
D
B
OSPF 的拓扑
Token
Ring
Interfaces
Neighbors
Token
Ring
Interfaces
Neighbors
Token
Ring
Interfaces
Cost = 10
Cost = 6Cost = 1785
Neighbors
Token
Ring
Interfaces
Area 1
Area 0Cost = 10
Cost = 6Cost = 1785
Autonomous System
Neighbors
Token
Ring
Interfaces
Area 1
Area 0
Cost = 1785
Cost = 10
Cost = 6
Autonomous System
Neighborship
Database
Lists Neighbors
Neighbors
Token
Ring
Interfaces
Area 1
Area 0Cost = 10
Cost = 6Cost = 1785
Autonomous System
Topology
Database
Lists All Routers
Neighborship
Database
Lists Neighbors
Neighbors
Token
Ring
Interfaces
Area 1
Area 0
Cost = 1785
Cost = 10
Cost = 6
Autonomous System
Routing
Table
Lists Best Routes
Topology
Database
Lists All Routers
Neighborship
Database
Lists Neighbors
Cost = 10
Cost = 1785 Cost = 6
Neighbors
Token
Ring
Interfaces
Area 1
Area 0
OSPF 的实现要点
? 所有的 Router都维持一个 Link State Database
? 每一个 Router都能用 DB的数据算出路由表
? 只要网络拓扑发生变化,DB就能快速更新，从而得到新
的路由表
? DB保持同步
? 直接用 IP数据报传送（不用 UDP)且数据报很短，在 IP
首部协议字段的值是 89。
好处：减少路由信息的通信量
不必将长数据报分片
OSPF的优点（与 RIP相比）
? OSPF可以对每个 I P服务类型计算各自的路由集，这意
味着对于任何目的，可以有多个路由表表项，每个表项对
应着一个 I P服务类型。
? 给每个接口指派一个无维数的费用，可以通过吞吐率、往
返时间、可靠性或其他性能来进行指派，可以给每个 I P
服务类型指派一个单独的费用。
? 当对同一个目的地址存在着多个相同费用的路由时，
OSPF在这些路由上平均分配流量，称之为流量平衡。
? OSPF支持子网：子网掩码与每个通告路由相连。
? 路由器之间的点对点链路不需要每端都有一个 I P地址，
我们称之为无编号网络，这样可以节省 I P地址。
? 采用了一种简单鉴别机制，可以采用类似于 RIPV2的方
法指定一个明文口令。
? OSPF采用多播而不是广播形式，以减少不参与 O S P F的
系统负载。
OSPF 的报文格式
IP head OSPF报文
OSPF head 类型 1至类型 5的 OSPF报文
IP 数据报
24字节
OSPF 的五类报文
? Hello报文，用来发现和维持邻站的可达性
? Database Description报文，向邻站给出自己的链路状态数
据库中的所有链路状态项目的摘要信息
? Link State Request 报文，向对方请求发送某些链路状态项
目的详细信息
? Link State Update 报文，用洪泛法向全网更新的链路状态
? Link State Acknowledgment 报文，对链路更新报文的确认
OSPF 的工作过程
? 路由器刚开始工作时
? 通过 Hello报文获取邻站信息，用来发现和维持邻站的可达性
? 1.每个路由器与邻站交换 Database Description报文
? 2.使用 Link State Request 报文，请求对方发送自己缺少的链路
状态项目的详细信息，使用 Link State Update 报文发送详细信息，
用 Link State Acknowledgment 报文发确认。
? 重复 1,2，全网的 DB逐渐建立起来
? 网络运行过程中
只要有一个路由器的链路状态发生变化，该路由器就使用 Link
State Update 报文，用可靠洪泛法向全网发送更新的链路状态。
可靠洪泛法即：收到更新报文后用 Link State Acknowledgment
报文发确认
建立邻居关系 Neighborship
Hello
afadjfjorqpoeru
39547439070713
Router ID
Hello/dead intervals
Neighbors
Area-ID
Router priority
DR IP address
BDR IP address
Authentication password
Stub area flag
*
*
**
Hello
A
D E
CB
Hello
afadjfjorqpoeru
39547439070713
Router ID
Hello/dead intervals
Neighbors
Area-ID
Router priority
DR IP address
BDR IP address
Authentication password
Stub area flag
*
*
**
Hello
A
D E
CB
选举 DR 和 BDR
DR BDR
? 通过 IP多播交换 Hello信息
? 具有高优先级的路由器被选为 DR和 BDR
P=1 P=0P=1
选举 DR 和 BDR
P=3 P=2
Hello
DR BDR
信息交换过程
172.16.5.1/24
E0
172.16.5.2/24
E1A B
Down State
172.16.5.1/24
E0
172.16.5.2/24
E1
Router B
Neighbors List
172.16.5.1/24,int E1
I am router ID 172.16.5.1 and I see no one.
Down State
Init State
A B
172.16.5.1/24
E0
I am router ID 172.16.5.2,and I see 172.16.5.1.
172.16.5.2/24
E1
Router B
Neighbors List
172.16.5.1/24,int E1
I am router ID 172.16.5.1 and I see no one.
Down State
Init State
A B
172.16.5.1/24
E0
I am router ID 172.16.5.2,and I see 172.16.5.1.
Router A
Neighbors List
172.16.5.2/24,int E0
172.16.5.2/24
E1
Router B
Neighbors List
172.16.5.1/24,int E1
I am router ID 172.16.5.1 and I see no one.
Down State
Init State
Two-Way State
A B
发现路由
E0
172.16.5.1
DR
E0
172.16.5.3
No,I will start exchange because I have a
higher router ID.
I will start exchange because I have router ID 172.16.5.1.Hello
afadjfjorqpoeru
39547439070713
Hello
afadjfjorqpoeru
39547439070713
Exstart State
Here is a summary of my link-state database,DBD
afadjfjorqpoeru
39547439070713
Exchange State
Here is a summary of my link-state database.DBD
afadjfjorqpoeru
39547439070713
E0
172.16.5.1
E0
172.16.5.3
No,I will start exchange because I have a
higher router ID.
I will start exchange because I have router ID 172.16.5.1.Hello
afadjfjorqpoeru
39547439070713
Hello
afadjfjorqpoeru
39547439070713
Exstart State
DR
E0
172.16.5.1
E0
172.16.5.3
Thanks for the information!LSAck
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
DR
I need the complete entry for network 172.16.6.0/24.
Here is the entry for network 172.16.6.0/24.
Thanks for the information!
LSR
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
LSU
afadjfjorqpoeru
39547439070713
Loading State
E0
172.16.5.1
E0
172.16.5.3
Thanks for the information!LSAck
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
DR
Full State
I need the complete entry for network 172.16.6.0/24.
Here is the entry for network 172.16.6.0/24.
Thanks for the information!
LSR
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
LSU
afadjfjorqpoeru
39547439070713
Loading State
E0
172.16.5.1
E0
172.16.5.3
Thanks for the information!LSAck
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
DR
选择路由
Topology Table
Net Cost Out Interface
10.2.2.0 7 To0
10.3.3.0 17 To0
10.3.3.0 20 E0
TokenRing
Cost=10
Cost=6
FDDI
Cost=1
A B C
This is the best route to 10.3.3.0.
10.1.1.0/24 10.2.2.0/24 10.3.3.0/24
10.4.4.0/24
Cost=10
维持路由信息
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DRs
x
Link-State Change
LSU1
DR
A
B
LSU
2
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DR
? DR用广播地址 224.0.0.5 通知其它路由器
x
Link-State Change
LSU1
DR
A
B
LSU
3
LSU
2
x
Link-State Change
LSU1
DR
A
B
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DR
? DR用广播地址 224.0.0.5 通知其它路由器
I need to update
my routing table.4
LSU
3
LSU
2
x
Link-State Change
LSU1
DR
A
B
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DR
? DR用广播地址 224.0.0.5 通知其它路由器
Is entry in
link-state
database?
LSA
LSU
No
Run OSPF to calculate
new routing table
Add to database
Flood LSU
End
Send LSAck
to DR
Yes
Is seq,#
the same? Yes Ignore LSU
Is entry in
link-state
database?
LSA
LSU
No
Run SPF to calculate
new routing table
Add to database
Flood LSU
Send LSAck
to DR
End
No
Send LSU
with newer
information to
source
Is seq,#
higher?
No
Yes
Is seq,#
the same? Yes Ignore LSU
Is entry in
link-state
database?
LSA
LSU
No
Run SPF to calculate
new routing table
Add to database
Flood LSU
Send LSAck
to DR
End End
Yes
Go
to
A
A
No
Send LSU
with newer
information to
source
Is seq,#
higher?
No
Yes
Is seq,#
the same? Yes Ignore LSU
Is entry in
link-state
database?
LSA
LSU
No
Run SPF to calculate
new routing table
Add to database
Flood LSU
Send LSAck
to DR
End End
三、边界网关协议 BGP
Border Gateway Protocol
自治系统 65000 自治系统 65500
IGPs,RIP,IGRP,
OSPF,EIGRP EGPs,BGP
边界网关协议 BGP
? 1989年起，新的外部网关协议就称为边界网关
协议 BGP, RFC1267 对第 3版的 B G P进行了
描述。
? 1995年公布 BGP-4 （ BGPV4 支持 CIDR）
RFC 1467
? RFC 1268 描述了如何在 Internet中使用 BGP
边界网关协议 BGP
? 边界网关协议 BGP必须考虑有关策略，包括政治、安全、
经济等方面（由人工设置）。
? 两个 BGP路由器通信时先要建立 TCP连接
? BGP基本上是一个距离向量协议，但和其它的距离向量
协议有很大的差别。 BGP不是保留到每一个目的站的距
离，而是保留到每一个目的站的完整路由，并周期性地
将它使用的每一个路由告诉其邻站。
BGP工作原理举例
F从邻站得到至
目的站 D的信息 A
J
H
G
E
B C
D
F
I
B,B-C-D
G, G-C-D
I,I-F-G-C-D
E,E-F-G-C-D
? F收到这些信息后要找出其中最好的一个
? I和 E的显然不能用，因为这两条路由都通过 F。
? 因此，只能在 B和 G提供的路由中选择。
? 每个 BGP路由器都有一个模块用来检查到某个目的站
的路由，并给他们打分，对每个到该目的站的, 距离,
返回一个数值，不符合路由选择策略的就返回无穷大。
BGP-4共使用四种报文
? Open报文，用来与相邻的路由器建立邻站关系。
? Update报文，用来发送某一路由的信息，以及
列出要撤销的多条路由。
? Keepalive报文，用来确认 Open报文，和周期
性地证实邻站关系。
? Notification报文，用来发送监测到的差错。
BGP有三个功能过程
? 邻站探测 neighbor acquisition
? 邻站可达性 neighbor reachability
? 网络可达性 network reachability
邻站探测
Open
Keepalive
从而建立邻站关系
邻站可达性
Keepalive
周期性地交换 Keepalive报文，从而保持邻站关系。
Keepalive
网络可达性
? 每一个路由器都要维持一个所能到达的子网以
及到此子网的最佳路由的路由表。
? 网络的可达性 就是当路由表发生变化时，路由
器就用广播方式对所有执行 BGP的路由器发出
一个 Update报文，从而使所有的 BGP路由器
维持新的路由信息。
Update
X
Update
Update
Update
BGP 用于不同的自治系统之间
BGP B
BGP
AS
65500
AS
65250
BGPAS64520
AS
65000
A
B C
F
ED
6.3 无类路由选择 CIDR
Classless Inter-Domain Routing
? RFC1518 和 RFC1519是它的综述,RFC1467对 Internet中
CIDR的开发状况进行了小结
? CIDR用来解决两类问题：
? 主干网路由表的增长 —— 聚合路由，使属于同一个 AS的多个地址
映射到一个地址上。
? IP地址不够用 —— 合理分配网络号和主机号的长度，使得 IP地址
被充分利用。
? 关键技术：在 IP地址和路由表中变长前缀之间有效地找到最长匹
配
? 参考网站,http://www.netland.com.cn/
有类和无类路由协议
路 由 协 议 有类或无类
路由信息协议 RIP 有类
路由信息协议 RIPV2 无类
内部网关路由协议 IGRP 有类
开放最短通路优先 OSPF 无类
边界网关协议 BGP 无类
增强内部网关路由协议 EIGRP 无类
课下作 业（必做）
1,查资料：各种路由算法和路由协议及相关研究
2.查资料：路由协议的测试
3,查路由器方面的资料
课下作 业（选做）
1.熟悉 OSPF协议，按要求编写寻求最短路径的程序。
（ 1）程序提示用户输入有向图的顶点数和源站点 V，
程序根据用户的输入创建类，分配所需空间。
（ 2）程序提示用户输入有向图对应的邻接矩阵。
（ 3）输出 V到其他各点的最短路径。
路由协议
TCP/IP详解卷 1,CH9,CH10
主要内容
? 6.1 IP选路
? 6.2 动态选路协议（路由协议）
? RIP
? OSPF
? BGP
? 6.3 无类路由选择 CIDR
? 课下作业
6.1 IP选路
为数据包选路的可以是路由器，
也可以是主机（该主机被配置为路由器）
生成静态路由的方法
? 配置接口 IP地址时生成直连表项
? 路由守护程序
? 用 route配置静态路由
? ICMP重定向报文
配置接口 IP地址
? 在接口配置模式下
? ip address ip地址 子网掩码
路由守护程序
? 通常这是一个用户进程。
? 在 U n i x系统中，大多数普通的守护程序
都是路由程序和网关程序。
? 可以更新路由表
Defines a path to an IP destination network or subnet
Router(config)#ip route network [mask]
{address | interface}[distance] [permanent]
用 route配置静态路由
ip route 172.16.1.0 255.255.255.0 172.16.2.1
172.16.2.1
SO
静态路由举例
172.16.1.0
B172.16.2.2
Network
A10.0.0.0
桩网络
ip route 0.0.0.0 0.0.0.0 172.16.2.2
缺 省 路由
172.16.2.1
SO
172.16.1.0
B172.16.2.2
Network
A B10.0.0.0
桩网络
ICMP重定向举例
ICMP重定向报文格式
四种类型的重定向报文
I C M P重定向报文的接收者必须查看三个 I P地址
? 导致重定向的 I P地址
? 发送重定向报文的路由器的 I P地址
? 应该采用的路由器 I P地址
关于 I C M P重定向报文有很多规则
? 重定向报文只能由路由器生成，而不能由主机生
成。
? 重定向报文是为主机而不是为路由器使用的。
? 假定路由器和其他一些路由器共同参与某一种选
路协议，则该协议就能消除重定向的需要。
ICMP路由器发现报文
? RFC1256
? 主机在引导以后要广播或多播传送一份 路由器请求报文 。
? 一台或更多台路由器响应一份 路由器通告报文 。
? 另外，路由器定期地广播或多播传送它们的路由器通告报
文，允许每个正在监听的主机相应地更新它们的路由表。
I C M P路由器请求报文的格式
ICMP路由器通告报文格式
? 地址数 指的是报文中所含的地址数。
? 地址项大小 指的是每个路由器地址 4字节的数目，
始终为 2。
? 生存期 指的是通告地址有效的时间（秒数）。
? I P地址 必须是发送路由器的某个地址。
? 优先级 是一个有符号的 32 bit整数，指出该 I P地址
作为默认路由器地址的优先等级，值越大说明优先
级越高，优先级的默认值一般为 0。
路由器操作
? 当路由器启动时，它定期在所有广播或多播传送
接口上发送通告报文。
? 路由器还要监听来自主机的请求报文，并发送路
由器通告报文以响应这些请求报文。
? 如果子网上有多台路由器，由系统管理员为每个
路由器设置优先等级。
主机操作
? 主机在引导期间一般发送三份路由器请求报文，每三秒钟
发送一次。
? 主机也监听来自相邻路由器的请求报文，这些通告报文可
以改变主机的默认路由器。
? 如果没有接收到来自当前默认路由器的通告报文，那么默
认路由器会超时。
? 只要有一般的默认路由器，该路由器就会每隔 1 0分钟发
送通告报文，报文的生命周期是 3 0分钟。这说明主机的
默认表项是不会超时的，即使错过一份或两份通告报文。
路由器发现报文的实现
? 路由器发现报文一般由用户进程（守护程序）创
建和处理。
? I C M P路由器请求报文和 I C M P路由器通告报
文是新加的，不是所有的系统都支持它们。
? 路由器发现还可以利用广播报文来实现。
6.2 动态选路协议（路由协议）
? 路 由器上有一个进程称为路由守护程序（
routing daemon），它运行选路协议，并
与相邻的一些路由器进行通信。
? 路由守护程序根据它从相邻路由器接收到的
信息，更新内核中的路由表。
? 路由守护程序将选路策略加入到系统中，选择路由并加入
到内核的路由表中。
? 如果守护程序发现前往同一信宿存在多条路由，那么它
（以某种方法）将选择最佳路由并加入内核路由表中。
? 如果路由守护程序发现一条链路已经断开（可能是路由器
崩溃或电话线路不好），它可以删除受影响的路由或增加
另一条路由以绕过该问题。
动态路由协议的类型
自治系统 AS
内部网关协议 IGP
外部网关协议 EGP,BGP
基于距离向量的 RIP,IGRP
基于链路状态数据库的 OSPF
r o u t e d 和 g a t e d 所支持的选路协议
Unix选路守护程序
? U n i x系统上常常运行名为 r o u t e d路由守护程序，几
乎在所有的 T C P / I P实现中都提供该程序，该程序只使
用 R I P进行通信。
? 另一个程序是 g a t e d,I G P和 E G P都支持它。
? 大多数运行路由守护程序的系统都可以运行 r o u t e d，
除非它们需要支持 g a t e d所支持的其他协议。
一、路由信息协议 RIP
? RFC 1058
是一个基于距离向量的路由协议
?路由器之间周期性地交换路由信息，并重新计算路由表。
C
D
B
A
C B AD
Routing
Table
Routing
Table
Routing
Table
Routing
Table
距离 — 多远
向量 — 在哪个方向
RIP基于跳数选路
? 基于距离向量的分布式路由选择协议
? 距离 —— 跳数
? RIP认为：好路由就是跳数最小的路由
规定：跳数 ≤15
? RIP只适合于小型互连网
RIP的工作原理
? 每隔 30秒，每个路由器向其相邻路由器广播其路由表
? 所有路由器更新其路由表（距离向量算法）
? 一段时间后，所有路由器都建立起自己的路由表。
? 每条路由都有与之相关的定时器。如果运行 R I P的系统发
现一条路由在 3分钟内未更新，就将该路由的度量设置成无
穷大（ 1 6），并标注为删除。再过 6 0秒，将从本地路由
表中删除该路由，以保证该路由的失效已被传播开。
? RIP使用 UDP进行传送，其 常用的 U D P端口号是 5 2 0。
RIPV1的报文格式
IP首部 UDP首部 RIP报文
IP数据报
UDP数据报
命令 版本 必为 0
地址类别 必为 0
某个网络的 32位 IP地址
必为 0
必为 0
到此网络的距离（ 1-16）
可增加不超过 24个路由格式同上的 20字节
20字节
的路由
4字节的首部
? 命令字段：
? 1表示请求
? 2表示应答。
? 3和 4已经舍弃不用的命令
? 5表示轮询,6表示轮询表项，是两个非正式的命令。
请求表示要求其他系统发送其全部或部分路由表，
应答则包含发送者全部或部分路由表。
? 版本 RIP为 1,RIPV2为 2。
? 地址类别 0—— 请求报文（距离置为 16）
2—— 采用 IP地址
? I P地址以及相应的度量,RIP的度量是跳数。
? 必为 0字段在 RIPV2中是子网掩码和下站 IP
RIP报文的最大长度 =4+20× 25=504字节
采用 RIP协议的 routed程序正常运行的情况
? 初始化：在启动一个路由守护程序时，它先判断
启动了哪些接口，并在每个接口上发送一个请求
报文，要求其他路由器发送完整路由表。
? 接收到请求：如果这个请求是刚才提到的特殊请
求，那么路由器就将完整的路由表发送给请求者。
否则，就处理请求中的每一个表项然后发回响应。
? 接收到响应：使响应生效，可能会更新路由表。
可能会增加新表项，对已有的表项进行修改，或
是将已有表项删除。
? 定期选路更新：每过 3 0秒，所有或部分路由器会
将其完整路由表发送给相邻路由器。
? 触发更新：每当一条路由的度量发生变化时，就
对它进行更新。不需要发送完整路由表，而只需
要发送那些发生变化的表项。
RIP的缺陷
? RIPV1没 有子网地址的概念，即：它不支持无类 IP。
? 好消息传得快，坏消息传得慢。在路由器或链路发生故障
后，需要很长的一段时间才能稳定下来。这段时间通常需
要几分钟。在这段建立时间里，可能会发生循环路由。在
实现 R I P时，必须采用很多措施来防止路由环路的出现，
并使其尽快建立。
? 采用跳数作为路由度量忽略了其他一些应该考虑的因素。
? 跳数最大值为 1 5限制了可以使用 R I P的网络的大小。
维护路由信息的问题 —— 路由循环
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0
Routing Table
10.3.0.0 S0
E0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
0
Routing Table
10.1.0.0 E0
S0
S0
S0
1
210.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
10.2.0.0 S0
S1
S1
S0
1
110.1.0.0
10.4.0.0
10.3.0.0
0
0
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
E0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
Down
Routing Table
10.1.0.0 E0
S0
S0
S0
1
210.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
10.2.0.0 S0
S1
S1
S0
1
110.1.0.0
10.4.0.0
10.3.0.0
0
0
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
2
Routing Table
10.1.0.0 E0
S0
S0
S0
1
210.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
10.2.0.0 S0
S1
S1
S1
1
110.1.0.0
10.4.0.0
10.3.0.0
0
0
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
S0
S0
S0
S0
1
2
10.3.0.0
10.1.0.0
10.2.0.0
10.4.0.0
0
2
Routing Table
E0
S0
S0
S0
1
4
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
S0
3
1
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
症状, 距离计数到无限
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
4
Routing Table
E0
S0
S0
S0
1
6
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
S0
5
1
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
解决办法 1,定义一个最大值
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
16
Routing Table
E0
S0
S0
S0
1
16
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
S0
16
1
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
解决办法 2,水平分割
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 XXX
Routing Table
10.3.0.0 S0
S0
S0
S0
1
210.1.0.0
10.2.0.0
10.4.0.0
0
0
Routing Table
E0
S0
S0
S0
1
2
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
S0
S1
S1
E1
1
2
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
解决办法 3,计时器
网络 10.4.0.0 时好时坏
到达计时器的
规定值再更新
网络 10.4.0.0
不通
A B C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
到达计时器的
规定值再更新
解决办法 4,触发更新
A B C
10.2.0.0 10.3.0.0 10.4.0.0
E0 S0 S0 S1 S0 E0 X
10.1.0.0
网络 10.4.0.0
不通
网络 10.4.0.0
不通
网络 10.4.0.0
不通
RIPV2 RFC1388
? 路由域是一个选路守护程序的标识符，它指出了
这个数据报的所有者。在一个 U n i x实现中，它
可以是选路守护程序的进程号。该域允许管理者
在单个路由器上运行多个 R I P实例，每个实例在
一个选路域内运行。
? 路由标记是为了支持外部网关协议而存在的，它
携带着一个 E G P和 B G P的自治系统号。
RIPV2的优越之处
? 支持无类 IP
? 提供了一种简单的鉴别机制。可以指定 RIP报文
的前 2 0字节表项地址系列为 0 x ffff，
? 路由标记为 2，表项中的其余 16字节包含一个明
文口令。
? RIPV2除了广播外，还支持多播。
? 路由器配置
? 选择路由协议
? 指定网络或接口 Network160.89.0.0
Network 172.30.0.0
IGRP,
RIP
Network 172.16.0.0
RIP
RIP
IGRP
IP 路由配置任务
? 定义一个 IP 路由协议
Router(config)#router protocol [keyword]
Router(config-router)#network network-number
动态路由配置
? Starts the RIP routing process
Router(config)#router rip
Router(config-router)#network network-number
RIP 配置
2.3.0.0router rip
network 172.16.1.0
network 10.1.0.0
RIP 配置举例
router rip
network 10.0.0.0
2.3.0.0router rip
network 192.168.1.0
network 10.2.0.0
172.16.1.1
S2E0 S3
192.168.1.110.1.1.1 10.2.2.210.1.1.2
S2 S3
10.2.2.3
172.16.1.0
A B C 192.168.1.0
E0
验证路由协议 — RIP
RouterA#sh ip protocols
Routing Protocol is "rip"
Sending updates every 30 seconds,next due in 0 seconds
Invalid after 180 seconds,hold down 180,flushed after 240
Outgoing update filter list for all interfaces is
Incoming update filter list for all interfaces is
Redistributing,rip
Default version control,send version 1,receive any version
Interface Send Recv Key-chain
Ethernet0 1 1 2
Serial2 1 1 2
Routing for Networks:
10.0.0.0
172.16.0.0
Routing Information Sources:
Gateway Distance Last Update
10.1.1.2 120 00:00:10
Distance,(default is 120)
172.16.1.1
S2E0 S3
192.168.1.110.1.1.1 10.2.2.210.1.1.2
S2 S3
10.2.2.3
172.16.1.0 A B C 192.168.1.0
E0
查 看 IP 路 由 表
RouterA#sh ip route
Codes,C - connected,S - static,I - IGRP,R - RIP,M - mobile,B -
BGP
D - EIGRP,EX - EIGRP external,O - OSPF,IA - OSPF inter area
N1 - OSPF NSSA external type 1,N2 - OSPF NSSA external type 2
E1 - OSPF external type 1,E2 - OSPF external type 2,E - EGP
i - IS-IS,L1 - IS-IS level-1,L2 - IS-IS level-2,* - candidate
default
U - per-user static route,o - ODR
T - traffic engineered route
Gateway of last resort is not set
172.16.0.0/24 is subnetted,1 subnets
C 172.16.1.0 is directly connected,Ethernet0
10.0.0.0/24 is subnetted,2 subnets
R 10.2.2.0 [120/1] via 10.1.1.2,00:00:07,Serial2
C 10.1.1.0 is directly connected,Serial2
R 192.168.1.0/24 [120/2] via 10.1.1.2,00:00:07,Serial2
172.16.1.1
S2
E0
S3
192.168.1.110.1.1.1 10.2.2.210.1.1.2
S2 S3
10.2.2.3
172.16.1.0 A B C 192.168.1.0
E0
? 收敛快
? 支持无类 IP
? 更新效率高
? 基于带宽选路
? 支持多条开销相同的路径
二,开放最短通路优先 OSPF
Open Shortest Path First
是一个基于链路状态数据库的路由协议
Link-State Packets
SPF
Algorithm
Topological
Database
Shortest Path First Tree
Routing
Table
C A
D
B
OSPF 的拓扑
Token
Ring
Interfaces
Neighbors
Token
Ring
Interfaces
Neighbors
Token
Ring
Interfaces
Cost = 10
Cost = 6Cost = 1785
Neighbors
Token
Ring
Interfaces
Area 1
Area 0Cost = 10
Cost = 6Cost = 1785
Autonomous System
Neighbors
Token
Ring
Interfaces
Area 1
Area 0
Cost = 1785
Cost = 10
Cost = 6
Autonomous System
Neighborship
Database
Lists Neighbors
Neighbors
Token
Ring
Interfaces
Area 1
Area 0Cost = 10
Cost = 6Cost = 1785
Autonomous System
Topology
Database
Lists All Routers
Neighborship
Database
Lists Neighbors
Neighbors
Token
Ring
Interfaces
Area 1
Area 0
Cost = 1785
Cost = 10
Cost = 6
Autonomous System
Routing
Table
Lists Best Routes
Topology
Database
Lists All Routers
Neighborship
Database
Lists Neighbors
Cost = 10
Cost = 1785 Cost = 6
Neighbors
Token
Ring
Interfaces
Area 1
Area 0
OSPF 的实现要点
? 所有的 Router都维持一个 Link State Database
? 每一个 Router都能用 DB的数据算出路由表
? 只要网络拓扑发生变化,DB就能快速更新，从而得到新
的路由表
? DB保持同步
? 直接用 IP数据报传送（不用 UDP)且数据报很短，在 IP
首部协议字段的值是 89。
好处：减少路由信息的通信量
不必将长数据报分片
OSPF的优点（与 RIP相比）
? OSPF可以对每个 I P服务类型计算各自的路由集，这意
味着对于任何目的，可以有多个路由表表项，每个表项对
应着一个 I P服务类型。
? 给每个接口指派一个无维数的费用，可以通过吞吐率、往
返时间、可靠性或其他性能来进行指派，可以给每个 I P
服务类型指派一个单独的费用。
? 当对同一个目的地址存在着多个相同费用的路由时，
OSPF在这些路由上平均分配流量，称之为流量平衡。
? OSPF支持子网：子网掩码与每个通告路由相连。
? 路由器之间的点对点链路不需要每端都有一个 I P地址，
我们称之为无编号网络，这样可以节省 I P地址。
? 采用了一种简单鉴别机制，可以采用类似于 RIPV2的方
法指定一个明文口令。
? OSPF采用多播而不是广播形式，以减少不参与 O S P F的
系统负载。
OSPF 的报文格式
IP head OSPF报文
OSPF head 类型 1至类型 5的 OSPF报文
IP 数据报
24字节
OSPF 的五类报文
? Hello报文，用来发现和维持邻站的可达性
? Database Description报文，向邻站给出自己的链路状态数
据库中的所有链路状态项目的摘要信息
? Link State Request 报文，向对方请求发送某些链路状态项
目的详细信息
? Link State Update 报文，用洪泛法向全网更新的链路状态
? Link State Acknowledgment 报文，对链路更新报文的确认
OSPF 的工作过程
? 路由器刚开始工作时
? 通过 Hello报文获取邻站信息，用来发现和维持邻站的可达性
? 1.每个路由器与邻站交换 Database Description报文
? 2.使用 Link State Request 报文，请求对方发送自己缺少的链路
状态项目的详细信息，使用 Link State Update 报文发送详细信息，
用 Link State Acknowledgment 报文发确认。
? 重复 1,2，全网的 DB逐渐建立起来
? 网络运行过程中
只要有一个路由器的链路状态发生变化，该路由器就使用 Link
State Update 报文，用可靠洪泛法向全网发送更新的链路状态。
可靠洪泛法即：收到更新报文后用 Link State Acknowledgment
报文发确认
建立邻居关系 Neighborship
Hello
afadjfjorqpoeru
39547439070713
Router ID
Hello/dead intervals
Neighbors
Area-ID
Router priority
DR IP address
BDR IP address
Authentication password
Stub area flag
*
*
**
Hello
A
D E
CB
Hello
afadjfjorqpoeru
39547439070713
Router ID
Hello/dead intervals
Neighbors
Area-ID
Router priority
DR IP address
BDR IP address
Authentication password
Stub area flag
*
*
**
Hello
A
D E
CB
选举 DR 和 BDR
DR BDR
? 通过 IP多播交换 Hello信息
? 具有高优先级的路由器被选为 DR和 BDR
P=1 P=0P=1
选举 DR 和 BDR
P=3 P=2
Hello
DR BDR
信息交换过程
172.16.5.1/24
E0
172.16.5.2/24
E1A B
Down State
172.16.5.1/24
E0
172.16.5.2/24
E1
Router B
Neighbors List
172.16.5.1/24,int E1
I am router ID 172.16.5.1 and I see no one.
Down State
Init State
A B
172.16.5.1/24
E0
I am router ID 172.16.5.2,and I see 172.16.5.1.
172.16.5.2/24
E1
Router B
Neighbors List
172.16.5.1/24,int E1
I am router ID 172.16.5.1 and I see no one.
Down State
Init State
A B
172.16.5.1/24
E0
I am router ID 172.16.5.2,and I see 172.16.5.1.
Router A
Neighbors List
172.16.5.2/24,int E0
172.16.5.2/24
E1
Router B
Neighbors List
172.16.5.1/24,int E1
I am router ID 172.16.5.1 and I see no one.
Down State
Init State
Two-Way State
A B
发现路由
E0
172.16.5.1
DR
E0
172.16.5.3
No,I will start exchange because I have a
higher router ID.
I will start exchange because I have router ID 172.16.5.1.Hello
afadjfjorqpoeru
39547439070713
Hello
afadjfjorqpoeru
39547439070713
Exstart State
Here is a summary of my link-state database,DBD
afadjfjorqpoeru
39547439070713
Exchange State
Here is a summary of my link-state database.DBD
afadjfjorqpoeru
39547439070713
E0
172.16.5.1
E0
172.16.5.3
No,I will start exchange because I have a
higher router ID.
I will start exchange because I have router ID 172.16.5.1.Hello
afadjfjorqpoeru
39547439070713
Hello
afadjfjorqpoeru
39547439070713
Exstart State
DR
E0
172.16.5.1
E0
172.16.5.3
Thanks for the information!LSAck
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
DR
I need the complete entry for network 172.16.6.0/24.
Here is the entry for network 172.16.6.0/24.
Thanks for the information!
LSR
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
LSU
afadjfjorqpoeru
39547439070713
Loading State
E0
172.16.5.1
E0
172.16.5.3
Thanks for the information!LSAck
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
DR
Full State
I need the complete entry for network 172.16.6.0/24.
Here is the entry for network 172.16.6.0/24.
Thanks for the information!
LSR
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
LSU
afadjfjorqpoeru
39547439070713
Loading State
E0
172.16.5.1
E0
172.16.5.3
Thanks for the information!LSAck
afadjfjorqpoeru
39547439070713
LSAck
afadjfjorqpoeru
39547439070713
DR
选择路由
Topology Table
Net Cost Out Interface
10.2.2.0 7 To0
10.3.3.0 17 To0
10.3.3.0 20 E0
TokenRing
Cost=10
Cost=6
FDDI
Cost=1
A B C
This is the best route to 10.3.3.0.
10.1.1.0/24 10.2.2.0/24 10.3.3.0/24
10.4.4.0/24
Cost=10
维持路由信息
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DRs
x
Link-State Change
LSU1
DR
A
B
LSU
2
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DR
? DR用广播地址 224.0.0.5 通知其它路由器
x
Link-State Change
LSU1
DR
A
B
LSU
3
LSU
2
x
Link-State Change
LSU1
DR
A
B
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DR
? DR用广播地址 224.0.0.5 通知其它路由器
I need to update
my routing table.4
LSU
3
LSU
2
x
Link-State Change
LSU1
DR
A
B
? 路由器 A 用广播地址 224.0.0.6 通知所有的 OSPF DR
? DR用广播地址 224.0.0.5 通知其它路由器
Is entry in
link-state
database?
LSA
LSU
No
Run OSPF to calculate
new routing table
Add to database
Flood LSU
End
Send LSAck
to DR
Yes
Is seq,#
the same? Yes Ignore LSU
Is entry in
link-state
database?
LSA
LSU
No
Run SPF to calculate
new routing table
Add to database
Flood LSU
Send LSAck
to DR
End
No
Send LSU
with newer
information to
source
Is seq,#
higher?
No
Yes
Is seq,#
the same? Yes Ignore LSU
Is entry in
link-state
database?
LSA
LSU
No
Run SPF to calculate
new routing table
Add to database
Flood LSU
Send LSAck
to DR
End End
Yes
Go
to
A
A
No
Send LSU
with newer
information to
source
Is seq,#
higher?
No
Yes
Is seq,#
the same? Yes Ignore LSU
Is entry in
link-state
database?
LSA
LSU
No
Run SPF to calculate
new routing table
Add to database
Flood LSU
Send LSAck
to DR
End End
三、边界网关协议 BGP
Border Gateway Protocol
自治系统 65000 自治系统 65500
IGPs,RIP,IGRP,
OSPF,EIGRP EGPs,BGP
边界网关协议 BGP
? 1989年起，新的外部网关协议就称为边界网关
协议 BGP, RFC1267 对第 3版的 B G P进行了
描述。
? 1995年公布 BGP-4 （ BGPV4 支持 CIDR）
RFC 1467
? RFC 1268 描述了如何在 Internet中使用 BGP
边界网关协议 BGP
? 边界网关协议 BGP必须考虑有关策略，包括政治、安全、
经济等方面（由人工设置）。
? 两个 BGP路由器通信时先要建立 TCP连接
? BGP基本上是一个距离向量协议，但和其它的距离向量
协议有很大的差别。 BGP不是保留到每一个目的站的距
离，而是保留到每一个目的站的完整路由，并周期性地
将它使用的每一个路由告诉其邻站。
BGP工作原理举例
F从邻站得到至
目的站 D的信息 A
J
H
G
E
B C
D
F
I
B,B-C-D
G, G-C-D
I,I-F-G-C-D
E,E-F-G-C-D
? F收到这些信息后要找出其中最好的一个
? I和 E的显然不能用，因为这两条路由都通过 F。
? 因此，只能在 B和 G提供的路由中选择。
? 每个 BGP路由器都有一个模块用来检查到某个目的站
的路由，并给他们打分，对每个到该目的站的, 距离,
返回一个数值，不符合路由选择策略的就返回无穷大。
BGP-4共使用四种报文
? Open报文，用来与相邻的路由器建立邻站关系。
? Update报文，用来发送某一路由的信息，以及
列出要撤销的多条路由。
? Keepalive报文，用来确认 Open报文，和周期
性地证实邻站关系。
? Notification报文，用来发送监测到的差错。
BGP有三个功能过程
? 邻站探测 neighbor acquisition
? 邻站可达性 neighbor reachability
? 网络可达性 network reachability
邻站探测
Open
Keepalive
从而建立邻站关系
邻站可达性
Keepalive
周期性地交换 Keepalive报文，从而保持邻站关系。
Keepalive
网络可达性
? 每一个路由器都要维持一个所能到达的子网以
及到此子网的最佳路由的路由表。
? 网络的可达性 就是当路由表发生变化时，路由
器就用广播方式对所有执行 BGP的路由器发出
一个 Update报文，从而使所有的 BGP路由器
维持新的路由信息。
Update
X
Update
Update
Update
BGP 用于不同的自治系统之间
BGP B
BGP
AS
65500
AS
65250
BGPAS64520
AS
65000
A
B C
F
ED
6.3 无类路由选择 CIDR
Classless Inter-Domain Routing
? RFC1518 和 RFC1519是它的综述,RFC1467对 Internet中
CIDR的开发状况进行了小结
? CIDR用来解决两类问题：
? 主干网路由表的增长 —— 聚合路由，使属于同一个 AS的多个地址
映射到一个地址上。
? IP地址不够用 —— 合理分配网络号和主机号的长度，使得 IP地址
被充分利用。
? 关键技术：在 IP地址和路由表中变长前缀之间有效地找到最长匹
配
? 参考网站,http://www.netland.com.cn/
有类和无类路由协议
路 由 协 议 有类或无类
路由信息协议 RIP 有类
路由信息协议 RIPV2 无类
内部网关路由协议 IGRP 有类
开放最短通路优先 OSPF 无类
边界网关协议 BGP 无类
增强内部网关路由协议 EIGRP 无类
课下作 业（必做）
1,查资料：各种路由算法和路由协议及相关研究
2.查资料：路由协议的测试
3,查路由器方面的资料
课下作 业（选做）
1.熟悉 OSPF协议，按要求编写寻求最短路径的程序。
（ 1）程序提示用户输入有向图的顶点数和源站点 V，
程序根据用户的输入创建类，分配所需空间。
（ 2）程序提示用户输入有向图对应的邻接矩阵。
（ 3）输出 V到其他各点的最短路径。
