第2章TCPIP协议分析-5IP路由协议.ppt

网 络 协 议,第2章 TCP/IP协议分析,TCP/IP协议族 编址与地址解析 网际协议 网际控制消息协议 IP路由协议 IP组播协议 传输层协议 应用层协议,路由是指导IP报文发送的路径信息。,2.5 IP路由协议,（1）路由器基本概念,路由器通过一定的策略决定数据的转发。转发策略称为路由选择（routing）,网络上传输的IP数据包就是“行人、车辆”,路由器是IP互联网络的枢纽、主要节点设备、“交通警察”,2.5.1 路由转发,实现远程网络的互联（DDN、LAN、ATM） 数据在各种链路协议间的转换（HDLC、PPP、FR） 流量管理（QOS） 互联网络的“邮递员”数据包路由（静态路由、动态路由）,（2）路由器功能,用路由器实现LAN-LAN互连,路由器实现LAN-WAN-LAN互连,（3）路由器基本结构,路由表结构,共有内容 目标网络地址 目标网络的网络地址以及相应的子网掩码。 网关地址 接口 此外，依厂商不同，路由表中还会有 标记 生成该路由条目的协议 管理距离值 开销 该路由条目生存的时间等,（4）基本路由转发方式,直接路由 间接路由 默认路由 特定主机路由, 直接路由,指在一个物理网络上，数据报从一台机器直接传送到另一台机器。 直接路由是在配置完路由器网络接口的IP地址后自动生成的，因此，如果没有对这些接口进行特殊的限制，这些接口所直连的网络之间就可以直接通信。,发方如何知道与目的地是否同处一个网络？,对照发方和目的主机的网络编号； ARP映射IP地址为MAC地址。,路由器R2的概念路由表,路由器R2直接连接网络2和网络3，因此，R2能将数据报直接发往连在这两个网络上的任何目的主机。 当一个数据报的目的地在网络4中时，R2就需将数据报发往路由器R3。, 间接路由,当路由器与目的结点不在同一个网络中时，无法直接转发，需采用间接转发方式。 间接转发的过程是先通过路由选择功能选定某一个下一跳路由器，并把分组封装到物理帧中，发送到这个下一跳路由器上，由下一跳路由器进行进一步转发。,R2的路由表,默认路由和特定主机路由,在选路时，若未能在路由表中搜索到与目的地址相匹配的表项，那么 IP 协议可以采用一条预定义的默认路由，将分组转发到一个默认的下一跳路由器上；默认路由用来进一步减少路由表的规模。 默认路由被定义为网络编号为 0.0.0.0 的路由。,特定主机路由：指定每个主机的路由使本地网络管理员对网络的使用有更多的控制，允许对它进行测试，并且也可以用于安全访问的控制。 在调试网络连接或选路表时，为单个主机指定一个特殊路由的能力尤其有用。,路由表的建立也就是路由表的初始化。路由表的建立是在路由器启动的时候进行的，路由器启动时首先建立一个初始路由表，然后通过路由协议逐步进行路由刷新，以反映真实的网络拓扑。,（5）路由表的建立和刷新,路由表的初始化一般有以下几种情况： a. 在系统启动时从外存中读取完整的路由表，而在系统关闭时将当前的路由表（已经经过刷新）保存到外存中，供下次启动时使用； b. 系统启动使提供一个空路由表，使用命令填充初始表项，然后通过路由协议逐步刷新； c. 系统启动时，通过路由器所直接连接的周边网络推导出一组初始路由，然后再通过路由协议，从周边路由器那里获得距离更远的网络的路由信息，如此不断通过已知网络获取未知网络的路由信息，直到逐步掌握全网的路由信息。, 标准路由选择算法,(网络地址，下一跳地址),基于路由表,前三个比特对地址类型和格式进行了编码（A、B、C和D）,（6）路由选择算法,从数据库中提取目的IP地址D，并计算网络前缀N； if N与任何直接相连的网络的地址匹配 then 通过该网络把数据报交付到目的地D（其中涉及到把D转换成物理地址、封装数据报及发送该帧。） else if 表中包含特定于具体主机的一个到D的路由 then 把数据报发送到表中指定的下一跳 else if 表中包含到网络N的一个路由 then 把数据报发送到表中指定的下一跳 else if 表中包含了一个默认路由 then 把数据报发送到表中指定的默认路由器 else 宣布路由选择错误；,IP选路算法：RouteDatagram(Datagram,RoutingTable),10.0.0.5,20.0.0.5,20.0.0.6,30.0.0.6,30.0.0.7,40.0.0.7,目的网络 路由到,20.0.0.0 直接投递 30.0.0.0 直接投递 10.0.0.0 20.0.0.5 40.0.0.0 30.0.0.7,例: R2的下一跳路由选择,R1,R2,R3,10.0.0.0,20.0.0.0,30.0.0.0,40.0.0.0, 子网路由选择算法,基于路由表,(子网掩码，网络地址，下一跳地址),子网掩码和目的地址逐比特“与”操作，再与网络地址相比较。, 掩码和数据报转发,往往只包含目的地的网络地址,目的地址,掩码,下一跳,如果下一跳是一个路由器，则必须给出该路由器的IP地址。,决定了第一部分网络地址的长度,if ( (Maski&D) = = Destinationi) forwarding to NextHopi,从数据库中提取目的IP地址ID；计算目的网络的网络地址IN； if IN = 某直接相连网络的地址 then 通过该网络发送该数据报 （包括把ID转换成物理地址、封装数据报及发送该帧。） else for 路由表中的每一项 do N = ID逐位与子网掩码“与” if N = 该表项中的网络地址字段 then 将本数据报发往该表项中的下一跳地址所指定的路由器 endforloop else if 表中包含了一个默认路由 then 将本数据报发往该表项中的默认路由器 if 没有找到匹配的表项 then 宣布路由选择错误；,算法：Route_IP_Datagram(datagram, routing_table),30.0.0.7,40.0.0.7,40.0.0.8,128.1.0.8,128.1.0.9,192.4.10.9,例: R2的路由表,R1,R2,R3,30.0.0.0,40.0.0.0,128.1.0.0,192.4.10.9,目的网络 掩 码 下一跳,30.0.0.0 255.0.0.0 40.0.0.7 40.0.0.0 255.0.0.0 直接投递 128.1.0.0 255.255.0.0 直接投递 192.4.10.0 255.255.255.0 128.1.0.9,路由器基本工作原理路由转发,查找主机路由,IP packet,丢弃,查找直连路由,查找网段路由,查找默认网关,添加静态路由 Route add （系统重启后不保存这些路由） Route add p (不管计算机启动多少次，路由都会在） 更改网关 Route change （当需要优化路由中的数据报传输时，可以用该命令更改分配给特定路由的度量标准） 删除路由 Route delete （允许使用通配符来删除同类的路由） Route delete f （清除所有网关入口的路由表） -f 选项和别的命令一起使用时，会在运行该命令前先清除路由表。,为了保证选路的正确，任何一个路由器都必须了解全部网络或部分网络的路由信息。为此，TCP/IP定义了一组路由协议实现路由信息的自动获取： 在路由器之间传播网络的动态变化信息及其相应的路由信息； 使路由器根据获得的知识实现特定的路由算法； 使路由器根据计算结果维护路由表，并为数据报确定传输路径。,2.5.2 路由协议,需要考虑的要素： a. 可升级性和可扩展性：协议本身在不改变其基本操作和向后兼容的前提下加入新功能的能力（新功能可能包括组播、QoS选路等）。可升级性是由协议自身的能力所决定的。 b. 环路避免：路由协议在计算和生成新的路由表时，应该能够避免环路的出现，特别时在网络拓扑发生改变的不稳定期间，避免环路的难度很大。 c. 收敛速度：当网络拓扑改变时（链路失效或信网络加入等），路由协议必须能够将该信息发布到整个网络中，使每个路由器都能根据该信息计算和生成新的路由表，反映网络拓扑的变化。收敛速度是路由协议的一项重要性能。 d. 路由算法：路由协议所采用的路由算法也将影响到协议的性能。目前的路由协议中存在着两种基本的路由算法（距离向量法和链路状态法）。,讨论路由选择算法涉及的主要参数：,跳数（hop count） 分组从源结点到达目的结点经过的路由器的个数 带宽（bandwidth） 链路的传输速率 延时（delay） 分组从源结点到达目的结点花费的时间 负载（load） 通过路由器或线路的单位时间通信量 可靠性（reliability） 传输过程中的误码率 开销（overhead） 传输过程中的耗费，与所使用的链路带宽相关,Internet是由大量的AS组成，各个AS由不同机构操纵。,1、自治系统,每个自治系统有一个唯一的 16 bit 标识符,（1）静态路由（Static routing） 静态路由是在路由器中设置的固定的路由表。除非网络管理员干预，否则静态路由不会发生变化。由于静态路由不能对网络的改变作出反映，一般用于网络规模不大、拓扑结构固定的网络中。 静态路由的优点是简单、高效、可靠，还可以提高安全性。在所有的路由中，静态路由优先级最高。当动态路由与静态路由发生冲突时，以静态路由为准。,2、路由协议分类,（2）动态路由（Dynamic routing） 动态路由是网络中的路由器之间相互通信，传递路由信息，利用收到的路由信息更新路由器表的过程。 根据实测或估计的距离、时延和网络拓扑结构等度量权值，自动计算最佳路径和建立路由表，而且能自动适应网络拓扑结构的变化，实时、动态地更新路由表. 动态路由适用于网络规模大、网络拓扑复杂的网络。当然，各种动态路由协议会不同程度地占用网络带宽和CPU资源。,根据是否在一个自治域内部使用，动态路由协议分为： （1）内部网关协议（IGP-Interior Gateway Protocol） 在自治系统（AS）边界内部运行的路由协议为内部网关协议（如：RIP、OSPF、IS-IS、IGRPE和IGRP） （2）外部网关协议EGP(Exterior Gateway Protocol) 在自治系统之间运行的路由协议为外部网关协议.,自治系统与路由选择协议,域内路由协议 （1）距离矢量路由选择 距离矢量路由选择（Distance vector routing）是让路由器维护一个路由表（即向量），路由表中存放着到达每个目的站点已知的最佳距离和路径。通过与相邻路由器交换信息，实现路由表的更新。该算法更新过程慢、交换信息量大、收敛速度慢，并且在刷新的过程中容易发生远近路由器路径不一致的问题。 （2）链路状态路由选择 链路状态路由选择，又称最短路径优先（SPF-Shortest Path First）算法。它弥补了距离矢量算法的缺陷，是一种更为先进的路由选择算法。,域间路由协议： 由于自治系统的组织管理不同，因此在计算跨越不同自治系统的通路时，需要考虑多方面的因素，如费用、可用性、性能、不同自治系统之间的商业关系等。 每个自治系统可以自由地选择最适合其需要的IGP，不过所有相互通信的自治系统必须使用相同的EGP。 例如：EGP-2(Exterior Gateway Protocol ) BGP-4(Border Gateway Protocal),两个AS在内部使用不同的IGP，一个路由器可同时运行两种路由协议：运行EGP以通告其可达性的路由器，也需要运行IGP以获得来自其自身自治系统的信息。,RIP（Route Information Protocol）是一种基于距离向量路由算法（distance vector routing）的用于小型AS中的路由协议。 路由器在以下三种情况下以响应报文的形式向外公告本地的距离向量信息： 每隔30秒自动发送一次 对相邻路由器发来的请求报文进行响应 当本地距离向量表发生变化时而进行的触发式更新 路由器收到响应报文后，将更新信息和本地距离向量表进行比较，选取代价更低的路由更新本地距离向量表。,3、RIP路由协议,N1,R1,R2,更新,N1 1 R1,RIP只适用于小型的同构网络，因为它允许的最大站点数为15，任何超过15个站点的目的地均被标记为不可达。而且RIP每隔30s一次的路由信息广播也是造成网络的广播风暴的重要原因之一。,距离向量算法,收到相邻路由器（其地址为 X）的一个 RIP 报文： (1) 先修改此 RIP 报文中的所有项目：将“下一跳”字段中的地址都改为 X，并将所有的“距离”字段的值加 1。 (2) 对修改后的 RIP 报文中的每一个项目，重复以下步骤： 若项目中的目的网络不在路由表中，则将该项目加到路由表中。 否则 若下一跳字段给出的路由器地址是同样的，则将收到的项 目替换原路由表中的项目。 否则 若收到项目中的距离小于路由表中的距离，则进行更新， 否则，什么也不做。 (3) 若 3 分钟还没有收到相邻路由器的更新路由表，则将此相邻路由器记为不可达的路由器，即将距离置为16（距离为16表示不可达）。 (4) 返回。,路由表的建立 路由表信息的更新,路由信息协议的工作过程, DV算法：链路成本变化（A上网）及链路故障（A下网）,B C D E A上网 初始时 1 第一次交换 1 2 第二次交换 1 2 3 第三次交换 1 2 3 4 第四次交换,B C D E A下网 1 2 3 4 初始时 3 2 3 4 第一次交换 3 4 3 4 第二次交换 5 4 5 4 第三次交换 5 6 5 6 第四次交换 7 6 7 6 第五次交换 7 8 7 8 第六次交换,无穷计算问题, DV算法：水平分裂法,如果z要通过y才能到达x，则z将对y宣称它到x的距离为无穷大。,x,y,z,水平分裂法的失败情况,A通知C到D的距离为； B通知C到D的距离为；,当C-D链路失效后，C到D不可达；,A选择经过B到D且距离为3； B选择经过A到D且距离为3；,A 、B相互交换最短距离直到无穷大。,RIPv1 vs. RIPv2,80年代中期，RIP已不能适应大规模异构网络的互连，开放最短路径优先OSPF随之产生。 OSPF采用链接状态（L-S）算法，1990年成为标准（RFC1247）。现在成为大型网络环境中广泛采用的路由协议。 改进RIP(Routing Information Protocal)的问题 计数至无穷大 收敛速度慢,4、OSPF路由协议,与RIP不同，OSPF将一个自治域再划分为区，相应地有两种类型的路由选择方式：当源和目的地在同一区时，采用区内路由选择；当源和目的地在不同区时，则采用区间路由选择。 一个大型的AS可分成若干32位编号的区域(area)，每个AS都有一个主干(backbone)区域，称为区域0。所有区域都与主干相连(可能要经过隧道)。 4类路由器：内部路由器，区域边界路由器，主干路由器，AS边界路由器。每个路由器都被分配一个唯一的32位的路由器标识符RID（Route ID）。,划分层次结构的区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。,OSPF 支持三种网络的连接,(1) 两个路由器之间的点对点连接 (2) 具有广播功能的局域网 (3) 无广播功能的广域网,OSPF协议的主要特点,使用分布式的链路状态协议； 路由器发送的信息是本路由器与哪些路由器相邻，以及链路状态（距离、时延、带宽等）信息； 当链路状态发生变化时用洪泛法向所有路由器发送； 所有的路由器最终都能建立一个链路状态数据库 ； 将一个自治系统再划分为若干个更小的区域，一个区域内的路由器数不超过200个。,链路状态路由选择算法的步骤,找出所有可达的相邻结点及它们的网络地址； 测定到这些相邻结点的代价； 将以上信息构成链路状态分组（link state packet）； 向网上所有结点发送链路状态分组； 利用收到的链路状态分组计算到各目的结点的最短通路。,OSPF报文头格式（24字节）,0=无认证 1=口令,0，填入0 1，8个字符的口令,OSPF报文使用IP数据报（协议标识为89）进行传输。 在广播环境中，发送到称为AllSPFRouter的保留组播地址224.0.0.5。 在非广播环境中，发送到特定邻居的IP地址。 OSPF有五种类型的路由协议包，通过报文中的类型字段加以定义： “1”-Hello：发现和维护邻居关系，每隔10秒交换一次 “2”-数据库描述：LSA（Link State Advertisement） “3”-链路状态请求：向一个邻居路由器请求LSA “4”-链路状态更新：向一个邻居路由器提供LSA “5”-链路状态确认：对收到的LSA的确认,OSPF的基本操作,确定可达性,只拥有本域的及到主干区域的路由信息； 具有相同的L-S图，采用相同的SPF算法； 采用扩散方式广播自己获得的网络知识（邻居和开销）到邻接路由器； 根据扩散的信息修改L-S图，计算到域内其他路由器的最短路径； 根据计算机结果维护各自的路由表。,内部路由器,拥有主干网的L-S信息，计算区域间、到其他AS的最短路径； 从与之相连的下级域边界路由器获取该域的路由信息，计算其到每个域的最短路径； 将主干到每个域的最短路径信息回传给域边界路由器。,主干路由器,具有域内路由器的功能； 拥有相邻域的L-S信息，并计算到达相邻域的最短路径； 域间的分组交换都通过其进行路径选择和数据交换。 例如：本域的路由器通过域边界路由器把分组送往主干网，经主干网送达目的域边界路由器，再由其通过域内路由送往目的主机。,区域边界路由器,指派路由器,多点接入的局域网采用了指派路由器的方法，使广播的信息量大大减少。 指派路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。 通过指派一个路由器来使相邻关系减少到N。,所有路由器都要维护与指派路由器及其备份的相邻关系,邻居与邻接,区域内 区域间 从源路由器到主干区域； 穿越主干区域到达目的区域； 到达目的路由器。 自治系统间,OSPF 支持三类路由,同一区域的路由器使用Dijkstra最短路径算法计算该区域中每个网络的最好路径,Interior router computes shortage (best) path to each network in the same area.,内部路由（Interior Routing）,区域间路由（Inter-Area） Routing,AS间路由（Inter-AS Routing）,OSPF的工作原理,区域内：利用洪泛法（flooding），每个路由器将它的相邻的所有路由器的链路状态，告诉给本区域中的所有其它路由器，这些信息使每个路由器都能建立一个链路状态数据库，构造出一个本区域的有向图，并计算最短路径（Dijkstra）。 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。而不像RIP那样，不管网络拓扑有无发生变化，路由器之间都要定期交换路由表的信息。,区域间：主干路由器从区域边界路由器处获取信息，计算出每个主干路由器到每个其它路由器的最佳路径。这一信息再传回区域边界路由器，由该路由器在它的区域中进行广播。这样一个要发送区域间分组的路由器就可选择一个去往主干的最佳出口路由器。,边界网关协议:用于AS之间 必须大量考虑策略 路由限制的例子 策略由手工配置 从BGP观点,网络分三类: 支线网络 多连接网络 中转网络 属于路径向量（path vector）协议 记录使用确切路由,5、外部网关路由选择协议BGP,在距离向量（DV）协议中，到目的站点的所有与路径相关的信息都集中在“度量”值里。不能很快发现环路。 BGP每个路由更新报文都带有从源站点到目的站点的全部列表。只要AS在列表中出现了2次，即表明路由出现环路。Destination Route 203.154/16 AS143, AS203, AS16888, AS501 128.95.128/17 AS2001, AS4400, AS2323, AS787, AS75 在收到一个路由通告时，外部路由器检查它本身所在的AS是否出现在路径列表中。如果是，则拒绝使用该路径；否则，将本地标识插入到路径中，再进一步发布路由通告。,BGP Routes,A,F,G,E,J,I,H,D,C,B,F丢弃经过自己的路由（I、E来的路径） 解决DV算法的无穷计算问题：发生故障时可选择正确的路由（FBCD为新路由）,假设F使用到D的路径FGCD，F从所有邻接路由器收到的路由： B：“I use BCD” G：“I use GCD” I：“I use IFGCD” E：“I use EFGCD”,×,内部路由与外部路由的配对使用,每个外部路由器都与AS的所有其它外部路由器建立“内部”BGP连接，传播与IGP无关的外部路由信息。,BGP 使 AS 能够实现路由策略: accept traffic from AS20 for delivery to AS30 do not accept traffic for delivery to AS40 AS30 has a preference value of 5 for route decisions AS20 has a preference value of 20,Policy Based Routing,BGP 发言人,每个 AS 选择一个 BGP 路由器作为特权路由器，也称为该自治系统的“BGP 发言人” 。 BGP 的特权路由器之间交换路由信息。 一般说来，两个 BGP 发言人都是通过一个共享网络连接在一起的，而 BGP 发言人往往就是 BGP 边界路由器，但也可以不是 BGP 边界路由器。,BGP 发言人和自治系统 AS 的关系,BGP 发言人,BGP 发言人,BGP 发言人,BGP 发言人,BGP 发言人,AS1,AS3,AS2,AS5,AS4,BGP 交换路由信息,一个 BGP 发言人与其他自治系统中的 BGP 发言人要交换路由信息，就要先建立 TCP 连接，然后在此连接上交换 BGP 报文以建立 BGP 会话(session)，利用 BGP 会话交换路由信息。 使用 TCP 连接能提供可靠的服务，也简化了路由选择协议。 使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此成为对方的邻站或对等站。,自治系统连通图,BGP所交换的网络可达性的信息就是要到达某个网络(用网络前缀表示)所要经过的一系列的自治系统。 BGP 发言人互相交换网络可达性的信息后，各BGP发言人就可找出到达各自治系统的比较好的路由。,AS1,AS6,AS2,AS3,AS5,AS4,AS7,AS8,一个BGP发言人构造出的自治系统连通图，树型结构，没有回路,BGP 发言人交换路径向量,主干网 （AS1）,地区 ISP （AS2）,地区 ISP （AS3）,本地 ISP（AS6） N5,本地 ISP（AS7） N6， N7,自治系统 AS2 的 BGP 发言人通知主干网的 BGP 发言人：“要到达网络 N1, N2, N3 和 N4 可经过 AS2。”,BGP 发言人交换路径向量,主干网 （AS1）,地区 ISP （AS2）,地区 ISP （AS3）,本地 ISP（AS4） N1， N2,本地 ISP（AS5） N3， N4,主干网还可发出通知：“要到达网络 N1, N2，N3 和 N4 可沿路径（AS1, AS2）。”,BGP 发言人交换路径向量,主干网 （AS1）,地区 ISP （AS2）,地区 ISP （AS3）,本地 ISP（AS4） N1， N2,本地 ISP（AS5） N3， N4,主干网还可发出通知：“要到达网络 N5, N6 和 N7 可沿路径（AS1, AS3）。”,BGP-4 共使用四种报文,(1) 打开(Open)报文，用来与相邻的另一个BGP发言人建立关系。 (2) 更新(Update)报文，用来发送某一路由的信息，以及列出要撤消的多条路由。 (3) 保活(Keepalive)报文，用来确认打开报文和周期性地证实邻站关系。 (4) 通知(Notificaton)报文，用来发送检测到的差错。,BGP报文格式,BGP 协议的特点,BGP 协议交换路由信息的结点数量级是自治系统数的量级，这要比这些自治系统中的网络数少很多。 每一个自治系统中 BGP 发言人（或边界路由器）的数目是很少的。这样就使得自治系统之间的路由选择不致过分复杂。 BGP 支持 CIDR，因此 BGP 的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列。 在BGP 刚刚运行时，BGP 的邻站是交换整个的 BGP 路由表。但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销方面都有好处。,在一个路由器中，可同时配置静态路由和一种或多种动态路由，称为多路径路由。它们各自维护的路由表都提供给转发程序，但这些路由表的表项间可能会发生冲突。这种冲突可通过配置各路由表的优先级来解决。通常静态路由具有默认的最高优先级，当其它路由表表项与它矛盾时，均按静态路由转发。 如果优先权最高的路由失败，则使用下一级优先权的路由。,6、路由表项的优先问题,路由优先权排序（从最高到最低）的例子：,（1）添加的静态路由不能被动态路由替代(允许网络管理员规定该路由，而不考虑成本更低的动态路由)； （2）用OSPF获得的路由； （3）用RIP获得的路由； （4）用ICMP重新定向消息获得的路由； （5）用EGP获得的路由； （6）添加的静态路由能够被动态路由替换（即使一条静态成本比一条动态成本低，也允许动态路由始终优先于静态路由）。,