《计算机网络技术》课件-项目三：路由协议

1.透明网桥的自学习网桥及其转发表转发表接口管理软件网桥协议实体接口1接口

2缓存①②③⑥⑤④网段B网段

A网桥111①③⑤②④⑥站地址接口222透明网桥目前使用得最多的网桥是透明网桥(transparentbridge)。透明网桥通过自学习算法建立自己的转发表，无需用户配置，是一种即插即用设备。“透明”是指局域网上的站点并不知道所发送的帧将经过哪几个网桥，对各站点来说，网桥好像是“透明”的，是看不见的。网桥自学习转发表在转发表中记录接收到帧的源地址及接收到该帧的接口在转发表中找不到目的地址所在接口时就向所有其他接口转发网桥自学习转发表地址接口B2B1ABCDEF1212地址接口A→CA1A→CA1

当网桥找不到目的地址所在接口时向所有其他接口转发！收到该帧网桥自学习转发表地址接口B2B1ABCDEF1212地址接口A→CA1C→AC2A→CA1C→AC1不转发该帧网桥自学习转发表地址接口B2B1ABCDEF1212地址接口B1B→AA→CA1C→AC2A→CA1C→AC1通过接收帧的源地址及接收接口学习站点和接口的对应关系！不转发该帧网桥自学习转发表网络拓扑可能会发生改变。在网桥的转发表中写入的信息除了地址和接口外，还有帧进入该网桥的时间。定期丢弃陈旧的信息，使网桥中的转发表能反映当前网络的最新拓扑状态。网桥的自学习和转发帧的步骤如没有，就在转发表中增加一个项目（源地址、进入的接口和时间）。如有，则把原有的项目进行更新。网桥收到一个帧后先进行自学习。查找转发表中与收到帧的源地址有无相匹配的项目：然后进行转发帧操作。先查找转发表中与收到帧的目的地址有无相匹配的项目：如没有，则向所有其他接口（进入的接口除外）转发。如有，则按转发表中给出的接口进行转发。若转发表中给出的接口就是该帧进入网桥的接口，则应丢弃该帧（因为这时不需要通过网桥进行转发）。如图所示，如果网桥的转发表初始为空，这时站点A发送帧给站点B会导致什么问题？思考题局域网2局域网1网桥2网桥1

A

B透明网桥的自学习2.OSPF协议OSPF与RIP一样都是互联网中被广泛应用的内部网关协议开放最短路径优先(OpenShortestPathFirst)但与RIP使用的是距离向量路由选择算法不同，OSPF使用的是链路状态（LinkState,LS）路由选择算法如果一个路由器能获得整个网络的完整拓扑，则很容易计算出到每个网络的最短路径，并生成路由表1.链路状态算法基本思想将网络抽象成一个图2111522335ABCDEF管理员根据流量、距离、时延、带宽等为每条链路设置一个度量使用Dijkstra算法求出到所有结点的最短路径如何让每个路由器都能获得整个网络的拓扑？广播链路状态广播：我和哪些结点相邻，以及与相邻结点之间链路的度量（链路状态）广播链路状态当链路状态发生变化时，广播链路状态每个路由器感知其直接连接的链路的链路状态当直接连接的链路状态发生变化时，向所有路由器广播该链路状态路由器根据获取的全网拓扑计算到每个网络的最短路径（最短路径树）基于最短路径树生成路由表OSPF是使用链路状态算法的协议之一1.链路状态算法每个路由器都维护了一个链路状态数据库。这个数据库实际上存储的就是全网拓扑结构图链路状态数据库的同步（实现全网一致）初始数据从邻居获得状态变化时广播状态更新报文为增强健壮性，也会周期性广播，例如每30分钟2.链路状态数据库(link-statedatabase)类型1，问候(Hello)分组用来发现和维持邻站的可达性。每两个相邻路由器每隔10秒钟要交换一次问候分组，若有40秒钟没有收到某个相邻路由器发来的问候分组，则认为该相邻路由器不可达，并修改相应的链路状态。3.OSPF的分组类型3.OSPF的分组类型类型2，数据库描述(DatabaseDescription)分组初始时，路由器用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。类型3，链路状态请求(LinkStateRequest)分组路由器可以主动使用链路状态请求分组向相邻路由器请求发送自己所缺少的某些链路状态项目的详细信息。3.OSPF的分组类型类型4，链路状态更新(LinkStateUpdate)分组作为链路状态请求的应答用洪泛法对全网更新链路状态（当链路状态发生改变时，或周期性）类型5，链路状态确认(LinkStateAcknowledgment)

