计算机网络：路由基础 IP路由

IP路由第2页内容概述路由的基本概念路由选择算法静态路由选择算法动态路由选择算法路由选择算法介绍第3页第4页第5页第6页/Software/Cichlid/gallery/cheap_callouts.html第7页第8页网络层的主要功能是将分组从源端机器经选定的路由送到目的端机器。在绝大多数网络当中分组需要经过多次的转发才能到达目的端机器。路由选择算法和它们所使用的数据结构是网络层设计当中的一个关键问题。第9页发送端的处理过程： 当主机A要和主机B进行通信时，首先判断主机B是否和它位于同一子网。方法：把两个主机的IP地址分别与它(主机A)的 子网掩码进行“位与”操作，把分别得到的网络ID进行比较，如果结果相同，则表明位于同一子网，否则位于不同的子网。示例：第10页主机A的IP地址与子网掩码进行“位与”操作主机B的IP地址与子网掩码进行“位与”操作结果相同，可见，两个主机位于同一子网中示例1：第11页主机A的IP地址与子网掩码进行“位与”操作主机B的IP地址与子网掩码进行“位与”操作结果不同，可见，两个主机不在同一子网中示例2：第12页

如果在同一子网，则源主机用ARP确定目标主机的硬件地址后直接发送数据帧到目标主机。(直接路由，无需路由器)

如果不在同一子网，则源主机用ARP确定默认网关(路由器)的硬件地址后，把数据帧转发给默认网关(间接路由)。 至此源主机的发送就结束了。第13页

剩下的任务是间接路由情形下： 路由器把收到的数据帧解开，利用IP包中的地址选择如何进一步处理， 如果目的主机在路由器所处的另一个子网，则变成直接路由的情况，封装IP包，直接发送。 如果目的主机不在与路由器直接相连的子网，则需要选择转发到下一个路由器。通过进行转发，最终到达与目的主机在同一物理网络的路由，从而传送到目标主机（最终的一个步骤总是直接路由）。 问题：路由器如何选择转发的下一个路由器?第14页路由器为了把收到的数据传送到目标主机，需要知道那些主机是可达的以及如何达到。这些网络拓扑信息由路由器中的路由表保存，路由器通过查找路由表，选择转发数据的路径。路由表第15页下一跳(Next-Hop)路由表一个简化：是只保存目标网络的路由信息，因为一旦找到目标主机所在的目标网络，就可以直接在物理层传输数据帧了。进一步的简化：是不必在每个路由器中都保存一个到目标网络的完整路径，而只保存从本路由器到目标网络的路径的下一步路由器地址，这样就可以一步一步达到目标网络了。这种路由方式称为下一跳路由。其路由表的内容是这样的：第16页下一跳路由表示例表的第一列指明目标网络，第二列指明为到达该目标网络下一步应转发给哪一个路由器。第17页说明：路由表中通过指定网络号而非具体的主机，对主机进行屏蔽。使主机通信依赖于路由器。更主要的是，通过只指定网络，极大地减少了路由表的大小，只有网络数目的增长才会引起路由表的扩大，而主机的增加对路由表没有影响。路由表中列出的接口地址均应与路由器在同一物理网络，可直接转发物理帧的。还应该指定一个默认路由，以确定当网络号均不匹配时，如何转发。（当主机只能访问一个路由器时尤其应设置）也可以为了某些目的为某个主机指定路由。第18页

Destination

Gateway

Flags

Ref

Use

Interface

