网络层分析教程

《网络层分析教程》由会员分享，可在线阅读，更多相关《网络层分析教程（112页珍藏版）》请在金锄头文库上搜索。

1、计算机网络 授 课 老 师: 童 宇 联 系 方 式: 13077327687 第5章 网络层 n网络层概述 n路由选择算法 n路由选择协议 n流量控制和拥塞控制 n网络互连设备 5.1 网络层概述 网络层是OSI参考模型中的第三层,目的是屏蔽 各种不同类型网络之间的差异，实现两个端系统之 间的数据透明传送，具体功能包括路由选择、阻塞 控制等 网络服务模式 Internet团体（正努力获得更好的服务质量） 电话公司 虚电路与数据报机制 设计目标 n网络层的服务是按下列目标设计的 n服务应与通信子网的技术无关 n通信子网的数量、类型和拓扑结构对于 传输层来说是隐蔽的 n传输层所能获得的网络地址应

2、采用统一 的的编号方式，即使跨越了多个LAN和WAN n网络设计冲突的焦点是网络层究竟应该 提供面向连接还是无连接的服务 n实质是将复杂的功能放在何处的问题 n指整个通信子网向传输层或资源子网提供的服务规范。 网络服务模式 面向连接无连接 优点 1、分组携带虚电路号，带宽利用率高 2、连接一旦建立，容易进行拥塞控制 3、容易实现保证质量服务 4、容易实现计费 1、无连接开销，分组可立即发 送 2、对于通信线路的故障，如路由 器崩溃等，适应性很强，可以及 时绕道 缺点 1、有呼叫损耗，有创建开销 2、路由器需要存储虚电路状态信息 3、所有经过失效路由器的虚电路要 终止 1、每个分组必须携带完整的

3、目的 地址，浪费带宽 2、拥塞控制较难实现 3、不易实现保证质量服务 实 现 虚电路数据报 实例X.25 ATM 帧中继ARPANET、因特网 数据报子网内路由 虚电路与数据报机制 虚电路（virtual circuit）和数据报(datagrams)是网 络层实现面向连接和无连接服务的子网技术。 虚电路操作方式中，为了进行数据传输，网络的源 节点和目的节点之间先要建立一条逻辑通路，称之为“ 虚”电路。每个节点的虚电路表(例)中要记录两个逻辑信 道：前一个节点所选取的逻辑信道号和本节点所选取的 逻辑信道号。 数据报机制中，每个分组需要携带完整的目的地址 ，路由器要为每个数据报做路由选择，分组到

4、达的顺序 与发送的顺序可能不同。因特网就使用了一个数据报机 制的网络层。 虚电路子网内的路由 A E D CB H2H3 H1 H4 H5 依次建立5条VC： VC1：A-B-E VC2：A-B-D VC3：B-D-E VC4：C-E-D VC5：A-B-C-D vc4 vc3 vc5 vc2 vc1 入口出口 H1 H1 H1 0 1 2 B 0 1 2 B B 入口出口 A A H2 3 0 1 0 E0 0 1 D D 入口 出口 B B E 0 1 0 H4 0 0 1 E H4 入口 出口 H3 B 0 0 0 E 0 0 2 D 入口 出口 B D C 0 0 0 H5 0 1 0

5、D A B C D E A2C0 H5 CH4 虚电路与数据报之间的折衷 n路由器的内存与带宽 n建立虚电路的时间和地址解析的时间 n保证服务质量，子网避免拥塞 n交换虚电路和永久虚电路 n大量的建立和清除虚电路所需要的开销 会影响虚电路的使用 5.2 路由选择算法 路由选择算法概述 静态路由选择策略 动态路由选择策略 路由选择算法(Routing Algorithm) n是网络层软件的一部分，负责确定所收 到分组应传送的外出路线。 n路由选择算法可以分为两大类： n非自适应-事先脱线计算好或设定好的 ，在网络启动时就下载到路由器中 n自适应-根据拓扑结构、通信量的变化 来改变其路由选择。 n

