約束路由及動態(tài)業(yè)務量疏導算法研究與實現(xiàn).pdf

1、目前，在廣域網(wǎng)上進行大規(guī)模實時視頻傳輸已成為可能。對于傳統(tǒng)的IP網(wǎng)絡，實施的路由策略集中于建立端到端的連接，并且一般只考慮一種服務數(shù)據(jù)結(jié)構(gòu)。而高速多媒體應用具有不同的性能需求諸如帶寬、延遲、延遲抖動、損失率和必經(jīng)/禁忌等。QoS的概念被用來描述服務提供者和用戶應用程序之間的性能約定，QoS需求體現(xiàn)為一系列網(wǎng)絡約束條件，如鏈路約束或端到端的加性約束等。Qos路由是一種具有雙重目標的路由機制：尋找滿足約束條件的路徑同時有效利用網(wǎng)絡資源，因此

2、QoS路由問題可歸結(jié)為尋找路徑在滿足約束條件的同時優(yōu)化某種特定的代價函數(shù)。這類問題可以用ILP建模求解，但隨著網(wǎng)絡規(guī)模的增加，求解時間會變得無法接受，所以，本文集中研究如何利用啟發(fā)式算法解決現(xiàn)有約束路由中存在的問題。 本文第二章首先從多加性約束路由計算出發(fā)，研究并實現(xiàn)了多種k路由算法，分析對比性能，指出各種不同算法不同的應用場景和改進措施。必經(jīng)點/必經(jīng)鏈路約束是較常見的策略約束，目前尚未有成熟算法在保證低時間復雜度基礎上達到較好

3、性能。本文提出了一種基于分割和迭代的必經(jīng)點/必經(jīng)鏈路約束路由算法，仿真結(jié)果表明該算法具有較好的性能且時間復雜度較低。在此基礎之上，本文提出了可支持多分離原則的多約束多分離路徑算法，可有效支持計算節(jié)點分離、鏈路分離和SRLG分離等，比APF等傳統(tǒng)算法的成功率提高很多，可用于大網(wǎng)絡下的多點失效問題如1+1+shared保護等場景。 本文第三章主要研究在基于PCE環(huán)境下的域間多約束路由計算問題。傳統(tǒng)的基于PCE的BRPC算法在求解域問

4、路由時過分追求源目之間的最優(yōu)路徑，而使得算法易陷入路由陷阱。本文提出了一種新的求解域間路由的框架，將域間約束路由計算分為正向約束傳遞過程和反向約束路由計算過程，從而有效的將約束合理的分配到各域，該方法能有效解決多域中路由陷阱問題，提高域問路由成功率。 針對兩層網(wǎng)絡中動態(tài)業(yè)務批量到達的業(yè)務選路問題，本文在第四章提出了一種基于業(yè)務持續(xù)時間的啟發(fā)式算法。該算法在繼承已有算法在均勻業(yè)務模型下低阻塞率的優(yōu)點基礎之上，還有效的解決了在非均勻