軟件定義網(wǎng)絡(luò)與網(wǎng)絡(luò)功能虛擬化是當前的研究熱門方向。通過將軟件定義網(wǎng)絡(luò)與網(wǎng)絡(luò)功能虛擬化技術(shù)相結(jié)合雖然能夠為運營商提供便捷高效靈活的管理模式,但是對中間盒不合理的部署將會影響到對數(shù)據(jù)包路由的規(guī)劃,進而還是為運營商帶來了不必要的路由成本。該文在此基礎(chǔ)上研究了在單播和多播中受多目標約束的聯(lián)合中間盒部署與路由問題以優(yōu)化總路由成本。首先該文針對中間盒的依賴關(guān)系約束、鏈路帶寬約束來最小化路由成本,首次提出聯(lián)合優(yōu)化虛擬中間盒部署與路由問題,并證明了該問題是NP-hard。該路由成本包括了鏈路傳輸成本與中間盒部署成本。之后設(shè)計一種面向小型拓撲網(wǎng)絡(luò)的服務(wù)鏈感知精準算法（Service Chain Aware Exact Algorithm,SCAEA）,該算法可以根據(jù)給定的中間盒依賴關(guān)系和鏈路帶寬約束條件較快地計算出最優(yōu)的中間盒部署方案,并規(guī)劃出成本最低的路由。在實驗仿真部分通過與混合整數(shù)線性規(guī)劃數(shù)學(xué)模型所求得的最優(yōu)解進行對比后,驗證了SCAEA的有效性,并具有良好的應(yīng)用前景。考慮到問題的復(fù)雜性,該文之后也是首次研究了多播中的中間盒的有序約束、時延約束來最小化總路由成本問題,提出一種近似比為O（k）的受時... 

【文章來源】：合肥工業(yè)大學(xué)安徽省 211工程院校 教育部直屬院校

【文章頁數(shù)】：63 頁

【學(xué)位級別】：碩士

【部分圖文】：

(a)信源樹

樹的；PIM-DM通過泛洪多播數(shù)據(jù)包并剪除來定期更新多播樹；MOSPF通過將組成員信息分發(fā)給所有具有多播功能的路由器來構(gòu)建多播樹。傳統(tǒng)多播是由具有多播功能的路由器維護的，并通過其實現(xiàn)數(shù)據(jù)流的轉(zhuǎn)發(fā)和路由到相應(yīng)的多個接收方。目前IP網(wǎng)絡(luò)下的多播轉(zhuǎn)發(fā)樹主要是以信源樹(SourceBasedTree,SBT)和核心轉(zhuǎn)發(fā)樹(CoreBasedTree,CBT)這兩種形式存在[35]。SBT協(xié)議通過使用相鄰路由器間的已知信息來構(gòu)建從多播源點到各個目的點間的最短路徑，從而形成以源點到目的點的最短路徑樹(ShortestPathTree,SPT)，有利于對時延敏感的通信，如圖2.2(a)。但是這種多播轉(zhuǎn)發(fā)樹的構(gòu)造方式需要要求網(wǎng)絡(luò)中的每個路由器都必須為每個多播組和源點保留狀態(tài)信息[3]，這無疑大大增加了路由器的額外存儲負擔，導(dǎo)致多播轉(zhuǎn)發(fā)樹的伸縮性受到嚴重的約束。CBT協(xié)議通過將一個大的自治區(qū)域劃分為幾個小區(qū)域，并且為每一個小區(qū)域設(shè)置一個匯聚點，這樣可以實現(xiàn)從源點到各個匯聚點，再從各個匯聚點到各個區(qū)域內(nèi)的目的點間的轉(zhuǎn)發(fā)和路由，如圖2.2(b)所示。雖然CBT是通過分治的方式將多播組劃分為多個小組，降低了路由器的存儲負擔，但是這也明顯增加路由數(shù)據(jù)包在鏈路上的傳輸成本。在圖論中，最佳生成樹是Steiner樹，但是該問題屬于NPC[37-38]，這意味著不可能存在時間復(fù)雜度為多項式時間的精準算法來構(gòu)造該生成樹。另一方面，Steiner樹的構(gòu)造需要掌握完整的網(wǎng)絡(luò)拓撲信息，而傳統(tǒng)網(wǎng)絡(luò)中的每個路由器只能通過“下一跳”的方式來獲取相鄰路由器的信息，也就是說每個路由器它只能掌握到局部網(wǎng)絡(luò)拓撲信息，因此難以將其部署在實際應(yīng)用中。圖2.2(a)信源樹Fig2.2(a)Sourcebasedtree.圖2.2(b)核心轉(zhuǎn)發(fā)樹Fig2.2(b)Corebasedtree.圖2.2SBT與CBT示意圖Fig2.2SBTandCBTschematicdiagram.

