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

项目名称： 多级交换结构中的公平调度算法及偏射机制

项目编号： No.61201223

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 电子学与信息系统

项目作者： 闫芳芳

作者单位： 上海交通大学

项目金额： 25万元

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

中文关键词： 交换结构；调度算法；数据中心；虚拟化；分配算法

英文摘要： 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,

英文关键词： Switch fabric；Scheduling algorithm；Data center；Virtualization；Allocation algorithm