高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)課件

高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)2022/12/31史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)2022/12/21史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要7.1概述7.2現(xiàn)代通信中的排隊(duì)理論7.3現(xiàn)代通信業(yè)務(wù)的自相似特性7.4擁塞控制7.5通信量控制7.6ABR通信量管理

2022/12/32史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要7.1概述2022/12/22史忠植高級(jí)計(jì)算機(jī)7.1概述高速網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵是對(duì)性能參數(shù)的進(jìn)行建模和估計(jì)的能力。設(shè)計(jì)者需要有能力在觀察到的通信量的基礎(chǔ)上估計(jì)未來(lái)的通信量的大小和特性。通信量的統(tǒng)計(jì)特性對(duì)很多類設(shè)計(jì)和配置問(wèn)題都有影響,這些問(wèn)題包括資源預(yù)留協(xié)議,在路由器和ATM交換機(jī)上使用的排隊(duì)規(guī)則和緩存大小。另外,為了做出明智的資源預(yù)留決定,用戶也需要能夠?qū)τ?jì)劃的通信量特性進(jìn)行描述。對(duì)描述數(shù)據(jù)通信量而言由許多參數(shù)很重要。2022/12/33史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.1概述2022/12/23史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性平均速率:信源提供的平均負(fù)載對(duì)于確定分配給該信源的總量是十分關(guān)鍵的。平均速率表示信源在較長(zhǎng)的時(shí)間里持續(xù)發(fā)出的流量。

2022/12/34史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性平均速率:2022/12/24史忠植高級(jí)計(jì)算機(jī)吞吐量特性峰值速率這個(gè)參數(shù)告訴網(wǎng)絡(luò)通信量最大的速率是多少,以便網(wǎng)絡(luò)能夠通過(guò)預(yù)留足夠的數(shù)據(jù)傳輸容量和緩存空間接納此通信量。2022/12/35史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性峰值速率2022/12/25史忠植高級(jí)計(jì)算機(jī)網(wǎng)吞吐量特性可變性

峰值是可變性的一種度量;一種更直接的度量是吞吐量的變化?？勺冃院饬恳粋€(gè)信源的突發(fā)性,它是統(tǒng)計(jì)復(fù)用被用于提高資源利用效率的程度的一個(gè)度量。2022/12/36史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性可變性2022/12/26史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)時(shí)延特性傳輸時(shí)延

這個(gè)參數(shù)度量的是數(shù)據(jù)從信源到目的地的過(guò)程中網(wǎng)絡(luò)所施加的時(shí)延。最大傳輸時(shí)延也常常被應(yīng)用程序作為一項(xiàng)需求提出來(lái)。2022/12/37史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)時(shí)延特性傳輸時(shí)延2022/12/27史忠植高級(jí)計(jì)算機(jī)網(wǎng)時(shí)延特性時(shí)延偏差傳輸時(shí)延的偏差大小是實(shí)時(shí)應(yīng)用的一個(gè)重要參數(shù),在實(shí)時(shí)應(yīng)用中目的端應(yīng)該以平滑連續(xù)的速率播放收到的數(shù)據(jù),該速率與信源產(chǎn)生的速率匹配。這些以及相似的參數(shù)對(duì)于網(wǎng)絡(luò)配2022/12/38史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)時(shí)延特性時(shí)延偏差2022/12/28史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)性能分析排隊(duì)分析提供了一個(gè)簡(jiǎn)單的,容易處理的方法來(lái)得到有用的結(jié)果,這些結(jié)果可以用來(lái)知道網(wǎng)絡(luò)的設(shè)計(jì)和擴(kuò)展。幾十年來(lái),基于泊松通信量假設(shè)的排隊(duì)分析一直是網(wǎng)絡(luò)性能分析人員的應(yīng)用工具。然而,近些年出現(xiàn)了一個(gè)對(duì)于大家來(lái)講是驚人的結(jié)果:至少在某些情況下,數(shù)據(jù)通信量實(shí)質(zhì)上不是泊松分布的而是自相似(self-similar)或分形(fractal)的。對(duì)于這種通信量,網(wǎng)絡(luò)的性能不能再用排隊(duì)分析的清楚的公式來(lái)描述,網(wǎng)絡(luò)的時(shí)延比預(yù)期的更大,吞吐量更低。自從最初的發(fā)現(xiàn)之后,對(duì)于許多的通信量類型自相似的結(jié)果被證實(shí)了很多次。2022/12/39史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)性能分析排隊(duì)分析提供了一個(gè)簡(jiǎn)單的,容易處理的方法來(lái)得到有7.2現(xiàn)代通信中的排隊(duì)理論排隊(duì)理論也稱為隨機(jī)服務(wù)理論，是現(xiàn)代運(yùn)籌學(xué)以及通信網(wǎng)理論的重要基礎(chǔ)之一。然而盡管經(jīng)典的排隊(duì)論有一些漂亮的數(shù)學(xué)結(jié)果，它還是與現(xiàn)代通信技術(shù)所要研究的排隊(duì)問(wèn)題有一定的差距。2022/12/310史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.2現(xiàn)代通信中的排隊(duì)理論排隊(duì)理論也稱為隨機(jī)服務(wù)理論，是現(xiàn)主要的排隊(duì)分析法早期的排隊(duì)研究，主要針對(duì)一類輸入為泊松過(guò)程，服務(wù)時(shí)間為負(fù)指數(shù)分布的排隊(duì)系統(tǒng)。在這種系統(tǒng)中，由于到達(dá)和服務(wù)的無(wú)后效性特點(diǎn)，可用生滅過(guò)程(或稱生死過(guò)程)描述。2022/12/311史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)主要的排隊(duì)分析法早期的排隊(duì)研究，主要針對(duì)一類輸入為泊松過(guò)程，擴(kuò)大狀態(tài)空間的方法當(dāng)輸入或服務(wù)不再具有無(wú)后效性時(shí)，直接應(yīng)用生滅過(guò)程理論求解就顯得無(wú)能為力。這時(shí)采用補(bǔ)充變量，用擴(kuò)大狀態(tài)空間的方法將非馬爾柯夫過(guò)程的排隊(duì)化成一個(gè)狀態(tài)空間為多維的馬爾柯夫過(guò)程求解。這類方法統(tǒng)稱為擴(kuò)大狀態(tài)空間法。處理M/Er/1/∞和Er/M/1/∞等排隊(duì)系統(tǒng)便可以采用這種方法。我們經(jīng)常提到的相位法屬于此類方法。2022/12/312史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)擴(kuò)大狀態(tài)空間的方法當(dāng)輸入或服務(wù)不再具有無(wú)后效性時(shí)，直接應(yīng)用生半馬氏分析法當(dāng)一個(gè)排隊(duì)系統(tǒng)的服務(wù)過(guò)程不是馬爾柯夫過(guò)程，但到達(dá)或服務(wù)二者之間有一個(gè)具有無(wú)后效性時(shí)，往往可以采用嵌入馬氏鏈法。當(dāng)可以用半馬氏過(guò)程描述排隊(duì)隊(duì)長(zhǎng)變化過(guò)程，或輸入過(guò)程(或服務(wù)時(shí)間)本身即為一個(gè)半馬氏過(guò)程時(shí)，或可嵌入一個(gè)半馬氏過(guò)程時(shí)，往往采用半馬爾柯夫(Semi-Markov)理論對(duì)這類系統(tǒng)進(jìn)行分析。這種方法稱為半馬氏分析法。2022/12/313史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)半馬氏分析法當(dāng)一個(gè)排隊(duì)系統(tǒng)的服務(wù)過(guò)程不是馬爾柯夫過(guò)程，但到達(dá)近似逼近法對(duì)于更一般的排隊(duì)系統(tǒng)，如G/G/1排隊(duì)系統(tǒng)，其隊(duì)長(zhǎng)變化過(guò)程是一般的隨機(jī)過(guò)程。這時(shí)，要求出平穩(wěn)分布極為困難?？刹捎梅e分微分方程法近似求解。不等式定界法近年來(lái)也用于分析一般的排隊(duì)系統(tǒng)，可將之看作近似逼近法的一種。另外的近似逼近法包括系統(tǒng)逼近法和過(guò)程逼近法。流體流方法就是一種過(guò)程逼近法。2022/12/314史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)近似逼近法對(duì)于更一般的排隊(duì)系統(tǒng)，如G/G/1排隊(duì)系統(tǒng)，其隊(duì)長(zhǎng)

現(xiàn)代通信中排隊(duì)的特點(diǎn)現(xiàn)代通信的發(fā)展趨勢(shì)之一是業(yè)務(wù)綜合。它要求實(shí)現(xiàn)多種業(yè)務(wù)在同一個(gè)網(wǎng)中傳輸。顯然排隊(duì)系統(tǒng)的輸入將是復(fù)合業(yè)務(wù)流，也就是說(shuō)輸入過(guò)程將更加復(fù)雜，不再具有Poisson輸入過(guò)程的無(wú)后效性(馬爾柯夫性)特點(diǎn)。另外，服務(wù)過(guò)程和排隊(duì)策略(規(guī)則)也變得更復(fù)雜。即使是現(xiàn)有的通信網(wǎng)絡(luò)在引入新業(yè)務(wù)之后也會(huì)表現(xiàn)出這些特點(diǎn)。比如傳統(tǒng)的PSTN網(wǎng)主要是針對(duì)普通電話業(yè)務(wù)設(shè)計(jì)的，在撥號(hào)入(Internet)網(wǎng)業(yè)務(wù)大量出現(xiàn)之后，描述呼叫的排隊(duì)系統(tǒng)發(fā)生了深刻的變化，Erlang公式不再適應(yīng)。自然依據(jù)該公式設(shè)計(jì)的PSTN網(wǎng)出現(xiàn)呼損急劇增大甚至系統(tǒng)崩潰等現(xiàn)象便不足為奇了。下面具體地針對(duì)ATM這一通信領(lǐng)域最新技術(shù)來(lái)加以分析。我們需要在三個(gè)層次上利用排隊(duì)理論，分別是呼叫級(jí)、突發(fā)級(jí)和信元級(jí)。2022/12/315史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)現(xiàn)代通信中排隊(duì)的特點(diǎn)現(xiàn)代通信的發(fā)展趨勢(shì)之一是業(yè)務(wù)綜合。它要ATM網(wǎng)對(duì)于呼叫級(jí)分析而言，由于ATM網(wǎng)中可以同時(shí)傳輸多種業(yè)務(wù)，包括面向連接的數(shù)據(jù)業(yè)務(wù)、語(yǔ)音業(yè)務(wù)和視頻業(yè)務(wù)，以及無(wú)連接的業(yè)務(wù)等。業(yè)務(wù)呼叫的發(fā)生(即顧客到達(dá))具有相當(dāng)復(fù)雜的特點(diǎn)，用簡(jiǎn)單的Poisson輸入過(guò)程或Erlang輸入過(guò)程描述也許是不精確的。同時(shí)每種業(yè)務(wù)的持續(xù)時(shí)間(即服務(wù)時(shí)間)也將是比較復(fù)雜的。突發(fā)級(jí)排隊(duì)也具有類似的特點(diǎn)。呼叫級(jí)排隊(duì)分析的目的是要了解呼損的大小等參數(shù)。突發(fā)級(jí)排隊(duì)分析的目的是要了解以突發(fā)級(jí)為單位的丟失大小等參數(shù)。2022/12/316史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)ATM網(wǎng)對(duì)于呼叫級(jí)分析而言，由于ATM網(wǎng)中可以同時(shí)傳輸多種業(yè)信元級(jí)分析需要指出，ATM網(wǎng)中的呼叫接入控制，帶寬分配等是以是否能滿足一定的業(yè)務(wù)要求(QOS)為判斷標(biāo)準(zhǔn)的，而QOS是以信元丟失率、時(shí)延等量描述的。因此還需要將以上兩個(gè)層次上的分析結(jié)果，特別是以突發(fā)為單位的丟失，轉(zhuǎn)化為信元丟失率、時(shí)延等量。因此更為關(guān)鍵的是信元級(jí)分析。2022/12/317史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元級(jí)分析需要指出，ATM網(wǎng)中的呼叫接入控制，帶寬分配等是以排隊(duì)策略

