一、基本概念

1、理想的路由算法应具备的特点

2、分层次的路由选择协议

二、内部网关协议RIP

1、特点

2、路由交换信息

3、距离向量算法

4、坏消息传送慢问题

5、RIP报文格式

三、内部网关协议OSPF

1、特点

2、其他特点

3、自治系统区域划分

4、OSPF的5中分组类型

5、OFPS数据报格式

该章节主要讨论如何得到路由表

一、基本概念

1、理想的路由算法应具备的特点

正确和完整：所有的数据分组一定最终能到达终点
简单：不能有太大开销，增加通信负担
自适应：自动调整各个路径的负载，1负担大了就走2
稳定：网络拓扑和通信量稳定时，路由路径不能老是变化
公平：大多数用户的时延都差不多
最佳：最目标要求而言，相对最优

静态路由选择：人工配置，用于小网络
动态路由选择：由算法自适应网络变化而动态调整路由表达到最佳

2、分层次的路由选择协议

许多单位不希望别人知道自己的路由选择协议细节，同时希望上网
因此，把整个互联网分为一个个自治系统（autonomous system） AS
一个自治系统由一个单一的技术来管理多个网络、IP地址和路由器
A自治系统有A的一套，B有B的一套
你打你的，我打我的
于是，将整个互联网的路由协议分为两层：
在一个自治系统内部使用的路由器协议：内部网关协议（Internal Gateway Protocal）
在不同自治系统之间使用的路由器协议：外部网关协议（External Gateway Protocal）
自治系统内的路由选择：域内路由选择
不同资质系统之间的路由选择：域间路由选择

常用内部网关协议是RIP和OSPF
常用外部网关协议是BGP-4

二、内部网关协议RIP

1、特点

路由信息协议RIP：Routing Information Protocol
是基于距离向量的路由协议
路由表中维护本网络到每一个目的网络的距离
距离如何定义：路由器和直接连接的网络距离为1（也可以定义为0，不影响）
因此，距离也叫做跳数，每经过一个网络，跳数+1
该协议人为：好的协议就是路径短
路径最多15，16不可达
因此RIP只适用于小网络
RIP对两个路由器之间，不能同时拥有多个路由
只能有一个，就是跳数最短，网络最少的一条
不管这一条速度快还是慢，我只管短还是长，不管速度

2、路由交换信息

本路由器需要和其他路由器交换信息建立路由表
那么：
和哪些路由器交换信息？所有的路由器吗？
仅和相邻路由器交换信息，不相邻不交换

交换什么信息？部分信息还是所有信息？
交换全部信息，即所有的路由表信息

什么时候交换信息？条件满足才交换还是隔一段时间就交换？
按固定的时间间隔交换信息，例如每隔30s

路由器刚开始工作的时候，路由表是空的
路由收敛：自治系统内所有节点得到正确的路由信息
路由表更新的原则是：找出每个目的网路的最短距离

3、距离向量算法

A的相邻路由器是B
从B->A发来的路由表信息有三个：
目的网络Net，距离d，下一跳

因为对A来说，到B的下一跳只能是B
所以，B发来的路由表的下一跳都是B
因此，对A来说，B发来的路由只有以下几种：

A原来没有
那就加上

A有，目的网络一样，查看下一跳
如果下一跳也是B，直接换掉（不管距离长短）
如果吓一跳不是B（也就是说有别的路径可以到达目的）
这个时候就看距离，那个距离短，用哪个

3分钟还没有收到相邻路由器信息
即A3分钟还没有收到B的路由信息，把到B的路由距离设置为16
标记不可到达

总结：
Net没有，加上去
Net一样，看下一跳：下一跳相同，直接更新；下一跳不一样，看谁短

4、坏消息传送慢问题

由于上述的更新策略，导致一下问题：
坏消息传的慢
什么意思？
举个例子，如图：

此时Net1故障，R1无法到达Net1，将到Net1距离改为16
30s后，将路由表发送给邻居R2
但是，还没到30s，R2就给R1发送自己的路由表信息了
此时，R2到达Net1的信息是：Net1 3 R2
该条信息到达R1后，一对比，Net1 16 直接
下一跳不相同，但是距离更短，更换
于是，R1到Net1的路由被换成：Net1 3 R2

到达30s后，R1再把Net1 4 R1发送给R2
一对比，R2为Net1 2 R1
下一跳一样，直接换

于是，二者不断更新循环
直到距离加到16才停止
此时，才知道Net1故障
即所谓坏消息慢

