多级交换结构中的公平调度算法及偏射机制

To keep pace with the exponential growth of Internet traffic, there is an urgent requirement for the high capacity cluster routers with scalability.The three-stage Clos switch fabric can be adopted in the cluster routers to support a large number of ports. Scheduling algorithm is essential for congestion resolution, including port and path conflicts, in the Clos switch fabric. The quasi-static path switching, based on Birkhoff-von Neumann (BvN) decomposition, can guarantee the capacity from any input module to output module in Clos switch fabric. Path switching is inadequate because: (1) The BvN decomposition results in poor delay jitter performance especially when there are a large number of ports in the switch; (2) it does not address either the burst traffic or deviation of traffic matrix from prediction. Delay jitter seriously affected the quality of services that the voice and video users experience. In this project, we propose fair scheduling algorithm in order to minimize delay jitter of the regulated packet flows. The proposed fair algorithm is motivated by source coding and expected to have the time complexity of O(logK), where K is the number of matching patterns. We will attempt to derive the delay jitter bound for the fair scheduling algorithm. Secondly, as a complement to fair scheduling algorithm, we propose deflection mechanism in order to reduce packet loss probability. We will derive an analytical model to compute loss probability as a function of burstiness and buffer size. Deflection mechanism has the time complexity of O(1) and does not consume extra bandwidth.? With these efforts, we expect that this project will impact the development of QoS provisioning in Clos switch fabric.

互联网流量正在呈指数级增长，迫切需要研发大容量、可扩展的集群路由器。集群路由器的核心交换矩阵普遍采用三级Clos交换结构。准静态调度既为Clos交换结构提供了严格带宽保证，又能避免复杂的在线计算，但仍存在以下不足：端口数增大时延时抖动非常严重；在突发业务环境或业务矩阵与预测有偏差时，丢包较严重。本项目首先以最小化输入分组流的延时抖动为目标，研究匹配模式的公平调度算法，并分析其延时抖动上界。我们提出将信源编码观念用于设计公平调度算法，计算时间复杂度为O(logK)，其中K为匹配模式数。其次，作为公平调度算法的补充，我们研究偏射机制以降低突发业务的丢包率；拟建立数学模型分析偏射机制的丢包率、延时性能和稳定性。偏射机制既不占用额外的带宽，也不涉及任何最大匹配算法，时间复杂度与端口数无关为O(1)，兼具灵活性和可行性。本项目所提调度算法有助于提高Clos交换结构的服务质量，具有很好的应用潜力。

准静态Birkhoff-von Neumann（BvN）调度算法为交换结构提供严格带宽保证，且能避免复杂的在线计算，但在突发业务环境或业务矩阵与预测有偏差时服务质量严重劣化。本项目提出最大权匹配和BvN竞争混合调度算法，其时间复杂度为O(N)，其中N为端口数，比最大权匹配低两个数量级。利用二阶Lyapunov函数理论证明混合调度是稳定的。仿真证明对于非对称突发流量，竞争调度的性能非常接近时隙最大权匹配算法：延时与抖动的差距随负载增高而减小，丢包率无差异；而相对BvN算法有显著改善：平均延时降低约65%～93%，而延时抖动降低58%～98%，高负载（例如0.95）丢包率从10%降低至0。所提调度算法不会带来分组乱序，利于应用于数据中心超低延迟环境中。. 本项目还提出基于流量预测的动态BvN重构调度算法。在流量预测方面，证明局部高斯预测相比静态/动态指数加权移动平均预测可以提供更有保障的带宽。分别提出复杂度和精准度不同的三种系数重构算法：系数降序重构法、最大权匹配重构法、二次规划法等。与准静态BvN相比，动态BvN重构在高负载情况下能将吞吐量提升9%，将延时降低30%~40%。. 在数据中心网络应用方面，基于软管抽象的虚拟数据中心（VDC）分配问题，已有研究局限于树形拓扑。本项目研究一般拓扑中的VDC分配（属于NP完全）问题,分别针对均匀和非均匀带宽请求提出多项式复杂度的启发式算法，称为K最短路微扰和拥塞规避算法，其利用线性规划求解符合物理网络带宽约束的最优路由分配问题，并提出K-最短路径负载均衡路由算法以控制多路径延迟差异；通过选择性的卸载瓶颈服务器中虚拟机来消除网络拥塞。仿真证实微扰启发算法的性能（成功率、拥塞度、带宽成本、收益／成本比等）与指数时间的穷举搜索算法非常接近，相对单路径算法有大幅改善。研究成果受到审稿人的好评“完整的阐述了多路径数据网络中的虚拟数据中心的有带宽保证的路由问题，而多路径路由更符合现实场景中的数据中心网络，提出的启发算法在复杂度和性能之间取得良好平衡”。. 针对数据中心能源消耗问题，提出功率感知的虚拟数据中心分配算法。在树形网络拓扑结构中，得到虚拟数据中心的最小化功耗分配方式；并通过业务接入策略减少功率波动；针对动态业务流产生的资源碎片，提出通过虚拟机迁移的进行碎片整理，提高服务器和链路的利用率。