基於前置反饋的兩級交換結構工作方法

2023-09-16 06:45:10 2

專利名稱：基於前置反饋的兩級交換結構工作方法
技術領域：
本發明屬於網際網路信息傳輸技術領域。
背景技術：
網際網路用戶的迅猛增長和多媒體業務流的激增使Internet面臨越來越大的數據 傳輸壓力，雖然密集波分復用技術使單個波長的數據傳輸率高達160Gbps，但中繼系統的交 換速率卻遠遠低於光域內的數據傳輸率，這就使中繼系統因交換速率過低而成為Internet 的瓶頸。此外，長期的流量監測表明Internet數據流具有自相似性，其典型特徵是數據具 有突發性。因此，能夠適應自相似業務流的高速交換結構就成為下一代Internet的核心技 術之一。傳統的交換結構因為複雜度或加速比等原因均無法滿足未來的交換需求。近年 來，張正尚教授等人提出的負載均衡結構LB-BvN(Load Balanced Birkhoff-von Neumann switch architecture)因非常接近未來的交換需求而備受關注。LB-BvN由兩級crossbar 組成，其第一級crossbar將到達的數據流均勻散布到中間緩存，這使得該結構能夠較好地 適應自相似業務流；此外其兩級crossbar均採用確定的、周期性的連接模式，這種複雜度 為0(1)的crossbar連接模式排除了算法調度時間對時槽長度的影響，在信元長度一定的 情況下，時槽長度僅與埠速率有關。這就意味著，埠速率可以提高到微電子技術甚至是 光傳輸技術所能達到的極限。但該結構可能導致信元失序，國內外現有解決失序問題的方 案都在性能和複雜度之間取捨。文獻YEUNGK L, HU B, LIU N H A novel feedback mechanism for load balanced two-stage switches[C]IEEE International Conference on Communications Glasgow, Scotland, United kingdom Institute of Electrical and Electronics Engineers Inc.，2007，6193-6198.提出的FTSA利用輸入埠 i和輸出埠 i位於同一線 卡這一特性，通過一種錯列對稱特性(staggered symmetry)的crossbar連接模式將中間 緩存的隊列信息反饋到輸入端，輸入端基於該反饋信息選擇一個信元傳輸至中間緩存，這 種「有的放矢」的工作模式可以有效降低中間緩存的下溢(underflow)問題，從而獲得了極 其優異的時延性能。但該結構所允許的調度算法的執行時間過於短暫，現有微電子和存儲 技術必然會導致時槽長度的增加，進而損害FTSA的高速交換能力和可擴展性。對該問題的 詳細介紹如下為便於表達，本文約定交換結構的輸入輸出埠數均為N，定義到達輸入埠 i且 目的埠為k的信元集合為數據流Fi, k，記Ci, k泛指Fi, k的任意一個信元。兩級crossbar 分別記為XBl和XB2，XBl前的VOQ (Virtual Output Queue)緩衝稱為輸入緩存，記為V0Q1， XB2前的VOQ緩衝稱為中間緩存，記為V0Q2。VOQl (i，k)用於緩存Ciik, V0Q2(j, k)用於緩 存到達中間埠 j且目的埠為k的信元。在不引起混淆的前提下，文中的「輸入埠」均 指XBl的輸入埠，「中間埠，，指XB2的輸入埠，「輸出埠，，指XB2的輸出埠。輸入 埠 i通過中間埠 j與輸出埠 i_l相連簡記為Ii—Mj-—Oi^10
(I)FTSA結構和錯列對稱連接模式FTSA結構由XBUXB2和VOQU V0Q2組成，如圖1所示。任意V0Q2(j, k)都只有1 個信元的緩存空間(本文稱之為單信元緩衝模式)，兩級crossbar採用圖2所示的錯列對 稱連接模式，其關鍵特性在於若t時槽％—0k，則在t+Ι時槽Ik--MpFTSA採用圖3所示的後置反饋模式，即中間埠 j在轉發信元之後繼續向輸出端 口 k傳輸記錄V0Q2(j，k) (k = 0,1,2, -,N-1)狀態的緩存信息。由於輸入埠 k和輸出 埠 k位於同一線卡，故可方便地將到達輸出埠 k的N位緩存信息反饋至輸入埠 k。錯 列對稱的crossbar連接模式又恰恰使得下一個時槽Ik-Mj,這樣輸入埠 k即可根據目 的埠(Mj)的緩存狀態信息進行「有的放矢」的信元轉發以降低中間緩存的underflow問 題，從而獲得十分優異的時延性能。圖2所示錯列對稱模式具有以下特性①若t時槽Ii-—Mj則同時必有Mj-—Oh
②若t時槽Ii-—Mj則t+Ι時槽Mj—0卜2注埠號的加減操作最終都需要對N取模，即i-Ι實質上是(i-l)mod N，下同。(2)FTSA對調度算法的時間限制從圖3可知FTSA中信元傳輸和算法調度嚴格串行，為避免在XBl轉發階段因信元 傳輸等待調度結果而增加時槽長度，FTSA要求調度算法必須在crossbar重配置時間內完 成(算法的時域空間用格子紋理顯示)。然而FTSA中的三種算法=RR(Roimd-Robin)、EDF 和Longest Queue First (LQF)最壞情況下均需搜索N次。首先，LQF算法性能最優但尋找最長隊列的複雜度為O(IogN)，而且最長隊列並不 一定是符合條件的(目標位置已有信元)，最壞情況下LQF算法需要搜索所有N個隊列才能 獲得符合條件的最大隊長。EDF選擇能在最短時間內離開交換機的信元，對於圖2所示的錯 列對稱連接模式，輸入埠 i 總按照 VOQl (i，i-2)，VOQl (i，i_3)，-,VOQl (i，N)，VOQl (i， 0)，…，V0Ql(i，i-l)的次序搜索第一個符合條件的隊列，最壞情況下也需要搜索N次。盡 管RR算法相對易於實現，但事實上輪詢的下一個隊列同樣不一定符合要求，故最壞情況下 也需要搜索N次。另一方面，crossbar重配置所消耗的時間本質上取決於crossbar交叉點的開關 速度，隨著微電子技術的發展，目前成熟的商用晶片的工作頻率可達4GHz以上，即元器件 開關的周期約為0. 25nS(lS/4GHZ)。但存儲技術的發展卻相對滯後，目前高速存儲器的存取 周期約為0. 5ns。雖然N-bit緩存信息的反饋過程因輸入輸出埠位於同一線卡的原因耗 時較少，但對最壞情況下要搜索N次且需多次比較運算的算法而言，在crossbar重配置時 間內完成反饋和調度是無法實現的。由上可知雖然FTSA在仿真中表現出十分優異的交換性能，但該結構中信元傳輸 與調度算法的串行工作模式要求調度算法在極短的時間內完成，對最壞情況下要搜索N次 且需多次比較運算的算法而言，在crossbar重配置時間內完成反饋和調度是無法實現的， 這種時間限制必然導致調度算法耗時遠遠超出crossbar重配置時間，信元傳輸不得不等 待調度結果，時槽長度勢必因調度算法而增加，進而限制埠速率的提升，降低FTSA的高 速交換能力和可擴展性。