分组实现可靠洪泛，对链路状态更新分组进行确认OSPF的分组直接用IP数据报传送更新分组R收到状态更新分组，要发回确认分组，并向其他接口转发更新分组4.OSPF的可靠洪泛确认分组更新分组图例：确认分组状态更新分组有序号，路由器不会转发重复分组4.OSPF的可靠洪泛R确认分组更新分组图例：仅向上游路由器发回确认，但不会转发确认分组4.OSPF的可靠洪泛R确认分组更新分组图例：对于大规模的网络，大量更新分组的洪泛导致网络严重拥塞！4.OSPF的可靠洪泛R确认分组更新分组图例：区域1区域2区域3主干区域AS边界路由器主干路由器区域边界路由器区域内部路由器5.层次OSPF区域1区域2区域3主干区域AS边界路由器主干路由器区域边界路由器更新分组仅在本区域内广播；每个内部路由器维护本区域完整拓扑但仅知道到其他区域网络的概括信息区域内部路由器5.层次OSPF区域1区域2区域3主干区域主干路由器区域边界路由器区域边界路由器:负责为发送到该区域以外的分组选路，概括区域路由信息AS边界路由器区域内部路由器5.层次OSPF区域1区域2区域3主干区域主干路由器区域边界路由器主干路由器:维护主干区域完整拓扑，以及到其他区域网络的路由概括信息AS边界路由器区域内部路由器5.层次OSPF区域1区域2区域3主干区域主干路由器区域边界路由器边界路由器:连接到其他ASAS边界路由器区域内部路由器5.层次OSPF区域1区域2区域3主干区域主干路由器区域边界路由器AS边界路由器由于链路状态更新分组的洪泛被限制在小范围的区域内，通过层次路由OSPF能用于规模很大的网络区域内部路由器5.层次OSPFOSPF的要点基于链路状态路由选择算法，没有RIP“坏消息传播得慢”的问题01OPTION02OPTION网络管理员可以根据流量、距离、时延、带宽等为链路设置度量03OPTION支持分区域层次路由，将链路状态信息的洪泛限制在小范围的区域内部，可用于大规模网络04OPTIONOSPF的分组直接使用IP数据报进行传输，并采用可靠洪泛请比较“距离向量”路由选择算法和“链路状态”路由选择算法要点。习题OSPF协议3.边界网关协议BGP路由选择算法将很难收敛交换的路由信息会占用大量的带宽许多单位不愿意外界了解自己单位网络的具体细节希望采用自己喜欢的路由选择协议但又需要与互联网上其它单位网络互通因特网分层路由管理问题规模问题AS1AS3AS2AS5AS4在自治系统内部的路由选择叫做域内路由选择(intradomainrouting)，自治系统之间的路由选择也叫做域间路由选择(interdomainrouting)自治系统AutonomousSystem分层路由和自治系统

用内部网关协议（例如，RIP）自治系统B自治系统A用外部网关协议（BGP-4）R1R2

