第十章 IP路由协议

1、1第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy蔡开裕蔡开裕 副教授副教授国防科大计算机学院国防科大计算机学院603室室2003年年9月月30日日2第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy第十章第十章 IP路由协议路由协议10.1 路由器与路由选择路由器与路由选择10.2 Internet结构结构10.3 基本路由算法基本路由算法10.3.1 V-D路由算法路由算法10.3.2 L-S路由算法路由算法10.4 IGP：内部网关协议：内部网关协

2、议10.4.1 RIP协议协议10.4.2 IGRP协议协议10.4.3 OSPF协议协议10.5 外部网关协议外部网关协议EGP10.6 IP组播组播10.7 移动移动IP3第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.1 路由器与路由选择路由器与路由选择 路由器路由器(router)是是TCP/IP互联网的标准组件，用互联网的标准组件，用于实现网络互联的硬件设备。路由器在物理结构于实现网络互联的硬件设备。路由器在物理结构上类似于网桥，每台路由器一般都有处理器和内上类似于网桥，每台路由器一般都有处理器和内存，对所

3、连接的每个物理网络都有一个单独的接存，对所连接的每个物理网络都有一个单独的接口。口。 路由器的主要工作是接收路由器的主要工作是接收IP报文，然后查找路由报文，然后查找路由表寻找与目的地址相匹配的项并将表寻找与目的地址相匹配的项并将IP数据报发送数据报发送到下一个路由器或目的主机。到下一个路由器或目的主机。 4第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.1.1路由器路由器局域网广域网路由器局域网5第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy

4、路由器路由器 主机 A主机 B路由器应用程序TCP 或 UDPIP物理物理接口 AIP 接口 A 接口 B应用程序TCP 或 UDPIP物理物理接口 B网络 A网络 B6第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy网络互联网络互联7第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy多协议路由器多协议路由器8第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由器结构路由器结构CPU

5、Main memoryI/O busInterface 1Interface 2Interface 39第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy交换机交换机InputportInputportInputportInputportOutputportOutputportOutputportOutputportFabric10第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyCrossbar交换阵列交换阵列11第十章第十章 IP路由协议路由协议 Ne

6、tworking Networking techno;ogytechno;ogy高速路由器（高速路由器（1）Line card(forwarding buffering)Line card(forwarding buffering)Line card(forwarding buffering)Line card(forwarding buffering)RoutingCPUBuffermemoryRouting softwarew/ router OS12第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy高速路由器（高速路由

7、器（2）CrossbarSwitchPCCPUMEMNI withuP.NI withuPPCCPUMEMNI withuP.NI withuPPCCPUMEMNI withuP.NI withuPPCCPUMEMNI withuP.NI withuPPCCPUMEMNI withuP.NI withuPPCCPUMEMNI withuP.NI withuP13第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.1.2 路由选择路由选择 直接路由（直接传送）直接路由（直接传送）l在同一个物理网络中的两个站点在同一个物理网

8、络中的两个站点(主机主机-主机、主机、主机主机-路由器或路由器路由器或路由器-路由器路由器)之间发送之间发送IP数据数据报时，源站点将报时，源站点将IP数据报通过物理网络（局域数据报通过物理网络（局域网或广域网）直接发送给目的站点。网或广域网）直接发送给目的站点。 间接路由（要经过中间路由器）间接路由（要经过中间路由器）l源站点与目的站点相隔源站点与目的站点相隔1个或多个物理网络，个或多个物理网络，IP数据报从源站点到达目的站点要穿过数据报从源站点到达目的站点要穿过1个或个或多个中间路由器，源站点在发送多个中间路由器，源站点在发送IP数据报时只数据报时只是将其首先发给某个路由器。是将其首先发给

9、某个路由器。14第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由选择实例路由选择实例15第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyR4的路由表（的路由表（1）目的主机所在网络目的主机所在网络 下一下一跳跳地址地址 10（） 20（） 直接传送 30（） 直接传送 40（） 直接传送 50（） 直接传送 16第十章第十章 IP路由协议路由协议 Ne