ATM排隊(duì)系統(tǒng)的排隊(duì)策略(規(guī)則)比較復(fù)雜。首先，ATM網(wǎng)中存在優(yōu)先級(jí)，包括丟失優(yōu)先級(jí)和時(shí)延優(yōu)先級(jí)。這樣，信元到達(dá)排隊(duì)系統(tǒng)后就要根據(jù)其優(yōu)先級(jí)采取相應(yīng)的排隊(duì)策略，這是一個(gè)多優(yōu)先級(jí)排隊(duì)問(wèn)題。其次，為了滿足多種業(yè)務(wù)的QOS要求，控制策略多種多樣，對(duì)應(yīng)于排隊(duì)系統(tǒng)便是排隊(duì)策略的不一致。比如ABR業(yè)務(wù)的引入使得其排隊(duì)是一個(gè)有反饋的閉環(huán)系統(tǒng)。另外，根據(jù)ATM論壇關(guān)于業(yè)務(wù)分類的新建議，多隊(duì)列排隊(duì)將是ATM排隊(duì)系統(tǒng)的另一特點(diǎn)。2022/12/318史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)排隊(duì)策略ATM排隊(duì)系統(tǒng)的排隊(duì)策略(規(guī)則)比較復(fù)雜。首業(yè)務(wù)建模業(yè)務(wù)模型On-Off模型MMPP模型MMDP模型排隊(duì)系統(tǒng)模型B/D/1/K(這里B表示On-Off輸入)MMPP/D/1/KMMDP/D/1/K2022/12/319史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)業(yè)務(wù)建模業(yè)務(wù)模型排隊(duì)系統(tǒng)模型2022/12/21現(xiàn)代通信研究中常用的排隊(duì)分析方法不等式定界逼近方法擴(kuò)大狀態(tài)空間法半馬氏分析法流體流方法2022/12/320史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)現(xiàn)代通信研究中常用的排隊(duì)分析方法不等式定界逼近方法2022/分組語(yǔ)音通信半馬爾柯夫過(guò)程模型及連續(xù)時(shí)間馬爾柯夫鏈模型。在前一個(gè)模型中，首先利用擴(kuò)大狀態(tài)空間法將狀態(tài)定義為一個(gè)二維變量，包括信源狀態(tài)和排隊(duì)隊(duì)長(zhǎng)。由于采用了多個(gè)On-Off語(yǔ)音模型的復(fù)合信源作為排隊(duì)輸入，可以用一個(gè)馬爾柯夫鏈(在這里更特殊地它是一個(gè)生死鏈)描述，在每一個(gè)信源狀態(tài)下語(yǔ)音分組按一個(gè)與狀態(tài)有關(guān)的速率均勻發(fā)出。在該文限定的條件下排隊(duì)狀態(tài)(二維)服從一個(gè)半馬爾柯夫過(guò)程。我們可以認(rèn)為這前一個(gè)排隊(duì)模型所采用的分析方法是擴(kuò)大狀態(tài)空間法與半馬氏分析法的結(jié)合。2022/12/321史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)分組語(yǔ)音通信半馬爾柯夫過(guò)程模型及連續(xù)時(shí)間馬爾柯夫鏈模型。在前分組語(yǔ)音通信后一個(gè)模型中，也利用擴(kuò)大狀態(tài)空間法將狀態(tài)定義為一個(gè)二維變量，包括信源狀態(tài)和排隊(duì)隊(duì)長(zhǎng)。不過(guò)它的排隊(duì)輸入是多個(gè)兩狀態(tài)MMPP模型的復(fù)合信源(即多狀態(tài)MMPP)，在每一個(gè)信源狀態(tài)下語(yǔ)音分組的發(fā)出服從Poisson過(guò)程。于是整個(gè)排隊(duì)狀態(tài)(二維)服從一個(gè)連續(xù)時(shí)間馬爾柯夫過(guò)程。顯然這個(gè)排隊(duì)模型所采用的分析方法是擴(kuò)大狀態(tài)空間法。2022/12/322史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)分組語(yǔ)音通信后一個(gè)模型中，也利用擴(kuò)大狀態(tài)空間法將狀態(tài)定義為一流體流方法流體流方法(FluidFlowMethod)是一種排隊(duì)近似分析法。它忽略到達(dá)過(guò)程及排隊(duì)隊(duì)長(zhǎng)的離散性質(zhì)，將到達(dá)及隊(duì)長(zhǎng)變化看成連續(xù)變化，屬于前面介紹的系統(tǒng)逼近法。由于它計(jì)算簡(jiǎn)單、物理意義明確，在文獻(xiàn)［Anick82］將之引入通信領(lǐng)域之后很快得到廣泛運(yùn)用。例如，文獻(xiàn)［Daigle86］分析了它在分組語(yǔ)音通信中的應(yīng)用。文獻(xiàn)［Yin90］利用它研究語(yǔ)音通信(多On-Off復(fù)合輸入)中的擁塞控制；文獻(xiàn)［Stamoulis94］將之用于視頻業(yè)務(wù)(生死鏈模型)的排隊(duì)分析；文獻(xiàn)［Yin91］用它分析了On-Off數(shù)據(jù)業(yè)務(wù)輸入的漏桶監(jiān)管策略；文獻(xiàn)［蔣志剛95］用它分析了突發(fā)業(yè)務(wù)(多On-Off復(fù)合的生死鏈模型)輸入的漏桶監(jiān)管策略。2022/12/323史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)流體流方法流體流方法(FluidFlowMethod)是流體流方法流體流方法的計(jì)算復(fù)雜度與排隊(duì)容量大小無(wú)關(guān)，這是一個(gè)優(yōu)良性質(zhì)。在信元緩沖區(qū)有增大趨勢(shì)的今天，這是非常有利的。它在計(jì)算中的稍微困難之處在于特征值及特征向量的求取。同時(shí)，在大維數(shù)情況下，穩(wěn)定的數(shù)值解較難獲得。2022/12/324史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)流體流方法流體流方法的計(jì)算復(fù)雜度與排隊(duì)容量大小無(wú)關(guān)，這是一個(gè)流體流方法其中一方面是對(duì)輸入信源適用范圍的拓展，采用馬爾柯夫調(diào)制的確定速率過(guò)程(MMDP)，指出流體流方法可用于所有MMDP信源的排隊(duì)分析。On-Off模型、生死鏈調(diào)制速率過(guò)程只是其中特例。另一方面發(fā)展了一套分析ATM網(wǎng)部分緩沖共享(PartialBufferSharing,PBS)流量控制策略的流體流法，它可用于對(duì)基于緩沖門(mén)限的流量控制策略的分析。采用這種方法分析具有優(yōu)先級(jí)管理的漏桶監(jiān)管器的性能。2022/12/325史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)流體流方法其中一方面是對(duì)輸入信源適用范圍的拓展，采用馬爾柯夫大偏差理論是一種近似分析方法，可以歸結(jié)為不等式定界逼近方法一類。這種方法往往只能求出信元丟失率的近似值，而且在分析過(guò)程中涉及到求解超越方程。然而需要著重指出，這種方法可以沒(méi)有Markov假設(shè)，對(duì)于業(yè)務(wù)長(zhǎng)時(shí)相關(guān)性(longrangedependence,LRD)的研究或許有特別的意義。2022/12/326史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)大偏差理論是一種近似分析方法，可以歸結(jié)為不等式定界逼近方法一7.3現(xiàn)代通信業(yè)務(wù)的

自相似特性高速網(wǎng)絡(luò)業(yè)務(wù)具有自相似性．自相似性反映了業(yè)務(wù)在所有（或至少一個(gè)較大范圍）時(shí)間標(biāo)度上的統(tǒng)計(jì)相似性，突出表現(xiàn)為突發(fā)（ｂｕｒｓｔ）沒(méi)有明確的長(zhǎng)度，我們不可能將它們平滑掉．從傳統(tǒng)模型得到的結(jié)論是：當(dāng)業(yè)務(wù)源數(shù)目增加時(shí)，突發(fā)性會(huì)被吸收，聚集業(yè)務(wù)將變得越來(lái)越平滑；而對(duì)于自相似模型，其聚集業(yè)務(wù)的突發(fā)性將更突出而不是減少．近年來(lái)的研究結(jié)果表明，自相似性對(duì)網(wǎng)絡(luò)性能產(chǎn)生一些意想不到的影響，它直接影響到網(wǎng)絡(luò)的設(shè)計(jì)、控制、分析和管理．目前，國(guó)外圍繞這一新課題的研究工作剛剛開(kāi)始，取得了一些成果，大量的問(wèn)題有待解決．主要的困難在于傳統(tǒng)排隊(duì)論基本上是在短相關(guān)的假定下研究隊(duì)列性能，目前還沒(méi)有一套完整的技術(shù)能解決長(zhǎng)相關(guān)下隊(duì)列性能的分析問(wèn)題．2022/12/327史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.3現(xiàn)代通信業(yè)務(wù)的

