張方爽　段新明

摘 要：最壞情況的吞吐率是衡量路由算法性能的重要因素之一。負(fù)載最重的地方是最壞情況吞吐率的體現(xiàn)，因此最壞情況的吞吐率在路由算法中很關(guān)鍵。在此基礎(chǔ)上本文提出了通過(guò)利用匈牙利算法來(lái)評(píng)估網(wǎng)絡(luò)負(fù)載的方法并且通過(guò)實(shí)驗(yàn)仿真進(jìn)行比較。將匈牙利算法和窮舉法運(yùn)用到Oblivious路由中的O1TURN、VAL等算法中進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明運(yùn)用該方法與利用傳統(tǒng)的窮舉法相比，可以大大減少計(jì)算量、降低時(shí)間復(fù)雜度，實(shí)驗(yàn)結(jié)果證明了方法的可行性和有效性。

關(guān)鍵詞：匈牙利算法；最壞情況吞吐率；Oblivious路由；窮舉法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

路由算法是決定網(wǎng)絡(luò)性能重要因素之一，最壞情況的吞吐率是衡量路由算法的重要指標(biāo)。通過(guò)隨機(jī)選擇路由路徑網(wǎng)絡(luò)傳輸過(guò)程中故障節(jié)點(diǎn)繞道路由問(wèn)題，以及自適應(yīng)網(wǎng)絡(luò)選擇路由的路徑問(wèn)題，負(fù)載最重的地方是最壞情況吞吐率的體現(xiàn)，因此最壞情況的吞吐率在路由算法中很關(guān)鍵[1，2]。本文通過(guò)利用匈牙利算法的思想計(jì)算網(wǎng)絡(luò)吞吐率的負(fù)載。利用Oblivious路由功能的線性，找到最壞情況的流量模式被視為二分圖的最大權(quán)重匹配。使用這種結(jié)構(gòu)，問(wèn)題通常在多項(xiàng)式時(shí)間內(nèi)解決，快速產(chǎn)生確切的最壞情況結(jié)果。使用最壞情況來(lái)確定特定系統(tǒng)的最壞情況吞吐。William J.Dally等人提出將匈牙利算法運(yùn)用到Oblivious路由中的DOR和ROMM中評(píng)估吞吐率[3]，在此基礎(chǔ)上本文引入擴(kuò)展到Oblivious路由的O1TURN等算法中[1，4]。

2 相關(guān)知識(shí)（Related information）

匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性證明的思想，它是二分圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。用于為任意網(wǎng)絡(luò)拓?fù)渖系穆酚晒δ苷业酱_切的最壞情況模式。

網(wǎng)絡(luò)負(fù)載對(duì)性能有很大的影響。一般而言，對(duì)于給定目的節(jié)點(diǎn)的分布，網(wǎng)絡(luò)負(fù)載對(duì)網(wǎng)絡(luò)平均消息延遲的影響比其他設(shè)計(jì)參數(shù)的影響大很多，因此需要合理的選擇這些參數(shù)。而且，吞吐率主要受通信模式也就是目的節(jié)點(diǎn)的影響。因此，計(jì)算網(wǎng)絡(luò)負(fù)載時(shí)非常重要。

由于網(wǎng)絡(luò)通道不飽和，可以利用通道負(fù)載的線性相關(guān)。線性意味著特定通道上的負(fù)載僅僅是每對(duì)源節(jié)點(diǎn)到目的節(jié)點(diǎn)引起的負(fù)載的總和。實(shí)際上這個(gè)可以將最壞情況模式搜索限制為置換矩陣。然后，通過(guò)將所有置換矩陣表示為單個(gè)二分圖內(nèi)的匹配，并且用源節(jié)點(diǎn)到目的節(jié)點(diǎn)通道負(fù)載的邊進(jìn)行加權(quán)，則最大權(quán)重匹配產(chǎn)生特定通道及其相應(yīng)負(fù)載的確定最壞情況的置換排列。最后，在網(wǎng)絡(luò)中所有通道的集合上重復(fù)以找到最差情況下，最大權(quán)重匹配的理想吞吐量[1，3]。