10、tworking Networking techno;ogytechno;ogyR4的路由表（的路由表（2）目的地址目的地址/ /前缀长度前缀长度 下一跳地址下一跳地址 端口端口 /8（10） R2（） a /8（20） 直接传送 a /8（30） 直接传送 b /8（40） 直接传送 c /8（50） 直接传送 d 17第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyR4的路由表（的路由表（3）/32：特定主机

11、路由/0： 默认路由目的地址目的地址/ /前缀长度前缀长度 下一跳地址下一跳地址 端口端口 /32 直接传送 a /8（10） R2（） a /8（20） 直接传送 a /8（30） 直接传送 b /8（40） 直接传送 c /8（50） 直接传送 d /0 R6（） e 18第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由表表项的分类路由表表项的分类 特定主机路由

12、特定主机路由l前缀长度为前缀长度为32比特的路由表表项比特的路由表表项 网络前缀路由网络前缀路由l是前缀长度为是前缀长度为131比特的路由表表项比特的路由表表项l最长前缀匹配最长前缀匹配/CIDR引起的多个匹配项重叠引起的多个匹配项重叠 缺省路由缺省路由l前缀长度为前缀长度为0比特的路由。比特的路由。19第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy网络路由实例网络路由实例20第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy主机主机1的路由表的路由表

13、目的地址目的地址/ /前缀前缀长度长度 下一跳地址下一跳地址 端口号端口号 /32 直接传送 a /24 直接传送 a /0 a 21第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由器路由器1的路由表的路由表目的地址目的地址/ /前缀长度前缀长度 下一跳地址下一跳地址 端口端口 /24 c /24 直接传送 c /24 直接传送 a 2

14、2第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由器路由器2的路由表（练习）的路由表（练习）目的地址目的地址/ /前缀长度前缀长度 下一跳地址下一跳地址 端口端口 /24 c /24 直接传送 b /24 直接传送 c 23第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由器路由器1的转发表的转发表目的地址目的地址/ /前缀长度前缀长度 下一跳地址下

15、一跳地址 端口端口 MACMAC 地址地址 /24 c F3 /24 直接传送 c F4 /24 直接传送 a E1 24第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyR4的转发表（部分）的转发表（部分）目的地址目的地址/ /前缀长度前缀长度 下一跳地址下一跳地址 端口号端口号 MACMAC 地址地址 /32 直接传送 b E2 /8 R2（） b E1 /24

16、 直接传送 b E2 /0 直接传送 e 拨号地址 25第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyARP协议协议 以太网主机 1主机 2IP 地址：物理地址：E1IP 地址：物理地址：E226第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy代理代理ARP27第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyRARP协

17、议协议 RARP协议用于解决给无盘工作站协议用于解决给无盘工作站IP地址分配的问地址分配的问题，它要求网络上必须配置题，它要求网络上必须配置RARP服务器服务器 。 引导协议引导协议BOOTP用于动态分配用于动态分配IP地址和引导远程工地址和引导远程工作站（作站（ BOOTP协议使用了协议使用了TFTP协议）。协议）。 动态主机配置协议动态主机配置协议DHCP能够自动分配能够自动分配IP地址给客地址给客户计算机并对其进行配置户计算机并对其进行配置(内容包括内容包括IP地址、子网掩地址、子网掩码、缺省网关等等码、缺省网关等等)。它能够减轻用户配置。它能够减轻用户配置TCP/IP网网络的负担。络的

18、负担。28第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyARP/RARP 报文的格式报文的格式 硬件类型协议类型硬件地址长度协议地址长度操作发送者硬件地址(03 字节)发送者硬件地址(45 字节)发送者 IP 地址(01 字节)发送者 IP 地址(23 字节)目的硬件地址(01 字节)目的硬件地址(25 字节)目的 IP 地址(03 字节)29第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由器的路由规则路由器的路由规则1.如果存在特定主机路由，选

