信息网络与协议讲义15 ch07

1、 信息网络与协议 第第七七章章 业务量管理业务量管理 信息网络与协议信息网络与协议 主要内容主要内容 分组分类分组分类 业务量监管业务量监管 分组调度分组调度 队列管理队列管理 流量调节：保证用户按照约定流量调节：保证用户按照约定 （SLA）使用网络资源）使用网络资源 流量控制：网络分配资源保证流量控制：网络分配资源保证 约定（约定（SLA）的用户）的用户QoS 信息网络与协议信息网络与协议 主要内容主要内容 分组分类分组分类 业务量监管业务量监管 分组调度分组调度 队列管理队列管理 信息网络与协议信息网络与协议 流与类流与类 类（类（Class）是一个比流（）是一个比流（flow）更大的概念

2、，）更大的概念， 类由多个流汇聚而成类由多个流汇聚而成 对于路由器来说，判断分组属于哪个流或者对于路由器来说，判断分组属于哪个流或者 哪个类，执行的是相同的操作哪个类，执行的是相同的操作 依据是分组头标中的某些域和事先预设的规则集依据是分组头标中的某些域和事先预设的规则集 这个操作称为分类，在路由器上，分类功能由分这个操作称为分类，在路由器上，分类功能由分 类器来完成类器来完成 信息网络与协议信息网络与协议 分类器分类器 分类器（分类器（Classifier）维护一个规则集）维护一个规则集 分类就是在规则集找到与分组匹配的规则的过程分类就是在规则集找到与分组匹配的规则的过程 在分类器中根据分组

3、头标匹配规则在分类器中根据分组头标匹配规则 输入分输入分 组组 Action 分组分类分组分类 信息网络与协议信息网络与协议 分类器描述分类器描述 规则中域的形式规则中域的形式：Fi对应着用于匹配规则的分组头标域，主要有两种形对应着用于匹配规则的分组头标域，主要有两种形 式，式，前缀前缀和和数值范围数值范围 规则优先级：规则优先级：规则定义了优先级，并且按优先级顺序从高到低排列，规则定义了优先级，并且按优先级顺序从高到低排列，R1 具有最高优先级具有最高优先级分组匹配到的第一条规则优先级最高分组匹配到的第一条规则优先级最高 前缀前缀数值范围数值范围 信息网络与协议信息网络与协议 分类算法分类算

4、法 当规则中的域为前缀时当规则中的域为前缀时 与路由查找算法类似与路由查找算法类似 当规则中的域为数值范围时当规则中的域为数值范围时 K-Way Search Tree来组织数据结构来组织数据结构 几何算法几何算法 规则中的域既可以是前缀，也可以是数值范围规则中的域既可以是前缀，也可以是数值范围 信息网络与协议信息网络与协议 1. 假设规则集中域假设规则集中域F为数值范围，将其在规则中的取值投影到一条直线上为数值范围，将其在规则中的取值投影到一条直线上 2. 在在1的基础上得到的基础上得到Three-way Search Tree结构如下结构如下 对于对于k-way search Tree，

5、每个节点最多包含每个节点最多包含k个指个指 针和针和k-1个端点个端点 假设假设P位于位于I3,查找查找P K-way Search Tree算法过程算法过程 信息网络与协议信息网络与协议 K-way Search Tree算法性能算法性能 Tree的深度为的深度为logkM，M为规则集中指定域为规则集中指定域 的数值范围投影到直线上后的间隔数的数值范围投影到直线上后的间隔数 查找复杂度为查找复杂度为logkM Three-way Search Tree：根据间隔数量进行三等分：根据间隔数量进行三等分 信息网络与协议信息网络与协议 几何算法：原理几何算法：原理 对于前缀或者数值范围形式的域的，

6、都可以表示对于前缀或者数值范围形式的域的，都可以表示 为数值线上的间隔为数值线上的间隔 具有具有d个域的规则表示一个个域的规则表示一个d维超矩形维超矩形 每个待分类分组对应着每个待分类分组对应着d维空间中的一个点维空间中的一个点p 分类器就是一个带有优先级的超矩形集合，分类分类器就是一个带有优先级的超矩形集合，分类 问题等价于找到一个包含点问题等价于找到一个包含点p的具有最高优先级的的具有最高优先级的 超矩形超矩形 适用于基于任意数量和任意类型域的分类适用于基于任意数量和任意类型域的分类 信息网络与协议信息网络与协议 几何算法：几何算法：Cross-Producting Scheme 对于每个

