第9章路由协议概述

第9章路由协议概述要求：1掌握路由表建立和维护的两种方式：静态配置和动态交换路由信息；2掌握Internet的路由体系结构,特别是自治系统AS的概念和作用；3掌握两种路由更新算法:矢量距离算法和SPF算法。路由协议解决的问题：如何获得路由表？9.1引言H1H2R1R5R2R3R4路径：H1-R1-R2-R4-H2问题：（1）路由器的路由表如何获取？（2）为什么选择这条路径？（3）假设R2与R4的连接断掉，如何通知R1？（4）在Internet中，是否每个路由器都必须了解其它路由器的情况？9.2路由表的建立和维护两种方式：静态配置and动态路由交换1.静态配置：管理员手工配置和更新路由表优点：节省路由器的处理时间、存储空间以及网络带宽缺陷：对于链路故障及拓扑结构变化的响应速度慢H1H2R1R5R2R3R4适用环境：拓扑相对稳定，路由器个数较少2.动态路由信息交换：利用路由协议交换路由信息，并根据拓扑结构的变化动态更新路由表优点：自动适应链路故障及拓扑结构的变化缺陷：耗费路由器的处理时间、存储空间以及网络带宽适用环境：路由器较多的大规模网络H1H2R1R5R2R3R49.3选路涉及到的2个关键问题（1）路径存在性（2）路径最优性1.路径存在性路由表的两个普遍特点：（1）路由表中不包含到达所有目的地的路由（2）路由表中存在默认路由要求：（1）单个路由器为连接关系所做的贡献是局部的（2）所有路由器组成的系统是完备的问题：如何确保各个路由器维护信息的一致性？答案：不同路由器更新路由表的信息是一致的，使得它们对网络拓扑结构有着一致性的认识。2.路由度量问题：如何确定一条路径是最优的？解答：选择不同的度量指标（1）带宽（静态指标）（2）延迟（3）负载（4）可靠性（5）跳数（6）其它指标，比如代价理想情况：综合利用以上各指标缺陷：可能会造成路由震荡实现：简单的算法仅考虑一个要素，复杂的则综合考虑（如DUAL）最常用的：基于跳数9.4选路算法（1）非自适应（2）自适应1.非自适应算法（1）不考虑当前的拓扑结构和网络流量（2）设置中心路由器，由管理员预先为每个路由器设置路由表（3）拓扑发生变化时，由管理员操作中心路由器，更新路由表（4）适用于规模小，拓扑结构变化少的网络2.自适应算法（1）矢量-距离算法（2）链路状态算法（1）矢量距离路由算法(Bellman、Bellman-Ford和Ford-Fulkerson算法)思想：以跳数作为度量值，通过交换路由表，计算出所有已知的最短路由，更新路由表。表项格式：目的网络，距离（跳数hop），下一站跳数：从源站到目的站间所经过的路由器数目。步骤：①初始化:路由器启动时，对每个直接相连的网络生成一个表项，hop数都为0。②路由交换:路由器周期性向相邻路由器广播自己的整个路由表。(交换信息是V,D)③路由表更新:路由器每收到一个邻站的路由表，即更新自己的路由表。(假设K收到J的路由表)(1)K不知道目的站，则加入(2)有通过J的更短路，则替换(3)原下站为J的距离有变化，则修改例：目的站距离下一跳网络10直接网络20直接网络48路由器L网络175路由器M网络246路由器J网络302路由器Q网络422路由器J目的站距离网络12网络43网络176网络214网络245网络3010网络423目的站距离下一跳网络10直接网络20直接网络44J（替换）网络175路由器M网络246路由器J网络302路由器Q网络424J（修改）网络215J（增加）思想：通过交换链路状态，让AS中的每个路由器都有一张该AS的网络拓扑结构图。节点：路由器；边：网络。使用Dijkstra算法求最短路径，计算该路由器到其它目的站的最短路径，然后更新路由表。优点：①每个路由器使用相同的原始数据，具有良好的收敛性。②每个路由器的链路状态报文尺寸取决于只连链路的数量，具有较好的规模可扩展性（2）链路状态路由算法-最短路径优先SPF步骤：①链路状态检测：周期性发测试报文，检查直接相邻的路由器状态，并按“n中取k”原则进行状态检查。②路由信息广播：路由器周期性广播它的各个链路状态。所有参与SPF的路由器负责转发收到的链路状态。③路由表更新：收到链路状态的路由器更新自己的网络拓扑图，并用Dijkstra算法计算最短路径。9.5Internet路由体系的发展路由体系的内容：如何对Internet中的路由器进行划分、管理和控制，以便有效地交换路由信息路由体系的重要性：决定了互联网的运行效率Internet路由体系的发展：（1）最早的核心路由体系（2）随后的对等主干路由体系（3）当前的自治系统路由体系1.核心路由器与核心体系结构ARPANET主干网本地网络2R2本地网络nRnARPANET主干网本地网络2本地网络2本地网络m本地网络1R1核心路由器k1k2kn核心路由器G1G2Gk外围路由器2.选路模式核心网关:构成核心系统，集中管理,提供到所有目的地的路由。外围网关:为外出数据报提供默认路由,发往某核心网关;将核心网关传入的数据报投递到直连的物理网络。2.Internet的对等主干结构问题：①两主干间多重接入，造成选路困难。②具有非法目的地址的数据报形成选路回路契机：NSFNET的引入R2RnR1ARPANET主干网主机2主机1NSFNET主干网主机4主机3选路模式：①各主干网内部按核心结构方式进行选路②各核心网关拥有对另一部分的默认路由。核心C1核心C2核心C1内网点的非法目的分组x到核心C2的默认路由P1到核心C1的默认路由P2目前的Internet结构Internet主干网NAP1NAP2NAPnNSP1NSP2NSPNISP1ISP1ISP1………………核心层分布层接入层3.Internet中的自治系统结构AS(自治系统)：出于选路目的，处于一个管理机构控制之下的一组网络和路由器。如何限制选路信息的传播?参与交换路由信息的路由器群组规模不能太大。指导原则：（1）广域网范围≤12个路由器（2）若干局域网范围≤60个路由器。多主干下选路问题如何解决？说明:（1）AS自治的主要内容是选路自治,AS可自由地选择路由算法；（2）AS必须严格界定，并被赋予全局唯一的自治系统号(NIC分配)；（3）主干网络本身也构成一个AS(教育网AS4538)。主干网(AS)AS2R2ASnRnAS1R1AS1R1主干网(AS)ASn……Internet的路由管理模式:（1）AS内部：IGP，比如RIP、OSPF、IS-IS等；（2）AS之间：EGP，最常用的是BGP;（3）EGP通常是一种可达性协议。R1R2R3AS1AS2AS3IGP1IGP2IGP3EGP12EGP13EGP23