發(fā)布時(shí)間：2020-11-19 17:06

　　 業(yè)務(wù)量工程(Traffic Engineering)能夠通過為業(yè)務(wù)選擇合理的網(wǎng)絡(luò)路由來達(dá)到充分利用網(wǎng)絡(luò)資源、提高網(wǎng)絡(luò)性能、滿足Qos需求等目的。在SDN網(wǎng)絡(luò)中,集中式的SDN控制器能夠在全局拓?fù)渖线M(jìn)行業(yè)務(wù)量工程,提高業(yè)務(wù)量工程的優(yōu)化效果。然而,由于互聯(lián)網(wǎng)應(yīng)用的快速增加,短時(shí)間內(nèi)會(huì)有大量業(yè)務(wù)到達(dá)SDN網(wǎng)絡(luò),同時(shí),SDN網(wǎng)絡(luò)的規(guī)模也相應(yīng)增大,這要求SDN控制器能在短時(shí)間內(nèi)在大網(wǎng)絡(luò)拓?fù)渖蠟榇罅繕I(yè)務(wù)計(jì)算路由,業(yè)務(wù)量工程的計(jì)算面臨著時(shí)間上的挑戰(zhàn)。所以,為了縮短SDN控制器的計(jì)算時(shí)間,本文利用GPU的強(qiáng)大并行計(jì)算能力來加速業(yè)務(wù)量工程算法。針對(duì)SDN IP網(wǎng)絡(luò),本文首先將業(yè)務(wù)量工程問題建模成一個(gè)帶鏈路容量約束的MILP模型。為了求解這個(gè)模型,本文設(shè)計(jì)了兩種并行算法GA-PTEA(Genetic Algorithm Based Parallel Traffic Engineering Algorithm)和LR-PTEA(Lagrange Relaxing Based Parallel Traffic Engineering Algorithm)。其中,GA-PTEA將原來的業(yè)務(wù)量工程模型簡(jiǎn)化為基于備選路徑的業(yè)務(wù)量工程模型,利用并行的遺傳算法來求解業(yè)務(wù)量工程問題,并行加速比可達(dá)到10倍以上。LR-PTEA則采用了拉格朗日松弛的方法,首先通過松弛鏈路容量約束,將業(yè)務(wù)量工程問題分解為一批業(yè)務(wù)的最短路徑計(jì)算問題,然后設(shè)計(jì)了基于GPU的并行算法來加速最短路的計(jì)算。LR-PTEA使用次梯度下降方法來求解拉格朗日對(duì)偶問題,為了加快次梯度算法的收斂速度,LR-PTEA采用了高效的次梯度步長(zhǎng)更新方法,同時(shí),LR-PTEA在求解對(duì)偶問題的過程中采用了快速的路徑調(diào)整策略來獲得對(duì)原問題目標(biāo)函數(shù)的可行解。本文的實(shí)驗(yàn)發(fā)現(xiàn)基于GPU的LR-PTEA并行算法可以在短時(shí)間內(nèi)得到業(yè)務(wù)量工程問題的優(yōu)化解,與串行算法LR-STEA(Lagrange Relaxing Based Serial Traffic Engineering Algorithm)相比,加速比可達(dá)到10倍以上。在SDN彈性光網(wǎng)絡(luò)中,首先,為了簡(jiǎn)化頻譜分配問題,本文采用分層圖模型將彈性光網(wǎng)絡(luò)中的頻譜分配問題轉(zhuǎn)化為路由選擇問題。其次,為了優(yōu)化彈性光網(wǎng)絡(luò)中業(yè)務(wù)的路由代價(jià),減少資源使用,降低阻塞率,本文設(shè)計(jì)了TESAA(Traffic Engineering and Spectrum Allocate Algrithm)優(yōu)化算法。最后,為了縮短SDN控制器的計(jì)算時(shí)間,我們對(duì)TESAA進(jìn)行并行加速,分別針對(duì)無權(quán)圖和帶權(quán)圖設(shè)計(jì)了基于GPU的并行路由算法。實(shí)驗(yàn)發(fā)現(xiàn)TESAA可以大大減小路由的代價(jià)、節(jié)省網(wǎng)絡(luò)資源和有效降低業(yè)務(wù)的阻塞率,基于GPU的并行算法PTESAA(Parallel TESAA)與串行算法STESAA(Serial TESAA)相比,加速比可達(dá)到10倍以上。
【學(xué)位單位】：電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：TP393.0
【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 研究背景與意義
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
        1.2.1 SDNIP網(wǎng)絡(luò)下業(yè)務(wù)量工程算法的研究現(xiàn)狀
        1.2.2 SDN彈性光網(wǎng)絡(luò)下業(yè)務(wù)量工程算法的研究現(xiàn)狀
    1.3 論文內(nèi)容及結(jié)構(gòu)安排
