第五章-网络层ppt课件

《第五章-网络层ppt课件》由会员分享，可在线阅读，更多相关《第五章-网络层ppt课件（149页珍藏版）》请在金锄头文库上搜索。

1、第五章 网络层,2020年11月12日,2,5.1 网络层基本概念,ISO给网络层的定义 网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。 网络层是处理端到端传输的最低层。 网络层要解决的关键问题是了解通信子网的拓扑结构，选择路由。,2020/11/12,3,5.1 网络层基本概念,设计网络层时应考虑的主要问题 存储转发方式的分组交换 为传输层提供的服务 实现无连接服务 实现面向连接的服务 比较虚电路与数据报服务,2020/11/12,4,5.1 网络层基本概念,设计网络层时应考虑的主要问题 存储转发方式的分组交换 网络层协

2、议的工作环境,2020/11/12,5,5.1 网络层基本概念,设计网络层时应考虑的主要问题 为传输层提供的服务 实现无连接服务 Internet的观点：通信子网无论怎么设计都是不可靠的，因此网络层只需提供无连接服务（Internet终端：计算机，复杂）,数据报子网中的路由选择,2020/11/12,6,5.1 网络层基本概念,设计网络层时应考虑的主要问题 为传输层提供的服务 实现面向连接的服务 传统电信的观点：通信子网应该提供可靠的、面向连接的服务。（电信网终端：电话，简单）,虚电路子网中的路由选择,2020/11/12,7,5.1 网络层基本概念,设计网络层时应考虑的主要问题 虚电路与数据

3、报服务的比较,2020/11/12,8,5.2 路由算法,路由问题：路径选择,2020/11/12,9,5.2 路由算法,谁来完成路径选择工作 由邮局组成的邮政系统完成路径选择的全过程 由每个邮局进行具体的存储转发工作,2020/11/12,10,5.2 路由算法,如何进行路径选择 路径选择依据 根据信宿地址确定下一个站点是谁 路径选择方法 查看邮局各自去往信宿的路由表,前往旧金山,2020/11/12,11,5.2 路由算法,路由算法是网络层软件的一部分 子网采用数据报方式，每个包都要做路由选择； 子网采用虚电路方式，只需在建立连接时做一次路由选择。 路由算法应具有的特性 正确性（Corre

4、ctness）：沿路由，分组一定能到目的交换机； 简单性（Simplicity）：不增加额外开销； 健壮性（Robustness）：自适应，可适应通信量和拓扑变化； 稳定性（Stability）：算法收敛； 公平性（Fairness） 最优性（Optimality） 路由算法分类 非自适应算法，静态路由算法 自适应算法，动态路由算法,2020/11/12,12,5.2 路由算法,路由算法公正性与优化的矛盾,2020/11/12,13,5.2 路由算法,最优化原则（Optimality Principle） 如果路由器J在路由器I到K的最优路由上，那么从J到K的最优路由会落在同一路由上。 汇集树

5、（Sink Tree） 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树； Fig. 5-5 路由算法的目的是找出并使用汇集树。,2020/11/12,14,5.2 路由算法,2020/11/12,15,5.2 路由算法,最短路径路由算法（Shortest Path Routing） 属于静态路由算法 基本思想 构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。 测量路径长度的方法 结点数量（hops） 地理距离 传输延迟 距离、信道带宽等参数的加权函数,2020/11/12,1

6、6,5.2 路由算法,最短路径路由算法（Shortest Path Routing） Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注； 初始时，所有结点都为临时性标注，标注为无穷大； 将源结点标注为0，且为永久性标注，并令其为工作结点； 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点； 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点； 重复第四、五步，直到目的结点成为工作结点； Fig. 5-6 Fig. 5-7，

7、程序与算法的区别是：从目的结点开始。,2020/11/12,17,5.2 路由算法,最短路径路由算法（Shortest Path Routing）,2020/11/12,18,5.2 路由算法,洪泛算法（Flooding） 属于静态路由算法 基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。 主要问题 洪泛要产生大量重复包。 解决措施 每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包； 每个结点记录包经过的路径，当包再次重复通过同一结点时，丢弃该包。,2020/11/12,19,5.2 路由算法,洪泛算法（Flooding） 选择性洪泛算法（Selective

8、 Flooding） 洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。 应用情况 路由器和线路的资源过于浪费，实际很少直接采用； 具有极好的健壮性，可用于军事应用； 作为衡量标准评价其它路由算法。,2020/11/12,20,5.2 路由算法,基于流量的路由算法（Flow-Based Routing） 属于静态路由算法 基本思想 既考虑拓扑结构，又兼顾网络负荷； 前提：每对结点间平均数据流是相对稳定和可预测的； 根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。 提前离线（off-line）计算 需要预知的信息 网络拓扑结构； 通

