《计算机网络》第五章（4） 第五章 网络互连技术 （四） 信阳师范学院计算机系

第五章 网络互连技术 5.1 网络互连需要解决的问题 5.2 地址 5.3 路由技术 5.4 交换技术 信阳师范学院计算机系

5.3 路由技术 1. 路由技术的基本概念 2. 路由选择算法需要考虑的基本因素 3. 路由选择算法 4. 路由选择协议概述 5.3 路由技术 1. 路由技术的基本概念 2. 路由选择算法需要考虑的基本因素 3. 路由选择算法 4. 路由选择协议概述 信阳师范学院计算机系

3. 路由选择算法 1）默认路由 2）静态路由 3）动态路由—距离向量法 4）动态路由—链路状态法 信阳师范学院计算机系

3）距离向量算法 Distance-Vector D-V算法的基本概念 D-V算法的动态特性 D-V算法的收敛性问题及其解决办法 RIP协议 信阳师范学院计算机系

距离向量算法小结 路径选择采用最短路径准则，计算D信宿(距离，下站)； 每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法； 算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大； 当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题； 各种加速收敛方法的目的在于避免路径环的形成，但不能从根本上杜绝这一现象的发生； 在具体的路由协议中，各种加速收敛方法往往综合使用。 信阳师范学院计算机系

RIP协议 RIP协议的基本概念 网络路由举例 RIP协议的实现 RIP路由数据封装 RIP协议的工作原理 路由请求/路由响应 对路由信息的处理 对时钟的处理 信阳师范学院计算机系

RIP协议的基本概念 Router Information Protocol 最初为Xerox网络系统的通用协议而设计 与4BSD/UNIX捆绑在一起（routed进程） 1988年RFC1058正式定义 基于以站点数（hop）为度量的D-V算法 定义hop=16为无穷大 刷新周期为30秒 适于小型网络的内部路由协议 信阳师范学院计算机系

网络路由举例 HostB HostA Router 128.1.2.15 128.1.1.15 128.1.2.0 128.1.1.0 128.1.1.8 0:20:c5:d4:a3:68 128.1.2.15 0:a0:24:ea:b3:57 HostB HostA Router 128.1.1.15 0:20:c5:e2:d4:77 128.1.2.10 0:a0:24:ec:c6:63 128.1.2.0 128.1.1.0 信阳师范学院计算机系

Solaris系统的RIP实现 routed进程的启动 routed进程的运行 主动路由（active）： 路由器广播 被动路由（passive）：主机接收 routed进程的运行 具有相同路径长度的路由选择—先入为主 定义路由条目的生存时间—180秒 对慢收敛的对策 水平分割 毒性逆转 触发更新 信阳师范学院计算机系

routed进程的启动 开机 检查所有网卡 有静态路由 一块网卡 Router Host 启动routed进程 进入主动路由工作模式 不用RIP协议选择路由 有静态路由 是 否 128.1.2.15 一块网卡 128.1.2.10 否 是 Router Host 启动routed进程 进入主动路由工作模式 启动routed进程 进入被动路由工作模式 主动广播路由信息/30秒 被动监听路由信息/30秒 信阳师范学院计算机系

routed进程发出路由请求 RIP报文 Ethernet 报头 UDP报头 IP报头 目的地址=ff:ff:ff:ff:ff:ff 源地址=0:a0:24:ec:c6:63 协议类型=0800(IP) 宿=128.1.2.255 源=128.1.2.10 协议类型=17(UDP) 宿端口=520（RIP） 源端口=520 命令类型=1 (route request) 寻径地址类别=2(IP) 寻径目的地址=0.0.0.0 下站=default 端口=0 距离=16（不可达） 主机128.1.2.10向广播地址发出路由请求（开机时自动完成）。 信阳师范学院计算机系