6、路由选择算法应具有下列特性：正确性 、简单性、健壮性、稳定性、公平性和最 优性。 n优化的目标：分组的平均延时小，网络 吞吐量大。 n相互矛盾，因为任何队列系统，在接近 容量的情况下有很长的延迟。 n折衷降低跳数(使分组必须经过的站点 减少到最少)，减少了延迟和消耗的带宽 5.2.1 静态路由选择算法 目的节点下一节点费用 BB2 CC1 DC5 EB5 FB7 目的节点下一节点费用 AA2 CA3 DD5 EE3 FE5 A节点的路由 B节点的路由 最优化原则 n最优化原则（optimality principle） n如果路由器 J 在路由器 I 到 K 的最优路 由上，那么从 J 到 K

7、 的最优路由会落在同 一路由上。 n汇集树（sink tree） n从所有的源结点到一个给定的目的结点 的最优路由的集合形成了一个以目的结点为 根的树，称为汇集树； n路由算法的目的是找出并使用汇集树。 一个子网路由器B的汇集树 1. 最短路由选择 n基本思想 n构建子网的拓扑图，图中的每个结点代 表一个路由器，每条弧代表一条通信线路。 为了选择两个路由器间的路由，算法在图中 找出最短路径。 n测量路径长度的方法 n结点数量 n地理距离 n传输延迟 n距离、信道带宽等参数的加权函数 Dijkstra算法 n每个结点用从源结点沿已知最佳路径到本结点的 距离来标注,标注分为临时性标注和永久性标注；

8、 n初始时,所有结点都为临时性标注,标注为无穷大； n将源结点标注为0,且为永久性标注,并令其为工作 结点； n检查与工作结点相邻的临时性结点,若该结点到工 作结点的距离与工作结点的标注之和小于该结点的 标注，则用新计算得到的和重新标注该结点； n在整个图中查找具有最小值的临时性标注结点， 将其变为永久性结点，并成为下一轮检查的工作结 点； n重复第四、五步,直到目的结点成为工作结点 最初五步计算从A到D的最短路径，箭头指示工作节点 Dijkstras algorithm 2. 扩散法路由选择(洪泛算法) n工作原理：将收到的每一个分组，从除了分组到 来的线路外的所有输出线路上发出 n缺点：产

9、生大量的重复分组 n抑制措施： n让每个分组头包含站点计数器； n记录下分组扩散的路径(记下来自于某源路由器的 序列号，可用一计数器)； n选择性扩散 n应用情况 n路由器和线路的资源过于浪费，实际很少直接采 用； n具有极好的健壮性，可用于军事应用； n作为衡量标准评价其它路由算法。 3. 基于流量的路由选择 n基本思想 n既考虑拓扑结构，又兼顾网络负荷 n前提：每对结点间平均数据流是相对稳定和可预 测的 n根据网络带宽和平均流量，可得出平均包延迟， 因此路由选择问题归结为找产生网络最小延迟的路由 n提前离线（off-line）计算 n需要预知的信息 n网络拓扑结构； n通信量矩阵Fij；

10、n线路带宽矩阵Cij； n路由算法（可能是临时的） (a)用kb/s表示线路载荷的子网 (b)用分组/s表示通信量和路由选择矩阵 采用了平均分组长度为800位的上图所示网络的分析， 反向通信量（BA,CB等）与正向通信量相同 1/ = 800 bits 根据排队论，平均延迟 T = 1/ (C - ) 5.2.2 动态路由选择算法 n可根据网络的变化适时调整路由表选择 最佳路径，有利于改善网络的性能。但算 法复杂，增加网络负担，有时还会因反应 太快引起振荡或反应太慢不起作用。 n工作过程包括四部分：测量、报告、更 新、决策。 1. 距离向量路由算法 n基本思想 n每个路由器维护一张表，表中给出

11、了到 每个目的地的已知最佳距离和线路，并通过 与相邻路由器交换距离信息来更新表； n以子网中其它路由器为表的索引，表项 包括两部分：到达目的结点的最佳输出线路 ，和到达目的结点所需时间或距离； n每隔一段时间，路由器向所有邻居结点 发送它到每个目的结点的距离表，同时它也 接收每个邻居结点发来的距离表； n邻居结点X发来的表中，X到路由器i的距 离为Xi，本路由器到X的距离为m，则路由器 经过X到i的距离为Xi + m。根据不同邻居发 来的信息，计算Xi + m，并取最小值，更新 本路由器的路由表； n“距离”:到目的路由器的站点数、估计 的时间延迟、路由排队的分组估计总数或 类似的值 目的站

