服務質(zhì)量(QoS)路由理論與實現(xiàn)的核心問題.ppt

1、清華大學計算機科學系、中國人民解放軍炮兵學院博士后副教授崔訓學是QoS路由理論與實現(xiàn)的核心問題。首先，問題的背景。第二，過去不成熟的解決方案。第三，核心問題。第四，研究展望，議程。首先，問題的背景是，當前的互聯(lián)網(wǎng)只能提供盡力而為的交付服務，而網(wǎng)絡層不能區(qū)分用戶服務的類型，而是公平地為各種服務提供網(wǎng)絡資源。在丟包率和延遲等方面。這種機制使得網(wǎng)絡層無法控制傳輸質(zhì)量。因此，為不同的應用提供不同的服務質(zhì)量是互聯(lián)網(wǎng)面臨的一個重要研究課題。如果服務質(zhì)量路由(MCP)真正在網(wǎng)絡上實現(xiàn)，網(wǎng)絡將實現(xiàn)良好的負載平衡，當前流量工程中的許多問題將很容易解決。目前的研究結(jié)果表明，通過合理配置區(qū)域內(nèi)基于鏈路狀態(tài)的服務質(zhì)量

2、路由協(xié)議，支持服務質(zhì)量的成本是可以接受的。因此，在當前的互聯(lián)網(wǎng)上實現(xiàn)服務質(zhì)量一般是可行的。第二，IntServ是過去不成熟的解決方案，是最早提出的實現(xiàn)網(wǎng)絡服務質(zhì)量的框架，它具有面向連接和資源預留的特點。面向連接的機制會導致核心路由器維護的信息爆炸，降低可擴展性；資源預留機制會導致網(wǎng)絡利用率的降低和成本的增加。因此，綜合業(yè)務框架類似于電信網(wǎng)絡，違背了互聯(lián)網(wǎng)的基本機制，在大規(guī)?；ヂ?lián)網(wǎng)環(huán)境下綜合業(yè)務是不可行的。為了提高網(wǎng)絡傳輸?shù)目蓴U展性，人們提出了區(qū)分服務(DiffServ)框架，通過分簇來解決綜合業(yè)務所面臨的可擴展性問題。然而，差異化服務框架不能區(qū)分參數(shù)類型，也不能從根本上提供服務質(zhì)量?，F(xiàn)有的服務

3、質(zhì)量路由研究往往是面向連接的，擴展性差。升級路由的最好方法是在現(xiàn)有互聯(lián)網(wǎng)的基礎上實現(xiàn)無連接逐跳路由。然而，先前的研究已經(jīng)證明，尋找滿足多個約束的可行路徑具有NPC復雜性。人們對這個問題已經(jīng)做了大量的研究，相關的啟發(fā)式路由算法也比較成熟。然而，當啟發(fā)式路由算法被實現(xiàn)時，它在集成服務框架中提供服務質(zhì)量。這意味著將采用面向連接的方法，并且需要資源預留。因此，這個系統(tǒng)將像綜合服務一樣不可行。目前，最好的啟發(fā)式服務質(zhì)量路由算法是MCOP算法。它的復雜性非常低；找到可行解的成功率接近精確算法。第三，核心問題，服務質(zhì)量路由包括兩個部分：協(xié)議和算法。目前，這兩個方面的研究存在嚴重不足。具有多個附加度量的服務質(zhì)

4、量路由被證明是NP完全問題。這個定理極大地影響了研究機構(gòu)，這導致人們普遍認為準確的路由在實踐中是不可行的。因此，出現(xiàn)了許多啟發(fā)式算法來解決這個問題。然而，很少有人認真分析過哪些最壞的情況會導致NPC行為。實際上，MCP問題不是強NPC問題，這表明精確算法可以在多項式時間內(nèi)求解。另外，人們在實際網(wǎng)絡中很少遇到網(wǎng)絡傳輸?shù)腘P-C行為。在大多數(shù)實際網(wǎng)絡中，服務質(zhì)量路由問題是否不能在多項式時間內(nèi)解決，需要進一步研究。1996年，王和克羅夫特證明了當約束數(shù)大于或等于2時，服務質(zhì)量路由問題是NP完全的。他們主要將帶有兩個約束的主成分分析問題歸結(jié)為一個典型的NP完全問題分割問題。但是一些實驗表明事實并非如此

