HA
1）经过标准 的IP选路， 发往移动节 点的数据包 抵达归属网
FA
移动节点
4）移动节点发出 的数据包通过标 准的IP选路规程 发送到目的地 （FA为移动节点 的缺省Router）
IP主机
Copyright ChenBing Email:cb_china@ 南京航空航天大学网络研究室
Copyright ChenBing Email:cb_china@
南京航空航天大学网络研究室 15
通信量控制策略：漏桶算法
基本漏桶的原理
– 固定服务时间的单服务员 排队系统 – 主机与网络之间有一个带 漏桶的接口（有限内部队 列）；一旦队列满，主机 再发出的分组将被丢弃； 接口每隔一个时钟节拍向 网络发送一个分组 – 适用于固定长度分组
传输层
• 子网内的虚电路与数据报 网络层 • 分组排队与服务策略 • 选路算法 数据链路层 • 重传策略 • 应答策略 • 分组丢弃策略 • 分组生命期管理 • 失序缓存策略 • 流控制策略
Copyright ChenBing Email:cb_china@
南京航空航天大学网络研究室 12

流控制 拥塞控制与流量控制的区别
– 作用范围不同，前者涉及全局，后者涉及点到点之间 – 拥塞控制确保全网畅通；而流量控制只负责源端---目的端 的点到点通信，确保发送速率 ≤ 接收速率

Copyright ChenBing Email:cb_china@
南京航空航天大学网络研究室
主机
分组 无规则的流
包含一个 漏桶的接口
装有分组的 漏桶
有规则的流
网络
Copyright ChenBing Email:cb_china@ 南京航空航天大学网络研究室 16
通信量控制策略：漏桶算法
字节计数漏桶
– 适用于可变长度分组 – 漏桶每隔一个固定的间隔输出固定数目的字节，规定每 节拍发送的字节数， – 每个节拍开始时，计数器初始化为n，如果队列的第一个 分组的字节数小于当前计数器值，就将其发送出去。计 数器减去分组的字节数。只要计数器的值足够大，下一 个分组也可能发送。如果计数器的值小于队列中下一个 分组的长度字节数，传输便停止，直到下一个节拍开 始。此时，这些剩余字节都将被覆盖丢弃

虚电路和数据报的选择
– 很多拥塞算法仅仅用于虚电路子网
Copyright ChenBing Email:cb_china@
南京航空航天大学网络研究室 13
影响拥塞的策略（开环方法）

分组排队和服务策略
– 关系到是否为路由器的每条输入线路建立一个队列，每 条输出线一个队列，或者兼而有之；还关系到分组的处 理顺序，如循环排序或者基于优先级
Copyright ChenBing Email:cb_china@
令牌（每∆T 产生一个）
漏桶容量W
输入分 组队列 输出分组
南京航空航天大学网络研究室 18
通信量控制策略：令牌桶算法

举例
– 发送之前，桶中有3个令牌，5个分组等待发送 – 每传送一个分组，消耗1个令牌 – 消耗3个令牌，传递3个分组，还有2个分组等待新令牌的产生
4
假如没有拥塞和流控制…

情况1
– λBA＝7Kbps，λCD＝0，不会出现拥塞 – B->Y，Y->X，X->A每段速率均为7Kbps
B 16 Y λBA X 8 8 D 64 32 Z λCD 16 C