routed进程发出路由响应 RIP报文 Ethernet 报头 UDP报头 IP报头 目的地址=ff:ff:ff:ff:ff:ff 源地址=0:a0:24:ea:b3:57 协议类型=0800(IP) 宿=128.1.2.255 源=128.1.2.15 协议类型=17(UDP) 宿端口=520（RIP） 源端口=520 命令类型=2 (route response) 寻径地址类别=2(IP) 寻径目的地址=128.1.1.0 下站=128.1.1.0 端口=0 距离=1 间隔30秒，从广播地址可以接收到路由器128.1.2.15发出的路由响应。 信阳师范学院计算机系

RIP协议的路由刷新 Routed进程接收到路由广播信息，在满足以下任一条件下更新自己的路由表项： 《计算机网络》第五章（4） RIP协议的路由刷新 Routed进程接收到路由广播信息，在满足以下任一条件下更新自己的路由表项： 一条新的路由表项，且到达目的地址的距离不是无穷大； 一条旧的路由表项，且此条目被原信息提供者（邻接路由器）更新； 一条旧的路由表项已经有90秒未被刷新；有一条新的到达同一目的地址的路由信息到来，且距离更短。 信阳师范学院计算机系 信阳师范学院计算机系

RIP协议的时钟 路由刷新周期 路由失效计时 路由保持计时 每个路由器每隔30秒刷新和广播自己的路由表。 《计算机网络》第五章（4） RIP协议的时钟 路由刷新周期 每个路由器每隔30秒刷新和广播自己的路由表。 路由失效计时 一条路由表项未被更新的时间达3分钟（180秒），则视其为失效信息，将本路由表项的距离置为无穷大（毒性逆转）。 路由保持计时 发现一条路由失效信息后，立即启动保持计时，60秒之后删除此条目。 信阳师范学院计算机系 信阳师范学院计算机系

4）链路状态（Link-State）算法 L-S算法的基本概念 L-S算法的动态特性 L-S算法的性能分析 L-S算法与 D-V算法的比较 OSPF协议 信阳师范学院计算机系

链路状态算法的基本概念 链路状态算法的基本概念 链路状态法的计算举例 Dijkatra算法计算结果 信阳师范学院计算机系

链路状态算法的基本概念 每个路由器周期性地收集和发送信息 每个路由器刷新自己的路由表 D C A B L-S包 主动测试其到所有邻居的链接状态（度量值） 向所有的路由器发送（广播）自己拥有的状态信息 得到一个全网的、动态的逻辑链路状态（L-S）图 每个路由器刷新自己的路由表 当L-S变化时，用最短路径优先(SPF)算法重新计算本地路由 D C A ______________________________ _______________ 路由表 SPF 算法 B L-S包 拓扑数据库（L-S图） SPF树 信阳师范学院计算机系

链路状态法的计算举例 Dijkatra最短路径算法 计算加权无向图（即L-S图）中两个结点之间的最短路径 对每结点赋以标注{D(v),NP(v)} 其中 自变量v：无向图中的结点 函数D(v)：到目前为止，从源点到结点v的最短路径（边长之和） 函数NP(v)：沿从源点到结点v且与其相邻的前一结点 5 3 B C 2 5 2 1 F A 3 1 2 D E 1 信阳师范学院计算机系

Dijkatra算法计算结果 源点A到所有结点的最短路径 L-S图 5 3 B C A 1 2  2 5 B D 1  2 1 F A 《计算机网络》第五章（4） Dijkatra算法计算结果 源点A到所有结点的最短路径 L-S图 5 3 B C A 1 2  2 5 B D 1  2 1 F A 3 E 1 2 1 2 C F SPF树 D E 1 信阳师范学院计算机系 信阳师范学院计算机系

L-S算法的动态特性 建立路由表的初始过程 发现新的网络 路由表的维护 发现拓扑变化 修改拓扑数据库 计算SPF树 修改路由表 信阳师范学院计算机系

L-S建立路由表的初始过程 C A B 10.0.0.0 20.0.0.0 30.0.0.0 40.0.0.0 a0 a1 b0 b1 c0 c1 信阳师范学院计算机系

