一種交叉點小緩存的高性能crossbar調度方法
2023-06-14 21:27:56
專利名稱：一種交叉點小緩存的高性能crossbar調度方法
技術領域：
本發明涉及一種交叉點小緩存的高性能crossbar調度方法，主要適用於高速、多 埠、大容量的IP路由器/交換機。
背景技術：
IP路由器/交換機是網際網路中重要的網絡互聯設備，隨著Internet規模和容量的 飛速增長，以及多業務的發展，要求路由器不僅支持多埠、高速鏈路速率、具備大容量的 處理能力，還要能提供一定的QoS保證，具體表現在滿足吞吐量、帶寬、時延等方面的不同 需求。在路由器中，交換網絡用於建立輸入與輸出端之間的數據通路，負責數據的轉發，是 制約路由器埠速度和容量的關鍵因素。 交換結構中典型的分組緩存機制大致有3種輸出緩存(0Q :0utput Queuing)、 輸入緩存(IQ :Input Queuing)和聯合輸入輸出緩存(CI0Q-Combined Input Output Queuing)。這3種典型的交換結構均採用單一調度器，來尋找輸入與輸出之間的最大或極 大匹配。由於需要集中控制，大大限制了交換結構的可擴展性。目前一種有效地提高交換 結構可擴展性途徑是將緩存設置在交換陣列的交叉點處，這樣調度器在輸入/輸出端可以 獨立執行，不需要集中控制。近年來VLSI技術的發展使得在中小規模的交換陣列中設置少 量緩存已成為可能。如Xilinx公司開發的Xilinx XCV812E，在16X 16的交換陣列中做進 了 1. 12Mbits的RAM，每個交叉點可以緩存4Kbits的數據。在交換陣列的交叉開關處緩存 分組是早期的分組交換機用來解決阻塞問題的手段。依據目前的技術條件，交叉點緩存尚 不足以存放所有滯留在交換結構中的分組，仍然需要與輸入緩存結合使用，這就是聯合輸 入交叉點緩存(CICQ-Combined Input andCrosspoint Queuing)交換結構。由於CICQ結 構與IQ結構面臨同樣的隊頭阻塞(head of lineblocking)問題，CICQ的輸入緩存一般也 採用虛輸出隊列技術(VOQ:Virtual Output Queuing)。 對於crossbar調度算法的問題，與0Q， IQ和CI0Q等交換結構相比，CICQ特別具備 的交叉點緩存的特點，解開了輸入與輸出調度匹配的耦合，從而可以在輸入和輸出端分布 式地進行調度。在CICQ交換結構上，實用的調度算法設計往往注重三個指標小緩存、低復 雜度和高吞吐率。小緩存是指CICQ結構本身所具備的特定指標。與IQ，0Q，CI0Q等其他交 換結構不同，鑑於目前VLSI技術，尚不能在CICQ結構Crossbar的交叉點處植入足夠大的 緩存。因此，設計CICQ交換結構的調度算法首先必須能工作於"小緩存"這個特定指標下。 低複雜度是針對高速交換的設計需求而提出的核心指標。 一般情況下，交換機每塊線卡至 少能支撐100ms的分組緩衝，對於40Gbps的鏈路而言，緩衝區至少要達到500MB，複雜度高 的調度算法將導致仲裁時間過長而成為交換機調度的瓶頸，特別對於支持大埠和高鏈路 帶寬的交換機而言，其調度器的執行時間越短越好，這需要調度算法的複雜度儘可能地低， 並且，低複雜度的調度算法意味著更容易在硬體設計中得以實現。高吞吐率是對任何交換 結構調度算法設計需求而提出的根本指標，一個具備實用性的調度算法是指在各種流量下 均能達到至少95%以上的吞吐率。
綜觀已有的研究成果，關於CICQ交換結構調度算法的研究分為兩大類一類是純 理論分析，探討CICQ調度算法的吞吐量、時延、服務質量保證等性能的理論基礎但是卻存 在複雜、硬體難以實現的問題，無法在高速的環境下應用。 關於CICQ交換結構調度算法另一類研究方法是從實用性出發，以交叉點小緩存、 高效、低複雜度、硬體易實現作為性能指標，設計各種易於硬體實現的快速啟發式調度算 法。這類算法的共同點在於減少控制信息量和複雜的計算，一般採用兩種手段一種是依 據交叉點緩存的狀態信息進行調度；另一種是基於輪轉(Round-Robin)機制。MCBF(Most Critical BufferFirst)和LFF-LBF算法都是依據交叉點緩存的忙閒來進行輸入/輸出調 度，使得交叉點緩存得到充分的利用，仿真結果表明算法在均勻流量下具有良好的時延、穩 定性能。然而這兩種算法沒有考慮輸入端隊列的狀態，在非均勻流量下會出現不穩定現象， 導致性能嚴重下降。 由於輪轉機制具有低複雜度、硬體易實現等優良特性，成為實用性研究方面的重 點，其中典型的調度算法有RR-RR和LQF(Longest Queue First)-RR。雖然RR-RR簡單易實 現、複雜度僅為0(1)，但是在非均勻流量下不能提供良好的吞吐量和時延性能。LQF-RR算 法在輸入端總是優先服務最長的V0Q，儘量保持各個隊列調度均衡，在各種流量下都具有優 良的性能，然而該算法複雜度為O(logN)，限制了算法在高速處理環境下的應用。為了提高 CICQ交換結構在非均勻流量下的性能，研究者通過改進輪轉指針更新的規則，基於RR-RR 提出了眾多改進算法，基本思想是通過為每個V0Q隊列分配固定的調度份額、或者根據相 鄰調度V0Q長度關係的"差分因子"來約束輪轉指針的更新，這些算法的複雜度都是0(1)， 保留了 RR-RR低複雜度的特點，仿真結果表明，當每個交叉點容量是1個信元大小時，在非 均勻流量下能夠獲得較好的吞吐量和時延性能，然而它們的"差分因子"或者"份額"的取 值都是仿真得到的經驗值，在複雜的業務流量下無法得到可靠性驗證。
因此，高效、實用的調度算法應當在簡單的RR-RR算法的基礎上，通過某些指針更 新策略彌補其在非均勻流量下性能不佳的缺憾，並且新的更新策略不依賴其他人為設定的 "經驗"參數。 發明內容本發明的目的是提供一種交叉點小緩存，硬體易實現的高性能crossbar 調度方法。基於最長隊列預測的輪轉型調度算法RR-LQD(Round Robin with Longest QueueDetecting)的主要思想是在輸入端內局部預測隊列最長的V0Q並盡力為該隊列服 務，保持調度中各個隊列長度均衡，在保持低複雜度的同時提高系統穩定以及在非均勻流 量下吞吐量、時延等性能。 本發明的適用於高速、多埠 、大容量IP路由器/交換機的crossbar調度方法由 排隊技術和RR-LQD調度算法構成，具體如下 (1)信元排隊不同長度的IP分組在轉發前劃分成固定長度的"信元"，在輸出端 重組後再發送到鏈路上去。信元到達過程是一個離散時間隨機過程，每個輸入端每個時隙 至多到達一個信元。輸入隊列採用V0Q排隊技術，若輸入端i到達一個目的端為j的信元 (1《i， j《N)，那麼該信元被放入V0Qij隊列中。crossbar的每個交叉點都有緩存，每個 輸入端和每個輸出端可以相互獨立地和交叉點緩存進行交換。 (2) RR-LQD算法分為輸入調度和輸出調度兩部分，每個輸入調度器維護兩個指針 最長隊列預測指針dp和輪轉指針rp (1《dp，rp《N);每個輸出端調度器維護一個輪轉指
4針p(l《p《N)。這些指針分別指向當前優先服務的隊列或交叉點。算法具體描述如下
輸入端調度首先進行最長隊列預測輸入調度器從dp指向的位置開始，通過輪 轉策略尋找第一個隊列長度大於當前dp所指向VOQ的隊列。若找到，更新dp指針，指向該 預測的隊列；否則，dp指針不更新。然後判斷預測隊列是否為EVOQ(非空且對應的交叉點 不滿)。此時，調度器認為dp指針指向的隊列就是該輸入端中"最長"的隊列，要優先對它 服務，判斷預測隊列是否為EVOQ :若是EVOQ，則調度器將它的隊頭信元調度至相應的交叉 點緩存；若不是EVOQ，則調度器從rp指向的位置開始，通過輪轉策略尋找下一個EVOQ，若找 到則調度器將它的隊頭信元調度至相應的交叉點緩存，並將rp更新至該EVOQ的下一個位 置；若找不到則rp保持不變。 輸出端調度從p指向的位置開始，通過輪轉策略尋找下一個非空的交叉點CB，若 找到，則將該交叉點的隊頭信元調度輸出；若找不到則p保持不變。 本發明通過在crossbar的輸入端調度中引入最長隊列預測和輪轉的雙指針技 術，實現了 crossbar交叉點小緩存調度高吞吐率、低複雜度、硬體易實現的目標。通過應用 該方法，crossbar調度過程具有以下有益效果 (1)依據隊列長度信息進行調度，消除了對各種經驗參數的依賴； (2)總是對預測的最長隊列進行優先服務，保持了各個隊列長度均衡，能夠自適應
網絡環境中各種業務流量，在各種均勻和非均勻流量下，均能達到100%的吞吐量，並且具
有良好的時延性能； (3)以求解局部最佳取代LQF-RR算法的全局最佳，從而省略了排序比較的過程， 大大降低了算法的複雜度，算法複雜度僅為O(l);
下面結合附圖和實施例對本發明進一步說明。 圖1是聯合輸入交叉點排隊crossbar交換結構的組成圖； 圖2是本發明方法一實施例的執行過程。
具體實施例方式
參考圖l，聯合輸入交叉點排隊crossbar交換結構主要由輸入隊列(V0Q)、帶緩存 的crossbar、輸入端調度器和輸出端調度器組成。輸入隊列用於存儲暫時得不到輸入調度 的信元；crossbar用於建立輸入/輸出端的連接，傳輸信元，交叉點緩存用於存儲暫時得不 到輸出調度的信元；輸入端仲裁器和輸出端仲裁器分工完成RR-LQD調度算法。當輸入端有 分組到達時，首先進行一系列的分組處理，包括查表、報頭更新、分類、分段，然後在輸入隊 列中緩衝，等待輸入端調度器調度。輸入端調度器根據V0Q和交叉點緩存的狀態信息完成 信元從輸入隊列到交叉點緩存的調度；輸出端調度器根據交叉點緩存的狀態信息完成信元 從交叉點緩存到輸出端的調度。所有的輸入/輸出端調度器是相互獨立工作的。
圖2所示為本發明方法一實施例的執行過程。本實施例展示了一個4X4的CICQ 交換結構中RR-LQD算法在輸入端i和輸出端j的執行過程。在開始時，輸入端i的最長隊 列預測指針dp指向V0Q^EV0Q輪轉指針rp指向V0Qi4。調度器從VOQn以輪轉方式尋找第 一個長於V0Qn的V0Q，若找不到，則dp保持不變；若找到為V0Qi3，將dp更新指向V0Qi3，如圖2 (a)所示。然後判斷V0Qi3是否為EV0Q，若是EV0Q，則調度器將V0Qi3的隊頭信元調度至 CBi3 ;若V0Qi3不是EV0Q，則調度器從rp指向的V0Qi4開始以輪轉方式尋找EV0Q，若找不到， 則rp保持不變；若找到為V0Qu，則調度器將V0Qn的隊頭信元送至CBn，並將rp指向V0Qi2， 如圖2(b)所示。輸出端j的調度器從p指針開始以輪轉方式尋找ECB，若找不到，則p指針 保持不變；若找到為CB4j，則調度器將CB4j的隊頭信元輸出，並將p指針指向CBU，如圖2 (c) 所示。 本領域人員在本發明方案基礎上，以選取不同參數(交叉點緩存容量、埠數等) 或用於其它交換結構而做出的其它方案，亦在本發明保護的範圍之內。
權利要求
一種交叉點小緩存的高性能crossbar調度方法，包括排隊技術和crossbar調度算法，其特徵在於(1)、不同長度的IP分組在轉發前劃分成固定長度的「信元」，在輸出端重組後再發送到鏈路上去；輸入隊列採用虛擬輸出排隊(VOQ)技術，若輸入端i到達一個目的端為j的信元(1≤i，j≤N)，那麼該信元被放入VOQij隊列中；crossbar的每個交叉點都有少量緩存，每個輸入端和每個輸出端可以相互獨立地和交叉點緩存進行交換；(2)、crossbar調度算法稱為RR-LQD，RR-LQD算法分為輸入調度和輸出調度兩個部分輸入調度階段每個輸入調度器維護最長隊列預測指針dp和輪轉指針rp兩個指針(1≤dp，rp≤N)，每個時隙開始時首先進行最長隊列預測，從dp指向的位置開始，通過輪轉策略尋找第一個隊列長度大於當前dp所指向VOQ的隊列；若找到，更新dp指針，指向該預測的隊列，否則，dp指針不更新；然後判斷預測隊列是否為EVOQ(非空且對應的交叉點不滿)，此時，調度器認為dp指針指向的隊列就是該輸入端中「最長」的隊列，要優先對它服務，判斷預測隊列是否為EVOQ，若是EVOQ，則調度器將它的隊頭信元調度至相應的交叉點緩存，若不是EVOQ，則調度器從rp指向的位置開始，通過輪轉策略尋找下一個EVOQ，若找到則調度器將它的隊頭信元調度至相應的交叉點緩存，並將rp更新至該EVOQ的下一個位置，若找不到則rp保持不變；輸出調度階段每個輸出端調度器維護一個輪轉指針p(1≤p≤N)，每個時隙開始時從p指向的位置開始，通過輪轉策略尋找下一個非空的交叉點，若找到，則將該交叉點的隊頭信元調度輸出；若找不到則p保持不變。
2. 如權利要求l所述的排隊技術，其特徵在於crossbar的每個交叉點緩存是少量的。
3. 如權利要求1所述的crossbar調度方法，其特徵在於分為輸入調度和輸出調度兩 部分，之間無需信息交互，二者相互獨立，並行工作。
4. 如權利要求1所述的crossbar調度方法，其特徵在於每個時隙每個輸入端和輸出 端分別調度一個分組。
5. 如權利要求1所述的crossbar調度方法，其特徵在於每個輸入端維護兩個優先級 指針，分別是最長隊列預測指針dp和輪轉指針rp。
6. 如權利要求1所述的crossbar調度方法，其特徵在於輸入端調度時，只有當最長 隊列預測指針dp找不到滿足條件的VOQ時，才執行輪轉。
7. 如權利要求1所述的crossbar調度方法，其特徵在於輸入端調度時，dp指針更新 不依賴於經驗性參數，而是通過隊列預測尋找局部最長，並向全局最長隊列逼近。使得一旦 預測某一隊列為"最長"隊列，無論本時隙內是否被調度，dp指針都指向它。
8. 如權利要求1所述的crossbar調度方法，其特徵在於輸入端調度時，每個時隙並 行執行N次比較，算法複雜度為0(1)。
9. 如權利要求1所述的crossbar調度方法，其特徵在於crossbar交換的信元大小為 64位元組，埠速率為lOGbps。
全文摘要
本發明公開了一種交叉點小緩存的高性能crossbar調度方法，主要包括排隊技術和crossbar調度算法，其方法是，分組在輸入端和crossbar交叉點兩處存儲，到達的分組被劃分成固定長度的信元根據其目標轉發埠放入相應的隊列進行排隊，交叉點設立較小容量的緩存，解開了輸入與輸出調度匹配的耦合；在輸入端與輸出端分別採用調度器，輸入端採用最長隊列預測機制算法選擇一個信元進入相應的交叉點緩存，輸出端採用簡單的輪詢算法選擇一個交叉點緩存中的信元輸出；該調度方法穩定、高效、複雜度低，適用於大容量的高速路由器/交換機。
文檔編號H04L12/56GK101695052SQ20091023391
公開日2010年4月14日 申請日期2009年10月21日 優先權日2009年10月21日
發明者彭來獻, 田暢, 趙文棟, 路欣 申請人:中國人民解放軍理工大學;