[發(fā)明專利]約束分離路徑計(jì)算

有效

• 申請(qǐng)?zhí)枺?/td>: 201580080486.7
• 申請(qǐng)日: 2015-10-21
• 公開(kāi)（公告）號(hào): CN107710701B
• 公開(kāi)（公告）日: 2020-09-11
• 發(fā)明（設(shè)計(jì)）人: 保羅·瑪?shù)赂覃惏材?/a>;斯特凡諾·帕里斯;杰瑞米·萊瓜伊;揚(yáng)尼斯·斯緹柯吉安納庫(kù)斯
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): H04L12/735
• 分類號(hào): H04L12/735;H04L12/721;H04L12/707;H04L12/717
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明公開(kāi)了一種確定通信網(wǎng)絡(luò)中的多個(gè)分離約束路徑的方法。該方法包括：為具有源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的至少兩個(gè)路徑的分離路徑組合中的每一個(gè)路徑選擇QoS度量作為上限；確定最小代價(jià)分離路徑組合和最小QoS度量分離路徑組合；通過(guò)對(duì)所最小代價(jià)分離路徑組合中的每個(gè)最小代價(jià)路徑的該QoS度量求和，來(lái)計(jì)算最大QoS度量，并通過(guò)對(duì)該最小QoS分離路徑組合中每個(gè)最小QoS度量路徑的該QoS度量求和，來(lái)計(jì)算最小QoS度量。該方法還包括：確定該最大QoS和該最小QoS的間隔內(nèi)的所有最小代價(jià)分離路徑組合；從該間隔內(nèi)的該所有最小代價(jià)分離路徑組合中選擇具有路徑的所有組合，其中，該路徑中的每個(gè)路徑的QoS度量在該上限內(nèi)。該方法進(jìn)一步包括：從該具有其QoS度量在該上限內(nèi)的路徑的集合中選擇最小代價(jià)分離路徑組合。本發(fā)明還公開(kāi)了一種實(shí)現(xiàn)該方法的裝置。

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

本發(fā)明大體涉及通信網(wǎng)絡(luò)，尤其涉及一種約束分離路徑計(jì)算方法和裝置。

背景技術(shù)

在典型的SDN(軟件定義網(wǎng)絡(luò))或PCE(路徑計(jì)算單元)架構(gòu)中，例如圖1中的SDN網(wǎng)絡(luò)架構(gòu)100所示，SDN路由器102和SDN交換機(jī)104可以通過(guò)通信網(wǎng)絡(luò)105與集中式SDN控制器106進(jìn)行交互，可以確定新的傳入需求應(yīng)該采取的路線。SDN網(wǎng)絡(luò)架構(gòu)100可以使用OpenFlow協(xié)議108等通信協(xié)議來(lái)實(shí)現(xiàn)SDN控制器106的南向接口內(nèi)的標(biāo)準(zhǔn)化交互。針對(duì)SDN交換機(jī)102處理的每個(gè)數(shù)據(jù)包，可使用OpenFlow協(xié)議108向SDN控制器106發(fā)送流請(qǐng)求110。SDN控制器可以回復(fù)flow mod消息112以更新SDN路由器102和SDN交換機(jī)104的路由表。此外，SDN控制器106可以主動(dòng)地配置通信網(wǎng)絡(luò)105中的路由，以應(yīng)答來(lái)自應(yīng)用114并經(jīng)過(guò)北向接口的請(qǐng)求。

SDN和PCE架構(gòu)經(jīng)常用于可能包括視頻或語(yǔ)音流的多媒體應(yīng)用。這些類型的應(yīng)用通常需要限制數(shù)據(jù)的發(fā)射和接收之間的時(shí)延，以確保令最終用戶滿意的QoE(體驗(yàn)質(zhì)量)。

通常，SDN控制器負(fù)責(zé)進(jìn)行路徑計(jì)算，確定滿足給定QoS(服務(wù)質(zhì)量)約束的主路徑和備用路徑，同時(shí)嘗試在給定的時(shí)間范圍內(nèi)提供滿意QoE的最佳解決方案。SDN控制器可以包括快速路徑計(jì)算模塊，其能夠計(jì)算網(wǎng)絡(luò)中的嘗試滿足與應(yīng)用相關(guān)聯(lián)的約束的路徑。例如，如果其中一個(gè)約束是在主路徑中存在故障的情況下保持服務(wù)連續(xù)性，則可以類似地將與主路徑相關(guān)聯(lián)的時(shí)延要求應(yīng)用于備份路徑。

確定滿足應(yīng)用約束的主路徑和備用路徑的最佳方式通常為NP困難(非確定性多項(xiàng)式時(shí)間困難)。現(xiàn)已開(kāi)發(fā)了一些啟發(fā)式演算法，并已被用來(lái)嘗試解決路徑路由中的約束優(yōu)化問(wèn)題，包括拉格朗日松弛法、最短路徑算法和迪杰斯特拉算法等。下面將描述這些啟發(fā)式演算法到約束路徑路由的一些應(yīng)用的示例。

在《IEICE信息與系統(tǒng)匯刊》90.2(2007)的第465-472頁(yè)，PengShen發(fā)表的《計(jì)算雙限分離路徑的新近似算法》一文涉及“通過(guò)使用拉格朗日松弛法和用于發(fā)現(xiàn)以合理的總代價(jià)滿足時(shí)延約束的多鏈路分離路徑的近似算法來(lái)【識(shí)別具有最小總代價(jià)OPT并且滿足圖G中的時(shí)延界限D(zhuǎn)的多個(gè)分離路徑】的近似算法”。若最佳解決方案中時(shí)延限制D下產(chǎn)生代價(jià)OPT，則該算法可以找到一個(gè)解決方案，其時(shí)延限制為(1+1/k)D，且代價(jià)不超過(guò)(1+k)OPT。

Juttner等人的美國(guó)專利號(hào)7020086涉及“一種用于實(shí)際QoS路由的方法”，該方法為時(shí)延約束的最小代價(jià)路由問(wèn)題提供了一種解決方案。該方法使用聚合代價(jià)的概念，并基于拉格朗日松弛法找到最佳乘數(shù)。該方法在運(yùn)行時(shí)間使用多項(xiàng)式，并產(chǎn)生理論下限(即最佳解決方案)和結(jié)果。下限和結(jié)果之間的差異很小，用來(lái)表明結(jié)果的質(zhì)量。此外，為進(jìn)一步緩解對(duì)最佳解決方案的需求，提供了一種權(quán)衡控制算法的運(yùn)行時(shí)間與結(jié)果的質(zhì)量的選項(xiàng)。

授予Kothari等人的美國(guó)專利號(hào)8243604涉及“一種通信方法，包括同時(shí)計(jì)算通過(guò)節(jié)點(diǎn)對(duì)之間的網(wǎng)絡(luò)的最短路徑和備用路徑。通過(guò)從最短路徑和備份路徑中選出至少一個(gè)路徑對(duì)數(shù)據(jù)包在網(wǎng)絡(luò)進(jìn)行路由”。