情况2
– λBA＝8+βKbps(β>0)，λCD＝0，出现拥塞 – 在某一时刻，X节点的缓冲区满，Y发出的 分组将被X丢弃，Y将保留未确认分组以便 重发，结果Y节点缓冲区满，最后Y->X链 路的业务量将达到？B->Y的业务量将达 到？ – 解决方案： A （1）网络备有足够的容量，X->A链路能够适 应B节点最大可能的业务量 （2）限制B节点的最大业务量
南京航空航天大学网络研究室 14
拥塞控制：通信量整形
目的：
– 引起拥塞的主要原因之一是业务的突发性 – 如果主机能够以均匀的速率发送，则拥塞发生的 频率将大大降低 – 调整数据传送的平均速率和突发性，迫使分组以 可预见的速率发送 – 对于虚电路方式，用户和子网事先约定传输模式 – 对于数据报方式，在传输层使用，如TCP
– – –
链路层、网络层和传输层的超时间隔过小 报文生命期太短 流量控制窗口大小，重传方式（选择重传或后退 N步）
Copyright ChenBing Email:cb_china@
南京航空航天大学网络研究室 10
拥塞控制
• 控制论的角度：
开环 -- 静态方法，通过预先良好的设计来避免拥塞 闭环 -- 向源端反馈 ： (1) 实时检测网络，确定拥塞发生的时间和地点 (2) 传送拥塞信息，三种方法：由路由器回送源端；在分组 中设置某些字段指示拥塞；通过调查分组显式询问拥塞状况 (3) 源端调整操作：增加资源；降低负载
•
拥塞控制算法分类
{
开环 闭环
{ {
作用于源端 作用于目的端 显式反馈 隐式反馈
南京航空航天大学网络研究室 11
Copyright ChenBing Email:cb_china@
影响拥塞的策略（开环方法）
层次 策略 • 重传策略 • 应答策略 • 失序缓存策略 • 流控制策略 • 超时确定

情况3
– λBA＝7Kbps，λCD＝ 7Kbps ，不会出现拥 塞 – 发往A和D的总数据率为14Kbps
Copyright ChenBing Email:cb_china@ 南京航空航天大学网络研究室
5
假如没有拥塞和流控制…

情况4
– λBA＝8+βKbps(β>0)，λCD＝7Kbps，B 至A与C到D的分组共享X的缓冲区容量 – B->A的业务请求将导致X节点缓冲区满 – 结果：C和B发出的分组将被频繁丢弃 – 不公平性：C受到B的牵连，并且由于 Y->X的速率是Z->X的速率的两倍，因 此，X到D的速率将是X到A的一半，即 4Kbps – 结论： （1）总吞吐量降低 （2）对主机C的业务量待遇不公 – 解决方案： （1）网络备有足够的容量，X->A链路能 够适应B节点最大可能的业务量 （2）限制B节点的最大业务量 （3）分别保留缓冲区
南京航空航天大学网络研究室
7
拥塞和流控制

拥塞
– ∑ 对资源的需求 > 可用资源时，网络的吞吐量（交付的分 组）将随输入负载（发送的分组）的增加而严重下降 – 死锁：拥塞发展到一定程度，已经没有可用资源，吞吐量降 为0，整个网络瘫痪 – 是全局问题，涉及到所有主机、路由器以及路由器存储转发 的过程和所有其它减少网络运载能力的因素 – 仅涉及发送方和接收方之间点到点的业务流 – 保证发送方不会连续发送速率高于接收方可接收速率的数据

丢弃策略
– 当没有剩余空间时，哪些分组被丢弃
路由选择算法
– 好算法能够通过将通信量分散到所有线路上来避免拥 塞；坏算法会将过多的通信量发送到本来已经拥塞的线 路上

分组生命周期
– 太长，丢失的分组可能会长时间地阻碍工作；太短，分 组可能在到达目的地之前就超时，由此导致重传
Copyright ChenBing Email:cb_china@
B 16 Y λBA X 8 A 8 D 64 32 Z λCD 16 C
Copyright ChenBing Email:cb_china@
南京航空航天大学网络研究室
6
假如没有拥塞和流控制…
吞吐量下降 不公平性
Copyright ChenBing Email:cb_china@
最大速率突发的持续时间(S)的计算
– 设令牌桶容量为C字节，令牌到达速率为ρ字节/秒，桶 的最大输出速率为M字节/秒，则有 C+ ρS = MS，即 S = C / ( M - ρ )
Copyright ChenBing Email:cb_china@
南京航空航天大学网络研究室 20
第三章 网络层协议与算法
陈兵
南航航空航天大学 计算机网络研究室 Cb_china@
Copyright ChenBing Email:cb_china@ 南京航空航天大学网络研究室
1
Review:路由协议
路由协议分类
通信量控制策略：令牌桶算法
举例：
– 假设：一个计算机能以25MB/s的速率产生数据，网络也能以该速 率传输。但网络中的路由器只能在很短的间隔内可以处理，大部 分时间只能以不超过2MB/s的速率工作。假定输入数据的突发长 度为1MB，持续40ms。漏桶的输出速率2MB/s（令牌桶算法中当 令牌到达时），容量C＝1MB，则： S = C / ( M - ρ ) – 输入：将以25MB/s的速率持续40ms – 漏桶算法：将以2MB/s的速率持续500ms – 令牌漏桶（C＝250KB）：先以25MB/s速率持续约11ms，然后 以2MB/s的速率持续约364ms – 令牌漏桶（C＝500KB）：先以25MB/s速率持续约22ms，然后 以2MB/s的速率持续约228ms
子网运载的最大容量 吞吐量 理想曲线的流量控制 实际的流量控制 无流量控制
死锁 轻度拥塞 拥塞
Copyright ChenBing Email:cb_china@
输入负载
南京航空航天大学网络研究室
9
引起拥塞的原因
过多的突发报文引起缓冲区淹没 路由不合理 路由器处理能力不足 重传处理不当
影响拥塞的策略（开环方法）

重传策略
– 处理发送者的速度多快会超时以及超时后传送什么，使 用重传还是退后N帧