5、。一類問題，包括分割問題，已經(jīng)被許多人證明是可以解決的。目前，有偽多項式算法來解決路由問題。至少有三種情況在多項式時間內(nèi)是可解的。(1)服務質(zhì)量參數(shù)是相關的，也就是說，如果所有參數(shù)都與某個度量相關，則可以在多項式時間內(nèi)求解。(2)如果服務質(zhì)量參數(shù)中除一個以外都是有界整數(shù)，這類問題可以用擴展的迪克斯特拉算法或貝爾曼-福特算法在多項式時間內(nèi)求解。(3)微通道板問題不是一個強NP完全問題，因為偽多項式算法已經(jīng)被用來精確地求解這個問題。在我看來，路由協(xié)議是目前實現(xiàn)服務質(zhì)量的關鍵。然而，這方面的探索很少，而且研究起來比研究算法要困難得多。(1)協(xié)議問題；(4)研究前景：在面向連接的網(wǎng)絡中，路由協(xié)議(自動

6、柜員機中的PNNI)已經(jīng)標準化，但在無連接網(wǎng)絡(互聯(lián)網(wǎng))中，沒有服務質(zhì)量路由協(xié)議的標準。域內(nèi)路由協(xié)議相對容易升級，但域間BGP-4協(xié)議很難升級到服務質(zhì)量路由協(xié)議。目前，無連接網(wǎng)絡沒有可行的服務質(zhì)量路由協(xié)議。因此，研究的重點應該適當?shù)貜乃惴ㄞD(zhuǎn)向協(xié)議。(2)可擴展性?；谌譅顟B(tài)和源路由的協(xié)議和算法的可擴展性較差。雖然網(wǎng)絡狀態(tài)聚合可以將信息量以對數(shù)形式減少，使得相應的分層路由解決了可擴展性問題，但也帶來了一個新問題：目前設計的狀態(tài)聚合方法往往會丟失大量可用信息，嚴重影響性能。隨著網(wǎng)絡規(guī)模的擴大，可擴展性一直是網(wǎng)絡研究的話題。當前和未來的路由體系結(jié)構(gòu)都必須采用分層模型。層次結(jié)構(gòu)的目的是壓縮和聚合網(wǎng)絡

7、狀態(tài)信息，但是壓縮和聚合會導致網(wǎng)絡狀態(tài)信息的丟失。如何從根本上解決這一矛盾，提高路由算法的性能也是一個重要的研究方向。通常，需要模擬實驗來評估所設計的算法或協(xié)議，這需要一定的網(wǎng)絡拓撲和服務流模型。目前，有幾種常用的拓撲模型：1)采用眾所周知的拓撲結(jié)構(gòu)，如ARPAnet網(wǎng)絡；2)隨機生成拓撲結(jié)構(gòu)，例如平面隨機圖；3)特定規(guī)則的結(jié)構(gòu)，如網(wǎng)格結(jié)構(gòu)。根據(jù)實際網(wǎng)絡的研究結(jié)果，目前還沒有“典型”的網(wǎng)絡拓撲和流量模型來指導路由的研究。(3)拓撲模型。目前，互聯(lián)網(wǎng)已經(jīng)有了相當大的規(guī)模。徹底取代現(xiàn)有的盡力而為的IPv4網(wǎng)絡將是一個漫長而艱巨的過程。未來的網(wǎng)絡應該是服務質(zhì)量路由和盡力傳輸?shù)慕Y(jié)合。從目前狀態(tài)分析，改

8、造過程應采用覆蓋模式，即在新增加的網(wǎng)絡設備中逐步增加具有服務質(zhì)量功能的路由器，或者逐步更換原有設備。因此，基于覆蓋的理論框架和核心算法設計是實際應用中的一個重要問題。(4)實施模式，中國學者閔華英指出，目前理論界對網(wǎng)絡基礎研究存在兩個思想障礙：一是認為互聯(lián)網(wǎng)上路由器的硬件和軟件已經(jīng)形成，不太可能改變，骨干網(wǎng)上的核心路由器技術完全被思科等國外大公司所控制。這種觀點只來自于工程技術發(fā)展的角度，只看到了目前國內(nèi)的情況。(5)理論研究的重要性從自然科學基礎研究的角度來看，如果國內(nèi)研究人員受現(xiàn)有協(xié)議和RFC的約束，很難看到原創(chuàng)作品的價值和意義。只有當基礎研究工作做得充分而扎實，突破了現(xiàn)有的或不完善的國際協(xié)定和草案，并能實際轉(zhuǎn)化為應用時，工業(yè)部門將不可避免地接受這些理論成果。另一個是人們對實用性的誤