一種雙向交換調度方法

2023-07-18 05:16:16

一種雙向交換調度方法
【專利摘要】本發明公開了一種適用於多級多平面結構網絡的同向交換調度方法，在度為2的滿配業務矩陣中，逐行遍歷各個元素，將第一次找到的非零值1的元素作為起點，分別在該元素的行方向和列方向尋找非零值1，在找到的兩個非零值1中，分別在同行非零值1的列方向、同列非零值1的行方向尋找非零值1，在本次找到的兩個非零值1中，在同列非零值1的行方向、同行非零值1的列方向尋找非零值1，依次類推。每次找到非零值元素時，則更新連接矩陣的業務矩陣中的相應元素，直到將業務矩陣中所有非零值元素處理完畢。本發明中，在確定起點後的每個步驟可以返回兩條業務分配結果，從而將業務矩陣的分配時間縮短為現有單向環形算法的一半左右。
【專利說明】—種雙向交換調度方法
【技術領域】
[0001]本發明屬於網絡交換調度【技術領域】，更為具體地講，涉及一種基於環形算法的雙向交換調度方法。
【背景技術】
[0002]多級多平面(Mult1-Plane and Mult1-Stage，MPMS)結構網絡是目前一種常用的交換網絡結構。圖1是MPMS結構網絡示意圖。如圖1所示，MPMS結構網絡包括輸入模塊、交換平面和輸出模塊，交換平面即輸入模塊和輸出模塊之間的中間級模塊。在MPMS結構網絡的交換調度中，環形算法是一種常用的交換調度算法。
[0003]為了更好地說明環形算法，首先定義幾個名詞概念:
[0004]定義1:矩陣的度:矩陣中每行元素之和與每列元素之和的最大值m是矩陣的度。假設有AXB的矩陣Matrix[i，j]，0≤i≤A-1，O ^ j ^ B_l，矩陣Matrix[i，j]的度即為
【權利要求】
1.一種雙向交換調度方法，其特徵在於包括以下步驟: 51:對於度為2的業務矩陣H2，將其中各個元素記為H2 [i，j]，i和j的取值範圍分別為O≤i≤N-1、0≤j≤N-1，N表示輸入/輸出模塊；初始化所有連接矩陣.丨'/；:] = 1，￡?[,.:，/J = I，HJi1J2] = O, HJi2J1] =0,進入步驟 S4; 54:在元素HJi1, j2]所在的第j2列和H2[i2，jj所在的第「行同時尋找是否存在非零值1，如果未找到則返回步驟S2，若找到元素H2 [i3，j2]和H2[i2，j3]，則更新連接矩陣和業務矩陣相應元素:￡；'[/.—」./.:]= I，￡，:[/'/.—;] = 1，H2[i3, j2] = O, H2[i2, j3] = 0,判斷元素H2[i3, j2]和4[「，j3]是否為同一元素，如果不是進入步驟S5，否則返回步驟S2 ； 55:在元素H2[i3，j2]所在的第i3行和H2[i2，j3]所在的第九列同時尋找是否存在非零值1，如果未找到則返回步驟S2，若找到元素H2 [i3，j4]和H2[i4，j3]，則更新連接矩陣和業務矩陣相應元素:Ε[[?,, /4] = ?, ￡丨][/4,./.;] = 1，H2[i3, jj = O, H2 [i4, j3] = 0,判斷元素H2 [i3, jj H2 [i4, j3]是否為同一元素,如果不是則令 h = i3、i2 = i4> ji = j3、j2 = j4，返回步驟S4，否則返回步驟S2。
【文檔編號】H04L12/931GK103944840SQ201410157917
【公開日】2014年7月23日 申請日期:2014年4月17日 優先權日:2014年4月17日
【發明者】楊琦, 張念, 邱昆, 許渤 申請人:電子科技大學