UH 0 26492lo055 UGH 0 0 emd02 3 U 3 58503le0default29 UG 0 43454emd0第19页Flags:U:可用G:网关H:主机D:ICMP重定向报文创建M:ICMP重定向报文修改Refent：正在使用路由的活动进程个数Use：通过该路由的分组数第20页问题：一旦路由表给定，所有的流量均将沿指定的同一路径转发，即使有多个可选路径。只有最后与目标网络相连的路由器才和目标主机直接通信，前面的路由器完全不知道目标主机的状态，如果目标主机已经不存在，那么也只有等数据发到最后一个路由器时才知道。第21页下一跳路由的算法：执行：拆开IP数据报，从中抽取目的IP地址：D，通过“位与”运算求出目的地址的网络ID：NifN和某个与路由器直接相连的网络匹配，则直接转发到该网络中的相应主机（这需要执行：从IP地址D解析出目的主机的物理地址，封装IP数据报为帧，帧头包含目的主机的物理地址，发送帧）。elseif路由器的路由表中包含有为该主机D指定的路由，则按路由表中所指定的发送到下一跳（这需要执行：解析所指定的下一跳路由的物理地址，封装IP数据报为帧，帧头包含下一跳路由的物理地址，发送帧）。elseif路由器的路由表中包含有到达该网络N的路由，则按路由表中所指定的发送到下一跳（这需要执行：同上）。elseif路由器的路由表中包含有默认路由，则发送到路由表中所指定的默认路由（这需要执行：解析所指定的默认路由的物理地址，封装IP数据报为帧，帧头包含默认路由的物理地址，发送帧）。else发回路由出错消息。

第22页一个问题：上述执行中均要解析下一跳的物理地址封装成帧，而不用IP地址，十分繁琐，为什么不在路由中直接指定下一跳的物理地址呢？原因：层次分明，物理地址在低层使用，如果又在网络层使用，则层次不清。分层体系的一个要点就是下层应该对上层是透明的。IP地址易于管理和维护，当路由表更新时，查看IP地址比查看物理地址更易明白发生了什么问题。第23页子网路由当要与子网中的主机进行通信时，那么只在路由表中指定网络ID还不够，因为一个网络ID中可能有多个物理子网，此时，还必须指定子网掩码：当选择路由时，就需要把目的主机的IP地址与子网掩码进行“位与”，以确定目标主机所在的网络地址，从而选择下一跳地址。第24页IP是提供的是无连接的服务，源主机一旦把数据报发出之后，各个中间路由器根据数据报中的信息自主操作，与源主机无关，如果所有中间传输以及目的接收都不出问题，则此机制能正常工作。但如果出现问题，如路径拥塞不能正常转发数据报或目的主机宕机等，如何通知源主机此类情况以便其采取相应措施。(ICMP消息)路由表中包含一些什么内容最好？如何建立路由表？(路由协议)第25页主机A主机Beth0eth1eth2eth2/24eth1/24eth2/24eth1/24eth0/24接口下一跳路由网络地址路由器1eth2/24eth0/24eth2/24eth1/24eth0/24接口下一跳路由网络地址路由器2eth0eth1eth2第26页IP路由协议第27页两个问题：路由表中应该包含一些什么信息？路由器如何获得这些信息？第28页11

Iproute

IprouteCisco路由器：11add-iproute=add-iproute=3com路由器：11

Iproute

Iprouteadd-iproute=add-iproute=11第29页路由表第30页路由表输出的解释第31页理想路由算法特点算法必须是正确的和完整的。算法在计算上应简单。算法应能适应通信量和网络拓扑的变化算法应具有稳定性。

路由算法应收敛于一个可以接受的解，路由不应不停的变化。算法应是公平的。算法应是最佳的。

只能相对于某一种特定要求下得出的较为合理的选择。

第32页第33页关于“最佳路由”不存在一种绝对的最佳路由算法。所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。实际的路由选择算法，应尽可能接近于理想的算法。路由选择是个非常复杂的问题它是网络中的所有结点共同协调工作的结果。路由选择的环境往往是不断变化的，而这种变化有时无法事先知道。

第34页从路由算法的自适应性考虑静态路由选择策略——即非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。动态路由选择策略——即自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。第35页ExampleofStaticRouting

directdefault