7、域，将所有规则在该域上的取值映射到对于每个域，将所有规则在该域上的取值映射到 数值线上的一个范围数值线上的一个范围 在在d维空间，维空间，d个域所对应的个域所对应的d条数值线的上的范条数值线的上的范 围互相交叉，得到一个交叉乘积表围互相交叉，得到一个交叉乘积表 根据规则集以及规则的优先级，在交叉乘积表中根据规则集以及规则的优先级，在交叉乘积表中 预先设置好交叉区域所对应的规则预先设置好交叉区域所对应的规则 给定分组，根据分组中包含的给定分组，根据分组中包含的d个域信息在每一维个域信息在每一维 执行执行K-way Search Tree算法，找到该分组所对应的算法，找到该分组所对应的 交叉区域，

8、返回该区域所对应的规则交叉区域，返回该区域所对应的规则 信息网络与协议信息网络与协议 1101 00111000 1011 0111 F1 00001111 0000 1111 F2 1100 1000 0100 1011 0011 0111 信息网络与协议信息网络与协议 Cross-Producting Scheme举例举例 查找复杂度为查找复杂度为O(d*tRL)，tRL为在每一维执行范围查找的时间复为在每一维执行范围查找的时间复 杂度，交叉乘积表的大小为杂度，交叉乘积表的大小为O(Nd)，更新代价大，更新代价大 信息网络与协议信息网络与协议 主要内容主要内容 分组分类分组分类 业务量监管

9、业务量监管 分组调度分组调度 队列管理队列管理 信息网络与协议信息网络与协议 业务量监管业务量监管 业务监管：业务监管：Traffic Policing 对业务进行监视，以避免超过许可的服务质量参数约对业务进行监视，以避免超过许可的服务质量参数约 定（平均速率，峰值速率、突发长度等）定（平均速率，峰值速率、突发长度等） 通过业务监管机制，可以对超过约定通过业务监管机制，可以对超过约定QoS参数业务的流参数业务的流 量进行调节量进行调节 业务监管功能一般由位于网络入口处的边缘路由器上业务监管功能一般由位于网络入口处的边缘路由器上 执行执行 实现机制实现机制 漏桶算法漏桶算法 令牌桶算法令牌桶算法

10、 信息网络与协议信息网络与协议 漏桶算法漏桶算法 漏桶算法：漏桶算法：Leaky Bucket 只要桶中有水，水流出只要桶中有水，水流出 的速率就是常数的速率就是常数 桶中没有水的时候，水桶中没有水的时候，水 流出的速率为流出的速率为0 桶满以后，往里面流的桶满以后，往里面流的 水会溢出水会溢出 信息网络与协议信息网络与协议 漏桶算法漏桶算法 应用于分组传输的漏应用于分组传输的漏 桶算法桶算法 平滑突发业务流平滑突发业务流 不论输入的速率为多大，不论输入的速率为多大， 输出速率始终是常数输出速率始终是常数 信息网络与协议信息网络与协议 漏桶算法漏桶算法 算法过程：考虑数据以分组为单位到达算法过

11、程：考虑数据以分组为单位到达 1）将漏桶看做是一个有限长度的队列，以字节为单位计数，）将漏桶看做是一个有限长度的队列，以字节为单位计数， 当分组到达的时候，如果队列中还有空间的话，就被添加当分组到达的时候，如果队列中还有空间的话，就被添加 到对列的尾部，否则该分组将被丢弃到对列的尾部，否则该分组将被丢弃 2）重复以下的嘀嗒周期）重复以下的嘀嗒周期 a）在嘀嗒周期开始时，将计数器初始化为）在嘀嗒周期开始时，将计数器初始化为n b）若队列中第一分组小于）若队列中第一分组小于n，将该分组发送出去，并且将计数器减去，将该分组发送出去，并且将计数器减去 该分组的字节数，然后对下一个分组执行同样的过程，直

12、到出现计数该分组的字节数，然后对下一个分组执行同样的过程，直到出现计数 器的值小于队列中的分组的长度为止，此时，传输过程终止，直到下器的值小于队列中的分组的长度为止，此时，传输过程终止，直到下 一个嘀嗒再开始一个嘀嗒再开始 信息网络与协议信息网络与协议 令牌桶算法令牌桶算法 令牌桶：令牌桶：Token Bucket 桶中保存的是令牌，每隔桶中保存的是令牌，每隔T秒产生一个秒产生一个 只有当桶中有令牌时才能传输数据只有当桶中有令牌时才能传输数据 允许突发流量允许突发流量 Arriving packets 假设：假设： S:突发长度（突发长度（s） b: 令牌桶容量（令牌桶容量（B） M：最大输出

