片上網路的高效擁塞感知及協同擁塞控制方法研究

《片上網路的高效擁塞感知及協同擁塞控制方法研究》是依託北京交通大學，由趙宏智擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：片上網路的高效擁塞感知及協同擁塞控制方法研究
• 項目類別：青年科學基金項目
• 項目負責人：趙宏智
• 依託單位：北京交通大學

項目摘要

網路擁塞是片上網路設計需要解決的一個關鍵問題。對網路擁塞進行控制的方法主要有兩類：適應性路由算法與限流方法。已有的適應性路由算法所採用的擁塞感知策略效率較低，難以兼顧擁塞信息的高清晰度、全局性與可擴展性，能夠成功避讓路由器熱點的機率較小，使得端到端延時較大；已有的限流方法在擁塞感知時同樣難以兼顧擁塞信息的高清晰度、全局性與可擴展性，使得精確的限流比例難以被設定，出現因限流不足或限流過度導致的系統性能下降問題。. 本課題擬利用片上網路中流(flow)傳輸範圍固定且可見等特徵，研究片上網路的高效擁塞感知策略；在此基礎上，分析路由器熱點位置對適應性路由算法和限流方法性能影響的規律，研究更高性能的適應性路由算法和限流方法；此外，針對這兩類擁塞控制方法間未能有效協同的問題，將量化其各自適用的網路場景，研究其協同擁塞控制策略，在保持高吞吐量的情況下有效降低端到端延時，提升系統性能。

結題摘要

隨著片上網路中節點數目的不斷增加，錯誤節點或擁塞節點等特殊節點在片上網路中出現的可能性也在不斷地增加。如何高效感知這些特殊節點，以及標記出網路中的這些特殊節點及其之間的位置分布關係成為了片上網路設計中的重要問題。如果有一種能夠高效解決該問題的方法，那么可以套用於片上網路的多種套用場景中，比如容錯、擁塞控制、可靠性等。重要的研究內容及其結果有： 1，針對高效擁塞感知問題，提出了RSD(Rectangle defined by Source node and Destination node )的概念。對相互進行通信的源節點和目標節點來說，在採用曼哈頓路徑的前提下，其在進行擁塞感知時，只需感知RSD範圍內的擁塞節點即可，從而大幅度降低了感知的開銷以及延時，提升了感知的效率。 2，在RSD概念的基礎上，提出了一種路徑計數理論，能夠高效地標記出網路中的所有特殊節點及其之間的位置分布關係，其標註的複雜度與網路規模成線性關係。 3，針對容錯路由問題，提出了基於路徑計數方法的部分適應性的容錯路由方法, 其可以避讓開大部分的網路擁塞節點。理論分析和網路仿真的結果表明，套用本方法，可以將已有的部分適應性容錯路由方法的性能從O(n^2)降低為O(n),n為網路規模。此外，本方法還支持任意分布和任意數目的錯誤節點，支持路徑的存在性判斷功能等。 4，針對網路擁塞場景，提出了一種基於路徑計數的精確限流算法：已有的源限流方法要么將網路當做黑盒處理，難以精確確定網路擁塞位置；要么只能根據經驗值來設定限流係數，導致網路限流的效果並不是很理想。本課題提出的基於路徑計數的精確限流方法，可以精確量化限流對象，並精確計算限流係數，與以往的經驗方式確定限流係數的限流方法相比，可以大幅度提升網路吞吐量，降低網路延時，比如在在隨機模式下精確限流算法的平均延時比Self-tuned、INC算法、不限流算法分別好23.3%、34.6%、46.6%； 5，針對QoS可靠性場景，提出了一種基於路徑計數的分離路徑計算方法。在mesh拓撲結構下，與已有的分離路徑方法相比，在同樣能夠找到分離路徑的情況下，本方法可以將算法複雜度從O(n^2)降低為O(n),n為網路規模。 研究過程中產生的一些成果還套用到了其它一些領域如捷運網路的調度等的問題解決中。總的說來，本課題的研究取得了較多的重要成果，具有較好的學術價值。