《IP路由协议》PPT课件

蔡开裕副教授kycai国防科大计算机学院603室2003年9月30日,第十章IP路由协议,10.1路由器与路由选择10.2Internet结构10.3基本路由算法10.3.1V-D路由算法10.3.2L-S路由算法10.4IGP：内部网关协议10.4.1RIP协议10.4.2IGRP协议10.4.3OSPF协议10.5外部网关协议EGP10.6IP组播10.7移动IP,10.1路由器与路由选择,路由器(router)是TCP/IP互联网的标准组件，用于实现网络互联的硬件设备。路由器在物理结构上类似于网桥，每台路由器一般都有处理器和内存，对所连接的每个物理网络都有一个单独的接口。路由器的主要工作是接收IP报文，然后查找路由表寻找与目的地址相匹配的项并将IP数据报发送到下一个路由器或目的主机。,10.1.1路由器,路由器,网络互联,多协议路由器,路由器结构,交换机,Crossbar交换阵列,高速路由器（1）,高速路由器（2）,CrossbarSwitch,10.1.2路由选择,直接路由（直接传送）在同一个物理网络中的两个站点(主机-主机、主机-路由器或路由器-路由器)之间发送IP数据报时，源站点将IP数据报通过物理网络（局域网或广域网）直接发送给目的站点。间接路由（要经过中间路由器）源站点与目的站点相隔1个或多个物理网络，IP数据报从源站点到达目的站点要穿过1个或多个中间路由器，源站点在发送IP数据报时只是将其首先发给某个路由器。,路由选择实例,R4的路由表（1）,R4的路由表（2）,R4的路由表（3）,/32：特定主机路由/0：默认路由,路由表表项的分类,特定主机路由前缀长度为32比特的路由表表项网络前缀路由是前缀长度为131比特的路由表表项最长前缀匹配/CIDR引起的多个匹配项重叠缺省路由前缀长度为0比特的路由。,网络路由实例,主机1的路由表,路由器1的路由表,路由器2的路由表（练习）,路由器1的转发表,R4的转发表（部分）,ARP协议,代理ARP,RARP协议,RARP协议用于解决给无盘工作站IP地址分配的问题，它要求网络上必须配置RARP服务器。引导协议BOOTP用于动态分配IP地址和引导远程工作站（BOOTP协议使用了TFTP协议）。动态主机配置协议DHCP能够自动分配IP地址给客户计算机并对其进行配置(内容包括IP地址、子网掩码、缺省网关等等)。它能够减轻用户配置TCP/IP网络的负担。,ARP/RARP报文的格式,路由器的路由规则,如果存在特定主机路由，选择特定主机路由；如果存在网络前缀路由，选择最长前缀匹配路由；如果存在缺省路由，选择缺省路由；否则，宣告路由失败，向源主机发送ICMP报文，报告路由错误；,主机的路由规则,我们假设主机只有一个接口且转发表中只有一个缺省路由器，则该主机的路由规则是：如果IP报文目的地址与源地址的网络号相同（属于同一个物理网络），则直接传送（通过ARP协议获取目的主机的物理地址）；否则，将IP报文发给缺省路由器（也要通过ARP协议获取缺省路由器的物理地址）；,ICMP协议,为了让路由器可以向源主机报告差错情况，TCP/IP协议族中专门引入一个用于传输差错及控制报文的协议，即Internet控制报文协议ICMP。ICMP是IP协议的一部分，在每个IP协议软件中都包含了ICMP协议的实现模块。ICMP报文通过IP协议来传输，当路由器要发送ICMP报文时，它会创建一个IP数据报并将ICMP报文封装到IP报文的数据区中，然后这个数据报象普通的IP报文一样通过Internet。,ICMP报文的封装,ICMP报文的类型,ICMP差错报文用于路由器或目的主机向源主机报告出错情况。ICMP控制报文用于拥塞控制的源抑制报文和用于路由选择的重定向报文。ICMP请求/应答报文用于获得某些有关网络状态的信息，以便进行网络故障诊断和控制。,路由表是如何生成的？,手工配置静态路由一般用于主机结点；主机路由：目的结点与源结点在同一个物理网络，直接传送；否则，采用缺省路由。动态生成，可以通过接收ICMP重定向报文主要用于主机的路由表更新动态生成，通过路由协议自动更新路由器的路由表更新,10.2Internet的结构,InternetStructure（90年代）,InternetStructure（Today）,10.3.1V-D路由算法,V-D算法是让每个路由器维护一张距离向量表，向量表的每一项由两部分组成，输出线路和到达目的地所需要的路径代价。路径代价的度量单位可以是时间延迟、物理距离或其它参数。在V-D算法中，必须假定每个路由器都知道到它相邻路由器的距离。如果度量标准是跳步数，则距离为1；如果度量标准是延迟，则路由器可以通过发送一个回响(echo)报文来测出它到相邻路由器的延迟。,V-D算法的实例,JA=8JI=10JH=12JK=6,慢收敛问题,计算至无穷问题当网络出现故障后，有可能出现路径环，而要打破路径环，则需要花费比较长的时间；好信息传播快，坏消息传播慢；,慢收敛问题,分割范围法,到X的距离并不向真正通向X的邻居节点报告；对于前面的例子，由于CA要经过CB线路，因而C告诉B，它到A的hop数为infinity(C送给B的路由表中，CA这一项为infinity)，但C会告诉D它到A的实际hop数；同样的道理，D告诉C它到A的hop数为infinity，但它会告诉E它到A的实际hop数；C告诉B它到A的hop数这一信息本身就是通过B的，没有实际意义。,保持法（1）,基本原理当路由器得知某节点不可达的一定时间内(HoldingDown时间，RIP规定为60秒)，路由器不再接受关于该节点的任何可达性信息，而任坚持采用原来(在进入HoldingDown之前)认为最好的路径。,保持法（2）,目的给路径崩溃信息以充分的传播时间，使它尽可能赶在路径环形成之前传播出去，以防止出现路径环。存在的问题HoldingDown时间过长，导致线路恢复后不能尽快进入正常的交换HoldingDown时间过短，则可能在holdingdown后重新出现路径环,10.3.2L-S算法,解决V-D算法的两个问题V-D算法一般只考虑链路的时延(latency)；不考虑链路的带宽(bandwidth)；更不考虑链路的负载(load)V-D算法收敛慢计算到无穷问题,工作原理（1）,1）发现邻居结点，建立邻居关系HELLO分组2）测量链路开销（cost）以链路延迟（delay）作为开销度量，既考虑了线路时延（latency），又考虑了链路的带宽（bandwidth）；ECHO报文：round-triptime/2当测量链路开销时如果考虑链路负载，可能会引起路由振荡问题；,路由振荡问题,工作原理（2）,3）构造链路-状态报文L-S报文的内容路由器表识：RouterID序号：SequenceNumber年龄：Age邻居列表：Neighborsdelaymetriclist何时构造L-S报文周期性当链路状态发生变化时,L-S报文,工作原理（3）,4）可靠地广播L-S报文（ReliableFlooding）措施之一接收并转发最新的L-SpacketSequenceNumber字段措施之二删除掉网络中的旧的L-S报文Ages字段措施之三确认和重传,路由器B的L-S数据库,工作步骤（4）,5）计算最短路径路由器接收到所有的L-S报文后，可以重新构造网络拓扑图（带权的边），这样路由器就可以利用Dijktra算法计算出该路由器到达所有其它路由器的最短路径（ShortestPath），然后更新路由表。,L-S路由算法的特点,L-S路由算法的优点算法具有收敛性，可以对网络拓扑结构的改变、路由器或链路发生故障作出快速反应。L-S路由算法对路由器的要求路由器存储的信息量比较大（所有的L-S报文），带来路由算法的可扩展性问题假设一个AS内有n个Router，每个Router有k条链路；则每个Router的存储空间为O(kn)数量级；路由器计算最短路径的时间开销比较大Dijkstra算法的复杂度（O(n2)）,V-D算法和L-S算法的比较（1）,V-D算法每个路由器只与邻居路由器通信（邻居之间相互交换V-D向量表），但邻居路由器把所知道的全部信息（到所有结点的距离）都告诉它。L-S算法每个路由器都与其它路由器通信（L-S报文的广播），但每个路由器只告诉其它路由器它确切知道的信息（即与其直接相连的邻居的链路状态L-S报文）。,V-D算法和L-S算法的比较（2）,10.4IGP协议,RIP协议IGRP协议OSPF协议,10.4.1RIP协议（1）,RIP协议是基于V-D算法的RIP协议最初是由施乐公司的帕洛阿托研究中心PARC在70年代设计的，在此基础上，PARC和加州大学共同开发了routed程序，该程序使用RIP协议并与4BSDUnix系统一起推出。RIP协议最初用于ARPANET，目前主要用在Internet、DECnet以及Novell网络中。,RIP协议（2）,RIP协议的报文有两类：更新报文和请求报文。更新报文用于路由表（V-D表）的分派。请求报文被用于路由器发现网上其它运行RIP协议的路由器。运行RIP协议的路由器每隔30秒就向它的邻居路由器广播其路由表。RIP协议的路由度量值是到达目的地的跳步数。RIP协议的最大可用跳步数为15，跳步数16意味着无效(或无穷大度量值)路由。,10.4.2IGRP协议,IGRP(InternetGatewayRoutingProtocol)是由Cisco公司开发，基于V-D路由算法的IGP协议。IGRP协议在路径代价度量时考虑了链路的各种特性(如时延、带宽、负载或可靠性等)，而且路由更新的时间间隔是90秒(RIP协议是30秒)，并且它也具有易配置的特点，同时增加了其它一些功能。增强型IGRP协议(EIGRP)。,10.4.3OSPF协议,OSPF(OpenShortestPathFirst)协议基于L-S路由算法。使用OSPF协议的路由器维持一个有关网络拓扑结构的数据库。该数据库存放着网络中每一个路由器上所有链路的状态，每个路由器以此数据库为基础利用Dijkstra算法算出到网络中各目的结点的最短路径，并将最短路径写入路由表。路由器将链路状态更新信息广播给网络中的所有其它路由器，从而更新它们的数据库，重新计算最短路径。,10.5外部网关协议EGP,外部网关协议EGP和内部网关协议IGP是完全不同，原因是它们的目的不同。IGP的主要目的是要维持AS内部所有路由器之间的最短路经Metric-Based；EGP的主要目的是维持AS之间的“网络可达性”信息，也就是说，外部网关协议EGP是用于两个自治系统AS之间的关于“网络可达性”路由信息的交换。,Internet路由结构（1）,Internet路由结构（2）,自治系统AS,一个管理上独立与其他AS的网络独立管理，独立选择IGP协议，构成一个路由选择域（intradomain）；每个AS有一个唯一编号；每个AS有至少1个或多个边界路由器（borderrouter）；AS内部的路由器通过缺省路由（defaultroute）将目标地址标识为AS外部的报文首先路由到边界路由器；,Internet路由结构（3）,AS分类,支线AS（stubAS）：与另外一个AS只有一个连接，这样的AS只传送局部通信量（localtraffic）；多连接AS（mutlihomedAS）：与多个AS有连接，但是拒绝传送中转通信量（transittraffic）；中转AS（transitAS）：与多个AS有连接，并能传送局部通信量和中转通信量；,EGP路由例子,EGP路由信息通告,BGP-4（BorderGatewayProtocol）,目标支持多主干因特网，允许非树型结构的互联网络；支持CIDR路由，减缓了B类地址耗尽问题，同时克服路由表爆炸问题；PathVectorPolicy-Based难点可扩展性核心路由器的路由表项大约130KAS的自治性，导致路由策略非常复杂AS路由器之间的信任度安全问题,BGP实例（1）,BGP实例（2）,AS2的边界路由器可以向AS1的主干路由器通知关于AS4(网络号为128.96和192.4.153)和AS5(网络号为192.4.32和192.4.3)的可达性信息（通过AS2）AS1的主干路由器可以向外通知关于AS4(网络号为128.96和192.4.153)和AS5(网络号为192.4.32和192.4.3)的可达性信息（通过AS1和AS2）路由器可以撤销以前通知的路径,如何解决因特网规模的可扩展性？,如何解决路由选择的可扩展性？如何找到减少路由协议中携带和路由器的路由表中存储的网络号数目（路由表项）的方法？如何提高IP地址的利用率？如何确保IP地址（主要是B类地址）不会消耗的太快？,路由选择的可扩展性？,层次路由域内（inteadomain）路由：IGP协议域内路由的复杂性取决于AS内的网络数目域间（inteadomain）路由：EGP/BGP协议域间路由的复杂性取决于因特网的AS数目层次地址IP地址分为网络号+主机号路由器采用网络前缀路由，减少路由器的路由表项,层次路由/地址的缺点,层次路由的缺点在AS内的路径是最优路径，但AS之间的路径不一定是最优路经；层次地址的缺点地址分配的低效率，如：只有2个主机的C类地址(2/254=0.78%)，只有256台主机的B类地址256/65534=0.39%),问题的引发（1）,单位的网络可扩展性问题？象国防科大校园网：每个学院已经有各自的网络存在，要将这些网络互联起来怎么办？一种解决办法是用LAN交换机（如Ethernet网交换机或ATM交换机或FDDI集中器）将这些网络互联起来；假如整个单位的网络接口数目没有超过254，可以分配一个C类地址；如果超过254台，只能申请一个B类地址；,问题的引发（2）,另一种办法就是用路由器将这些网络连接起来用路由器来进行网络互联有什么优点？问题国防科大得申请多个C类地址外部路由器的路由表中必须包含多条指向国防科大网络的路由解决办法子网（subnet）技术,子网技术（subnet）,在IP地址，引入另一个地址/路由层次：子网（subnet）；把具有相同网络号的IP地址分配给一个单位的几个不同的物理网络；子网屏蔽（subnetmask）将IP地址的主机号划分为不同的子网；子网对网络外部（主干路由器）是不可见的，但在网络内部要采用子网路由；因此在因特网上不同的路由器看到的路由信息是不一样的；,子网技术的特点,可以减少广播通信量、增加网络的可管理性和安全性将不同的物理网络通过路由器（而不是通过LAN交换机）彼此连接，这样减少广播通信量；同时便于网络管理，也可以提高网络的安全性；可以提高B类IP地址的利用率少分配C类地址，多分配B类地址，以解决路由表爆炸问题；但同时提高了B类地址的利用率；子网技术主要是针对B类地址，但目前该技术也已被广泛应用于C类地址,子网实例（1）,子网技术如何解决可扩展性？,当新增一个物理网络时，我们不必用掉一个完整的B类或C类地址（如果没有子网技术支持，我们做不到这一点），从而使Internet地址的利用率更高；有利于路由信息的聚合，即多个物理网络只需要1条路由信息（对外部路由器而言）；,子网实例（2）,R1的路由表（内部路由）,子网号子网掩码下一跳28接口02828接口1R2,CIDR,由于子网技术的使用，使得B类地址的消耗速度过快；多分配C类地址，以解决B类地址耗尽问题；但C类地址的使用会引起路由表爆炸问题；假设一个AS被分配了16个C地址，则在主干网路由器的路由表中必须有关该AS的16条记录，即使到这些网络的路径相同也必须如此；如果我们给这个AS分配一个B类地址，同样的路由信息在路由表中只需要1条记录，然而地址分配效率则变为16*254/65534=6%。,超网技术（1）,如何在较少路由表项目和提高IP地址利用率之间找到平衡点？不采用层次地址，而引入以无类域间路由CIDR（ClasslessInter-DomainRouting）为基础的无类地址。CIDR还可以支持将网络地址中相邻的小块合并到较大的一块中（聚合路由），因此有时又称CIDR为超网（supernetting）技术。,超网技术,将剩下的C类地址以连续的地址块方式进行分配；限制块的大小为2的幂次方；使用一个位掩码(CIDRmask)，即来标识块大小；路由协议必须支持CIDR路由，即最长前缀匹配路由；,CIDR实例,我们使用假设有16个C类地址的AS作为例子，我们将连续的C类地址（192.4.16192.4.31）分配给该AS；我们可以观察到所有这些地址的高20位是一样的（11000000000001000001）；这样，我们就有效地构造了一个20位的网络号，它所能支持的主机数目介于B类网络和C类网络之间；这样既提高了地址的利用率，又有效地减少路由表表项的数量。,10.5IP组播,多媒体多终端交互应用电视会议，CSCW，远程教育特点：组成员的数目基本不变数据分配型应用Internet广播、电子出版、Newsgroup特点：组成员的数目变化较大,组播的优点,可以节省带宽IP组播是把要组播的IP报文发送1份或多份给组播地址，而不是为每个接收方单独发送一份拷贝；发送主机不必了解接收方每台计算机的IP地址，它只需了解组播地址即可；,组播地址和IGMP协议,IP组播地址D类地址（高位为1110）特殊组播地址组播管理协议IGMP组的加入和退出：主机通过IGMP协议向Router发送join和leave消息，加入或退出某组。,10.5.1组播协议,网中的一个定位点计算通向所有接收方的生成树(SpanningTree)，这个定位点可以是发送方、汇合点(RendezvousPoint)或核(Core)，由于这个定位点唯一标识了一棵生成树，组播路由器可以利用它来计算一个给定分组的转发方向。,组播协议分类,最短路径树(ShortestPathTree)的协议（又称源特定路由Source-Specificrouting)距离-向量组播协议DVMRP组播开发式最短路径优先协议MOSPF密集式PIM(Dense-modeProtocolIndependentMulticast)共享树(SharedTree)的协议(又称基于核心树Core-BasedTree)稀疏式PIM(Spares-modeProtocolIndependentMulticast),最短路径树协议,共享树协议,10.6移动IP路由,注册过程（1）,每个外地代理定期广播报文，通告自己的地址和状态。新进入该区域的移动主机等待接收