培训5：交换及路由(2013-07-08)

1、1. 交换型以太网2. 路由与路由器3. 路由选择算法4. 主要路由协议5. 第三层交换6. 多层交换1. 交换型以太网1.1. 交换机的功能1.2. 交换机工作原理1.3. 交换机结构1.4. 交换方式1.5. VLAN交换 减少冲突：交换机将冲突隔绝在每一个端口，避免了冲突的扩散 提升带宽：接入交换机的每个节点都可以使用全部的带宽，而不是各个节点共享带宽 地址学习地址学习转发转发/ /过滤过滤防止回路防止回路1.2 交换机工作原理以太网交换机通过内部的MAC地址表做出转发/过滤的决定MAC地址表存放在交换机的RAM中初始的MAC地址表为空MAC address table0260.8c01

2、.11110260.8c01.22220260.8c01.33330260.8c01.4444E0E1E2E3ABCD交换机的接口收到数据帧后，查找MAC地址表，如没有相应的表项，交换机将该数据帧泛洪（flood）到所有其它的接口上通过读取帧中的源MAC地址，交换机将端口及其连接的主机映射起来，放入MAC地址表0260.8c01.4444E0: 0260.8c01.1111MAC address table0260.8c01.11110260.8c01.22220260.8c01.3333E0E1E2E3DCBA 交换机的地址学习续）如果交换机连接的所有主机都发送过数据帧，就可以建立起一个完整

3、的MAC地址表，交换机将据此做出转发/过滤的决定MAC地址表是动态变化的，如果在一定时间内某一主机没有新的数据帧发送，则相应的表项将被清除0260.8c01.3333MAC address table0260.8c01.11110260.8c01.2222E0E1E2E3DCBA0260.8c01.4444 交换机的转发与过滤如果数据帧的目的MAC地址在MAC地址表中有相应的表项，则交换机将该数据帧直接发往对应的接口，从而保证其它接口上的主机不会收到无关的数据帧广播帧和组播帧仍将被泛洪（flood）到除接收接口以外的所有其它接口0260.8c01.33330260.8c01.22220260.

4、8c01.4444E0: 0260.8c01.1111E2: 0260.8c01.2222E1: 0260.8c01.3333E3: 0260.8c01.44440260.8c01.1111E0E1E2E3DCABMAC address table 交换机的特性 交换机的每一个端口所连接的网段都是一个独交换机的每一个端口所连接的网段都是一个独立的冲突域立的冲突域 交换机所连接的设备仍然在同一个广播域内，交换机所连接的设备仍然在同一个广播域内，也就是说，交换机不隔绝广播（惟一的例外是也就是说，交换机不隔绝广播（惟一的例外是在配有在配有VLANVLAN的环境中）的环境中） 交换机依据帧头的信息进行

5、转发，因此说交换交换机依据帧头的信息进行转发，因此说交换机是工作在数据链路层的网络设备机是工作在数据链路层的网络设备 交换机的类型不可管理交换机不具备可管理性，没有CPU或集中管理芯片，只是并行程度、吞吐能力等优于集线器。可管理式交换除了具有不可管理交换机的全部功能，还带有CPU或集中管理芯片，可以支持VLAN及SNMP管理，又称为智能型交换机。1.3 交换机结构 软件执行交换结构RAMCPUA输入 B输出串/并 交换 所有功能均由软件实现，结构灵活。但存在堆叠困难，无法处理信息的广播，及随着功能的增加性能下降等缺点。 矩阵交换结构优点： 利用硬件交换，结构紧凑，交换速度快，延迟时间短。缺点：

6、 不宜于简单堆叠和集成而扩展端口数和带宽。交换矩阵控制处理输入输出 总线交换结构优点： 便于堆叠扩展，容易监控和管理，容易实现帧的广播。缺点： 对总线的带宽要求很高，价格比较昂贵。交换总线输入输出 共享存储器交换结构优点： 结构简单，容易实现。缺点： RAM操作的延时比较大，冗余结构比较复杂，适合小型交换机。输入/输出输入/输出共享存储器1.4 交换方式 存储转发交换存储转发存储转发 转发速度慢转发速度慢 延迟可变延迟可变 转发前校验转发前校验 Frame Frame Frame 切入交换 切入式，又称直通式 转发速度快转发速度快 延迟固定延迟固定 转发错误帧转发错误帧 Frame1.5 VL

7、AN交换 端口交换端口交换 帧交换帧交换 端口交换端口交换方式的特点： 端口用户组成小规模的VLAN非常灵活； 在全局交换网络上，端口交换能够为全局VLAN提供有效的、灵活的前端配置端口组合的功能。 帧交换帧交换方式的特点： 比端口交换增加了有效的带宽，LAN交换器上的每个端口用户具有独占带宽的性能，交换器间互联的速率可达数百兆甚至千兆位传输率。2. 路由与路由器2.1. 直接寻径和间接寻径2.2. 有关路由的一些概念2.3. 路由器的功能2.4. 路由器的工作原理2.5. VLAN路由模式2.1 直接寻径和间接寻径 直接寻径（发送方与接收方在相同网络） 在物理网络内部主机与主机之间直接通讯