19、择特定主机路由；如果存在特定主机路由，选择特定主机路由；2.如果存在网络前缀路由，选择如果存在网络前缀路由，选择最长前缀匹配最长前缀匹配路路由；由；3.如果存在缺省路由，选择缺省路由；如果存在缺省路由，选择缺省路由；4.否则，宣告路由失败，向源主机发送否则，宣告路由失败，向源主机发送ICMP报文报文，报告路由错误；，报告路由错误；30第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy主机的路由规则主机的路由规则我们假设主机只有一个接口且转发表中我们假设主机只有一个接口且转发表中只有一个缺省路由器，则该主机的路由只有一个缺省路

20、由器，则该主机的路由规则是：规则是：l如果如果IP报文目的地址与源地址的网络号相同报文目的地址与源地址的网络号相同（属于同一个物理网络），则直接传送（通（属于同一个物理网络），则直接传送（通过过ARP协议获取目的主机的物理地址）；协议获取目的主机的物理地址）；l否则，将否则，将IP报文发给缺省路由器（也要通过报文发给缺省路由器（也要通过ARP协议获取缺省路由器的物理地址）；协议获取缺省路由器的物理地址）；31第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyICMP协议协议 为了让路由器可以向源主机报告差错情况，为了让路由器

21、可以向源主机报告差错情况，TCP/IP协议协议族中专门引入一个用于传输差错及控制报文的协议，即族中专门引入一个用于传输差错及控制报文的协议，即Internet控制报文协议控制报文协议ICMP。 ICMP是是IP协议的一部分，在每个协议的一部分，在每个IP协议软件中都包含了协议软件中都包含了ICMP协议的实现模块。协议的实现模块。 ICMP报文通过报文通过IP协议来传输，当路由器要发送协议来传输，当路由器要发送ICMP报报文时，它会创建一个文时，它会创建一个IP数据报并将数据报并将ICMP报文封装到报文封装到IP报报文的数据区中，然后这个数据报象普通的文的数据区中，然后这个数据报象普通的IP报文

22、一样通过报文一样通过Internet。32第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyICMP报文的封装报文的封装 IP 头部IP 数据区ICMP 头部ICMP 数据 帧头帧数据区33第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyICMP报文的类型报文的类型 ICMP差错报文差错报文l用于路由器或目的主机向源主机报告出错情况。用于路由器或目的主机向源主机报告出错情况。 ICMP控制报文控制报文l用于拥塞控制的源抑制报文和用于路由选择的重定向报用于

23、拥塞控制的源抑制报文和用于路由选择的重定向报文。文。 ICMP请求请求/应答报文应答报文l用于获得某些有关网络状态的信息，以便进行网络故障用于获得某些有关网络状态的信息，以便进行网络故障诊断和控制。诊断和控制。34第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由表是如何生成的？路由表是如何生成的？ 手工配置手工配置静态路由静态路由l一般用于主机结点；一般用于主机结点；l主机路由：目的结点与源结点在同一个物理网络，直主机路由：目的结点与源结点在同一个物理网络，直接传送；否则，采用缺省路由。接传送；否则，采用缺省路由。 动

24、态生成，可以通过接收动态生成，可以通过接收ICMP重定向报文重定向报文l主要用于主机的路由表更新主要用于主机的路由表更新 动态生成，通过路由协议自动更新动态生成，通过路由协议自动更新l路由器的路由表更新路由器的路由表更新35第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.2 Internet的结构的结构 RRRRR核心网关核心主干网RASASASEGP 协议RIGP 协议36第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyInternet Str

25、ucture（90年代）年代）NSFNET backboneStanfordBARRNETregionalBerkeleyPARCNCARUAUNMWestnetregionalUNLKUISUMidNetregional37第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyInternet Structure（Today）Backbone service providerPeeringpointPeeringpointLarge corporationLarge corporationSmallcorporation“Co