L-S网络发现过程剖析 30.0.0.0 40.0.0.0 A B C c0 c1 LSP C发现直连网络30.0.0.0和40.0.0.0 构造包含发现信息的L-S报文(LSP)向全网广播 接收全网的其他路由器发来的L-S报文 根据收集的信息建立拓扑数据库 启动SPF算法以C为源点计算SPF树 建立到达所有信宿的路由表（端口和代价） 信阳师范学院计算机系

（1）发现拓扑变化 C B A F  Net X E D Net X Down LSP 发现网络X不可达 构造LSP 向全网广播 信阳师范学院计算机系

（2）修改拓扑数据库 C B A F  Net X 全网具有相同的L-S逻辑图。 E D 信阳师范学院计算机系

（3）各自重新计算SPF树 C B F A  Net X D E 5 3 2 5 3 2 1 2 1 信阳师范学院计算机系 《计算机网络》第五章（4） （3）各自重新计算SPF树 5 C B 3 2 F 5 3 2 1 A  2 Net X 1 D E 信阳师范学院计算机系 信阳师范学院计算机系

（4）修改各自的路由表 C B A a0 F a1 a2  Net X Net Y E D 2 2 根据各自计算的SPF树刷新路由表 1 《计算机网络》第五章（4） （4）修改各自的路由表 路由表 路由表 C B A a0 2 F a1 2 根据各自计算的SPF树刷新路由表 a2 1  路由表 Net X 路由表 路由表 Net Y E D 信阳师范学院计算机系 信阳师范学院计算机系

L-S算法的性能分析 优点 代价 路由刷新问题 线路传输速率不同 网络运行状态不同 解决办法 信阳师范学院计算机系

L-S算法的优点 所有路由器具有相同的网络拓扑知识（L-S图） 路由器根据全局信息维护各自的路由表 一次性、无修改地向全网广播LSP 保证链路状态信息的单向传播 保证算法的收敛性 信阳师范学院计算机系

L-S算法的代价 SPF算法计算和拓扑数据库需要更多的CPU和内存资源 网络启动时的扩散路由信息（flood）需要占用很多带宽资源 《计算机网络》第五章（4） L-S算法的代价 SPF算法计算和拓扑数据库需要更多的CPU和内存资源 网络启动时的扩散路由信息（flood）需要占用很多带宽资源 信阳师范学院计算机系 信阳师范学院计算机系

线路传输速率不同产生的影响 E应该选择哪棵SPF树？ 开始 Net X down 后来 Net X up 慢 Net X E收到的LSP 来自A 来自D 信阳师范学院计算机系

网络运行状态不同产生的影响 网络的一部分已经启动，而另一部分正待启动 网络的一部分刷新速度快，而另一部分刷新速度慢 造成网络的不同部分学习拥有不同的L-S图 信阳师范学院计算机系

L-S对问题的解决办法 减少对资源的需求 协调L-S刷新 尽可能降低路由刷新频度 用Multicast取代Broadcast(flood) 将网络拓扑结构划分为不同层次和区域 在层次间和区域交接处交换路由信息 协调L-S刷新 对LSP加时间戳标识 对LSP加序列号标识 用分级路由管理网络的逻辑分组 信阳师范学院计算机系

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

OSPF协议 OSPF协议的基本概念 OSPF的区域划分 OSPF的工作原理 Area1的域内路由器 Area1的边界路由器 信阳师范学院计算机系

OSPF协议的基本概念 Open Shortest Path First 采用链接状态（L-S）算法 由IETF工作小组研制 1990年成为标准（RFC1247） 改进RIP协议的问题 计数至无穷大 收敛速度慢 信阳师范学院计算机系

OSPF划分编号区域（Area） …... Area0 主干路由器 国家主干 域边界路由器 域内路由器 地区主干 Area1 Area2 《计算机网络》第五章（4） OSPF划分编号区域（Area） Area0 主干路由器 国家主干 域边界路由器 …... 域内路由器 地区主干 Area1 Area2 AreaN 信阳师范学院计算机系 信阳师范学院计算机系

