基于約束分析的RapidIO 路由選擇算法

李宗燦，曹 建

（中南大學(xué) 物理與電子學(xué)院，湖南 長沙410083）

0 引 言

RapidIO 總線技術(shù)是專門針對高性能嵌入式系統(tǒng)芯片間和板間互連通信而設(shè)計的，該互連技術(shù)支持各種拓?fù)浣Y(jié)構(gòu)，通過交換器件可組成各種規(guī)模大小的通信網(wǎng)絡(luò)。同時作為高速總線技術(shù)，RapidIO 總線對網(wǎng)絡(luò)的延遲、帶寬及丟包率等服務(wù)質(zhì)量參數(shù) （quality of service，QoS）有著很高的要求，因此研究如何提高RapidIO 網(wǎng)絡(luò)的服務(wù)質(zhì)量有很重要的現(xiàn)實意義［1］。

RapidIO 網(wǎng)絡(luò)的服務(wù)質(zhì)量問題是一個多混合約束度量問題，在給定的多種混合約束條件下尋找可行的路徑，是一個NPC問題，應(yīng)采用啟發(fā)式算法進(jìn)行求解［2］。文獻(xiàn) ［3，4］提出采用改進(jìn)的遺傳算法進(jìn)行可行路徑的選擇，但該算法存在編碼困難等問題，且遺傳算法為局部搜索算法，容易陷入局部極值導(dǎo)致找不到可行解；文獻(xiàn) ［5］提出基于K－shortest算法，在尋徑過程中用模擬退火跳出局部最優(yōu)，該方法具有很好的全局最優(yōu)解，然而該算法性能非常依賴于溫度和節(jié)點存儲路徑的影響。針對這種情況，本文提出約束嚴(yán)苛度的概念，并在此基礎(chǔ)上設(shè)計基于K 最優(yōu)路徑的RapidIO 路由選擇算法。該算法采用約束嚴(yán)苛度表示不同系統(tǒng)對QoS的不同需求，并采用基于K 最短路徑的搜索算法進(jìn)行搜索，最終選擇滿足約束要求的可行路徑。仿真結(jié)果表明，該算法有較高的搜索成功率，同時具有多項式時間復(fù)雜度，因此有很好的實用價值。

1 RapidIO 網(wǎng)絡(luò)模型

1.1 RapidIO 網(wǎng)絡(luò)結(jié)構(gòu)

RapidIO 總線是基于包交換的傳輸協(xié)議，包是RapidIO協(xié)議中基本的傳輸單位。如圖1所示，RapidIO 網(wǎng)絡(luò)通常由2種器件構(gòu)成，分別是終端器件和交換器件。終端器件是各種處理器節(jié)點，是數(shù)據(jù)包的源端或目的端，在網(wǎng)絡(luò)中作為數(shù)據(jù)交換的發(fā)起方或接收方；交換器件通常不發(fā)起請求包，其作用是根據(jù)內(nèi)置路由表，將包含不同目的ID 的數(shù)據(jù)包傳送到不同的端口。

圖1 某系統(tǒng)RapidIO 結(jié)構(gòu)框架

1.2 QoS模型

RapidIO 網(wǎng)絡(luò)QoS問題通常包括跳數(shù)、時延、帶寬和丟包率等約束條件，因此是多混合度量參數(shù)路由問題。QoS研究通常分為2個方向，一是滿足多約束的可行路徑選擇，一是滿足多約束的最優(yōu)路徑選擇，兩者都是NP 完全問題。本文關(guān)注第一類QoS問題。

路由選擇的目的就是要找出滿足所有約束條件的可行路徑。將RapidIO 中路由選擇問題進(jìn)行抽象，可以得到其通用的數(shù)學(xué)模型。

2 算法設(shè)計

2.1 算法思想

