IP路由概念和工作原理

1、IP路由概念和工作原理路由（routing）的概念路由就是在网络层选择传输路径的处理过程，有两种形式：直接路由：目的主机与源主机在同一个子网中，它们之间能直接交换IP数据包。间接路由：目的主机与源主机不在同一个子网中，需要通过一个或多个路由器（网关）间接转发传递。路由表和目的地址路由表保存着目的IP地址和下一个网关地址的映射关系。路由器中共有四种目的地址：与路由器在同一子网的目的主机或网络地址路由器中明确定义的目的主机或网络地址由路由器收到的ICMP重定向消息所确定的目的主机或网络地址所有其它的目的主机或网络地址缺省网关（default gateway）0.0.0.0 0.0.0.0 对应的网

2、关匹配到任何目的地址的数据包如果没有其他的匹配，使用这个网关（可）被路由的协议和路由协议（可）被路由的协议（routed protocol）IP、IPX等NETBEUI协议是不可路由的协议路由协议（routing protocol）路由器之间用来生成路由表的协议静态路由、RIP、OSPF、BGP缺省网关（default gateway）0.0.0.0 0.0.0.0 对应的网关匹配到任何目的地址的数据包如果没有其他的匹配，使用这个网关有类和无类路由协议有类路由协议（Classful Routing Protocol）IP RIPv1IGRPIPX RIP (Novell)RTMP (Apple

3、)无类路由协议（Classless Routing Protocol）EIGRPOSPFIS_ISNLSP (Novell)IP RIPv2有类路由协议在跨多个子网通信时不携带子网掩码信息，所有子网使用的子网掩码都是一样的，只使用某类网络地址的缺省网络掩码。造成IP地址的浪费。无类路由协议和VLSM无类路由协议是一种能够携带子网掩码信息的路由协议。可变长度子网掩码VLSM（VariableLength Subnet Masking）是指在一网络的不同位置可使用不同的子网掩码。VLSM可灵活分配IP地址，充分利用地址空间。VLSM只能与无类路由协议一起使用。无类域间路由选择CIDR地址分配问题：

4、很多B类地址都已分配，且浪费严重；若剩余的C类地址（数量多，）的分配方式不当，会对路由表的管理造成严重后果。CIDR（Classless Interdomain Routing）是用可变长分块（多个连续的IP地址，具有相同的掩码）的方式分配网络地址。全世界被划分为4个区，每个区分配一部分C类地址：路由汇总（route summarization）路由汇总是一种允许路由器使用路由表中的单个条目指向多条不同的网络路径的技术。具有两种好处：减少路由表的大小。减少路由转发处理过程。只有在地址连续的情况下可以使用路由汇总。或者说只有当IP地址具有相同的高位地址位时，才可配置路由汇总。CIDR地址块就可以

5、用于配置路由汇总。路由表查找的例子路由器的路由表中存有三条网络的路由信息，当目的地址为的分组到达时应怎样处理？路由器S1: 194.24.0.0/21Packet: DestinationIP address: 194.24.17.4S2: 194.24.16.0/20S3: 194.24.8.0/22S1: 8CS3: 4CS2: 16C路由表查找：最长匹配R2R3R1R4All 10/8 exceptPacket: DestinationIP address: 10.1.1.110/8 - R310.1/16 - R420/8 - R530/8 - R6.R2s IP routing ta

6、ble路由表查找：最长匹配R2R3R1R4All 10/8 except10/8 - R310.1/16 - R420/8 - R5.R2s IP routing table10.1.1.1 & is equal toMatch!Packet: DestinationIP address: 10.1.1.1路由表查找：最长匹配R2R3R1R4All 10/8 except10/8 - R310.1/16 - R420/8 - R5.R2s IP routing table10.1.1.1 & is equal toMatch as well!Packet: DestinationIP addr

7、ess: 10.1.1.1路由表查找：最长匹配R2R3R1R4All 10/8 except10/8 - R310.1/16 - R420/8 - R5.R2s IP routing table10.1.1.1 & isnt equal toDoes not match!Packet: DestinationIP address: 10.1.1.1路由表查找：最长匹配R2R3R1R4All 10/8 except10/8 - R310.1/16 - R420/8 - R5.R2s IP routing tableLongest match, 16 bit netmaskPacket: Dest

