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

有效

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

技術(shù)領(lǐng)域

本發(fā)明屬于網(wǎng)絡(luò)交換調(diào)度技術(shù)領(lǐng)域，更為具體地講，涉及一種基于矩陣分解的網(wǎng)絡(luò)交換調(diào)度方法。

背景技術(shù)

多級(jí)交換結(jié)構(gòu)能提供更多的交換接口滿足大量用戶接入，提供更高的帶寬滿足用戶服務(wù)質(zhì)量，已成為了大容量交換結(jié)構(gòu)的首選。多級(jí)多平面（Multi-Plane?and?Multi-Stage，MPMS）結(jié)構(gòu)，屬于多級(jí)交換結(jié)構(gòu)的特例，是對(duì)多級(jí)交換結(jié)構(gòu)的中間模塊擴(kuò)展為交換平面而來。圖1是MPMS交換結(jié)構(gòu)示意圖。平面內(nèi)部可以是單級(jí)空分交換結(jié)構(gòu)，也可以是多級(jí)交換結(jié)構(gòu)。根據(jù)到達(dá)流量是否已知，交換調(diào)度算法分為兩種不同的處理方式。若到達(dá)流量未知，可以將調(diào)度抽象為二分圖匹配問題并使用二分圖匹配算法來解決。若到達(dá)流量已知，可以使用矩陣分解算法。

為了更好的說明矩陣分解算法，首先定義幾個(gè)名詞概念。

定義1：矩陣的度：矩陣中每行元素之和與每列元素之和的最大值m是矩陣的度。假設(shè)有A×B的矩陣Matrix[i,j]，0≤i≤A-1,0≤j≤B-1，矩陣Matrix[i,j]的度即為maxi(Σj=0B-1Matrix[i,j])]]>和maxj(Σi=0A-1matrix[i,j])]]>兩者中的較大值。

定義2：業(yè)務(wù)矩陣H_m，其中每個(gè)元素H_m[i,j]，0≤i,j≤N-1，表示輸入模塊序號(hào)i連接到輸出模塊序號(hào)j的業(yè)務(wù)數(shù)，m表示業(yè)務(wù)矩陣的度，即中間級(jí)模塊個(gè)數(shù)，代表多級(jí)交換結(jié)構(gòu)中最大可支持的業(yè)務(wù)數(shù)量；N表示輸入/輸出模塊的個(gè)數(shù)。可見，業(yè)務(wù)矩陣中的元素H_m[i,j]的值僅能從0，1，2......m-1，m中選一個(gè)。對(duì)于MPMS而言，中間級(jí)模塊指的是交換平面。

定義3：連接矩陣1≤k≤m，其中每個(gè)元素0≤i,j≤N-1，代表輸入模塊i是否有業(yè)務(wù)經(jīng)過中間級(jí)模塊k連接到輸出模塊j，其元素值為1代表有連接，元素值為0代表無連接。其中下標(biāo)1表示連接矩陣的度，即每個(gè)中間級(jí)模塊k中每個(gè)輸入模塊到每個(gè)輸出模塊最多只存在一個(gè)業(yè)務(wù)。

矩陣分解算法的基本思想是在統(tǒng)籌全局業(yè)務(wù)到達(dá)情況下，對(duì)業(yè)務(wù)進(jìn)行的一次統(tǒng)一路由分配。首先根據(jù)到達(dá)的全局業(yè)務(wù)情況，統(tǒng)計(jì)得出一個(gè)業(yè)務(wù)矩陣H_m。矩陣分解算法的目標(biāo)是對(duì)全局業(yè)務(wù)一次統(tǒng)一路由分配，即把業(yè)務(wù)矩陣H_m分解成為m個(gè)子矩陣E₁，由Hall定理可得知，在無阻塞交換結(jié)構(gòu)中，矩陣分解算法一定能分解出所有的子矩陣。屬于無阻塞交換結(jié)構(gòu)有：?jiǎn)渭?jí)Crossbar（交叉開關(guān)矩陣），多級(jí)MPMS、Banyan（榕樹網(wǎng)絡(luò)）、Bense、Clos等，均可采用矩陣分解算法進(jìn)行路由分配。以MPMS為例，如圖1所示，MPMS路由調(diào)度的第一步就是把輸入端到達(dá)的業(yè)務(wù)均勻下發(fā)到各個(gè)平面。矩陣分解算法對(duì)業(yè)務(wù)矩陣分解得到各個(gè)子矩陣，其中每個(gè)子矩陣就可以作為MPMS中每個(gè)平面的路由設(shè)置依據(jù)。