自相似特性高速網(wǎng)絡(luò)業(yè)務(wù)具有自相似性．自相似的定義對(duì)于廣義平穩(wěn)隨機(jī)變量序列X＝(X1，X2，……)，設(shè)其均值為μ≡EXt，自相關(guān)函數(shù)為r(k)=E[(Xi-μ)(Xi+k–μ)]/E(Xi-μ)2

2022/12/328史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義對(duì)于廣義平穩(wěn)隨機(jī)變量序列X＝(X1，X2，……)自相似的定義我們定義Xmt為：

Xmt=(1/m)*(X(t-l)(m-l)+…+Xtm)對(duì)于廣義平穩(wěn)隨機(jī)變量序列Xm＝(Xm1，Xm2，……)，rm(k)為過(guò)程Xm的自相關(guān)函數(shù)。如果r(k)滿足,則稱隨機(jī)變量序列X為長(zhǎng)相關(guān)(自相似)的。如果VAR(X1+X2+…+Xn)的增長(zhǎng)速度為n2H，則參數(shù)H稱為隨機(jī)變量序列X的Hurst參數(shù)(H＝1-β/2)。自相似隨機(jī)變量序列可以分為嚴(yán)格自相似序列和漸近自相似序列。

2022/12/329史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義我們定義Xmt為：2022/12/229史忠植自相似的定義如果對(duì)所有k，滿足

r(k)＝1/2［(k+1)2H-2k2H+(k-1)2H］(7.3)

則隨機(jī)變量序列X稱為具有Hurst參數(shù)H的嚴(yán)格自相似序列。

2022/12/330史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義如果對(duì)所有k，滿足2022/12/230史忠植自相似的定義則過(guò)程X稱為漸近自相似序列。如果對(duì)所有k，滿足2022/12/331史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義如果對(duì)所有k，滿足2022/12/231史忠植自相似的業(yè)務(wù)建模通過(guò)生成具有自相似性的業(yè)務(wù)進(jìn)行仿真研究，是目前一種有效的研究方法．生成自相似業(yè)務(wù)的方法，主要有以下幾種：（１）

考察隊(duì)列系統(tǒng)Ｍ/Ｇ/∞，隊(duì)列的到達(dá)過(guò)程為泊松過(guò)程，服務(wù)時(shí)間服從方差無(wú)窮的重尾分布．記Xt為時(shí)刻牠系統(tǒng)中的顧客數(shù)，則｛Xt｝是漸進(jìn)自相似過(guò)程．該方法需要在計(jì)算量和計(jì)算精度之間進(jìn)行折衷處理．（２）

隨機(jī)中點(diǎn)置換方法ＲＭＤ是產(chǎn)生自相似過(guò)程的另一種方法．它通過(guò)不斷分割間隔來(lái)產(chǎn)生樣本值．每次分割時(shí)，利用一個(gè)高斯置換來(lái)確定子間隔中點(diǎn)的樣本值．通過(guò)高斯置換方差的標(biāo)度變化，可以產(chǎn)生自相似性．這種方法的優(yōu)點(diǎn)是計(jì)算速度快，在ＳＰＡＲＣｓｔａｔｉｏｎ２０上生成２６００００個(gè)樣本只需幾分鐘的時(shí)間，而缺點(diǎn)是只能產(chǎn)生漸進(jìn)自相似過(guò)程．(3)Ｇａｒｒｅｔｔ等利用ＦＡＲＩＭＡ模型產(chǎn)生漸進(jìn)自相似過(guò)程，他們沒(méi)有分析所生成樣本的精度，但指出，產(chǎn)生N個(gè)樣本點(diǎn)的時(shí)間復(fù)雜度為O（n２），因此運(yùn)算速度相對(duì)較慢．限于篇幅其他方法不能在此一一列舉．2022/12/332史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的業(yè)務(wù)建模通過(guò)生成具有自相似性的業(yè)務(wù)進(jìn)行仿真研究，是目7.4擁塞控制已經(jīng)開(kāi)發(fā)出來(lái)的用于控制分組交換網(wǎng)和幀中繼擁塞的方法不適合于ATM網(wǎng)絡(luò)，因?yàn)槿缦乱恍┮蛩兀?.

很多通信量不接受擁塞控制。例如，話音和視頻通信量甚至在網(wǎng)絡(luò)發(fā)生擁塞時(shí)也不能停止發(fā)送信元。2.

由于信元的發(fā)送時(shí)間大大小于通過(guò)網(wǎng)絡(luò)的傳播時(shí)延，因此反饋就很慢。3.

ATM網(wǎng)絡(luò)通?？芍С趾艽蠓秶膽?yīng)用，其所需帶寬從幾kbps到幾百mbps，相對(duì)簡(jiǎn)單的擁塞控制方法只能適用于其中的一種。4.

2022/12/333史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.4擁塞控制已經(jīng)開(kāi)發(fā)出來(lái)的用于控制分組交換網(wǎng)和幀中繼擁塞的7.4擁塞控制4.

在ATM網(wǎng)絡(luò)上的各種應(yīng)用可以產(chǎn)生非常不同的通信量模式（例如，恒定比特率和可變比特率的信源）。另外，常規(guī)的擁塞控制技術(shù)難于公平的處理這樣多的種類。5.

ATM網(wǎng)絡(luò)上的不同應(yīng)用需要有不同的網(wǎng)絡(luò)服務(wù)（例如，對(duì)話音和視頻的時(shí)延敏感服務(wù)，以及對(duì)數(shù)據(jù)的丟失敏感服務(wù)）。6.非常高速的交換和傳輸使得ATM網(wǎng)絡(luò)隨著擁塞控制和通信量控制的方式不同而有很大的變化。若一種方法主要依賴于對(duì)情況的變化作出反應(yīng)，那么這將產(chǎn)生選路策略和流量控制的極大的和不必要的波動(dòng)。2022/12/334史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.4擁塞控制4.

在ATM網(wǎng)絡(luò)上的各種應(yīng)用高速率的信元插入考慮在一個(gè)網(wǎng)絡(luò)中以150Mbps的數(shù)據(jù)率傳送ATM信元。在此速率下，每隔（53×8bit）/(150×10bps)=3×10秒向網(wǎng)絡(luò)發(fā)送一個(gè)信元。從源用戶到目的用戶傳送此信元所需的時(shí)間取決于中間的ATM交換機(jī)的個(gè)數(shù)、在每個(gè)交換機(jī)的交換時(shí)間、以及從源站到目的站的通路中所有鏈路上的傳播時(shí)間。為簡(jiǎn)單起見(jiàn)，忽略ATM的交換時(shí)延，并假定信號(hào)以光速傳輸。這樣，如果源站和目的站橫跨美國(guó)的東西海岸，則此往返傳播時(shí)延約為30×10秒。在這種情況下，假定叢源站A到目的站B傳送一個(gè)長(zhǎng)文件，并使用了隱式擁塞控制（即沒(méi)有顯式擁塞通知；源站根據(jù)有數(shù)據(jù)丟失就推論出發(fā)生了擁塞）。如果網(wǎng)絡(luò)由于擁塞丟棄了信元，B就返回一個(gè)拒絕報(bào)文給A，A又重傳丟棄的信元，和所有可能的后繼信元。在網(wǎng)絡(luò)擁塞通知返回到A以前，A有可能已經(jīng)發(fā)送了另外的N個(gè)信元，而在A可能對(duì)擁塞作出反應(yīng)之前已經(jīng)有超過(guò)4Mb的數(shù)據(jù)發(fā)送出去了：

2022/12/335史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)高速率的信元插入考慮在一個(gè)網(wǎng)絡(luò)中以150Mbps的數(shù)據(jù)率傳送高速率的信元插入2022/12/336史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)高速率的信元插入2022/12/236史忠植高級(jí)計(jì)算機(jī)網(wǎng)信元時(shí)延偏差2022/12/337史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元時(shí)延偏差2022/12/237史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元時(shí)延偏差2022/12/338史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元時(shí)延偏差2022/12/238史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)UNI上的信元時(shí)延偏差2022/12/339史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)UNI上的信元時(shí)延偏差2022/12/239史忠植高級(jí)計(jì)ATM層通信量和擁塞控制的目標(biāo)

l

ATM層通信量和擁塞控制必須能夠支持一組ATM層的各種QoS類，它們能夠滿足所有可預(yù)計(jì)的網(wǎng)絡(luò)服務(wù)。

l

ATM層通信量和擁塞控制必須不依賴于特定網(wǎng)絡(luò)服務(wù)的AAL協(xié)議，也必須不依賴于特定應(yīng)用的高層協(xié)議。ATM層以上的各層協(xié)議可以利用ATM層所提供的信息，以改變它們從網(wǎng)絡(luò)得到的設(shè)施（utility）。

l

ATM層通信量和擁塞控制的最佳設(shè)計(jì)必須使網(wǎng)絡(luò)和端系統(tǒng)的復(fù)雜性最小，同時(shí)使網(wǎng)絡(luò)的利用率最大。2022/12/340史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)ATM層通信量和擁塞控制的目標(biāo)l

AT4級(jí)時(shí)間間隔

l

信元插入時(shí)間：這一級(jí)的功能在信元發(fā)送時(shí)就立刻作用到信元上。l

l往返傳播時(shí)間：網(wǎng)絡(luò)在信元在網(wǎng)絡(luò)中的生存時(shí)間內(nèi)作出反應(yīng)，同時(shí)提供反饋指示給信源。l

l連接持續(xù)時(shí)間：網(wǎng)絡(luò)要決定是否能夠接受一個(gè)給定QoS的新的連接，以及要同意那些性能等級(jí)。l長(zhǎng)期：這些是控制影響一個(gè)以上的ATM連接，并且是建立為長(zhǎng)期使用的。2022/12/341史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)4級(jí)時(shí)間間隔l

信元插入時(shí)間：這一相應(yīng)時(shí)間的關(guān)系2022/12/342史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)相應(yīng)時(shí)間的關(guān)系2022/12/242史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量控制策略的基本要點(diǎn)

1.

確定是否可以接受一個(gè)給定的新的ATM連接

2.

同意向用戶支持一些性能參數(shù)

2022/12/343史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量控制策略的基本要點(diǎn)1.

確定是否可通信量控制功能l

使用虛通道進(jìn)行資源管理l

連接準(zhǔn)許控制（CAC）l

使用參數(shù)控制（UPC）l

有選擇的丟棄信元l

通信量整形

2022/12/344史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量控制功能l

