4.4 速率流控和最大最小公平

1、14.4 速率控制最大最小公平2014.4.7本节的内容 漏斗式速率控制机制 Max-Min Fairness 路由器上的拥塞控制引言 窗口机制：适用于突发；探测网络能力；AIMD公平竞争网络资源； 不能只依靠用户自觉遵守规则，运营商也应对违约用户的措施 早期基于虚电路的如ATM、帧中继等系统，带宽是预安排的，无需复杂的窗口控制，只需相对平稳的发送速率，或有限突发(令牌桶)的发送能力； 基于漏斗机制的业务整形漏斗式速率控制机制 业务整形（流量整形） 严格实现：每秒发送最高不能超过R个分组 如TDMA，不适合用于突发业务； 宽松实现：允许一定规模的突发 平均速率仍是R个分组/秒，但允许W个分组的

2、突发 漏斗控制机制，保证用户以约定的速率发送，允许用户有限度的超过该发送速率。起源于虚电路业务如ATM、FR。1. Leaky Bucket Algorithm (LB)(a) A leaky bucket with water. (b) a leaky bucket with packets.Cont. 不管输入是否平稳，输出总小于等于某个恒定速度。漏斗空，则无输出。 超出漏斗容量的数据，整个分组被丢弃！ 实现方式： 如果分组大小一致（如ATM cell），则每隔一定时间输出一个分组； 如果分组大小不同，则每隔一定时间输出一定数目的字节，然后暂存或打包发送Leaky Bucket Algor

3、ithm:1986年Turner提出设计时，要根据业务突发，考虑漏桶的容量问题。实际发送速率能大于约定的速度嘛？2. Token Bucket Algorithm (TB)到达数据x令牌以速率r到达+数据进入网络12345带缓存的令牌漏桶(xr)到达数据，速率x令牌以速率r到达+数据进入网络带缓存的令牌漏桶(xr)到达数据，速率x以速率r到达的令牌+数据进入网络Token Bucket Algorithm (TB) 令牌桶最多能够容纳W个令牌 分组必须拿到一个令牌才能进入网络 令牌以每秒 r 的速率进入令牌桶 如果令牌到达时候,令牌桶满,丢弃到达的令牌 如果令牌桶满,用户可以连续发送W个分组的

4、突发进入网络Token Bucket Algorithm (TB) W决定了突发的大小. 小的W导致严格的速率控制 大的W,允许较大突发的发送 r定义了长期平均速率TB例题 设: 令牌桶容量C=250KB，令牌到达速率P=2MB/s，网络传输速率N=25MBps，假设分组到达时令牌桶是满的，突发分组长度Q=1MB时，发送多长时间？ 解： 在令牌耗尽之前，分组能以25MBps的速度传输S秒，随后就只能以2MBps的速度传输 显然C+PS=NS S=C/(N-P)=10.73ms 剩余数据量为Q-SN，以2MB/s的速度发送需要时间为(Q-SN)/2=364ms5 minutes break 2个

5、简单算法LB/TB的相同和不同？ 突发容量计算； 作业 6.6，219页。 Next Max-Min Fairness内容 基于速率的控制机制 Max-Min Fairness公平的定义是什么？没有唯一答案！ 如果每条链接的容量都是单位1，则 最大吞吐量的实现：分配给短会话1单位，长会话0单位；总吞吐量为3单位 一种公平性的概念是给每个用户1/2单位；总吞吐量为2单位 另外一种方法，分配给每个会话相同的资源，给会话2,3,4用户3/4，长会话1/4单位 最大最小公平例： s0,s1,s2共享链路C1 ，每个应得C1的1/3 s0,s3共享链路C2，每个应得C2的1/2 由于链路C1的限制，连接

6、s0只能得C2的1/3，因此s3应该得到C2的2/3C1=1S0S0C2=1S2S2S1S1S3S3R通俗来说，竞争瓶颈链路时，平均分配资源到每个Session基本思想：劫富济贫 最大最小公平的基本思想：尽可能给某个用户分配速率，但是不能从速率比这个用户低的其他用户身上剥夺速率来分配给这个用户 因此，为了增加某个用户的速率，只能降低另外一个速率比它高的用户的速率瓶颈链路 和 最大最小公平 给定一个速率分配矢量R，链路a是会话p的，当且仅当: 经过链路a的所有会话总和撑满链路a的容量 对于经过链路a的其他会话p，有RP RP ，否则应该劫富济贫 推论：一个速率分配矢量R是最大最小公平的,当且仅当