Oblivious路由算法是一種在進(jìn)行路由決策時(shí)，不考慮網(wǎng)絡(luò)的狀態(tài)，具有較高的靈活性。評(píng)估Oblivious路由算法的最壞情況吞吐率的關(guān)鍵是利用算法通道負(fù)載線性的特性。也就是說(shuō)，只要網(wǎng)絡(luò)的通道不飽和，特定通道c上的負(fù)載就是每對(duì)源節(jié)點(diǎn)到目的節(jié)點(diǎn)在流量模式中的所有負(fù)載的總和[3]：

其中，流量矩陣（Λ）：任意雙隨機(jī)矩陣，其中入口λi，j表示從源i到目的j的通道流量；遺忘路由算法（π）：一種路由算法；通道負(fù)載（γc（π，Λ））：流量矩陣Λ和路由選擇函數(shù)π在每個(gè)周期信道c的分組數(shù)量。

定理1：對(duì)于任何Oblivious的路由算法，置換矩陣總能實(shí)現(xiàn)理想的最壞情況吞吐量。在論文[3]中已得到了證明。

在窮舉法中找到最壞情況的負(fù)載，就要考慮所有的置換排列。時(shí)間復(fù)雜度為O（N?。且粋€(gè)NP難問(wèn)題，計(jì)算量很大。為此文本利用匈牙利算法計(jì)算最壞情況的吞吐率。大大降低了時(shí)間復(fù)雜度，提高算法的效率[2]。

3 算法模式（Algorithm mode）

3.1 窮舉法算法模式

（1）初始化數(shù)組；

（2）利用遞歸找出所有情況的排列；

（3）找到最后的結(jié)果。

3.2 匈牙利算法的基本模式

由于任何特定的置換，使用Oblivious路由算法的線性特性，二分圖可用于表示單個(gè)通道上的負(fù)載。二分圖匹配的最大流算法的核心算法是找增廣路徑（augment path）其基本模式如下：

（1）初始時(shí)最大匹配為空；

（2）while找得到增廣路徑。

do把增廣路徑加入到最大匹配中。

引理1：如果從一個(gè)點(diǎn)A出發(fā)，沒有找到增廣路徑，那么無(wú)論再?gòu)膭e的點(diǎn)出發(fā)找到多少增廣路徑來(lái)改變現(xiàn)在的匹配，從A出發(fā)都永遠(yuǎn)找不到增廣路徑。

匈牙利算法和最大流算法很相似。不同之處在于增廣路徑就有它一定的特殊性，雖然根本上是最大流算法，但是它不需要建構(gòu)網(wǎng)絡(luò)模型。二分圖最大流的核心算法中找增廣路徑的基本模式及相關(guān)定理，引出匈牙利算法基本模式，其基本模式如下：

（1）初始時(shí)最大匹配為空；

（2）for二分圖左半邊的每個(gè)點(diǎn)i；

（3）do從點(diǎn)i出發(fā)尋找增廣路徑。如果找到，則把它取反（即增加了總了匹配數(shù)）。

如果二分圖的左半邊一共有n個(gè)點(diǎn)，那么最多找n條增廣路徑。如果二分圖中共有m條邊，那么每找一條增廣路徑（DFS或BFS）時(shí)最多把所有邊遍歷一遍，所花時(shí)間也就是m。所以總的時(shí)間復(fù)雜度大概是O（n*m）。

KM（Kuhn-Munkras）算法用來(lái)解決最大權(quán)匹配問(wèn)題的算法。其基本原理：KM算法是通過(guò)給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)（叫做頂標(biāo)）來(lái)把求最大權(quán)匹配的問(wèn)題轉(zhuǎn)化為求完備匹配的問(wèn)題。設(shè)頂點(diǎn)Xi的頂標(biāo)為A[i]，頂點(diǎn)Yj的頂標(biāo)為B[j]，頂點(diǎn)Xi與Yj之間的邊權(quán)為w[i，j]。在算法執(zhí)行過(guò)程中的任一時(shí)刻，對(duì)于任一條邊（i，j），A[i]+B[j]>=w[i，j]始終成立。

KM算法基本模式：

（1）初始化可行頂標(biāo)的值；

（2）用匈牙利算法尋找完備匹配；