域内路由器 只拥有本域的路由信息； 具有相同的L-S图，采用相同的SPF算法； 采用扩散方式广播自己获得的网络知识（邻居和开销）； 《计算机网络》第五章（4） 域内路由器 只拥有本域的路由信息； 具有相同的L-S图，采用相同的SPF算法； 采用扩散方式广播自己获得的网络知识（邻居和开销）； 根据扩散的信息修改L-S图，计算到域内其他路由器的最短路径； 根据计算机结果维护各自的路由表。 信阳师范学院计算机系 信阳师范学院计算机系

域边界路由器 具有域内路由器的功能； 拥有相邻域的L-S信息，并计算到达相邻域的最短路径； 域间的分组交换都通过其进行路径选择和数据交换。 《计算机网络》第五章（4） 域边界路由器 具有域内路由器的功能； 拥有相邻域的L-S信息，并计算到达相邻域的最短路径； 域间的分组交换都通过其进行路径选择和数据交换。 例如： 本域的路由器通过域边界路由器把分组送往主干网，经主干网送达目的域边界路由器，再由其通过域内路由送往目的主机。 信阳师范学院计算机系 信阳师范学院计算机系

主干路由器 拥有主干网的L-S信息，计算到其他主干路由器的最短路径； 《计算机网络》第五章（4） 主干路由器 拥有主干网的L-S信息，计算到其他主干路由器的最短路径； 从与之相连的下级域边界路由器获取该域的路由信息，计算其到每个域的最短路径； 将主干到每个域的最短路径信息回传给域边界路由器。 信阳师范学院计算机系 信阳师范学院计算机系

4. 路由选择协议概述 1）路由选择协议的基本概念 2）路由选择协议的地位和作用 3）层次化路由选择系统 4）路由选择协议分类 4. 路由选择协议概述 1）路由选择协议的基本概念 2）路由选择协议的地位和作用 3）层次化路由选择系统 4）路由选择协议分类 5）路由协议的综合应用 信阳师范学院计算机系

1）路由协议的基本概念 在路由器之间传播网络的动态变化信息及其相应的路由信息； 使路由器根据获得的知识实现特定的路由算法； 《计算机网络》第五章（4） 1）路由协议的基本概念 在路由器之间传播网络的动态变化信息及其相应的路由信息； 使路由器根据获得的知识实现特定的路由算法； 使路由器根据计算结果维护路由表，并为数据报（datagram）确定传输路径。 信阳师范学院计算机系 信阳师范学院计算机系

2）路由选择协议的地位 路由选择协议属于OSI的网络层协议 TCP/IP：路由选择协议报文被封装在IP数据报中 IP 报头 路由选择协议 应用层 Application 传输层 Transport IP 报头 路由选择协议 报文 网间网层 Internet 网络接口层 Network Interface 信阳师范学院计算机系

3）层次化路由选择系统 核心系统 全球Internet 自治系统 CHINANET CERNET 自治系统 华北地区网 华南地区网 子网 复杂网络分层管理 路由交换 相同层次 层次之间 华北地区网 华南地区网 子网 子网 信阳师范学院计算机系

4）路由协议分类 网关-网关协议 外部路由协议 内部路由协议 Gateway-to-Gateway Protocol （GGP） 用于核心系统网关之间的路由交换 外部路由协议 Exterior Gateway Protocol （EGP） 用于不同自治系统（AS）之间的路由交换 内部路由协议 Interior Gateway Protocol （IGP） 用于自治系统（AS）内部的路由交换 信阳师范学院计算机系

5）路由协议的综合应用 核心系统 EGP GGP EGP EGP AS1 AS2 IGP IGP 信阳师范学院计算机系

5.4 交换技术 1）交换技术概述 2）第二层交换 3）第三层交换 信阳师范学院计算机系

1）交换技术概述 交换技术的定义 交换技术的分类 信阳师范学院计算机系

交换技术的定义 在网络上从一个站点到另一个站点之间为数据传输动态建立一条直接连接的路径。 网络1 网络2 网络4 网络3 信阳师范学院计算机系