13、速率（：最大输出速率（Bps） r：令牌到达速率（：令牌到达速率（Bps） b+rS = MS S=b/(M-r) 信息网络与协议信息网络与协议 令牌桶算法令牌桶算法 算法过程：数据以分组为单位到达算法过程：数据以分组为单位到达 1）每个令牌桶维护一个字节计数器，每隔）每个令牌桶维护一个字节计数器，每隔T秒，计数器的值秒，计数器的值 增加增加K字节，这就相当于往桶中放一个令牌，一个令牌代字节，这就相当于往桶中放一个令牌，一个令牌代 表了传输表了传输K字节的权利字节的权利 a）令牌速率为）令牌速率为=K/T（Bps）。）。 b）假设桶的大小为）假设桶的大小为b字节，当计数器的值大于字节，当计数器

14、的值大于b字节时，字节时， 就会发生溢就会发生溢 出，需要注意的是，这里溢出丢弃的是令牌，而不是数据出，需要注意的是，这里溢出丢弃的是令牌，而不是数据 2）当有分组等待发送时，如果计数器的值大于当前分组的）当有分组等待发送时，如果计数器的值大于当前分组的 长度，则发送该分组，并且将计数器的值减去分组长度。长度，则发送该分组，并且将计数器的值减去分组长度。 如果还有分组等待发送，继续执行上面的过程，直到计数如果还有分组等待发送，继续执行上面的过程，直到计数 器的值小于分组长度为止器的值小于分组长度为止 信息网络与协议信息网络与协议 6543210 Arrival time at bucket D

15、eparture time from a leaky bucket Leaky bucket rate = 1 packet / 2 time units6543210 6543210 Departure time from a token bucket Token bucket rate = 1 token / 2 time units Token bucket size = 2 tokens 漏桶和令牌桶漏桶和令牌桶 信息网络与协议信息网络与协议 主要内容主要内容 分组分类分组分类 业务量监管业务量监管 分组调度分组调度 队列管理队列管理 信息网络与协议信息网络与协议 概述概述 分组调度用

16、于缓存区中的多个分组竞争使用同一分组调度用于缓存区中的多个分组竞争使用同一 个输出链路时个输出链路时 使用什么样的策略来选择分组发送？使用什么样的策略来选择分组发送？ 该策略会对性能有什么影响？该策略会对性能有什么影响？ 1990年代的一个热点研究领域年代的一个热点研究领域 共享存储交换占主导共享存储交换占主导 传输链路带宽特别是骨干网链路带宽是稀缺的资源传输链路带宽特别是骨干网链路带宽是稀缺的资源 路由器输出缓存以队列的方式进行组织，调度主要对输出队列进行路由器输出缓存以队列的方式进行组织，调度主要对输出队列进行 调度可以更加有效地利用路由器有限的调度可以更加有效地利用路由器有限的 带宽资源

17、，以尽量满足不同业务的需求带宽资源，以尽量满足不同业务的需求 信息网络与协议信息网络与协议 算法算法 先到先服务先到先服务 优先级调度优先级调度 Round Robin 公平调度公平调度 GPS、FQ、WFQ等等 常用于具有常用于具有QoS 需求的场合需求的场合 信息网络与协议信息网络与协议 先到先服务先到先服务 先到先服务（先到先服务（FCFS：First-Come-First Served） 发送机会到来时，最先到达的分组具有最高的调度优发送机会到来时，最先到达的分组具有最高的调度优 先级先级 缺点：无法实现流区分，所有流的分组都同样对待缺点：无法实现流区分，所有流的分组都同样对待 信息网

18、络与协议信息网络与协议 优先级调度优先级调度 优先级队列（优先级队列（PQ：Priority Queueing） 到达输出队列的流被分成若干个具有不同优先级的队列到达输出队列的流被分成若干个具有不同优先级的队列 当发送机会到来时，选择最高优先级并且非空的队列中的分组来当发送机会到来时，选择最高优先级并且非空的队列中的分组来 发送，对于属于同一个优先级队列的分组，采用发送，对于属于同一个优先级队列的分组，采用FCFS调度机制调度机制 缺点：低优先级队列调度会出现缺点：低优先级队列调度会出现“饥饿饥饿”现象，因为只有高优先现象，因为只有高优先 级队列中无分组发送时，低优先级的分组才有发送机会级队列

19、中无分组发送时，低优先级的分组才有发送机会 高优先级队列：分组高优先级队列：分组1，3，4 低优先级队列：分组低优先级队列：分组2，5 信息网络与协议信息网络与协议 优先级调度优先级调度 当有比当前正在发送分组优先级更高的分当有比当前正在发送分组优先级更高的分 组到达时，如何处理？组到达时，如何处理？ 继续发送低优先级分组，直到发送完成后再处继续发送低优先级分组，直到发送完成后再处 理高优先级分组理高优先级分组 低优先级分组被停止服务，重新放回队列中或低优先级分组被停止服务，重新放回队列中或 者被丢弃，开始发送高优先级分组者被丢弃，开始发送高优先级分组 非抢占式调度非抢占式调度 抢占式调度抢占

