IP網(wǎng)絡(luò)多約束單路徑路由算法的研究.pdf

1、隨著IP網(wǎng)絡(luò)應(yīng)用日益膨脹，各種服務(wù)也層出不窮。對(duì)網(wǎng)絡(luò)應(yīng)用而言，需要多QoS約束的路由模型來支持可區(qū)分的服務(wù)。所以多約束單路徑路由問題(Multiple Constraints Single Path Routing，MCSPR)的研究非常重要。通過其研究可以實(shí)現(xiàn)：1、為每一個(gè)接納的QoS業(yè)務(wù)連接請(qǐng)求，找到滿足其QoS要求的可行路徑；2、優(yōu)化全局資源利用率，平衡網(wǎng)絡(luò)負(fù)載，從而最大化網(wǎng)絡(luò)接受其他QoS請(qǐng)求的能力。 MCSPR問題很難

2、完全解決的原因是：尋找到優(yōu)化目標(biāo)，滿足一個(gè)以上路徑約束的可行路徑具有NP完全的計(jì)算復(fù)雜度，本文主要研究內(nèi)容包括： 1、形式化地描述了多約束單路徑路由的模型，給出了問題的混合規(guī)劃形式，并基于背包問題的NP完全性證明了多約束單路徑路由問題也是NP完全的。 2、設(shè)計(jì)了該問題的一種集中式求解近似算法；證明了該算法求出的解的一些性質(zhì)，并基于該算法給出了一個(gè)分布式的實(shí)現(xiàn)；實(shí)驗(yàn)結(jié)果表明：該近似算法的近似程度較高，所需運(yùn)行時(shí)間較少。

3、 3、基于多目標(biāo)遺傳進(jìn)化思想求解多約束單路徑路由問題。首先對(duì)問題做了擴(kuò)展，由于在路由問題中多個(gè)優(yōu)化目標(biāo)的偏好信息很難獲得，文章先求解問題的Pareto近似解，然后再根據(jù)實(shí)際需求對(duì)這些Pareto近似解進(jìn)行分析決策，選擇出最終的路由選擇方案。算法是基于Strength Pareto Evolutionary Algorithm2(SPEA2)算法思想進(jìn)行優(yōu)化選擇，并設(shè)計(jì)相關(guān)的遺傳算子完成種群進(jìn)化操作。 4、最后本文對(duì)多約束路由