第五章 网络层 (2)
5.4 拥塞控制
5.5 X.25协议拥塞控制（ 1）
什么是拥塞？
当到达通信子网中某一部分的分组数高于一定的水平，使得该部分网络来不及处理这些分组，从而使这部分以至整个网络的性能下降
平均分组延迟和吞吐率与提供的负载之间的关系提供的负载 （ 发送的分组 ） 提供的负载 （ 发送的分组 ）
吞吐量
（
递交的分组
）
开销 平均分组延迟理想的控制的无控制的无控制的控制的拥塞控制（ 2）
拥塞由于网络资源没法满足用户的要求而引起：
路由器的缓冲区有限
通信线路带宽有限（线路带宽的不匹配） (a)(b)
CPU处理能力
拥塞是一个动态的概念，拥塞还可能带来恶性循环
S R R D
19.2kbps
(a) 传输一个文件需要 5分钟
S R R D
19.2kbps
(b) 传输一个文件需要 7小时
1Mbps
A C
B D
R
（ c）所有链路为 1Gbps
图 5.12 拥塞的发生可能拥塞控制和流量控制
流量控制机制用来保证发送端不以比接收者能承受的速率更高的速度传输数据
拥塞控制确保通信子网能够有效为主机传递分组网络
(a)
(b)
流量控制和拥塞控制拥塞控制区域
拥塞控制用来保证网络不进入拥塞崩溃点右边的区域，负载超过这一点后吞吐量会突然降低
拥塞避免工作在拥塞临界点处，鼓励用户增加负载，只要不会使延迟时间迅速增加就可以。
knee（ 拥塞临界点 ） cliff（ 拥塞崩溃点 ）
吞吐量拥塞控制策略
开环：通过良好的设计（,Design it right” ）来避免拥塞出现
决定何时接受新的负载
决定何时丢弃分组和丢弃哪个分组
闭环：建立在反馈的概念之上
监视子网的拥塞状况
丢包率
队列长度
由于超时重传的分组数目
平均分组延迟和延迟抖动情况
传递拥塞指示：显式和隐式
通知源
通知邻居
对拥塞作出响应影响拥塞控制的策略（ 1）
网络层：
虚电路或数据报？
分组排队和服务策略：
分组丢弃策略
路由选择算法
生命期管理策略
数据链路层：
重传机制：影响基于超时的拥塞控制策略的稳定性
排队和服务策略
分组丢失策略
确认策略：反馈延迟
流量控制：基于窗口和基于速率。
影响拥塞控制的策略（ 2）
拥塞控制策略要求满足：
低开销
公平
动态
,坏,环境下工作
全面考虑整个网络的情况许可控制
如果已经出现拥塞，则不允许新的虚电路
或者建立虚电路，但是绕过拥塞区域
资源预约：建立虚电路时就服务质量进行协商，
并且预留相应的资源。
通信量控制策略
通信量整形：子网强迫分组以某种预定的速率发送
用户则通过流规范来说明自己的通信量模式
通信子网通过通信量控制策略进行控制
漏桶算法：
恒定服务时间的单服务员排队系统
队列满之后，新的分组被丢弃
主机每隔一个时间节拍向网络发送一个分组漏桶算法
分组大小固定：漏桶由一个有限队列构成，每一个 clock tick，发送一个分组
分组大小可变：字节计数
每个节拍允许发送一定数量的字节规则的分组流主机网络包含一个漏桶的接口装有分组的漏桶分组不规则的分组流令牌桶算法（ 1）
突发负载到来时希望输出速率可以弹性增加一些。
令牌桶,每隔 秒生成一个令牌，而漏桶可以保留这些令牌。如果要发送分组，必须首先抓住一个令牌，
在发送分组后令牌被销毁。
T?
主机网络每隔往桶中装入一个令牌 桶中装有令牌
（ a）
主机网络
（ b）
图 5.7 令牌桶算法令牌桶算法（ 2）
令牌桶算法允许主机把空闲时候的发送权保留，最多为桶的大小，从而允许突发的通信量
漏桶在桶满时丢弃分组，令牌桶在桶满时丢弃令牌
字节计数的令牌桶算法：令牌代表可以发送的字节数令牌桶算法（ 3）
允许的最大突发时间 S：
最大输出速率为 M字节 /秒
令牌桶的容量为 C字节
令牌产生速率为?字节 /秒
MSSC
反馈机制（ 1）
监视网络的状态：
反馈机制：
抑制分组：路由器发送给源端
路由消息中传递
源端发送端到端的探测分组：
每个分组包括一个拥塞反馈字段：
反向反馈：
正向反馈
源端调整通信量：
拥塞反馈可能连续到来
faa o l dn e w )1(
反馈机制（ 2）
高速网络环境下,hop-by-hop反馈
上游路由器需要更多的缓冲区
加权公平队列：
公平队列：
每条输出线路有多个队列，分别对应源端
路由器循环扫描该队列，从下一个队列中取出第一个分组
分组大小可能不同，采取字节计数的方法
有些站点分配更多的带宽，加权公平队列负载脱落
分组丢弃，丢弃哪些分组？
随意丢弃分组并不是很适合：
葡萄酒策略和牛奶策略：文件传输和多媒体
优先级策略：首先丢弃最低优先级的分组
有些网络中，丢弃一个分组时，可以丢弃那些属于同一个消息的所有分组。
需要考虑应用层的信息
X.25协议
虚电路业务,SVC和 PVC
逻辑信道群号 (4b)＋逻辑信道号 (8b)：
呼叫建立和呼叫拆除过程：
DTE?DCE?Remote DCE?Remote DTE
发出的呼叫由主叫 DTE选择虚电路号
入呼叫由 DCE选择虚电路号
呼叫冲突时，入呼叫无效。
高层协议分组层数据链路层物理层分组层数据链路层物理层分组级协议帧级协议物理级协议与远程 DTE之间的高层协议
X.25
物理连接DTE DCE
图 5.17 X.25的分层结构
X.25：
多路复用
DTE可以建立 4095条虚电路（ 0保留传递诊断分组）
DTE-DCE链路提供全双工的多路复用，永久虚电路永久占用一个虚电路号
数据传输：和数据链路层类似
流量控制和差错控制
中断分组：紧急数据，不受流量控制机制的影响习题
5.13
5.16
5.4 拥塞控制
5.5 X.25协议拥塞控制（ 1）
什么是拥塞？
当到达通信子网中某一部分的分组数高于一定的水平，使得该部分网络来不及处理这些分组，从而使这部分以至整个网络的性能下降
平均分组延迟和吞吐率与提供的负载之间的关系提供的负载 （ 发送的分组 ） 提供的负载 （ 发送的分组 ）
吞吐量
（
递交的分组
）
开销 平均分组延迟理想的控制的无控制的无控制的控制的拥塞控制（ 2）
拥塞由于网络资源没法满足用户的要求而引起：
路由器的缓冲区有限
通信线路带宽有限（线路带宽的不匹配） (a)(b)
CPU处理能力
拥塞是一个动态的概念，拥塞还可能带来恶性循环
S R R D
19.2kbps
(a) 传输一个文件需要 5分钟
S R R D
19.2kbps
(b) 传输一个文件需要 7小时
1Mbps
A C
B D
R
（ c）所有链路为 1Gbps
图 5.12 拥塞的发生可能拥塞控制和流量控制
流量控制机制用来保证发送端不以比接收者能承受的速率更高的速度传输数据
拥塞控制确保通信子网能够有效为主机传递分组网络
(a)
(b)
流量控制和拥塞控制拥塞控制区域
拥塞控制用来保证网络不进入拥塞崩溃点右边的区域，负载超过这一点后吞吐量会突然降低
拥塞避免工作在拥塞临界点处，鼓励用户增加负载，只要不会使延迟时间迅速增加就可以。
knee（ 拥塞临界点 ） cliff（ 拥塞崩溃点 ）
吞吐量拥塞控制策略
开环：通过良好的设计（,Design it right” ）来避免拥塞出现
决定何时接受新的负载
决定何时丢弃分组和丢弃哪个分组
闭环：建立在反馈的概念之上
监视子网的拥塞状况
丢包率
队列长度
由于超时重传的分组数目
平均分组延迟和延迟抖动情况
传递拥塞指示：显式和隐式
通知源
通知邻居
对拥塞作出响应影响拥塞控制的策略（ 1）
网络层：
虚电路或数据报？
分组排队和服务策略：
分组丢弃策略
路由选择算法
生命期管理策略
数据链路层：
重传机制：影响基于超时的拥塞控制策略的稳定性
排队和服务策略
分组丢失策略
确认策略：反馈延迟
流量控制：基于窗口和基于速率。
影响拥塞控制的策略（ 2）
拥塞控制策略要求满足：
低开销
公平
动态
,坏,环境下工作
全面考虑整个网络的情况许可控制
如果已经出现拥塞，则不允许新的虚电路
或者建立虚电路，但是绕过拥塞区域
资源预约：建立虚电路时就服务质量进行协商，
并且预留相应的资源。
通信量控制策略
通信量整形：子网强迫分组以某种预定的速率发送
用户则通过流规范来说明自己的通信量模式
通信子网通过通信量控制策略进行控制
漏桶算法：
恒定服务时间的单服务员排队系统
队列满之后，新的分组被丢弃
主机每隔一个时间节拍向网络发送一个分组漏桶算法
分组大小固定：漏桶由一个有限队列构成，每一个 clock tick，发送一个分组
分组大小可变：字节计数
每个节拍允许发送一定数量的字节规则的分组流主机网络包含一个漏桶的接口装有分组的漏桶分组不规则的分组流令牌桶算法（ 1）
突发负载到来时希望输出速率可以弹性增加一些。
令牌桶,每隔 秒生成一个令牌，而漏桶可以保留这些令牌。如果要发送分组，必须首先抓住一个令牌，
在发送分组后令牌被销毁。
T?
主机网络每隔往桶中装入一个令牌 桶中装有令牌
（ a）
主机网络
（ b）
图 5.7 令牌桶算法令牌桶算法（ 2）
令牌桶算法允许主机把空闲时候的发送权保留，最多为桶的大小，从而允许突发的通信量
漏桶在桶满时丢弃分组，令牌桶在桶满时丢弃令牌
字节计数的令牌桶算法：令牌代表可以发送的字节数令牌桶算法（ 3）
允许的最大突发时间 S：
最大输出速率为 M字节 /秒
令牌桶的容量为 C字节
令牌产生速率为?字节 /秒
MSSC
反馈机制（ 1）
监视网络的状态：
反馈机制：
抑制分组：路由器发送给源端
路由消息中传递
源端发送端到端的探测分组：
每个分组包括一个拥塞反馈字段：
反向反馈：
正向反馈
源端调整通信量：
拥塞反馈可能连续到来
faa o l dn e w )1(
反馈机制（ 2）
高速网络环境下,hop-by-hop反馈
上游路由器需要更多的缓冲区
加权公平队列：
公平队列：
每条输出线路有多个队列，分别对应源端
路由器循环扫描该队列，从下一个队列中取出第一个分组
分组大小可能不同，采取字节计数的方法
有些站点分配更多的带宽，加权公平队列负载脱落
分组丢弃，丢弃哪些分组？
随意丢弃分组并不是很适合：
葡萄酒策略和牛奶策略：文件传输和多媒体
优先级策略：首先丢弃最低优先级的分组
有些网络中，丢弃一个分组时，可以丢弃那些属于同一个消息的所有分组。
需要考虑应用层的信息
X.25协议
虚电路业务,SVC和 PVC
逻辑信道群号 (4b)＋逻辑信道号 (8b)：
呼叫建立和呼叫拆除过程：
DTE?DCE?Remote DCE?Remote DTE
发出的呼叫由主叫 DTE选择虚电路号
入呼叫由 DCE选择虚电路号
呼叫冲突时，入呼叫无效。
高层协议分组层数据链路层物理层分组层数据链路层物理层分组级协议帧级协议物理级协议与远程 DTE之间的高层协议
X.25
物理连接DTE DCE
图 5.17 X.25的分层结构
X.25：
多路复用
DTE可以建立 4095条虚电路（ 0保留传递诊断分组）
DTE-DCE链路提供全双工的多路复用，永久虚电路永久占用一个虚电路号
数据传输：和数据链路层类似
流量控制和差错控制
中断分组：紧急数据，不受流量控制机制的影响习题
5.13
5.16