使用虛通道進(jìn)行資源管理20使用虛通道進(jìn)行資源管理一個(gè)虛通道VPC提供了一種很方便的手段將一些相似的虛通路VCC構(gòu)成組。網(wǎng)絡(luò)給虛通道提供聚集的容量和性能特性，而這些可以為許多虛通路共享。網(wǎng)絡(luò)資源管理主要考慮的QoS參數(shù)是：信元丟失率、最大信元傳送時(shí)延、峰值信元時(shí)延偏差，它們都受網(wǎng)絡(luò)分配給VPC的資源數(shù)量的影響。如果一個(gè)VCC延伸經(jīng)過(guò)幾個(gè)VPC，則VCC的性能就取決于這幾個(gè)連續(xù)的VPC的性能，以及取決于在實(shí)現(xiàn)VCC相關(guān)功能的任何一個(gè)接點(diǎn)上這些連接是怎樣被處理的。這些接點(diǎn)可以是一個(gè)交換機(jī)、集中器或其他的網(wǎng)絡(luò)設(shè)備。每一條VPC的性能取決于該VPC的容量，以及該VPC中所包含的VCC的通信量特性。每一個(gè)VCC相關(guān)功能的性能取決于結(jié)點(diǎn)的交換/處理速率，以及不同信元在處理時(shí)的優(yōu)先級(jí)。2022/12/345史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)使用虛通道進(jìn)行資源管理一個(gè)虛通道VPC提供了一種很方便的手段連接準(zhǔn)許控制連接準(zhǔn)許控制（connectionadmissioncontrol）是網(wǎng)絡(luò)保護(hù)自己免受過(guò)分負(fù)荷的第一道防線。當(dāng)一個(gè)用戶請(qǐng)求一條新的VPC或VCC時(shí)，用戶就必須（顯式的或隱式的）指明在該連接的每個(gè)方向所需的服務(wù)。請(qǐng)求包括以下一些內(nèi)容：l

服務(wù)種類（CBR，rt—VBR，nrt—VBR，ABR，UBR）l

通信量描述符，包括：——源通信量描述符（PCR，SCR，MBS，MCR）——CDVT——請(qǐng)求的一致性定義l

每一個(gè)QoS參數(shù)的請(qǐng)求值和接受值（峰值CDV，maxCTD，CLR）

2022/12/346史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)連接準(zhǔn)許控制連接準(zhǔn)許控制（connectionadmiss使用參數(shù)控制（UPC）

一旦連接準(zhǔn)許控制（CAC）接受了一個(gè)連接，網(wǎng)絡(luò)的使用參數(shù)控制UPC（UsageParameterControl）功能就監(jiān)視此連接，以決定通信量是否與通信量合約相一致。使用參數(shù)控制UPC的主要目的就是保護(hù)網(wǎng)絡(luò)的資源，通過(guò)檢測(cè)是否違背了已指派的參數(shù)并采取適當(dāng)?shù)拇胧?，可使得一條連接上的過(guò)載不致使另一條連接的QoS惡化。

2022/12/347史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)使用參數(shù)控制（UPC）

一旦連接準(zhǔn)許控制（CAC）接受了一個(gè)通信量合約參數(shù)值

2022/12/348史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量合約參數(shù)值

2022/12/248史忠植高級(jí)計(jì)算機(jī)虛擬調(diào)度算法2022/12/349史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)虛擬調(diào)度算法2022/12/249史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)連續(xù)狀態(tài)漏桶算法2022/12/350史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)連續(xù)狀態(tài)漏桶算法2022/12/250史忠植高級(jí)計(jì)算機(jī)網(wǎng)峰值信元速率算法

l

峰值信元速率的控制和相關(guān)的CDVT

l

持續(xù)信元速率的控制和相關(guān)的突發(fā)容許W2022/12/351史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)峰值信元速率算法2022/12/251史忠植高級(jí)計(jì)算機(jī)網(wǎng)一般信元速率算法GCRA當(dāng)CDVTτ增加時(shí)，信元的到達(dá)可以漂移得離開(kāi)TAT很遠(yuǎn)。更重要的是，這使得信元聚集成塊的可能性增大，而這又是造成網(wǎng)絡(luò)資源緊張的一種現(xiàn)象。信元最大程度的聚集成塊出現(xiàn)在當(dāng)信源可能以背靠背（backtoback）

的方式發(fā)送信元（即以鏈路的全速率）。當(dāng)τ超過(guò)δ時(shí)就可能出現(xiàn)這種情況。特別是，當(dāng)τδ時(shí)，背靠背信元的最大數(shù)目N等于2022/12/352史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)一般信元速率算法GCRA當(dāng)CDVTτ增加時(shí)，信元的到達(dá)可以漂漏桶算法2022/12/353史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)漏桶算法2022/12/253史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)漏桶算法算法維持了一個(gè)計(jì)數(shù)器對(duì)已發(fā)送的數(shù)據(jù)量進(jìn)行連續(xù)的累計(jì)記數(shù)。計(jì)數(shù)器以每一個(gè)時(shí)間單位一個(gè)單位的恒定速率減少，一直到最小值零；這相當(dāng)于一個(gè)桶以速率1漏出。每到達(dá)一個(gè)信元，計(jì)數(shù)器就增加，但受到的限制是計(jì)數(shù)器的最大值。任何到達(dá)的信元，如果試圖引起計(jì)數(shù)器超過(guò)其最大值，就被定義為不遵守合約的信元；這就相當(dāng)于桶的容量是。圖7.5（b）表示與圖7.5（a）等效的漏桶算法。這個(gè)算法定義了一個(gè)有限容量的桶，其排水的連續(xù)速率是每時(shí)間單位流出一個(gè)單位，而當(dāng)每一個(gè)遵守合約的信元到達(dá)時(shí)，桶的容量就增加，桶的總?cè)萘渴?。在第個(gè)信元到達(dá)后，算法檢測(cè)桶是否已溢出。如果是，則此信元就是不遵守合約的。如不是，桶的容量就增加。增加量取決于在信元的到達(dá)時(shí)間桶的容量是否已全部排光。2022/12/354史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)漏桶算法算法維持了一個(gè)計(jì)數(shù)器對(duì)已發(fā)送的數(shù)據(jù)量進(jìn)行連續(xù)的累計(jì)記持續(xù)信元速率算法（1）可作為持續(xù)信元速率與突發(fā)容許的關(guān)系的工作定義（2）可用于使用參數(shù)控制以監(jiān)視是否遵守通信量合約。2022/12/355史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)持續(xù)信元速率算法（1）可作為持續(xù)信元速率與突發(fā)容許的關(guān)系的工持續(xù)信元速率算法（它可從對(duì)通信流量的突發(fā)性的了解推導(dǎo)出來(lái)。特別是，我們可以令等于在峰值速率下信元之間的時(shí)間間隔。如果通信量受到使用GCRA的峰值信元速率和使用GCRA的持續(xù)信元速率這兩方面的約束，那么在峰值信元速率下的最大突發(fā)長(zhǎng)度應(yīng)為2022/12/356史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)持續(xù)信元速率算法（它可從對(duì)通信流量的突發(fā)性的了解推導(dǎo)出來(lái)。特持續(xù)信元速率算法在信令報(bào)文中，突發(fā)容許是用以信元數(shù)編碼的來(lái)傳遞的?？捎脕?lái)推導(dǎo)出，它在GCRA算法中用來(lái)監(jiān)視持續(xù)信元速率。若給出，和，則可以是以下區(qū)間中的任何一個(gè)數(shù)值：2022/12/357史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)持續(xù)信元速率算法在信令報(bào)文中，突發(fā)容許是用以信元數(shù)編碼的來(lái)傳使用參數(shù)控制UPC的動(dòng)作

(1)一個(gè)CLP=0的信元若遵守CLP=0的通信量和約，則使之通過(guò)。(2)一個(gè)CLP=0的信元若不遵守CLP=0的通信量合約但遵守（CLP=0+1）的通信量合約，則打上標(biāo)記并使之通過(guò)。(3)一個(gè)CLP=0的信元若不遵守CLP=0的通信量合約也不遵守（CLP=0+1）的通信量合約，則被丟棄。(4)一個(gè)CLP=1若遵守（CLP=0+1）的通信量合約，則使之通過(guò)。(5)一個(gè)CLP=1若不遵守（CLP=0+1）的通信量合約，則被丟棄。2022/12/358史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)使用參數(shù)控制UPC的動(dòng)作

(1)一個(gè)CLP=0的信元若遵守通信量整形

通信量整形的一種簡(jiǎn)單方法就是使用漏桶算法的一種形式，叫做令牌桶（tokenbucket）。GCRA漏桶只是簡(jiǎn)單的監(jiān)視通信量，并拒絕或丟棄不遵守合約的信元。通信量整形漏桶則與GCRA漏桶相反，它控制遵守合約的信元流2022/12/359史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量整形

通信量整形的一種簡(jiǎn)單方法就是使用漏桶算法的一種通信量整形2022/12/360史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量整形2022/12/260史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)

通信量整形

一個(gè)令牌產(chǎn)生器以每秒ρ個(gè)令牌的速率產(chǎn)生令牌，并將其放入令牌桶中，此令牌桶的最大容量為β各令牌。離開(kāi)信源到達(dá)的信元被放入一個(gè)緩存，其最大容量為個(gè)信元。要從服務(wù)器發(fā)送一個(gè)信元，必須從桶中移走一個(gè)令牌。若令牌桶已空，則信元必須排隊(duì)等待下一個(gè)令牌。這種方式的結(jié)果是：如果已經(jīng)儲(chǔ)備了一些信元并且桶是空的，那么信元就以每秒ρ個(gè)信元的平滑速率發(fā)送出去，同時(shí)在儲(chǔ)備的信元用完之前都沒(méi)有信元時(shí)延偏差。這樣，令牌桶就平滑了信元的突發(fā)。2022/12/361史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量整形

一個(gè)令牌產(chǎn)生器以每秒ρ個(gè)令牌的速率產(chǎn)生令牌，ABR通信量管理

允許多個(gè)信源共享尚未被CBR和VBR使用的容量，但是可以提供到信源的反饋，以便動(dòng)態(tài)調(diào)整負(fù)荷，因而可避免信元的丟失和更公平的共享網(wǎng)絡(luò)的容量。這稱為閉環(huán)控制，因?yàn)樗褂昧朔答仭＿@就是ABR使用的方法。下面闡述ABR服務(wù)的概念，并詳細(xì)的討論用來(lái)控制信元流的反饋機(jī)制。2022/12/362史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)ABR通信量管理

允許多個(gè)信源共享尚未被CBR和VBR使用反饋機(jī)制1.

l

容許的信元速率ACR（AllowedCellRate）：是信源被準(zhǔn)許發(fā)送的當(dāng)前速率。信源可以在零到ACR之間的任何速率發(fā)送信元。l

l

最小信元速率MCR（MinimumCellRate）：ACR可取的最小值（這就是說(shuō)，網(wǎng)絡(luò)并不限制信源發(fā)送的信元流的速率要小于MCR）。但是，對(duì)于一個(gè)給定的連接，MCR可以置為零。l