（3）若未找到完備匹配則修改可行頂標(biāo)值；

（4）重復(fù)（2）（3）直到找到相等子圖完備匹配為止。

4 網(wǎng)絡(luò)吞吐率評(píng)估（Network throughput evaluation）

使用Oblivious路由算法，對(duì)于任何特定的置換排列，二分圖可用于表示單個(gè)通道上的負(fù)載。如圖1所示，第一組N個(gè)節(jié)點(diǎn)用于表示數(shù)據(jù)的源節(jié)點(diǎn)，第二組N個(gè)節(jié)點(diǎn)表示數(shù)據(jù)的目的節(jié)點(diǎn)。在每對(duì)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間添加邊，從而獲得總共N2個(gè)邊[3]。排列矩陣與二分圖的完美匹配之間存在一對(duì)一對(duì)應(yīng)的關(guān)系。需要注意的是，二分圖的結(jié)構(gòu)與底層互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)無(wú)關(guān)。

源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的每條邊進(jìn)行加權(quán)，使得負(fù)載量給一個(gè)特定的通道c，即。這些權(quán)重由置換引起的負(fù)載量?jī)H為其相應(yīng)二分圖匹配中邊權(quán)重的總和[3-5]如圖1所示。對(duì)于源到目的對(duì)（s，d），用窮舉法列舉出路由算法生成的從s到d的所有路徑，以及包含通道c的每條路徑計(jì)算邊緣權(quán)重，是NP問(wèn)題，時(shí)間復(fù)雜度是O（N?。?。

根據(jù)二分圖的構(gòu)造，可以找到該圖的最大權(quán)重匹配。從匹配和排列之間的對(duì)應(yīng)關(guān)系來(lái)看，找到一個(gè)最大權(quán)重匹配就相當(dāng)于評(píng)估：其中P是所有置換矩陣的集合。通過(guò)在所有通道上重復(fù)該操作，可以確定理想的最差情況吞吐量為[3]：

最大權(quán)重匹配算法存在。窮舉法的時(shí)間復(fù)雜度O（N！），而利用匈牙利算法計(jì)算的時(shí)間復(fù)雜度O（N3）。窮舉法和匈牙利算法在效率上的差別，可以看出，利用匈牙利算法求吞吐率算法的性能是相當(dāng)好的。

5 仿真與分析（Simulation and analysis）

在Mesh網(wǎng)絡(luò)中，對(duì)于Oblivious路由算法論文[3]中對(duì)DOR和ROMM算法進(jìn)行了仿真實(shí)驗(yàn)，本文在此基礎(chǔ)上擴(kuò)展了Oblivious中的O1TURN，以及VAL[3，6]算法中。與DOR相比，源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的所有流量都集中在單一路徑上。ROMM更均勻地將源節(jié)點(diǎn)到目的節(jié)點(diǎn)流量分布在更多數(shù)量的通道上，ROMM選取節(jié)點(diǎn)時(shí)比較靈活。ROMM和VAL與DOR路由算法不同。ROMM和VAL路由算法是將路由路徑分為兩個(gè)階段，第一階段消息從源節(jié)點(diǎn)傳輸?shù)街虚g節(jié)點(diǎn)，在第二階段消息在由中間節(jié)點(diǎn)到達(dá)目的地，它們的區(qū)別在于選取中間節(jié)點(diǎn)方法不同。O1TURN路由算法[1]具有非常結(jié)構(gòu)簡(jiǎn)單，其隨機(jī)使用XY或YX路由算法。O1TURN和VAL路由算法都具有良好的最壞情況網(wǎng)路的吞吐率?；贠blivious的幾種通訊模式[1]，進(jìn)行了仿真實(shí)驗(yàn)的比較，如表1所示。

當(dāng)網(wǎng)絡(luò)規(guī)模比較低的情況下利用傳統(tǒng)的窮舉法和匈牙利算法進(jìn)行實(shí)驗(yàn)仿真得到結(jié)果是一樣的。如表2所示，采用4×4網(wǎng)絡(luò)規(guī)模進(jìn)行實(shí)驗(yàn)，理論和實(shí)驗(yàn)結(jié)果證明了利用窮舉法和匈牙利算法得到結(jié)果是一樣的。但是當(dāng)網(wǎng)絡(luò)的規(guī)模越大時(shí)窮舉法復(fù)雜度成指數(shù)級(jí)增長(zhǎng)，速度很慢，所以無(wú)法驗(yàn)證。