8、inationIP address: 10.1.1.1Internet上的两类路由协议Internet是由大量的AS组成，各个AS由不同机构操纵。在AS内部，路由选择的目的是要将分组尽可能高效地（最佳路径）从源端发送到目的端 ，这种路由选择算法称作内部网关协议IGP（Interior Gateway Protocol）。如RIP和OSPF。在AS之间，路由器除了要处理AS间汇总信息的交换，路由选择还必须考虑大量的策略（politic）问题，这种路由选择算法称为外部网关协议EGP（Exterior Gateway Protocol）。如BGP。路由信息协议RIPRIP（Route Informa

9、tion Protocol）是一种基于距离矢量路由算法（distance vector routing）的，用于小型AS中的路由协议。路由器在以下三种情况下以响应报文的形式向外公告本地的距离矢量信息：每隔30秒自动发送一次对其它路由器发来的请求报文进行响应当本地距离矢量表发生变化时而进行的触发式更新路由器收到响应报文后，将更新信息和本地距离矢量表进行比较，选取代价更低的路由更新本地距离矢量表。RIP的报文格式RIP使用UDP的520端口来收发RIP的报文，长度不超过512字节，一个512字节的RIP报文最多允许包含25个路由表项。命令(1B)版本(1B)保留(2B)AFI (2B)保留(2B)

10、IP地址(4B)保留(24B)度量(4B)1：请求2：响应版本为1路由表项（25）IP的地址簇标识符为2缺省为全0115RIP的操作模式主动模式：路由器即公告自己的距离矢量信息，也接收邻居的路由信息。被动模式：路由器只接收邻居的路由信息。一般端节点配置该种模式。RIP工作原理示意无穷计算(count-to-infinity)的问题收敛慢：特别是它对好消息的反应迅速，但对坏消息却反应迟钝。其对坏消息的反应迟钝，会造成相互交换的矢量信息错误，最终导致无穷计算的后果。在实际使用中，可通过设置距离的最大值（如设置为网络最长路由加1）来扼制这种无限的增长。RFC定义为16。水平分割算法是解决无穷计算的一

11、种有效方法，每个节点不向需经过的相邻节点发送路由信息（实际上报告距离为无穷大）。无穷计算示意图RIP-2RIP-2类式RIP-1，主要增加的功能有：支持CIDR和VLSM支持组播支持认证完全兼容RIP-1RIP-2的报文格式命令(1B)版本(1B)保留(2B)AFI(2B)认证类型(2B)认证数据(16B)AFI (2B)路由标志(2B)IP地址(4B)子网掩码(4B)下一跳(4B)度量(4B)1：请求2：响应版本为2当该域为0 xFFFF时，为认证表项为全0115第一个表项既可作为认证表项，也可作为路由表项。路由表项（24）0：没有认证2：密码认证IP的地址簇标识符为2密码数据用于区分内部路

12、由和外部路由开放式最短路径优先OSPFInternet上的IGP的发展：最初采用基于DVR的RIP。1979年5月替换成LSR。1988年IETF开发称作OSPF（Open Shortest Path First）的LSR后继版本。1990年OSPF成为标准，现在成为大型网络环境中广泛采用的路由协议。OSPF的特点支持负载均衡支持分级路由支持认证收敛速度快支持CIDR和VLSM支持各种距离度量，如hops，delays，costs等支持IP隧道技术用图代表实际网络并计算最佳路由OSPF中的一些概念一个大型的AS可分成若干32位编号的区域（area），每个AS都有一个主干（backbone）区域

13、，称为区域0。所有区域都与主干相连（可能要经过隧道）。4类路由器：内部路由器，区域边界路由器，主干路由器，AS边界路由器。每个路由器都被分配一个唯一的32位的路由器标识符RID（Route ID）。每个LAN选择一个称作指定路由器（designated router）的路由器来作为LAN中其它路由器的代表，它被认为与其它所有路由器邻接（adjacent），路由器之间必须通过邻接路由器交换信息。相邻的非指定路由器之间没有邻接关系。OSPF中AS、主干和区域之间的关系OSPF中的工作原理区域内：利用扩散法，每个路由器将它的邻居和开销信息告诉给本区域中的所有其它路由器，这些信息使每个路由器都能构造出

14、一个本区域的有向图，并计算最短路径。区域间：主干路由器从区域边界路由器处获取信息，计算出每个主干路由器到每个其它路由器的最佳路径。这一信息再传回区域边界路由器，由该路由器在它的区域中进行广播。这样一个要发送区域间分组的路由器就可选择一个去往主干的最佳出口路由器链路状态路由选择算法的步骤找出所有可达的相邻节点及它们的网络地址；测定到这些相邻节点的代价；将以上信息构成链路状态分组（link state packet）；向网上所有节点发送链路状态分组；利用收到的链路状态分组计算到各目的节点的最短通路。了解相邻节点每个路由器启动后，首先在所有与之相连的点-点线路上发送一个特殊的询问分组（HELLO分组

