五、交换式网络实时通信的保证机制和服务策略

1、五、交换式网络实时通信的保证机制和服务策略PART 021提纲实时流量模型real-time traffic model实时通信服务规程的概念调度器的参考模型服务规程（service discipline）的分类确定性数据包调度的服务规程WFQ及其扩展J-EDD和D-EDDWRR及其扩展* IntServ 与 DiffServ概念，在网络演算中详细分析PART 22五、交换式网络实时通信的保证机制和服务策略实时流量模型实时通信服务规程的概念确定性数据包调度的服务规程WFQ及其扩展D-EDD 和 J-EDDWRR及其扩展*IntServ 与 DiffServ20133最早预定期限优先EDDEar

2、lier Due Date对于每条通信任务进行细致调度的服务规程维护当前输出链路的状态信息现有连接的总密度现有连接的总缓冲空间 BS连接的准入控制、连接的建立与撤除消息流i ，周期性消息模式( pi , 1, Di )；从 源 到 目的 节点准许连接建立，确认消息中包含的调度信息由目的节点选择的本地相对截止期限Di,k ，以及缓冲空间值 bsi,k连接建立后，对于数据包的派发用数据包的预定期限作标记，每条连接FIFO，整体EDD11.2.4在每个交换节点上，按Due安排发送次序4最早预定期限优先连接的建立准入控制请求建立连接 i 的Req消息中，参数( pi , 1, Di ) ，峰值速度每p

3、i 一个数据包；相对截止期限Di 路径上每个交换节点都要确定是否接受这个连接，如果接受的话，能保证的最大延迟、提供给连接i的本地相对截止期限，预留链路带宽与缓冲区空间将本地相对截止期限放入Req消息，传送给下游节点5EDD收到Req消息其中，pmin是现有连接的最小周期值6EDD目的节点的确认消息检查申请途中的LDi的总和是否大于端到端DiIf LDi Direject 拒绝，发送 Ack_r 消息，到上游各节点otherwiseaccept接受，发送Ack_aDi,k , bi,k 消息到上游各节点对于新建立的连接i，在节点k上，Di,k LDi ，确定各节点的本地相对截止期限7EDD连接申

4、请后路径上的处理如果路径上的节点收到Ack_aDi,k , bi,k消息总密度：:= -1/ LDi+1/min(Di,k , pi) /为原LDi将连接 i 在本地的截止期限设为：LDi := Di,k缓冲空间：BS:=BS-Bi+bi,k更新pmin ： pmin :=min(pi , pmin)如果路径上的节点收到Ack_r消息释放预留的资源:= -1/ LDiBS:=BS-Bi8EDD速率控制 和 每个节点的EDF端到端Deadline，拆分到每个节点，Due（预定期限，“交货期限”）每个交换节点上，EDF由于EDF算法本身不能在其它连接超载的时候，对给定连接提供定时保护，所以定时保护

5、需要速率控制速率控制有效到达时间aei,j ，例如，连接i上第j个数据包aei,j =max(aei,j-1 +pi , ai,j)在交换节点k上，第j个数据包的本地绝对截止期限为： di,j = aei,j + Di,k9EDD速率控制 和 每个节点的EDF（续）每个节点上的延迟由于速率控制，连接上每两个连续的数据包的传输时限间隔不小于个时间单位pi相当于：偶发服务器(pi ,1)周期任务pi连接不会以超载（超过声明峰速的突发）相互影响，每个数据包的延迟也不会超过Di,k为什么？因为交换保留了“足够的”输出链路带宽1/pmin根据不可抢占EDF调度，根据Liu 2003p138 ，存在阻塞时

6、间bi=1，这里EDD，用于类似ATM的定长的数据包传输10EDD速率控制 和 每个节点的EDF（续）为什么?!如果按照时间需求法，分析的“最坏情况”并非如此 （设：按周期从小到大排序，p1p2Di,k12EDDD-EDD和J-EDD每个节点带有速率控制D-EDD，保证端到端延迟Best-CasekWorst-CaseJ-EDD，控制速率的前提下，控制抖动Non-greedy提前时间（ahead time） ahi,j由第k-1个交换节点感知，由数据包的头部携带，到k 对于第j个数据包，ahi,j=Di,k-1-D实际,i,k-1 在k节点，释放（就绪）时间ri,j = max(aei,j ,

7、 ai,j +ahi,j)13EDDD-EDD和J-EDD控制速率的前提下，控制抖动（续）本地的绝对截止期限 di,j =ai,j+Di,k实际上，只需要在第一级交换上控制速率，下游交换节点只用控制抖动第一级交换aei,j下游交换节点 ai,j +ahi,j在下游每个节点都会保留第一级交换的释放（就绪）模式优点：下游交换不需要维护状态信息aei,j端到端的抖动：小于最后一级连接上的本地相对时限。（?! 相对应用任务的到达，源端速率控制会造成抖动）14EDDD-EDD和J-EDD例如：消息流(5,1)，各节点本地相对截止期限D=4第一级交换到达0、5、10、16、2110051621S16051