發明內容
鑑於FTSA的這種缺陷，本發明的目的是使調度算法與信元傳輸並行工作，從而拓 展調度算法的時域空間(為調度算法提供更長的時間區間)，避免時槽長度因信元傳輸需 等待調度結果而被拉長，提高交換結構的高速交換能力和可擴展性。本發明的目的是通過如下的手段實現的。基於前置反饋的兩級交換結構工作方法FFTS (Front-Feedback-based Two-stage Switch architecture)，包含兩級crossbar和三級緩存第一級crossbar之前的輸入緩 存、兩級crossbar之間的中間緩存和第二級crossbar之後的重排序緩存；輸入緩存採用 VOQ緩衝模式，中間緩存採用雙信元空間的VOQ緩衝模式，重排序緩存採用VIQ緩衝模式； 中間埠在每個時槽之初預測本時槽結束時的緩存狀態信息並將其反饋至輸入埠，輸入 埠在進行信元傳輸的同時，根據反饋得到的信息選擇下一時槽要轉發的信元，被選中的 信元攜帶其理論路逕到達中間緩存等待轉發，信元到達輸出端後根據其所攜帶的理論路徑 值完成重排序過程。


圖1現有技術基於反饋(後置)的兩級交換結構FTSA結構圖。圖2是現有技術錯列對稱的crossbar連接模式示意圖。圖3是現有技術後置反饋模式示意圖。圖4是本發明前置反饋的兩級交換結構FFTS結構圖。圖5是本發明前置反饋操作示意6是本發明與現有技術在均勻流量模型環境中的時延比較圖。圖7是本發明與現有技術突發環境(長度為32)中的時延比較圖。圖8是本發明與現有技術在Hot-spot流量模型環境中的時延比較圖。
具體實施例方式下面結合附圖和實施例對本發明作進一步說明。本發明方法FFTS是針對FTSA結構對調度算法的時間限制問題所做的改進方案， 故FFTS具有FTSA結構的基本元素，如①FFTS和FTSA結構中均包含兩級crossbar (XBl和XB2)和VOQl及V0Q2。②XBl和XB2同採用錯列對稱連接模式。③在輸入埠均可選擇RR、EDF或LQF算法調度。FFTS與FTSA的不同之處在於①前置反饋模式。FFTS在每個時槽之初預測本時槽結束時中間緩存的狀態信息並將其反饋至對應 輸入埠，是為前置反饋，這使得信元傳輸可以與調度算法並行工作。而FTSA在每個時槽 之末向對應輸入埠反饋，是為後置反饋，信元傳輸必須與調度算法嚴格串行。②雙信元緩衝模式。FFTS中任意V0Q2(j，k)設置2個信元的緩存空間，是為雙信元緩衝模式。而FTSA 中任意V0Q2(j，k)設置1個信元的緩存空間，是為單信元緩衝模式。
5
③前置反饋信息的預測。FFTS在時槽之初所反饋的N-bit信息並不是該時刻中間緩存狀態的簡單複製，而 是預測該時槽結束時的緩存狀態信息。該預測規則需綜合考慮雙信元緩衝的應用環境和錯 列對稱的crossbar連接模式。④基於理論路徑的重排序策略。FFTS在輸出端設置VIQ緩衝；每個離開XBl的信元都被賦予一個「理論路徑」，信 元到達輸出埠後依據自身攜帶的理論路徑值在VIQ中完成重排序過程。以上手段的具體描述如下①前置反饋模式FFTS結構由兩級crossbar (XBl及XB2)和三級緩衝(V0Q1、V0Q2及VIQ)組成，如 圖4所示。前置反饋模式的核心思想在於中間埠 j在每個時槽之初(信元傳輸之前)預測 本時槽結束時的緩存狀態，並將預測結果反饋至輸入埠。前置反饋模式使得調度算法可 與信元傳輸並行工作，這一策略必然會賦予調度算法更長的執行時間，圖5中格子紋理所 覆蓋的時間區間表示算法經拓展後的時域空間。由於前置反饋的信息是基於預測的，且預 測時無法獲知本時槽內的信元到達情況，故前置反饋的N-bit緩存信息並不能準確反映本 時槽結束時中間埠的緩存狀態，即具有非完備性。②雙信元緩衝模式。在單信元緩衝模式下，前置反饋信息的非完備性可能導致信元衝突，為此FFTS採 用雙信元緩衝模式，中間緩存任意子隊列緩存容量均設置為兩個信元空間，若且唯若發生 信元衝突時才將衝突信元緩存於第二信元空間。即將任意V0Q2(j，k)的緩存容量設為兩個 信元空間，僅在發生信元衝突時將衝突信元緩存於第二個信元空間，否則第二信元空間不 使用。③前置反饋信息的預測規則基於圖2所示的錯列對稱連接模式，令t時槽Ii—Mj—Oi^10 FFTS中t時槽中間 埠 j前置反饋信息(記為V)的生成規則如下A:gV0Q2(j，i-1)的第二個信元空間為空，則 V[i_l] = 1，否則 V[i_l] = 0。B 若V0Q2(j，i_2)的第二個信元空間為空，則V[i_2] = 1，否則V[i_2] = 0。C 對於所有 r(r = 0，1，2，…，N-1 且 r 乒 i_l，r 乒 i_2)，若 V0Q2 (j，r)為空則 V[r] = 1，否則 V[r] = 0。④基於理論路徑的重排序策略。FFTS所採用的雙信元緩衝模式雖然解決了信元衝突問題，但同時卻導致了信元失 序。FFTS通過為每個信元賦予一個理論路徑及在輸出端設置VIQ來解決該問題。首先，FFTS在每個輸入埠 i均設置N個指針GiikGi = O, 1，2，…，N-1)，分別指 示流Fi, k的下一個信元的理論路徑值。若Ci, k被調度算法選中，則將Gi, k和Ci, k組合在一 起轉發至中間埠，之後將Gi,k更新為(Gu+Dmod N。這裡所謂「理論路徑」是相對於信元的真實路徑而言的。若流Fi, k某個信元Cf通 過中間埠 _r(_r = o，i，2，-,N-D到達目的埠 k，則稱其真實路徑為_r。在實踐中，不 妨設流Fi,k的第一個信元C°的理論路徑為0 (不管其真實路徑如何)，則其同一個流的下一個信元C1的理論路徑必為1( (0+1) mod N)。這種工作模式決定了同一個流的相鄰信元必然 具有相鄰的理論路徑，從而可以在輸出端通過信元的理論路徑值來恢復其原有順序，保證 信元的有序轉發。此外，FFTS在每個輸出端都設置N個VIQ隊列分別存儲來自不同輸入埠的信元。 每個VIQ包含N個子隊列分別存儲具有不同理論路徑的信元，如理論路徑為e的Ci, k置於 VIQ(i，e，k)中緩存；任意輸出埠 k均設置N個指針Pi,k(i = 0，1，2，…，N-1)分別指示 流Fi, k的下一個信元所應到達的VIQ隊列。雙信元緩衝模式決定了任意信元為避免失序而需等待的最大時槽數不超過N。這 就意味著若Pi, k所指隊列非空，則表示Fi, k 「最老的」信元已到達，直接將其轉發即可保證 信元不失序地離開交換機。轉發完畢後，Pu同樣更新為(Pu+Dmod N。本發明FFTS方法帶來的優點可由以下兩方面驗證①理論分析FFTS對算法執行時間的拓展效果。②仿真驗證FFTS的時延性能。以下予以分述①FFTS對算法執行時間的拓展。若記一個時槽的時間為T，crossbar的重配置時間為Τκ，信元傳輸時間為Tc， N-bit反饋信息的傳輸時間為TN，緩存信息從輸出端反饋至輸入端的時間為TF，信元在經 crossbar到達目的緩存的傳播時延記為TP，則T = TE+TN+TC+TP如圖5所示，XB2在一個時槽內需要傳輸一個信元和N-bit的反饋信息，而XBl在 一個時槽內只需傳輸一個信元，於是可將XBl上的信元傳輸時間向後推遲TN，從而為調度算 法拓展更多的時域空間。故FFTS中算法的執行時間Tffts TFFTS = TE+TN+TC-TF考慮相同的分析方法，圖3所示FTSA中算法的調度時間Tftsa為Tftsa = Te-Tf易見，相對於FTSA，本發明所提出的FFTS結構將調度算法的執行時間延長了 TN+T。，考慮到T。>> Tk，很明顯，FFTS為算法提供了相對較大的時域空間，這一特性使得交 換結構能夠支持較大規模的交換模塊和較高的交換速率。②FFTS的時延性能。我們分別從傳統(iSLIP)、同類型(Byte-Focal、CR switch和FTSA)及最優結構 (0Q(Output Queuing))的角度在均勻流量、突發流量和Hot-spot流量模型環境中仿真分 析，仿真採用32X32的交換模型，仿真結果越小越好。(1)均勻流量模型所謂均勻流量是指信元以Bernoulli i. i. d.過程到達且以等概率到達各輸出端 口。仿真結果如圖6所示。(2)突發流量模型突發流量用0N-0FF模型來產生，平均突髮長度ABL (average burst length)設為 32,同一突發塊內的信元具有相同的目的埠，仿真結果如圖7所示。(3) Hot-spot 流量模型
Hot-spot流量模型中cell以Bernoulli i. i. d.過程到達輸入埠 i，但cell以 2/3的概率到達目的埠 i，以等概率到達其餘埠。仿真結果如圖8所示。仿真所選六種結構中，iSLIP算法廣泛應用於現有各類型IQ交換機，但複雜的集 中式調度制約了其高速交換能力和可擴展性；OQ需要N倍的加速比，在實際應用中是無法 實現的(除非N極小)，其理論時延常被視為交換結構性能的上限。Byte-FocalXR switch、FTSA和本發明所提出的FFTS同屬於負載均衡結構，而負 載均衡結構在未來的高速交換和自相似業務流環境中具有特殊的優勢，從以上三種環境的 仿真結果可以看出，FFTS的時延性能遠優於Byte-Focal和CR switch而稍遜於FTSA，但考 慮到FTSA的理論性能是無法實現的，故本發明方法FFTS仍具有優異的應用價值。
權利要求
基於前置反饋的兩級交換結構工作方法，包含兩級crossbar和三級緩存第一級crossbar之前的輸入緩存、兩級crossbar之間的中間緩存和第二級crossbar之後的重排序緩存；輸入緩存採用VOQ緩衝模式，中間緩存採用雙信元空間的VOQ緩衝模式，重排序緩存採用VIQ緩衝模式；中間埠在每個時槽之初預測本時槽結束時的緩存狀態信息並將其反饋至輸入埠，輸入埠在進行信元傳輸的同時，根據反饋得到的信息選擇下一時槽要轉發的信元，被選中的信元攜帶其理論路逕到達中間緩存等待轉發，信元到達輸出端後根據其所攜帶的理論路徑值完成重排序過程。
2.根據權利要求1所述之基於前置反饋的兩級交換結構工作方法，其特徵在於，中間 緩存任意子隊列緩存容量均設置為兩個信元空間，若且唯若發生信元衝突時才將衝突信元 緩存於第二信元空間。
3.根據權利要求1所述之基於前置反饋的兩級交換結構工作方法，其特徵在於，任意 輸入埠i均設置N個指針Gi,k(k = 0，l，2，…，N-1)，分別指示流Fi,k下一個信元的理論 路徑值；若信元Ci, k被調度算法選中，則將Gi, k和Ci, k組合在一起轉發至中間埠，同時將 Giik更新為(Gu+Dmod Hk到達輸出埠 k後，取出其所攜帶的理論路徑值e並將其緩 存於VIQ(i，e，k)；任意輸出埠 k均設置N個指針PiJi = 0，1，2，…，N-1)分別指示流 Fi,,的下一個信元所應到達的VIQ隊列；若Pi,k所指隊列非空，即可將其隊首信元轉發。
全文摘要
本發明公開了一種基於前置反饋的兩級交換結構工作方法，輸入緩存採用VOQ緩衝模式，中間緩存採用雙信元空間的VOQ緩衝模式，重排序緩存採用VIQ緩衝模式；中間埠在每個時槽之初預測本時槽結束時的緩存狀態信息並將其反饋至輸入埠，輸入埠在進行信元傳輸的同時，根據反饋得到的信息選擇下一時槽要轉發的信元，被選中的信元攜帶其理論路逕到達中間緩存等待轉發，信元被轉發至輸出端後根據其所攜帶的理論路徑值完成重排序過程。本發明有效拓展了調度算法的時域空間，提高了交換結構的高速交換能力和可擴展性。
文檔編號H04L12/56GK101964747SQ20101027826
公開日2011年2月2日 申請日期2010年9月10日 優先權日2010年9月10日
發明者曾華燊, 申志軍 申請人:西南交通大學