20、式调度 信息网络与协议信息网络与协议 Round Robin Round Robin调度调度 到达输出队列的流被分成不同的队列到达输出队列的流被分成不同的队列 当有发送机会到来时，采用轮询的方式选择队列，并且从队列中当有发送机会到来时，采用轮询的方式选择队列，并且从队列中 选择分组发送选择分组发送 缺点：流的分组大小不同，每个流发送的数据量不同，难以保证公平性缺点：流的分组大小不同，每个流发送的数据量不同，难以保证公平性 队列队列1：分组：分组1，2，4 队列队列2：分组：分组3，5 信息网络与协议信息网络与协议 公平调度公平调度 公平（公平（Fairness） 不是指用户分配相同份额的资源，

21、而是指每个用户对不是指用户分配相同份额的资源，而是指每个用户对 资源具有相同的访问权利资源具有相同的访问权利 问题：如果系统没有足够的资源满足所有用户的需问题：如果系统没有足够的资源满足所有用户的需 求，并且某些用户可能比其他用户需要更少的资源。求，并且某些用户可能比其他用户需要更少的资源。 在保证公平的情况下如何分配资源？在保证公平的情况下如何分配资源？ Max-Min公平共享公平共享：首先要满足那些需求小于它们：首先要满足那些需求小于它们 可以得到部分的用户，然后将多余的资源在那些需可以得到部分的用户，然后将多余的资源在那些需 求更大的用户之间平均分配求更大的用户之间平均分配 可以证明，在

22、可以证明，在Round Robin调度算法中，如果每个调度算法中，如果每个 队列中的分组大小都相等，则满足队列中的分组大小都相等，则满足Max-Min公平共享公平共享 信息网络与协议信息网络与协议 Max-Min公平共享公平共享 原理原理 资源按照递增的顺序分配资源按照递增的顺序分配 没有用户获得大于其所需的资源没有用户获得大于其所需的资源 无法满足需求的用户获得相同的资源无法满足需求的用户获得相同的资源 分配过程分配过程 假设假设 系统总资源系统总资源R 用户集合用户集合1，2， n 对应的资源需求对应的资源需求r1，r2，rn，r1r2= maxth then mark or drop t

23、he packet else if minth= avgQ 0) wq：RED对拥塞的反应程度对拥塞的反应程度 过大，不能过滤由于突发导致的短暂拥塞过大，不能过滤由于突发导致的短暂拥塞 过小，对实际队列长度反应过慢，不能有效地检测拥塞过小，对实际队列长度反应过慢，不能有效地检测拥塞 avgQ = (1-wq)mavgQ (if q=0) m=queue_idle_time/typical_transmission_time Wq: 由路由器或者交换机允许的突发业务大小和持续时间决由路由器或者交换机允许的突发业务大小和持续时间决 定定 信息网络与协议信息网络与协议 RED 计算标记（丢弃）概率计

24、算标记（丢弃）概率 方法方法1：Pb = maxp*(avgQ-minth)/(maxth-minth) maxth-minth应该大于一个往返时间内平均队应该大于一个往返时间内平均队 列的增加列的增加 值，以避免由于丢弃过多的分组而导致全局同步值，以避免由于丢弃过多的分组而导致全局同步 一般将一般将maxth设置为设置为minth的的2倍倍 方法方法2：P = Pb/(1-count*Pb) count:上一次丢弃到现在进入队列的分组数量，实现均匀分组间隔上一次丢弃到现在进入队列的分组数量，实现均匀分组间隔 地丢包，避免对突发流的偏见和产生全局同步现象地丢包，避免对突发流的偏见和产生全局同步

25、现象 Average Queue Length 0 1 minthmaxth maxp 信息网络与协议信息网络与协议 在假设平均队列长度为常数的情况下，丢弃概率的选择应该使得分组在假设平均队列长度为常数的情况下，丢弃概率的选择应该使得分组 丢弃间隔尽量均匀丢弃间隔尽量均匀 避免对突发业务流的偏见避免对突发业务流的偏见 避免产生全局同步现象避免产生全局同步现象 X：连续两次分组丢弃之间到达分组数量（包括后一次丢弃分组）：连续两次分组丢弃之间到达分组数量（包括后一次丢弃分组） 1）直接使用）直接使用Pb计算丢弃概率计算丢弃概率 2）在计算丢弃概率时考虑）在计算丢弃概率时考虑count 丢弃间隔丢弃间隔 信息网络与协议信息网络与协议 RED 性能分析性能分析 Time Max Queue Size max_th min_th Forced drop Probabilistic drops No drops Drop probability Average queue length 丢弃概率依赖于拥塞程度，并且均匀间隔丢弃，避免了由于分丢弃概率依赖于拥塞程度，并且均匀间隔丢弃，避免了由于分 组连续丢弃导致的全局同步现象组