8、924S2123454ttD-EDD2ae1ae2ae3ae4ae59123184514ae1ae2ae3ae4ae58024S24tJ-EDD1218454+03+1延迟设为4,3,1,2,33111+32+23+19142025延迟设为4,3,1,2,3r1r2r3r4r5图例：有效达到时间=15EDDD-EDD和J-EDD例如：消息流(5,1)，各节点本地相对截止期限D=4第一级交换到达0、5、10、16、2110051621S112345t2ae1ae2ae3ae4ae58024S24tJ-EDD1218454+03+13111+32+23+19142025延迟设为4,3,1,2,3r

9、1r2r3r4r516EDD调度算法复杂度 与 缓存深度调度复杂度选择最早截止期限的排序算法O(logn)缓存深度D-EDD约J-EDD在k1的交换节点上，Di,k-117EDDEDD和其它调度方法的关系多处理器调度MPMModified Phase Modification 修正的相位调整RG Release Guide 释放守卫条件多处理器和分布式系统的整体调度holistic18五、交换式网络实时通信的保证机制和服务策略实时流量模型实时通信服务规程的概念确定性数据包调度的服务规程WFQ及其扩展D-EDD 和 J-EDDWRR及其扩展IntServ 与 DiffServ201319WRR及

10、其扩展Weighted Round-Robin适应于以流水线的形式通过交换不需要全局时钟（除同步S&G），不需要排序队列类型贪心WRR S&G（同步 /异步），非贪心HRR（层次化RR）BWRR（Budgeted Weighted Round-Robin），非贪心主要应用：CBR（常量比特率） (pi, ei, Di)消息由若干数据包构成，每个数据包传输时间为单位111.320WRR贪心WRR工作原理每个连接连接i，wi个时隙（slot）轮（Round）轮长RL吞吐量每一轮，连接i确保有wi个时隙（数据包）wi /RL21WRR贪心WRR延迟设定：RLntri ， bgi :=wi /补充预算

11、 IF srt(i) nrt(i) / 曾经设置下下次补充时间nrt(i) := srt(i) ELSEpgi := FALSE/ “悬而未决”的都已解决 END IFEND IF31WRRBWRR算法tt123123a1a2a3tbgiS1S2wi0t1t2t3tpgiFALSETRUEa1rt1rt2rt3rt1rt2a3rt3RLRLRLa2nrtisrtinrtit432WRRBWRR算法端到端延迟考虑消息Mi中一个数据包的延迟，每个路段的延迟上限为RL与贪心WRR相同所以，消息Mi的延迟可以用贪心WRR推导出的公式：端到端抖动Best-Case ：第一级交换 下游交换 K-1 （设共

12、有K级）考虑WC和BC的差值33交换网络调度算法的性能比较Liu 2003pp429调度复杂度ete延迟上界ete抖动上界缓冲空间需求WFQO(n)E/u+K(e+1)const.Kconst.KD-EDDO(log n)Dconst.Kconst.KJ-EDDO(log n)Dconst.const.贪WRRO(1)pi+(K-1)RL同步S&GO(1)pi+KRL2RL2wiBWRRO(1)pi+(K-1)RL(K-1)RL-wi+12wi34五、交换式网络实时通信的保证机制和服务策略实时流量模型实时通信服务规程的概念确定性数据包调度的服务规程WFQ及其扩展D-EDD 和 J-EDDWRR

13、及其扩展*IntServ 与 DiffServ201335IntServIETF综合服务QoS保证的规范说明（RFC 2212）资源预留协议 （RFC 2205）参考Bettati 200936IntServRFC 2212主要内容服务的“流体模型”（fluid model）流量规范（TSPEC）期望的服务规范 （RSPEC，desired serv. spec.）定义一些服务模块子网、交换机、trunk管制 与 重整形 （policing & reshaping） 37IntServRFC 2212说明服务质量保证（guaranteed QoS）是独立于连接建立协议或流识别机制的。包括RSV

