SDH網(wǎng)絡(luò)增量規(guī)劃算法研究與實現(xiàn).pdf

1、近年來，隨著信息社會的發(fā)展，全球Internet業(yè)務(wù)呈現(xiàn)出一種爆炸式增長的趨勢。人們在思考怎么樣改進現(xiàn)有的傳輸技術(shù)的同時，怎么樣有效的去規(guī)劃一個傳輸網(wǎng)絡(luò)，以節(jié)省資源也成為另一個熱點。光傳送網(wǎng)是電信網(wǎng)絡(luò)的基礎(chǔ)，它為整個電信網(wǎng)絡(luò)的業(yè)務(wù)提供傳輸通道和平臺。SDH(同步數(shù)字系列)作為一種傳送網(wǎng)標(biāo)準(zhǔn)化的傳送技術(shù)體制，在光傳送網(wǎng)中獲得了巨大的發(fā)展。本文主要研究了SDH網(wǎng)絡(luò)規(guī)劃中增量規(guī)劃算法研究與實現(xiàn)。 增量規(guī)劃是在網(wǎng)絡(luò)中已經(jīng)配置好業(yè)務(wù)的時候

2、，將新增的業(yè)務(wù)配置在當(dāng)前的網(wǎng)絡(luò)上，使得網(wǎng)絡(luò)成本或資源最小。增量規(guī)劃中是否允許網(wǎng)絡(luò)擴容會直接導(dǎo)致優(yōu)化的目標(biāo)不同。本文詳細分析了單層SDH網(wǎng)絡(luò)增量規(guī)劃和兩層SDH網(wǎng)絡(luò)增量規(guī)劃，在允許擴容與不允許擴容兩種場景下，提出了適用于各自場景的啟發(fā)式算法。 本文第一章中概要介紹了SDH網(wǎng)絡(luò)的基本原理和結(jié)構(gòu)、生存性和業(yè)務(wù)量疏導(dǎo)相關(guān)問題。第二章中，主要研究了單層SDH網(wǎng)絡(luò)的增量規(guī)劃問題，在不允許擴容的場景下，我們給出了該問題的整數(shù)線性規(guī)劃的數(shù)學(xué)語言

3、描述，提出的啟發(fā)式算法采取不同的權(quán)重值結(jié)合，通過迭代得到多次計算的最優(yōu)值。權(quán)重設(shè)計中主要考慮了最小跳和負載均衡。仿真部分與ILP對比分析的結(jié)果表明該算法達到了很好的效果。在允許擴容的場景下，引入擴容權(quán)重，分析了單純的考慮充分利用現(xiàn)有資源或者直接新增資源，這兩種方法都會導(dǎo)致總的新增資源的增加，本文提出的啟發(fā)式算法綜合考慮了二者對總的新增資源的影響，期望在二者之間找到一個合理的折中。此外，也給出了該場景下的整數(shù)線性規(guī)劃(ILP)數(shù)學(xué)語言描述

4、。與ILP對比的仿真結(jié)果表明算法達到了理想的效果。 第三章中，主要研究了兩層SDH網(wǎng)絡(luò)的增量規(guī)劃問題。通過引入預(yù)先構(gòu)建的虛拓撲、在虛拓撲上進行客戶層業(yè)務(wù)的分層計算、業(yè)務(wù)量疏導(dǎo)，將低粒度的客戶層業(yè)務(wù)匯聚為高粒度的服務(wù)層業(yè)務(wù)，從而將兩層增量規(guī)劃問題轉(zhuǎn)化為兩個獨立的單層增量規(guī)劃問題。因此本章中，我們將詳細介紹在虛拓撲上面計算客戶層業(yè)務(wù)的增量啟發(fā)式算法設(shè)計。在不允許擴容與允許擴容兩種場景下，各自給出了在端到端和多跳(End-to-End

5、和Sub-Path)兩種業(yè)務(wù)量疏導(dǎo)方式下的啟發(fā)式算法設(shè)計。在不允許擴容的場景下，在端到端疏導(dǎo)方式下，鏈路權(quán)重設(shè)計考慮了最小跳和負載均衡兩種方式；在多跳疏導(dǎo)方式下，鏈路權(quán)重設(shè)計除了考慮最小跳和負載均衡之外，還考慮了上下層資源的聯(lián)合優(yōu)化設(shè)計。應(yīng)該減少FA的數(shù)目，且通過分析在計算下層需要保護的業(yè)務(wù)時，上層工作路徑的選取對總的使用資源的影響，可以看出，上下層資源的聯(lián)合優(yōu)化設(shè)計可以有效的減少總的使用資源。仿真數(shù)據(jù)的對比分析表明了多跳疏導(dǎo)方式下啟發(fā)