對一個約束可行的路徑，往往對另一個不成立，求解滿足多個QoS約束的路徑是NP 完全問題，不具有多項式的復(fù)雜度，必須采用啟發(fā)式算法。在目前提出的算法中，算法H＿M(jìn)COP［6］提出費用函數(shù)來統(tǒng)一多個約束之間的關(guān)系，并通過兩次Dijkstra算法來預(yù)測前向路徑，但是前后兩次查找都可能陷入局部最優(yōu)，導(dǎo)致找不到可行路徑。算法DS＿M(jìn)CP提出采用模擬退火算法跳出局部最優(yōu)解，可以有很好的全局收斂性，然而模擬退火算法性能對于溫度和迭代次數(shù)有很強(qiáng)的依賴性，并不能保證求得可行路徑。

不同系統(tǒng)對QoS參數(shù)的約束要求是不同的，通過分析約束信息，可以有效的指示可行路徑的搜索范圍，在減小的范圍空間內(nèi)進(jìn)行可行路徑的搜索會大大提高搜索成功率并減少搜索次數(shù)［7］。

我們知道，不同的系統(tǒng)對于QoS參數(shù)有著不同的需求，會提出各種不同的QoS約束參數(shù)。如某些系統(tǒng)更追求低時延，對于帶寬或其他服務(wù)質(zhì)量并沒有特別需要，則會對時延設(shè)置嚴(yán)格約束參數(shù)；某些系統(tǒng)對帶寬看重，對時延并沒有嚴(yán)格要求，那么系統(tǒng)的帶寬約束必定非常嚴(yán)格。根據(jù)不同的系統(tǒng)需求，我們提出約束嚴(yán)苛度的概念。

從定義中可以看出約束嚴(yán)苛度有以下幾個特點：

（1）若路徑p滿足某項QoS約束條件，則該項約束嚴(yán)苛度csl（p）≤1，若csl（p）＞1，則路徑p不滿足該項QoS約束條件；

（2）在csl（p）≤1時，當(dāng)csl（p）值越接近1，那么路徑p的該項QoS約束裕量越小，約束越嚴(yán)苛；

（3）對于（1≤l≤k），若csl（p）≤1都成立，則路徑p為滿足QoS約束的可行解。

在此基礎(chǔ)上，我們設(shè)計算法如下：

（1）針對k項不同約束度量，根據(jù)Dijkstra最短路徑算法，依次計算其在該項約束度量下的最短路徑，所有k種約束度量的最短路徑總數(shù)為k條，分別記作p1，p2，…，pk；

（2）根據(jù)得出的最短路徑，依次計算每條路徑在相應(yīng)的約束度量下的約束嚴(yán)苛度，分別記作cs1（p1），cs2（p2），…，csk（pk）；

（3）判斷上述約束嚴(yán)苛度，若存在任一約束嚴(yán)苛度值大于1，則判斷該網(wǎng)絡(luò)不存在可行解，算法結(jié)束，否則進(jìn)入下一步；

（4）若所有約束嚴(yán)苛度值都不大于1，則選擇約束嚴(yán)苛度值最大的路徑pm，則pm是在約束度量m 下得到的最優(yōu)路徑。分別計算路徑pm的所有k項約束嚴(yán)苛度csl（pm），（1≤l≤k）。若路徑pm的約束嚴(yán)苛度值存在大于1的情況，則進(jìn)入下一步執(zhí)行，否則pm即為可行解，算法結(jié)束；

（5）在第m 項度量約束條件下，采用文獻(xiàn) ［8，9］中的求解第K 最短路徑的方法，計算次優(yōu)解路徑，判斷該路徑的第m 項約束嚴(yán)苛度，若不大于1，則進(jìn)入下一步執(zhí)行，否則判斷無可行解，算法結(jié)束；

（6）計算上一步得到的路徑的所有約束項嚴(yán)苛度，當(dāng)該路徑有約束嚴(yán)苛度值大于1，則轉(zhuǎn)入上一步執(zhí)行，否則該路徑即為可行解，算法結(jié)束。

2.2 算法分析

