第四讲-动态路由(OSPF).

模拟软件已更新网络拓扑为：E0:192.168.1.254/24E0:192.168.2.254/24E0:192.168.3.254/24Router:lab_R3Router:lab_R2Router:lab_R1E1:192.168.10.1/30E2:192.168.10.5/30E2:192.168.10.6/30E2:192.168.10.10/30E1:192.168.10.2/30E1:192.168.10.9/30要求：所有计算机能互相Ping通PC_1_1PC_3_2PC_3_1PC_2_2PC_2_1PC_1_2X静态路由动手实验静态路由动手实验网络拓扑为：E0:192.168.1.254/24E0:192.168.2.254/24E0:192.168.3.254/24Router:lab_R3Router:lab_R2Router:lab_R1E1:192.168.10.1/30E2:192.168.10.5/30E2:192.168.10.6/30E2:192.168.10.10/30E1:192.168.10.2/30E1:192.168.10.9/30要求：所有计算机能互相Ping通PC_1_1PC_3_2PC_3_1PC_2_2PC_2_1PC_1_2（1）主要的动态路由选择协议—RIP（RoutingInformationProtocol）：适用于小型网络内，如小型校园网；—OSPF（OpenShortestPathFirstProtocol）、EIGRP：常用于中、大型网络内，如广域网、城域网和大型校园网；—BGP4（BorderGatewayProtocolv4）：用于大型网络之间的互联，如CERENT和ChinaNet之间。（2）动态路由选择协议分类按路由选择算法分，大致可分成3类：：—距离矢量路由选择（DistanceVector）：可确定到达任一网络的方向（矢量）和距离（跳数），如：RIP；—链路状态路由选择（LinkState）：重建整个网络精确拓扑结构，有较快的路由更新收敛速度，如：OSPF；—混合路由选择（HybridRouting）：是距离矢量和链路状态两种算法的结合，如：IS-IS，CiscoEnhancedIGRP。动态路由协议距离矢量路由选择算法(如：RIP)定期（30秒）在相邻路由器之间传送路由表的拷贝，计算可达网络的距离；路由器之间更新和交流网络拓扑结构的改变，但路由器不掌握全网络的确切拓扑结构。一个网络的初始状态如下图所示：网络W网络X网络Y网络Z路由器A路由器B路由器C路由表网络端口距离路由表网络端口距离路由表网络端口距离A1A2B1B2C1C2WA10XA20XB10YB20YC10ZC20路由收敛后的网络状态如下图所示：网络W网络X网络Y网络Z路由器A路由器B路由器C路由表网络端口距离路由表网络端口距离路由表网络端口距离A1A2B1B2C1C2WA10XA20XB10YB20YC10ZC20YA21B11WXC11WC12ZB21ZA22路由收敛后每个路由器知道到达每个网络该从哪个方向走，且知道到达每个网络的跳数（距离）是多少。距离矢量路由选择算法网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2XD22路由表网络端口距离XB12路由表网络端口距离XE10路由器CB1B2路由表网络端口距离XC23A3E1E1路由表网络端口距离XA31初始状态路由器D距离矢量路由选择算法中的路由循环网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2XD22路由表网络端口距离XB12路由表网络端口距离路由器CB1B2路由表网络端口距离XC23A3E1E1路由表网络端口距离XA31E发现网络X故障，E路由更新路由器D距离矢量路由选择算法中的路由循环网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2XD22路由表网络端口距离XB12路由表网络端口距离路由器CB1B2路由表网络端口距离XC23A3E1E1路由表网络端口距离E向A发送路由更新消息，A路由更新路由器D距离矢量路由选择算法中的路由循环网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC23A3E1E1路由表网络端口距离B、D路由更新路由器D距离矢量路由选择算法中的路由循环网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC23A3E1E1路由表网络端口距离路由器DC尚未更新，C定期向D发送路由表，据此D路由更新XD14距离矢量路由选择算法中的路由循环网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC23A3E1E1路由表网络端口距离路由器DD向A发送路由表，A路由更新XD14XA15距离矢量路由选择算法中的路由循环网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC23A3E1E2路由表网络端口距离路由器DB和E路由更新，此时任一路由器向网络X发送分组，都将会在路由器A、D、C、B之间无限循环。XD14XB16XA15XE16路由循环距离矢量路由选择算法中的路由循环网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC27A3E1E2路由表网络端口距离路由器D路由更新继续进行，C收到B的路由表，原来自B的路由距离=3，新的路由消息距离=6，认为拓扑发生变化，更新距离为7。XD14XB16XA15XE16路由循环距离矢量路由选择算法中的无限计数网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC27A3E1E2路由表网络端口距离路由器D类似地，D更新距离=8XD18XB16XA15XE16路由循环距离矢量路由选择算法中的无限计数网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC27A3E1E2路由表网络端口距离路由器DA更新距离=9，XD18XB16XA19XE16路由循环距离矢量路由选择算法中的无限计数网络X路由器A路由器B路由器E路由表网络端口距离A1A2D1D2C1C2路由表网络端口距离路由表网络端口距离路由器CB1B2路由表网络端口距离XC27A3E1E2路由表网络端口距离路由器DB、E更新距离=10，…A、B、C、D路由器距离出现无限计数。XD18XB110XA19XE110路由循环距离矢量路由选择算法中的无限计数—为解决分组的无限循环和距离的无限计数问题，规定当距离=16时，该路由信息无效，即表示目标网络不可达，这样既中止了分组无修止循环，也避免了无限计数。—由此限制了网络的规模，即网络的最大距离不能达于15。—无论拓扑结构是否发生变化，通过定期传送路由表来传达路由变更的方法，收敛速度慢，这是距离矢量算法的另一大缺陷。距离矢量路由选择算法局限链路状态路由选择算法链路状态路由算法又称最短路径优先算法，主要使用链路状态公告LSA（Link—StateAdvertisement）、网络拓扑数据库、最短路径SPF算法、最短路径SPF树和路由表5种技术手段；网络搜索过程：—路由器之间互相交换LSA。每个路由器都从交换直接连接的链路状态开始，并转发其他路由器送来的LSA；—每个路由器并行地建立一个网络拓扑数据库，数据库有来自于网上所有的LSA组成；—每个路由器中的最短路径SPF算法计算网络的可达性，确定从本路由器至网络中其他各点的最短路径，并建立一棵以自己为根的SPF树；—路由器根据SPF树生成路由表。链路状态变化和路由更新：—无论何时链路状态拓扑结构发生改变，路由器向其他路由器发送链路状态变化的消息，其他路由器则根据链路状态的变化更新网络拓扑数据库；或者发现链路状态变化的路由器向一个指定的路由器发送链路状态变化的消息，所有其他路由器根据这个指定的路由器来更新网络拓扑数据库；—LSA数据包每次引起网络拓扑数据库的改变，SPF算法则重新计算最短路径并更新路由表。最短路径计算SPF（ShortestPathFirst）最短路径优先算法又称Dijkstra算法，是链路状态路由选择算法的核心，它是一种广度优先搜索算法，按照每条链路的通信代价（如跳数、带宽等）计算出每一点至各点的最短路径。例：计算下图由A点出发至各点的最短路径：BACEDFG22341442132122334142每一路由器端口的数字代表由该端口输出的代价，缺省值按带宽来计算：COST=108/带宽（bit/s）以10M线路为例，COST=108/10,000,000=10路由器中每各路由器端口的COST值也可人工设置。最短路径计算标记：P—永久标记，表示由A点至该点的最短路径已找到；T—临时标记，表示由A点至该点的最短路径尚未找到；费用：—由A点至该点目前不可达；前件：至该点的最短路径中的前一节点。BACEDFG22341442132122334142前件：0AAA节点：ABCDEFG标记：PTTTTTT费用：0241—A到自身的路径费用为0，建立以A为根的SPF树；—在A目前可达的点B、D、F中，前件均为A；到F的路径最短，则A至F的最短路径已找到，F作永久标记，并选F作为下一步寻找的出发点；8888SPF最短路径树A最短路径计算BACEDFG22341442132122334142前件：0AAAF节点：ABCDEFG标记：PTTTTPT费用：02413—将F加入SPF最短路径树中，F由A直达；—由F点出发寻找最短路径，因A至F的费用为1，故F携带费用1；—F至G的费用为2，则由A至G的总费用为1+2=3，且前件为F；—目前在A未作永久标记的可达点B、D、G中B最短，选B，B由A直达，并作永久标记。881ASPF最短路径树F1最短路径计算BACEDFG22341442132122334142前件：0ABAAF节点：ABCDEFG标记：PPTTTPT费用：025413—将B加入SPF最短路径树中，B由A直达；—由B点出发寻找最短路径，B携带费用2；—B至C的费用为3，则由A至G的总费用为2+3=5，且前件为B；—B至G的费用为4，则由A至G的总费用为2+4=6，与原先A至G的费用3相比，已非最短，舍弃；—目前在A未作永久标记的可达点C、D、G中G最短，选G，并作永久标记。82ASPF最短路径树B2F1最短路径计算BACEDFG22341442132122334142前件：0ABAAF节点：ABCDEFG标记：PPTTTPP费用：025413—将G加入SPF最短路径树中，G由F到达；—由G点出发寻找最短路径，G携带费用3；—G至D的费用为2，则由A至D的总费用为3+2=5，与原先A至D的费用4相比，已非最短，舍弃；—目前在A未作永久标记的可达点C、D中D最短，选D，并作永久标记。83ASPF最短路径树B2F1G2最短路径计算BACEDFG22341442132122334142前件：0ABADAF节点：ABCDEFG标记：PPTPTPP费用：0254713—将D加入SPF最短路径树中，D由A到达；—由D点出发寻找最短路径，D携带费用4；—D至C的费用为2，则由A至C的总费用为4+2=6，与原先A至C的费用4相比，已非最短，舍弃；—D至E的费用为3，则由A至E的总费用为4+3=7，与原先A至C不可达相比，7为最短，且前件为D；—目前在A未作永久标记的可达点C、E中C最短，选C，并作永久标记。4ASPF最短路径树B2F1G2D4最短路径计算B