就是一个固定长度的分组队列，主机发送的每一 个分组都加入到队列中排队，如果队列满则分组被丢 弃，同时队列按照约定的速率向网络发送分组。

两种情况：


分组长度固定 让队列每隔一个固定的时间发送一个分组。 分组长度可变 规定队列每次可以发送的最大字节数。
漏桶算法举例※
[例] 假设主机和网络的数据速率都是25MB/s，但路由器处 理能力较弱，在较长时间里，进入路由器的平均数据速率 最好不超过 2MB/s。设主机每秒产生一个突发数据块 (峰值速率25MB/s )，数据块长度为1MB。 [解] 为了限制数据进入网络的平均速度，应选择漏桶的输出 速率为ρ= 2MB/s，漏桶的容量为C=1MB，这样漏桶每次 最多可装入1MB的数据，不会造成数据丢失。

重传、乱序缓存、 确认、流控 子网中的虚电路 和数据报、分组 排队和服务策略、 分组丢弃策略、 路由算法、分组 的生存时间管理 重传、乱序缓存、 确认、流控、超 时中止

网络层


传输层

开环控制 — 通信量整形

通信量整形(Traffic Shaping)的基本思想


网络上，突发的通信量是造成拥塞的主要原因。


链路状态路由算法(Link State Routing)
分级路由(Hierarchical Routing)
拥塞的基本概念


拥塞(congestion)：网络中存在过多分组的时候，网络性能 降低，这种情况被称为拥塞。图例 造成拥塞的原因



多个输入对应一个输出，只增加内存，并不能解决问题。 慢速处理器。 低带宽线路。 针对某个因素的解决方案，只能对提高网络性能起到一点点作用， 甚至可能仅仅是转移了影响性能的瓶颈。 拥塞控制需要确保通信子网能够承载用户提交的通信量，是一个 全局性问题，涉及主机、路由器等很多因素。 流量控制与点到点的通信量有关，主要解决快速发送方与慢速接 收方的问题，是局部问题，一般都是基于反馈进行控制的。
最优化原则

最优化原则(optimality principle)

如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由 会落在同一路由上。 路由算法的目的是找出并使用汇集树。

汇集树(sink tree)


从所有的源 结点到一个给定 的目的结点的最 优路由的集合形 成了一个以目的 结点为根的树， 称为汇集树。
几种常见的路由算法

静态路由算法

最短路径选择(Shortest Path Routing) 洪泛算法(Flooding Routing) 基于流量的路由算法(Flow-Based Routing)

动态路由算法g)

如何反馈 —— 反馈方法



在分组结构中保留一个位或一个域来表示发生拥塞，一旦发生拥 塞，路由器将所有输出分组的拥塞位填充，报警。 主机或路由器主动地、周期性地发送探报(probe)，查询是否发生 拥塞。

如何解决 —— 利用拥塞控制算法
开环控制 — 拥塞预防策略

影响拥塞的网络设 计策略

数据链路层
数据发送的峰值速率为 M = 25 MB/s，则最大突发长度为 ： S= C/(M-ρ) ≈11ms 也即：一开始可按峰值速率连续发送11ms，然后以2MB/s的平 均速率继续发送直至结束。若令牌桶容量750KB时最大突发长度 可33ms。

漏桶和令牌桶算法的比较

通信量整形策略不同

漏桶算法不允许空闲主机积累发送权。 令牌桶算法允许空闲主机积累发送权，以便以后发送大的突发数 据，最大为桶的大小。


闭环控制(因地制宜)

监控系统，发现何时何地发生拥塞。 把发生拥塞的消息传给能采取动作的站点。 调整系统操作，解决拥塞问题。

闭环控制操作需要完成以下三个问题：何为拥塞、如何反馈和如 何解决。
闭环控制

何为拥塞 —— 衡量网络拥塞的参数

缺乏缓冲区造成的丢包率 平均队列长度 超时重传的分组数目 平均分组延迟 分组延迟变化(Jitter) 向负载的发生源发送一个报警分组，这同时加强了拥塞。
输入负载
图 拥塞控制所起的作用
直接死锁

直接死锁即由互相占用了对方需要的资源而造成的死锁。 例如两个结点都有大量的分组要发往对方，但两个结点中的缓 存在发送之前就已经全部被待发分组占满了。


当每个分组到达对方时，由于没有地方存放，只好被丢弃。发送分 组的一方因收不到对方发来的确认信息，只能将发送过的分组依然 保存在自己结点的缓存中。 这两个结点就这样一直互相僵持着，谁也无法成功地发送出一个分 组。
虚电路
4.网络层的两种实现方式
面向连接
数据报
5.网络层提供的服务
面向无连接
举例