在算法步驟 （1）中，提出采用Dijkstra算法求取最短路徑，此處所說的最短路徑是廣義上的最短路徑，即在單約束條件下的最優(yōu)路徑，如對于時延、跳數(shù)等約束，則為尋找最短路徑，可直接通過Dijkstra算法尋找；對于帶寬則為尋找最大帶寬路徑，可以通過修改最短路徑算法得到，分別用求極大值和求極小值運算代替Dijkstra算法中求極小值運算和加法運算即可；對于丟包率則為尋找最小丟包率路徑，也可以通過修改最短路徑算法得到，將Dijkstra算法中求極小值運算和加法運算分別用求極大值和乘法運算代替就可得到，應(yīng)注意在算法過程中丟包率到成功率的轉(zhuǎn)換。Dijkstra算法的時間復(fù)雜度是O（n2），其中n為網(wǎng)絡(luò)中節(jié)點的個數(shù)，算法步驟 （1）時間復(fù)雜度為O（kn2），其中k為約束條件的個數(shù)。

在算法步驟 （4）中，選取約束嚴(yán)苛度最高的約束度量進(jìn)行后續(xù)第K 最優(yōu)路徑的計算，約束嚴(yán)苛度高表明系統(tǒng)更重視該約束條件，且滿足該約束的路徑數(shù)量相對更少，可以非常有效的減少后續(xù)算法的計算次數(shù)。

在算法步驟 （5）、步驟 （6）中，采用文獻(xiàn) ［8，9］中方法求解K 最短路徑，最壞情況下其時間復(fù)雜度為O（Kn2），其中K 為第K 短路徑，K 根據(jù)約束條件自適應(yīng)產(chǎn)生。所以整個算法的時間復(fù)雜度為多項式復(fù)雜度，同時，因為算法中提出了對無可行解情況的判斷和算法退出條件，因此在求解問題時，能夠及時停止運算，降低路由計算的盲目性，具有很高的時效性。

該算法通過約束嚴(yán)苛度這一概念對系統(tǒng)約束條件進(jìn)行評價，在該評價基礎(chǔ)上將相互無關(guān)的多約束問題轉(zhuǎn)化為有選擇性的約束問題進(jìn)行求解，可以快速尋找到可行解。同時該算法對于約束度量參數(shù)的增加也具有很好的擴(kuò)展性。

2.3 算法應(yīng)用

在圖1所示系統(tǒng)中為每條邊添加如下度量信息，為與別的算法進(jìn)行比較，因此采用2個加性度量，則圖1所示系統(tǒng)的拓?fù)浣Y(jié)構(gòu)如圖2所示。

對于圖2，設(shè)源節(jié)點為v1，目標(biāo)節(jié)點為v9，給定QoS約束條件為C（24，24），通過觀察可以發(fā)現(xiàn)可行路徑為p＝v1－v4－v5－v6－v9，然而當(dāng)采用H＿M(jìn)COP 算法進(jìn)行計算時，找不到可行路徑，因為該算法路徑由前向和后向2個路徑組成，在約束嚴(yán)苛情況下，一旦有一個路徑陷入局部最優(yōu)解，則找不到最終可行路徑。

圖2 系統(tǒng)拓?fù)?/p>

采用本文所提出算法，計算過程如下：

（2）比較可得約束度量2約束嚴(yán)苛度較大，因此以約束度量2作為側(cè)重約束進(jìn)行計算，計算p2 所有約束度量w（p2）＝（26，24）并不滿足約束條件，因此采用第K 最優(yōu)路徑法［7］，求解約束度量2的次優(yōu)路徑保存在p2。

（3）求得次優(yōu)路徑p2＝v1－v4－v5－v6－v9，計算其約束度量w（p2）＝（16，24），可以滿足約束條件，因此算法結(jié)束，可行解為p2＝v1－v4－v5－v6－v9。

在此問題中，若不采用約束嚴(yán)苛度進(jìn)行方向判斷，當(dāng)采用K 最短路徑求解時，K＝4才能求出可行解，約束嚴(yán)苛度的評判加速了可行解的查找。

3 算法性能測試