12、最短距离估计值 输出线路 交换距离信息更新路由表示例 n缺点 n开销大(节点间要不断的相互交换信息) n交换的信息从相邻节点开始，由于延时 获得全网状态信息的时间有先有后，有可能 先前的最佳路径在当前已经不是最佳了，甚 至是不通的，最终造成阻塞 无穷计算问题 第1次交换后 第3次交换后 ABCDE 1234 初始时 3234 第1次交换后 3434 第2次交换后 5454 第3次交换后 5656 第4次交换后 7676 第5次交换后 7878 第6次交换后 （b） . . . ABCDE 初始时 1 12 第2次交换后 123 123 第4次交换后 （a） 算法的缺陷：对好消息反应迅速，对坏消

13、息反应迟钝； 水平分裂算法 n工作过程与距离向量算法相同，区别在 于到X的距离不向真正通向X的邻居结点报 告，使得坏消息传播的也快。 n虽然广泛使用，但有时候会失败。 水平分裂算法一个失败 的例子 2. 链路状态路由算法 n距离向量路由算法的主要问题 n选择路由时，没有考虑线路带宽； n路由收敛速度慢 n链路状态路由算法 n发现邻居结点，并学习它们的网络地址 ； n测量到每个邻居结点的延迟或开销； n将所有学习到的内容封装成一个包； n将这个包发送给所有其它路由器； n计算到每个其它路由器的最短路径 n根据Dijkstra算法计算最短路径； 3. 分级路由 n网络规模增长带来的问题 n路由器中

14、的路由表增大； n路由器为选择路由而占用的内存、CPU时间和网 络带宽增大。 n分层路由 n分而治之的思想； n根据需要，将路由器分成区域（regions）、聚 类（clusters）、区（zones）和组（groups） n分层路由带来的问题 n路由表中的路由不一定是最优路由。 4.固定路由选择 n路由表是事先设定好的。一般，网络中有一个 网络控制中心，由它按照最佳路由算法求出每对 源、目的节点的最佳路由，然后为每一节点构造 一个固定路由表并分发给各个节点。 n优点：简便易行，在负载稳定，拓扑结构变化 不大的网络中运行效果很好。 n缺点：灵活性差，无法应付网络中发生的阻塞 和故障。 5.3

15、路由选择协议 n自治系统(AS)：即遵循共同的路由策略 统一管理下的网络群 n内部网关协议(interior gateway protocol): 在自治系统内部执行路由功能。如路由信 息协议(RIP)、开放最短路径优先(OSPF) n外部网关路由协议(exterior gateway protocol) :在不同的自治系统间进行路由。 如边缘网关协议(BGP) 路由信息协议(RIP) n用中间路由器的数目测量距离； n每个路由器向与它相连的网络发送说明它能在 一个站点内到达的网络的信息包； n与相应网络相连的路由器据此推断出自己可以 通过两个站点到达该网络，并更新路由表； n依次类推，各个路

16、由器建立自己的路由表； n各个路由器不断接收信息、存储、再发送信息 来建立、维护自己的路由表。 路由信息协议(RIP) nRIP分组在IP之上用UDP传送。RIP通过对从源到目的 的最大跳数加以限制来防止路由环，最大值为15。 nRIP使用了一些计时器来控制其性能，包括路由更新 计时器、路由超时和路由清空的计时器。 RIP的局限性 nRIP约定目的端距离值超过15就不可达，随着 互连网的增长，使得RIP不适合在大型网络应用 ，但如果允许更大的距离值，会造成初始化或拓 扑改变时协议的收敛时间增加。 nRIP采用路段数作为度量值，但过分简化的距 离值可能使得路由选择表达不到最佳状态。 n支持RIP的设备要从所有设备接收RIP更新向量 ，可能会使个别设备的配置错误影响到整