26、nsumer ” ISP“Consumer” ISP“Consumer” ISP38第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.3.1 V-D路由算法路由算法 V-D算法是让每个路由器维护一张距离向量表，向算法是让每个路由器维护一张距离向量表，向量表的每一项由两部分组成，输出线路和到达目的量表的每一项由两部分组成，输出线路和到达目的地所需要的路径代价。路径代价的度量单位可以是地所需要的路径代价。路径代价的度量单位可以是时间延迟、物理距离或其它参数。时间延迟、物理距离或其它参数。 在在V-D算法中，必须假定每个路由

27、器都知道到它相算法中，必须假定每个路由器都知道到它相邻路由器的邻路由器的距离距离。如果度量标准是跳步数，则距。如果度量标准是跳步数，则距离为离为1；如果度量标准是延迟，则路由器可以通过；如果度量标准是延迟，则路由器可以通过发送一个发送一个回响回响(echo)报文来测出它到相邻路由器报文来测出它到相邻路由器的延迟。的延迟。39第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyV-D算法的实例算法的实例JA=8 JI=10 JH=12 JK=6 40第十章第十章 IP路由协议路由协议 Networking Networking

28、techno;ogytechno;ogy慢收敛问题慢收敛问题 计算至无穷问题计算至无穷问题l当网络出现故障后，有可能出现路径环，而要当网络出现故障后，有可能出现路径环，而要打破路径环，则需要花费比较长的时间；打破路径环，则需要花费比较长的时间；l好信息传播快，坏消息传播慢；好信息传播快，坏消息传播慢；41第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy慢收敛问题慢收敛问题42第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy分割范围法分割范围法 到到X的

29、距离并不向真正通向的距离并不向真正通向X的邻居节点报告；的邻居节点报告； 对于前面的例子，由于对于前面的例子，由于CA要经过要经过CB线路，因而线路，因而C告诉告诉B，它到，它到A的的hop数为数为infinity(C送给送给B的路由的路由表中，表中，C A这一项为这一项为infinity)，但，但C会告诉会告诉D它到它到A的实际的实际hop数；同样的道理，数；同样的道理，D告诉告诉C它到它到A的的hop数为数为infinity，但它会告诉，但它会告诉E它到它到A的实际的实际hop数；数； C告诉告诉B它到它到A的的hop数这一信息本身就是通过数这一信息本身就是通过B的的，没有实际意义。，没有

30、实际意义。43第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy保持保持法法（1） 基本原理基本原理l当路由器得知某节点不可达的一定时间内当路由器得知某节点不可达的一定时间内(Holding Down时间，时间，RIP规定为规定为60秒秒)，路由，路由器不再接受关于该节点的任何可达性信息，而器不再接受关于该节点的任何可达性信息，而任坚持采用原来任坚持采用原来(在进入在进入Holding Down之前之前)认认为最好的路径。为最好的路径。44第十章第十章 IP路由协议路由协议 Networking Networking tec

31、hno;ogytechno;ogy保持保持法法（2） 目的目的l给路径崩溃信息以充分的传播时间，使它尽可给路径崩溃信息以充分的传播时间，使它尽可能赶在路径环形成之前传播出去，以防止出现能赶在路径环形成之前传播出去，以防止出现路径环。路径环。 存在的问题存在的问题lHolding Down时间时间过长，导致线路恢复后不能过长，导致线路恢复后不能尽快进入正常的交换尽快进入正常的交换lHolding Down时间时间过短，则可能在过短，则可能在holding down后重新出现路径环后重新出现路径环45第十章第十章 IP路由协议路由协议 Networking Networking techno;og

32、ytechno;ogy10.3.2 L-S算法算法 解决解决V-D算法的算法的两个问题两个问题lV-D算法算法一般只考虑链路的时延一般只考虑链路的时延(latency)；不；不考虑考虑链路的带宽链路的带宽(bandwidth)；更不考虑链路的；更不考虑链路的负载负载(load)lV-D算法收敛慢算法收敛慢计算到无穷问题计算到无穷问题46第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy工作原理（工作原理（1）1）发现邻居结点，建立邻居关系）发现邻居结点，建立邻居关系lHELLO 分组分组2）测量链）测量链路开销（路开销（co