15、），线路另一端的路由器收到后必须发回一个响应来告知它是谁（其网络地址）。测量线路代价（cost）路由器在链路上发送一个要求对方立即响应的特殊回声（ECHO）分组，将回声分组的来回时间除以2即得到该链路的延迟时间（代价）。一般重复若干次，取平均值。构造链路状态分组每个链路状态分组包括源节点的网络地址、分组的序号和寿命，然后是一系列相邻节点的网络地址和去往该节点的链路代价。决定何时创建链路状态分组一般有两种方法：定期创建链路状态分组。探测到网络连接发生变化时再创建链路状态分组。发送链路状态分组通过改进的扩散法（记录分组扩散路径：每个路由器维护一张带有源节点和最大分组序号的表，对来自于同一个源节点的

16、重复分组（分组序号表中序号）不转发）向网上所有其它节点发送链路状态分组。所有的链路状态分组都要应答。当线路空闲时，从缓冲区中选择发送一个分组或应答。为了保证高效可靠地发送链路状态分组，需采取如下一些措施：将分组序号长度设为32位可防止序号重叠太快，若每隔1秒发送一个分组，可发137年不重复。为每个分组规定一个寿命，分组在路由器中时，其寿命每隔1秒就减1，直到减为0被抛弃。可解决路由器崩溃及分组序号传输出错等造成新旧分组不分的问题。前图中路由器B的分组缓冲区，包含新近到达还未处理完毕的分组。计算新的路由当一个路由器收集齐了所有的链路状态分组后，便可构造出整个网络的拓扑带权图；通过最短通路路由选择

17、算法就可确定到达所有其它节点的最短路径；将此结果存入路由选择表中达到更新目的。最佳原理和接收树当计算两点之间的最佳路由时，存在一个最佳原理（optimality principle）：如果J位于I到K的最佳路由上，则J到K的最佳路由也必定落在该路由上。可通过反证求得。根据最佳原理可以推出，所有源节点到一个给定目的节点的最佳路由的集合组成一棵以该目的节点为根的树，称为该目的节点的接收树（sink tree）。接收树并不是唯一的。最短通路路由选择算法最短通路（shortest path）路由选择算法属于自适应路由算法。它将一个通信子网抽象成一张图，图中的顶点代表网络节点（路由器），弧线代表通信线路

18、，弧线上的权代表相邻顶点间的“距离”（可为物理上的距离，或指分组在其间的传输时间，也可指线路上的通信费用等）。任意一对顶点之间的最小权值即为它们的最短通路。求任意一对顶点之间的最短通路可有很多方法，其中迪杰斯特拉（Dijkstra）提出了按通路长度递增的次序产生最短通路的算法，基本思想为：首先从起始点出发，找出距起始点最短的通路，然后在此基础上找出距起始点次短的通路，如此每次都找出比前一次次短的通路，直至某个通路到达给定的目的，这时所得到的通路就是源到目的的最短通路。具体可采用标记方法。利用Dijkstra算法求A到D的最短通路ABCEFGHD22164273223AB(2,A)E(,-)G(

19、6,A)C(,-)F(,-)H(,-)D(,-)AB(2,A)E(4,B)G(6,A)C(9,B)F(,-)H(,-)D(,-)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(,-)D(,-)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(9,G)D(,-)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(8,F)D(,-)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(8,F)D(10,H)AB(2,A)E(4,B)G(5,E)C(9,B)F(6,E)H(8,F)D(10,H)AB(2,A)E(4,B)G(5,E)C(9,

20、B)F(6,E)H(8,F)D(10,H)最短通路为：A-B-E-F-H-D，权值为10OSPF报文类型OSPF报文使用IP数据报（协议标识为89）进行传输。在广播环境中，发送到称为AllSPFRouter的保留组播地址。在非广播环境中，发送到特定邻居的IP地址。OSPF有五种类型的路由协议包，通过报文中的类型字段加以定义：“1”-Hello：发现和维护邻居关系“2”-数据库描述：LSA（Link State Advertisement）“3”-链路状态请求：向一个邻居路由器请求LSA“4”-链路状态更新：向一个邻居路由器提供LSA“5”-链路状态确认：对收到的LSA的确认OSPF报文头格式0