00NetMaskNexthopNetwork/16H1H2H3H4TotherestoftheInternetRouteraddress00RouterR1第36页路由表的创建包含两个方面—初始化路由表和更新路由表初始化路由表取决于操作系统，可能有如下几种情况：路由器在启动时从二级存储器中读取一个初始路由表，并驻留在主存中。初始路由表为空，在启动后通过执行外部命令来填充。从它所连接的本地网络的地址集推出一个初始的路由，并与相邻的路由器联系以获得更多的路由信息。初始的路由表建立之后，就需要根据网络路由的变化进行更新。对于较小的、变化较慢的网络可以由管理员手工来做；而对于大的、变化较复杂的网络则很难能由手工完成迅速的更新，就需要一些自动的方法第37页下一跳路由表的问题：由于下一跳路由表中只包含了到下一个网络（对于中间路由器而言，下一个网络不是目的网络）的路径，如果所有网络都是互通的，那么可以断定的是：除非进入了某个循环路径，数据最终总能到达目的网络，但问题在于：所走的路径是否是到达目的网络的最短路径？例如：第38页分层次的路由选择协议因特网采用分层次的路由选择协议。因特网的规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使因特网的通信链路饱和。许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到因特网上。第39页自治系统AS

(AutonomousSystem)自治系统AS的定义：在单一的技术管理下的一组路由器，而这些路由器使用一种AS内部的路由选择协议和共同的度量以确定分组在该AS内的路由，同时还使用一种AS之间的路由选择协议用以确定分组在AS之间的路由。现在对自治系统AS的定义是强调下面的事实：尽管一个AS使用了多种内部路由选择协议和度量，但重要的是一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。第40页通过把网络中的路由器分为两类：一类路由器成为核心路由器，其中保有所有网络路径完整、可靠、一致的信息，这一类的路由器数目较少，由专门的组织负责维护；另一类是非核心的路由器，自治地维护本地路径。示意图：第41页因特网有两大类路由选择协议内部网关协议

IGP(InteriorGatewayProtocol)即在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用得最多，如RIP和OSPF协议。外部网关协议EGP(ExternalGatewayProtocol)若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议EGP。在外部网关协议中目前使用最多的是BGP-4。第42页自治系统和

内部网关协议、外部网关协议

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

用内部网关协议（例如，OSPF）自治系统之间的路由选择也叫做域间路由选择(interdomainrouting)，在自治系统内部的路由选择叫做域内路由选择(intradomainrouting)第43页这里要指出两点因特网的早期RFC文档中未使用“路由器”而是使用“网关”这一名词。但是在新的RFC文档中又使用了“路由器”这一名词。应当把这两个属于当作同义词。IGP和EGP是协议类别的名称。但RFC在使用EGP这个名词时出现了一点混乱，因为最早的一个外部网关协议的协议名字正好也是EGP。因此在遇到名词EGP时，应弄清它是指旧的协议EGP还是指外部网关协议EGP这个类别。第44页因特网的路由选择协议内部网关协议IGP：具体的协议有多种，如RIP和OSPF等。外部网关协议EGP：目前使用的协议就是BGP。第45页abbaaC ABdA.cA.aC.bB.acbcborder(exteriorgateway)routers第46页Intra-ASandInter-ASroutingHosth2abbaaCABdcA.aA.cC.bB.acbHosth1Intra-ASroutingwithinASAInter-ASroutingbetweenAandBIntra-ASroutingwithinASB第47页

InternetBackbonesinNorthAmerica第48页第49页第50页在核心路由系统中，通过把所有可能路径的完备信息在核心路由器之间不断传播、更新而使核心路由系统能保有完整、一致、可靠的路由信息。其中的一个关键是路由传播和更新的算法。两种路由协议的区别：网络规模大小的不同域和域之间的路径度量不同考虑策略不同第51页内部网关协议RIP

(RoutingInformationProtocol)1.工作原理路由信息协议RIP是内部网关协议IGP中最先得到广泛使用的协议。RIP是一种分布式的基于距离向量的路由选择协议。RIP协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。