33、st）l以链路延迟（以链路延迟（delay）作为开销度量，既考）作为开销度量，既考虑了线路时延（虑了线路时延（latency），又考虑了链路的），又考虑了链路的带宽（带宽（bandwidth）；）；lECHO报文：报文：round-trip time/2l当测量链路开销时如果考虑链路负载，可能当测量链路开销时如果考虑链路负载，可能会引起路由振荡问题；会引起路由振荡问题；47第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由振荡问题路由振荡问题 CD 线路AB 线路甲地乙地48第十章第十章 IP路由协议路由协议 Netwo

34、rking Networking techno;ogytechno;ogy工作原理（工作原理（2）3）构造链路）构造链路-状态报文状态报文lL-S报文的报文的内容内容u路由器表识：路由器表识：Router IDu序号：序号：Sequence Numberu年龄：年龄：Ageu邻居列表：邻居列表：Neighbors delay metric listl何时构造何时构造L-S报文报文u周期性周期性u当链路状态发生变化时当链路状态发生变化时49第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyL-S报文报文50第十章第十章 IP路

35、由协议路由协议 Networking Networking techno;ogytechno;ogy工作原理（工作原理（3）4）可靠地）可靠地广播广播L-S报文（报文（Reliable Flooding）l措施之措施之一一u接收并转发最新的接收并转发最新的L-S packetSequence Number字段字段l措施之二措施之二u删除掉网络中的旧的删除掉网络中的旧的L-S报文报文Ages字段字段l措施措施之之三三u确认和重传确认和重传51第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由器路由器B的的L-S数据库数据库

36、52第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy工作步骤（工作步骤（4）5）计算最短路径）计算最短路径l路由器路由器接收到所有的接收到所有的L-S报文报文后，可以重新构后，可以重新构造网络拓扑图（带权的边），这样路由器就可造网络拓扑图（带权的边），这样路由器就可以利用以利用Dijktra算法计算出该路由器到达所有其算法计算出该路由器到达所有其它路由器的最短路径（它路由器的最短路径（Shortest Path），然后），然后更新路由表。更新路由表。53第十章第十章 IP路由协议路由协议 Networking Networ

37、king techno;ogytechno;ogyL-S路由路由算法的特点算法的特点 L-S路由路由算法的优点算法的优点l算法具有收敛性，可以对网络拓扑结构的改变、路由算法具有收敛性，可以对网络拓扑结构的改变、路由器或链路发生故障作出快速反应。器或链路发生故障作出快速反应。 L-S路由路由算法对路由器的要求算法对路由器的要求l路由器存储的信息量比较大（所有的路由器存储的信息量比较大（所有的L-S报文报文），带来），带来路由算法的可扩展性问题路由算法的可扩展性问题u假设一个假设一个AS内有内有n个个Router，每个每个Router有有k条链条链路；路；则每个则每个Router的存储空间为的存储

38、空间为O(kn)数量级；数量级；l路由器计算最短路径的时间开销比较大路由器计算最短路径的时间开销比较大uDijkstra算法的复杂度（算法的复杂度（O(n2) ）54第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyV-D算法和算法和L-S算法的比较（算法的比较（1） V-D算法算法l每个路由器只与邻居路由器通信（邻居之间相互交换每个路由器只与邻居路由器通信（邻居之间相互交换V-D向量表），但邻居路由器把所知道的全部信息（向量表），但邻居路由器把所知道的全部信息（到所有结点的距离）都告诉它。到所有结点的距离）都告诉它。 L-

39、S算法算法l每个路由器都与其它路由器通信（每个路由器都与其它路由器通信（L-S报文的广播），报文的广播），但每个路由器只告诉其它路由器它确切知道的信息（但每个路由器只告诉其它路由器它确切知道的信息（即与其直接相连的邻居的链路状态即与其直接相连的邻居的链路状态L-S报文）。报文）。55第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyV-D算法和算法和L-S算法的比较（算法的比较（2）V-D 算法算法 L-S 算法算法 不知道整个网络的拓扑结构 知道整个网络的拓扑结构 收敛速度慢 收敛速度快 在邻居路由器提供的路由信息基础上

