南京理工大学《ip网络技术》ip网络技术第4章 路由选择协议

第4章 路由选择协议,主要内容,路由选择技术 分类寻址路由表 无分类域间路由选择（CIDR） 内部和外部路由协议,2,4.1 路由选择技术,下一跳路由选择 特定网络路由选择 默认路由选择 特定主机路由选择,3,路由选择技术就是寻找一条将IP分组从源站传输到目的站的最佳路径的技术，而传输路径往往由一系列路由器组成。因此，路由选择实质是在不同的路由器之间做出选择，选择分组传输过程中的下一个路由器。,图4-1 一个互联网的拓扑结构,4,交付：主机主机主机路由器路由器路由器路由器主机直接交付的含义、类型、判断间接交付的含义,5,IP分组在网络中的一次传递过程称作一次交付。,指分组的最终目的站与交付者在同一个网络上时实现的交付方式。,1.分组的源站和目的站主机都在同一个物理网络上的交付；2.在目的网络上实现的交付，即IP分组在目的网络上的路由器与目的站主机之间的交付,发送IP分组的站点提取出交付分组的目的IP地址，计算目的网络地址，如果与本网络的网络地址一致，就是直接交付。,当目的站主机与交付者不在同一个物理网络上时，分组就实现间接交付。,分组从源站到目的站主机的一个交付过程总是包含一个直接交付和零个或多个间接交付，并且最后一次的交付总是直接交付。,间接交付中，发送站使用IP分组的目的IP地址和路由表来找出下一个路由器的IP地址，分组必须要交付到这个路由器。怎样得到分组要交付的下一个路由器的IP地址呢？,4.1.1 下一跳路由选择,在路由表中并不需要保留从源站到目的站的完整路由，而只需要保留转发的下一个路由器地址。,6,下一跳路由选择就是在路由表中只保留下一跳的地址，而不是保留完整路由的信息，通过各路由表之间的彼此协作，实现IP分组转发的完整路由。,图4-2 基于下一跳的路由选择,7,4.1.2 特定网络路由选择,在路由表中并不需要为每一个目的站主机保留一个路由表项，而只需对目的网络保留一个路由表项。,8,特定网络路由选择就是在路由表中仅用一个路由表项来定义该网络，而不是为网络中所有主机定义路由表项，这样可以减小路由表的大小，简化路由表的查找过程。,图4-3 特定网络路由选择,9,4.1.3 特定主机路由选择,在特定主机路由选择中，路由表中给出的是主机的路由表项，而不是目标网络的路由表项。,10,在检查路由或提供安全措施等的一些特殊情况下，特定主机路由选择就是一种很好的选择。,图4-4 特定主机路由选择路由器R1的路由表,11,4.1.4 默认路由选择,在主机的路由表中可以不必列出整个互联网中所有网络的路由表项，仅需使用一个网络地址为0.0.0.0的默认路由表项表示这些剩余的互联网路由表项。,12,图4-5 默认路由选择主机A的路由表,13,4.2 分类寻址路由表,路由表表项 路由选择流程,14,主机或路由器根据自身保留的路由表实现网络层IP分组的转发。在路由表中，每一个路由表对应到一个目的站的路由。,4.2.1 路由表表项,15,路由表结构:,例：Windows 路由表,16,例：路由器中的路由表,17,4.2.2 路由选择流程,从被转发的IP分组首部中提取目的IP地址D。判断直接交付路由表项。否则就是间接交付，执行。判断特定主机路由表项。若路由表中有目的地址为D的特定主机地址，则将分组传送给该路由表项所指明的下一跳地址，完成分组转发；否则，执行。,18,判断特定网络路由表项。对每一条路由表项：用子网掩码和D逐比特相“与”，若结果与本路由表项中的目的网络地址相同，则将分组传送给该路由表项指明的下一跳地址，完成分组转发；否则，执行 。判断默认路由表项。若路由表中有一个默认路由表项，则将分组传送给该路由表项指明的下一跳地址，完成分组转发；否则，执行 。报告转发分组出错。,19,路由选择流程,20,路由器转发IP分组时，从某一条路由表项中得到下一跳地址后，并不是将下一跳地址填入到该IP分组首部，而是把它送交给下层的网络接口软件。网络接口软件负责将下一跳地址映射到硬件地址（使用ARP协议），通过数据链路层的帧把该IP分组发送到下一跳路由器。,否,4.3 无分类域间路由选择（CIDR）Classless Inter-Domain Routing,CIDR的基本思想是：适当分配多个合适的IP地址，使得这些地址能够进行聚合，减少这些地址在路由表中的表项数。,21,CIDR也称为超网(supernetting)，是防止因特网路由表膨胀的另一种方法。“无分类”的含义是指可以不考虑IP地址所属的A类、B类或C类的区别，路由决策完全基于整个32位IP地址的掩码来操作。,CIDR的思想最初是基于标准的C类地址提出的，但并不局限于C类地址，可以把地址聚合的思想扩展到对子网地址的聚合中。,地址聚合的步骤,把点分十进制表示的网络地址转换成二进制形式；提取地址中的相同部分，对剩余不同部分按位数的全排列进行划分，得到多块地址。对每一块地址聚合成一个地址。计算掩码值。,22,例:把下面的4个C类网络地址，实现地址聚合。 200.41.24.0 200.41.25.0 200.41.26.0 200.41.27.0,23,例: 地址聚合后路由表的变化,24,有效地址聚合，需满足的特性,多个IP地址进行聚合，必须具有相同的高位地址。路由表和路由选择算法基于32bit的IP地址和32bit的掩码。路由协议要支持32bit掩码的传输，如OSPF和RIP v2都能够携带32bit的掩码。,25,IP地址类的提出是为了便于区分地址的网络部分和主机部分，减少路由表的表项，但CIDR的出现，打破了IP地址类的概念，通过IP地址和掩码的结合来决定地址的网络部分和主机部分，从而减少路由表的表项。,4.4 内部和外部路由协议,因特网将整个互联网划分为许多较小的自治系统（Autonomous System，简称AS）。一个AS通常代表一个独立的组织机构，同时，一个AS是由若干个路由器组成的一个互联网络，并由本组织机构内的管理员进行管理，有权决定在本AS内所采用的路由选择协议。,26,一个AS内的网络必须是连通的。如果一个机构管辖两个互联网，但这两个网络通过其他的主干网络互连，那么尽管这两个互联网属于同一个机构，还是不能构成一个AS，它们属于两个AS。,AS 特 征,每个有一个16位的标识符，由因特网注册机构或ISP分配。16451265535,27,ISP，共享ISP路由策略,某机构,可使用私有AS标识符,网络,需使用ISP注册的AS标识符,NAT,留作私用,路由选择协议分类,1)内部网关协议 IGP, Interior Gateway Protocol在一个AS内部使用的路由选择协议。e.g. RIP、 OSPF2)外部网关协议 EGP, External Gateway Protocol在AS之间使用的路由选择协议。e.g. BGP-4,28,互联网的路由协议关系,29,4.4.1 理想的路由选择算法,当路由器转发分组时，必须有路由表可供查找。路由表应指明分组的最佳路径。路由表可以是静态或动态的。如何得到动态路由表？这就是路由选择协议要解决的问题。,30,1. 度量 Metric,度量就是给通过某个网络所指派的代价。一个特定路由的总度量等于组成该路由的所有网络的度量之和。路由器选择具有最小度量的路由。,31,2. 理想路由选择算法的特点,正确性和完整性。简单性。自适应性。稳定性。公平性。最佳性。,路由协议一般会采用以下两种基本的路由算法中的一种，即距离向量（Distance vector）法或链路状态（Link state）法。一个实际的路由选择算法，应尽可能接近于理想的算法。实际上路由选择很复杂，路由环境变化迅速，无法预先获知。,32,目前有多种路由选择协议生成动态路由表。路由选择协议是一些规则和过程的组合，使得在互联网中的各种路由器能彼此互相通告变化，路由选择协议使得路由器能共享所知的互联网情况或邻站情况。,33,4.4.2 路由信息协议(RIP),路由信息协议（Routing Information Protocol，简称RIP）是在同一个自治系统内路由器之间传送路由的最常用协议。RIP是一个基于距离向量路由选择的协议。,34,RIP协议工作原理,互联网中的每一个路由器保留一个路由表，路由表由多个路由表项构成，每一个表项表示到达一个目的网络的路由。路由表项包括：目的网络地址、到达目的网络的最短距离、为到达最终目的网络而必须把分组交付到的下一跳。,35,RIP是基于距离向量的路由协议，把到达目的网络的“距离”作为选择路由的度量。每经过一个路由器，跳数增加1，即距离增加1。,一个互联网的拓扑结构,36,图4-11,初始状态路由表,37,图4-12,路由表中只有直接相连的网络,图4-13 RIP路由更新算法,38,图4-14 路由器B路由表的更新,39,图4-15 路由器D路由表的更新,40,邻站B来的路由表,邻站D来的路由表,A的旧路由表,A的新路由表,距离向量路由算法,图4-16 路由器A路由表的更新,41,各路由器的最终路由表,42,图4-17,RIP中的3个计时器,定期计时器截止期计时器无效信息计时器,43,用于控制定期发送更新报文。,用来管理路由的有效性，每一条路由表项有自己的截止期。,用来管理无效的路由表项，每一条路由表项有自己的无效信息计时器。,RIP通过发送更新报文传送邻站路由表的信息。何时发送更新报文？怎么标识路由表中路由的有效性？怎么删除无效的路由表项？通过3个定时器。,RIP的特点,RIP协议适用于小型网络。RIP协议是基于距离向量路由选择的协议。不能保证所选择的是最快的路径。,44,RIP协议定期更新路由表。RIP v1协议是一个有类别路由协议，在RIP v1报文中不传送掩码地址。RIP v2协议是一个无类别路由协议。,RIP v1报文格式,45,路由条目1,路由条目n,46,RIP报文,数据,UDP首部,RIP报文封装,RIP协议的局限性,47,增加一个网络Net1,图4-20,表4-6 增加网络Net1后路由表的变化,48,RIP协议的局限性,删除一个网络Net1,49,图4-21,表47 删除网络Net1后路由表的变化,50,RIP的一个特点：对增加一个新网络的好消息传播较快，而对删除一个故障网络的坏消息传播很慢。怎样加快坏消息的传播？,51,发送路由更新报文时，路由器必须区分不同的接口。如果路由器从某个接口已经收到了路由更新报文，那么同样的更新报文不再通过这个接口回送过去。避免出现循环更新现象。,若网络没有变化，则按通常的30s间隔发送更新报文。而一旦有变化，路由器就立即发送更新报文。可避免按增量发送的更新报文所引起的任何兜圈子的问题。,RIPv2协议,52,路由条目,扩展特性包括无类别路由协议，可以使用可变长子网掩码，通过携带子网掩码来实现。相对v1，采用多播方式更新路由。本地网络上和RIP路由选择无关的设备不需浪费时间解析路由器广播的更新报文。,4.4.3 开放最短路径优先协议(OSPF),开放最短路径优先（Open Shortest Path First, 简称OSPF）是目前流行的另一种内部路由选择协议。它是基于开放标准的链路状态路由选择协议。,53,OSPF协议可以支持多种类型的度量，但是默认的度量是带宽。一个路由器通过度量值决定最佳路径，度量值越低，路径越佳。如果到一个目的站有多条不同度量值的路径，则选择较低度量值的路径放在路由表中。,区域（Area）区域是自治系统中网络、主机和路由器的一个集合。在一个区域里的所有网络必须是互相连接的，并使用洪泛法Flooding传送路由选择信息。,54,自治系统中的区域,55,内部路由器主干路由器区域边界路由器(Area Border Router)自治系统边界路由器(AS Border Router),位于运行OSPF协议和其他路由协议的两个自治系统的边界上，可以配置ASBR实现非OSPF路由通告到所有区域。,OSPF路由器类型,56,所有接口包含在一个单个的OSPF区域中，它并不运行其他的路由协议。,是在主干区域中的路由器。一个主干路由器至少有一个接口与区域0相连。,处在一个区域的边界，把有关本区域的信息汇总起来发送给其他区域。,链路状态路由选择,57,OSPF协议使用链路状态路由选择生成一个区域内的最短路径。基于一个基本假设：如果一个自治系统中的某条路径在每个区域内路径都最短，那么在整个自治系统内该路径一定最短。,数据库,邻站数据库（邻接表）链路状态数据库（网络拓扑图）转发数据库（路由表）,58,对于OSPF路由器而言，首先需要知道哪些是与它直接相连的邻站，即得到邻站数据库。,在一个区域内的每一个路由器从所有其他路由器接收链路状态通告，构成一个链路状态数据库。从这个数据库中每个路由器创建一个树结构，并把它自己标识为通过最短路径与每个目的站相连的根。,采用链路状态数据库形成转发数据库。,OSPF的特点,公开发布了各种规范。它是一个开放标准。支持服务类型路由。易于网络扩展和管理。提供负载均衡功能。提供鉴别功能。支持多播。属于无类别路由选择协议。,59,OSPF报文传输流程,60,OSPF报文,数据,IP首部,OSPF报文首部格式,61,图4-26 公共首部,问候报文格式 (Hello),62,数据库描述报文(Database Description),63,64,链路状态请求报文(Link Status Request),链路状态更新报文(Link Status Update),65,66,图431 链路状态通告的首部格式,路由器链路网络链路汇总链路到网络汇总链路到自治系统边界路由器外部链路,5. 链路状态确认报文,67,4.4.4 边界网关协议BGP,边界网关协议（Border Gateway Protocol，简称BGP）是自治系统之间的路由选择协议。 BGP的任务是在自治系统之间交换路由信息，同时确保无环路的路径选择。,68,为什么距离向量路由选择和链路状态路由选择不适合在自治系统之间进行路由选择？路径向量路由选择的路由表中除了包含目的网络、下一个路由器，还包括到达目的站点的路径。,69,路径向量路由选择中，各自治系统的自治边界路由器通告在其自治系统中的网络到各相邻自治边界路由器的可达性。这里“相邻”是指连接到同一个网络上的两个自治边界路由器。,距离向量路由选择基于最小距离选择路由，实际上，在有些情况下具有最小跳数的路由并不是最佳的路由。例如不安全性、不稳定性。,链路状态路由选择也不适合于自治系统之间的路由选择，因为如要对整个互联网使用链路状态路由选择，每一个路由器需要一个庞大的链路状态数据库，就会花费大量时间。,BGP工作原理,在一个BGP网络中有四种不同类型的路由器： BGP发言者路由器 对等路由器 内部对等路由器 外部对等路由器,70,通过BGP进行直接通信的路由器,两个或多个进行直接通信的BGP发言者路由器,在同一个自治系统中的BGP发言者路由器,自治系统间的BGP发言者路由器,BGP根据在BGP邻站之间交换的信息来建立一张自治系统图。从BGP的角度来看，整个互联网络就是由自治系统组成的一张图或树。任何两个自治系统之间的连接就形成一条路径，路径信息的集合由一个自治系统号码序列表示，该序列构成一条去往特定目的站的路由。,路径向量分组,71,图433,72,图4-33所示网络中路由器的路由表,BGP的特点, 是自治系统间的通信协议。 支持策略路由。 避免了路由回路。 支持CIDR编址。,73,74, 支持路由聚合。 支持鉴别。 实现可靠传输。 实现增量更新。,BGP在一定程度上综合了距离向量和链路状态路由选择的优点，是一种路径向量协议。被称为路径向量协议的原因在于BGP路由信息中包含着自治系统编号的一个序号，这个序列指明了路由经过的路径。利用此信息可建立起各自治系统的连接图，从而避免路由循环。,BGP报文类型,75,76,BGP报文公共首部,打开报文,运行BGP的对等路由器通过TCP连接，创建邻站关系。首先发送打开报文，若邻站响应保活报文，则这两个对等路由器之间就建立了邻站关系。,77,更新报文,更新报文是BGP的核心。路由器使用更新报文来撤销以前已通告的目的站和（或）宣布到一个新目的站点的路由。更新报文中一次可以撤销多个已通告的目的站，但在单个更新报文中只能通告一个新的目的站。,78,保活报文,在保活期内，对等路由器之间通过传递保活报文，告诉对方自己正处于工作状态。保活报文只包含BGP的公共首部。,79,通知报文,路由器检测出差错或打算关闭TCP连接时，就发送通知报文。定义了多种差错码含义。,80,BGP报文基于建立的TCP连接进行传输，BGP报文封装在TCP报文段中，并使用熟知端口179。因为BGP使用TCP连接，所以BGP具有可靠和面向连接的特性，不需要另外的差错控制和流量控制。当建立TCP连接后，更新报文、保活报文和通知报文就一直交换直至通知停止。,81,静态路由表由网管在系统安装时根据网络的配置情况预先设定，网络结构发生变化后由网管手工修改路由表。适合于网络传输状态比较简单的环境。,动态路由随网络运行情况的变化而变化，路由器根据路由协议提供的功能自动计算数据传输的最佳路径，由此得到动态路由表。,总结 ：常用路由协议分析比较,路由分为静态路由和动态路由，相应的路由表称为静态路由表和动态路由表。,82,根据路由算法,距离向量路由协议动态路由协议 链路状态路由协议,83,RIP、IGRP在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器。,OSPF在链路状态路由协议中，路由器将链路状态信息传递给在同一区域内的所有路由器。,根据路由器在AS中的位置,内部网关协议路由协议 外部网关协议/域间路由协议 外部网关协议EGP域间路由协议 边界网关协议BGP,84,EGP是一个简单树型拓扑结构，目前已被BGP代替。,EIGRP是一个Cisco公司的私有协议，是一种混合协议，它既有距离向量路由协议的特点，同时又继承了链路状态协议的优点。,85,距离向量路由和链路状态路由协议对比,距离向量指协议使用跳数或向量来确定从一个设备到另一个设备的距离。不考虑每条链路的速率。距离向量路由协议不仅造成了网