7、每一个会话都有一个瓶颈链路扩展应用 加权最大最小速率分配WPMM (Weighted Proportional Max-Min) 建立多个连接的用户，能够获得总传输速率就大Max-min fair举例S1R1S2S3R2R31061581255584643355最大最小公平（MMF）算法 初始化:所有会话速率设为0 每一个会话的速率都增加一个很小的量 持续不断的增加,直到经过某条链路的流量等于链路的容量 共享那条链路的会话具有相同的速率；这条链路是这些会话的瓶颈链路 以后,不能再增加这些会话的速率,它们已经达到MMF 连续增加没有经过那条链路的会话的速率 直到另外一条链路成为瓶颈 如果所有的会

8、话都有一个瓶颈链路,算法停止处理机共享调度GPS Generalized Processor Sharing 假定处理机基于流来调度多个sessions，且服务每个session的权重可有不同。 如果基于流会怎样？GPS思想如此简单！ 循环处理所有sessiones/会话 如果每个会话总有分组发送，则他们每个都能得到相同的链路份额（等权重的），或对应权重的比例份额； 如果某些会话空闲，则其余会话按权重分享链路容量 GPS是一种基于分组的最大最小公平近似，分组从每个会话处以循环顺序被处理Cont. 由于数据传输实际上以分组为单位，GPS的分组近似实现算法是PGPS(Packet-by-Packe

9、t GPS)，即WFQ（通常相同）。 根据分组p在GPS中服务的结束时间tp，PGPS按照tp的顺序依次传输分组。E1D1C1B1A1P1P2P3P4P6A2Flow 1(0.5)Flow 2(0.1)Flow 3(0.1)Flow 4(0.1)Flow 5(0.1)Flow 6(0.1)分组到达时间0123456789 10A分组到达顺序P1P2P3P4P5P6分组离开时间0123456789 10B GPS服务顺序E1D1C1B1A1P1P2P3P4P5P6A2分组离开时间0123456789 10C WFQ服务顺序E1D1C1B1A1P1P2P3P4P5P6A2分组离开时间0123456

10、789 10WF2Q服务顺序GPS、WFQ和WF2Q分组输出的时间E1D1C1B1A15 minutes break Questions Before We Proceed?Router对拥塞的处理机制 传统上，拥塞控制主要由end-systems负责（TCP）；路由器很少起作用。 但是，Router的机制影响拥塞控制效果 缓存调度策略 缓存管理策略 老的路由器：简单 FIFO Tail DropFIFO with DropTail的问题 DropTail容易造成“TCP全局同步问题” 突发的或多个连续的分组被丢弃，不利于TCP快速恢复，易导致慢启动； 此外 FIFO不区分优先级； 公平性差；

11、UDP抢占资源FIFO Router with Two TCP SessionsRED FIFO scheduling Buffer management: Probabilistically discard packets 丢弃概率是平均队长的函数Discard ProbabilityAverageQueue Length01min_th max_th queue_lenRED (contd) min_th： minimum threshold max_th：maximum threshold avg_len：平均队长 （滑动平均） avg_len = (1-w)*avg_len + w*s

12、ample_len Discard ProbabilityAverageQueue Length01min_th max_thqueue_lenW:滑动平均系数RED (contd) If (avg_len max_th) 全部丢弃 If (avg_len = min_th and avg_len max_th) 依概率 P丢弃Discard Probability (P)AverageQueue Length01min_th max_thqueue_lenRED (contd)P = max_P*(avg_len min_th)/(max_th min_th)Improvements to

13、spread the dropsP = P/(1 count*P), where count how many packets were consecutively enqueued since last dropDiscard ProbabilityAverageQueue Length01min_thmax_th queue_lenavg_lenPmax_PRED Advantages 避免全局TCP同步问题 给end systems更早的提示，尽早降速，而不是重启（慢启动）RED Router with Two TCP SessionsRED没有解决的问题 一个坏流会伤害其他好流 如：1 UDP (10 Mbps) and 31 TCPs sharing a 10 Mbps linkRED0123456789101471013161922252831Flow NumberThroughput(Mbps)UDP用其他的Solutions Round-robin among di