40、计算新路由 根据网络拓扑结构 计算新路由 V-D 表只发给邻居路由器 L-S 报文发给所有的路由器 56第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.4 IGP协议协议 RIP协议协议 IGRP协议协议 OSPF协议协议57第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.4.1 RIP协议（协议（1） RIP协议是基于协议是基于V-D算法的算法的 RIP协议最初是由施乐公司的帕洛阿托研究中心协议最初是由施乐公司的帕洛阿托研究中心PARC在

41、在70年代设计的，在此基础上，年代设计的，在此基础上，PARC和加州大学共和加州大学共同开发了同开发了routed程序，该程序使用程序，该程序使用RIP协议并与协议并与4BSD Unix系统一起推出。系统一起推出。 RIP协议最初用于协议最初用于ARPANET，目前主要用在，目前主要用在Internet、DECnet以及以及Novell网络中。网络中。58第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyRIP协议（协议（2） RIP协议的报文有两类：更新报文和请求报文。协议的报文有两类：更新报文和请求报文。l更新报文用于路

42、由表（更新报文用于路由表（V-D表）的分派。表）的分派。l请求报文被用于路由器发现网上其它运行请求报文被用于路由器发现网上其它运行RIP协议的协议的路由器。路由器。 运行运行RIP协议的路由器每隔协议的路由器每隔30秒就向它的邻居路秒就向它的邻居路由器广播其路由表。由器广播其路由表。 RIP协议的路由度量值是到达目的地的跳步数。协议的路由度量值是到达目的地的跳步数。RIP协议的最大可用跳步数为协议的最大可用跳步数为15，跳步数，跳步数16意味意味着无效着无效(或无穷大度量值或无穷大度量值)路由。路由。59第十章第十章 IP路由协议路由协议 Networking Networking techn

43、o;ogytechno;ogy10.4.2 IGRP协议协议 IGRP(Internet Gateway Routing Protocol)是由是由Cisco公司开发，基于公司开发，基于V-D路由算法的路由算法的IGP协议。协议。 IGRP协议协议在路径代价度量时考虑了链路的各种特在路径代价度量时考虑了链路的各种特性性(如时延、带宽、负载或可靠性等如时延、带宽、负载或可靠性等)，而且路由更，而且路由更新的时间间隔是新的时间间隔是90秒秒(RIP协议是协议是30秒秒)，并且它也，并且它也具有易配置的特点，同时增加了其它一些功能。具有易配置的特点，同时增加了其它一些功能。 增强型增强型IGRP协议

44、协议(EIGRP)。60第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.4.3 OSPF协议协议 OSPF(Open Shortest Path First)协议基于协议基于L-S路由路由算法。算法。 使用使用OSPF协议的路由器维持一个有关网络拓扑结协议的路由器维持一个有关网络拓扑结构的数据库。该数据库存放着网络中每一个路由构的数据库。该数据库存放着网络中每一个路由器上所有链路的状态，每个路由器以此数据库为器上所有链路的状态，每个路由器以此数据库为基础利用基础利用Dijkstra算法算出到网络中各目的结点的算法算出

45、到网络中各目的结点的最短路径，并将最短路径写入路由表。最短路径，并将最短路径写入路由表。 路由器将链路状态更新信息广播给网络中的所有路由器将链路状态更新信息广播给网络中的所有其它路由器，从而更新它们的数据库，重新计算其它路由器，从而更新它们的数据库，重新计算最短路径。最短路径。61第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy10.5 外部网关协议外部网关协议EGP 外部网关协议外部网关协议EGP和内部网关协议和内部网关协议IGP是完全不是完全不同，原因是它们的目的不同。同，原因是它们的目的不同。 IGP的主要目的是要维