14、PResource reservation protocol）手工配置SNMP然而，如果路径上每个服务元素支持相应服务，则QoS得以保证。保证：端到端延迟队列不溢出（overflow），但是IntServ不一定保证Jitter保证服务作为网络延迟控制的一种扩展形式。38IntServRFC 2212流体模型定义：“Fluid model”，服务率R“专线”，源端到接收端的专用的带宽；流（flow）的服务完全独立于其它任何流。算法和实现WFQJ-EDDVirtual Clock通用定义39IntServRFC 2212流体模型下的延迟分析考虑到：流由令牌桶（即：漏桶）(r,b)约束，如果通过一条

15、物理连线，带宽为R；只要Rr，延迟界限为b/R。但是，问题是：速率为R的保证服务（guaranteed service）如何逼近带宽为R物理连线的行为网络元件必须确保本地数据包延迟小于b/R+C/R+DC：与速率有关的误差项例如：ATM信元，发送频率1/rD：与速率有关的误差项（与间隔有关）例如：必须等待时隙40IntServ流量规范TSPECTSPEC为 令牌桶 + 峰值速率 + 最小管制单位 + 最大数据报长度(b,r)深度b，补充速率rp注入网络的最大突发速率m最小管制单位，所有的小于m的数据报的长度，都认为是mM最大数据报长度，注：该值不应大于链路的MTU。41IntServ期望的服务

16、规范（RSPEC）R：速率R必须不小于rS：空闲时间项（slack term）期望的延迟与使用预留带宽R达到的延迟的差值；有的网络元件可能参考这个值，减少资源预留。42IntServ管制与重整形管制（policing）在网络的边缘如果流量超过TSPEC，管制器确保b(I)M+min(pI，rI+b-M)没有提供管制的数据报按照“best-effort”质量服务（QoS保证被放弃）重整形（re-shaping）在网络内部对于不符合的数据报，缓存（延迟），直到满足TSPEC后再发送缓存需求：b+Csum+(Dsumr)，其中C,D为误差项。43IntServ资源预留协议RSVPResource R

17、eSerVation ProtocolRFC 2205Internet的控制协议，本身并不是路由协议支持 单播 和 多到多的多播 应用，但是它为单向的数据流协商预留资源维护“Soft”状态预留的建立准入控制+管制控制44IntServ资源预留协议预留模型预留请求：flow-descriptor = flow-spec + filter-spec流规范规定QoSRSPECTSPEC过滤规范定义接受QoS服务的数据包的集合（即：流）一般会话中的仲裁子集现在根据发送的IP地址和源端口号存在一些问题：分段？IPv6？ 加密的IP45IntServ资源预留协议预留请求One-passOne-Pass-W

18、ith-Advertising (OPWA)预留请求带有一些选项，作为预留的“style”46IntServ资源预留协议协议机制基本的两个信令消息：RESV 和 PATHPATH发送主机从多播或单播路径，发送PATH，包含当前跳得地址发送末拌报文的格式发送的TSPECOPWA的ADSPEC给本地的准入控制机构在数据段，“源目的”地址为了穿过中间“非RSVP”的部分RESV从接收主机到发送主机在每个节点创建并保持“预留状态”。软状态RSVP在路由器和主机上维护“软状态”，它由PATH和RESV创建，并被周期地刷新。47IntServ资源预留协议例子48DiffServ区分服务 Different

19、iated Serv.目的与理念服务类同样服务类的流量成为“聚合流”（aggregate flow）网络边界“micro-flow”遵守相应到达约束LeBoudec 2004 pp8749DiffServ区分服务 Differentiated Serv.对一些逐跳行为（PHB，per-hop behavior）进行标准化“DS field” RFC 2474 and RFC 2475 define the architecture, and the general use of bits within the DS field加速转发EF 和 保证转发AFExpedited Forwardin

20、g RFC 2598 An Expedited Forwarding PHB，1999.6Assured Forwarding RFC 259750DiffServ区分服务 Differentiated Serv.例如：加速转发的PHB提供给聚合流的速率大于它的可持续速率，EF PHB曾经被重新定义Bennett 2011 在这样的定义下，端到端延迟上界如果其中：h 跳数，k所需寻找的整数，M最大长度51参考文献Liu 2003 Liu Jane W S 著, 姬孟洛 等译. 实时系统 M. 北京: 高等教育出版社, 2003.12.Aras 1994 Aras Gaglan M, Kurose James F, Reeves Douglas S, Schulzrinne Henning. Real-Time Communication in Packet-