《Internet课程2IP路由》由会员分享，可在线阅读，更多相关《Internet课程2IP路由（24页珍藏版）》请在金锄头文库上搜索。
1、4.1.1 Internet路由体系结构路由体系结构 核心系统核心系统GG自治系统自治系统自治系统自治系统自治系统自治系统G核心网关核心网关局域网局域网局域网局域网GG局域网局域网局域网局域网GG局域网局域网G非核心网关非核心网关信任信任GGPEGPIGP第第四四章章 I IP P路路由由4.1 IP IP路由概述路由概述4.1.3 路由选择策略路由选择策略/ /转发模式转发模式静态选择策略：静态选择策略：静态选择策略：静态选择策略：泛洪法；泛洪法；选择泛洪法；选择泛洪法；固定路由表法；固定路由表法；随机法；随机法；分散通信量法。分散通信量法。4.1.2 路由器功能部件路由器功能部件 选路与转
2、发选路与转发（路由策略）（路由策略）转发表更新转发表更新（路由协议）（路由协议）分分组组分分组组动态选择策略：动态选择策略：动态选择策略：动态选择策略：孤立路由法；孤立路由法；集中式路由算法；集中式路由算法；分布式路由算法；分布式路由算法；分层式路由算法；分层式路由算法；混合式路由算法。混合式路由算法。第第四四章章 I IP P路路由由4.1.4 最短路径搜索算法最短路径搜索算法1、距离向量算法、距离向量算法(Bellmen-Ford) 寻找由指定节点到目的节点的最短通路。需要周寻找由指定节点到目的节点的最短通路。需要周期性地与相邻节点（路由器）交换路由状态信息，路期性地与相邻节点（路由器）交
3、换路由状态信息，路由状态信息由由状态信息由(V,D)序偶对组成表，序偶对组成表，V代表可到达的目代表可到达的目的，的，D代表到达代表到达V的距离。的距离。数学描述：数学描述：V(n,D(m), D(m)为为m经过经过n到达到达v的距离；的距离； 设设k为为m的邻居，的邻居， D(m)=minD(k)+l(k,m), n=k。2、链路状态、链路状态/最短路径算法最短路径算法(Dijkstra) 寻找由源节点到所有节点的最短通路。需要一张寻找由源节点到所有节点的最短通路。需要一张整个网络拓扑结构的无向图，该图可称为整个网络拓扑结构的无向图，该图可称为LinkState图。图。LS图全局一致，节点需
4、要向所有其他节点广播图全局一致，节点需要向所有其他节点广播LS信息。信息。数学描述：数学描述：Ns； 对对v, D(v)=l(s,v) ，s直接连接直接连接v或无穷大或无穷大 ； 选择选择D(w)最小的最小的w, 对其他的对其他的v， D(v)=minD(v),D(w)+l(w,v)； N=s,w; 直至直至N包括所有节点。包括所有节点。第第四四章章 I IP P路路由由4.2.1 RIP特点：特点：采用采用Bellmen算法，简单、运行开销小，适用算法，简单、运行开销小，适用于小型网络。于小型网络。RIP使用使用UDP的的520端口传递路由信息；端口传递路由信息；交互的报文：请求报文和响应报
5、文；最大距离为交互的报文：请求报文和响应报文；最大距离为16跳，跳，否则，为不可达。否则，为不可达。升级：升级：1988年年RIPv1；RIPv2增加了认证、路由标签、增加了认证、路由标签、子网掩码、下一跳、组播、请求与响应等；子网掩码、下一跳、组播、请求与响应等；RIPng针针对对IPv6。运行过程：运行过程：启动时，启动时，RIP处理模块发出请求报文，然后处理模块发出请求报文，然后进入等待；接收到请求报文的路由器发送自己路由信进入等待；接收到请求报文的路由器发送自己路由信息的响应报文；接收到响应的路由器判断是否更新路息的响应报文；接收到响应的路由器判断是否更新路由表。由表。定时器：定时器：
6、启动后，路由器以启动后，路由器以30秒（可调）间隔周期发秒（可调）间隔周期发送响应报文；每条路由信息项的无效定时为送响应报文；每条路由信息项的无效定时为180秒（默秒（默认），超时没有收到对应邻居（下一跳）的响应报文认），超时没有收到对应邻居（下一跳）的响应报文则将该距离值设为无穷大（则将该距离值设为无穷大（16）；该路由项继续保留）；该路由项继续保留120秒，以便可达邻居受到更新信息。秒，以便可达邻居受到更新信息。计数无穷大计数无穷大/收敛慢问题：收敛慢问题：由于邻居传递信息时差，存由于邻居传递信息时差，存在路由环路问题，会导致距离计算到无穷大，造成一在路由环路问题，会导致距离计算到无穷大，
7、造成一段时间的无序状态。解决办法段时间的无序状态。解决办法：简单水平分裂：不向简单水平分裂：不向邻居发送从该邻居获取的路由信息；毒性逆转水平分邻居发送从该邻居获取的路由信息；毒性逆转水平分裂：将从邻居获得的路由信息回送时距离设为无穷大；裂：将从邻居获得的路由信息回送时距离设为无穷大；触发更新：一旦发现路由信息变化，立即广播更新报触发更新：一旦发现路由信息变化，立即广播更新报文，不必等待文，不必等待30秒的周期。秒的周期。验证：身份认证；验证：身份认证；路由标签：传递路由标签：传递AS的标号给外部网关路由协议；的标号给外部网关路由协议；子网掩码：支持特定的子网路由和超网路由；子网掩码：支持特定的
8、子网路由和超网路由；下一跳：避免分组在传送过程增加不必要的跳数，下一跳：避免分组在传送过程增加不必要的跳数， 可直接抵达；可直接抵达；组播：增加了使用组播方式传递路由信息，降低组播：增加了使用组播方式传递路由信息，降低 通信量；通信量；请求与响应：请求与响应：RIPv2可以不对可以不对RIPv1的请求作出的请求作出 响应。响应。第第四四章章 I IP P路路由由4.2 单播路由单播路由4.2.2 OSPF特点：特点：采用采用Dijkstra算法，协议复杂，适用于大型网络。算法，协议复杂，适用于大型网络。OSPF直接基于直接基于IP设计，路由器维持一个统一的链路状设计，路由器维持一个统一的链路状
9、态数据库，构造自己为根的最短路径树，算法收敛时间态数据库，构造自己为根的最短路径树，算法收敛时间短。短。OSPFv3支持支持IPv6，引入区域概念来隐藏区域内部拓扑引入区域概念来隐藏区域内部拓扑结构，减少路由流量，采用分层路由管理机制结构，减少路由流量，采用分层路由管理机制。数据库同步：数据库同步：初始数据库同步通过数据库交换过程完成；初始数据库同步通过数据库交换过程完成；其后，数据库同步（链路状态变化的同步）通过泛洪过其后，数据库同步（链路状态变化的同步）通过泛洪过程维护。程维护。类型类型OSPF PDU名称名称功能功能1Hello发现发现/维护邻居维护邻居关系关系2数据库描述（数据库描述（
10、Database Description）数据项变更情数据项变更情况描述况描述3链路状态请求（链路状态请求（Link State Request)请求所需要的请求所需要的记录项记录项4链路状态更新（链路状态更新（Link State Update）发送指定的记发送指定的记录项录项5链路状态确认（链路状态确认（Link State Ack）对对泛洪消息进泛洪消息进行确认行确认第第四四章章 I IP P路路由由Connect with other AS主干：主干路主干：主干路由器由器R2R6。区域：域内路区域：域内路由器由器R1、R4、R7。域间路由器域间路由器R2、R3、R5、R6。AS边界路由
11、器边界路由器R2。Area1Area2Area3BackboneHello：1）发现邻居路由器；发现邻居路由器； 2）选举链路代表路由器和备份路由器。）选举链路代表路由器和备份路由器。 路由器周期发送路由器周期发送Hello报文，邻居间必须建立双向报文，邻居间必须建立双向连接；若超时无连接；若超时无Hello消息则认为邻居死亡。消息则认为邻居死亡。 一条链路涉及的多个路由器中需选举出一个（优先一条链路涉及的多个路由器中需选举出一个（优先级最高的）路由器作为代表，另选定一个备份代表，故级最高的）路由器作为代表，另选定一个备份代表，故障时备份代表自动接管工作。障时备份代表自动接管工作。4.2.2.
12、1 建立邻居关系建立邻居关系邻居数据库同步：邻居数据库同步：1）状态比较，）状态比较，邻居路由器通过可靠邻居路由器通过可靠地交换数据库描述分组来判断是否更新数据库记录，通地交换数据库描述分组来判断是否更新数据库记录，通过比较过比较“链路状态序号链路状态序号” 判断判断；2）请求更新，）请求更新，对变化对变化的链路，路由器请求最新序号的记录，发送链路状态请的链路，路由器请求最新序号的记录，发送链路状态请求分组求分组；3）修改记录，）修改记录，收到请求的路由器发送被请求收到请求的路由器发送被请求记录的链路状态更新分组。记录的链路状态更新分组。4.2.2.2 泛洪泛洪广播链路状态通告广播链路状态通告
13、：一旦链路的状态发生变化，代表该一旦链路的状态发生变化，代表该链路的路由器通过泛洪的方法向全网广播发生变化的链链路的路由器通过泛洪的方法向全网广播发生变化的链路状态更新通告；为保证可靠性，路由器周期性广播通路状态更新通告；为保证可靠性，路由器周期性广播通告，直到收到所有（邻居）的确认消息。告，直到收到所有（邻居）的确认消息。第第四四章章 I IP P路路由由生存时间：该生存时间：该LSA的生成至今的时间。的生成至今的时间。LS类型：表示类型：表示LSA执行的功能及泛洪的范围，有些执行的功能及泛洪的范围，有些LSA信息需要在信息需要在 整个整个AS内泛洪，有些只在区域内泛洪。不同的类型内泛洪，有
14、些只在区域内泛洪。不同的类型LSA共共 同构成同构成OSPF的链路状态数据库，就像数据库系统中不同的链路状态数据库，就像数据库系统中不同 的表共同构成一个应用数据库。的表共同构成一个应用数据库。链路状态链路状态ID：该字段与类型、通告路由器一起唯一标识数据库中的一该字段与类型、通告路由器一起唯一标识数据库中的一 个个LSA记录。记录。通告路由器：生成该通告路由器：生成该LSA的路由器的路由器ID。链路状态序号：链路状态序号：N231，计数从计数从N1（0x80000001)开始至开始至N1 （0x7FFFFFFF）。）。当计数到当计数到N1，须将，须将对应的对应的LSA老化，老化， 重新泛洪，
15、得到确认（计数同步）后从重新泛洪，得到确认（计数同步）后从N1开始。开始。4.2.2.3 链路状态数据库链路状态数据库 链路状态通告链路状态通告LSA是是OSPF同步数据库信息记录的同步数据库信息记录的存在形式，有多种存在形式，有多种LSA类型，其泛洪的范围不同，但都类型，其泛洪的范围不同，但都有标准的有标准的20字节字节LSA报头：报头：生存时间生存时间 类型类型 链路状态链路状态ID 通告路由器通告路由器 链路状态序号链路状态序号 校验和校验和 长度长度 第第四四章章 I IP P路路由由路由器路由器LSA：域内泛洪，描述路由器连接到某区域的所域内泛洪，描述路由器连接到某区域的所有接口的状
16、态。有接口的状态。网络网络LSA：域内泛洪，描述多个附接路由器网络构成的域内泛洪，描述多个附接路由器网络构成的链路的状态。链路的状态。域间前缀域间前缀LSA：由区域边界路由器生成，域内泛洪，描由区域边界路由器生成，域内泛洪，描述可达的区域外、述可达的区域外、AS内的子网集合及状态。内的子网集合及状态。域间路由器域间路由器LSA：域内泛洪，描述到达区域外、域内泛洪，描述到达区域外、AS内内目标路由器（边界路由器）的路径的状态。目标路由器（边界路由器）的路径的状态。AS外部外部LSA：由边界路由器产生，由边界路由器产生，AS内泛洪，描述可内泛洪，描述可到达的本到达的本AS外部目的网络或路由器的路径
17、状态。外部目的网络或路由器的路径状态。链路链路LSA：链路本地泛洪，描述多个附接路由器链路的链路本地泛洪，描述多个附接路由器链路的非代表链路。非代表链路。域内前缀域内前缀LSA：域内泛洪，描述域内的相关子网集合。域内泛洪，描述域内的相关子网集合。汇总汇总LSA：某个区域的域间前缀某个区域的域间前缀LAS和域间路由器和域间路由器LSA统称为汇总统称为汇总LSA。4.2.2.4 路由表计算路由表计算 OSPF路由计算过程较为复杂，路由器在每一步计路由计算过程较为复杂，路由器在每一步计算中须访问链路状态数据库的不同部分，主要由查找函算中须访问链路状态数据库的不同部分，主要由查找函数完成。数完成。计算
18、域内路由：计算域内路由：通过对所接入的区域利用通过对所接入的区域利用Dijkstra算法算法建立最短路径树生成域内路由表，计算所用图的建立最短路径树生成域内路由表，计算所用图的来源于路由器来源于路由器LSA和网络和网络LSA中的路由器和链路。中的路由器和链路。计算域间路由：计算域间路由：通过搜索汇总通过搜索汇总LSA计算域间路由表。对计算域间路由表。对区域边界路由器使用主干汇总区域边界路由器使用主干汇总LSA确定区域到区域的路确定区域到区域的路径；对区域内路由器使用区域汇总径；对区域内路由器使用区域汇总LSA确定多个区域边确定多个区域边界中的合适路径。采用距离矢量算法选择路径。界中的合适路径。
19、采用距离矢量算法选择路径。检查传输区域的汇总检查传输区域的汇总LSA：对连接非主干区域的区域边对连接非主干区域的区域边界路由器进行传输区域的汇总界路由器进行传输区域的汇总LSA检查，以便发现是否检查，以便发现是否有比最短路径树计算和域间路由计算所得结果更好的路有比最短路径树计算和域间路由计算所得结果更好的路径。径。计算计算AS外部路由：外部路由：通过查看通过查看AS外部外部LSA，可以计算到可以计算到达达AS外部目的的路径，每个外部目的的路径，每个AS外部外部LSA被依次考虑。被依次考虑。当可以通过多个区域到达同一个当可以通过多个区域到达同一个AS边界路由器，或有边界路由器，或有多个多个AS边
20、界路由器可达同一个外部目的时，非主干网边界路由器可达同一个外部目的时，非主干网的区域路径始终是最高优先级。的区域路径始终是最高优先级。第第四四章章 I IP P路路由由4.2.3 IS-IS IS-IS(Intermediate System to Intermediate System)是是OSI的无连接网络路由协议。的无连接网络路由协议。ISO规定，一规定，一个路由器就是一个个路由器就是一个IS，一个主机就是一个一个主机就是一个ES。处理过程：处理过程：IS-IS与与OSPF很相似，利用链路状态协议数很相似，利用链路状态协议数据单元据单元LSP来同步区域内路由器的链路状态数据库；用来同步区
21、域内路由器的链路状态数据库；用Hello报文建立和维护邻居关系；通过交换报文建立和维护邻居关系；通过交换LSP摘要判摘要判断断LSP的新旧，并发出更新请求和响应；的新旧，并发出更新请求和响应；IS在事件触发在事件触发下生成新的下生成新的LSP并向所有邻居扩散，接收到更新并向所有邻居扩散，接收到更新LSP的的路由器对其进行标记（以便确认），然后继续扩散。路由器对其进行标记（以便确认），然后继续扩散。分级路由体系：分级路由体系：IS-IS路由域中，大的路由域被分为若路由域中，大的路由域被分为若干区域，区域内的路由为一级路由，区域间的路由为二干区域，区域内的路由为一级路由，区域间的路由为二级路由。与
22、之相应，级路由。与之相应，IS分为分为L1和和L2。L1仅了解本区域仅了解本区域的拓扑结构，不识别区域外的目标地址，将其转发给区的拓扑结构，不识别区域外的目标地址，将其转发给区域内的域内的L2处理。处理。L2了解区域间的拓扑结构。了解区域间的拓扑结构。OSPF中的中的区域边界路由器在区域边界路由器在IS-IS中成为中成为L1/L2，L1/L2维护两个维护两个路由级别链路状态数据库，分别计算路由级别链路状态数据库，分别计算L1和和L2拓扑的最拓扑的最短路径树，但是短路径树，但是L1/L2不通告不通告L2的路由信息给的路由信息给L1，故，故L1不知道区域外的路由信息。不知道区域外的路由信息。支持：
23、支持：IS-IS对对IP路由提供支持，既支持路由提供支持，既支持IPv4，也支持也支持IPv6；IETF在在RFC3784IS-IS流量工程扩展流量工程扩展和和 IS-IS支持无特征多协议标签交换扩展支持无特征多协议标签交换扩展中定义了许多中定义了许多用于用于IS-IS发布流量工程用的新的数据结构。发布流量工程用的新的数据结构。第第四四章章 I IP P路路由由BGP4消息：消息：设置了设置了4种消息进行信息交换，以及维护种消息进行信息交换，以及维护路由信息状态；利用路由信息状态；利用TCP实现消息的可靠传递。实现消息的可靠传递。4.2.4 BGP 当前当前Internet核心路由协议是边界网
24、关路由协议核心路由协议是边界网关路由协议BGP4，扩展后的扩展后的BGP4为为BGP4，其支持其支持IPv6、IPX等网络层协议。等网络层协议。对等体：对等体：两个相互间构成两个相互间构成BGP4路由协议连接的一对路由协议连接的一对或多对路由器。或多对路由器。BGP4又分为外部又分为外部EBGP4和内部和内部IBGP4（同一同一AS内）。内）。4.2.4.1 基本概念基本概念BGP4选路原理：选路原理：采用距离矢量协议，每个节点根据采用距离矢量协议，每个节点根据下游节点传送的路由信息进行路由计算，并将结果继续下游节点传送的路由信息进行路由计算，并将结果继续传递给上游节点，利用传递给上游节点，利
25、用AS号列表（路径向量）作为距离号列表（路径向量）作为距离选择最佳路由，同时，也可以避免路由环路。选择最佳路由，同时，也可以避免路由环路。名名 称称功功 能能OPEN建立邻接关系，如果对方同意则用建立邻接关系，如果对方同意则用KEEPALIVE确认。确认。UPDATE发送路由更新消息，通告对等体对端发送路由更新消息，通告对等体对端一条可用的路由或者撤销不可用路由。一条可用的路由或者撤销不可用路由。根据根据UPDATE消息可构造出消息可构造出AS间的间的拓扑关系，进而得到拓扑关系，进而得到AS路径向量，选路径向量，选定合适的路由。定合适的路由。KEEPALIVE保持对等体对端可达的心跳机制。保持
26、对等体对端可达的心跳机制。NOTIFICATION通告出错信息（消息头错误、通告出错信息（消息头错误、OPEN错误、错误、UPDATE错误）。错误）。第第四四章章 I IP P路路由由4.2.4.2 BGP4有限状态机有限状态机事件事件1,71,7事件事件1,51,5空闲空闲连接连接活动活动OPEN发送发送建立建立OPEN确认确认事件事件1 1事件事件2,4,6,2,4,6,813事件事件1010事件事件7 7事件事件5 5事件事件1111事件事件2,3,52,3,513事件事件2,4,6,2,4,6,813事件事件3 3事件事件4 4事件事件3 3事件事件2 28,10,12,13,10,1
27、2,13事件事件2 28,10,12,13,10,12,13事件事件2 213事件事件1 1事件事件1,9,11,121,9,11,12事件事件1,91,9事件事件1 1 BGP4BGP4开始开始事件事件8 8保持计时器溢出保持计时器溢出事件事件2 2 BGP4BGP4停止停止事件事件9 9KEEPALIVEKEEPALIVE计时器溢计时器溢出出事件事件3 3BGP4BGP4请求传输请求传输连接连接事件事件1010 接收接收OPENOPEN消息消息事件事件4 4BGP4BGP4关闭传输关闭传输连接连接事件事件1111 接收接收KEEPALIVEKEEPALIVE消息消息事件事件5 5BGP4B
28、GP4请求传输请求传输连接失败连接失败事件事件1212 接收接收UPDATEUPDATE消息消息事件事件6 6 BGP4BGP4传输异常传输异常事件事件1313接收接收NOTIFICATIONNOTIFICATION消息消息事件事件7 7 重传重传计时器溢出计时器溢出第第四四章章 I IP P路路由由4.2.4.3 路径属性路径属性 路径属性是路径属性是BGP的重要组成部分，的重要组成部分，BGP路由器将自路由器将自己所处己所处AS内的子网、链路状态等参数信息写入内的子网、链路状态等参数信息写入UPDATE的路径属性部分，传递给对等体。的路径属性部分，传递给对等体。分分类类公认必遵类，公认必遵
29、类，所有所有BGP路由器支持、不可缺少路由器支持、不可缺少的属性。的属性。公认自决类，公认自决类，所有所有BGP路由器支持、可缺少路由器支持、可缺少（空缺）的属性。（空缺）的属性。可选过渡类，可选过渡类，其他路由器可以不识别、不支持，其他路由器可以不识别、不支持，但必须传递的属性。但必须传递的属性。可选非过渡类，可选非过渡类，其他路由器可以不识别、不支其他路由器可以不识别、不支持，不再传递的属性。持，不再传递的属性。起点属性起点属性公认必遵型，指明路由更新的起点公认必遵型，指明路由更新的起点AS。AS路径属性路径属性公认必遵型，公认必遵型， UPDATE消息经过的消息经过的AS列表向量。列表向
30、量。下一中继属性下一中继属性公认必遵型，公认必遵型， UPDATE列出的目的地址的下一跳列出的目的地址的下一跳BGP路由器。路由器。多出多出/入口属性入口属性可选非过渡型，指明同一个可选非过渡型，指明同一个AS的多个出口或者多的多个出口或者多个入口。个入口。本地优先属性本地优先属性公认自决型，从公认自决型，从AS外部学习到路由的优先程度并外部学习到路由的优先程度并通知对等的通知对等的IBGP4。自动聚合属性自动聚合属性公认自决型，接收的重叠路由中聚合性最好（前公认自决型，接收的重叠路由中聚合性最好（前缀最短）的路由。缀最短）的路由。聚合者属性聚合者属性可选过渡型，指明产生聚合的可选过渡型，指明
31、产生聚合的AS和路由器。和路由器。团体属性团体属性可选过渡型，具有共同目的地址的集合。可选过渡型，具有共同目的地址的集合。多协议可达多协议可达NLRI可选非过渡型，可用路由；网络层地址；本系统可选非过渡型，可用路由；网络层地址；本系统子网接入点。子网接入点。多协议不可达多协议不可达NLRI可选非过渡型，撤销多个不可用路由。可选非过渡型，撤销多个不可用路由。第第四四章章 I IP P路路由由4.2.4.4 路由更新路由更新BGP4路由信息库包含路由信息库包含3个部分，其转换过程如下：个部分，其转换过程如下：BGP4路由器路由器Adj-RIB-in接收的路由信息Loc-RIB路由决策选择的路由Ad
32、j-RIB-out需通告的路由信息UPDATEUPDATE本本地地 决决策策准准备备 通通告告计算优先级：计算优先级：对本地新的路由和邻居传来的路由计算优对本地新的路由和邻居传来的路由计算优先级，并且存入先级，并且存入Adj-RIB-in。策略信息的确切特性和相策略信息的确切特性和相关计算是本地问题。关计算是本地问题。路由选择：路由选择：对当前对当前Adj-RIB-in中的所有路由判断、选择，中的所有路由判断、选择，并且将选定的路由存入并且将选定的路由存入Loc-RIB，而不用的路由从而不用的路由从Loc-RIB删除。这需用到路径属性中的多项参数，同时遵循删除。这需用到路径属性中的多项参数，同
33、时遵循一定的原则（多条相同优先级路径只选其一）。一定的原则（多条相同优先级路径只选其一）。路由分发：路由分发：负责发布负责发布Loc-RIB中的路由信息到所有的对中的路由信息到所有的对等体。涉及内容：内部更新（发布信息到对等等体。涉及内容：内部更新（发布信息到对等IBGP4）；外部更新（发布信息到对等外部更新（发布信息到对等EBGP4+）；）；控制路由流控制路由流量开销（减少量开销（减少UPDATE占用的带宽及决策占用的占用的带宽及决策占用的CUP能力）；路由信息有效组织（路由信息简化、聚合路由能力）；路由信息有效组织（路由信息简化、聚合路由信息）。信息）。路由选择标准：路由选择标准：不产生路
34、由环路和稳定可行的路由（有不产生路由环路和稳定可行的路由（有以源为根的树）。以源为根的树）。 简单路径向量协议（简单路径向量协议（SPVP）用分布式的用分布式的Bellmen-Ford算法解决路径稳定问题。算法解决路径稳定问题。 对路由器对路由器u(非源节点）执行非源节点）执行spvp(u)，即从即从Adj-RIB-in中用中用spvp算法找出一条最佳的路径，存入算法找出一条最佳的路径，存入Loc-RIB。计算中，如果计算中，如果Adj-RIB-in最终为空，则选择的路径是稳最终为空，则选择的路径是稳定的；否则，是不稳定的。定的；否则，是不稳定的。120341,01,3,02,02,1,03,
35、04,3,04,2,012034路径路径(1,0)、(2,0)、(4,3,0)120341,3,01,03,4,2,03,04,2,04,3,02,1,02,0第第四四章章 I IP P路路由由4.2.4.5 出错处理出错处理 BGP4路由检测到错误立即发送路由检测到错误立即发送NOTIFICATION，并关闭并关闭BGP连接。连接。保持计数器错误保持计数器错误有限状态机错误有限状态机错误终止终止消息头错误消息头错误连接未同步连接未同步错误的消息长度错误的消息长度错误的消息类型错误的消息类型OPEN消息错误消息错误不支持的版本号不支持的版本号错误的对端错误的对端AS坏的坏的BGP4标识符标识符
36、不支持的选项参数不支持的选项参数认证失败认证失败不支持的保持时间不支持的保持时间UPDATE消息错误消息错误畸形属性列表畸形属性列表不认识的公认属性不认识的公认属性缺少公认属性缺少公认属性属性标志错误属性标志错误属性长度错误属性长度错误无效起点属性无效起点属性AS路由环路路由环路无效的下一中继属性无效的下一中继属性可选属性参数错误可选属性参数错误无效网络域无效网络域畸形畸形AS路径路径4.2.4.6 IBGP4与与IGP同步同步BGP4必须在必须在IGP建立了内部路由后，才能向外部通建立了内部路由后，才能向外部通告穿越路径。告穿越路径。第第四四章章 I IP P路路由由解决方案：解决方案：在在
37、AS内部建立内部建立IBGP4的全连接，或者向的全连接，或者向AS内部内部IGP注入注入BGP4路由。由于路由。由于BGP4路由数量路由数量巨大，注入方式会造成内部路由器巨大开销，可有选巨大，注入方式会造成内部路由器巨大开销，可有选择地注入。择地注入。4.2.4.7 路由反射器路由反射器问题：问题：一个一个N个个IBGP4网络中，需要网络中，需要N*(N-1)/2个连接个连接来建立全连接。来建立全连接。解决方法：解决方法：在一个在一个AS内指定一个路由器作为内指定一个路由器作为IBGP会话会话中心（路由反射器），其他中心（路由反射器），其他IBGP路由器只与路由反射路由器只与路由反射器进行对等
38、化，只需器进行对等化，只需(N-1)个连接。个连接。RRRRRR4.2.4.8 联盟联盟 其作用与路由反射器一样。将一个大的其作用与路由反射器一样。将一个大的AS划分为划分为若干若干Sub-AS， 各个各个Sub-AS之间运行之间运行EBGP4， Sub-AS内部运行内部运行IBGP4。拥有划分了拥有划分了Sub-AS的源的源AS则成为联盟。则成为联盟。AS100IBGP4+EBGP4+EBGP4+不参加不参加AS外部路由外部路由4.2.4.9 路由衰减路由衰减 只选择性能好的路由对外通告，抑止大量路由信息只选择性能好的路由对外通告，抑止大量路由信息进入网络占用资源。进入网络占用资源。第第四四
39、章章 I IP P路路由由4.3.1 概述概述特性：特性：实现一对多的传输（非广播）实现一对多的传输（非广播）；使网络负载减少使网络负载减少到最小（小于多次单点传输或泛洪）；允许资源发现到最小（小于多次单点传输或泛洪）；允许资源发现（组成员自动加入和撤出）。（组成员自动加入和撤出）。4.3.1.1 编址编址1 1 1 0IP D类地址类地址IP到到MAC映射映射 9bits 23bits 01 00 5E 0 23bits4.3.1.2 动态登记动态登记IGMPv1：加入（主机可主动申请）；维护（路由器定加入（主机可主动申请）；维护（路由器定期查询）；脱离（路由器一定时间无回应接收，则删除期查
40、询）；脱离（路由器一定时间无回应接收，则删除端口）。端口）。IGMPv2：增加了主机主动脱离报文。增加了主机主动脱离报文。IGMP侦听：侦听：交换机检查含有交换机检查含有IGMP帧的端口，然后，在帧的端口，然后，在过滤表中创建添加记录项。交换机过滤表中创建添加记录项。交换机CPU负荷大。负荷大。GMRP：在网卡驱动中实现，主动向邻居交换机发出在网卡驱动中实现，主动向邻居交换机发出GMRP登记消息，告知登记消息，告知“发往发往M组的帧给我组的帧给我”；撤销过；撤销过程类似。程类似。第第四四章章 I IP P路路由由4.3 组播路由组播路由4.3.2 组播路由算法组播路由算法问题描述：问题描述：根
41、据网络拓扑结构和当前网络状态，构造根据网络拓扑结构和当前网络状态，构造一棵包含组成员节点的、满足约束条件（时延、带宽、一棵包含组成员节点的、满足约束条件（时延、带宽、丢失率等）的最优组播树。丢失率等）的最优组播树。最短路径树：最短路径树：从源到每个接收节点的路径都是两者之从源到每个接收节点的路径都是两者之间的最短路径的树，可以解决树约束问题，如间的最短路径的树，可以解决树约束问题，如Dijkstra、Bellman-Ford。最小生成树：最小生成树：连接图中的所有节点，并且树枝的全部连接图中的所有节点，并且树枝的全部权值之和最小的树，可以解决树的优化问题，如权值之和最小的树，可以解决树的优化问
42、题，如Prim、Kruskal。Prim算法的执行非常类似于寻找图的最短通路的算法的执行非常类似于寻找图的最短通路的Dijkstra算法。在算法的每一步，树中的结点确定了算法。在算法的每一步，树中的结点确定了图的一个割集，并且通过该割集的轻边（权值最图的一个割集，并且通过该割集的轻边（权值最小的小的边）被加进树中。边）被加进树中。abcdehgfi48811276174214910第第四四章章 I IP P路路由由KMB算法是一种基于最小生成树的启发式算法：算法是一种基于最小生成树的启发式算法：1）从网络的拓扑图）从网络的拓扑图G中构造组成员节点的完全中构造组成员节点的完全 距离图距离图H；2
43、）计算图计算图H的最小生成树的最小生成树U；3）把）把U中的边替换成中的边替换成G中的最短路径，得到一个中的最短路径，得到一个 连接子图连接子图V；4）对）对V求最小生成树求最小生成树T；5）删除删除T中不包含组成员的叶节点。中不包含组成员的叶节点。Steiner树：树：只需求出连接网络中部分节点（组成员）只需求出连接网络中部分节点（组成员）的代价最小的组播树。通常的代价最小的组播树。通常Steiner树问题是树问题是NP难度问难度问题，只能求得近似解。题，只能求得近似解。abcdefhgikjlbfjg222223abcdefhgikjl约束约束Steiner树：树：Steiner树问题可以
44、被扩展包括其他约树问题可以被扩展包括其他约束条件，如时延、时延抖动等，但仍然属于束条件，如时延、时延抖动等，但仍然属于NP难度问难度问题，有许多启发式方法求解近似最优组播树。题，有许多启发式方法求解近似最优组播树。最大带宽树：最大带宽树：使用类使用类Dijkstra算法计算源到所有接收者算法计算源到所有接收者的最大带宽路径，然后，构造一个最大带宽树。的最大带宽路径，然后，构造一个最大带宽树。组播树组播树类型：类型：有源树：以源节点为根覆盖所有组成有源树：以源节点为根覆盖所有组成员的树，每个节点独立产生。员的树，每个节点独立产生。共享树：以汇聚点为根覆盖所有组成共享树：以汇聚点为根覆盖所有组成员
45、的树，所有节点公用。单向共享树员的树，所有节点公用。单向共享树组播流必须经过根；双向共享树组播组播流必须经过根；双向共享树组播流可不经过树根。流可不经过树根。第第四四章章 I IP P路路由由4.3.3 组播路由协议组播路由协议泛洪与剪枝：泛洪与剪枝：SGGGSGGG4.3.3.1 域内组播路由协议域内组播路由协议DVMRP：距离向量组播路由协议为每个源构造一棵组距离向量组播路由协议为每个源构造一棵组播树。利用播树。利用RIP协议实施泛洪和剪枝，需协议实施泛洪和剪枝，需进行反向路径进行反向路径检查检查。实现容易，但第一个分组需在整个网络中扩散；。实现容易，但第一个分组需在整个网络中扩散；扩展性
46、不好；不支持扩展性不好；不支持QoS。MOSPF：最短路径优先多播协议为每个源构造一棵组最短路径优先多播协议为每个源构造一棵组播树，使用一个新的播树，使用一个新的LSA对对OSPF数据库进行补充。利数据库进行补充。利用用OSPF协议反向路径检查，实施泛洪和剪枝。当第一协议反向路径检查，实施泛洪和剪枝。当第一个组播分组到达时，路由器本地构造有源树，不需分组个组播分组到达时，路由器本地构造有源树，不需分组扩散到全网扩散到全网。但是计算量相当大，扩展性不好，两层结但是计算量相当大，扩展性不好，两层结构只能部分改进路由计算问题。构只能部分改进路由计算问题。CBT（Core Based Tree）：）：
47、构造一棵所有组成员共享构造一棵所有组成员共享的组播树，路由器只需为每个组播组维护一个状态即可；的组播树，路由器只需为每个组播组维护一个状态即可；不采用反响路径检查，使用路由表获得通往核心的下一不采用反响路径检查，使用路由表获得通往核心的下一跳，独立于路由协议（交换跳，独立于路由协议（交换RPDU）。）。构造构造CBT的步骤：的步骤：1）定位核心。）定位核心。2）新成员利用最短路径向核心发送）新成员利用最短路径向核心发送“Join”，经过的，经过的 路由器记录这一状态。路由器记录这一状态。3）核心或核心或CBT成员收到成员收到“Join”，沿反向路经发回沿反向路经发回 “Join-ack”，所有
48、经过的路由器生成组播记录所有经过的路由器生成组播记录 （增加一个树的分支）。（增加一个树的分支）。 CBT通过通过Join和和Join-ack保证不出现环路；允许保证不出现环路；允许组播分组不经过核转发，双向共享树。组播分组不经过核转发，双向共享树。JoinJoin-ackR2R4R3R5R1R7R6SCoreNew第第四四章章 I IP P路路由由 计算计算Steiner树以及选择核心本身就是一个树以及选择核心本身就是一个NP难度问题；不支持难度问题；不支持QoS路由和策略路由；多核心的路由和策略路由；多核心的方案不理想。方案不理想。PIM-DM：协议无关的组播密集模式是专门针对具有大协议无
49、关的组播密集模式是专门针对具有大量组成员的组播设计的，与量组成员的组播设计的，与DVMRP类似，但独立于路类似，但独立于路由协议进行反向路径转发检查。直接检查路由表去往源由协议进行反向路径转发检查。直接检查路由表去往源节点的端口是否是接收分组的端口，然后实施转发、剪节点的端口是否是接收分组的端口，然后实施转发、剪枝、或者丢弃操作，构造有源树。枝、或者丢弃操作，构造有源树。PIM-SM：协议无关的组播稀疏模式是专门针对组成员协议无关的组播稀疏模式是专门针对组成员不集中分布的组播设计的，与不集中分布的组播设计的，与CBT类似。但类似。但PIM-SM中，中，源发送的分组必须先发给汇聚点源发送的分组必
50、须先发给汇聚点RP（核心）；如果源核心）；如果源节点发送分组速率超过特定阈值，可以使用有源树替代节点发送分组速率超过特定阈值，可以使用有源树替代RP共享树。共享树。R1R2R3R4R5RPSMR1R2R3R4R5RPSMMIP：Multicast Internet Protocol中组播树构造既可中组播树构造既可以从源节点发起（小组播组），也可以从接收方发起以从源节点发起（小组播组），也可以从接收方发起（有大量接收者），（有大量接收者），MIP不需预先配置核心，共享树以不需预先配置核心，共享树以源节点或接收节点为根，使用双向共享树。源节点或接收节点为根，使用双向共享树。MIP独立于协议，采用扩
51、散机制（发送请求独立于协议，采用扩散机制（发送请求/等待确认）等待确认）来与邻节点交互构造树、修改树。提出来与邻节点交互构造树、修改树。提出MIP的主要目的的主要目的是在单播路由表出现短暂不一致时，仍可以构造无环路是在单播路由表出现短暂不一致时，仍可以构造无环路的组播树。的组播树。第第四四章章 I IP P路路由由4.3.3.2 域间组播路由协议域间组播路由协议PIM-DM/PIM-SM：利用利用PIM-DM建立有源树进行域内建立有源树进行域内组播路由；利用组播路由；利用PIM-SM建立共享树进行域间组播路由。建立共享树进行域间组播路由。该方案适用于企业级网络，不适合应用于该方案适用于企业级网
52、络，不适合应用于Internet，因因为发布为发布RP和维护软状态需消耗大量网络资源，且该方和维护软状态需消耗大量网络资源，且该方案不支持策略路由。案不支持策略路由。MSDP：是一种过渡方案。是一种过渡方案。Multicast Source Discovery Protocol不够造域间共享树，每个域的不够造域间共享树，每个域的RP都和某些其他域的都和某些其他域的RP建立建立MSDP会话，为自己内部的会话，为自己内部的组成员找到位于其他域的源节点。其特点是实现简单，组成员找到位于其他域的源节点。其特点是实现简单，采用反向路径检查来提高鲁棒性。采用反向路径检查来提高鲁棒性。BGMP：是一种长远方
53、案，可以和任何一种域内组播路是一种长远方案，可以和任何一种域内组播路由协议协同工作。由协议协同工作。BGMP使用使用BGP路由表构造连接各路由表构造连接各个域内组播树的域间双向共享树，类似于个域内组播树的域间双向共享树，类似于CBT，但根为但根为某个域。域边界路由器即运行某个域。域边界路由器即运行BGMP，也运行也运行MIGP；MIGP将域内成员的变化通知将域内成员的变化通知BGMP，触发加入或剪枝触发加入或剪枝操作。操作。BGMP中，根域的选择对性能很大。中，根域的选择对性能很大。EXPRESS：EXPlicit Requested Single Source是是介介于网络层组播和应用层组播
54、之间的策略。于网络层组播和应用层组播之间的策略。EXPRESS中，中，主机向网络发送明确的订阅请求来申请接收组播信道主机向网络发送明确的订阅请求来申请接收组播信道（S，E）的数据，而只有组播信道的源可以向信道发的数据，而只有组播信道的源可以向信道发送数据。订阅和退订的过程类似于送数据。订阅和退订的过程类似于CBT的加入和离开，的加入和离开，只是订阅消息向源传播，且可以认证。只是订阅消息向源传播，且可以认证。MSDP操作过程：操作过程：1）组播源在域内使用）组播源在域内使用PIM-SM方式发送组播分组。方式发送组播分组。2）本域的）本域的RP向其向其MSDP对等体发送活动源对等体发送活动源SA消
55、息。消息。3）收到）收到SA的对等体利用的对等体利用BGP4路由表反向路径检查。路由表反向路径检查。4）收到）收到SA的对等体检查自己域内是否有对应的组成员，的对等体检查自己域内是否有对应的组成员， 如果有，如果有，RP触发一个加入消息发往组播源，建立源触发一个加入消息发往组播源，建立源 节点域与本域之间的组播树分支。节点域与本域之间的组播树分支。5）如果）如果SA消息中包含数据，消息中包含数据，RP在本域组播树中转发在本域组播树中转发 数据。数据。6）重复）重复35步骤，直到所有步骤，直到所有MSDP对等体都收到对等体都收到SA 消息，以及所有组成员都收到源节点数据为止。消息，以及所有组成员
56、都收到源节点数据为止。问题：问题：只要源节点发送组播数据，对应的只要源节点发送组播数据，对应的RP就要周期性就要周期性 发送发送SA，这个周期的选择是一个很重要的问题。这个周期的选择是一个很重要的问题。6.3 组播路由协议S1Domain B根域IGMPPIM-DMR3Domain EDVMRPDomain FPIM-DMS2Domain ACBTR1Domain DPIM-SMDomain CCBTR2有源分支第第四四章章 I IP P路路由由4.3.4 可靠组播可靠组播4.3.4.1 基本概念基本概念可靠性：可靠性：所有组播数据最终都能够正确传送给每个接所有组播数据最终都能够正确传送给每个
57、接 收者。收者。评估指标：评估指标：出错率（误码、失序）、丢失率（超时、出错率（误码、失序）、丢失率（超时、 被丢弃）。被丢弃）。半可靠性：半可靠性：通常用于可容忍一定数据丢失率的实时组通常用于可容忍一定数据丢失率的实时组 播应用。播应用。时间限制可靠性：时间限制可靠性：适用于实时性要求高的组播应用。适用于实时性要求高的组播应用。完全可靠性：完全可靠性：适用于正确性要求高、实时性不强的组适用于正确性要求高、实时性不强的组 播应用。播应用。可靠性组播需要解决的问题：可靠性组播需要解决的问题：不再是一对一的端可靠性，而是一对多、多对多的关不再是一对一的端可靠性，而是一对多、多对多的关 系，需要不同
58、机制来满足不同应用对可靠性的不同要系，需要不同机制来满足不同应用对可靠性的不同要 求。求。一对多和多对多会导致大量的一对多和多对多会导致大量的TCP的的Ack数据包，即数据包，即 “Ack”风暴，这给发送者和网络都带来极大的资源消风暴，这给发送者和网络都带来极大的资源消 耗。耗。过多的远程差错恢复过程对实时性组播应用的效率，过多的远程差错恢复过程对实时性组播应用的效率， 以及网络带宽的占用都产生严重影响。以及网络带宽的占用都产生严重影响。第第四四章章 I IP P路路由由4.3.4.2 重传情求重传情求ARQ4.3.4.3 前向纠错前向纠错FEC FEC通过在传输中引入冗余码来提高可靠性，传输
59、通过在传输中引入冗余码来提高可靠性，传输层层FEC利用丢失校正码和已知包数来处理丢失情况。一利用丢失校正码和已知包数来处理丢失情况。一旦网络传输质量不好，旦网络传输质量不好，FEC不能保证绝对的可靠性。不能保证绝对的可靠性。 4.3.4.4 ARQ和和FEC组合应用组合应用 可实现高可靠性，但是具体实现难度和计算复杂度可实现高可靠性，但是具体实现难度和计算复杂度都较大。都较大。4.3.4.5 差错恢复差错恢复 通过设置分布式的重传代理来提高重传效率，以及通过设置分布式的重传代理来提高重传效率，以及减轻网络流量负荷。减轻网络流量负荷。第第四四章章 I IP P路路由由肯定确认肯定确认ACK：由发
60、送者检测数据包丢失并重由发送者检测数据包丢失并重传，接收者回送传，接收者回送ACK。需要使用需要使用ACK聚合方法聚合方法（乐观聚合或悲观聚合）来减少（乐观聚合或悲观聚合）来减少ACK风暴。风暴。否定确认否定确认NACK：由接收者检测数据包丢失，由接收者检测数据包丢失，并回送并回送NACK请求重传。出错率低时，只需少请求重传。出错率低时，只需少量量NACK即可。但是，即可。但是，NACK定时器的设置是定时器的设置是一个关键问题。一个关键问题。确确认认模模型型4.4.1 任意播定义任意播定义任意播任意播/选播：选播：是指源主机报数据传输给任意播地址表示是指源主机报数据传输给任意播地址表示的一组主
61、机中的一组主机中“最近最近”的一台主机。的一台主机。4.4.2 任意播策略任意播策略网络层任意播：网络层任意播：IP anycast基于网络拓扑结构信息来确基于网络拓扑结构信息来确定接收分组的服务器，如最小路由代价。定接收分组的服务器，如最小路由代价。应用层任意播：应用层任意播：Application layer anycast基于应用参基于应用参数确定接收分组的服务器，如处理器能力、响应时间、数确定接收分组的服务器，如处理器能力、响应时间、请求连接数量等。请求连接数量等。4.4.3 优点与作用优点与作用 1）简化配置；）简化配置； 2）提高网络可靠性；）提高网络可靠性； 3）负载均衡。）负载均衡。4.4.4 涉及的问题涉及的问题 1）地址空间；）地址空间； 4）组成员通告）组成员通告 2）路由；）路由； 5）TCP重定向；重定向； 3）局域网通信；）局域网通信； 6）全球）全球IP任意播。任意播。第第四四章章 I IP P路路由由4.4 选播选播