第52页“距离”的定义从一路由器到直接连接的网络的距离定义为1。从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加1。RIP协议中的“距离”也称为“跳数”(hopcount)，因为每经过一个路由器，跳数就加1。这里的“距离”实际上指的是“最短距离”，第53页“距离”的定义RIP认为一个好的路由就是它通过的路由器的数目少，即“距离短”。RIP允许一条路径最多只能包含15个路由器。“距离”的最大值为16时即相当于不可达。可见RIP

只适用于小型互联网。RIP不能在两个网络之间同时使用多条路由。RIP选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。第54页RIP协议的三个要点仅和相邻路由器交换信息。交换的信息是当前本路由器所知道的全部信息，即自己的路由表。按固定的时间间隔交换路由信息，例如，每隔30秒。第55页路由信息协议（RouteInformationProtocol）v1首个RIP（RIP1RFC1058，1988）标准发布于1988年六月。RIP把网络中的节点分为活动的和被动的。活动节点可以广播路由信息，也可以接收、更新信息，被动节点只能接收广播并更新自己的路由信息。只有路由器可以作为活动节点，而主机只能作为被动节点。活动节点每隔30秒广播一轮其当前路由表中的路由信息。RIP使用“跳数”来计算到目的网络的距离。通过一个网络为一跳，可以人为地把某些慢速网络设置为多跳数，以更精确。RIP规定最大跳数为15，若跳数为16则表示不可达。RIP路由信息中只包含两项：目的网络和达到目的网络的跳数。第56页路由信息协议仅和相邻路由器交换信息交换信息是当前本路由器所知道全部信息按固定时间间隔交换信息采用距离向量算法第57页距离向量算法路由表格式第58页距离向量算法收到相邻路由器X的RIP报文1。修改此报文中的所有项目：将“下一跳”字段的地址都改为X，并且将所有的“距离”字段＋12。对修改后的RIP报文的每一个项目，重复以下步骤：若项目当中的目的网络不在路由表中，则添加该项目到路由表中否则：若下一跳字段给出的路由器地址是相同的，则将收到项目替换原路由表中的项目否则：若收到项目中的距离小于路由器表当中的距离，则进行更新否则：什么也不做若超过3分钟没有收到相邻路由器的更新路由表，则将相邻路由距离置16返回第59页NET1ABCNET2NET3NET4NetHopNextnet31-net41-NetHopNextnet11-net21-NetHopNextnet21-net31-第60页NET1ABCNET2NET3NET4NetHopNextnet31-net41-net22BNetHopNextnet11-net21-net32BNetHopNextnet21-net31-net12Anet42C第61页NET1ABCNET2NET3NET4NetHopNextnet31-net41-net22Bnet13BNetHopNextnet11-net21-net32Bnet43BNetHopNextnet21-net31-net12Anet42C第62页RIP提出了一些规则来提供性能和可靠性。例如：一旦路由器从别的路由器学习到一个路由，那么它将一致保留直到学到了另一个更好的。（最优，又避免振荡）被动节点在学到一个路由后要立即开始计时，在180秒之内，如果一直没有再次得到关于此路由的广播，则放弃此路由。（宁缺勿错）RIP中的问题：慢收敛问题问题的描述：第63页NET1ABNET2NetHopNextnet11-net21-net32BNetHopNextnet21-net31-net12ANET3第64页NET1ABNET2NetHopNextnet116-net21-net32BNetHopNextnet21-net31-net12ANET3第65页NET1ABNET2NetHopNextnet13Bnet21-net32BNetHopNextnet21-net31-net12ANET3第66页NET1ABNET2NetHopNextnet13Bnet21-net32BNetHopNextnet21-net31-net14ANET3………………第67页NET1ABNET2NetHopNextnet116Bnet21-net32BNetHopNextnet21-net31-net116ANET3好消息传播快，坏消息传播慢－需要较长时间才能将网络故障信息传播到网络当中所有路由器第68页解决方案:水平切割路由器计录每个接口收到的路由信息，禁止把一条路由信息从收到它的接口再广播出去。如上例，可以解决问题，但有些拓扑结构也不行。保持一旦某个路由器在收到一个网络变为不可达的消息后，它将在一个规定时间区间内保持此消息而忽略其他路由器发给它的其他消息（坏消息优先，针对网上：好消息传的快，坏消息传的慢），这样就确保坏消息能先传播出去，而不会在传出去之前就被更新。但会造成一个较长的保持时间，特别对广域网。即使此时有好消息，也不可传播。触发更新一旦收到消息报告网络不可达，就立即广播，不必等下一个广播周期到。同时，在广播中保留此目的网络，只是加一个很大的代价值。但在某些结构中，如多个路由器同时连在某个网络上，此时会造成突然的流量激增。第69页RIP报文格式:RIP报文封装在用户数据报(UDP)中，默认UDP端口号为520第70页不同的命令字段值指定不同的操作:路由器和主机可以通过发送请求命令来请求另外的路由器发送路由信息。通常，路由器周期性发送非请求的路由信息。每个报文最多携带25个路由。第71页RIP选路中的距离为hop值，有以下问题：hop值刻画距离并不能十分精确，每一跳并不可能精确相同不能动态表现某个网络的通信量负载不支持子网RIP2（RFC1388，1993）对RIP1的扩展，协议本身并无变化，只是利用RIP报文格式中的为零部分来传递更多的信息。其中通过传递子网掩码扩展了对子网路由的支持。格式见下页图：第72页第73页内部网关协议OSPF

