路由routing的概念

1、第四章 IP路由,路由（routing）的概念,路由就是在网络层选择传输路径的处理过程，有两种形式： 直接路由：目的主机与源主机在同一个子网中，它们之间能直接交换IP数据包。 间接路由：目的主机与源主机不在同一个子网中，需要通过一个或多个路由器（网关）间接转发传递。,路由表和目的地址,路由表保存着目的IP地址和下一个网关地址的映射关系。 路由器中共有四种目的地址： 与路由器在同一子网的目的主机或网络地址 路由器中明确定义的目的主机或网络地址 由路由器收到的ICMP重定向消息所确定的目的主机或网络地址 所有其它的目的主机或网络地址,缺省网关（default gateway）,0.0.0.0 0.0.0.0 对应的网关 匹配到任何目的地址的数据包 如果没有其他的匹配，使用这个网关,（可）被路由的协议和路由协议,（可）被路由的协议（routed protocol） IP、IPX等 NETBEUI协议是不可路由的协议 路由协议（routing protocol） 路由器之间用来生成路由表的协议 静态路由、RIP、OSPF、BGP,缺省网关（default gateway）,0.0.0.0 0.

2、0.0.0 对应的网关 匹配到任何目的地址的数据包 如果没有其他的匹配，使用这个网关,有类和无类路由协议,有类路由协议（Classful Routing Protocol） IP RIPv1 IGRP IPX RIP (Novell) RTMP (Apple) 无类路由协议（Classless Routing Protocol） EIGRP OSPF IS_IS NLSP (Novell) IP RIPv2,有类路由协议,在跨多个子网通信时不携带子网掩码信息，所有子网使用的子网掩码都是一样的，只使用某类网络地址的缺省网络掩码。 造成IP地址的浪费。,无类路由协议和VLSM,无类路由协议是一种能够携带子网掩码信息的路由协议。 可变长度子网掩码VLSM（VariableLength Subnet Masking）是指在一网络的不同位置可使用不同的子网掩码。 VLSM可灵活分配IP地址，充分利用地址空间。 VLSM只能与无类路由协议一起使用。,无类域间路由选择CIDR,地址分配问题：很多B类地址都已分配，且浪费严重；若剩余的C类地址（数量多，192.0.0.0223.255.255.255）

3、的分配方式不当，会对路由表的管理造成严重后果。 CIDR（Classless Interdomain Routing）是用可变长分块（多个连续的IP地址，具有相同的掩码）的方式分配网络地址。 全世界被划分为4个区，每个区分配一部分C类地址：,路由汇总（route summarization）,路由汇总是一种允许路由器使用路由表中的单个条目指向多条不同的网络路径的技术。具有两种好处： 减少路由表的大小。 减少路由转发处理过程。 只有在地址连续的情况下可以使用路由汇总。或者说只有当IP地址具有相同的高位地址位时，才可配置路由汇总。CIDR地址块就可以用于配置路由汇总。,路由表查找的例子,路由器的路由表中存有三条网络的路由信息，当目的地址为194.24.17.4的分组到达时应怎样处理？,路由表查找：最长匹配,R2,R3,R4,All 10/8 except 10.1/16,10.1/16,路由表查找：最长匹配,R2,R3,R4,All 10/8 except 10.1/16,10.1/16,10.1.1.1 & FF.0.0.0 is equal to 10.0.0.0 & FF.0.0.0

4、,Match!,路由表查找：最长匹配,R2,R3,R4,All 10/8 except 10.1/16,10.1.1.1 & FF.FF.0.0 is equal to 10.1.0.0 & FF.FF.0.0,Match as well!,10.1/16,路由表查找：最长匹配,R2,R3,R4,All 10/8 except 10.1/16,10.1.1.1 & FF.0.0.0 isnt equal to 20.0.0.0 & FF.0.0.0,Does not match!,10.1/16,路由表查找：最长匹配,R2,R3,R4,All 10/8 except 10.1/16,Longest match, 16 bit netmask,10.1/16,Internet上的两类路由协议,Internet是由大量的AS组成，各个AS由不同机构操纵。 在AS内部，路由选择的目的是要将分组尽可能高效地（最佳路径）从源端发送到目的端 ，这种路由选择算法称作内部网关协议IGP（Interior Gateway Protocol）。如RIP和OSPF。 在AS之间，路由器除了要处理AS间汇总信

