[發(fā)明專利]基于反饋的自適應(yīng)多約束的路徑搜索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210118658.3
• 申請(qǐng)日: 2012-04-20
• 公開（公告）號(hào): CN102664802A
• 公開（公告）日: 2012-09-12
• 發(fā)明（設(shè)計(jì)）人: 張大陸;匡增美;胡治國(guó)
• 申請(qǐng)（專利權(quán)）人: 同濟(jì)大學(xué)
• 主分類號(hào): H04L12/56
• 分類號(hào): H04L12/56
• 代理公司: 上海光華專利事務(wù)所 31219
• 代理人: 李儀萍

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

本發(fā)明涉及一種路由器的路徑搜索方法，特別是涉及一種基于反饋的自適應(yīng)多約束的路徑搜索方法。

背景技術(shù)

隨著網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大，QoS路徑算法一直是網(wǎng)絡(luò)領(lǐng)域的研究熱點(diǎn)。網(wǎng)絡(luò)技術(shù)的高速發(fā)展和各種網(wǎng)絡(luò)服務(wù)興起，人們對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量的要求也越來越高，然而IP網(wǎng)絡(luò)無法提供服務(wù)質(zhì)量保證。為滿足用戶需求，人們提出了多QoS約束路由。多QoS約束路由是一種基于數(shù)據(jù)流QoS請(qǐng)求和網(wǎng)絡(luò)可用資源進(jìn)行路由的機(jī)制。多QoS約束路由不但能滿足對(duì)多個(gè)QoS參數(shù)有嚴(yán)格要求的業(yè)務(wù)的傳輸需求，而且可以提高網(wǎng)絡(luò)傳輸效率，充分利用網(wǎng)絡(luò)資源，網(wǎng)絡(luò)運(yùn)營(yíng)商也可以通過多QoS約束路由對(duì)不同需求的用戶提供不同質(zhì)量的服務(wù)。

其中，利用單混合度量參數(shù)路由算法來搜索滿足多QoS約束的最短路徑是一種解決網(wǎng)絡(luò)傳輸效率的方法。其中，單混合度量參數(shù)路由算法主要思想是將多個(gè)QoS約束通過一個(gè)線性或非線性函數(shù)表示成一個(gè)度量函數(shù)，然后利用最短路徑算法最終近似解決QoS路由問題。其理論依據(jù)是單個(gè)度量函數(shù)求解兩節(jié)點(diǎn)間最短路徑能在多項(xiàng)式時(shí)間內(nèi)完成。

目前，常用的單混合度量參數(shù)路由算法將兩個(gè)可加性QoS參數(shù)通過線性花費(fèi)函數(shù)擬合成單一函數(shù)值，再以該函數(shù)值為路徑選擇的度量，調(diào)用Dijkstra算法尋找路徑。缺陷是成功率相對(duì)較低，最后找出的路徑雖然具備最少花費(fèi)，但搜索出的路徑未必能同時(shí)滿足兩可加性QoS約束。

因此，需要對(duì)現(xiàn)有的單混合度量參數(shù)路由算法進(jìn)行改進(jìn)，以提高同時(shí)滿足多個(gè)可加性QoS約束的路徑的搜索成功率。

發(fā)明內(nèi)容

鑒于以上所述現(xiàn)有技術(shù)的缺點(diǎn)，本發(fā)明的目的在于提供一種基于反饋的自適應(yīng)多約束的路徑搜索方法，以提高同時(shí)滿足多個(gè)可加性QoS約束的路徑的搜索成功率。

為實(shí)現(xiàn)上述目的及其他相關(guān)目的，本發(fā)明提供一種基于反饋的自適應(yīng)多約束的路徑搜索方法，其包括步驟：1)基于單源最短路徑算法搜索第一節(jié)點(diǎn)至第二節(jié)點(diǎn)的滿足第一加性約束條件的第一路徑；判斷所述第一路徑的第二加性約束是否滿足第二加性約束條件；若所述第一路徑的第二加性約束滿足第二加性約束條件，則結(jié)束搜索并將所述第一路徑作為第一節(jié)點(diǎn)至第二節(jié)點(diǎn)的可行路徑；反之，若所述第一路徑的第二加性約束不滿足第二加性約束條件時(shí)，則進(jìn)入步驟2)：基于單源最短路徑算法搜索所述第二節(jié)點(diǎn)至第一節(jié)點(diǎn)的滿足所述第二加性約束條件的第二路徑，判斷所述第二路徑的第一加性約束是否滿足第一加性約束條件；若所述第二路徑的第一加性約束滿足第一加性約束條件，則結(jié)束搜索并將所述第二路徑作為第一節(jié)點(diǎn)至第二節(jié)點(diǎn)的可行路徑；反之，若所述第二路徑的第一加性約束不滿足所述第一加性約束條件，則進(jìn)入步驟3)：基于所述第一路徑的第一加性約束、所述第二路徑的第二加性約束、預(yù)設(shè)的第一加性約束、預(yù)設(shè)的第二加性約束來確定搜索所述第一節(jié)點(diǎn)至第二節(jié)點(diǎn)之間的第三路徑的度量函數(shù)，以單源最短路徑算法來搜索所述第三路徑；在確定所述第三路徑同時(shí)滿足所述第一加性約束條件和所述第二加性約束條件的情形下，將所述第三路徑作為第一節(jié)點(diǎn)至第二節(jié)點(diǎn)的可行路徑。

優(yōu)選地，若所述第一路徑與所述第二路徑中存在除第一節(jié)點(diǎn)和第二節(jié)點(diǎn)以外的至少一個(gè)共有節(jié)點(diǎn)，所述步驟3)還包括：3-1)基于所述第一路徑的第一加性約束、所述第二路徑的第二加性約束、預(yù)設(shè)的第一加性約束、預(yù)設(shè)的第二加性約束來確定搜索所述第一路徑與第二路徑不重疊的共有節(jié)點(diǎn)之間的子路徑的第一加性約束的權(quán)重以及所述子路徑的第二加性約束的權(quán)重；3-2)基于所述第一路徑與第二路徑不重疊的共有節(jié)點(diǎn)之間的子路徑的第一加性約束的權(quán)重和第二加性約束的權(quán)重所得到的度量函數(shù)以單源最短路徑算法來搜索所述子路徑，并用所述子路徑替換所述第一路徑和第二路徑中對(duì)應(yīng)節(jié)點(diǎn)之間的路徑部分，以確定替換后的第一路徑或第二路徑是否同時(shí)滿足所述第一加性約束條件和所述第二加性約束條件；在確定替換后的第一路徑或第二路徑同時(shí)滿足所述第一加性約束條件和所述第二加性約束條件的情形下，將所述替換后的第一路徑或第二路徑作為第一節(jié)點(diǎn)至第二節(jié)點(diǎn)的可行路徑。

優(yōu)選地，若所述替換后的第一路徑和第二路徑均不滿足所述第一加性約束條件和所述第二加性約束條件，所述步驟3)還包括：基于替換后的第一路徑和第二路徑中最小的第一加性約束和最小的第二加性約束、以及預(yù)設(shè)的第一加性約束、預(yù)設(shè)的第二加性約束來重復(fù)步驟3-1)和步驟3-2)。