交换技术分类 按被交换的数据单元分类 按交换技术所实现的功能层次分类 按用交换技术连接的网络特性分类 帧交换（frame switching） 信元交换（cell switching） 按交换技术所实现的功能层次分类 第二层（L2）交换 第三层（L3）交换 按用交换技术连接的网络特性分类 局域网交换（LAN switching） 广域网交换（WAN switching） 信阳师范学院计算机系

2）第二层交换 工作在数据链路层，实现数据帧的交换 网络设备： 与第二层交换相关的技术 第二层交换的问题 网桥 交换机 交换式以太网 虚拟局域网VLAN 第二层交换的问题 信阳师范学院计算机系

交换机与网桥的比较 用硬件实现网桥的大部分功能 具有8个以上端口 适应100M以太网的市场需求 隔离冲突域 向不同网络扩散/转发数据帧 通过对源地址的学习建立MAC地址表 具有8个以上端口 适应100M以太网的市场需求 信阳师范学院计算机系

交换式以太网 100M以太网主干 Ethernet switch 共享10M 独享10M Hub 信阳师范学院计算机系

VLAN 什么是VLAN 为什么用VLAN技术 基于端口的VLAN VLAN的标识 信阳师范学院计算机系

什么是VLAN 概念 用简单的交换技术管理一个大型网络 跨越物理网段划分逻辑网段（划分工作组） 财务 研发 管理 管理 财务 研发 共享主干 信阳师范学院计算机系

为什么用VLAN技术 物理分布 应用要求 一个工作组可能分布在不同物理位置上 同组用户可以方便地交换数据 不同组之间相互隔离 信阳师范学院计算机系

基于端口的VLAN 对帧插入/去除VLAN标记 贴标记 剥标记 财务 研发 管理 管理 财务 研发 共享主干 frame frame 信阳师范学院计算机系

VLAN的标识 IEEE802.3帧 信阳师范学院计算机系

第二层交换的问题 大型、平坦的交换网络面临的问题 解决办法 广播风暴 生成树环路 低效率的寻址（物理寻址） 安全的脆弱性 划分子网 将路由器引入桥接式网络 信阳师范学院计算机系

3）第三层交换 第三层交换的必要性 采用路由技术存在的问题 解决办法 按层次结构划分为互连的子网 出于安全性考虑，在子网之间进行IP包交换 路由器的处理能力成为瓶颈 路由器的价格较高 解决办法 第三层交换机 用标签匹配模式替代路由表查询 信阳师范学院计算机系

标签交换 基于ATM的IP交换 Ipsilon（1996.3） 标记交换 Cisco 基于路由的IP汇聚交换 IBM 信阳师范学院计算机系

标记交换 位于网络边缘的标记路由器进行路由选择，为IP包贴标记 位于网络核心的标记交换机根据嵌在标记中的信息完成IP包的交换 采用标记分配协议 举例 信阳师范学院计算机系

标记交换举例 标记交换机 根据标记转发IP包 选路由贴标记 标记路由器 标记路由器 去除标记 子网1 子网2 发送 接收 主要用于千兆位以太网 信阳师范学院计算机系

课程总结 L-S算法 路由协议 交换技术 L-S状态图和数据表 SPF树计算方法 路由刷新不一致的问题 路由协议的分类 典型的内部路由协议：RIP、OSPF 交换技术 信阳师范学院计算机系

思考题 从以下几方面描述L-S算法的工作原理 从以下几方面比较D-V和L-S算法 比较网络互连技术中的路由技术与交换技术 《计算机网络》第五章（4） 思考题 从以下几方面描述L-S算法的工作原理 如何传播路由更新信息 什么样的知识需要被传播 什么时候传播这样的知识 怎样存放路由更新信息 从以下几方面比较D-V和L-S算法 信息交换的复杂性 算法的收敛速度 比较网络互连技术中的路由技术与交换技术 信阳师范学院计算机系 信阳师范学院计算机系