約束路由及動(dòng)態(tài)業(yè)務(wù)量疏導(dǎo)算法研究與實(shí)現(xiàn).pdf

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

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

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

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