[發(fā)明專利]基于層次分析法的多度量參數(shù)的通信網(wǎng)路由方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310083053.X
• 申請(qǐng)日: 2013-03-15
• 公開(kāi)（公告）號(hào): CN103139069A
• 公開(kāi)（公告）日: 2013-06-05
• 發(fā)明（設(shè)計(jì)）人: 袁東明;范智宇;劉元安;胡鶴飛;冉靜;鄭廣杰;楊學(xué)斌
• 申請(qǐng)（專利權(quán)）人: 北京安拓思科技有限責(zé)任公司
• 主分類號(hào): H04L12/721
• 分類號(hào): H04L12/721;H04L12/801
• 代理公司: 北京德琦知識(shí)產(chǎn)權(quán)代理有限公司 11018
• 代理人: 夏憲富

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

本發(fā)明涉及一種基于層次分析法的多度量參數(shù)的通信網(wǎng)路由方法，屬于通信網(wǎng)中的路由交換技術(shù)領(lǐng)域。

背景技術(shù)

現(xiàn)有技術(shù)的網(wǎng)絡(luò)路由算法中，根據(jù)網(wǎng)絡(luò)中的網(wǎng)絡(luò)參數(shù)信息存儲(chǔ)方式，目前主要有三類路由算法：源路由算法，分布式路由算法和分層路由算法。其中：

源路由算法是假設(shè)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都了解網(wǎng)絡(luò)的全局狀態(tài)，每個(gè)節(jié)點(diǎn)都分別維護(hù)一個(gè)全局狀態(tài)信息庫(kù)，當(dāng)要發(fā)送消息時(shí)，源節(jié)點(diǎn)就能夠決定數(shù)據(jù)轉(zhuǎn)發(fā)的路徑。使用源路由算法的典型協(xié)議有鏈路狀態(tài)協(xié)議OSPF，該OSPF協(xié)議中的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)其他節(jié)點(diǎn)廣播本節(jié)點(diǎn)的狀態(tài)信息，以使每個(gè)節(jié)點(diǎn)都能獲知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和鏈路信息的變化。路由器根據(jù)這些狀態(tài)信息生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，再根據(jù)拓?fù)浣Y(jié)構(gòu)計(jì)算出路由。其他的源路由算法有：Ma-Steenkiste?algorithms，Guerin-Orda?algorithms和Chen-Nahrstedt?algorithms等等。

1996年Wang和Crowcroft證明了當(dāng)約束條件數(shù)大于等于2時(shí)，服務(wù)質(zhì)量路由問(wèn)題為NP完全問(wèn)題。隨著網(wǎng)絡(luò)規(guī)模的逐漸增大，源路由算法的復(fù)雜度呈幾何階數(shù)上升，而且，路由表的大小和周期更新報(bào)文的總量也在不斷變大。這就使得在大型網(wǎng)絡(luò)中有效更新和存儲(chǔ)狀態(tài)信息的難度日趨嚴(yán)重。如果不采取有效方法解決網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的伸縮性問(wèn)題，在網(wǎng)絡(luò)規(guī)模繼續(xù)增大的發(fā)展趨勢(shì)下，路由器的處理和存儲(chǔ)能力最終將被耗盡。

分布式路由算法中，每個(gè)節(jié)點(diǎn)只了解其相鄰節(jié)點(diǎn)的情況，即只獲知網(wǎng)絡(luò)局部狀態(tài)（包括時(shí)延、時(shí)延抖動(dòng)、帶寬和花費(fèi)等）。它的路由過(guò)程不是在源節(jié)點(diǎn)完成的，而是經(jīng)過(guò)節(jié)點(diǎn)的逐跳計(jì)算才完成的。分布式路由算法有Wang-Crowcroft?algorithms，Sun-Landgendorfer?algorithms和Shin-Chou?algorithms等等。分布式路由算法回避了復(fù)雜的路徑計(jì)算問(wèn)題，算法方法簡(jiǎn)單，鏈路開(kāi)銷小，同時(shí)也節(jié)省了維護(hù)全網(wǎng)狀態(tài)的處理時(shí)間。其缺點(diǎn)是：節(jié)點(diǎn)間尋路協(xié)同性能降低，容易引起環(huán)路或忽略最佳路徑。