5、息的交换，路由选择还必须考虑大量的策略（politic）问题，这种路由选择算法称为外部网关协议EGP（Exterior Gateway Protocol）。如BGP。,路由信息协议RIP,RIP（Route Information Protocol）是一种基于距离矢量路由算法（distance vector routing）的，用于小型AS中的路由协议。 路由器在以下三种情况下以响应报文的形式向外公告本地的距离矢量信息： 每隔30秒自动发送一次 对其它路由器发来的请求报文进行响应 当本地距离矢量表发生变化时而进行的触发式更新 路由器收到响应报文后，将更新信息和本地距离矢量表进行比较，选取代价更低的路由更新本地距离矢量表。,RIP的报文格式,RIP使用UDP的520端口来收发RIP的报文，长度不超过512字节，一个512字节的RIP报文最多允许包含25个路由表项。,1：请求2：响应,版本为1,路由表项（25）,IP的地址簇标识符为2,缺省为全0,115,RIP的操作模式,主动模式：路由器即公告自己的距离矢量信息，也接收邻居的路由信息。 被动模式：路由器只接收邻居的路由信息。一般端节点配置

6、该种模式。,RIP工作原理示意,无穷计算(count-to-infinity)的问题,收敛慢：特别是它对好消息的反应迅速，但对坏消息却反应迟钝。 其对坏消息的反应迟钝，会造成相互交换的矢量信息错误，最终导致无穷计算的后果。 在实际使用中，可通过设置距离的最大值（如设置为网络最长路由加1）来扼制这种无限的增长。RFC定义为16。 水平分割算法是解决无穷计算的一种有效方法，每个节点不向需经过的相邻节点发送路由信息（实际上报告距离为无穷大）。,无穷计算示意图,RIP-2,RIP-2类式RIP-1，主要增加的功能有： 支持CIDR和VLSM 支持组播 支持认证 完全兼容RIP-1,RIP-2的报文格式,1：请求2：响应,版本为2,当该域为0xFFFF时，为认证表项,为全0,115,第一个表项既可作为认证表项，也可作为路由表项。,路由表项（24）,0：没有认证2：密码认证,IP的地址簇标识符为2,密码数据,用于区分内部路由和外部路由,开放式最短路径优先OSPF,Internet上的IGP的发展： 最初采用基于DVR的RIP。 1979年5月替换成LSR。 1988年IETF开发称作OSPF（Op

7、en Shortest Path First）的LSR后继版本。 1990年OSPF成为标准，现在成为大型网络环境中广泛采用的路由协议。,OSPF的特点,支持负载均衡 支持分级路由 支持认证 收敛速度快 支持CIDR和VLSM 支持各种距离度量，如hops，delays，costs等 支持IP隧道技术,用图代表实际网络并计算最佳路由,OSPF中的一些概念,一个大型的AS可分成若干32位编号的区域（area），每个AS都有一个主干（backbone）区域，称为区域0。所有区域都与主干相连（可能要经过隧道）。 4类路由器：内部路由器，区域边界路由器，主干路由器，AS边界路由器。每个路由器都被分配一个唯一的32位的路由器标识符RID（Route ID）。 每个LAN选择一个称作指定路由器（designated router）的路由器来作为LAN中其它路由器的代表，它被认为与其它所有路由器邻接（adjacent），路由器之间必须通过邻接路由器交换信息。相邻的非指定路由器之间没有邻接关系。,OSPF中AS、主干和区域之间的关系,OSPF中的工作原理,区域内：利用扩散法，每个路由器将它的邻居和开销