實(shí)驗(yàn)采用以1000為周期的前提下，利用窮舉法和匈牙利算法在不同的網(wǎng)絡(luò)模式時(shí)間效率的比值（運(yùn)行時(shí)間單位：ms）。實(shí)驗(yàn)以網(wǎng)絡(luò)模式為2×2、3×3，以及4×4進(jìn)行比較，如表3結(jié)果所示。

表3的結(jié)果分析可知，網(wǎng)絡(luò)模式越大時(shí)，傳統(tǒng)的窮舉法與匈牙利算法的時(shí)間效率比值成指數(shù)級(jí)別增長(zhǎng)。從實(shí)驗(yàn)結(jié)果可知很明顯利用匈牙利算法極大的改善了運(yùn)行時(shí)間的效率。采用窮舉法的時(shí)間復(fù)雜度是O（N?。?，而采用匈牙利算法的時(shí)間復(fù)雜度是O（N3）。當(dāng)隨著網(wǎng)絡(luò)規(guī)模增加時(shí)傳統(tǒng)的窮舉法復(fù)雜度會(huì)越來(lái)越高，速度很慢。利用匈牙利算法評(píng)估網(wǎng)絡(luò)吞吐率可以有效的改善計(jì)算的運(yùn)行速度、提高效率。

6 結(jié)論（Conclusion）

利用匈牙利算法我們可以在多項(xiàng)式時(shí)間內(nèi)找到Oblivious的路由算法的最壞情況吞吐量，這使得最壞情況的分析變得易于處理。二分圖構(gòu)造來(lái)分析Oblivious路由算法是評(píng)估最壞情況下網(wǎng)絡(luò)吞吐率的一個(gè)方法。對(duì)比窮舉法，計(jì)算最壞情況下的吞吐率時(shí)間效率得到很大改善；在時(shí)間復(fù)雜度上，窮舉法的時(shí)間復(fù)雜度是O（N?。?，而利用匈牙利算法的時(shí)間復(fù)雜度是O（N3）。實(shí)驗(yàn)通過(guò)利用Oblivious路由算法中O1TURN等算法，以及運(yùn)行時(shí)間的對(duì)比，證明了利用匈牙利算法評(píng)估網(wǎng)絡(luò)吞吐率的可行性和有效性。

參考文獻(xiàn)（References）

[1] Seo D，Ali A.Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks[C].International Symposium on Computer Architecture，Proceedings IEEE，2005，33（2）：432-443.

[2] 張立，戴一奇.隨機(jī)Oblivious路由算法中隨機(jī)性與時(shí)間代價(jià)的研究[J].計(jì)算機(jī)學(xué)報(bào)，1996，19（5）：388-397.

[3] Towles B，Dally WJ.Worst-case traffic for oblivious routing functions[C].Fourteenth ACM Symposium on Parallel Algorithms and Architectures，ACM，2002，1（1）：1-8.

[4] Sullivan，Herbert.A large scale，homogeneous，fully distributed parallel machine，I.[C].Proc Fourth Symposium on Computer Architecture ACM，1977，5（7）：105-117.

[5] J.Upadhyay，V.Varavithya，P.Mohapatra.A Traffic Balanced Adaptive Wormhole Routing Scheme for Two-Dimensional Meshes[J].Transactions on Computers，1997，46（2）：190-197.

[6] Rajasekaran S，Overholt R.Constant queue routing on a mesh[J].Journal of Parallel&Distributed; Computing，1991，15（15）：

160-166.

作者簡(jiǎn)介：

張方爽（1993-），女，碩士生.研究領(lǐng)域：片上網(wǎng)絡(luò)技術(shù).

段新明（1970-），男，博士，副教授.研究領(lǐng)域：互聯(lián)網(wǎng)絡(luò)技術(shù)，片上網(wǎng)絡(luò)技術(shù)，容錯(cuò)路由.