流量控制
网络服务模式
指整个通信子网向传输层或资源子网提供的服务规范。
面向连接
优点
1、分组携带虚电路号，带宽利用率高 2、连接一旦建立，容易进行拥塞控制 3、容易实现保证质量服务 4、容易实现计费
无连接
1、无连接开销，分组可立即发送 2、对于通信线路的故障，如路由 器崩溃等，适应性很强，可以及 时绕道
缺点
路由选择算法应具有下列特性：正确性、 简单性、健壮性、稳定性、公平性和最 优性。
优化的目标：分组的平均延时小，网络 吞吐量大。 相互矛盾，因为任何队列系统，在接近 容量的情况下有很长的延迟。 折衷—降低跳数(使分组必须经过的站点 减少到最少)，减少了延迟和消耗的带宽
5.2.1 静态路由选择算法
需要预知的信息
(a)用kb/s表示线路载荷的子网
(b)用分组/s表示通信量和路由选择矩阵
采用了平均分组长度为800位的上图所示网络的分析， 反向通信量（BA,CB等）与正向通信量相同 1/ = 800 bits 根据排队论，平均延迟 T = 1/ (C - )
5.2.2 动态路由选择算法
可根据网络的变化适时调整路由表选择 最佳路径，有利于改善网络的性能。但 算法复杂，增加网络负担，有时还会因 反应太快引起振荡或反应太慢不起作用。 工作过程包括四部分：测量、报告、更 新、决策。
1. 距离向量路由算法
基本思想
每个路由器维护一张表，表中给出了到每个 目的地的已知最佳距离和线路，并通过与相 邻路由器交换距离信息来更新表； 以子网中其它路由器为表的索引，表项包括 两部分：到达目的结点的最佳输出线路，和 到达目的结点所需时间或距离； 每隔一段时间，路由器向所有邻居结点发送 它到每个目的结点的距离表，同时它也接收 每个邻居结点发来的距离表；
链路状态路由算法
根据Dijkstra算法计算最短路径；
3. 分级路由
网络规模增长带来的问题
路由器中的路由表增大； 路由器为选择路由而占用的内存、CPU时间和网络 带宽增大。
分而治之的思想； 根据需要，将路由器分成区域（regions）、聚类 （clusters）、区（zones）和组（groups）… 路由表中的路由不一定是最优路由。
1、有呼叫损耗，有创建开销 2、路由器需要存储虚电路状态信息 3、所有经过失效路由器的虚电路要终 止
虚电路 X.25 ATM 帧中继
1、每个分组必须携带完整的目的 地址，浪费带宽 2、拥塞控制较难实现 3、不易实现保证质量服务
数据报 ARPANET、因特网
实现 实例
数据报子网内路由
虚电路与数据报机制
路由信息协议(RIP)
N1 N3
路由器3
N5
路由器1
路由器2
N2
N4
路由器4
RIP分组在IP之上用UDP传送。RIP通过对从源到目的 的最大跳数加以限制来防止路由环，最大值为15。 RIP使用了一些计时器来控制其性能，包括路由更新 计时器、路由超时和路由清空的计时器。
RIP的局限性
RIP约定目的端距离值超过 15 就不可达，随着 互连网的增长，使得 RIP 不适合在大型网络应 用，但如果允许更大的距离值，会造成初始化 或拓扑改变时协议的收敛时间增加。 RIP 采用路段数作为度量值，但过分简化的距 离值可能使得路由选择表达不到最佳状态。 支持RIP的设备要从所有设备接收RIP更新向量， 可能会使个别设备的配置错误影响到整个网络 的配置。
最初五步计算从A到D的最短路径，箭头指示工作节点
Dijkstra's algorithm
2. 扩散法路由选择(洪泛算法)
工作原理：将收到的每一个分组，从除了分组到 来的线路外的所有输出线路上发出 缺点：产生大量的重复分组 抑制措施：
让每个分组头包含站点计数器； 记录下分组扩散的路径(记下来自于某源路由器的序列 号，可用一计数器)； 选择性扩散
路由信息协议(RIP)
Fra bibliotek用中间路由器的数目测量距离； 每个路由器向与它相连的网络发送说明它能在 一个站点内到达的网络的信息包； 与相应网络相连的路由器据此推断出自己可以 通过两个站点到达该网络，并更新路由表； 依次类推，各个路由器建立自己的路由表； 各个路由器不断接收信息、存储、再发送信息 来建立、维护自己的路由表。
交换距离信息更新路由表示例
缺点
开销大(节点间要不断的相互交换信息) 交换的信息从相邻节点开始，由于延时获得 全网状态信息的时间有先有后，有可能先前 的最佳路径在当前已经不是最佳了，甚至是 不通的，最终造成阻塞
无穷计算问题
算法的缺陷：对好消息反应迅速，对坏消息反应迟钝；
A B ∞ 1 1 1 1 C ∞ ∞ 2 2 2 D ∞ ∞ ∞ 3 3 E ∞ ∞ ∞ ∞ ∞ A 初始时 第1次交换后 第2次交换后 第3次交换后 第4次交换后 B 1 3 3 5 5 7 7 ∞ （a） C 2 2 4 4 6 6 8 . . . ∞ D 3 3 3 5 5 7 7 ∞ E 4 4 4 4 6 6 8 ∞ 初始时 第1次交换后 第2次交换后 第3次交换后 第4次交换后 第5次交换后 第6次交换后
第5章 网络层
网络层概述 路由选择算法 路由选择协议 流量控制和拥塞控制 网络互连设备
5.1 网络层概述
网络层是OSI参考模型中的第三层,目的是屏蔽各 种不同类型网络之间的差异，实现两个端系统之间 的数据透明传送，具体功能包括路由选择、阻塞控 制等 网络服务模式 Internet团体（正努力获得更好的服务质量） 电话公司 虚电路与数据报机制
开放最短路径优先(OSPF)
OSPF是个链接状态路由协议，是由IETF的 IGP工作组为IP网开发的路由协议。 最短路径优先算法（SPF）思路： 每个路由器周期性地发送链路状态信息，提 供其相邻节点的信息或其状态改变信息。通过对 已建立的邻接关系和链接状态进行比较，失效的 路由器可以很快被检测出来，网络拓扑相应地更 动。每个路由器以自己为根计算最短路径树，通 过最短路径树生成路由表。
设计目标
网络层的服务是按下列目标设计的
服务应与通信子网的技术无关 通信子网的数量、类型和拓扑结构对于传输 层来说是隐蔽的 传输层所能获得的网络地址应采用统一的的 编号方式，即使跨越了多个LAN和WAN
网络设计冲突的焦点是网络层究竟应该 提供面向连接还是无连接的服务
实质是将复杂的功能放在何处的问题
邻居结点X发来的表中，X到路由器i的距离 为Xi，本路由器到X的距离为m，则路由器经 过X到i的距离为Xi + m。根据不同邻居发来 的信息，计算Xi + m，并取最小值，更新本 路由器的路由表；
“距离”:到目的路由器的站点数、估计 的时间延迟、路由排队的分组估计总数 或类似的值
目的站 最短距离估计值 输出线路
大量的建立和清除虚电路所需要的开销会影 响虚电路的使用
5.2 路由选择算法
路由选择算法概述 静态路由选择策略 动态路由选择策略
路由选择算法(Routing Algorithm)
是网络层软件的一部分，负责确定所收 到分组应传送的外出路线。 路由选择算法可以分为两大类：
非自适应---事先脱线计算好或设定好的， 在网络启动时就下载到路由器中 自适应---根据拓扑结构、通信量的变化来 改变其路由选择。
vc1 3 H2 0 vc2 A 2 A 入口 出口 H1 0 B 0 H1 1 H1 2 B 1 B 2
0 H4 1
C 0 H4 2 vc5 C 入口 H3 0 B 0
出口
E 0 D 0 vc4
E
入口 出口 B 0 H5 0 D 0 H5 1 C 0 D 0
虚电路与数据报之间的折衷
路由器的内存与带宽 建立虚电路的时间和地址解析的时间 保证服务质量，子网避免拥塞 交换虚电路和永久虚电路
应用情况
路由器和线路的资源过于浪费，实际很少直接采用； 具有极好的健壮性，可用于军事应用； 作为衡量标准评价其它路由算法。
3. 基于流量的路由选择
基本思想
既考虑拓扑结构，又兼顾网络负荷 前提：每对结点间平均数据流是相对稳定和可预测的 根据网络带宽和平均流量，可得出平均包延迟，因此 路由选择问题归结为找产生网络最小延迟的路由 提前离线（off-line）计算 网络拓扑结构； 通信量矩阵Fij； 线路带宽矩阵Cij； 路由算法（可能是临时的）
5.3 路由选择协议
自治系统(AS)：即遵循共同的路由策略统 一管理下的网络群 内部网关协议(interior gateway protocol): 在自治系统内部执行路由功能。如路由信 息协议(RIP)、开放最短路径优先(OSPF) 外部网关路由协议(exterior gateway protocol) :在不同的自治系统间进行路由。 如边缘网关协议(BGP)
分层路由
分层路由带来的问题
4.固定路由选择
路由表是事先设定好的。一般，网络中有一个 网络控制中心，由它按照最佳路由算法求出每 对源、目的节点的最佳路由，然后为每一节点 构造一个固定路由表并分发给各个节点。 优点：简便易行，在负载稳定，拓扑结构变化 不大的网络中运行效果很好。 缺点：灵活性差，无法应付网络中发生的阻塞 和故障。
B 5 2 A 1 4 7 2 C 6 E 3 7 4 F D