8、信息告诉给本区域中的所有其它路由器，这些信息使每个路由器都能构造出一个本区域的有向图，并计算最短路径。 区域间：主干路由器从区域边界路由器处获取信息，计算出每个主干路由器到每个其它路由器的最佳路径。这一信息再传回区域边界路由器，由该路由器在它的区域中进行广播。这样一个要发送区域间分组的路由器就可选择一个去往主干的最佳出口路由器,链路状态路由选择算法的步骤,找出所有可达的相邻节点及它们的网络地址； 测定到这些相邻节点的代价； 将以上信息构成链路状态分组（link state packet）； 向网上所有节点发送链路状态分组； 利用收到的链路状态分组计算到各目的节点的最短通路。,了解相邻节点,每个路由器启动后，首先在所有与之相连的点-点线路上发送一个特殊的询问分组（HELLO分组），线路另一端的路由器收到后必须发回一个响应来告知它是谁（其网络地址）。,测量线路代价（cost）,路由器在链路上发送一个要求对方立即响应的特殊回声（ECHO）分组，将回声分组的来回时间除以2即得到该链路的延迟时间（代价）。一般重复若干次，取平均值。,构造链路状态分组,每个链路状态分组包括源节点的网络地址、分组的序

9、号和寿命，然后是一系列相邻节点的网络地址和去往该节点的链路代价。 决定何时创建链路状态分组一般有两种方法： 定期创建链路状态分组。 探测到网络连接发生变化时再创建链路状态分组。,发送链路状态分组,通过改进的扩散法（记录分组扩散路径：每个路由器维护一张带有源节点和最大分组序号的表，对来自于同一个源节点的重复分组（分组序号表中序号）不转发）向网上所有其它节点发送链路状态分组。 所有的链路状态分组都要应答。当线路空闲时，从缓冲区中选择发送一个分组或应答。 为了保证高效可靠地发送链路状态分组，需采取如下一些措施： 将分组序号长度设为32位可防止序号重叠太快，若每隔1秒发送一个分组，可发137年不重复。 为每个分组规定一个寿命，分组在路由器中时，其寿命每隔1秒就减1，直到减为0被抛弃。可解决路由器崩溃及分组序号传输出错等造成新旧分组不分的问题。,计算新的路由,当一个路由器收集齐了所有的链路状态分组后，便可构造出整个网络的拓扑带权图； 通过最短通路路由选择算法就可确定到达所有其它节点的最短路径； 将此结果存入路由选择表中达到更新目的。,最佳原理和接收树,当计算两点之间的最佳路由时，存在一个最佳原理（optimality principle）：如果J位于I到K的最佳路由上，则J到K的最佳路由也必定落在该路由上。可通过反证求得。 根据最佳原理可以推出，所有源节点到一个给定目的节点的最佳路由的集合组成一棵以该目的节点为根的树，称为该目的节点的接收树（sink tree）。接收树并不是唯一的。,最短通路路由选择算法,最短通路（shortest path）路由选择算法属于自适应路由算法。它将一个通信子网抽象成一张图，图中的顶点代表网络节点（路由器），弧线代表通信线路，弧线上的权代表相邻顶点间的“距离”（可为物理上的距离，或指分组在其间的传输时间，也可指线路上的通信费用等）。任意一对顶点之间的最小权值即为它们的最短通路。 求任意一对顶点之间的最短通路可有很多方法，其中迪杰斯特拉（Dijkstra）提出了按通路长度递增的次序产生最短通路的算法，基本思想为： 首先从起始点出发，找出距起始点最短的通路，然后在此基础上找出距起始点次短的通路，如此每次都找出比前一次次短的通路，直至某个通路到达给定的目的，这时所得到的通路就

《路由routing的概念》由会员suns****4568分享，可在线阅读，更多相关《路由routing的概念》请在金锄头文库上搜索。