[發(fā)明專利]一種基于矩陣分解的網(wǎng)絡交換調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201310385601.4
• 申請日: 2013-08-30
• 公開（公告）號: CN103475597A
• 公開（公告）日: 2013-12-25
• 發(fā)明（設(shè)計）人: 許渤;張念;楊琦;邱昆
• 申請（專利權(quán)）人: 電子科技大學
• 主分類號: H04L12/861
• 分類號: H04L12/861;H04L12/751;H04L12/721
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平

1.一種基于矩陣分解的網(wǎng)絡交換調(diào)度方法，其特征在于，包括以下步驟：

S1：網(wǎng)絡中輸入模塊和輸出模塊的個數(shù)均為N，根據(jù)業(yè)務流量到達情況，統(tǒng)計得到N階業(yè)務矩陣H_m，其中，m表示業(yè)務矩陣H_m的度并滿足2的冪指數(shù)即m＝2^r；業(yè)務矩陣H_m的每個元素H_m[i,j]表示輸入模塊i連接到輸出模塊j的業(yè)務數(shù)，i,j的取值范圍為0≤i≤N-1,0≤j≤N-1；

S2：采用擴展算法對業(yè)務矩陣H_m進行擴展，得到度為2的P階擴展矩陣M₂，其中，P＝N×m/2；M₂[x,y]表示擴展矩陣M₂中的元素，x,y的取值范圍為0≤x≤P-1,0≤y≤P-1；

S3：采用環(huán)形算法對擴展矩陣M₂進行矩陣分解，分解得到兩個P階分解矩陣此時分解矩陣個數(shù)K＝2；

S4：采用壓縮算法分別對K個P階分解矩陣k＝1,2,…,K進行壓縮，得到K個度為2的P/2階壓縮矩陣

S5：再次采用環(huán)形算法對K個壓縮矩陣中的每個壓縮矩陣分別進行矩陣分解，得到2K個壓縮矩陣

S6：判斷分解矩陣的階數(shù)P/2是否等于業(yè)務矩陣階數(shù)N，如果等于，矩陣分解結(jié)束，得到網(wǎng)絡交換調(diào)度的連接矩陣如果不等于，令P＝P/2，K＝2K，返回步驟S4。

2.根據(jù)權(quán)利要求1所述的網(wǎng)絡交換調(diào)度方法，其特征在于，所述步驟S2中擴展算法包括：

S2.1：業(yè)務矩陣H_m的每行、每列對應一個標志數(shù)R_i、L_j，初始化所有標志數(shù)為0；擴展矩陣M₂的每行、每列對應一個計數(shù)器初始化所有計數(shù)器為0；初始化擴展矩陣M₂中每個元素M₂[x,y]；

S2.2：逐行逐列遍歷業(yè)務矩陣H_m中的每個元素H_m[i,j]，如果H_m[i,j]為零值，進入步驟S2.6，如果H_m[i,j]為非零值，進入步驟S2.3；

S2.3：令判斷計數(shù)器是否等于2，如果不是，不作任何操作，如果是，標志數(shù)R_i＝R_i+1并更新x；同時判斷計數(shù)器是否等于2，如果不是，不作任何操作，如果是，標志數(shù)L_j＝L_j+1并更新y；進入步驟S2.4；

S2.4：令M₂[x,y]＝M₂[x,y]+1，更新計數(shù)器H_m[i,j]＝H_m[i,j]-1；

S2.5：判斷H_m[i,j]是否為0，如果不為0，重復步驟S2.3；如果為0，進入步驟S2.6；

S2.6：判斷業(yè)務矩陣H_m的元素是否遍歷完畢，如果沒有遍歷完畢，則返回步驟S2.2遍歷下一元素，如果遍歷完畢，則業(yè)務矩陣擴展結(jié)束。

3.根據(jù)權(quán)利要求1或2所述的網(wǎng)絡交換調(diào)度方法，其特征在于，所述步驟S4中的壓縮算法的具體方法為：將分解矩陣按兩行兩列進行分塊，得到P/2階的分塊矩陣，將分塊矩陣中的每個子矩陣替換為子矩陣中所有元素的和，得到P/2階壓縮矩陣