9、信量矩阵Fij； 线路带宽矩阵Cij； 路由算法（可能是临时的）,2020/11/12,21,5.2 路由算法,基于流量的路由算法（Flow-Based Routing）,2020/11/12,22,5.2 路由算法,距离向量路由算法（Distance Vector Routing） 属于动态路由算法 应用 ARPANET、因特网、DECNet、Novell IPX、Cisco Routers 等 基本思想 每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表； 以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达

10、目的结点所需时间或距离；,2020/11/12,23,5.2 路由算法,距离向量路由算法（Distance Vector Routing） 基本思想 每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表； 邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则本路由器经过X到i的距离为Xi+m。根据不同邻居发来的信息，计算Xi+m，并取最小值，更新本路由器的路由表； 注意：本路由器中的老路由表在计算中不被使用。,2020/11/12,24,5.2 路由算法,距离向量路由算法（Distance Vector Routing）,2

11、020/11/12,25,5.2 路由算法,距离向量路由算法（Distance Vector Routing） 无限计算问题（Count-to-Infinity Problem） 算法的缺陷：对好消息反应迅速，对坏消息反应迟钝；,2020/11/12,26,5.2 路由算法,距离向量路由算法（Distance Vector Routing） 无限计算问题（Count-to-Infinity Problem） 解决坏消息 对于以hop为费用的，设置“”为最大路径+1； 对于以时延为费用的，设置一较高值表示路径不通。,2020/11/12,27,5.2 路由算法,距离向量路由算法（Distance

12、 Vector Routing） 水平分裂算法 解决对“坏消息”反应慢的问题； 工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告（报告为无穷大）； 坏消息传播的快； 虽然广泛使用，但有时候会失败。 Fig. 5-12,2020/11/12,28,5.2 路由算法,链路状态路由算法（Link State Routing） 距离向量路由算法的主要问题 选择路由时，没有考虑线路带宽； 路由收敛速度慢。 算法原理 发现邻居节点，并获得其网络地址； 测量到每个邻居结点的延迟或开销； 将所有学习到的内容封装成链路状态分组； 将这个分组发送给所有其它所有路由器； 计算到每个其它路由

13、器的最短路径。,2020/11/12,29,5.2 路由算法,链路状态路由算法（Link State Routing） 发现邻居节点，并获得其网络地址 路由器启动后，通过发送HELLO包发现邻居结点； 两个或多个路由器连在一个LAN时，引入人工结点；,2020/11/12,30,5.2 路由算法,链路状态路由算法（Link State Routing） 测量延迟与开销 一种直接的方法是：发送一个要对方立即响应的ECHO分组，来回时间除以2即为延迟。 考虑信道的负载 在ECHO分组进入等待队列时，启动计时器（若考虑负载）； 在ECHO分组进入等待队列最前端时，启动计时器（若忽略负载）； 争议 F

14、ig. 5-14 路由表不断反复变化,2020/11/12,31,5.2 路由算法,2020/11/12,32,5.2 路由算法,链路状态路由算法（Link State Routing） 封装链路状态分组 分组以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表； 列表中对应每个邻居结点，都有发送方到它们的延迟或开销； 链路状态分组创建时机 定期创建 发生重大事件时创建 Fig. 5-15,2020/11/12,33,5.2 路由算法,链路状态路由算法（Link State Routing） 封装链路状态分组,2020/11/12,34,5.2 路由算法,链路状态路由算法（Link Sta

15、te Routing） 分发链路状态分组 基本思想 洪泛法分发链路状态包； 为控制洪泛，每个分组包含一个序号，每次发送新分组时加1； 路由器记录信息对（源路由器，序号），当一个链路状态分组到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃。,2020/11/12,35,5.2 路由算法,链路状态路由算法（Link State Routing） 分发链路状态分组 问题与改进 序号循环使用会混淆 解决办法：使用32位序号 路由器崩溃，造成序号丢失 序号出错 第二、三问题的解决办法：增加年龄（age）域，每秒钟年龄减1，为零则丢弃。 链路状态分组到达后，

16、延迟一段时间，并与其它已到达的来自同一路由器的链路状态分组比较序号，丢弃重复包和年龄大的分组； 链路状态分组需要应答（避免出现差错）；,2020/11/12,36,5.2 路由算法,链路状态路由算法（Link State Routing） 分发链路状态分组,从E发来的链路状态分组有两个，一个经过EAB，另一个经过EFB 从D发来的链路状态分组有两个，一个经过DCB，另一个经过DFB,2020/11/12,37,5.2 路由算法,链路状态路由算法（Link State Routing） 计算新的最短路由 根据Dijkstra算法计算最短路径 实用协议 OSPF（开放最短路径优先） IS-IS（中间系统至中间系统） 两者的区别 IS-IS可同时携带多个网络层协议的信息,2020/11/12,38,5.2 路由算法,分层路由（Hierarchical Routing） 网络规模增长带来的问题 路由器中的路由表增大； 路由器为选择路由而占用的内存、CPU时间和网络带宽增大。 分层路由 分而治之的思想； 根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组