第二章 GPU硬件結(jié)構(gòu)與CUDA編程模式
    2.1 CPU與GPU
        2.1.1 CPU與GPU區(qū)別
        2.1.2 CPU+GPU異構(gòu)計(jì)算模型
    2.2 GPU硬件架構(gòu)
        2.2.1 流處理器
        2.2.2 線程束（Warp）
        2.2.3 存儲(chǔ)結(jié)構(gòu)
        2.2.4 流多處理器細(xì)節(jié)
        2.2.5 執(zhí)行模型
    2.3 CUDA編程模式
        2.3.1 CUDA軟件線程組織
        2.3.2 kernel函數(shù)
        2.3.3 CUDA線程同步
        2.3.4 CUDA流并行
    2.4 本章總結(jié)
第三章 SDNIP網(wǎng)絡(luò)下的并行業(yè)務(wù)量工程算法研究
    3.1 引言
    3.2 網(wǎng)絡(luò)模型和問題建模
        3.2.1 網(wǎng)絡(luò)模型
        3.2.2 問題建模
    3.3 基于遺傳算法的業(yè)務(wù)量工程算法
        3.3.1 備選路模型
        3.3.2 遺傳算法設(shè)計(jì)
            3.3.2.1 染色體結(jié)構(gòu)
            3.3.2.2 初始可行解的生成
            3.3.2.3 評(píng)價(jià)與排序
            3.3.2.4 交叉
            3.3.2.5 變異
            3.3.2.6 終止條件
        3.3.3 基于GPU的并行遺傳算法設(shè)計(jì)
            3.3.3.1 并行評(píng)價(jià)算法設(shè)計(jì)
            3.3.3.2 并行排序,變異與交叉
    3.4 基于拉格朗日的優(yōu)化算法設(shè)計(jì)
        3.4.1 基于拉格朗日松弛的模型
        3.4.2 基于GPU的并行路由計(jì)算
        3.4.3 鏈路權(quán)重更新
            3.4.3.1 權(quán)重更新步長(zhǎng)
            3.4.3.2 隨機(jī)更新策略
        3.4.4 路徑調(diào)整
        3.4.5 終止條件
    3.5 仿真實(shí)驗(yàn)分析
        3.5.1 仿真介紹
        3.5.2 目標(biāo)函數(shù)比較
        3.5.3 算法時(shí)間比較
        3.5.4 算法收斂性
    3.6 本章總結(jié)
第四章 SDN彈性光網(wǎng)絡(luò)下的并行業(yè)務(wù)量工程算法研究
    4.1 引言
    4.2 分層圖模型
    4.3 分層圖模型下的業(yè)務(wù)量工程算法
    4.4 無權(quán)圖情況下的GPU算法設(shè)計(jì)
        4.4.1 相同速率業(yè)務(wù)的并行
        4.4.2 不同速率間業(yè)務(wù)的并行
        4.4.3 GPU上的kernel設(shè)計(jì)
    4.5 帶權(quán)圖情況下的GPU算法設(shè)計(jì)
        4.5.1 帶跳數(shù)限制的最短路算法
        4.5.2 相同速率業(yè)務(wù)的動(dòng)態(tài)規(guī)劃算法并行
        4.5.3 不同速率間業(yè)務(wù)的并行
        4.5.4 GPU上的kernel設(shè)計(jì)
    4.6 實(shí)驗(yàn)仿真分析
        4.6.1 對(duì)比算法
        4.6.2 實(shí)驗(yàn)設(shè)置
        4.6.3 無權(quán)圖下的仿真結(jié)果
            4.6.3.1 路由跳數(shù)優(yōu)化結(jié)果分析
            4.6.3.2 時(shí)間分析
            4.6.3.3 阻塞率分析
        4.6.4 帶權(quán)圖下的仿真結(jié)果
            4.6.4.1 路由代價(jià)優(yōu)化結(jié)果分析
            4.6.4.2 時(shí)間分析
    4.7 本章總結(jié)
