多業(yè)務量矩陣下TE算法性能研究.pdf

1、近十年來，Internet得到了引人注目的發(fā)展。隨著Internet的快速發(fā)展，網(wǎng)絡規(guī)模和業(yè)務量急速增長，用戶對網(wǎng)絡性能的要求也越來越高，這對網(wǎng)絡服務商提出了嚴峻的挑戰(zhàn)，如何滿足客戶的需求迫在眉睫。流量工程應運而生。流量工程是一種具有重要價值的網(wǎng)絡優(yōu)化技術，它通過優(yōu)化網(wǎng)絡資源的利用率來避免網(wǎng)絡擁塞。傳統(tǒng)的流量工程算法針對的均為精確的業(yè)務量矩陣，通過多商品流問題就可以解決。實際上要想精確的獲取業(yè)務量信息是很困難的，對于規(guī)模巨大的Inter

2、net，其業(yè)務又時常改變，在動態(tài)改變的業(yè)務量矩陣或不確定業(yè)務量矩陣的環(huán)境中尋找一組有效的，魯棒的路由方案是很多大型ISP網(wǎng)絡運營商不得不關注的問題。這種動態(tài)性或不確定性可以用多個業(yè)務量矩陣來表示，也即多業(yè)務量矩陣下流量工程的求解。
　　 本文主要研究的是多業(yè)務量矩陣中TE算法相關問題。第二章主要討論了多業(yè)務量矩陣TE算法中性能指標問題，主要包含了最差性能，平均性能以及它們之間的折中性能，通過設計平均性能與最差性能權重和因子來控制

3、折中性能，并發(fā)現(xiàn)利用該因子獲得的最優(yōu)化問題具有某些特殊的特性，即平均性能是折中因子的非遞減連續(xù)函數(shù)，最差性能是折中因子的非遞增連續(xù)函數(shù)。并強調了后面章節(jié)考慮的性能指標是最差性能。第三章為基于OSPF/IS-IS多業(yè)務量矩陣下TE算法的研究，首先討論了單業(yè)務量矩陣下的基于OSPF/IS-IS路由優(yōu)化的問題，傳統(tǒng)算法均為NP-hard問題，然后擴展到多業(yè)務量矩陣下的路由優(yōu)化，設計了多套不同的啟發(fā)式算法來求解。并著重分析了其中一種算法的性能因

4、子，并發(fā)現(xiàn)該算法中K最短路算法K的取值，迭代次數(shù)對算法性能有很大的影響。第四章討論了采用ECMP分流機制下多業(yè)務量矩陣算法的研究。也是從單業(yè)務量矩陣最優(yōu)化擴展而來，設計了多套算法，并著重分析其中一種算法的性能因子。第五章首先討論了多業(yè)務量矩陣下如何求解滿足運營商性能要求的路由方案，通過設計一種啟發(fā)式算法用于求解一套滿足要求的方案。當一套路由不能滿足要求時，則需使用多套路由方案，然后著重分析了在多套路由下如何通過監(jiān)控最少的鏈路信息最快的切