l

峰值信元速率PCR（PeakCellRate）：ACR可取的最大值。

l

初始信元速率ICR（InitialCellRate）：指派給ACR的初始值。2022/12/363史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反饋機(jī)制1.

l

容許的信元速率AC資源管理信元

每個(gè)RM信元包括3個(gè)字段向信源提供反饋：一個(gè)擁塞指示比特CI（CongestionIndication）,一個(gè)不增加比特NI（NoIncrease），以及一個(gè)顯式信元速率字段ER（ExplicitCellRate）。信源按如下規(guī)則進(jìn)行反應(yīng)： 若CI=1

則將ACR減少一個(gè)正比于當(dāng)前ACR的量，但不小于MCR；

否則， 若NI=0，則將ACR增加一個(gè)正比于PCR的量，但不大于PCR；

若ACR>ER，則將ACR置為max[ER，MCR]。2022/12/364史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)資源管理信元

每個(gè)RM信元包括3個(gè)字段向信源提供反饋：一個(gè)容許的信元速率ACR2022/12/365史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)容許的信元速率ACR2022/12/265史忠植高級(jí)計(jì)算容許的信元速率的變化2022/12/366史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)容許的信元速率的變化2022/12/266史忠植高級(jí)計(jì)算反饋的方法2022/12/367史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)反饋的方法2022/12/267史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)速率控制反饋到信源

l

設(shè)置EFCI：當(dāng)一個(gè)正向傳輸?shù)腁TM數(shù)據(jù)信元通過(guò)交換機(jī)時(shí)，交換機(jī)可對(duì)信元首部（使用負(fù)荷類型字段）中的顯式前向擁塞指示EFCI（ExplicitForwardCongestionIndication）進(jìn)行設(shè)置。這將引起目的端系統(tǒng)在反向資源管理信元BRM中CI比特置1。l

設(shè)置相對(duì)速率：交換機(jī)可以直接對(duì)一個(gè)經(jīng)過(guò)的RM信元的CI或NI比特進(jìn)行設(shè)置。若這種比特的設(shè)置是在一個(gè)前向資源管理信元FRM中，則當(dāng)在目的站出現(xiàn)信元調(diào)頭傳輸時(shí)，該比特將在相應(yīng)的BRM中保持置1。若在一個(gè)通過(guò)的BRM信元中設(shè)置其中的一個(gè)比特，則可獲得更快的結(jié)果。要得到更快的結(jié)果，一個(gè)交換機(jī)可產(chǎn)生一個(gè)將CI或NI置1的BRM信元，而不需要等待一個(gè)通過(guò)的BRM信元。l

設(shè)置顯式速率：交換機(jī)可減少一個(gè)FRM或BRM信元中的ER字段中的值。2022/12/368史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)速率控制反饋到信源

l

設(shè)置EFCI：當(dāng)一

RM信元的格式2022/12/369史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)RM信元的格式2022/12/269史忠植高級(jí)計(jì)算機(jī)網(wǎng)

RM信元的格式

l

首部（5字節(jié)）：ATM信元首部中的PT=110即表示是一個(gè)RM信元。要進(jìn)行在一個(gè)虛通路上的速率控制，其VPI和VCI就要和該連接上的數(shù)據(jù)信元的VPI和VCI一樣。若要在一條虛通路上進(jìn)行速率控制，就要使用同樣的VPI，并使VCI=6。l

協(xié)議標(biāo)示符（1字節(jié)）：使用這個(gè)RM信元標(biāo)示服務(wù)。對(duì)于ABR，ID=1。l

報(bào)文類型（1字節(jié)）：包括下列1bit的指示符：方向（DIR）：FRM（DIR=0）或BRM（DIR=1）。BECN信元（BN）：指出信元最初是由信元產(chǎn)生（BN=0）還是由一個(gè)交換機(jī)或目的站產(chǎn)生（BN=1）。擁塞指示（CI）：（CI=1）表示擁塞。不增加（NI）：（NI=1）表示不再允許負(fù)荷的增加。請(qǐng)求/確認(rèn)（RA）：在I。371中定義；在ATM論壇的ABR中不使用。2022/12/370史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)RM信元的格式

l

首部（5字節(jié)）：A

ABR容量分配

l

擁塞控制：因?yàn)锳BR服務(wù)是要提供最小的信元丟失，因此交換機(jī)必須使用ABR的速率控制機(jī)制來(lái)限制到達(dá)的分組的速率，使得網(wǎng)絡(luò)能夠進(jìn)行處理。為此，交換機(jī)必須監(jiān)視隊(duì)列長(zhǎng)度，并且當(dāng)緩存快滿時(shí)就要抑制信元的速率。l

l

公平容量分配：一個(gè)ATM交換機(jī)必須將其容量在所有的通過(guò)此交換節(jié)點(diǎn)的連接之間進(jìn)行公平分配。因此，當(dāng)擁塞發(fā)生時(shí)，交換機(jī)必須對(duì)使用容量超過(guò)其公平份額的那些連接進(jìn)行速率抑制。

2022/12/371史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)ABR容量分配

l

擁塞

二進(jìn)制反饋方式

最簡(jiǎn)單的處理方法就是將每個(gè)輸出端口的緩存分配給一個(gè)單個(gè)先進(jìn)先出隊(duì)列（singleFIFOqueue）。當(dāng)緩存的占有率超過(guò)一定的門(mén)限時(shí)（例如，80%的緩存大?。?，交換機(jī)就開(kāi)始發(fā)出二進(jìn)制通知并繼續(xù)這樣做，直到緩存的占有率下降到低于該門(mén)限。通知可以這樣發(fā)出：將每個(gè)入數(shù)據(jù)信元中的EFCI值1，或在每個(gè)通過(guò)的RM信元上將CI或NI值1。一個(gè)較小的改進(jìn)時(shí)使用兩個(gè)門(mén)限。當(dāng)隊(duì)列長(zhǎng)度增加到足夠大以至要超過(guò)高門(mén)限時(shí)，就開(kāi)始發(fā)出二進(jìn)制通知。只有當(dāng)隊(duì)列長(zhǎng)度小于低門(mén)限時(shí)，二進(jìn)制才停止通知。2022/12/372史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)二進(jìn)制反饋方式

最簡(jiǎn)單的處理方法就是將每

二進(jìn)制反饋方式

若給每個(gè)虛連接或給每組虛連接分配一個(gè)單獨(dú)的隊(duì)列（separatequeue），那么公平性就可以得到改善。每個(gè)隊(duì)列使用一個(gè)單獨(dú)的門(mén)限，因而在任何時(shí)刻，只有具有長(zhǎng)隊(duì)列的虛連接才得到二進(jìn)制通知。除了更加公平，這種方法還有兩個(gè)另外的優(yōu)點(diǎn)。第一，由于每個(gè)隊(duì)列與其它隊(duì)列是隔離的，因此一個(gè)信源的錯(cuò)誤動(dòng)作并不會(huì)影響到其他的虛連接。第二，不同虛連接的時(shí)延和信元丟失是互不相關(guān)的，因此有可能使不同的虛連接具有不同的QoS。2022/12/373史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)二進(jìn)制反饋方式

若給每個(gè)虛連接或給每組虛

二進(jìn)制反饋方式

更復(fù)雜的技術(shù)是有選擇地反饋或智能置位。這種技術(shù)基于試圖動(dòng)態(tài)地分配容量的公平份額（fairshare）。例如，可以簡(jiǎn)單的將公平份額定義為Fairshare=當(dāng)擁塞發(fā)生時(shí)，對(duì)于任何VC,只要當(dāng)前信元速率CCR>Fairshare，則交換機(jī)就對(duì)該VC上的信元進(jìn)行置位。

2022/12/374史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)二進(jìn)制反饋方式

更復(fù)雜的技術(shù)是有選擇地反饋或顯式速率反饋方式

所有的顯式反饋方式都有以下的一些共有功能：(1)計(jì)算可支持每條VC的容量的公平份額。(2)確定當(dāng)前的負(fù)荷，或擁塞程度。(3)對(duì)每條連接計(jì)算一個(gè)顯式速率ER（explicitrate）信息發(fā)布

2022/12/375史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)顯式速率反饋方式

所有的顯式反饋方式都有以下的一些共有功能顯式速率反饋方式

增強(qiáng)的均衡速率控制算法EPRCA（ExplicitPropotionalRateControlAlgorithm）l

顯式速率指示擁塞避免ERICA（ExplicitRateIndicationforCongestionAvoidance）使用均衡速率的擁塞避免CAPC（CongestionAvoidanceusingPropotionalControl）2022/12/376史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)顯式速率反饋方式

增強(qiáng)的均衡速率控制算法EPRCA（Ex增強(qiáng)的均衡速率控制算法

對(duì)于EPRCA方式，一個(gè)交換機(jī)隨時(shí)注意每條連接上當(dāng)前負(fù)荷的平均值，它以平均容許的信元速率MACR（MeanAllowedCellRate）來(lái)表示2022/12/377史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)增強(qiáng)的均衡速率控制算法

對(duì)于EPRCA方式，一個(gè)交換機(jī)隨時(shí)注增強(qiáng)的均衡速率控制算法

MACR就表示在當(dāng)前時(shí)刻通過(guò)這個(gè)交換機(jī)的平均負(fù)荷的估值。這樣做的目的是：若擁塞發(fā)生了，則交換機(jī)將每條VC上的速率減小到不超過(guò)DPFMACR，這里DPF是一個(gè)降壓因子（DownPressureFactor）。因?yàn)樗蠽C上的速率都減小到同樣的ER，因而對(duì)速率的抑制是公平的。特別是，當(dāng)一個(gè)輸出端口的隊(duì)列長(zhǎng)度超過(guò)門(mén)限值時(shí)，所有通過(guò)該端口的連接上的RM都要按下式進(jìn)行更新：2022/12/378史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)增強(qiáng)的均衡速率控制算法

MACR就表示在當(dāng)前時(shí)刻通過(guò)這個(gè)交換顯式速率指示擁塞避免2022/12/379史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)顯式速率指示擁塞避免2022/12/279史忠植高級(jí)計(jì)算顯式速率指示擁塞避免2022/12/380史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)顯式速率指示擁塞避免2022/12/280史忠植高級(jí)計(jì)算使用均衡速率的擁塞避免CAPC2022/12/381史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)使用均衡速率的擁塞避免CAPC2022/12/281史忠植

謝謝!THANKYOU2022/12/382史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)謝謝!2022/12/282史

