文档介绍：第六章 网络层
第五节 路由选择协议
一、路由选择协议的基本概念
路由选择算法（routing algorithm）与 路由选择协议（routing protocol）的概念不同；
路由选择算法的目标是产生一个路由表，为路由器转发期性地通知相邻路由器自己的（V,D）信息。
路由器刚启动时，只包含与该路由器直接相连的网络的路由，表中的距离均为0；
路由信息协议RIP
路由信息协议在向量-距离(V-D)路由选择算法的基础上，规定了路由信息交互格式、错误处理方式，设置了周期更新定时器、延迟定时器、超时定时器与清除定时器等。
RIP只适用于相对较小的自治系统，否则RIP信息交换量会过大，但由于其较简单，因此应用广泛。
三、最短路径优先协议OSPF
OSPF协议的主要特点：
使用链路状态协议 (link state protocol)；
要求每个路由器周期性发送链路状态信息（费用、距离、延时、带宽等），使每个路由器形成一个跟踪网络状态的链路状态数据库，包括路由器可用端口、已知可达路由和链路状态信息。
利用链路状态数据库，每个路由器以自己为“根”，建立一个最短路径优先树SPF，用于描述从该路由器出发到达每个目的网络所需的开销。
Flooding：洪泛法
要求路由器在链路状态发生变化时用洪泛法向所有路由器发送该信息。（RIP仅通报相邻）
洪泛法不要求维护网络的拓扑结构和相关的路由计算，仅要求接收到信息的节点以广播方式转发数据包。
OSPF协议执行过程
通过“问候分组”完成邻居发现
用“数据库描述分组”和相邻路由器交换本地数据库中已有的链路状态摘要信息，直至建立了全网同步的链路状态数据库。
网络运行过程中，只要一个路由器的链路状态发生变化，该路由器就使用“链路状态更新分组”，用洪泛法向全网更新链路状态。
自治系统的内部结构示意图
主干区域
区域
主干路由器
区域边界路由器
自治系统边界路由器
OSPF域最短路径选择过程
一个自治系统划分为多个区域的结构
计算最短路径的拓扑图：网络抽象成点
根据最小开销计算方法得出的最短路径。 Dijkstra提出的最短路径优先算法SPF。 Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。
Dijkstra算法流程：
s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]；
初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
循环n-1次：
1）在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
2）对于每个与u相邻的点v，执行Relax(u,v)，也就是说，如果dist[u]+w[u,v]<dist[v]，那么把dist[v]更新成更短的距离dist[u]+w[u,v]。此时到点v的最短路径上，前一个节点即为u。
结束。此时对于任意的u，dist[u]就是s到u的距离。
复杂度分析：
最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，时间复杂度显然为
以R8为根的最短路径树→R8的路由表
四、外部网关协议BGP
外部网关协议是不同自治系统的路由器之间交换路由信息的协议，BGP-4采用路由向量（path vector）路由协议；
在配置BGP时，需要选择至少一个BGP边界路由器作为该自治系统的“BGP发言人”；
BGP发言人之间交换路由信息时，需要先建立TCP连接；利用BGP会话交换路由信息，增加新的或撤销过时的路由，以及报告出差错情况。
BGP发言人与自治系统的关系
自治系统连接的树形结构
BGP路由选择协议的工作过程
开始运行时，与相邻边界路由器交换整个BGP路由表
只需发生变化时进行更新，不必周期性更新；
BGP路由选择协议的分组
打开(open)分组—用来与相邻的另一个BGP发言人建立关系；
更新(update)分组—用来发送某一路由的信息，以及列出要撤销的多条路由；
保活(keepalive)分组—用来确认打开报文，和周期性地证实相邻边界路由器的存在；
通知(notification)分组—用来发送检测到的差错。
路由选择协议的目标是实现路由表中路由信息的动态更新。
内部网关协议（IGP）：在一个自治系统内部使用的路由选择协议；路由信息协议（RIP）、开放最短路径优先（OSPF）协议 。
外部网关协议（EGP）：在连接不同自治系统之间的路由器之间使用，以交换路由信息。
边界网关协议（BGP）。
总结<br****题
使用 RIP 协议的自治系统中， 如果路由器 R1 收到邻居路由器 R2 发送到距离矢量中包含<net1,16>，那么可以得到的结论是___
A