1、2本章学习要求本章学习要求： IPIP分组的交付分组的交付 路由选择算法的分类路由选择算法的分类 路由表查询效率的提高方法路由表查询效率的提高方法 InternetInternet路由选择协议及其分类路由选择协议及其分类内部网关协议内部网关协议外部网关协议外部网关协议36.4 6.4 IPIP分组交付和路由选择分组交付和路由选择 6.4.1 6.4.1 IPIP分组交付分组交付 分组交付是指在互联网络中分组交付是指在互联网络中路由器转发路由器转发IPIP分组分组的物理传输过程与分组转发交付机制的物理传输过程与分组转发交付机制 ; ;分组交付包括分组交付包括: :直接交付和间接交付两类直接交付和
2、间接交付两类 直接交付直接交付: :不通过路由器的转发不通过路由器的转发, ,分组直接交付分组直接交付目的主机与源主机在同一个网络内目的主机与源主机在同一个网络内分组通过最后一个路由器到达目的主机分组通过最后一个路由器到达目的主机 间接交付：通过若干个路由器的转发间接交付：通过若干个路由器的转发目的主机与源主机在不同的网络内目的主机与源主机在不同的网络内4直接交付直接交付5间接交付间接交付66.4.2 6.4.2 路由选择的基本概念路由选择的基本概念 IPIP分组的间接交付，需要通过多个路由器分组的间接交付，需要通过多个路由器路由选择路由选择 路由器路由器通过查询路由表，决定转发分组的端口通过
3、查询路由表，决定转发分组的端口路由表记录：目的地址和端口号（下一个路由表记录：目的地址和端口号（下一个路由器）的对应关系路由器）的对应关系 路由表通常是根据路由表通常是根据路由选择算法建立路由选择算法建立的的7路由选择算法的路由选择算法的设计设计要求要求 稳定、正确和公平稳定、正确和公平可收敛的可收敛的可到达目的主机可到达目的主机对所有主机公平对所有主机公平 尽可能简单尽可能简单 算法速度快，路由器转发分组的延时小算法速度快，路由器转发分组的延时小 健壮的健壮的(Robust)(Robust)能够自动适应网络拓扑（如路由器故障）能够自动适应网络拓扑（如路由器故障）和通信量（如链路的负载）的变化
4、和通信量（如链路的负载）的变化 性能最佳性能最佳算法开销最小：链路长度、数据速率、链算法开销最小：链路长度、数据速率、链路容量、传输延时路容量、传输延时8路由选择算法涉及的主要参数路由选择算法涉及的主要参数 跳步数跳步数 分组从源结点到达目的结点经过的分组从源结点到达目的结点经过的路由器的个数。路由器的个数。 带宽带宽 链路的传输速率。链路的传输速率。 延时延时 分组从源结点到达目的结点花费的时分组从源结点到达目的结点花费的时间。间。 负载负载 通过路由器或线路的单位时间通信量。通过路由器或线路的单位时间通信量。 可靠性可靠性 传输过程中的误码率。传输过程中的误码率。 开销开销 传输过程中的耗
5、费（传输过程中的耗费（“费用费用” ），与），与所使用的链路带宽相关。所使用的链路带宽相关。92. 2. 路由选择算法的分类路由选择算法的分类 路由选择算法路由选择算法包括：包括：静态和动态静态和动态 静态路由选择算法静态路由选择算法: :非自适应路由选择算法非自适应路由选择算法采用人工方式采用人工方式建立：通过手工输入所有的目的地址的路径建立：通过手工输入所有的目的地址的路径更新：通过手工修改更新：通过手工修改特点特点简单，开销较小简单，开销较小但不能及时适应网络状态的变化但不能及时适应网络状态的变化适合小型、固定的局域网系统适合小型、固定的局域网系统10动态路由选择算法动态路由选择算法 动
6、态路由选择算法动态路由选择算法: :自适应路由选择算法自适应路由选择算法自动方式自动方式自动建立自动建立路由表路由表自动更新自动更新路由表路由表 特点特点能自动适应网络状态的变化能自动适应网络状态的变化算法实现复杂，开销较大。算法实现复杂，开销较大。 113.3.路由选择模块与路由表路由选择模块与路由表 路由选择是通过路由选择是通过路由选择模块和路由表路由选择模块和路由表实现的实现的 在每个路由器接收到一个在每个路由器接收到一个IPIP分组时，路由选择分组时，路由选择模块必须进行路由查询；模块必须进行路由查询； 为了提高效率，路由器查询采用层次策略：为了提高效率，路由器查询采用层次策略：判断该
7、判断该IPIP分组是不是直接交付分组是不是直接交付? ?判断是不是特定主机交付判断是不是特定主机交付? ?判断是不是特定网络交付判断是不是特定网络交付? ?判断是不是默认交付？判断是不是默认交付？12路由选择算法结构路由选择算法结构路由选择模块路由表IP处 理模 块分片模块IP分 组下一跳地址IP分 组接收IP分 组转发IP分 组136.6.4.3 4.3 提高路由表查询效率的基本方法提高路由表查询效率的基本方法 随着网络规模的急剧膨胀，路由表的记录数也随着网络规模的急剧膨胀，路由表的记录数也相应迅速扩大相应迅速扩大 路由表的查询效率提高方法路由表的查询效率提高方法下一跳路由选择下一跳路由选择
8、特定网络路由选择特定网络路由选择特定主机路由选择特定主机路由选择默认路由选择默认路由选择14 下一跳路由选择下一跳路由选择路由表中不记录分组路径的所有路由器的地路由表中不记录分组路径的所有路由器的地址址仅仅保留仅仅保留下一跳（下一个路由器）的地址下一跳（下一个路由器）的地址 特定网络路由选择特定网络路由选择路由表中的目的地址是：路由表中的目的地址是：目的主机的网络号目的主机的网络号一条路由记录可以表示一个网络的所有主机一条路由记录可以表示一个网络的所有主机的路由的路由 特定主机路由选择特定主机路由选择目的地址：目的主机的目的地址：目的主机的IPIP地址地址 默认路由选择默认路由选择目的地址：目
9、的地址：0.0.0.00.0.0.0151.1.下一跳路由选择下一跳路由选择162.2.特定网络路由选择特定网络路由选择173.3.特定特定主机路主机路由选择由选择 184.4.默认路由选择默认路由选择 196.6.5 Internet5 Internet的路由选择协议的路由选择协议 6.6.5.1 5.1 自治系统与路由选择协议自治系统与路由选择协议 根据路由选择协议，根据路由选择协议，InternetInternet可以分为可以分为2 2层层: :第一层：自治系统第一层：自治系统单位内部网，内网单位内部网，内网路由选择：域内路由选择路由选择：域内路由选择第二层：主干区域第二层：主干区域主干
10、网，外网主干网，外网域间路由选择域间路由选择 自治系统的内部路由器负责第一层区域内部的主自治系统的内部路由器负责第一层区域内部的主机之间的分组交换机之间的分组交换 主干路由器负责不同的第一层区域之间的分组交主干路由器负责不同的第一层区域之间的分组交换换20 自治系统的核心是自治系统的核心是路由寻址的路由寻址的“自治自治”，即，即有权有权自主决定在系统内采用路由选择协议的类型自主决定在系统内采用路由选择协议的类型 自治系统内部的路由器自治系统内部的路由器了解系统内部的全部网络的路由信息了解系统内部的全部网络的路由信息能够连接本自治系统的主干路由器，对外网能够连接本自治系统的主干路由器，对外网收发
11、收发IPIP分组；分组； 要向主干路由器报告内部路由信息。要向主干路由器报告内部路由信息。21InternetInternet路由选择协议的分类路由选择协议的分类 内部网关协议内部网关协议IGP(InteriorIGP(Interior Gateway Protocol) Gateway Protocol)一个自治系统内部使用一个自治系统内部使用的路由选择协议的路由选择协议实例：路由信息协议实例：路由信息协议(RIP)(RIP)、开放最短路径优、开放最短路径优先协议先协议(OSPF)(OSPF) 外部网关协议外部网关协议EGP(EnteriorEGP(Enterior Gateway Prot
12、ocol) Gateway Protocol)使用不同的使用不同的IGPIGP的两个自治系统的两个自治系统内主机之间的内主机之间的通信通信分组传送到自治系统的边界时分组传送到自治系统的边界时 此处网关和路由器等同此处网关和路由器等同22236.6.5.2 5.2 内部网关协议内部网关协议 1.1.路由信息协议的基本概念路由信息协议的基本概念 路由信息协议路由信息协议（RIP,RoutingRIP,Routing Information Information ProtocolProtocol）使用最广泛的内部网关协议使用最广泛的内部网关协议分布式、基于距离向量的路由选择协议；分布式、基于距离向
13、量的路由选择协议； RIPRIP的特点的特点协议简单协议简单适用于相对较小的自治系统，直径一般适用于相对较小的自治系统，直径一般小小于于1515跳步数跳步数。RIP演示演示25 RIPRIP的思想的思想路由器周期性地向外发送路由刷新报文；路由器周期性地向外发送路由刷新报文；路由刷新报文主要内容是由若干路由刷新报文主要内容是由若干（V V，D D）组成的表组成的表；矢量矢量V V标识该路由器可以到达的目的网络标识该路由器可以到达的目的网络或目的主机，或目的主机，D D表示该路由器到达目的网络或目的主机表示该路由器到达目的网络或目的主机的跳步数；的跳步数；其他路由器在接收到该路由器的（其他路由器在
14、接收到该路由器的（V V，D D）报文后，报文后，按照最短路径原则对各自的路由表按照最短路径原则对各自的路由表进行刷新进行刷新；262.2.RIPRIP的工作过程的工作过程 路由表的建立路由表的建立路由器启动时，对路由器启动时，对(V,D)(V,D)路由表进行初始化路由表进行初始化此时路由表只包含此时路由表只包含与该路由器直接相连的网络与该路由器直接相连的网络的路由的路由，即，即D=0D=0 路由表信息的更新路由表信息的更新各个路由器周期性地向相邻的路由器广播它的各个路由器周期性地向相邻的路由器广播它的路由表内容路由表内容该路由器根据其它路由器的路由表，进行更新该路由器根据其它路由器的路由表，
15、进行更新27更新实例更新实例 假设：假设：路由器路由器R1R1和和R2R2是一个自治系统内的是一个自治系统内的2 2个个相邻相邻路路由器由器R1R1接收到接收到R2R2的的(V,D)(V,D)报文报文 R1R1的路由表更新的路由表更新R1R1的路由表某项纪录中，路径距离过大，则根的路由表某项纪录中，路径距离过大，则根据据R2R2的路由表，修改该记录的路由表，修改该记录R1R1的路由表缺少一项记录，则根据的路由表缺少一项记录，则根据R2R2的路由表，的路由表，添加该记录添加该记录R1R1与与R2R2的跳步数为的跳步数为1 128R1R1的路由表的路由表29R2R2的路由表的路由表30R1R1更新后的路由表更新后的路由表31小结小结 IPIP分组交付的分类分组交付的分类直接交付直接交付间接交付间接交付 路由选择算法的设计要求及分类路由选择算法的设计要求及分类 路由查询的四种改进措施路由查询的四种改进措施 InternetInternet路由选择协议及其分类路由选择协议及其分类内部网关协议内部网关协议外部网关协议外部网关协议