用内部网关协议（例如，OSPF）域内路由选择协议也称为内部网关协议IGP(InteriorGatewayProtocol)域间路由选择协议也称为外部网关协议EGP(ExternalGatewayProtocol)边界网关协议BGP自治系统间路由选择，一条路径要通过几个不同AS时，要想对这样的路径计算出有明确物理意义的代价是不太可能的。自治系统之间的路由选择必须考虑有关策略，例如：尽量使自己的流量不通过某个自治系统不允许某个自治系统的流量通过自己的自治系统因此，边界网关协议BGP力求寻找一条到达目的网络符合策略要求，经过自治系统少的路由，而并非要寻找一条有明确物理意义的“最佳”路由。1.BGP的设计目标01OPTION02OPTION03OPTIONBGP发言人BGP发言人BGP发言人BGP发言人BGP发言人AS1AS3AS2AS5AS4在TCP连接上建立BGP会话，交换BGP报文（路由信息）。2.BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人AS1AS3AS2AS5AS4使用TCP连接能提供可靠的服务，保证了路由信息传输的可靠性2.BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人AS1AS3AS2AS5AS4使用TCP连接交换路由信息的两个BGP发言人，彼此成为对方的邻站或对等方2.BGP发言人BGP发言人BGP发言人BGP发言人AS1AS3AS2AS5AS4向邻站通告到所有已知网络的最短路径（包含经过的所有AS号）2.BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人AS1AS3AS2AS5AS4将两个AS之间的BGP会话称为外部BGP会话（externalBGPsession）3.eBGP与iBGPeBGPBGP发言人BGP发言人BGP发言人AS1AS3AS2AS5AS43.eBGP与iBGPeBGP将同一AS内部路由器之间的BGP会话称为内部BGP会话（internalBGPsession）iBGP

AS内部的各路由器将iBGP获得的外部路由信息和内部网关协议得到的路由信息进行合并生成最终的路由表。主干网（AS1）地区ISP（AS2）地区ISP（AS3）本地ISP（AS4）N1，N2本地ISP（AS5）N3，N4本地ISP（AS6）N5本地ISP（AS7）N6，N7自治系统AS2

的BGP发言人通知主干网的BGP发言人：“经过(AS2,AS4)可到达网络N1,N2。”4.路径向量算法主干网AS1可向其他AS通告：“经过（AS1,AS2,AS4）可到达网络N1

和N2

。”4.路径向量算法主干网（AS1）地区ISP（AS2）地区ISP（AS3）本地ISP（AS4）N1，N2本地ISP（AS5）N3，N4本地ISP（AS6）N5本地ISP（AS7）N6，N7获得路由：“经（AS3,AS1,AS2,AS4）可到达网络N1

和N2

。”4.路径向量算法主干网AS1可向其他AS通告：“经过（AS1,AS2,AS4）可到达网络N1

和N2

。”主干网（AS1）地区ISP（AS2）地区ISP（AS3）本地ISP（AS4）N1，N2本地ISP（AS5）N3，N4本地ISP（AS6）N5本地ISP（AS7）N6，N7由于路径（AS1,AS2,AS4）中包含自己AS2，不接受该路由信息！4.路径向量算法主干网（AS1）地区ISP（AS2）地区ISP（AS3）本地ISP（AS4）N1，N2本地ISP（AS5）N3，N4本地ISP（AS6）N5本地ISP（AS7）N6，N7路径向量算法：相邻结点间互相通告自己到所有目的地的路径信息（路径经过的结点列表），各结点从获取的路径信息中选择一条到目的地经过结点数最少且不存在环路的路由。没有“坏消息传播得慢”的问题！采用路径向量算法，能够有效检测路由环路，因此没有距离向量算法的“坏消息传播得慢的问题”。在BGP刚刚运行时，BGP的邻站间交换整个的BGP路由表。但以后只在发生变化时更新有变化的部分（增加、修改或撤销某路由）。使用TCP传输路由信息，保证了信息传输的可靠性。由于路径向量信息包含经过的每个自治系统的ID，策略可以很方便地加入到路径的选择中。4.BGP协议的要点为什么BGP选择“路径向量”路由选择算法，而没有使用“距离向量”路由选择算法？思考题边界网关协议BGP4.路由器的工作原理一、路由器的构成路由器是一种具有多个输入端口和多个输出端口的专用计算机，其任务是转发分组。路由器将某个输入端口收到的分组，按照分组要去的目的地（即目的网络），把该分组从路由器的某个合适的输出端口转发给下一跳路由器。下一跳路由器也按照这种方法处理分组，直到该分组到达终点为止。课件制作人：谢钧谢希仁路由器的任务“转发”和“路由选择”的区别课件制作人：谢钧谢希仁“转发”(forwarding)就是路由器根据转发表将用户的IP数据报从合适的端口转发出去。“路由选择”(routing)则是按照路由选择算法，根据从各相邻路由器得到的关于网络拓扑的变化情况，动态地改变所选择的路由。路由表是根据路由选择算法得出的。而转发表是由路由表生成的。路由器的任务可分解为两个部分1.典型的路由器结构课件制作人：谢钧谢希仁路由选择（控制平面）路由选择处理机路由选择协议路由表3输入端口3交换结构输入端口输出端口分组转发(数据平面)转发表分组处理输出端口……11133122223——网络层2——数据链路层1——物理层2.输入端口若分组的接收者是路由器自己，需要交给相应的上层协议去处理，如发送给路由器的RIP或OSPF分组等需要送交路由器的路由选择部分中的路由选择处理机。否则，网络层处理模块按照分组首部中的目的地址查找转发表，交给交换结构交换到合适的输出端口。课件制作人：谢钧谢希仁物理层处理数据链路层处理网络层处理分组排队