21、 78 1516 31版本：2类型：15报文长度：字节总长度路由器ID：包的源路由器地址区域ID：路由器接口的区域号校验和认证类型认证数据认证数据0=无认证 1=密码密码邻居通信每个路由器与网络中的其它路由器交换LSA，具体的过程有：发现邻居：交换Hello协议报文选择一个DR和BDR建立邻接关系与同步数据库数据库交换：交换数据库描述报文数据库装载：交换链路状态请求报文和链路状态更新报文Hello协议报文0 78 1516 31版本类型=1报文长度路由器ID区域ID校验和认证类型认证数据认证数据网络掩码（发送接口的子网掩码）HelloInterval选项路由器优先级RouterDeadInte

22、rvalDRBDR邻居路由器（本路由器的邻居列表）Hello协议报文说明HelloInterval：Hello协议报文传输之间的秒数。路由器优先级：用于DR的选取（选取优先级最高的；若相同，选IP地址最高的）。默认值为1。值0表示不能被选为DR。RouterDeadInterval：用于确定邻居是否出故障。若没有在指定的秒数内从已建立的邻居处收到Hello协议报文，则邻居宣布为故障，从邻居列表中删除。数据库描述报文0 78 1516 31版本类型=2报文长度路由器ID区域ID校验和认证类型认证数据认证数据00选项00000 I M MS数据库描述序列号LSA包头链路状态请求报文0 78 151

23、6 31版本类型=3报文长度路由器ID区域ID校验和认证类型认证数据认证数据LS类型链路状态ID宣告路由器链路状态更新报文0 78 1516 31版本类型=4报文长度路由器ID区域ID校验和认证类型认证数据认证数据LSA的数量数据库描述序列号LSA链路状态确认报文0 78 1516 31版本类型=5报文长度路由器ID区域ID校验和认证类型认证数据认证数据LSA头LSA头0 1516 2324 31LS寿命选项LS类型链路状态ID宣告路由器LS序列号LS校验和长度五种LS类型：“1”-路由器LSA，描述了区域内路由器接口（链路）的状态，由每个OSPF路由器产生。“2”-网络LSA ，列出了与一个

24、多路访问网络连接的所有路由器，由多路访问网段上的DR产生。“3”-汇总LSA ，描述了区域间的路由信息，由ABR产生。“4”-汇总LSA ，描述了到达ASBR的路径，由ABR产生。“5”-AS外部LSA ，描述了AS外部网络的路由信息，由ASBR产生。路由器LSA0 1516 2324 31LS寿命选项LS类型=1链路状态ID宣告路由器LS序列号LS校验和长度00000 V E B0链路数量链路ID链路数据类型TOS数量TOS 0的度量TOS0度量TOS0度量链路ID链路数据路由器LSA说明4种类型：“1”-点到点连接到其它路由器“2”-连接到传输网络“3”-连接到stub网络（只有一个出口路

25、径的区域）“4”-虚拟连接4种链路ID ：标识路由器的接口所连接的对象“1”-邻居路由器的路由器ID“2”-DR的IP地址“3”-IP网络/掩码“4”-邻居路由器的路由器IDOSPF的虚链路和传输网络ABRABR虚链路区域0区域1区域2 传输网络网络LSA0 1516 2324 31LS寿命选项LS类型=2链路状态ID宣告路由器LS序列号LS校验和长度网络掩码附着路由器汇总LSA0 1516 2324 31LS寿命选项LS类型=3或4链路状态ID宣告路由器LS序列号LS校验和长度网络掩码TOS度量AS外部LSA0 1516 2324 31LS寿命选项LS类型=5链路状态ID宣告路由器LS序列号

26、LS校验和长度网络掩码ETOS度量转发地址外部路由标志边界网关协议BGPBGP（Border Gateway Protocol）提供一种在AS之间交换路由信息的非循环方法。支持路由信息的聚集和汇总。BGP网络的组成部份OSPF/RIP BGP speakerOSPF/RIPOSPF/RIPOSPF/RIPAS 1OSPF/RIP BGP speakerOSPF/RIPAS 2OSPF/RIP BGP speakerOSPF/RIPAS 3OSPF/RIP BGP speakerOSPF/RIPIBGPOSPF/RIP BGP speakerIBGPEBGPEBGPAS xEBGPBGP的概念AS号是一个唯一标识一个AS的16位号码。如果两个BGP共享同一网络，则认为它们是相连的。根据BGP的连接，定义了三种AS（网络）：stub ASmulticonnected AStran