8、间接寻径（发送方与接收方在不同网络） 确定到达接收方网络的路径将数据利用直接寻径发送给相邻的中转方，直到目的网络在目的网络中用直接寻径方法到达信宿 间接寻径与直接寻径的关系网络层寻径是直接寻径与间接寻径的相互作用的过程关系AB141.20.11.0DATA141.20.11.25141.20.11.33宿宿IP地址地址=141.20.11.33宿宿MAC地址地址=141.20.11.33的的MAC地址地址宿宿MACAddr宿宿IPAddr 直接寻径举例数据从主机数据从主机A发送到主机发送到主机B目的网络目的网络=141.20.11.0（同一物理网络）（同一物理网络） 间接寻径举例B141.20

9、.11.0141.20.11.25141.20.11.33AC141.20.245Ethernet 141.20.28.0141.20.17.0141.20.17.21141.20.17.26141.20.257DATA宿宿IPaddr宿宿MACaddr宿宿MAC地址地址=141.20.257的的Eth地址地址宿宿IP地址地址= 141.20.257下站下站IP地址地址141.20.11.33目的网络目的网络:141.20.28/24下站地址下站地址:141.20.17.26端口：端口：141.20.17.21的的MAC 地址地址下站下站IP地址地址141.20.257D数据从主机数据从主机A

10、发送到主机发送到主机DDATA宿宿IP地址地址= 141.20.257宿宿MAC地址地址=141.20.11.33的的Eth地址地址宿宿MACaddr宿宿IPaddr 间接寻径与直接寻径的关系IPMACIPIPIPMACMACMAC A B C DEthernet140.20.11/24Ethernet140.20.28/24Ethernet140.20.17/24L3L1L2间接间接 直接直接 间接寻径：第三层数据交换间接寻径：第三层数据交换 被寻径的数据单元是数据报（被寻径的数据单元是数据报（datagram） 通过信宿的通过信宿的IP地址寻径（查看路由表）地址寻径（查看路由表） 通过路由

11、表的相互关联获得到达信宿的全部信息通过路由表的相互关联获得到达信宿的全部信息输入输入 输出输出B的第三层的第三层IPHdrDATAIPHdrDATAdatagramdatagram查看路由表，查看路由表，下站下站IP地址是地址是141.20.17.26直接寻径：第二层数据交换直接寻径：第二层数据交换 被寻径的数据单元是帧（被寻径的数据单元是帧（frame） 通过物理地址寻径通过物理地址寻径 只知道下一站的物理地址，不知道任何信宿的信息只知道下一站的物理地址，不知道任何信宿的信息输入输入 输出输出B的第二层的第二层frameHdrIPdatagramframeHdrIPdatagramframe

12、frame查看查看ARP表表，确，确定定141.20.17.26的的MAC地址是地址是.2.2 有关路由的一些概念 什么是路由技术什么是路由技术 IP路由技术的地位和路由技术的地位和作用作用 网关网关(gateway) 驿站驿站(hop) 自治系统自治系统(AS) 路由表路由表(routing table) 路由选择的基本活动路由选择的基本活动 路由的实现路由的实现 路由选择算法路由选择算法 默认路由默认路由 静态路由与动态路由静态路由与动态路由 什么是路由技术 为数据报在网间寻找传输路径为数据报在网间寻找传输路径 采用间接寻径方式将数据报逐站传递采用间接寻径方式将数据报逐站传递 通过网间互连

13、设备通过网间互连设备路由器实现路由功能路由器实现路由功能信宿地址信宿地址 去往信宿的路径去往信宿的路径路由表路由表 IP路由技术的地位和作用 实现异种网络互连的关键技术实现异种网络互连的关键技术 完成完成OSI参考模型的第三层功能参考模型的第三层功能 体现体现TCP/IP协议协议IP层的设计思想层的设计思想 屏蔽下层与物理网络相关的技术细节屏蔽下层与物理网络相关的技术细节 用统一的用统一的IP地址分层次寻址和寻径地址分层次寻址和寻径 根据网络地址实现到达目的网络的路径选择根据网络地址实现到达目的网络的路径选择 根据主机地址在目的网络中选择到达信宿的路径根据主机地址在目的网络中选择到达信宿的路径

14、 网关概念的早期解释BEthernet 141.20.11.0141.20.11.25141.20.11.33AC141.20.245Ethernet 141.20.28.0Ethernet 141.20.17.0141.20.17.21141.20.17.26141.20.257D路由器路由器网络网络28与网络与网络17的互连系统的互连系统网络网络11与网络与网络17的互连系统的互连系统 网关概念的当前解释数据链路数据链路层层Data Link网络网络层层Network传输层传输层Transport应用层应用层Application网关（网关（Gateway）路由器（路由器（Router）

15、对网关概念的理解 网关的确切定义网关的确切定义 将两个采用不同协议的网络互连起来，在应用层用软将两个采用不同协议的网络互连起来，在应用层用软件实现协议转换的系统。件实现协议转换的系统。例如：例如： TCP/IP ISO/OSITCP/IP Novell 网关与路由器的混淆网关与路由器的混淆 两者混用，网关两者混用，网关 = 路由器（早期解释的历史原因）路由器（早期解释的历史原因） 目前厂家生产的路由器产品加载协议转换软件，具有目前厂家生产的路由器产品加载协议转换软件，具有网关功能。网关功能。 早期邮政系统的驿站（Hop）甲地甲地乙地乙地发信人发信人收信人收信人驿站驿站11驿站驿站12驿站驿站2