交换结构

输入端口的处理从线路接收分组查表和转发

若交换结构处理分组的速率赶不上分组进入队列的速率，则会导致输入队列排队！3.交换结构课件制作人：谢钧谢希仁最早的路由器就是多网络接口的计算机，收到一个分组时，将分组就从输入端口复制到存储器中，从分组首部提取目的地址，查找路由表，再将分组复制到合适的输出端口的缓存中。采用这种方式分组要两次经过系统的总线（一次写和一次读），交换速度比较慢。许多现代的低端路由器也通过存储器进行交换，与早期的路由器的区别就是目的地址的查找和分组在存储器中的缓存都是在输入端口中进行的。I1I3I2O1O2存储器(a)通过存储器O33.交换结构课件制作人：谢钧谢希仁分组从输入端口通过共享的总线直接传送到合适的输出端口，不需要路由选择处理机的干预。但是，由于总线是共享的，因此在同一时间只能有一个分组在总线上传送。当分组到达输入端口时，若发现总线忙，则被阻塞而不能通过交换结构，并在输入端口排队等待。路由器的转发带宽显然要受到总线速率的限制，要想实现无阻塞交换，交换总线的速率要大于所有输入端口速率的总和。由于只经过一次总线，比通过存储器交换要快。I1I3I2O1O2(b)通过总线总线O33.交换结构课件制作人：谢钧谢希仁这种交换结构常称为互连网络（InterconnectionNetwork），它有2N条纵横交叉的总线，通过控制相应的交叉结点使水平总线和垂直总线接通还是断开，将分组转发到合适的输出端口。当输入端口收到一个分组时，就将它发送到与该输入端口相连的水平总线上。若通向所要转发的输出端口的垂直总线是空闲的，则在这个结点将垂直总线与水平总线接通，然后将该分组转发到这个输出端口。但若该垂直总线已被占用（有另一个分组正在转发到同一个输出端口），则后到达的分组就被阻塞，必须在输入端口排队。I1I3I2O1O2O3(c)通过互连网络互连网络4.输出端口把交换结构传送过来的分组先进行缓存。数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。课件制作人：谢钧谢希仁物理层处理数据链路层处理网络层处理分组排队

输出端口的处理向线路发送分组缓存管理交换结构若从交换结构到达队列的分组速率超过输出链路的速率，则会导致输出队列排队！如果路由器足够快是不是就不会出现排队？二、路由器与交换机的比较两种基于存储转发的分组交换设备的比较：交换机工作在数据链路层，优点是：即插即用，并具有相对高的分组过滤和转发速度。缺点是：大型交换机网络要求交换机维护大的转发表，主机中维护大的ARP表，并可能产生广播风暴，逻辑拓扑被限制为树。路由器工作在网络层，优点是：能提供更加智能的路由选择，并能隔离广播域。缺点是：路由器不是即插即用的，对每个分组处理时间通常比交换机更长。课件制作人：谢钧谢希仁二、路由器与