高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)2022/12/383史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)2022/12/21史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要7.1概述7.2現(xiàn)代通信中的排隊(duì)理論7.3現(xiàn)代通信業(yè)務(wù)的自相似特性7.4擁塞控制7.5通信量控制7.6ABR通信量管理

2022/12/384史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)容提要7.1概述2022/12/22史忠植高級(jí)計(jì)算機(jī)7.1概述高速網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵是對(duì)性能參數(shù)的進(jìn)行建模和估計(jì)的能力。設(shè)計(jì)者需要有能力在觀察到的通信量的基礎(chǔ)上估計(jì)未來(lái)的通信量的大小和特性。通信量的統(tǒng)計(jì)特性對(duì)很多類設(shè)計(jì)和配置問(wèn)題都有影響,這些問(wèn)題包括資源預(yù)留協(xié)議,在路由器和ATM交換機(jī)上使用的排隊(duì)規(guī)則和緩存大小。另外,為了做出明智的資源預(yù)留決定,用戶也需要能夠?qū)τ?jì)劃的通信量特性進(jìn)行描述。對(duì)描述數(shù)據(jù)通信量而言由許多參數(shù)很重要。2022/12/385史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.1概述2022/12/23史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性平均速率:信源提供的平均負(fù)載對(duì)于確定分配給該信源的總量是十分關(guān)鍵的。平均速率表示信源在較長(zhǎng)的時(shí)間里持續(xù)發(fā)出的流量。

2022/12/386史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性平均速率:2022/12/24史忠植高級(jí)計(jì)算機(jī)吞吐量特性峰值速率這個(gè)參數(shù)告訴網(wǎng)絡(luò)通信量最大的速率是多少,以便網(wǎng)絡(luò)能夠通過(guò)預(yù)留足夠的數(shù)據(jù)傳輸容量和緩存空間接納此通信量。2022/12/387史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性峰值速率2022/12/25史忠植高級(jí)計(jì)算機(jī)網(wǎng)吞吐量特性可變性

峰值是可變性的一種度量;一種更直接的度量是吞吐量的變化?？勺冃院饬恳粋€(gè)信源的突發(fā)性,它是統(tǒng)計(jì)復(fù)用被用于提高資源利用效率的程度的一個(gè)度量。2022/12/388史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)吞吐量特性可變性2022/12/26史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)時(shí)延特性傳輸時(shí)延

這個(gè)參數(shù)度量的是數(shù)據(jù)從信源到目的地的過(guò)程中網(wǎng)絡(luò)所施加的時(shí)延。最大傳輸時(shí)延也常常被應(yīng)用程序作為一項(xiàng)需求提出來(lái)。2022/12/389史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)時(shí)延特性傳輸時(shí)延2022/12/27史忠植高級(jí)計(jì)算機(jī)網(wǎng)時(shí)延特性時(shí)延偏差傳輸時(shí)延的偏差大小是實(shí)時(shí)應(yīng)用的一個(gè)重要參數(shù),在實(shí)時(shí)應(yīng)用中目的端應(yīng)該以平滑連續(xù)的速率播放收到的數(shù)據(jù),該速率與信源產(chǎn)生的速率匹配。這些以及相似的參數(shù)對(duì)于網(wǎng)絡(luò)配2022/12/390史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)時(shí)延特性時(shí)延偏差2022/12/28史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)性能分析排隊(duì)分析提供了一個(gè)簡(jiǎn)單的,容易處理的方法來(lái)得到有用的結(jié)果,這些結(jié)果可以用來(lái)知道網(wǎng)絡(luò)的設(shè)計(jì)和擴(kuò)展。幾十年來(lái),基于泊松通信量假設(shè)的排隊(duì)分析一直是網(wǎng)絡(luò)性能分析人員的應(yīng)用工具。然而,近些年出現(xiàn)了一個(gè)對(duì)于大家來(lái)講是驚人的結(jié)果:至少在某些情況下,數(shù)據(jù)通信量實(shí)質(zhì)上不是泊松分布的而是自相似(self-similar)或分形(fractal)的。對(duì)于這種通信量,網(wǎng)絡(luò)的性能不能再用排隊(duì)分析的清楚的公式來(lái)描述,網(wǎng)絡(luò)的時(shí)延比預(yù)期的更大,吞吐量更低。自從最初的發(fā)現(xiàn)之后,對(duì)于許多的通信量類型自相似的結(jié)果被證實(shí)了很多次。2022/12/391史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)性能分析排隊(duì)分析提供了一個(gè)簡(jiǎn)單的,容易處理的方法來(lái)得到有7.2現(xiàn)代通信中的排隊(duì)理論排隊(duì)理論也稱為隨機(jī)服務(wù)理論，是現(xiàn)代運(yùn)籌學(xué)以及通信網(wǎng)理論的重要基礎(chǔ)之一。然而盡管經(jīng)典的排隊(duì)論有一些漂亮的數(shù)學(xué)結(jié)果，它還是與現(xiàn)代通信技術(shù)所要研究的排隊(duì)問(wèn)題有一定的差距。2022/12/392史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.2現(xiàn)代通信中的排隊(duì)理論排隊(duì)理論也稱為隨機(jī)服務(wù)理論，是現(xiàn)主要的排隊(duì)分析法早期的排隊(duì)研究，主要針對(duì)一類輸入為泊松過(guò)程，服務(wù)時(shí)間為負(fù)指數(shù)分布的排隊(duì)系統(tǒng)。在這種系統(tǒng)中，由于到達(dá)和服務(wù)的無(wú)后效性特點(diǎn)，可用生滅過(guò)程(或稱生死過(guò)程)描述。2022/12/393史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)主要的排隊(duì)分析法早期的排隊(duì)研究，主要針對(duì)一類輸入為泊松過(guò)程，擴(kuò)大狀態(tài)空間的方法當(dāng)輸入或服務(wù)不再具有無(wú)后效性時(shí)，直接應(yīng)用生滅過(guò)程理論求解就顯得無(wú)能為力。這時(shí)采用補(bǔ)充變量，用擴(kuò)大狀態(tài)空間的方法將非馬爾柯夫過(guò)程的排隊(duì)化成一個(gè)狀態(tài)空間為多維的馬爾柯夫過(guò)程求解。這類方法統(tǒng)稱為擴(kuò)大狀態(tài)空間法。處理M/Er/1/∞和Er/M/1/∞等排隊(duì)系統(tǒng)便可以采用這種方法。我們經(jīng)常提到的相位法屬于此類方法。2022/12/394史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)擴(kuò)大狀態(tài)空間的方法當(dāng)輸入或服務(wù)不再具有無(wú)后效性時(shí)，直接應(yīng)用生半馬氏分析法當(dāng)一個(gè)排隊(duì)系統(tǒng)的服務(wù)過(guò)程不是馬爾柯夫過(guò)程，但到達(dá)或服務(wù)二者之間有一個(gè)具有無(wú)后效性時(shí)，往往可以采用嵌入馬氏鏈法。當(dāng)可以用半馬氏過(guò)程描述排隊(duì)隊(duì)長(zhǎng)變化過(guò)程，或輸入過(guò)程(或服務(wù)時(shí)間)本身即為一個(gè)半馬氏過(guò)程時(shí)，或可嵌入一個(gè)半馬氏過(guò)程時(shí)，往往采用半馬爾柯夫(Semi-Markov)理論對(duì)這類系統(tǒng)進(jìn)行分析。這種方法稱為半馬氏分析法。2022/12/395史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)半馬氏分析法當(dāng)一個(gè)排隊(duì)系統(tǒng)的服務(wù)過(guò)程不是馬爾柯夫過(guò)程，但到達(dá)近似逼近法對(duì)于更一般的排隊(duì)系統(tǒng)，如G/G/1排隊(duì)系統(tǒng)，其隊(duì)長(zhǎng)變化過(guò)程是一般的隨機(jī)過(guò)程。這時(shí)，要求出平穩(wěn)分布極為困難?？刹捎梅e分微分方程法近似求解。不等式定界法近年來(lái)也用于分析一般的排隊(duì)系統(tǒng)，可將之看作近似逼近法的一種。另外的近似逼近法包括系統(tǒng)逼近法和過(guò)程逼近法。流體流方法就是一種過(guò)程逼近法。2022/12/396史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)近似逼近法對(duì)于更一般的排隊(duì)系統(tǒng)，如G/G/1排隊(duì)系統(tǒng)，其隊(duì)長(zhǎng)

現(xiàn)代通信中排隊(duì)的特點(diǎn)現(xiàn)代通信的發(fā)展趨勢(shì)之一是業(yè)務(wù)綜合。它要求實(shí)現(xiàn)多種業(yè)務(wù)在同一個(gè)網(wǎng)中傳輸。顯然排隊(duì)系統(tǒng)的輸入將是復(fù)合業(yè)務(wù)流，也就是說(shuō)輸入過(guò)程將更加復(fù)雜，不再具有Poisson輸入過(guò)程的無(wú)后效性(馬爾柯夫性)特點(diǎn)。另外，服務(wù)過(guò)程和排隊(duì)策略(規(guī)則)也變得更復(fù)雜。即使是現(xiàn)有的通信網(wǎng)絡(luò)在引入新業(yè)務(wù)之后也會(huì)表現(xiàn)出這些特點(diǎn)。比如傳統(tǒng)的PSTN網(wǎng)主要是針對(duì)普通電話業(yè)務(wù)設(shè)計(jì)的，在撥號(hào)入(Internet)網(wǎng)業(yè)務(wù)大量出現(xiàn)之后，描述呼叫的排隊(duì)系統(tǒng)發(fā)生了深刻的變化，Erlang公式不再適應(yīng)。自然依據(jù)該公式設(shè)計(jì)的PSTN網(wǎng)出現(xiàn)呼損急劇增大甚至系統(tǒng)崩潰等現(xiàn)象便不足為奇了。下面具體地針對(duì)ATM這一通信領(lǐng)域最新技術(shù)來(lái)加以分析。我們需要在三個(gè)層次上利用排隊(duì)理論，分別是呼叫級(jí)、突發(fā)級(jí)和信元級(jí)。2022/12/397史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)現(xiàn)代通信中排隊(duì)的特點(diǎn)現(xiàn)代通信的發(fā)展趨勢(shì)之一是業(yè)務(wù)綜合。它要ATM網(wǎng)對(duì)于呼叫級(jí)分析而言，由于ATM網(wǎng)中可以同時(shí)傳輸多種業(yè)務(wù)，包括面向連接的數(shù)據(jù)業(yè)務(wù)、語(yǔ)音業(yè)務(wù)和視頻業(yè)務(wù)，以及無(wú)連接的業(yè)務(wù)等。業(yè)務(wù)呼叫的發(fā)生(即顧客到達(dá))具有相當(dāng)復(fù)雜的特點(diǎn)，用簡(jiǎn)單的Poisson輸入過(guò)程或Erlang輸入過(guò)程描述也許是不精確的。同時(shí)每種業(yè)務(wù)的持續(xù)時(shí)間(即服務(wù)時(shí)間)也將是比較復(fù)雜的。突發(fā)級(jí)排隊(duì)也具有類似的特點(diǎn)。呼叫級(jí)排隊(duì)分析的目的是要了解呼損的大小等參數(shù)。突發(fā)級(jí)排隊(duì)分析的目的是要了解以突發(fā)級(jí)為單位的丟失大小等參數(shù)。2022/12/398史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)ATM網(wǎng)對(duì)于呼叫級(jí)分析而言，由于ATM網(wǎng)中可以同時(shí)傳輸多種業(yè)信元級(jí)分析需要指出，ATM網(wǎng)中的呼叫接入控制，帶寬分配等是以是否能滿足一定的業(yè)務(wù)要求(QOS)為判斷標(biāo)準(zhǔn)的，而QOS是以信元丟失率、時(shí)延等量描述的。因此還需要將以上兩個(gè)層次上的分析結(jié)果，特別是以突發(fā)為單位的丟失，轉(zhuǎn)化為信元丟失率、時(shí)延等量。因此更為關(guān)鍵的是信元級(jí)分析。2022/12/399史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元級(jí)分析需要指出，ATM網(wǎng)中的呼叫接入控制，帶寬分配等是以排隊(duì)策略

