路由原理与技术第2章IP路由基础.ppt

第二章第二章 IPIP路由基础路由基础北京邮电大学北京邮电大学网络技术研究院网络技术研究院下一代互联网技术研究中心下一代互联网技术研究中心本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念vIPv6协议体系及地址结构协议体系及地址结构v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构v现有信息网络基本上都采用了分层的体系结构，即现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分为若干个层次，每个层次完成特将其协议体系划分为若干个层次，每个层次完成特定的功能，这样，各个层次综合在一起，就可以完定的功能，这样，各个层次综合在一起，就可以完成一个完整的系统功能。成一个完整的系统功能。v子子网网层层一一般般又又称称网网络络接接口口层层，负负责责从从网网络络层层接接收收IP报报文文并并向向物物理理网网络络发发送送，或或从从网网络络上上接接收收物物理理帧帧，取取出出IP数数据据报报并并提提交交给网络层。给网络层。v网网络络层层负负责责处处理理分分组组在在网网络络中中的的活活动动，提提供供跨跨越越多多个个网网络络的的选路功能，并对上层屏蔽底层具体子网技术的细节。选路功能，并对上层屏蔽底层具体子网技术的细节。v传传输输层层主主要要为为两两台台主主机机上上的的应应用用程程序序提提供供端端到到端端的的通通信信。在在IP网网络络中中，有有两两个个传传输输协协议议：TCP（Transmission Control Protocol，传传输输控控制制协协议议）和和UDP（User Datagram Protocol，用户数据报协议）。用户数据报协议）。v应用层处理特定应用程序细节，为用户完成各种网络服务。应用层处理特定应用程序细节，为用户完成各种网络服务。本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念vIPv6协议体系及地址结构协议体系及地址结构v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构v路由器路由器路由器是工作在网络层上，可以连接不同类型的网络，能路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传送路径并对数据进行转发的网络设备。从够选择数据传送路径并对数据进行转发的网络设备。从通信的角度看，路由器是一种中继系统。通信的角度看，路由器是一种中继系统。v路由表路由表路由器在接收到数据时，要对其传输路径进行选择。为了路由器在接收到数据时，要对其传输路径进行选择。为了实现这一目标，路由器需要维护一个称为实现这一目标，路由器需要维护一个称为“路由表路由表”的数的数据结构据结构。路由表包含若干条目，供路由器选路时查询数据传输路径。路由表包含若干条目，供路由器选路时查询数据传输路径。路由表中的一个条目至少要包含：路由表中的一个条目至少要包含：数据的目的地址（通常是目的主机所在网络的地址）数据的目的地址（通常是目的主机所在网络的地址）下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通过的下一个路由器）的地址过的下一个路由器）的地址相应的网络接口相应的网络接口一般情况下还应该有标志位等内容。一般情况下还应该有标志位等内容。泛洪（泛洪（Flooding）源路由源路由v选路策略和选路机制选路策略和选路机制选路策略（选路策略（Routing Policy）：根据数据包的目的地和网络）：根据数据包的目的地和网络的拓扑结构选择一条最佳路径，把对应不同目的地的最的拓扑结构选择一条最佳路径，把对应不同目的地的最佳路径存放在路由表中；佳路径存放在路由表中；选路机制（选路机制（Routing Mechanism）：搜索路由表，决定向哪）：搜索路由表，决定向哪个接口转发数据，并执行相应的操作；个接口转发数据，并执行相应的操作；选路策略只影响路由表的内容，比如对同一个目的地址来选路策略只影响路由表的内容，比如对同一个目的地址来说，由于选路策略的不同，最佳路径可能会不一样，但说，由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。果产生影响。vIP网络地址结构网络地址结构指指IP地址（包括地址（包括IPv4和和IPv6）的编址方式。的编址方式。通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选择时，一般按照目的网络来查询，这样既可以降低路由表规模，也择时，一般按照目的网络来查询，这样既可以降低路由表规模，也可以提高路由查询效率。可以提高路由查询效率。早早期期IPv4网网络络把把地地址址分分为为A、B、C、D、E五五类类，浪浪费费了了大大量量的的地地址址空空 间间，并并 造造 成成 路路 由由 效效 率率 低低 下下。为为 解解 决决 这这 些些 问问 题题，出出 现现 了了CIDR（Classless InterDomain Routing，无无类类别别域域间间路路由由）机机制制，即即不不再再严严格格的的对对IP地地址址类类别别进进行行区区分分，IP地地址址网网络络号号长长度度也也不不再再固固定。定。IPv6地地址址的的编编址址方方式式与与CIDR类类似似，也也是是不不限限定定网网络络号号空空间间的的长长度度，因此有很强的灵活性。因此有很强的灵活性。IP网络地址结构对路由选择和路由查询都有很大的影响。网络地址结构对路由选择和路由查询都有很大的影响。v自治系统和路由域自治系统和路由域由于由于Internet规模太大，分布范围太广，所以路由表中对规模太大，分布范围太广，所以路由表中对应每一个目的网络都有一个条目是不可能的；同样，也应每一个目的网络都有一个条目是不可能的；同样，也不可能采用一个全局的路由算法或协议。因此，不可能采用一个全局的路由算法或协议。因此，Internet将整个网络划分为若干个相对自治的局部系统，即自治将整个网络划分为若干个相对自治的局部系统，即自治系统（系统（AS，Autonomous System）。）。自治系统自治系统可以定义为可以定义为同一机构下管理的路由器和网络的集合。同一机构下管理的路由器和网络的集合。一个自治系统内部还可以再划分几个小的路由域，也称作一个自治系统内部还可以再划分几个小的路由域，也称作区域。区域。v内部网关协议和外部网关协议内部网关协议和外部网关协议 路由协议可以分为内部网关协议（路由协议可以分为内部网关协议（IGP，Interior Gateway Protocol）和外部网关协议（和外部网关协议（EGP，Exterior Gateway Protocol）两大类。）两大类。v内部网关协议是用于自治系统内部的动态路由协议内部网关协议是用于自治系统内部的动态路由协议 RIP（Routing Information Protocol，路由信息协议，路由信息协议）OSPF（Open Shortest Path First，开放最短路径优先，开放最短路径优先）；）；v外部网关协议是用于自治系统之间拓扑信息交换的路由协议外部网关协议是用于自治系统之间拓扑信息交换的路由协议 BGP（Border Gateway Routing Protocol，边界网关路由协议，边界网关路由协议）。）。v路由选择算法路由选择算法路由算法是指路由器获得对网络拓扑结构路由算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确传输路径的的认知，并为数据包选择正确传输路径的方法或者策略。方法或者策略。一一个个理理想想的的路路由由算算法法至至少少应应该该具具备备以以下下几几点点特特征征：完完整整性性和和正正确确性性；简简单单性性；健壮性；健壮性；公平性；公平性；最佳性。最佳性。路由算法的分类。路由算法的分类。v静态路由选择和动态路由选择静态路由选择和动态路由选择按按照照能能否否自自动动适适应应网网络络拓拓扑扑结结构构的的变变化化，可可以以将将选选路路策策略略分分为为静静态态路路由由选选择择和和动动态态路路由由选选择择两两大大类。类。静态路由选择并不是表示路由表一成不变，只是静态路由选择并不是表示路由表一成不变，只是说明路由器不是通过彼此之间动态交换路由信息说明路由器不是通过彼此之间动态交换路由信息来建立和更新路由表的。来建立和更新路由表的。动态路由选择是通过网络中路由器间的相互通信动态路由选择是通过网络中路由器间的相互通信来传递路由信息，利用接收到的路由信息自动更来传递路由信息，利用接收到的路由信息自动更新路由表。新路由表。v距离矢量路由选择协议和链路状态路由选择协议距离矢量路由选择协议和链路状态路由选择协议距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器周期地和相邻路由器交换路由表中的信息。这种信息是由若干（周期地和相邻路由器交换路由表中的信息。这种信息是由若干（V，D）对组成的表项，其中，对组成的表项，其中，V代表矢量，指出该路由器可以达到的目代表矢量，指出该路由器可以达到的目的地；的地；D表示去往目标表示去往目标V的距离。各个路由器根据收到的信息重新计的距离。各个路由器根据收到的信息重新计算到各目的节点的距离，对自己的路由表进行修正。算到各目的节点的距离，对自己的路由表进行修正。链路状态路由选择协议也被称为最短路径优先协议，它基于链路状态链路状态路由选择协议也被称为最短路径优先协议，它基于链路状态路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓扑结构的无向图扑结构的无向图G（V，E），），在图在图G中，节点中，节点V表示路由器，边表示路由器，边E表表示连接路由器的链路，因此示连接路由器的链路，因此G又可以称为又可以称为L-S（链路链路-状态）图，各路状态）图，各路由器的路由表通过由器的路由表通过L-S图计算。图计算。本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念vIPv6协议体系及地址结构协议体系及地址结构v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构IPv6协议体系协议体系vIPv6基本协议栈：基本协议栈：IPv6、ICMPv6（Internet Control Messages Protocol version 6，因特网控制报文协议版本，因特网控制报文协议版本6）、）、ND（Neighbor Discovery Protocol，邻居发现协议）等，邻居发现协议）等v传输层协议：传输层协议：TCP/UDPv路由协议：路由协议：RIPng、OSPFv3、BGP4+v网络管理协议网络管理协议SNMP（Simple Network Management Protocol，简单网络管理协议）、安全协议，简单网络管理协议）、安全协议IPSec（IP security，IP安安全）全）v应用层协议应用层协议IPv6地址分类地址分类vIPv6地址可以分为单播地址、多播地址和任地址可以分为单播地址、多播地址和任播地址三类。播地址三类。单播地址：仅标识一个接口，相当于传统的点对点地址单播地址：仅标识一个接口，相当于传统的点对点地址多播地址：用于标识一组接口，发给多播地址的报文通多播地址：用于标识一组接口，发给多播地址的报文通常要发给该组的所有成员常要发给该组的所有成员任播地址：也用于标识一组接口，但发给任播地址的报任播地址：也用于标识一组接口，但发给任播地址的报文只发给其中的一个，通常是最近（根据路由的度量）文只发给其中的一个，通常是最近（根据路由的度量）一个一个IPv6地址的表示地址的表示vIPv6的的128位位（即即16个个字字节节）地地址址写写成成8个个16位位无无符符号号整整数数，每每个个整整数数用用4位位十十六六进进制制数数来来表表示示，这这些些数数之之间间用用冒冒号号(:)分开，例如：分开，例如：AEDC:FA20:7484:32B0:AEFC:BC91:2645:3214v形形如如ABCD:0000:0000:0000:0008:0800:800C:417C 的的可可以以简化为简化为ABCD:0008:0800:800C:417Cv简化只可以用一次。简化只可以用一次。IPv6地址分配地址分配IPv4映射的映射的IPv6地址地址 IPv4兼容的兼容的IPv6地址地址 回环地址回环地址 :1(即即0000 0001)0000 0000FFFF IPv4地址地址 80位位0000 00000000IPv4地址地址 80位位 16位位 16位位 32位位 32位位 127个个0IPv6地址分配（续）地址分配（续）本地链路单播地址本地链路单播地址 本地网点单播地址本地网点单播地址 1111 1110 100000 0000接口接口ID 54位位1111 1110 110000 0000 子网子网ID接口接口ID 64位位 10位位 64位位 16位位 38位位 10位位IPv6地址分配（续）地址分配（续）单播地址单播地址 64位接口位接口ID应符合应符合IEEE EUI-64的格式。可聚集全局单播地址的格式。可聚集全局单播地址的格式如下：的格式如下：多播地址多播地址 常见的多播地址：常见的多播地址：FF02:1 所有节点地址所有节点地址 FF02:2 所有路由器地址所有路由器地址 FF02:5 OSPF路由器路由器 FF02:6 OSPF指派路由器指派路由器 FF02:9 RIP路由器路由器001全球路由前缀全球路由前缀子网子网ID接口接口ID3位位 45位位 16位位 64位位IPv6地址的自动配置地址的自动配置v一个接口一旦被初始化，主机就可以为该接口建立一个链一个接口一旦被初始化，主机就可以为该接口建立一个链路局部地址，接口路局部地址，接口ID符合符合IEEE EUI-64标准。标准。v无状态自动配置无状态自动配置一个一个IPv6节点启动时，要加入节点启动时，要加入“所有节点所有节点”多播组；多播组；向向“所有路由器所有路由器”多播组发送请求报文，源地址是其链多播组发送请求报文，源地址是其链路局部地址；路局部地址；路由器收到这样一个报文后，就回应一个应答报文，通路由器收到这样一个报文后，就回应一个应答报文，通告自己的前缀。告自己的前缀。v有状态自动配置有状态自动配置利用利用DHCP配置主机地址。配置主机地址。从从IPv4过渡到过渡到IPv6 在从在从IPv4过渡到过渡到IPv6的过程中，为保证的过程中，为保证IPv6节节点和点和IPv4节点之间的互通，主要有以下几种技术：节点之间的互通，主要有以下几种技术：双协议栈技术双协议栈技术隧道技术隧道技术网络地址转换技术网络地址转换技术其他：其他：SOCKS64、应用层网关、传输层中继、主、应用层网关、传输层中继、主动网络动网络本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念vIPv6协议体系及地址结构协议体系及地址结构v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构路由转发原理路由转发原理 处理器处理器内存内存接口接口1接口接口2接口接口n查询路由表查询路由表本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念vIPv6协议体系及地址结构协议体系及地址结构v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构距离矢量路由算法距离矢量路由算法（1）各路由器对自己的路由表进行初始化，把与自己直）各路由器对自己的路由表进行初始化，把与自己直接相连网络的距离设为接相连网络的距离设为0（在某些具体实现中也设为（在某些具体实现中也设为1，这只，这只是一个初始值设定的问题），然后周期性地向外广播其路由是一个初始值设定的问题），然后周期性地向外广播其路由表的内容。表的内容。（2）路由器）路由器Ri收到相邻路由器收到相邻路由器Rj的距离矢量信息后，对的距离矢量信息后，对自己的路由表进行修正。自己的路由表进行修正。若若Rj的距离矢量信息中所包含的目的节点的距离矢量信息中所包含的目的节点va在在Ri的路由的路由表中没有，则在表中没有，则在Ri的路由表中增加一个目的节点为的路由表中增加一个目的节点为va的条目，的条目，令令dia=dja+1，并把到节点并把到节点va的下一跳路由器设为的下一跳路由器设为Rj。若到若到Rj目的节点目的节点vb的路由比的路由比Ri到目的节点到目的节点vb的路由短，的路由短，则令则令dib=djb+1，并把到节点，并把到节点vb的下一跳路由器设为的下一跳路由器设为Rj。Ri到目的节点到目的节点vc最短路径上的下一跳是最短路径上的下一跳是Rj。如果。如果Rj的路由表中不再包含到的的路由表中不再包含到的vc路由，则在路由，则在Ri中也应该中也应该把去往把去往vc的路由删掉；如果的路由删掉；如果Rj到到vc的距离发生了变化，的距离发生了变化，则则Ri修改路由表中到修改路由表中到vc的距离，令的距离，令dic=djc+1。v距离矢量路由算法在理论上是可以正常工作距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一个严重的缺陷：尽的，但在实际中存在着一个严重的缺陷：尽管它可以收敛到正确的路由，但它对好消息管它可以收敛到正确的路由，但它对好消息传播的快，而对坏消息则传播的慢。传播的快，而对坏消息则传播的慢。v总的来说，距离矢量路由选择协议的优点是总的来说，距离矢量路由选择协议的优点是易于实现，但难以适应网络拓扑的剧烈变动易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。或者大型的网络环境。链路状态路由算法链路状态路由算法 v链路状态路由算法的基本步骤如下：链路状态路由算法的基本步骤如下：（1）每一个路由器（节点）启动后，首先执行对相邻）每一个路由器（节点）启动后，首先执行对相邻节点的发现工作，并获取它们的地址。节点的发现工作，并获取它们的地址。（2）各路由器主动测试到每一个相邻路由器的链路时）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关链路的状态。延或成本，并根据测试结果设置相关链路的状态。（3）各路由器构造自己的）各路由器构造自己的L-S（Link-State，链路状态）信息链路状态）信息包，包，L-S信息的内容包括本路由器的标号、本路由器的邻居路信息的内容包括本路由器的标号、本路由器的邻居路由器列表、本路由器到各邻居路由器的链路状态（时延或成本）由器列表、本路由器到各邻居路由器的链路状态（时延或成本）、该、该L-S信息包的序号和生存时间等。信息包的序号和生存时间等。（4）各路由器向所有参与链路状态交互的路由器广播其）各路由器向所有参与链路状态交互的路由器广播其L-S信信息，可以是周期性地发送，也可在链路状态发生变化时发送。息，可以是周期性地发送，也可在链路状态发生变化时发送。（5）每个路由器在收到所有的）每个路由器在收到所有的L-S信息后，可以构造或更新信息后，可以构造或更新表示整个网络拓扑结构的图表示整个网络拓扑结构的图G（V，E），），顶点顶点V表示路由器，表示路由器，边边E表示连接路由器的链路；这时路由器就可以用表示连接路由器的链路；这时路由器就可以用Dijkstra算法算法从图从图G中计算出到所有目的路由器的最短路径，也就是构造以中计算出到所有目的路由器的最短路径，也就是构造以自己为根节点的自己为根节点的SPF树。树。Dijkstra算法简介算法简介 设目的节点（就构造设目的节点（就构造SPF树而言，是根节点）为树而言，是根节点）为k，任一，任一条链路条链路（i，j）的长度为的长度为dij，每个节点到，每个节点到k的最短路径长度估的最短路径长度估计为计为Dik；定义所有节点的集合为；定义所有节点的集合为A，定义集合，定义集合PA，并设定，并设定集合的初始值为集合的初始值为P=k。在算法迭代的过程中，如果在算法迭代的过程中，如果Dik已经变成一个确定值，则已经变成一个确定值，则将将i标记为固定点，并将其加入集合标记为固定点，并将其加入集合P。在算法的每一步迭代。在算法的每一步迭代中，在中，在P以外的节点中，选择与目的节点以外的节点中，选择与目的节点k最近的节点加入到最近的节点加入到P中，算法的具体步骤如下：中，算法的具体步骤如下：Dijkstra算法简介算法简介（1）P=k,Dkk=0，Djk=djk（若（若j和和k不相邻，不相邻，）（2）求解使）求解使 成立的成立的i，即寻找下一个和，即寻找下一个和目的节点最近的节点；令目的节点最近的节点；令 ，若，若P=A，算法结束。，算法结束。（3）对所有）对所有 ，置，置 ，返回步骤，返回步骤（2）本章提纲本章提纲v互联网的体系结构互联网的体系结构vIP路由中的基本概念路由中的基本概念vIPv6协议体系及地址结构协议体系及地址结构v路由转发原理路由转发原理v路由选择算法路由选择算法v路由器硬件体系结构路由器硬件体系结构v集中式单（多）集中式单（多）CPU+总线结构总线结构缺陷缺陷CPU要负责整体系统的控制管理、路由计算和数要负责整体系统的控制管理、路由计算和数据转发等各项功能，存在计算瓶颈。据转发等各项功能，存在计算瓶颈。所有接口卡的数据都要争用总线，存在数据交换所有接口卡的数据都要争用总线，存在数据交换瓶颈瓶颈。v分布式多分布式多CPU+总线结构总线结构特点特点路由计算和转发分离：主控路由计算和转发分离：主控CPU负责整个系统的负责整个系统的控制管理和路由计算（即运行路由协议，维护和控制管理和路由计算（即运行路由协议，维护和更新路由表）；线卡上的更新路由表）；线卡上的CPU负责查询路由表，负责查询路由表，对数据进行转发。对数据进行转发。部分地克服了总线瓶颈，即如果数据的接收和发部分地克服了总线瓶颈，即如果数据的接收和发送都在一个线卡上，就不用争用总线；若数据的送都在一个线卡上，就不用争用总线；若数据的接收和发送涉及不同的线卡，还是会出现总线争接收和发送涉及不同的线卡，还是会出现总线争用问题。用问题。v分布式多分布式多CPU+Crossbar结构结构特点特点路由计算和转发分离。路由计算和转发分离。采用采用Crossbar的交换结构（的交换结构（Switch Fabric），），每个每个输入端口和输出端口之间都有一个交叉开关，只输入端口和输出端口之间都有一个交叉开关，只要数据流彼此不相关，就可以实现无阻塞的交换，要数据流彼此不相关，就可以实现无阻塞的交换，解决了总线争用问题。解决了总线争用问题。基本上解决了路由器吞吐量的问题。基本上解决了路由器吞吐量的问题。交叉开关的设计和调度算法是研究的重点和难点。交叉开关的设计和调度算法是研究的重点和难点。v路由器硬件体系结构发展总结路由器硬件体系结构发展总结共享总线共享总线 交叉开关交叉开关路由计算与转发分离路由计算与转发分离