46、持的主要目的是要维持AS内部所有路由器之间内部所有路由器之间的最短路经的最短路经Metric-Based； EGP的主要目的是维持的主要目的是维持AS之间的之间的“网络可达性网络可达性”信息，也就是说，外部网关协议信息，也就是说，外部网关协议EGP是用于两个是用于两个自治系统自治系统AS之间的关于之间的关于 “网络可达性网络可达性” 路由信路由信息的交换。息的交换。62第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyInternet路由结构（路由结构（1） RRRRR核心网关核心主干网RASASASEGP 协议RIGP 协

47、议63第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyInternet路由结构（路由结构（2）NSFNET backboneStanfordBARRNETregionalBerkeleyPARCNCARUAUNMWestnetregionalUNLKUISUMidNetregional64第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy自治系统自治系统AS 一个管理上独立与其他一个管理上独立与其他AS的网络的网络l独立管理，独立选择独立管理，独立选择I

48、GP协议，构成一个路由选择域协议，构成一个路由选择域（intradomain）；）； 每个每个AS有一个唯一编号；有一个唯一编号； 每个每个AS有至少有至少1个或多个边界路由器（个或多个边界路由器（border router）；）； AS内部的路由器通过缺省路由（内部的路由器通过缺省路由（default route）将目标地址标识为将目标地址标识为AS外部的报文首先路由到边界外部的报文首先路由到边界路由器；路由器；65第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyInternet路由结构（路由结构（3）Backbone

49、service providerPeeringpointPeeringpointLarge corporationLarge corporationSmallcorporation“Consumer ” ISP“Consumer” ISP“Consumer” ISP66第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyAS分类分类 支线支线AS（stub AS）：与另外一个）：与另外一个AS只有一个连接只有一个连接，这样的，这样的AS只传送局部通信量（只传送局部通信量（local traffic）；）； 多连接多连接AS（m

50、utlihomed AS）：与多个）：与多个AS有连接，有连接，但是拒绝传送中转通信量（但是拒绝传送中转通信量（transit traffic）；）； 中转中转AS（transit AS）：与多个）：与多个AS有连接，并能传有连接，并能传送局部通信量和中转通信量；送局部通信量和中转通信量；67第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyEGP路由例子路由例子 A自治系统 X自治系统 YBAS 间链路68第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;og

51、yEGP路由信息通告路由信息通告 秘密通道A自治系统 XC自治系统 YEF自治系统 Z(中转网络)BDAS 间链路AS 间链路69第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyBGP-4（Border Gateway Protocol） 目标目标l支持多主干因特网，允许非树型结构的互联网支持多主干因特网，允许非树型结构的互联网络；络；l支持支持CIDR路由，减缓了路由，减缓了B类地址耗尽问题，同类地址耗尽问题，同时克服路由表爆炸问题；时克服路由表爆炸问题；lPath Vector Policy-Based 难点难点l可扩

52、展性可扩展性核心路由器的路由表项大约核心路由器的路由表项大约130KlAS的自治性，导致路由策略非常复杂的自治性，导致路由策略非常复杂lAS路由器之间的信任度路由器之间的信任度安全问题安全问题70第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyBGP 实例（实例（1）Backbone network(AS 1)Regional provider A(AS 2)Regional provider B(AS 3)Customer P(AS 4)Customer Q(AS 5)Customer R(AS 6)Customer S

53、(AS 7)128.96192.4.153192.4.32192.4.3192.12.69192.4.54192.4.2371第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogyBGP 实例（实例（2） AS2的边界路由器可以向的边界路由器可以向AS1的主干路由器通知关的主干路由器通知关于于AS4(网络号为网络号为128.96和和192.4.153)和和AS5(网络号网络号为为192.4.32和和192.4.3)的可达性信息（通过的可达性信息（通过AS2） AS1的主干路由器可以向外通知关于的主干路由器可以向外通知关于AS4(

54、网络号网络号为为128.96和和192.4.153)和和AS5(网络号为网络号为192.4.32和和192.4.3)的可达性信息（通过的可达性信息（通过AS1和和AS2） 路由器可以撤销以前通知的路径路由器可以撤销以前通知的路径72第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy如何解决因特网规模的可扩展性？如何解决因特网规模的可扩展性？ 如何解决路由选择的可扩展性？如何解决路由选择的可扩展性？l如何找到减少路由协议中携带和路由器的路由如何找到减少路由协议中携带和路由器的路由表中存储的网络号数目（路由表项）的方法？表中存储