本文分別設(shè)計實驗進(jìn)行仿真，并與目前性能較好的H＿M(jìn)COP算法和DS＿M(jìn)CP 算法作對比，同時測試在多次測量過程中所需要求解的第K 最優(yōu)路徑參數(shù)情況。

3.1 實驗參數(shù)

（1）本實驗使用Matlab產(chǎn)生N 個節(jié)點的完全隨機(jī)拓?fù)鋱D，為每個鏈路設(shè)置了在 ［1，100］區(qū)間內(nèi)均勻分布且相互無關(guān)的k種約束度量wl（e），分別模擬了節(jié)點數(shù)為50，100，150，200的隨機(jī)網(wǎng)絡(luò)，每種情況產(chǎn)生10 個拓?fù)鋱D，本文選取k＝2進(jìn)行仿真。

（2）約束條件的設(shè)置對于問題是否有可行解有著決定性作用，本文依據(jù)3種方法產(chǎn)生約束條件。

C1：cl（p）＝wl（p），（1≤l≤k），路徑p是用第1個約束參數(shù)計算出來的最優(yōu)路徑，若最優(yōu)路徑有多條，則在這些路徑中取第2個約束參數(shù)最優(yōu)的路徑，從而保證路徑p的唯一性。

3.2 性能評價

（1）成功率［10］，在節(jié)點數(shù)為50，100，150，200 的網(wǎng)絡(luò)上分別隨機(jī)選取1000對源－目標(biāo)節(jié)點對，對每個網(wǎng)絡(luò)計算路由成功率，并對10個同規(guī)模拓?fù)涞某晒β嗜【怠?/p>

（2）K值，由于本文采用了基于K 最短路徑的算法，K值的大小決定算法耗費時間，也是算法評價的一個重要標(biāo)準(zhǔn)。

圖3 3種不同約束下算法成功率比較

從圖3中可以看出，在約束條件為C1 和C2，本文提出算法成功率要優(yōu)于H－MCOP算法和DS－MCP算法。在約束條件為C3時，因為約束條件的隨機(jī)變化，導(dǎo)致可行解是否存在不能保證，在相同的約束條件下進(jìn)行測試，本文算法成功率也要優(yōu)于H－MCOP 和DS－MCP。此處為保證DSMCP算法有最好效果，取M 為3，I為3。

當(dāng)約束條件分別為C1，C2，C3 時，本文分別對本文算法和不采用約束嚴(yán)苛度的K 最短路徑算法進(jìn)行研究，對K 的大小進(jìn)行了統(tǒng)計。結(jié)果見表1，表2，表3。

表1 C1約束下K 值比較

表2 C2約束下K 值比較

表3 C3約束下K 值比較

從上面3 個表格中可以看出，由于C1 約束下路徑唯一，當(dāng)采用約束嚴(yán)苛度進(jìn)行搜索指引時，會大大減少K 最短路徑求解次數(shù)，迅速找到可行解；C2約束非常寬松，在這種情況下約束嚴(yán)苛度影響不大；C3約束下本算法比K 最短路徑的求解次數(shù)也有一定的減少。

通過上表可以看到，約束嚴(yán)苛度概念的引入，為算法后續(xù)求解K 最短路徑提供了方向指導(dǎo)，尤其是在約束嚴(yán)格條件下，采用約束嚴(yán)苛度判別可以非常有效的減少K 最短路徑的求解次數(shù)，從而大大減少了時間的消耗。

4 結(jié)束語

本文以多約束條件的RapidIO 網(wǎng)絡(luò)路由選擇問題為模型，定義了約束嚴(yán)苛度來表征系統(tǒng)對約束參數(shù)的需求，并通過約束嚴(yán)苛度指示搜索方向，避免了盲目搜索。在此基礎(chǔ)上采用K－最優(yōu)路徑算法進(jìn)行可行路徑的搜索。本文所提出的啟發(fā)性算法滿足多項式復(fù)雜度，比以往算法有較高概率找到可行解，同時對于約束度量個數(shù)的擴(kuò)展有著很好的適用性，因此具有很強(qiáng)的實用價值。