16、1驿站驿站22信源信源信宿信宿 计算机网络的驿站（Hop）甲地甲地乙地乙地发信人发信人收信人收信人驿站驿站11驿站驿站12驿站驿站21驿站驿站22信源信源信宿信宿IP datagramIP数据报传输数据报传输路径中的路由器路径中的路由器 自治系统CERNET全球全球InternetCHINANET自治系统自治系统自治系统自治系统 自治系统（或称自治域）的定义自治系统（或称自治域）的定义 由一个独立管理机构运行和维护的网络（由自设的网由一个独立管理机构运行和维护的网络（由自设的网络运行中心络运行中心NOC履行职责）履行职责） 系统内部采用相同的路由协议系统内部采用相同的路由协议内部采用内部采用O

17、SPF路由协议路由协议 路由表 每个站点每个站点/主机用某个特定的路由协议建立和主机用某个特定的路由协议建立和维护的、向网络发送维护的、向网络发送IP包的路由信息。包的路由信息。 路由表包含的主要信息路由表包含的主要信息DestinationInterfaceGateway 目的地址目的地址 网关网关/主机地址主机地址 网卡网卡/ 串口串口 某台主机地址某台主机地址某个子网地址某个子网地址某个网络地址某个网络地址Default（默认路由）（默认路由）128.1.5.1 路由表举例路由表举例128.1.4.0128.1.5.0128.1.5.2128.1.5.5A主机主机A的路由表的路由表信信宿

18、宿主主机机网网关关网网卡卡127.0.0.1127.0.0.1Lo0Default128.1.5.1Le0128.1.4.0128.1.5.2Le0128.1.5.0128.1.5.5Le0 路由选择的基本活动 路径判断路径判断 数据交换数据交换 路径判断选择最佳传输路径选择最佳传输路径 什么是最佳？什么是最佳？ 定义一种度量标准（定义一种度量标准（Metric） 如何得到最佳？如何得到最佳？ 根据度量标准确定一种路由算法根据度量标准确定一种路由算法 根据算法收集路由信息，作出判断根据算法收集路由信息，作出判断 将判断结果填入路由表将判断结果填入路由表 路由器之间交换网络动态的路由信息路由器之

19、间交换网络动态的路由信息 数据交换 将将IP包在网间传送包在网间传送 在在IP层查看去往信宿的路由表，确定下一站点层查看去往信宿的路由表，确定下一站点 找不到下站的路由，丢弃数据报找不到下站的路由，丢弃数据报 找到下站的路由，确定下站的物理地址找到下站的路由，确定下站的物理地址 在数据链路层数据封装，送网下站在数据链路层数据封装，送网下站 数据交换特点数据交换特点 数据报的目的数据报的目的IP地址始终保持不变地址始终保持不变 帧的目的物理地址根据路径判定结果逐站改变帧的目的物理地址根据路径判定结果逐站改变 路由的实现 确定路由算法确定路由算法 设计目标设计目标 选择类型选择类型 定义最佳路径的

20、度量准则定义最佳路径的度量准则 实现路由协议实现路由协议 路由传输协议（路由传输协议（Routed Protocol） 网间经路由被传输的协议：网间经路由被传输的协议：IP，IPX 路由选择协议（路由选择协议（Routing Protocol） 实现路由选择算法的协议：实现路由选择算法的协议：RIP，OSPF，BGP 路由选择算法 默认路由默认路由 静态路由静态路由 动态路由动态路由 默认路由（Default Route） 什么是默认路由？什么是默认路由？ 对那些在路由表中未包含其路由选择信息的信对那些在路由表中未包含其路由选择信息的信宿（网络宿（网络/主机）设定的缺省路径主机）设定的缺省路径

21、 在路由表中信宿地址取值在路由表中信宿地址取值0.0.0.0(Default) 默认路由的作用默认路由的作用 对所有自治系统以外的信宿都采用默认路由对所有自治系统以外的信宿都采用默认路由 简化路由计算，提高寻径效率，缩短表长简化路由计算，提高寻径效率，缩短表长 默认路由举例网络网络A网络网络DRdb0c0f0e0Default Rd e0Default Rd f0Default Rab0Default Rac0RaRcRbRfRe 静态路由 静态路由的概念静态路由的概念 静态路由工作原理静态路由工作原理 路由配置举例路由配置举例 故障举例（网络拓扑结构变化）故障举例（网络拓扑结构变化） 用人工

22、修改配置排除故障用人工修改配置排除故障 静态路由的概念 由网络管理员设置路由表由网络管理员设置路由表 简单、有效，适于结构简单的网络简单、有效，适于结构简单的网络 不适于拓扑结构和传输流量经常改变的复不适于拓扑结构和传输流量经常改变的复杂网络杂网络 静态路由举例网络网络A网络网络C网络网络BRa路由表路由表网络网络BRba2网络网络CRca3Rb路由表路由表网络网络ARab3网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1RaRbRc 链路发生故障链路发生故障网络网络A网络网络C网络网络BRb路由表路由表网络网络ARab3网络网络CRc