ATM排隊(duì)系統(tǒng)的排隊(duì)策略(規(guī)則)比較復(fù)雜。首先，ATM網(wǎng)中存在優(yōu)先級(jí)，包括丟失優(yōu)先級(jí)和時(shí)延優(yōu)先級(jí)。這樣，信元到達(dá)排隊(duì)系統(tǒng)后就要根據(jù)其優(yōu)先級(jí)采取相應(yīng)的排隊(duì)策略，這是一個(gè)多優(yōu)先級(jí)排隊(duì)問(wèn)題。其次，為了滿足多種業(yè)務(wù)的QOS要求，控制策略多種多樣，對(duì)應(yīng)于排隊(duì)系統(tǒng)便是排隊(duì)策略的不一致。比如ABR業(yè)務(wù)的引入使得其排隊(duì)是一個(gè)有反饋的閉環(huán)系統(tǒng)。另外，根據(jù)ATM論壇關(guān)于業(yè)務(wù)分類的新建議，多隊(duì)列排隊(duì)將是ATM排隊(duì)系統(tǒng)的另一特點(diǎn)。2022/12/3100史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)排隊(duì)策略ATM排隊(duì)系統(tǒng)的排隊(duì)策略(規(guī)則)比較復(fù)雜。首業(yè)務(wù)建模業(yè)務(wù)模型On-Off模型MMPP模型MMDP模型排隊(duì)系統(tǒng)模型B/D/1/K(這里B表示On-Off輸入)MMPP/D/1/KMMDP/D/1/K2022/12/3101史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)業(yè)務(wù)建模業(yè)務(wù)模型排隊(duì)系統(tǒng)模型2022/12/21現(xiàn)代通信研究中常用的排隊(duì)分析方法不等式定界逼近方法擴(kuò)大狀態(tài)空間法半馬氏分析法流體流方法2022/12/3102史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)現(xiàn)代通信研究中常用的排隊(duì)分析方法不等式定界逼近方法2022/分組語(yǔ)音通信半馬爾柯夫過(guò)程模型及連續(xù)時(shí)間馬爾柯夫鏈模型。在前一個(gè)模型中，首先利用擴(kuò)大狀態(tài)空間法將狀態(tài)定義為一個(gè)二維變量，包括信源狀態(tài)和排隊(duì)隊(duì)長(zhǎng)。由于采用了多個(gè)On-Off語(yǔ)音模型的復(fù)合信源作為排隊(duì)輸入，可以用一個(gè)馬爾柯夫鏈(在這里更特殊地它是一個(gè)生死鏈)描述，在每一個(gè)信源狀態(tài)下語(yǔ)音分組按一個(gè)與狀態(tài)有關(guān)的速率均勻發(fā)出。在該文限定的條件下排隊(duì)狀態(tài)(二維)服從一個(gè)半馬爾柯夫過(guò)程。我們可以認(rèn)為這前一個(gè)排隊(duì)模型所采用的分析方法是擴(kuò)大狀態(tài)空間法與半馬氏分析法的結(jié)合。2022/12/3103史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)分組語(yǔ)音通信半馬爾柯夫過(guò)程模型及連續(xù)時(shí)間馬爾柯夫鏈模型。在前分組語(yǔ)音通信后一個(gè)模型中，也利用擴(kuò)大狀態(tài)空間法將狀態(tài)定義為一個(gè)二維變量，包括信源狀態(tài)和排隊(duì)隊(duì)長(zhǎng)。不過(guò)它的排隊(duì)輸入是多個(gè)兩狀態(tài)MMPP模型的復(fù)合信源(即多狀態(tài)MMPP)，在每一個(gè)信源狀態(tài)下語(yǔ)音分組的發(fā)出服從Poisson過(guò)程。于是整個(gè)排隊(duì)狀態(tài)(二維)服從一個(gè)連續(xù)時(shí)間馬爾柯夫過(guò)程。顯然這個(gè)排隊(duì)模型所采用的分析方法是擴(kuò)大狀態(tài)空間法。2022/12/3104史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)分組語(yǔ)音通信后一個(gè)模型中，也利用擴(kuò)大狀態(tài)空間法將狀態(tài)定義為一流體流方法流體流方法(FluidFlowMethod)是一種排隊(duì)近似分析法。它忽略到達(dá)過(guò)程及排隊(duì)隊(duì)長(zhǎng)的離散性質(zhì)，將到達(dá)及隊(duì)長(zhǎng)變化看成連續(xù)變化，屬于前面介紹的系統(tǒng)逼近法。由于它計(jì)算簡(jiǎn)單、物理意義明確，在文獻(xiàn)［Anick82］將之引入通信領(lǐng)域之后很快得到廣泛運(yùn)用。例如，文獻(xiàn)［Daigle86］分析了它在分組語(yǔ)音通信中的應(yīng)用。文獻(xiàn)［Yin90］利用它研究語(yǔ)音通信(多On-Off復(fù)合輸入)中的擁塞控制；文獻(xiàn)［Stamoulis94］將之用于視頻業(yè)務(wù)(生死鏈模型)的排隊(duì)分析；文獻(xiàn)［Yin91］用它分析了On-Off數(shù)據(jù)業(yè)務(wù)輸入的漏桶監(jiān)管策略；文獻(xiàn)［蔣志剛95］用它分析了突發(fā)業(yè)務(wù)(多On-Off復(fù)合的生死鏈模型)輸入的漏桶監(jiān)管策略。2022/12/3105史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)流體流方法流體流方法(FluidFlowMethod)是流體流方法流體流方法的計(jì)算復(fù)雜度與排隊(duì)容量大小無(wú)關(guān)，這是一個(gè)優(yōu)良性質(zhì)。在信元緩沖區(qū)有增大趨勢(shì)的今天，這是非常有利的。它在計(jì)算中的稍微困難之處在于特征值及特征向量的求取。同時(shí)，在大維數(shù)情況下，穩(wěn)定的數(shù)值解較難獲得。2022/12/3106史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)流體流方法流體流方法的計(jì)算復(fù)雜度與排隊(duì)容量大小無(wú)關(guān)，這是一個(gè)流體流方法其中一方面是對(duì)輸入信源適用范圍的拓展，采用馬爾柯夫調(diào)制的確定速率過(guò)程(MMDP)，指出流體流方法可用于所有MMDP信源的排隊(duì)分析。On-Off模型、生死鏈調(diào)制速率過(guò)程只是其中特例。另一方面發(fā)展了一套分析ATM網(wǎng)部分緩沖共享(PartialBufferSharing,PBS)流量控制策略的流體流法，它可用于對(duì)基于緩沖門(mén)限的流量控制策略的分析。采用這種方法分析具有優(yōu)先級(jí)管理的漏桶監(jiān)管器的性能。2022/12/3107史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)流體流方法其中一方面是對(duì)輸入信源適用范圍的拓展，采用馬爾柯夫大偏差理論是一種近似分析方法，可以歸結(jié)為不等式定界逼近方法一類。這種方法往往只能求出信元丟失率的近似值，而且在分析過(guò)程中涉及到求解超越方程。然而需要著重指出，這種方法可以沒(méi)有Markov假設(shè)，對(duì)于業(yè)務(wù)長(zhǎng)時(shí)相關(guān)性(longrangedependence,LRD)的研究或許有特別的意義。2022/12/3108史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)大偏差理論是一種近似分析方法，可以歸結(jié)為不等式定界逼近方法一7.3現(xiàn)代通信業(yè)務(wù)的

自相似特性高速網(wǎng)絡(luò)業(yè)務(wù)具有自相似性．自相似性反映了業(yè)務(wù)在所有（或至少一個(gè)較大范圍）時(shí)間標(biāo)度上的統(tǒng)計(jì)相似性，突出表現(xiàn)為突發(fā)（ｂｕｒｓｔ）沒(méi)有明確的長(zhǎng)度，我們不可能將它們平滑掉．從傳統(tǒng)模型得到的結(jié)論是：當(dāng)業(yè)務(wù)源數(shù)目增加時(shí)，突發(fā)性會(huì)被吸收，聚集業(yè)務(wù)將變得越來(lái)越平滑；而對(duì)于自相似模型，其聚集業(yè)務(wù)的突發(fā)性將更突出而不是減少．近年來(lái)的研究結(jié)果表明，自相似性對(duì)網(wǎng)絡(luò)性能產(chǎn)生一些意想不到的影響，它直接影響到網(wǎng)絡(luò)的設(shè)計(jì)、控制、分析和管理．目前，國(guó)外圍繞這一新課題的研究工作剛剛開(kāi)始，取得了一些成果，大量的問(wèn)題有待解決．主要的困難在于傳統(tǒng)排隊(duì)論基本上是在短相關(guān)的假定下研究隊(duì)列性能，目前還沒(méi)有一套完整的技術(shù)能解決長(zhǎng)相關(guān)下隊(duì)列性能的分析問(wèn)題．2022/12/3109史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.3現(xiàn)代通信業(yè)務(wù)的

自相似特性高速網(wǎng)絡(luò)業(yè)務(wù)具有自相似性．自相似的定義對(duì)于廣義平穩(wěn)隨機(jī)變量序列X＝(X1，X2，……)，設(shè)其均值為μ≡EXt，自相關(guān)函數(shù)為r(k)=E[(Xi-μ)(Xi+k–μ)]/E(Xi-μ)2