［1］PAN Ling，SANG Nan.Path distribution strategy in RapidIO network ［J］.Computer Applications，2008，28 （s2）：294－295 （in Chinese）.［潘靈，桑楠.一種RapidIO 網(wǎng)絡(luò)路徑分配策略 ［J］.計算機(jī)應(yīng)用，2008，28 （s2）：294－295.］

［2］HAN He，QIN Yong.Overview of multi－constrained QoS routing algorithm ［J］.Computer Technology and Development，2012，22 （4）：133－136 （in Chinese）. ［韓賀，秦勇.基于多約束QoS路由算法綜述 ［J］.計算機(jī)技術(shù)與發(fā)展，2012，22（4）：133－136.］

［3］CAI Wei，ZHANG Jiandong，CAI Huizhi.Optimization and improvement of RapidIO network routing strategy ［J］.Computer Engineering and Applications，2011，47 （14）：87－90（in Chinese）.［蔡煒，張建東，蔡惠智.RapidIO 網(wǎng)絡(luò)路由分配策略的優(yōu)化和改進(jìn) ［J］.計算機(jī)工程與應(yīng)用，2011，47（14）：87－90.］

［4］CAI Wei，ZHANG Jiandong，CAI Huizhi.Multi－objective optimization of RapidIO network ［J］.Journal of Computer Applications，2010，30 （12）：3172－3175 （in Chinese）.［蔡煒，張建東，蔡惠智.RapidIO 網(wǎng)絡(luò)QoS多目標(biāo)優(yōu)化 ［J］.計算機(jī)應(yīng)用，2010，30 （12）：3172－3175.］

［5］ZOU Yonggui，WEI Lai.Optimal path algorithm with multiconstrained condition ［J］.Computer Applictions，2008，28（5）：1101－1103 （in Chinese）.［鄒永貴，魏來.帶多約束條件的最優(yōu)路徑選擇算法研究 ［J］.計算機(jī)應(yīng)用，2008，28 （5）：1101－1103.］

［6］QIAN Yi，QIAN Jin.Improved multi－constrained QoSR algorithm［J］.Computer Engineering and Design，2008，29 （8）：1931－1934 （in Chinese）.［錢奕，錢進(jìn).改進(jìn)的QoS多約束路由算法［J］.計算機(jī)工程與設(shè)計，2008，29 （8）：1931－1934.］

［7］QI Xiaogang，LIU Lifang，LIU Sanyang.Multi－constrained path selection algorithm based on the depth of the distance vector［J］.ACTA Electronica SINICA，2009，37 （1）：175－179 （in Chinese）.［齊小剛，劉立芳，劉三陽.基于距離向量深度的多約束路徑選擇算法［J］.電子學(xué)報，2009，37 （1）：175－179.］

［8］FU Junwei，LI Xingming，CHEN Jie.A practical algorithm for finding the shortest Kth path based on deviation path ［J］.Computer Technology and Development，2009，19 （2）：120－126 （in Chinese）.［傅俊偉，李興明，陳捷.基于背離路徑的Kth最短路徑使用搜索算法 ［J］.計算機(jī)技術(shù)與發(fā)展，2009，19 （2）：120－126.］

［9］BAI Yiduo，HU Peng，XIA Lanfang，et al.A kth－shortest path algorithm based on k－1shortest paths［J］.Geomatics and Information science of Wuhan University，2009，34 （4）：492－494 （in Chinese）.［白軼多，胡鵬，夏蘭芳，等.關(guān)于k次短路徑問題的分析與求解 ［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2009，34 （4）：492－494.］

［10］MA Yueyong，WANG Haimei，LIAO Jianjun.Comparative study of multi－constrained optimal path algorithms［J］.Journal of Nanjing University of Science and Technology，2011，35 （6）：749－754 （in Chinese）.［馬躍勇，王海梅，廖建軍.多約束最優(yōu)路徑算法比較研究 ［J］.南京理工大學(xué)學(xué)報，2011，35 （6）：749－754.］