23、b2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1?Ra路由表路由表网络网络BRba2网络网络CRca3RaRbRc 解决办法：人工修改网络网络A网络网络C网络网络BRb路由表路由表网络网络ARab2网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1！不适于网络变化！不适于网络变化！Ra路由表路由表网络网络BRca3网络网络CRca3RaRbRc 动态路由的概念 由路由协议依据网络变化自动修改路由信息由路由协议依据网络变化自动修改路由信息 适于拓扑结构和传输流量经常改变的复杂网络适于拓扑结构和传输

24、流量经常改变的复杂网络隔绝广播，划分广播域通过路由选择算法决定最优路径转发基于三层地址的数据包（网络层设备）流量统计、拥塞控制、记帐等功能与网桥和交换机使用帧中的MAC地址转发帧相比较，路由器是通过数据包中的网络层地址(如IP地址)来转发数据包的，不对MAC地址进行操作。因此，在用路由器连接的网络上，源节点不需要知道目的节点的MAC也能够找到它。与网桥和交换机类似，路由器的内存中也存有一个表，叫做路由表(Routing Table)，其中记录的是数据包地址(网络层地址)和物理端口号的对应关系。路由器根据路由表来转发数据包。如果包中的目标地址与源地址在同一个网段内，路由器就将数据流限制在那个网段

25、内，不转发数据包；如果目标地址在另一个网段，路由器就把包发送到与目标网段相对应的物理端口上。依据路由表转发路由表包含路由器直连的网络和学习到的目的网络Routed Protocol: IPNetworkProtocolDestinationNetworkExit InterfaceE0S010.120.2.0172.16.1.0ConnectedLearned172.16.1.010.120.2.0S0E02.5 VLAN路由模式 边界路由 “独臂”路由器 第三层交换3. 路由选择算法3.1. 3.1. 距离向量算法距离向量算法3.2. 3.2. 链路状态算法链路状态算法3.1 距离向量算法D

26、istance-Vector D-V算法的基本概念算法的基本概念 D-V算法的动态特性算法的动态特性 D-V算法的收敛性问题及其解决办法算法的收敛性问题及其解决办法 D-V算法小结算法小结A路由表路由表 距离向量算法的基本概念 周期性地相互传递信息周期性地相互传递信息 每个路由器向与它每个路由器向与它相邻的站点相邻的站点发送一个包含它到所有其他路发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价）由器的距离的向量（最短路径或最小代价） 维护各自的路由表维护各自的路由表 路由器根据邻居发送的距离路由器根据邻居发送的距离向量的动态信息启动算法，更向量的动态信息启动算法，更新路由表新路由

27、表DCAB路由表路由表C路由表路由表B从从 E经经 A经经 B经经 D到到 A到到 B到到 C到到 D从从 E经经 A经经 B经经 D到到 A1155到到 B到到 C到到 D从从 E经经 A经经 B经经 D到到 A1155到到 B到到 C到到 D4112从从 E经经 A经经 B经经 D到到 A1155到到 B到到 C694到到 D4112 距离向量法的计算举例ADECB718221信宿信宿（D,V）到到 A1,A到到 B5,D到到 C4,D到到 D2,D从从 E 经经 A经经 B 经经 D到到 A1155到到 B885到到 C694到到 D4112 计算从计算从E经相邻站点经相邻站点A、B和和

28、D到达信宿到达信宿A、B、C和和D的最小代价的最小代价D (destination,neighbor) 得从得从E到达信宿的最佳路径（最小代价）路由表到达信宿的最佳路径（最小代价）路由表最小代价最小代价D (des,nei)E的路由表的路由表 D-V算法的动态特性 建立路由表的初始过程建立路由表的初始过程 网络发现过程剖析网络发现过程剖析 D-V建立路由表的初始过程ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1b0 b1 c0 c1A 的的路路由由表表C 的的路路由由表表B 的的路路由由表表A 的的路路由由表表10.0.0.0a0020.0.0.0a10C 的

29、的路路由由表表30.0.0.0c0040.0.0.0c10B 的的路路由由表表20.0.0.0b0030.0.0.0b10A 的的路路由由表表10.0.0.0a0020.0.0.0a1030.0.0.0a11C 的的路路由由表表30.0.0.0c0040.0.0.0c1020.0.0.0c01B 的的路路由由表表20.0.0.0b0030.0.0.0b1040.0.0.0b1110.0.0.0b01A 的的路路由由表表10.0.0.0a0020.0.0.0a1030.0.0.0a1140.0.0.0a12C 的的路路由由表表30.0.0.0c0040.0.0.0c1020.0.0.0c0110

30、.0.0.0c02B 的的路路由由表表20.0.0.0b0030.0.0.0b1040.0.0.0b1110.0.0.0b01 D-V网络发现过程剖析 1 1ACB到达信宿到达信宿40.0.0.0的路由变化的路由变化如果网络中的最长路径为如果网络中的最长路径为N，则算法经过，则算法经过N次迭代计算后收敛。即次迭代计算后收敛。即第第N步之后，网上的所有路由器都获得到达信宿步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。的路由信息。40.0.0.0 down40.0.0.0 up时时间间ABC刷刷新新初初始始 信信宿宿不不可可达达时时间间ABC刷刷新新初初始始 信信宿宿不不可可达