2022/12/3110史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義對(duì)于廣義平穩(wěn)隨機(jī)變量序列X＝(X1，X2，……)自相似的定義我們定義Xmt為：

Xmt=(1/m)*(X(t-l)(m-l)+…+Xtm)對(duì)于廣義平穩(wěn)隨機(jī)變量序列Xm＝(Xm1，Xm2，……)，rm(k)為過(guò)程Xm的自相關(guān)函數(shù)。如果r(k)滿足,則稱隨機(jī)變量序列X為長(zhǎng)相關(guān)(自相似)的。如果VAR(X1+X2+…+Xn)的增長(zhǎng)速度為n2H，則參數(shù)H稱為隨機(jī)變量序列X的Hurst參數(shù)(H＝1-β/2)。自相似隨機(jī)變量序列可以分為嚴(yán)格自相似序列和漸近自相似序列。

2022/12/3111史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義我們定義Xmt為：2022/12/229史忠植自相似的定義如果對(duì)所有k，滿足

r(k)＝1/2［(k+1)2H-2k2H+(k-1)2H］(7.3)

則隨機(jī)變量序列X稱為具有Hurst參數(shù)H的嚴(yán)格自相似序列。

2022/12/3112史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義如果對(duì)所有k，滿足2022/12/230史忠植自相似的定義則過(guò)程X稱為漸近自相似序列。如果對(duì)所有k，滿足2022/12/3113史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的定義如果對(duì)所有k，滿足2022/12/231史忠植自相似的業(yè)務(wù)建模通過(guò)生成具有自相似性的業(yè)務(wù)進(jìn)行仿真研究，是目前一種有效的研究方法．生成自相似業(yè)務(wù)的方法，主要有以下幾種：（１）

考察隊(duì)列系統(tǒng)Ｍ/Ｇ/∞，隊(duì)列的到達(dá)過(guò)程為泊松過(guò)程，服務(wù)時(shí)間服從方差無(wú)窮的重尾分布．記Xt為時(shí)刻牠系統(tǒng)中的顧客數(shù)，則｛Xt｝是漸進(jìn)自相似過(guò)程．該方法需要在計(jì)算量和計(jì)算精度之間進(jìn)行折衷處理．（２）

隨機(jī)中點(diǎn)置換方法ＲＭＤ是產(chǎn)生自相似過(guò)程的另一種方法．它通過(guò)不斷分割間隔來(lái)產(chǎn)生樣本值．每次分割時(shí)，利用一個(gè)高斯置換來(lái)確定子間隔中點(diǎn)的樣本值．通過(guò)高斯置換方差的標(biāo)度變化，可以產(chǎn)生自相似性．這種方法的優(yōu)點(diǎn)是計(jì)算速度快，在ＳＰＡＲＣｓｔａｔｉｏｎ２０上生成２６００００個(gè)樣本只需幾分鐘的時(shí)間，而缺點(diǎn)是只能產(chǎn)生漸進(jìn)自相似過(guò)程．(3)Ｇａｒｒｅｔｔ等利用ＦＡＲＩＭＡ模型產(chǎn)生漸進(jìn)自相似過(guò)程，他們沒(méi)有分析所生成樣本的精度，但指出，產(chǎn)生N個(gè)樣本點(diǎn)的時(shí)間復(fù)雜度為O（n２），因此運(yùn)算速度相對(duì)較慢．限于篇幅其他方法不能在此一一列舉．2022/12/3114史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)自相似的業(yè)務(wù)建模通過(guò)生成具有自相似性的業(yè)務(wù)進(jìn)行仿真研究，是目7.4擁塞控制已經(jīng)開(kāi)發(fā)出來(lái)的用于控制分組交換網(wǎng)和幀中繼擁塞的方法不適合于ATM網(wǎng)絡(luò)，因?yàn)槿缦乱恍┮蛩兀?.

很多通信量不接受擁塞控制。例如，話音和視頻通信量甚至在網(wǎng)絡(luò)發(fā)生擁塞時(shí)也不能停止發(fā)送信元。2.

由于信元的發(fā)送時(shí)間大大小于通過(guò)網(wǎng)絡(luò)的傳播時(shí)延，因此反饋就很慢。3.

ATM網(wǎng)絡(luò)通?？芍С趾艽蠓秶膽?yīng)用，其所需帶寬從幾kbps到幾百mbps，相對(duì)簡(jiǎn)單的擁塞控制方法只能適用于其中的一種。4.

2022/12/3115史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.4擁塞控制已經(jīng)開(kāi)發(fā)出來(lái)的用于控制分組交換網(wǎng)和幀中繼擁塞的7.4擁塞控制4.

在ATM網(wǎng)絡(luò)上的各種應(yīng)用可以產(chǎn)生非常不同的通信量模式（例如，恒定比特率和可變比特率的信源）。另外，常規(guī)的擁塞控制技術(shù)難于公平的處理這樣多的種類。5.

ATM網(wǎng)絡(luò)上的不同應(yīng)用需要有不同的網(wǎng)絡(luò)服務(wù)（例如，對(duì)話音和視頻的時(shí)延敏感服務(wù)，以及對(duì)數(shù)據(jù)的丟失敏感服務(wù)）。6.非常高速的交換和傳輸使得ATM網(wǎng)絡(luò)隨著擁塞控制和通信量控制的方式不同而有很大的變化。若一種方法主要依賴于對(duì)情況的變化作出反應(yīng)，那么這將產(chǎn)生選路策略和流量控制的極大的和不必要的波動(dòng)。2022/12/3116史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)7.4擁塞控制4.

在ATM網(wǎng)絡(luò)上的各種應(yīng)用高速率的信元插入考慮在一個(gè)網(wǎng)絡(luò)中以150Mbps的數(shù)據(jù)率傳送ATM信元。在此速率下，每隔（53×8bit）/(150×10bps)=3×10秒向網(wǎng)絡(luò)發(fā)送一個(gè)信元。從源用戶到目的用戶傳送此信元所需的時(shí)間取決于中間的ATM交換機(jī)的個(gè)數(shù)、在每個(gè)交換機(jī)的交換時(shí)間、以及從源站到目的站的通路中所有鏈路上的傳播時(shí)間。為簡(jiǎn)單起見(jiàn)，忽略ATM的交換時(shí)延，并假定信號(hào)以光速傳輸。這樣，如果源站和目的站橫跨美國(guó)的東西海岸，則此往返傳播時(shí)延約為30×10秒。在這種情況下，假定叢源站A到目的站B傳送一個(gè)長(zhǎng)文件，并使用了隱式擁塞控制（即沒(méi)有顯式擁塞通知；源站根據(jù)有數(shù)據(jù)丟失就推論出發(fā)生了擁塞）。如果網(wǎng)絡(luò)由于擁塞丟棄了信元，B就返回一個(gè)拒絕報(bào)文給A，A又重傳丟棄的信元，和所有可能的后繼信元。在網(wǎng)絡(luò)擁塞通知返回到A以前，A有可能已經(jīng)發(fā)送了另外的N個(gè)信元，而在A可能對(duì)擁塞作出反應(yīng)之前已經(jīng)有超過(guò)4Mb的數(shù)據(jù)發(fā)送出去了：

2022/12/3117史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)高速率的信元插入考慮在一個(gè)網(wǎng)絡(luò)中以150Mbps的數(shù)據(jù)率傳送高速率的信元插入2022/12/3118史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)高速率的信元插入2022/12/236史忠植高級(jí)計(jì)算機(jī)網(wǎng)信元時(shí)延偏差2022/12/3119史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元時(shí)延偏差2022/12/237史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元時(shí)延偏差2022/12/3120史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)信元時(shí)延偏差2022/12/238史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)UNI上的信元時(shí)延偏差2022/12/3121史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)UNI上的信元時(shí)延偏差2022/12/239史忠植高級(jí)計(jì)ATM層通信量和擁塞控制的目標(biāo)

l

ATM層通信量和擁塞控制必須能夠支持一組ATM層的各種QoS類，它們能夠滿足所有可預(yù)計(jì)的網(wǎng)絡(luò)服務(wù)。

l

ATM層通信量和擁塞控制必須不依賴于特定網(wǎng)絡(luò)服務(wù)的AAL協(xié)議，也必須不依賴于特定應(yīng)用的高層協(xié)議。ATM層以上的各層協(xié)議可以利用ATM層所提供的信息，以改變它們從網(wǎng)絡(luò)得到的設(shè)施（utility）。

l

ATM層通信量和擁塞控制的最佳設(shè)計(jì)必須使網(wǎng)絡(luò)和端系統(tǒng)的復(fù)雜性最小，同時(shí)使網(wǎng)絡(luò)的利用率最大。2022/12/3122史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)ATM層通信量和擁塞控制的目標(biāo)l

AT4級(jí)時(shí)間間隔

l

信元插入時(shí)間：這一級(jí)的功能在信元發(fā)送時(shí)就立刻作用到信元上。l

l往返傳播時(shí)間：網(wǎng)絡(luò)在信元在網(wǎng)絡(luò)中的生存時(shí)間內(nèi)作出反應(yīng)，同時(shí)提供反饋指示給信源。l

l連接持續(xù)時(shí)間：網(wǎng)絡(luò)要決定是否能夠接受一個(gè)給定QoS的新的連接，以及要同意那些性能等級(jí)。l長(zhǎng)期：這些是控制影響一個(gè)以上的ATM連接，并且是建立為長(zhǎng)期使用的。2022/12/3123史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)4級(jí)時(shí)間間隔l

信元插入時(shí)間：這一相應(yīng)時(shí)間的關(guān)系2022/12/3124史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)相應(yīng)時(shí)間的關(guān)系2022/12/242史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量控制策略的基本要點(diǎn)

1.

確定是否可以接受一個(gè)給定的新的ATM連接

2.

同意向用戶支持一些性能參數(shù)

2022/12/3125史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量控制策略的基本要點(diǎn)1.

確定是否可通信量控制功能l

使用虛通道進(jìn)行資源管理l

連接準(zhǔn)許控制（CAC）l

使用參數(shù)控制（UPC）l

有選擇的丟棄信元l

通信量整形

2022/12/3126史忠植高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)通信量控制功能l

使用虛通道進(jìn)行資源管理20使用虛通道進(jìn)行資源管理一個(gè)虛通道VPC提供了一種很方便的手段將一些相似的虛通路VCC構(gòu)成組。網(wǎng)絡(luò)給虛通道提供聚集的容量和性能特性，而這些可以為許多虛通路