一種用於緩衝Crossbar的隊列長度均衡調度方法

2023-04-27 10:01:41 1

專利名稱：：一種用於緩衝Crossbar的隊列長度均衡調度方法
技術領域：
：本發明涉及一種用於緩衝Crossbar的隊列長度均衡調度方法，它以緩衝Crossbar交換結構為背景，在輸入/輸出端調度時充分利用了輸入隊列和交叉點緩衝長度信息，從而使輸入端最長的隊列在輸入端和輸出端均能優先調度，使得整個隊列系統保持均衡與穩定，從而獲得更優的性能，本發明主要適用於高速路由器/交換機。
背景技術：
當前Internet的規模和業務量增長迅速，作為網絡核心節點的路由器/交換機逐漸成為限制網絡速率和容量的瓶頸。高性能的交換結構是路由器的核心部件，其性能卻要受到調度算法的制約。調度算法主要是解決數據輸入/輸出競爭，避免發送衝突，達到合理利用交換結構資源，提高吞吐量和減少時延的目的。可以說，交換結構及其調度算法的優劣直接影響整個路由器的埠速率、容量和時延等性能。傳統的中、低速路由器大多採用輸出排隊的交換網絡(包括共享緩存)，它們雖然具有良好的吞吐量和時延性能，但是要求交換結構的速率是鏈路速率的N(N指輸入埠數目)倍，而在網際網路幹線中鏈路速率往往很高(如0C-192、10GE)，交換網絡難以達到數十Gbps的速率，造成系統可擴展性差，已無法滿足Internet日益發展的需求。基於輸入排隊的Crossbar是一種快速的定長交換網絡，只要求交換網絡的速率與鏈路速率相同，並且Crossbar具有簡單易實現、無阻塞等優點，被廣泛應用於高速路由器/交換機的設計中。在這種交換結構中，分組只在輸入端存儲，經過調度通過crossbar輸出。輸入隊列為了避免由於HOL阻塞(headoflineblocking)而帶來的交換網絡吞吐量下降的問題，一般採用虛擬輸出排隊技術(VOQ:virtualoutputqueueing)來消除HOL阻塞，即每個輸入端為每一個輸出端維護一個單獨的FIFO(firstinfirstout)隊列，我們統稱之為V0Q隊列。然而Crossbar需要集中控制，當埠數目增加時，調度算法可擴展性仍然受到很大地限制。為解決可擴展性問題，近年來，緩衝Crossbar交換結構因其良好的分布並行調度特性，逐漸成為交換領域的研究熱點。所謂緩衝Crossbar,就是在Crossbar的交叉點植入少量緩衝，這樣能夠將輸入端與輸出端的數據傳輸競爭隔離開來，調度算法可以在輸入/輸出端獨立並行工作，不需要集中控制。依據目前的技術條件，交叉點緩存容量比較小，仍然需要與輸入排隊結合使用，輸入隊列仍然採用VOQ排隊技術。與純Crossbar的高速交換結構相比，緩衝Crossbar交換結構具有分布式調度、易擴展的良好特性，是高速、大容量路由器的理想選擇。為了實現高速交換和控制上的方便，緩衝Crossbar處理的數據單元為固定長度的信元，一個信元通常取64位元組長度，傳輸一個信元的時間間隔稱為一個時隙。緩衝Crossbar交換結構中輸入端調度算法負責調度本輸入端V0Q隊列中的信元，保證在一個時隙內每個輸入端至多發送一個信元，被調度的信元被發送到對應的交叉點緩衝中；輸出端調度算法負責調度交叉點緩衝中的信元，保證在一個時隙內每個輸出端至多發送一個信元，被調度的信元被發送到輸出鏈路上。近年來，在緩衝Crossbar交換結構的調度問題上取得了許多有價值的研究成果，提出了不少算法，這些算法共同的設計指標是1)高吞吐率和低時延；2)交叉點小緩存；3)低複雜度。輸入和輸出端都採用輪轉(RR:Round-Robin)策略的RR-RR算法的實現複雜度僅低，但在非均勻流量下不能提供良好的吞吐率、時延和穩定性。仿真結果表明，輸入端採用最長隊列優先策略的LQF-RR(LongestQueueFirstRound-Robin)算法在非均勻流量下的性能明顯好於RR-RR。有的研究者從交叉點緩存的狀態出發考慮調度算法的設計，以降低實現的複雜度，如MCBF(MostCriticalBufferFirst)，但是該算法沒有考慮輸入端VOQ的狀態，當到達信元分布不均勻時，負載高的輸入隊列會出現不穩定現象，從而限制了最大吞吐率。仿真結果表明MCBF的穩定性比LQF-RR要差。還有的算法如RR-AF(Round-RobinwithAdaptable-Size)、FD-RR(FullDrainingRound-Robin)、QD-RR(Quantum-basedRound-Robin)和DRR(DifferentialRoundRobin)，在RR-RR的基礎上對輪轉指針的更新策略(滯留規則)稍加改動，既保留RR-RR低複雜度的優勢，又提高了吞吐率和時延性能，它們的基本思想都是通過為每個VOQ隊列分配固定的調度份額來約束輪轉指針的更新，然而其中的"差分因子"或者"份額"的取值都是仿真得到的經驗值，在複雜的網絡流量下無法得到可靠性驗證。在上述算法中，LQF-RR具有最好的吞吐率和時延性能，在任何可接受流量下都能保持系統的穩定。原因是輸入端調度充分利用了VOQ隊列的長度信息，給較長的隊列更多的被服務機會，使各VOQ的隊列長度達到均衡，從而保證了非均勻流量下輸入端的穩定。然而對於輸出端調度而言，簡單的RR策略僅考慮了交叉點中的信元狀態，而沒有考慮到相應VOQ隊列的狀態，相對於輸入端積壓信元較多的隊列，也無法得到及時的服務，從一定程度上削弱了輸入端隊列均衡的效果。
發明內容為了解決這個問題，本發明提供一種基於隊列長度均衡的調度算法MUIQF(MostUrgentInputQueueFirst)，目的是使輸入端最長的隊列在輸入端和輸出端均能優先調度，使得整個隊列系統保持均衡、穩定，從而獲得更優的性能。通過仿真研究，該算法在各種流量模型下能夠達到比LQF-RR算法更優的吞吐率、時延性能和穩定性。MUIQF算法的基本思想是將輸入和輸出調度的出發點統一到"使輸入端VOQ隊列長度均衡"上來。輸入端調度器與LQF-RR的輸入端調度器執行過程完全相同，即選擇一個輸入端中隊長最長的V0Q優先調度；輸出端調度時，一個輸出端對應的所有交叉點並非擁有相同的優先級，而是優先調度自身隊列長度與對應的VOQ長度之和最大的交叉點。算法每個時隙調度一次，調度結果配置Crossbar,並進行相關信元傳輸。本發明解決其技術問題所採用的技術方案是(1)分組分段和重組不同長度的IP分組在調度前劃分成固定長度的"信元"，在輸出端重組後再發送到鏈路上去。(2)信元排隊信元到達過程是一個離散時間隨機過程，每個輸入端每個時隙至多到達一個信元。輸入隊列採用V0Q排隊技術，若輸入端i到達一個目的端為j的信元，那麼該信元被放入V0Qij隊列中；若V0Qij隊列被調度，隊頭信元將被存入交叉點緩衝CBij中。V0Qij在t時隙的隊列長度表示為L(V0Qij,t);CBij在t時隙的隊列長度表示為L(CBij,t);其中1《i，j《N。(3)符號與定義一個交叉點緩存的最大容量用C表示；t時隙時，若L(VOQij,t)>0且L(CBij,t)0，稱CBi，.為ECB(EligibleCrosspointBuffer);其中1《i，j《N。(4)MUIQF調度算法在MUIQF算法中，每個輸入/輸出端都有一個調度器，各設有1個優先指針，指向當前最高優先服務的隊列。每次執行過程開始時所有輸入/輸出端為空閒狀態。MUIQF輸入/輸出端調度器獨立執行輸入端調度輸入端i的調度器指針《i《N)，指向當前優先選擇服務的V0Q。從指針Ii所指的隊列開始，按照輪轉規則，尋找第一個L(VOQij,t)(1《j《N)最大的EVOQ，假定找到為V0Qiq(l《q《N)，把它的隊頭信元傳送到CB^，指針^更新至(q+l)(模N)。如果找不到，指針保持不變。輸出端調度輸出端j的調度器指針0j(1《j《N)，指向當前優先選擇服務的CB。從優先指針Oj所指的隊列開始，按照輪轉規則，尋找第一個L(VOQij,t)+L(CBij,t)(1《i《N)最大的ECB，假定找到為CBpj(l《p《N)，就把它的隊頭信元傳送到輸出端j，指針Oj更新至(P+1)(模N)。如果找不到，指針保持不變。下面結合附圖和實施例對本發明進一步說明。圖1是緩衝Crossbar交換結構的組成圖；圖2是輸入端排隊方法示意圖；圖3是本發明方法一實施例的執行過程。具體實施方式參考圖l，緩衝Crossbar交換結構主要由輸入隊列(V0Q)、緩衝Crossbar、輸入端調度器和輸出端調度器組成。輸入隊列和交叉點緩衝用於存儲暫時得不到調度輸出的信元；Crossbar用於建立輸入/輸出端的連接，傳輸信元；輸入/輸出端調度器共同完成MUIQF調度算法。當輸入端有分組到達時，首先進行一系列的分組處理，包括查表、報頭更新、分類、分段，然後在輸入隊列中緩衝，等待輸入端調度。為解決輸入/輸出端的競爭，每一個輸入/輸出端都設有一個調度器。在每個時隙，MUIQF算法根據VOQ和交叉點緩衝長度信息，每個輸入調度器從其輸入埠的N個VOQ隊列中選出一個隊頭信元送往相應的交叉點；每個輸出調度器從對應的N個交叉點緩存中選出一個輸出。輸入和輸出端調度器之間不需信息的交互，分別獨立執行。圖2所示為輸入端排隊策略，採用了VOQ排隊機制，主要是為了避免單個FIFO帶來的HOL阻塞問題，輸入端為每個輸出端維護一個單獨的FIFO的隊列。在具體實現時，這些隊列可以用一個單獨的物理存儲器，通過簡單的存儲器管理，劃分成多個邏輯獨立的隊列。對於一個NxN的緩衝Crossbar,每個輸入端總共有N個獨立的FIFO,信元經過查表、分類存於不同的FIF0隊列。圖3所示為本發明方法一實施例的執行過程。本實施例展示了在一個交叉點緩衝容量C為1的4x4緩衝Crossbar中MUIQF算法一次迭代的過程，圖中V0Q隊列和交叉點緩衝中的一個黑點代表一個信元。初始時(t時隙)時輸入/輸出調度器指針、隊列長度狀態如圖3(a)所示，調度之後(t+l時隙)狀態如圖3(b)所示。以輸入端l和輸出端l調度器執行情況為例說明。輸入端調度器指針L初始值為2，由於V0Q13和V0Q14是EV0Q，並且L(V0Q14，t)〉L(V0Q^t)，所以選擇V0QM調度，指針更新為^更新為(4+1)(模4)=1;同樣，輸入端2、3、4也各自選擇V0QM、V0Q『V0Qu調度，指針分別更新為1、2、2。輸出端1對應的交叉點都有信元等待發送，則指針開始按照輪轉規則，選擇交叉點緩衝和對應輸入隊列長度之和最大的交叉點進行調度，即交叉點CBn，之後將(^更新為(1+1)(模4)=2;同樣輸出端2、4選擇CB12、CB44調度，指針分別更新為2、1，輸出端3沒有信元調度，指針不5變。本領域人員在本發明方案基礎上，以選取不同參數(信元大小、C、N等)或用於其它交換結構而做出的其它方案，亦在本發明保護的範圍之內。權利要求一種用於緩衝Crossbar的隊列長度均衡調度方法，包括排隊技術和緩衝Crossbar調度算法，其特徵在於(1)、不同長度的IP分組在調度前劃分成固定長度的「信元」，在輸出端重組後再發送到鏈路上去；信元輸出到鏈路之前只在輸入隊列和交叉點緩衝存儲；輸入隊列採用虛擬輸出排隊(VOQ)技術，若在時隙t輸入端i到達一個目的端為j的信元，那麼該信元被放入VOQij隊列中；若VOQij隊列被調度，隊頭信元將被存入交叉點緩衝CBij中；VOQij在t時隙的隊列長度表示為L(VOQij，t)；CBij在t時隙的隊列長度表示為L(CBij，t)；其中1≤i，j≤N；(2)、一個交叉點緩存的最大容量用C表示；t時隙時，若L(VOQij，t)＞0且L(CBij，t)＜C，稱VOQij在t時隙為EVOQ(EligibleVOQ)；t時隙時，若L(CBij，t)＞0，稱CBij為ECB(EligibleCrosspointBuffer)；其中1≤i，j≤N；(3)、緩衝Crossbar調度算法稱為MUIQF，在MUIQF算法中，每個輸入/輸出端都有一個調度器，各設有1個優先指針，指向當前最高優先服務的隊列，每次執行過程開始時所有輸入/輸出端為空閒狀態；MUIQF輸入/輸出端調度器獨立執行輸入端調度輸入端i的調度器指針Ii(1≤i≤N)，指向當前優先選擇服務的VOQ；從指針Ii所指的隊列開始，按照輪轉規則，尋找第一個L(VOQij，t)(1≤j≤N)最大的EVOQ，假定找到為VOQiq(1≤q≤N)，把它的隊頭信元傳送到CBiq，指針Ii更新至(q+1)(模N)；如果找不到，指針保持不變；輸出端調度輸出端j的調度器指針Oj(1≤j≤N)，指向當前優先選擇服務的CB；從優先指針Oj所指的隊列開始，按照輪轉規則，尋找第一個L(VOQij，t)+L(CBij，t)(1≤i≤N)最大的ECB，假定找到為CBpj(1≤p≤N)，就把它的隊頭信元傳送到輸出端j，指針Oj更新至(p+1)(模N)。如果找不到，指針保持不變。2.如權利要求1所述的緩衝Crossbar調度方法，其特徵在於分為輸入調度和輸出調度之間無需信息交互，二者相互獨立，並行工作。3.如權利要求1所述的緩衝Crossbar調度方法，其特徵在於每個時隙每個輸入端和輸出端至多調度一個信元。4.如權利要求1所述的緩衝Crossbar調度方法，其特徵在於輸入端調度時，優先調度該輸入端中隊長最長的VOQ;輸出端調度時，優先調度交叉點自身隊列長度與對應的VOQ長度之和最大的交叉點緩衝。5.如權利要求l所述的緩衝Crossbar調度方法，其特徵在於Crossbar交換的信元大小為64位元組。全文摘要本發明涉及了一種用於緩衝Crossbar的隊列長度均衡調度方法。本發明屬於寬帶網絡交換
技術領域：
。本發明包括Crossbar輸入端和輸出端調度方法，其方法是，分組只在輸入端隊列和Crossbar交叉點緩衝存儲；每個輸入/輸出端都有一個調度器，調度方法由這些調度器協同執行；輸入端調度器負責將分組從輸入端隊列調度到相應交叉點緩衝，執行時從本輸入端選擇長度最長的隊列進行調度，輸出端調度器負責將分組從交叉點緩衝調度到輸出鏈路上，執行時選擇自身隊列長度與對應的輸入隊列長度之和最大的交叉點進行調度；該調度方法給較長的隊列更多的被服務機會，能夠自適應均勻和非均勻等各種流量，使各個輸入端隊列長度儘量均衡，具有良好的穩定性、吞吐量和時延性能，適用於高速路由器/交換機。文檔編號H04L12/56GK101695051SQ20091023391公開日2010年4月14日申請日期2009年10月21日優先權日2009年10月21日發明者彭來獻,田暢,趙文棟,路欣申請人:中國人民解放軍理工大學;