一種負載均衡分組交換結構及其構造方法
2023-06-02 13:10:06 2
專利名稱：一種負載均衡分組交換結構及其構造方法
技術領域：
本發明涉及通信技術領域，尤其涉及一種負載均衡分組交換結構及其構造 方法。
背景技術：
電信應用中，所謂的交換結構是一種網絡設備，該設備實現數據單元的路 徑選擇，並將數據單元發送到下一個目標地址。由於交換結構的內部容量是有限的，因此，當到達交換結構的流量不均衡 時，會出現有些埠或者內部線路已經處於飽和狀態，而有些埠或者內部線 路卻仍處於空閒狀態的情況。為了避免上述不均衡狀態的出現， 一般採用負載 均衡交換結構來均衡到達的流量。該結構使流量的分布在交換結構內部處於均 衡狀態，即交換結構的埠和各個內部線路的利用率相同。這樣便可以最大限 度的提高交換結構的吞吐量，降低交換結構內部的阻塞。負載均衡Birkhoff-von Neumann交換結構恰好能夠解決交換結構內部阻塞 的問題。如圖1所示，負載均衡Birkhoff-von Neumann交換結構包含兩級縱橫式負載 均衡(Load-balancing)交換、伯克霍夫-馮諾伊曼(Birkhoff-vonNeumann switch)交換和一個處於兩級之間的虛擬輸出隊列VOQ(virtual output queue)。 第一級交換完成負載均衡，第二級交換完成數據分組交換。由於交換結構兩級 的連接方式是確定和周期性的，所以不需要任何輸入輸出埠間的調度。連接 模式的選擇必須要求在每一個連續的W個時間間隙，每個輸入端都要和每個輸 出端恰好連接一次。可見，上述的負載均衡交換結構解決了交換結構數據阻塞 的問題。但是，在每個輸入埠，由於業務流量是不相同和不均衡的，於是不同流 所含有的數據分組的數量也是不同的，這就使得中間級虛擬輸出隊列VOQ的長度不同。又由於隊列服務是獨立於各自長度的，因此，上述負載均衡交換機 構又出現了隊列排隊延遲，數據分組亂序的問題。而分組亂序傳輸可能導致TCP (Transmission Control Protocol傳輸控制協議快速恢復，使得TCP滑動窗 口減半，端到端的吞吐量也會減半。發明內容為此，本發明所要解決的技術問題是提供一種負載均衡分組交換結構及 其構造方法，使得負載均衡Birkhoff-von Neumann交換結構能夠解決分組亂序 的問題，提高端到端的吞吐量。於是，本發明提供了一種負載均衡分組交換結構的構造方法，該方法包括將基於自路由集線器的負載均衡分組交換結構分成具有完成負載均衡功 能的第一級交換模塊和具有完成分組自路由轉發功能的第二級交換模塊；在所述第一級交換模塊輸入端前設置虛擬輸出群組隊列，在所述第二級交 換模塊輸出端後設置重排序緩存，所述虛擬輸出群組隊列，用於存儲帶有自路 由地址信息的分組悽t據塊，所述重排序緩存，用於將屬於同一個輸入群組的分 組數據塊按自路由地址信息排列，以j更後續處理；所述虛擬輸出群組隊列存儲的分組發送到第 一級交換前，組合成預置長度 的數據塊，然後被分割成等長的數據片，同時在數據片上添加用於實現自路由 的自路由標籤；擁有自路由標籤的數據片經第一級交換模塊和第二級交換模塊傳輸後到 達目的輸出埠的重排序緩存，根據數據片攜帶的自路由標籤，把數據片重新 組合成所述虛擬輸出群組隊列組合成的數據塊。其中，在所述第一級交換模塊和第二級交換模塊之間設置中間線群組。其中，所述基於自路由集線器的負載均衡分組交換結構採用分布式自路由。本發明還提供一種負載均衡分組交換結構，包括基於自路由集線器用於完 成負載均衡功能的第一級交換模塊和用於完成分組數據自路由轉發功能的第二級交換模塊，其中，在所述第一級交換模塊輸入端前設置虛擬輸出群組隊列， 在所述第二級交換模塊輸出端後設置重排序緩存，所述虛擬輸出群組隊列，用 於存儲帶有自路由地址信息的分組數據塊，所述重排序緩存，用於將屬於同一 個輸入群組的分組數據塊按自路由地址信息排列，以便後續處理，所述第一級 交換和第二級交換之間為中間線群組連接。可見，通過將基於自路由集線器的負載均衡分組交換結構分成第一級交換 模塊和第二級交換模塊，在第一級交換模塊輸入端前設置虛擬輸出群組隊列， 在第二級交換模塊輸出端後設置重排序緩存，並在所述虛擬輸出群組隊列存儲 的分組發送到第一級交換前，將分組組合成預置長度的數據塊，然後被分割成 等長的數據片，同時在數據片上添加用於實現自路由的自路由標籤，在重排序 緩存中，根據數據片攜帶的自路由標籤，再把數據片重新組合成所述虛擬輸出 群組隊列組合成的數據塊。通過上述結構的變化，可見，本發明提供的負載均 衡分組交換結構取消了背景技術中所述的第一級交換和第二級交換之間的虛擬輸出隊列VOQ這一中間級，使得本發明所述的負載均衡分組交換結構不存 在排隊延遲問題，進而避免了分組亂序。所以，本發明解決了負載均衡 Birkhoff-von Neumann交換結構能夠分組亂序的問題，提高端到端的吞吐量。
圖1為現有技術中負載均衡Birkhoff-vonNeumann交換結構示意圖；圖2a為本發明實施例所述多路逕自路由交換結構一般構造方法流程示意圖；圖2b為圖2a所述多路徑N=128 G=8 M=16的多路逕自路由交換結構構造 方法流程示意圖；圖3為本發明實施例所述負載均衡分組交換結構^t型示意圖；圖4為本發明實施例所述算法一示例圖；圖5為本發明實施例所述算法二示例圖。
具體實施方式
下面，結合附圖對本發明進行詳細描述。本發明實施例採用基於自路由集線器的分組交換結構，而該交換結構主要 是利用集線器和線組技術，在可路由多級互連網絡的基礎上來構造。如圖2a所示， 一個MxM可路由的多級互連網絡構成一個基於自路由集線 器的分組交換結構， 一般的，設N=2n , N = MxQM=2m，G=2g,先構造一個 MxM的可路由網絡(通常選擇版圖複雜性最優的分治網絡)。然後將網絡中 各級2x2路由單元替換為2G-to-G自路由群組集線器，把網絡中各級間的連線替 換成G條平行的線束，這樣就建立了一個擁有M個輸出(輸入)群組，每群組 包含G個輸出(輸入)埠的NxN網絡。2G-to-G集線器具有兩組輸入埠和 兩組輸出埠的，兩個輸出組中地址小的稱為O-輸出組和地址大的稱為l-輸出 組；同理，兩個輸入組稱為O-輸入組和l-輸入組。同一個輸出組中的埠是不 用區分的，這是因為對於一個信號而言，交換到同一組中任何一個埠的效果 都是等價的。如圖2b所示，當線束大小G為8時，將線組和16-to-8集線器應用於圖2a所示 的16xl6網絡，就得到了一個128xl28網絡。邏輯上，2G-to-G集線器等同於2x2基本路由單元，因為它每個輸入(輸出) 組中的G個埠的地址是相同的。 一個2G-to-G集線器是指一個2Gx2G的排序 交換模塊，它將2G個輸入信號中地址最大的G個信號交換到具有最大輸出地址 的G個輸出埠 ，並將其餘的G個信號路由到具有最小輸出地址的G個輸出端 ti 。如圖3所示，基於上述構造的自路由集線器的分組交換結構，通過疊加2 個基於自路由集線器的分組交換結構以及在第一級交換模塊前添置虛擬輸出 群組隊列(VOGQ:Virtual Output Group Queuing),在第二級交換模塊後面設置 重排序緩存(RB:Re-sequencingBuffer)便可構造負載均衡的分組交換結構。實際上，第 一級交換模塊起到了負載均衡的作用，它負責將輸入的網絡流 量均勻化後轉送到第二級交換模塊輸入端。之後，通過數據攜帶的自路由標籤， 第二級交換模塊就可利用自路由特性將數據送到最終目的埠。每G個輸入(輸出)埠組成一個輸入(輸出)群組，這樣在交換結構的輸入輸出端各形成了M個群組。交換結構內部共同連接不同集線器的G根內部鏈路也相應組成 一個線群組。為了便於表達，設IGj (OGi)代表一個特定的輸入(輸出)群組, MGi代表前後兩級交換模塊之間的線群組(i=0,l,…M-l )。-水袖ffi野卩入:7'J VULr^逸^i"工f l叫丁乂亞^A糊VOGQ隊列負責存儲來自G個輸入埠的數據，實質上VOGQ由M個虛擬輸出 隊列組成。假定VOGQ (i,j)代表存儲來自輸入群組IGi,目的地為輸出群組OGj 數據的隊列，(i， j=0，l， ...M-l )，同時設當前VOGQ (i，j)隊列長度為Ly，即有 Lij個分組在緩存中等待傳送。一般而言，負載均衡的分組交換結構按時隙為單位進行調度，每時隙對分 組的處理可大致分為以下幾個連續階段，並且應儘可能以流水線方式運行來加 快處理速度1) 到達階段新的分組在此階段到達輸入端IGs.其中到達輸入群組IGi去往輸 出群組OGj的分組被存儲於VOGQ (i，j)隊列中2) 封裝階段存儲於VOGQ中的分組首先被組合成最大長度一定的數據塊(datablock)。然後根據算法l，這些數據塊將在分割和打標籤後成為小的 數據片(dataslice),並等待進一步傳輸。參見圖3中的數據片格式(a)。3) 均衡階段通過使用MG自路由標籤，所有輸入群組IG同時將封裝後的數 據片送到兩級間的線群組。當^L據片到達中間線群組後，MG地址將作為 MG籤重新插入到IG標籤與數據負載之間。參見圖3中的數據片格式(J3)。4) 轉發階段數據片將進一步使用OG標籤自路由地穿越第2級轉發模塊，並 最終到達其預期的輸出群組。當數據片到達輸出端OGs的重排序緩存RB時， OG標籤將被丟棄。參見圖3中的數據片格式(Y)。5) 離開階段在重排序緩存RB中，根據算法1被分割的數據塊將使用算法2進 行重組，並離開交換結構的輸出端。下面，針對所述算法1和算法2進行詳細說明。算法l:對於每一個輸入群組IQ在封裝階^:，存儲於VOGQ 的數據塊首先 被均勻地切割成M個等長的數據片，即為圖3中標記出的負載。之後，自路由 標籤MG、 IG和OG被插入到相應數據片之前，以供穿越兩級結構路由時使用。 其中MG將按從小到大的順序依次插入到特定VOGQ所對應的M份數據片前。為了便於理解，下面列出了算法1對應的C語言偽代碼，圖4則給出了當 M-8, IGs上的VOGQ滿足L5，。-4，L5,i-2,L5，6-L5，產l時的具體例子。/*算法1偽代碼，M為總的群組數"DataBlock[M][M]; DataBlock(id)為VOGQ(i,j)內存儲的數據塊"SlicePayload[M][M][M];SlicePayload(g,k)代表DataBlock(i，j)分割後的 數據片負載*/DataSlice[M][M][M]; DataSlice(i,j,k)代表力。標記後的數據片*/IG[M]={0, 1,2,3,…，M-1}; OG[M]={0, 1,2,3,…，M-1}; MG[M]={0， 1,2,3,…，M-1}; /* IQOGMG數組存儲了自路由標籤*/for(i=0;i<M;i++)/*對每個輸入群組進行處理，實現時輸入群組間並行運行*/for(j=0;j<M;j++){Segment(DataBlock[i][j]);嚴將數據塊均勻分割為M份負載，生成未 加自路由標籤的數據片SlicePayload */for (k=0;k<M;k++)AddTag(SlicePayload[i][j][k],IG[i],OG[j],MG[k]); /*為切割後的負載依次加標籤，生成數據片DataSlice(i，j,k)*/圖4中，對於輸入群組IG5，在封裝階段，存儲於VOGQ(5j)的數據塊首 先被均勻地切割成M-8個等長數據片。之後，自路由標籤MCUG和OG被插入 到數據片之前。對於VOGQ (5，j) ，8個數據片的IG-5,(XH,而MG則按0到7 依次編號。這樣便將輸入端去往某輸出群組的流量均勻地導出到所有輸出群 組。算法2:具有相同IG標籤的數據片被重組在一起，MG標籤將用於按順序將數據塊 復原。然後將數據塊按分組大小重新切割為分組。處理後的分組就可被送離輸 出埠。如圖5所示，算法2的C語言偽代碼如下 /*算法2偽代碼，M為總的群組數"DataBlock[M][M]; /*DataBlock(i j)為VOGQ(i j)內存儲的數據塊*/SlicePayload[M][M][M];嚴SlicePayload(i，j，k)代表DataBlock(i,j)分割後的 數據片負載*/DataSlice[M][M][M]; 嚴DataSlice(i,j,k)代表加標籤後的數據片*/ IG[M]={0， 1 , 2 ， 3 ，…，M-1}; OG[MH0， 1 ， 2 ， 3 ，…，M-1}; MG[M]-{0， 1 , 2 ， 3 ,…，M-1}; /* IQOGMG數組存儲了自路由標籤*/for(j=0;j<M;j++)/*對每個輸出群組進行處理，實現時輸出群組間並行運formula see original document page 10嚴去除DataSlice的自路由標籤IQMG,還原成未加標籤的SlicePayload; OG 標誌已在自路由過程中去除，見圖3格式f/Recover(DataBlock(i,j)， SlicePayload(i，j,k));/*將數據片負載SlicePayload(i，j，k)按k從小到大依次組合，最終恢復 DataBlock(ij)*//*數據塊恢復完成，按分組大小重新分割後可離開交換結構輸出端*/圖5中，根據算法2，在每個輸出群組OG上，我們首先搜集同屬輸入群組 IGs的數據片，然後根據數據片的MG標籤，從小到大依次將這些數據片組合起 來。去除多餘的自路由標籤後，我們就復原了數據塊。再將這些數據塊按分組 大小切割後，就可將它們送出輸出埠了。我們在負載均衡的分組交換結構輸入端前置的VOGQ中對去往每個輸出 埠的分組進行封裝切割，在輸出的後置的重排序緩存中對這些經過切割的數 據片進行重排序。由於交換結構的輸出埠為M，即需要把分組組合成數據塊 然後平均切割成M個數據片，而一個2G-to-G自路由集線器的組大小為G，於是 M和G的大小關係影響著分組組合封裝和輸出的方法。本實施例給出M和G的 三種關係的封裝和傳輸方法。1)M=G:這種情況最簡單。交換結構的兩個輸入群組連接到一個2G-to-G自路由群組集線器，而2G-to-G自路由集線器的規模是2Gx2G。在封裝的時候，把 VOGQ的某一個虛擬輸出隊列的一個數據塊切割成了M個數據片，於是一個 2G-to-G自路由群組集線器的每個輸入端有M個數據片。由於M-G,所以對每 個VOGQ的某一個虛擬輸出隊列進行封裝切割而成的M個數據片可以在一個 時隙全部送到輸入端。由於交換結構中間沒有緩存，於是這M個數據片在交換 結構中經過相同的傳輸延遲，同一個時隙到達輸出埠後置的重排序緩存，從 而根據自路由標籤重新組合成沒有切割的數據塊，然後送到輸出端的線卡上。 由於G個輸入的數據分組根據輸出埠地址分別存放到VOGQ相應的隊列中， 而輸出埠有M個，於是一個輸入群組的前置VOGQ實際上有M個虛擬輸出隊 列組成。這樣每經過M個時隙，VOGQ的每一個虛擬輸出隊列就可以發送一次 數據分組。2) M〈G:由於lV^2m，G-2g，於是G是M的2X倍(x為正整數)。由於VOGQ的每個 虛擬輸出隊列的一個數據塊被封裝切割成了M個數據片，而一個2G-to-G的規 模是2Gx2G,如果每次只傳輸VOGQ的某一個虛擬輸出隊列，則只使用了自路 由集線器的2M個輸入(或者輸出)埠，而自路由集線器共有2G個輸入(或 者輸出)埠。為了充分利用自路由集線器的路由交換能力，我們對每個VOGQ 的2X個虛擬輸出隊列進行封裝切割，這樣一個自^^由集線器的兩個輸入端共輸 入2x2XxM-2G個數據片。這樣每經過M/2X個時隙，VOGQ的每一個虛擬輸出隊 列就可以發送一次數據分組。3) M〉G:由於M-2,G-2g,於是M是G的2X倍(x為正整數)。由於VOGQ的每個 虛擬輸出隊列的一個數據塊被封裝切割成了M個數據片，如果每次封裝傳輸 VOGQ的一個虛擬輸出隊列，則一個自路由集線器的兩個輸入端共產生2M個 數據片，而一個2G-to-G的規模是2Gx2G，這樣便超過了自路由集線器的路由 交換能力。為了解決這個問題，我們把M個數據片分成2X個部分，這樣每個部 分有G個數據片。同時為了防止負載均衡模塊內部的阻塞，我們把負載均衡交 換結構的輸入組也分成2X個部分，這樣每部分有G個輸入組。在一個時隙中， 一個輸入組部分的G個輸入組分別向O至(G-l )， G至(2G-1)，…，(M-l-G) 至(M-l)輸出組發送數據，這樣2X個時隙便完成了一個輪轉，即VOGQ的一個虛擬輸出隊列完成了一次數據發送。於是每經過2XxM個時隙，VOGQ中的 每一個虛擬輸出隊列完成一次數據的傳輸。由於本發明實施例中的交換結構採用基於自路由集線器的分組交換結構， 而這種結構可以遞歸構造，於是這個負載均衡交換結構的少見模不受限制。同時 該交換結構是完全分布式的自路由，也為該負載均衡交換結構的大規模實現提 供了技術和物理上的基礎。綜上所述，通過將基於自路由集線器的負載均衡分組交換結構分成第一級 交換模塊和第二級交換模塊，在第一級交換模塊輸入端前設置虛擬輸出群組隊 列，在第二級交換模塊輸出端後設置重排序緩存，並在所述虛擬輸出群組隊列 存儲的分組發送到第一級交換前，將分組組合成預置長度的數據塊，然後被分 割成等長的數據片，同時在數據片上添加用於實現自路由的自路由地址信息， 在重排序緩存中，根據數據片攜帶的自路由地址信息，再把數據片重新組合成 所述虛擬輸出群組隊列組合成的數據塊。通過上述結構的變化，可見，本發明 實施例提供的負載均衡分組交換結構取消了背景技術中所述的第一級交換和 第二級交換之間的虛擬輸出隊列VOQ這一中間級，使得本發明實施例所述的 負載均衡分組交換結構不存在排隊延遲問題，進而避免了分組亂序。所以，本 發明實施例解決了負載均衡Birkhoff-von Neumann交換結構能夠分組亂序的問 題，提高端到端的吞吐量。通過將基於自路由集線器的負載均衡分組交換結構分成第一級交換模塊 和第二級交換模塊，在第一級交換模塊輸入端前設置虛擬輸出群組隊列，在第二級交換模塊輸出端後設置重排序緩存，並在所述虛擬輸出群組隊列存儲的分 組發送到第一級交換前，將分組組合成預置長度的數據塊，然後被分割成等長 的數據片，同時在數據片上添加用於實現自路由的自路由標籤，在重排序緩存 中，根據數據片攜帶的自路由標籤，再把數據片重新組合成所述虛擬輸出群組 隊列組合成的數據塊，解決了負載均衡Birkhoff-vonNeumann交換結構能夠分 組亂序的問題，提高端到端的吞吐量。以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發 明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發 明的保護範圍之內。
權利要求
1、一種負載均衡分組交換結構的構造方法，其特徵在於，包括將基於自路由集線器的負載均衡分組交換結構分成具有完成負載均衡功能的第一級交換模塊和具有完成分組自路由轉發功能的第二級交換模塊；在所述第一級交換模塊輸入端前設置虛擬輸出群組隊列，在所述第二級交換模塊輸出端後設置重排序緩存，所述虛擬輸出群組隊列，用於存儲帶有自路由地址信息的分組數據塊，所述重排序緩存，用於將屬於同一個輸入群組的分組數據塊按自路由地址信息排列，以便後續處理；所述虛擬輸出群組隊列存儲的分組發送到第一級交換前，組合成預置長度的數據塊，然後被分割成等長的數據片，同時在數據片上添加用於實現自路由的自路由標籤；擁有自路由標籤的數據片經第一級交換模塊和第二級交換模塊傳輸後到達目的輸出埠的重排序緩存，根據數據片攜帶的自路由標籤，把數據片重新組合成所述虛擬輸出群組隊列組合成的數據塊。
2、 根據權利要求l所述的方法，其特徵在於，在所述第一級交換模塊和第 二級交換模塊之間設置中間線群組。
3、 根據權利要求1或2所述的方法，其特徵在於，所述基於自路由集線器 的負載均衡分組交換結構採用分布式自路由。
4、 一種負載均衡分組交換結構，包括基於自路由集線器用於完成負載均 衡功能的第一級交換模塊和用於完成分組數據自路由轉發功能的第二級交換 模塊，其特徵在於，在所述第一級交換模塊輸入端前設置虛擬輸出群組隊列， 在所述第二級交換模塊輸出端後設置重排序緩存，所述虛擬輸出群組隊列，用 於存儲帶有自路由地址信息的分組數據塊，所述重排序緩存，用於將屬於同一 個輸入群組的分組數據塊按自路由地址信息排列，以便後續處理，所述第一級 交換和第二級交換之間為中間線群組連接。
全文摘要
本發明提供了一種負載均衡分組交換結構及其構造方法，其中，所述構造方法包括將基於自路由集線器的負載均衡分組交換結構分成第一級交換模塊和第二級交換模塊；在第一級交換模塊輸入端前設置虛擬輸出群組隊列，在第二級交換模塊輸出端後設置重排序緩存，在虛擬輸出群組隊列存儲的分組發送到第一級交換前，將分組組合成預置長度的數據塊，然後再分割成等長的數據片，同時添加自路由標籤，傳輸後到達重排序緩存後，再把數據片重新組合成所述數據塊。本發明所述種負載均衡分組交換結構及其構造方法，解決了負載均衡Birkhoff-von Neumann交換結構的分組亂序的問題，提高了端到端的吞吐量。
文檔編號H04L12/56GK101404616SQ20081021726
公開日2009年4月8日 申請日期2008年11月4日 優先權日2008年11月4日
發明者鵬 伊, 偉 何, 張書鑫, 揮 李, 李碩彥, 汪斌強, 凱 潘, 建 陳, 黃佳慶 申請人:北京大學深圳研究生院;上海北京大學微電子研究院;李 揮