31、达40.0.0.0开开启启 0C 发发现现新新网网络络 时时间间 A B C 刷刷新新 初初始始 信信宿宿不不可可达达 40.0.0.0开开启启 0 C 发发现现新新网网络络 第第 1 步步 1 0 CB, 0+1=1 时时间间 A B C 刷刷新新 初初始始 信信宿宿不不可可达达 40.0.0.0开开启启 0 C 发发现现新新网网络络 第第 1 步步 1 0 CB, 0+1=1 第第 2 步步 2 1 0 BA, 1+1=2 距离向量法的收敛性问题 问题问题 逐站传递更新信息，算法的收敛速度慢逐站传递更新信息，算法的收敛速度慢 有可能出现各站路由信息不一致有可能出现各站路由信息不一致 有可能

32、传播错误的路由信息有可能传播错误的路由信息 后果后果 在站点间构成更新路由的路径环（在站点间构成更新路由的路径环（Routing Loops） 计数至无穷大（计数至无穷大（Count to Infinity） 距离向量法收敛性问题的解决办法距离向量法收敛性问题的解决办法 定义路径代价的最大值（定义路径代价的最大值（Maximum） 提高收敛速度提高收敛速度 水平分割（水平分割（Split Horizon） 毒性逆转（毒性逆转（Poison Reverse） 保持计时（保持计时（Hold-Down Timers） 触发更新（触发更新（Triggered Updates） 加速方法的综合应用举例加

33、速方法的综合应用举例40.0.0.0 时间时间ABC刷新刷新初始初始210信宿可达信宿可达 传播错误的路由信息传播错误的路由信息 1 1ACB 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0断断开开 2 1 2 BC，1+1=2 到达信宿到达信宿40.0.0.0的路由变化的路由变化C与与B之间的对话：之间的对话：C 我得不到信宿我得不到信宿40.0.0.0的任何路由信息，你能告诉我如何到达的任何路由信息，你能告诉我如何到达信宿吗？信宿吗？B 我可以到达信宿，距离为我可以到达信宿，距离为1。（传播了一条过时的错误信息）（传播了一条过时的错误信息）C 既然

34、如此，我选择经过你到达信宿的路径，距离为既然如此，我选择经过你到达信宿的路径，距离为2。40.0.0.0 down 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0断断开开 2 1 2 BC，1+1=2 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0断断开开 2 1 2 BC，1+1=2 第第 1 步步 2 3 2 CB，2+1=3 1 1ACB 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0断断开开 2 1 2 BC，1+1=2 第第 1 步步 2 3 2 CB，2+1

35、=3 第第 2 步步 4 3 4 BC，3+1=4 BA，3+1=4 到达信宿到达信宿40.0.0.0的路由变化的路由变化 路径环（路径环（Routing LoopRouting Loop）问题）问题这条错误的路由信息在这条错误的路由信息在C与与B之间不断复制和修改，并在网络中之间不断复制和修改，并在网络中传播（殃及传播（殃及A），形成路径传播的环路。），形成路径传播的环路。40.0.0.0 down 1 1ACB 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0断断开开 2 1 2 BC，1+1=2 第第 1 步步 2 3 2 CB，2+1=3 第第

36、2 步步 4 3 4 BA，BC，3+1=4 第第 3 步步 4 5 4 CB，4+1=5 第第 13 步步 14 15 14 CB，14+1=15 第第 14 步步 16 15 16 BA，BC，15+1=16 到达信宿到达信宿40.0.0.0的路由变化的路由变化 严重后果：计数至无穷大严重后果：计数至无穷大40.0.0.0 down 1 1ACB 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0 断断开开 2 1 2 BC，1+1=2 第第 1 步步 2 3 2 CB，2+1=3 第第 2 步步 4 3 4 BA，BC，3+1=4 第第 3 步步 4

37、 5 4 CB，4+1=5 第第 13 步步 14 15 14 CB，14+1=15 第第 14 步步 16 15 16 BA，BC，15+1=16 第第 15 步步 不不可可达达 16 不不可可达达 CB，15+1=16 第第 16 步步 不不可可达达 扔扔弃弃 到达信宿到达信宿40.0.0.0的路由变化（定义的路由变化（定义Hop最大值为最大值为16） 定义距离的最大值收敛！收敛！40.0.0.0 down 水平分割方法的思路水平分割方法的思路 1 1ACB 分析路径环产生的原因分析路径环产生的原因 B向向C提供了一条过时的、错误的路由信息。提供了一条过时的、错误的路由信息。 能否避免事件

38、发生？能否避免事件发生？ B必须经由必须经由C方可到达网络方可到达网络40.0.0.0，B不可能向不可能向C提供任何有价提供任何有价值的路由信息。值的路由信息。 修改修改B对对C提供的路由，禁止提供的路由，禁止B向向C提供关于此信宿的路由信息。提供关于此信宿的路由信息。 解决办法解决办法 B告诉告诉C一条在正常情况下不真实的消息：一条在正常情况下不真实的消息：网络网络40.0.0.0不可达不可达（距离为（距离为 ）。40.0.0.0 down40.0.0.0时时间间ABC刷刷新新初初始始21/ 0信信宿宿可可达达 时时间间 A B C 刷刷新新 初初始始 2 1/ 0 信信宿宿可可达达 40.

