《多級交換結構中的公平調度算法及偏射機制》是依託上海交通大學，由閆芳芳擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：多級交換結構中的公平調度算法及偏射機制
- 項目類別：青年科學基金項目
- 項目負責人：閆芳芳
- 依託單位：上海交通大學
項目摘要,結題摘要,
項目摘要
網際網路流量正在呈指數級增長，迫切需要研發大容量、可擴展的集群路由器。集群路由器的核心交換矩陣普遍採用三級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-最短路徑負載均衡路由算法以控制多路徑延遲差異；通過選擇性的卸載瓶頸伺服器中虛擬機來消除網路擁塞。仿真證實微擾啟發算法的性能（成功率、擁塞度、頻寬成本、收益／成本比等）與指數時間的窮舉搜尋算法非常接近，相對單路徑算法有大幅改善。研究成果受到審稿人的好評“完整的闡述了多路徑數據網路中的虛擬數據中心的有頻寬保證的路由問題，而多路徑路由更符合現實場景中的數據中心網路，提出的啟發算法在複雜度和性能之間取得良好平衡”。針對數據中心能源消耗問題，提出功率感知的虛擬數據中心分配算法。在樹形網路拓撲結構中，得到虛擬數據中心的最小化功耗分配方式；並通過業務接入策略減少功率波動；針對動態業務流產生的資源碎片，提出通過虛擬機遷移的進行碎片整理，提高伺服器和鏈路的利用率。