合肥工業(yè)大學(xué)碩士學(xué)位論文41RPA)作為對比。對于每一條靜態(tài)多播請求的生成，我們在網(wǎng)絡(luò)拓撲中隨機挑選出一個交換機作為源節(jié)點，再挑選出V個交換機作為目的節(jié)點。此外，需要保證源節(jié)點與目的節(jié)點不重合，以及源點到各個目的節(jié)點必須是連通的。4.6.2實驗結(jié)果(1)服務(wù)鏈長度對算法DSCMRA性能的影響。本實驗采用真實的網(wǎng)絡(luò)拓撲圖newyork(|V|=16,|E|=49)[54]，將設(shè)置為0.3，服務(wù)鏈長度取值為{1,2,3,4,5}。在圖4.5(a)中，當服務(wù)鏈長度為3時，算法DSCMRA所得出的近似路由成本比GLPK得出的最優(yōu)解平均只略高出2.5%；當服務(wù)鏈長度為5時，近似解平均比最優(yōu)解只略高出3.0%。此外，該圖也展示出了，隨著服務(wù)鏈的增長，即中間盒個數(shù)的增多，DSCMRA的近似解始終接近于最優(yōu)解。在圖4.5(b)中，隨著服務(wù)鏈長度的增長，DSCMRA始終在指定時延內(nèi)將100條多播請求全部都路由成功，成功率達到100%。而RPA的請求成功率呈下降的趨勢，例如當服務(wù)鏈長度為5時，其路由成功的請求只有68條，成功率只為68%。因此隨著服務(wù)鏈長度的增長，即中間盒數(shù)量增加，DSCMRA可以在獲取較低的路由成本的同時，能夠保持較高的請求成功率。圖4.5(a)服務(wù)鏈長度對路由成本的影響Fig4.5(a)Impactofservicechainlengthonroutingcosts.圖4.5(b)服務(wù)鏈長度對請求成功的影響Fig4.5(b)Impactofservicechainlengthonrequestsuccessrate.圖4.5服務(wù)鏈長度對算法的影響Fig4.5Impactofservicechainlengthonalgorithm.(2)目的節(jié)點個數(shù)對算法DSCMRA性能的影響。本實驗也是采用newyork(|V|=16,|E|=49)作為真實網(wǎng)絡(luò)拓撲，并將服務(wù)鏈長度設(shè)置為3，的取值為{0.1,0.2,0.3,0.4,0.5}，由于DSCMRA的近似比為O(k)，因此，隨著目的節(jié)點個數(shù)的增加，可能會對該算法的性能產(chǎn)生一定的影響。在圖4.6(a)中?

【參考文獻】：
期刊論文
[1]一種面向運營成本優(yōu)化的虛擬網(wǎng)絡(luò)功能部署和路由分配策略[J]. 史久根,張徑,徐皓,王繼,孫立.  電子與信息學(xué)報. 2019(04)
[2]面向多業(yè)務(wù)需求的NFV和SDN融合的資源優(yōu)化算法[J]. 朱曉榮,張倩.  通信學(xué)報. 2018(11)
[3]基于服務(wù)質(zhì)量與資源約束的服務(wù)鏈部署策略[J]. 海梅生,伊鵬,江逸茗.  計算機工程. 2019(03)
[4]基于OpenFlow的SDN技術(shù)研究[J]. 左青云,陳鳴,趙廣松,邢長友,張國敏,蔣培成.  軟件學(xué)報. 2013(05)



本文編號：3558765