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

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

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

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

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

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