分層路由算法是把網(wǎng)絡(luò)節(jié)點(diǎn)分級(jí)，每一級(jí)節(jié)點(diǎn)只了解自己所在范圍內(nèi)的情況，而對(duì)遠(yuǎn)處的上級(jí)節(jié)點(diǎn)只獲知大致或基本情況。例如，ATM（Asynchronous?Transfer?Mode）網(wǎng)絡(luò)中使用的PNNI（Private?Network-to-Network?Interface）協(xié)議。分層路由算法中，處于不同層級(jí)的路由器分別負(fù)責(zé)各自不同層次的路由，將路由計(jì)算分為多個(gè)層次，減輕了每個(gè)路由器的路由計(jì)算負(fù)擔(dān)，同時(shí)也可以避免出現(xiàn)環(huán)路。但是，匯集成組后，組外節(jié)點(diǎn)無(wú)法完全獲知組內(nèi)節(jié)點(diǎn)的狀態(tài)信息，會(huì)加重路由信息的不準(zhǔn)確性。

層次分析法AHP（Analytic?Hierarchy?Process）是將一個(gè)復(fù)雜的多目標(biāo)決策問(wèn)題作為一個(gè)系統(tǒng)，即將設(shè)定目標(biāo)分解為多個(gè)具體目標(biāo)或準(zhǔn)則，進(jìn)而分解為多指標(biāo)（或準(zhǔn)則、約束）的若干層次，通過(guò)定性指標(biāo)模糊量化方法算出層次單排序（權(quán)數(shù)）和總排序，以作為目標(biāo)（多指標(biāo)）、多方案優(yōu)化決策的系統(tǒng)方法。其通常的操作步驟如圖1所示。

目前，網(wǎng)絡(luò)路由算法涉及的度量參數(shù)包括：帶寬、延時(shí)、延時(shí)抖動(dòng)、丟失率和跳數(shù)等等。根據(jù)運(yùn)算規(guī)則，這些度量參數(shù)可以分為加性度量參數(shù)、乘性度量參數(shù)和凹性度量參數(shù)。假設(shè)路徑P包含n條鏈路{l₁,l₂...l_n}，f(l_i)是鏈路l_i的參數(shù)值，f(P)是路徑P的參數(shù)值，則各種度量參數(shù)的定義如下：

加性度量參數(shù)：乘性度量參數(shù)：凹性度量參數(shù)：f(P)=min{f(l_i)}；式中，自然數(shù)i為鏈路序號(hào)，其最大值為n。其中，傳輸延時(shí)、跳數(shù)和代價(jià)都屬于加性度量參數(shù)，丟失率屬于乘性度量參數(shù)，帶寬屬于凹性度量參數(shù)。本發(fā)明如同其他研究多度量參數(shù)路由的情況，選取時(shí)延、丟包率和帶寬分別作為加性度量參數(shù)、乘性度量參數(shù)和凹性度量參數(shù)的代表。

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

有鑒于此，本發(fā)明的目的是提供一種基于層次分析法解決通信網(wǎng)中多度量參數(shù)的路由方法，以往的路由方法往往只確定單一最優(yōu)路徑，當(dāng)從一個(gè)源節(jié)點(diǎn)到目的節(jié)點(diǎn)的流量超過(guò)了最優(yōu)路徑的容量閾值，該最優(yōu)路徑將變得擁塞；然而，同時(shí)這兩點(diǎn)之間可能有一條次優(yōu)路徑未被充分使用。本方法根據(jù)業(yè)務(wù)類型，在源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間建立多條不同權(quán)重的路徑，當(dāng)權(quán)重最大的路徑因負(fù)載過(guò)重而出現(xiàn)擁塞時(shí)，選擇權(quán)重次之的路徑；當(dāng)次優(yōu)路徑擁塞時(shí)，再選擇下一級(jí)次優(yōu)路徑，這樣能夠有效改善流量擁塞，實(shí)現(xiàn)全局負(fù)載均衡。