張方爽　段新明

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

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

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

1 引言（Introduction）

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

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

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

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

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

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

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

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

在窮舉法中找到最壞情況的負(fù)載，就要考慮所有的置換排列。時間復(fù)雜度為O（N！），是一個NP難問題，計算量很大。為此文本利用匈牙利算法計算最壞情況的吞吐率。大大降低了時間復(fù)雜度，提高算法的效率[2]。

3 算法模式（Algorithm mode）

3.1 窮舉法算法模式

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

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

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

3.2 匈牙利算法的基本模式

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

（1）初始時最大匹配為空；

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

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

引理1：如果從一個點A出發(fā)，沒有找到增廣路徑，那么無論再從別的點出發(fā)找到多少增廣路徑來改變現(xiàn)在的匹配，從A出發(fā)都永遠(yuǎn)找不到增廣路徑。

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

（1）初始時最大匹配為空；

（2）for二分圖左半邊的每個點i；

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

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

KM（Kuhn-Munkras）算法用來解決最大權(quán)匹配問題的算法。其基本原理：KM算法是通過給每個頂點一個標(biāo)號（叫做頂標(biāo)）來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題。設(shè)頂點Xi的頂標(biāo)為A[i]，頂點Yj的頂標(biāo)為B[j]，頂點Xi與Yj之間的邊權(quán)為w[i，j]。在算法執(zhí)行過程中的任一時刻，對于任一條邊（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ò)吞吐率評估（Network throughput evaluation）

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

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

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

最大權(quán)重匹配算法存在。窮舉法的時間復(fù)雜度O（N?。眯傺览惴ㄓ嬎愕臅r間復(fù)雜度O（N3）。窮舉法和匈牙利算法在效率上的差別，可以看出，利用匈牙利算法求吞吐率算法的性能是相當(dāng)好的。

5 仿真與分析（Simulation and analysis）

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

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

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

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

6 結(jié)論（Conclusion）

利用匈牙利算法我們可以在多項式時間內(nèi)找到Oblivious的路由算法的最壞情況吞吐量，這使得最壞情況的分析變得易于處理。二分圖構(gòu)造來分析Oblivious路由算法是評估最壞情況下網(wǎng)絡(luò)吞吐率的一個方法。對比窮舉法，計算最壞情況下的吞吐率時間效率得到很大改善；在時間復(fù)雜度上，窮舉法的時間復(fù)雜度是O（N?。眯傺览惴ǖ臅r間復(fù)雜度是O（N3）。實驗通過利用Oblivious路由算法中O1TURN等算法，以及運行時間的對比，證明了利用匈牙利算法評估網(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ī)性與時間代價的研究[J].計算機(jī)學(xué)報，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.

作者簡介：

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

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