(OpenShortestPathFirst)1.OSPF协议的基本特点“开放”表明OSPF协议不是受某一家厂商控制，而是公开发表的。“最短路径优先”是因为使用了Dijkstra

提出的最短路径算法SPFOSPF只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。是分布式的链路状态协议。

第74页三个要点向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法。发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。

只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。

第75页链路状态数据库

(link-statedatabase)

由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。OSPF的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF的更新过程收敛得快是其重要优点。第76页OSPF的区域(area)为了使OSPF能够用于规模很大的网络，OSPF将一个自治系统再划分为若干个更小的范围，叫作区域。每一个区域都有一个32位的区域标识符（用点分十进制表示）。区域也不能太大，在一个区域内的路由器最好不超过200个。第77页自治系统ASOSPF划分为两种不同的区域区域区域主干区域至其他自治系统R9R7R6R5R4R3R2R1网

8网

6网

3网

2网

1网

7区域网4网

5R8第78页划分区域划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。OSPF使用层次结构的区域划分。在上层的区域叫作主干区域(backbonearea)。主干区域的标识符规定为。主干区域的作用是用来连通其他在下层的区域。

第79页自治系统AS主干路由器区域区域主干区域至其他自治系统R9R7R6R5R4R3R2R1网

8网

6网

3网

2网

1网

7区域网4网

5R8第80页自治系统AS区域边界路由器区域区域主干区域至其他自治系统R9R7R6R5R4R3R2R1网

8网

6网

3网

2网

1网

7区域网4网

5R8第81页OSPF直接用IP数据报传送OSPF不用UDP而是直接用IP

数据报传送。OSPF构成的数据报很短。这样做可减少路由信息的通信量。数据报很短的另一好处是可以不必将长的数据报分片传送。分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。第82页OSPF的其他特点OSPF对不同的链路可根据IP分组的不同服务类型TOS而设置成不同的代价。因此，OSPF对于不同类型的业务可计算出不同的路由。如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。这叫作多路径间的负载平衡。所有在OSPF路由器之间交换的分组都具有鉴别的功能。支持可变长度的子网划分和无分类编址CIDR。每一个链路状态都带上一个32位的序号，序号越大状态就越新。第83页IP数据报OSPF分组IP数据报首部OSPF分组OSPF分组首部类型1至类型5的OSPF分组24字节081631版本路由器标识符类型分组长度检验和鉴别位鉴别区域标识符鉴别类型第84页OSPF的五种分组类型类型1，问候(Hello)分组。类型2，数据库描述(DatabaseDescription)分组。类型3，链路状态请求(LinkStateRequest)分组。类型4，链路状态更新(LinkStateUpdate)分组，用洪泛法对全网更新链路状态。类型5，