5、RIP报文格式

RIP报文用运输层用户数据报UDP的数据部分传送
格式如下：

RIP报文：首部 + 路由部分
路由部分：自治系统号ASN（可能收到本自治系统外的路由信息）
目的网络、下一跳路由器地址、距离

一个RIP报文最多带25个路由
超过必须用下一个报文来传送

综上所述，由于RIP所采取的路由更新策略
导致了其结构性上的缺点：
1、最大距离15（16不可达），只能用于小网络
2、更换信息，传送所有路由信息，开销大
3、坏消息传的慢，更新过程收敛时间长

因此，对于大网络来说，RIP路由策略不适合
于是，有了OSPF路由协议

三、内部网关协议OSPF

1、特点

1、向本自治系统所有路由器发送信息，洪泛法
路由器向所有接口发送信息
相邻路由器除收到接口，对其余所有接口发送信息
以此类推
最后，所有路由器收到该信息副本

2、发送信息为：所有相邻路由器链路状态
什么是链路状态？
该路由器和哪些路由器相邻
该链路代价（费用、距离、时延、宽带等）

3、每隔一段时间 / 链路状态发生变化：则洪泛

由上述三点特征，使得：
所有路由器拥有全网（本自治系统内）的拓扑结构图
也就是建立了一个链路状态数据库
该数据库记录：全网有多少路由器、相邻情况、代价情况等
于是，每一个路由器就可以根据这些数据，使用Dijkstra最短路径算法计算自己的路由表

（OSPF链路状态数据库更新快，因此更新过程收敛快）

2、其他特点

1、OSPF允许管理员给每条路指定代价
2、到同一个网络，有多条路代价相同，可以对通信进行均衡平摊
3、路由器交换分组具有鉴别能力，坏的路由器不发
4、支持变长网络地址划分，支持误分类网络编制CIDR
5、网络链路经常变化，因此让链路状态带序号，更新一次，序号+1
于是序号越大，状态越新

3、自治系统区域划分

为了让OSPF应用于更大的网络
OSPF将一个自治系统网路划分为更小的区域
每个区域用32位标识区域，用点分十进制记录
每个区域路由器最好不超过200个

划分好以后：
1、洪泛只局限在一个区域内，以减少通信量
路由器只直到本区域内的网络拓扑

2、为区域间通信，对区域划分层次：
上层为主干区域，32位标识规定为0.0.0.0
在主干区域的路由器：叫做主干路由器

区域交界的路由器：叫做区域边界路由器
每个区域至少一个区域边界路由器，以维护其他区域通信

在自治系统边界之间的路由器：叫做自治系统边界路由器
负责和其他路由器通信

上述所做的区域划分和层次划分
目的只有一个：减少路由信息交互负担
以增强OSPF协议对更大网络的适应

4、OSPF的5中分组类型

1、问候分组
用于发现和维持邻居的可达性
说人话就是发个消息，看邻居家能不能去
规定每10s发送一次
如果40s没有收到某个邻居发来的问候分组，则认为邻居死了，设置为不可达
其余四个分组都是用于同步链路状态信息的

2、数据库描述分组
向邻居发送自己的所有链路状态数据

3、数据链路请求分组
请求邻居发送人家的某些链路状态

4、链路状态更新分组
对全网洪泛（本区域内）
（OSPF核心功能）

5、链路状态确认分组
对链路更新的确认
向发送链路状态更新分组的路由器发送确认分组
我收到邻居的链路状态分组，我得告诉人家，我确实收到了

5、OFPS数据报格式

OSPF分组作为IP数据报的数据部分
IP首部协议为89
OSPF分组很短

注意：
洪泛并非所有的路由器都洪泛发送本地链路状体信息
这代价很大
那么怎么做呢？
假设路由器A B相邻
A的数据库摘要和B的数据库摘要互相交换
于是：
A知道有些自己没有，但B有
同理，B也如此
于是，
A向B发送自己缺少的链路状态请求，这些我没有，但是B你有，你告诉我
B也向A发送自己缺少的链路状态请求，
经过多轮两两之间的交换
最后所有路由器都有了全部的信息

每隔一段时间，如30分钟，OSPF刷新一次链路状态数据库

四、学习本章需要具备能力

1、根据RIP路由策略得到路由表

2、认识RIP的特点

3、理解路由算法

4、RIP路由算法的优点和缺点，例如坏消息、收敛、不可达等