39、0.0.0断断开开 2 1/ BC， （虚虚假假） 时时间间 A B C 刷刷新新 初初始始 2 1/ 0 信信宿宿可可达达 40.0.0.0断断开开 2 1/ BC， （虚虚假假） 第第 1 步步 2 CB， 用水平分割法加速算法收敛用水平分割法加速算法收敛 1 1ACB 时时间间 A B C 刷刷新新 初初始始 2 1/ 0 信信宿宿可可达达 40.0.0.0断断开开 2 1/ BC， （虚虚假假） 第第 1 步步 2 CB， 第第 2 步步 BA， 到达信宿到达信宿40.0.0.0的路由变化的路由变化链路断开时链路断开时C与与B之间的对话：之间的对话：C 我得不到信宿我得不到信宿40.0

40、.0.0的任何路由信息，你能告诉我如何到达的任何路由信息，你能告诉我如何到达信宿吗？信宿吗？B 我不能到达信宿，距离为我不能到达信宿，距离为 。C 既然如此，我认为信宿不可达。既然如此，我认为信宿不可达。收敛！收敛！40.0.0.0 down40.0.0.0时时间间ABC刷刷新新初初始始210信信宿宿可可达达时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开21 C 主主动动改改距距离离为为 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0断断开开 2 1 C 主主动动改改距距离离为为 第第 1 步步 2 CB， 毒性逆转法 1

41、 1ACB 时时间间 A B C 刷刷新新 初初始始 2 1 0 信信宿宿可可达达 40.0.0.0断断开开 2 1 C 主主动动改改距距离离为为 第第 1 步步 2 CB， 第第 2 步步 BA， 到达信宿到达信宿40.0.0.0的路由变化的路由变化方法方法 当当C发现网络发现网络40.0.0.0发生故障时，发生故障时，主动将到达信宿的距离改为主动将到达信宿的距离改为 。结果结果 如果无其他到达信宿的路径，算法迅速收敛为信宿不可达。如果无其他到达信宿的路径，算法迅速收敛为信宿不可达。 如果存在其他到达信宿的路径，如果存在其他到达信宿的路径，C根据传播过来的信息再做修改。根据传播过来的信息再做

42、修改。收敛！收敛！40.0.0.0 down 保持计时法保持计时法 1 1ACB当当C发现网络发现网络40.0.0.0发生故障时，发生故障时，启动保持计时器启动保持计时器在保持计时期间内，在保持计时期间内，C的策略的策略 如果网络状态转变，如果网络状态转变，down up，关闭计时器，保留原有路由信息；，关闭计时器，保留原有路由信息； 如果收到来自如果收到来自B的关于信宿的路由信息，且路径比原有路径短，则关闭的关于信宿的路由信息，且路径比原有路径短，则关闭计时器，更新路由信息；计时器，更新路由信息； 如果无上述两种情况发生，计时器到时，更新路由为信宿不可达。如果无上述两种情况发生，计时器到时，

43、更新路由为信宿不可达。网络网络40.0.0.0不可达不可达到时到时40.0.0.0 down 1 1ACB 当当C发现网络发现网络40.0.0.0发生故障时，不等下一刷新周发生故障时，不等下一刷新周期到来，立刻更改路由为期到来，立刻更改路由为“信宿不可达信宿不可达” 引起全网的连锁反映，迅速刷新引起全网的连锁反映，迅速刷新 触发刷新法触发刷新法网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达40.0.0.0 downD40.0.0.0 (0，直接，直接) 加速加速方法的综合应用举例的综合应用举例DBAECC发现网络发现网络40.0.0

44、.0不可达：不可达：1. 用毒性逆转法将到达网络用毒性逆转法将到达网络40.0.0.0的距离该为的距离该为 ：2. 启动保持计时器；启动保持计时器；3. 用触发刷新法立即向用触发刷新法立即向B和和D发送发送“信宿可能不可达信宿可能不可达”通知。通知。0:0:05D40.0.0.0 (1，C)D40.0.0.0 (1，C)D40.0.0.0 (2，D)40.0.0.0D40.0.0.0 (0，直接，直接)D40.0.0.0 ( ，直接，直接)D40.0.0.0 ( ，直接，直接)40.0.0.0距离为距离为 （1 1）C C发现信宿不可达发现信宿不可达DBAECB和和D接收到来自接收到来自C的的