第五章 全文總結(jié)與展望
    5.1 全文總結(jié)
    5.2 后續(xù)工作展望
致謝
參考文獻(xiàn)
攻讀碩士學(xué)位期間取得的成果

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王超逸;;關(guān)于網(wǎng)絡(luò)分層信息泄露點(diǎn)快速檢測(cè)仿真[J];計(jì)算機(jī)仿真;2018年06期

2 侯凌燕;;網(wǎng)絡(luò)分層級(jí)算法在公路網(wǎng)絡(luò)中的應(yīng)用[J];北京信息科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年06期

3 楊冬;張宏科;宋飛;李世勇;;網(wǎng)絡(luò)分層優(yōu)先映射理論[J];中國(guó)科學(xué):信息科學(xué);2010年05期

4 李麗娟;樊林京;焦俊黨;;基于核心企業(yè)的網(wǎng)絡(luò)分層探究——以鄭州宇通客車為例[J];農(nóng)村經(jīng)濟(jì)與科技;2014年03期

5 黃和建;;GSM網(wǎng)900M/1800M網(wǎng)絡(luò)分層研究[J];移動(dòng)通信;2009年16期

6 劉彥婷;南作用;;從網(wǎng)絡(luò)仿真看LTE網(wǎng)絡(luò)分層結(jié)構(gòu)部署[J];郵電設(shè)計(jì)技術(shù);2015年10期

7 李明輝;夏靖波;陳才強(qiáng);;基于網(wǎng)絡(luò)分層譜系模型的綜合評(píng)估方法[J];中南大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年03期

8 宋鑫;SDH網(wǎng)絡(luò)分層[J];北京電信科技;1994年02期

9 張明星;楊垚;程光權(quán);劉忠;;目標(biāo)網(wǎng)絡(luò)分層描述與自修復(fù)機(jī)制研究[J];指揮控制與仿真;2016年06期

10 費(fèi)孔鶴;;引入層的介紹[J];信息通信;2012年02期

相關(guān)碩士學(xué)位論文 前8條

1 張騫;基于GPU的SDN網(wǎng)絡(luò)并行業(yè)務(wù)量工程算法研究[D];電子科技大學(xué);2018年

2 侯杰;一個(gè)基于領(lǐng)域知識(shí)的復(fù)雜網(wǎng)絡(luò)演化模型[D];哈爾濱工程大學(xué);2014年

3 杜常數(shù);面向DCI網(wǎng)絡(luò)流量調(diào)度方案的設(shè)計(jì)與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2017年

4 張貝;基于物理分層結(jié)構(gòu)的大規(guī)模Ad Hoc網(wǎng)絡(luò)分層協(xié)議的研究[D];西安電子科技大學(xué);2008年

5 劉海紅;基于復(fù)雜網(wǎng)絡(luò)統(tǒng)計(jì)特性的非線性時(shí)間序列分析方法研究[D];濟(jì)南大學(xué);2017年

6 郭鵬飛;光網(wǎng)絡(luò)核心節(jié)點(diǎn)交換矩陣與管控技術(shù)研究[D];北京郵電大學(xué);2014年

7 徐一鳴;水下無線傳感器網(wǎng)絡(luò)覆蓋控制策略與算法研究[D];杭州電子科技大學(xué);2017年

8 仇亞駿;面向數(shù)據(jù)中心的軟件定義光網(wǎng)絡(luò)資源調(diào)度研究[D];北京郵電大學(xué);2017年

本文編號(hào)：2890237