请判断是虚电路还是数据报？ M
R4 R5 HB
M1
M2
M3
R3
H
HA R1 R2
M1 M2 M1 H
M3
M3
M2
路由算法

路由算法是网络层软件的一部分

子网采用数据报方式，每个分组都要做路由选择。 子网采用虚电路方式，只需在建立连接时做一次路由选择。

基本思想：漏桶存放令 牌，每T秒产生一个令 牌，分组发送传输之前 必须获得一个令牌，传 输之后删除该令牌。 令牌代表的不是发送一 个分组的权利，而是可 以发送的字节数。

令牌桶算法※
令牌桶模型※

说明

主机
绿色-未整形的流量 紫色-整形后的流量 红色-桶内令牌 黄色-丢失的令牌
输入流量

效果

漏桶算法※
漏桶算法
无论水流进桶的速度为多少，只要桶中有水，水从桶中外 漏的速度是恒定的。桶空了，速度为零。桶满了，水外泄。
漏桶模型※
主机

说明

绿色-未整形的流量 紫色-整形后的流量 红色-丢失的分组
未经整形的流量 丢失的分组
分组漏桶 漏桶接口
整形后流量
网络
漏桶实现※

漏桶的本质
报文 A、B 和 C 经过路由器 P、Q 和 R 发往主机 H。 每一报文由 4 个分组构成。每个路由器的缓存只能容纳 4 个分组。 路由器 R 已为报文 A 预留了 4 个分组的缓存。 由于分组 A3 还未到达，所以目前还不能交付给主机 H。 分组 A3 暂存于路由器 P 的缓存中，它无法转发到路由 器 Q，因为路由器 Q 的缓存已全占满了。
Chap5 网 络 层
网络层主要内容

网络层概述


路由算法




网络层的地位 网络层需要解决的问题 数据报和虚电路 网络层提供的服务



拥塞控制算法


拥塞控制的基本原理 开环控制

最优化原则 最短路径路由算法 洪泛算法 基于流量的路由算法 距离向量路由算法 链路状态路由算法 分级路由
拥塞预防策略 通信量整形(漏桶和令牌桶) 流说明 虚电路网络中的拥塞控制 抑制分组 负载丢弃

闭环控制

Internet网络层协议(IP)
1.网络层的地位
通信子网的最高层
屏蔽各种不同类型网络 之间的差异 实现全网的数据传输
2.网络层需要解决的问题 3.三种通信交换方式
线路交换 报文交换 分组交换
拥塞控制
死锁主要有两种:一种是直接死锁,另一种重装死锁. (1)直接死锁:即由互相占用了对方需要的资源而造成的死锁.
①发送分组
⑥丢掉B 发来的 分组
A
分组1 分组2 分组3 ④发送分组
B
分组1 分组2 分组3
③丢掉A 发来的 分组
⑤节点A 的缓存已 满
②节点B 的缓存已 满
分组n
分组m
图 直接死锁的例
强迫分组以某种可以预见的速率传送，减少拥塞，这种方法就被 称为通信量整形。 此方法广泛应用于ATM网络中。 漏桶算法和令牌桶算法都可以实现通信量整形。 基本原理：图例。 在计算机中的使用




漏桶算法(The Leaky Bucket Algorithm)

漏桶——有限内部队列；水 —— 通信量，需要发送的分组。 分组到达队列时，队列满，分组被丢弃；队列空，分组放置在队尾。 将用户发出的不平滑的分组流转变成网络中平滑的分组流。 漏桶算法既可以用于分组长度固定的协议，如ATM，使用分组计数； 也可用于可变长分组的协议，如IP，使用字节计数。
拥塞控制的分类

根据控制论，拥塞控制可分为两类。 开环控制(防患于未然)

通过良好的设计解决问题，以避免拥塞发生。一旦运行，就不再 做中间阶段的更正。

进行开环控制的工具需要决定何时接收新的分组、何时丢弃分组、 丢弃哪些分组，制定网络中不同地点的计划表等。利用开环进行 拥塞控制时，所有这些操作都不会考虑网络的当前状态。 基于反馈机制。其工作过程为：


不采用漏桶算法： 1MB的数据块进入网络中只要 1MB÷25MB/s =40ms 就会全部流入网中 采用漏桶算法： 1MB的数据块进入网络中需要时间 1MB÷2MB/s =500ms 才能全部进入网中 平滑了原来波动很大的通信量曲线。
令牌桶算法

由于漏桶算法不够灵活，因 此加入令牌机制。 令牌桶算法 (The Token Bucket Algorithm)

桶中存放的内容不同


漏桶中存放的是数据，桶满了丢弃数据。 令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据。