45、“网络网络40.0.0.0可能不可达可能不可达”报文：报文：1. 启动各自的保持计时器；启动各自的保持计时器；2. 用触发刷新法立即向用触发刷新法立即向A发送发送“信宿可能不可达信宿可能不可达”通知；通知；3. C计时器到时，更新路由表。计时器到时，更新路由表。到时到时0:0:150:0:10刷新路由刷新路由D40.0.0.0 ( ，直接，直接)D40.0.0.0 ( ，C)D40.0.0.0 ( ，C)D40.0.0.0 (2，D）40.0.0.0 down（2 2）B B和和D D接收到触发刷新报文接收到触发刷新报文 加速方法的综合应用举例DBAECA接收到来自接收到来自B的的“网络网络4

46、0.0.0.0可能不可达可能不可达”报文：报文：1. 启动保持计时器；启动保持计时器；2. 在路由刷新之前，仍然可以向信宿发送数据包；在路由刷新之前，仍然可以向信宿发送数据包；3. 计时器时间到时，刷新路由表。计时器时间到时，刷新路由表。0:0:350:0:300:0:15D40.0.0.0 ( ，直接，直接)D40.0.0.0 (2，D)Packets for Net 40.0.0.040.0.0.0 down时间到时间到时间到时间到时间到时间到D40.0.0.0 ( ，D)D40.0.0.0 ( ，C)D40.0.0.0 ( ，C)（3 3）A A接收到触发刷新报文接收到触发刷新报文 加速

47、方法的综合应用举例 距离向量算法小结 采用最短路径准则，计算采用最短路径准则，计算D信宿信宿(距离，下站距离，下站)； 每个站点只知道自己和邻居的局部信息，在自己每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启的刷新周期到来时，根据邻居的路由变化重新启动算法；动算法； 算法的收敛速度慢（特别是对网络崩溃）造成全算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无网信息的不一致，导致产生路径环，使计数至无穷大；穷大； 当路径环产生时，定义距离的最大值可防止算法当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大

48、问题。进入死循环，解决计数至无穷大问题。3.2 链路状态算法Link-Status L-S算法的基本概念算法的基本概念 L-S算法的动态特性算法的动态特性L-S算法的性能分析算法的性能分析 每个路由器周期性地收集和发送信息每个路由器周期性地收集和发送信息 主动测试其到所有邻居的链接状态（度量值）主动测试其到所有邻居的链接状态（度量值） 向所有的路由器发送（广播）自己拥有的状态信息向所有的路由器发送（广播）自己拥有的状态信息 得到一个全网的、动态的逻辑链路状态（得到一个全网的、动态的逻辑链路状态（L-S）图图 每个路由器刷新自己的路由表每个路由器刷新自己的路由表 当当L-S变化时，用最短路径优先

49、变化时，用最短路径优先(SPF)算法重新计算本地路由算法重新计算本地路由DCAB 链路状态算法的基本概念_路路由由表表SPF算法算法拓扑数据库拓扑数据库（L-S图）图）SPF树树L-S包包AEDCB212113Dijkstra最短路径算法最短路径算法 计算加权无向图（即计算加权无向图（即L-S图）中两个结点之间的最短路径图）中两个结点之间的最短路径 对每结点赋以标注对每结点赋以标注D(v),NP(v) 链路状态链路状态法的计算举例法的计算举例F3552其中其中自变量自变量v：无向图中的结点无向图中的结点函数函数D(v)：到目前为止，到目前为止，从源点到结点从源点到结点v的最短路径的最短路径（边

50、长之和）（边长之和）函数函数NP(v)：沿源点到结：沿源点到结点点v且与其相邻的前一结且与其相邻的前一结点点2FB2D1计计算算BCDEF 计计算算BCDEF02,A5,A1,A ,- ,-计计算算BCDEF02,A5,A1,A ,- ,-12,A4,D2,D ,-计计算算BCDEF02,A5,A1,A ,- ,-12,A4,D2,D ,-22,A4,D4,E计计算算BCDEF02,A5,A1,A ,- ,-12,A4,D2,D ,-22,A4,D4,E33,E4,E Dijkstra算法计算结果AEDCB212113计计算算BCDEF02,A5,A1,A ,- ,-12,A4,D2,D ,-

51、22,A4,D4,E33,E4,E44,E源点源点A到所有结点的最短路径到所有结点的最短路径F3552AL-S图图SPF树树 E1C1 L-S L-S算法的动态特性算法的动态特性 建立路由表的初始过程建立路由表的初始过程 发现新的网络发现新的网络 路由表的维护路由表的维护 发现拓扑变化发现拓扑变化 修改拓扑数据库修改拓扑数据库 计算计算SPF树树 修改路由表修改路由表ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1b0 b1 c0 c1A 的的路路由由表表10.0.0.0a0020.0.0.0a10 L-S L-S建立路由表的初始过程建立路由表的初始过程C 的的

52、路路由由表表30.0.0.0c0040.0.0.0c10B 的的路路由由表表20.0.0.0b0030.0.0.0b10ACB40.0.0.0 L-S网络发现过程剖析网络发现过程剖析C发现直连网络发现直连网络30.0.0.0和和40.0.0.0 构造包含发现信息的构造包含发现信息的L-S报文报文(LSP)向全网广播向全网广播 接收全网的其他路由器发来的接收全网的其他路由器发来的L-S报文报文 根据收集的信息建立拓扑数据库根据收集的信息建立拓扑数据库 启动启动SPF算法以算法以C为源点计算为源点计算SPF树树 建立到达所有信宿的路由表（端口和代价）建立到达所有信宿的路由表（端口和代价）c1信信

53、宿宿端端 口口代代 价价3 0 .0 .0 .0c004 0 .0 .0 .0c10LSP30.0.0.0c0发现拓扑变化AEDCBFNet X发现发现网络网络X不可达不可达构造构造LSP向全网广播向全网广播发现发现网络网络X不可达不可达构造构造LSP向全网广播向全网广播Net X DownLSPNet X DownLSP修改拓扑数据库AEDCBFNet X全网具有相同全网具有相同的的L-S逻辑图。逻辑图。AEDCBFNet X各自重新计算各自重新计算SPFSPF树树2233115ECBFAD52212A的的SPF树树（新）（新）ECBFAD12211A的的SPF树树（旧）（旧）ECFAD32

54、212B的的SPF树树（旧（旧=新）新）BECFAD35211C的的SPF树树BECFAD2211F的的SPF树树B2ECFAD2211E的的SPF树树B2ECFAD22211D的的SPF树树B25AEDCBFNet X根据各自计算的根据各自计算的SPF树树刷新路由表刷新路由表修改各自的路由表a0a1a2Net YA 的的路路由由表表Net Ya21Net Ya14路路由由表表路路由由表表路路由由表表路路由由表表路路由由表表221 L-S算法的性能分析 优点优点 代价代价 路由刷新问题路由刷新问题 线路传输速率不同线路传输速率不同 网络运行状态不同网络运行状态不同 解决办法解决办法 L-S算法

55、的优点 所有路由器具有相同的网络拓扑知识（所有路由器具有相同的网络拓扑知识（L-S图）图） 一次性、无修改地向全网广播一次性、无修改地向全网广播LSP 路由器根据全局信息维护各自的路由表路由器根据全局信息维护各自的路由表 保证链路状态信息的单向传播保证链路状态信息的单向传播 保证算法的收敛性保证算法的收敛性AEDCBF L-S算法的代价算法的代价 SPF算法计算和拓扑算法计算和拓扑数据库需要更多的数据库需要更多的CPU和内存资源和内存资源 网络启动时的扩散路网络启动时的扩散路由信息（由信息（flood）需要需要占用占用很多带宽资源很多带宽资源 线路传输速率不同产生的影响线路传输速率不同产生的影

56、响Net X DownNet X upNet X Down来自来自D来自来自A慢慢Net XE收收到的到的LSP开始开始 Net X down后来后来 Net X upAEDCBF慢慢快快慢慢Net X downNet X downNet X upNet X upECFAD1211E的的SPF树树NetX upB2ECFAD2211E的的SPF树树NetX downB2E应该选择哪棵应该选择哪棵SPF树？树？AEDCBF网络已经启动部分网络已经启动部分网络尚未启动部分网络尚未启动部分 网络的一部分已经网络的一部分已经启动，而另一部分启动，而另一部分正待启动正待启动 网络的一部分刷新网络的一部分

57、刷新速度快，而另一部速度快，而另一部分刷新速度慢分刷新速度慢 造成网络的不同部造成网络的不同部分学习拥有不同的分学习拥有不同的L-S图图 网络运行状态不同产生的影响 L-S对问题的解决办法 减少对资源的需求减少对资源的需求 尽可能降低路由刷新频度尽可能降低路由刷新频度 用用Multicast取代取代Broadcast(flood) 将网络拓扑结构划分为不同层次和区域将网络拓扑结构划分为不同层次和区域 在层次间和区域交接处交换路由信息在层次间和区域交接处交换路由信息 协调协调L-S刷新刷新 对对LSP加时间戳标识加时间戳标识 对对LSP加序列号标识加序列号标识 用分级路由管理网络的逻辑分组用分级

58、路由管理网络的逻辑分组D-V和和L-S算法的比较算法的比较D-V 通过与邻居的信息交通过与邻居的信息交换获得网络拓扑知识换获得网络拓扑知识 路由计算是增加路由路由计算是增加路由器之间的站点数器之间的站点数（hops） 定期刷新路由：收敛定期刷新路由：收敛慢慢 向相邻站点传送路由向相邻站点传送路由表的副本表的副本L-S 全网获得共同的全局性网全网获得共同的全局性网络拓扑知识（络拓扑知识（L-S图）图） 计算到达其他站点的最短计算到达其他站点的最短路径（路径（SPF准则）准则） 触发刷新：收敛快触发刷新：收敛快 向其他站点发送链路状态向其他站点发送链路状态的动态变化的动态变化层次化路由选择系统层次

59、化路由选择系统子网子网核心系统核心系统子网子网自治系统自治系统自治系统自治系统全球全球InternetCERNETCHINANET华北地区网华北地区网华南地区网华南地区网复杂网络分层管理复杂网络分层管理路由交换路由交换相同层次相同层次层次之间层次之间4 主要路由协议4.1. 自治系统AS4.2. IGPs4.3. EGPs4.4. GGP4.1 自治系统AS 自治系统是一个自我管理的网络，统一管自治系统是一个自我管理的网络，统一管理自己内部的路由。理自己内部的路由。 自治系统内部的路由信息无须与外界共享。自治系统内部的路由信息无须与外界共享。内部与外部网关路由协议自治系统（Autonomous

60、 System）：在同一公共路由选择策略和公共管理下的网络集合，如一个ISP的网络内部网关协议（IGP）：在自治系统内交换路由信息 外部网关协议（EGP）：在自治系统间交换路由信息 Autonomous System 100Autonomous System 200IGPs: RIP, IGRPEGPs: BGP 网关网关-网关协议网关协议 Gateway-to-Gateway Protocol （GGP） 用于核心系统网关之间的路由交换用于核心系统网关之间的路由交换 外部路由协议外部路由协议 Exterior Gateway Protocol （EGP） 用于不同自治系统（用于不同自治系统（