55、的网络号数目（路由表项）的方法？ 如何提高如何提高IP地址的利用率？地址的利用率？l如何确保如何确保IP地址（主要是地址（主要是B类地址）不会消耗类地址）不会消耗的太快？的太快？73第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy路由选择的可扩展性？路由选择的可扩展性？ 层次路由层次路由l域内（域内（inteadomain）路由：）路由：IGP协议协议u域内路由的复杂性取决于域内路由的复杂性取决于AS内的网络数目内的网络数目l域间（域间（inteadomain）路由：）路由：EGP/BGP协议协议u域间路由的复杂性取决于因

56、特网的域间路由的复杂性取决于因特网的AS数目数目 层次地址层次地址lIP地址分为网络号地址分为网络号+主机号主机号l路由器采用网络前缀路由，减少路由器的路由路由器采用网络前缀路由，减少路由器的路由表项表项74第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy层次路由层次路由/地址的缺点地址的缺点 层次路由的缺点层次路由的缺点l在在AS内的路径是最优路径，但内的路径是最优路径，但AS之间的路径之间的路径不一定是最优路经；不一定是最优路经； 层次地址的缺点层次地址的缺点l地址分配的低效率，如：地址分配的低效率，如：u只有只有2个

57、主机的个主机的C类地址类地址 (2/254 = 0.78%)，u只有只有256台主机的台主机的B类地址类地址256/65534 = 0.39% )75第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy问题的引发（问题的引发（1） 单位的网络可扩展性问题？单位的网络可扩展性问题？象国防科大校园象国防科大校园网：每个学院已经有各自的网络存在，要将这些网：每个学院已经有各自的网络存在，要将这些网络互联起来怎么办？网络互联起来怎么办？ 一种解决办法是用一种解决办法是用LAN交换机（如交换机（如Ethernet网交网交换机或换机或AT

58、M交换机或交换机或FDDI集中器）将这些网络集中器）将这些网络互联起来；互联起来；l假如整个单位的网络接口数目没有超过假如整个单位的网络接口数目没有超过254，可以分配，可以分配一个一个C类地址；如果超过类地址；如果超过254台，只能申请一个台，只能申请一个B类地类地址；址；76第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy问题的引发（问题的引发（2） 另一种办法就是用路由器将这些网络连接另一种办法就是用路由器将这些网络连接起来起来l用路由器来进行网络互联有什么优点？用路由器来进行网络互联有什么优点？l问题问题u国防科大

59、得申请多个国防科大得申请多个C类地址类地址u外部路由器的路由表中必须包含多条指向国防科大外部路由器的路由表中必须包含多条指向国防科大网络的路由网络的路由l解决办法解决办法u子网（子网（subnet）技术）技术77第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy子网技术（子网技术（subnet） 在在IP地址，引入另一个地址地址，引入另一个地址/路由层次：子网（路由层次：子网（subnet）；）； 把具有相同网络号的把具有相同网络号的IP地址分配给一个单位的几个地址分配给一个单位的几个不同的物理网络；不同的物理网络； 子网屏

60、蔽（子网屏蔽（subnet mask）将）将IP地址的主机号划分为地址的主机号划分为不同的子网；不同的子网； 子网对网络外部（主干路由器）是不可见的，但在子网对网络外部（主干路由器）是不可见的，但在网络内部要采用子网路由；网络内部要采用子网路由； 因此在因特网上不同的路由器看到的路由信息是不因此在因特网上不同的路由器看到的路由信息是不一样的；一样的；78第十章第十章 IP路由协议路由协议 Networking Networking techno;ogytechno;ogy子网技术的特点子网技术的特点 可以减少广播通信量、增加网络的可管理性和安可以减少广播通信量、增加网络的可管理性和安全性全性l