自相似流與自相似性

自相似流與自相似性Self-similarTrafficandSelf-similarity鏈路級主機(jī)-節(jié)點(diǎn)間流量入網(wǎng)/出網(wǎng)節(jié)點(diǎn)間流量主機(jī)-主機(jī)間流量傳統(tǒng)的業(yè)務(wù)流模型基于泊松（Poison）--連續(xù)時間基于貝努利（Benolli）--離散時間Birth-DeathProcessesEkEkEk+1Ek-1DeathBirthtt+tPk（t+t）=Pk（t）pk,k（t） +Pk-1（t）pk-1,k（t） +Pk+1（t）pk+1,k（t） +O（t） k≥1概率分布函數(shù)（Poisoncase）概率密度函數(shù)a(t)t≥0t≥0M/M/1排隊系統(tǒng)012k-1kk+1MarkovProcess當(dāng)前時間t與過去的時間（t-s），若時間差足夠大，則t與（t-s）間隔的業(yè)務(wù)量是不相關(guān)；在s較小時，考慮到達(dá)業(yè)務(wù)量的相關(guān)性，稱之為“短相關(guān)”模型（SRD）自相似（self-similar）Leland對Bellcore的局域網(wǎng)的測試與分析結(jié)果，表明實(shí)際網(wǎng)絡(luò)的業(yè)務(wù)流在很長的時間范圍內(nèi)都具有相關(guān)性，即LRD。Hurst系數(shù)描述一個過程的自相關(guān)函數(shù)只需要方差問題：自相似流作仿真時，數(shù)據(jù)源如何產(chǎn)生？控制流量生成程序，如何得到符合特定方差和Hurst系數(shù)的自相似流？與用戶數(shù)、用戶數(shù)據(jù)流的特征、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等物理量關(guān)聯(lián)。自相似系數(shù)的在線測量如何實(shí)施？如何減少計算量并得到精度允許的估計值？1.自相似過程的概念設(shè)X（t）是隨機(jī)過程，R（t）是該隨機(jī)過程的相關(guān)函數(shù)。如果R（t）的積分是∞，則稱X（t）是長相關(guān)過程（LRD：LongRangeDependence）。如用二階距性質(zhì)描述X（t）

，只需要一個Hurst系數(shù)，稱之為H參數(shù)。令X（t）是寬平穩(wěn)隨機(jī)過程存在均值E[X]有限方差自相關(guān)系數(shù)僅取決于k假設(shè)：L（k）是隨k緩慢變化的函數(shù)。構(gòu)造新的隨機(jī)序列 X(m)(m=0,1,2…) X(m)的每一個序列值k≥1是X（t）的大小為m的不相交塊的算術(shù)平均值。如果X(m)的相關(guān)函數(shù)R(m)(k)與R(k)相等，則稱X（t）是嚴(yán)格二階自相似過程。如果X(m)的相關(guān)函數(shù)R(m)(k)在m→∞時趨于R(k)，則稱X（t）是二階漸近自相似過程。X（t）的Hurst系數(shù)

H=1-（/2）?<H<12.自相似過程的產(chǎn)生Mandelbrot給出了自相似流的產(chǎn)生方法。分形波朗運(yùn)動（FBM，F(xiàn)ractionalBrownianMotion）令B（t）為維納過程，F(xiàn)BM是維納積分的形式來表示。BH（0）=0其中（t）是伽瑪函數(shù)。BH（t）是零均值的高斯過程B（t）的積分。BH（t）的性質(zhì)：BH（t）是平穩(wěn)增量過程；BH（t）的相關(guān)函數(shù)BH（t）的方差2|t|2H；BH（t）與aH

BH（t）同分布FGN,FractionalGaussianNoise分布高斯噪聲（FGN）是BH（t）在單位時間內(nèi)的增量。ZH（t）=BH（t）-BH（t-1）將BH（t）-BH（0）離散化為高斯隨機(jī)變量的無窮和，忽略積分的高階泰勒展開式，然后推出部分和間的疊代關(guān)系，由疊代算法得出其結(jié)果。自相似過程的生成算法M/G/∞隊列：G是具有重尾分布（無限方差的分布）的隨機(jī)服務(wù)時間。流疊加法：更新過程（renewalprocess）W（t），更新間隔UK是具有無限方差的隨機(jī)變量。隨機(jī)中值替代法（RMD，RandomMidpointDisplacement）傅立葉變換法FARIMA過程小波變換混沌映射法評估標(biāo)準(zhǔn)：簡易性、準(zhǔn)確性。 （1）RMD的計算量為O（n），計算量最小； （2）傅立葉變換法或小波變換產(chǎn)生的自相似序列，其準(zhǔn)確性高。1.因特網(wǎng)流量數(shù)據(jù)的采集和分析評價網(wǎng)絡(luò)能力增加網(wǎng)絡(luò)資源改進(jìn)網(wǎng)絡(luò)協(xié)議網(wǎng)絡(luò)性能參數(shù)的測量網(wǎng)絡(luò)性能：理論分析、模型仿真泊松模型：點(diǎn)到點(diǎn)的傳遞方式有目的地收集、整理和分析當(dāng)前網(wǎng)絡(luò)運(yùn)行的狀態(tài)數(shù)據(jù)，為下一代Internet體系結(jié)構(gòu)的制定提供依據(jù)。仿真、測量、統(tǒng)計的方法理論分析多播在流量統(tǒng)計分析中得出的理論模型，能以簡單的形式擬合實(shí)際流量的特征。自相似模型驗證自相似模型的理論結(jié)果，需要在大的網(wǎng)絡(luò)規(guī)模上進(jìn)行大量的測量。1.1因特網(wǎng)測量BMWG：網(wǎng)絡(luò)互連技術(shù)的性能參數(shù)測量方法。/html.charters/bmwg-charter.htmlTEWG:負(fù)責(zé)定義、開發(fā)、制定和推薦關(guān)于因特網(wǎng)上流量工程相關(guān)的原則、技術(shù)和機(jī)制，同時提供一個通用的論壇，以研討和推動TE的發(fā)展。/html.charters/tewg-charter.htmlIPPM:負(fù)責(zé)研究和制定衡量、評估因特網(wǎng)數(shù)據(jù)傳輸?shù)馁|(zhì)量、性能和可靠性指標(biāo)的標(biāo)準(zhǔn)測度，并開發(fā)和推廣準(zhǔn)確、有效的網(wǎng)絡(luò)測量技術(shù)。/html.charters/ippm-charter.html

全球性的測量平臺NIMI：NationalInternetMeasurementInfrastructure（卡乃基梅隆大學(xué)）LBL,LawrenceBerkeleyLaboratory

網(wǎng)絡(luò)分析基礎(chǔ)體系結(jié)構(gòu)（NAI）美國國家網(wǎng)絡(luò)應(yīng)用技術(shù)研究實(shí)驗室（NLANR）

下屬的網(wǎng)絡(luò)測量和運(yùn)行分析小組（MOAT）

因特網(wǎng)性能測量和分析（IPMA）項目密執(zhí)根大學(xué)和Merit研究動態(tài)的路由行為

美國高級網(wǎng)絡(luò)和服務(wù)公司的Surveyor

測端到端的單向包延遲、包丟失以及因特網(wǎng)路由信息的測量體系1.2網(wǎng)絡(luò)測量機(jī)制網(wǎng)絡(luò)工程：測量網(wǎng)絡(luò)本身的行為特征接入點(diǎn)處測量（應(yīng)用層）：使用FTP、WWW測試網(wǎng)絡(luò)服務(wù)器的響應(yīng)性能Ttcp和Netperf工具利用傳輸層的服務(wù)來注入測量的流量數(shù)據(jù)Ping、Traceroute和Treno等工具利用網(wǎng)絡(luò)層的ICMP協(xié)議進(jìn)行測量網(wǎng)絡(luò)參數(shù)測量方法：PASSIVEMonitoringACTIVEMonitoringBasedSNMPMonitoring監(jiān)測網(wǎng)絡(luò)流量，如OCXmon向網(wǎng)絡(luò)注入測試流量數(shù)據(jù)，并從其響應(yīng)結(jié)果數(shù)據(jù)中測量網(wǎng)絡(luò)的狀態(tài)參數(shù)，如Traceroute、Skiller為網(wǎng)絡(luò)運(yùn)行和管理服務(wù)，收集數(shù)據(jù)加以統(tǒng)計、分析自相關(guān)函數(shù)的性質(zhì)，采用數(shù)學(xué)方法構(gòu)造出自相似流，其物理意義不夠明確，無法解釋自相似性的成因。

基于測量數(shù)據(jù)的自相似流生成方法2.經(jīng)驗型的自相似流的生成方法 引入級聯(lián)模型中流量分層的思想，以網(wǎng)絡(luò)業(yè)務(wù)的統(tǒng)計特征（會話到達(dá)間隔分布、會話持續(xù)期分布、分組到達(dá)間隔）為基礎(chǔ)，生成具有特征性質(zhì)的自相似流。

1.1原型模型設(shè)一更新過程W（t），t=0，1，2，…更新間隔UK是具有無限方差的隨機(jī)變量，例如服從Pareto分布。更新間隔內(nèi)，W（t）的值是一個服從有限方差分布的隨機(jī)變量WK，在每個更新間隔內(nèi)保持恒定。經(jīng)驗型生成方法原理令Sk=∑i=0Uim個更新過程W1….Wm疊加，則疊加過程m和t→∞，W（t，m）的極限過程是分布布朗運(yùn)動（FBM）。參考模型—HTTP的流量模型WWW服務(wù)器的服務(wù)端口是TCP的80，并用IP地址區(qū)分不同的流；請求包響應(yīng)包文檔請求包響應(yīng)包文檔頁面頁面思考連續(xù)請求概率HTTP流:請求包的長度（Requestlength）響應(yīng)包的長度（Replylength）每個頁面內(nèi)的文件數(shù)（Documentsize）相鄰頁面請求間隔（Thinktime）對同一服務(wù)器的連續(xù)請求概率（Consecutivedocumentretrievals）A.Math對實(shí)際的流量進(jìn)行了測量請求包長度呈雙峰分布；響應(yīng)包長度為重尾分布，比請求包的長度要長。基于時間的誘導(dǎo)型方法識別同屬一個頁面的文件：TthresholdC1C2TthresholdC1C2具有相同的IP地址，且T<Tthreshold的文件屬于同一頁面。80%頁面的文件數(shù)在4個以下，同一服務(wù)器連續(xù)的請求數(shù)小于6個（80%）。自相似性形成是由網(wǎng)絡(luò)中各協(xié)議層交互作用的結(jié)果：TCP自適應(yīng)性IP層路由的不穩(wěn)定性鏈路層資源的可用性TCP的影響TCP的工作機(jī)制：實(shí)現(xiàn)數(shù)據(jù)分組的可靠傳輸。當(dāng)TCP的端到端建立連接后，發(fā)送端將維護(hù)一個擁塞窗口cwnd，表示網(wǎng)絡(luò)允許TCP發(fā)送的字節(jié)數(shù)；接收端維護(hù)一個接收窗口rwnd,表示接收端可用的緩沖區(qū)字節(jié)大??；接收窗口的值通過ACK傳到發(fā)送端，發(fā)送端的發(fā)送窗口swnd=min（cwnd，rwnd）；TCP接收端的確認(rèn)信號是采用累計確認(rèn)方式。若收到一個不是所期待的數(shù)據(jù)包（失序）：接收端發(fā)送發(fā)送重復(fù)確認(rèn)信號：超時重傳：重傳定時器的值是通過自適應(yīng)算法動態(tài)計算得到的；快速重傳：如果收到3個要求重傳第k個報文的重復(fù)確認(rèn)信號。為了實(shí)現(xiàn)快速重傳，接收端必須連續(xù)收到至少3個失序數(shù)據(jù)包。TCP運(yùn)行的4個階段：慢啟動階段：cwnd從1開始，每收到一個ACK確認(rèn)，cwnd的值加倍，直到大于慢啟動門限（ssthresh）；擁塞避免階段：每收到一個ACK確認(rèn)，cwnd的值加1；快速重傳階段：當(dāng)連續(xù)收到3個序號相同的ACK時，立即重傳該序號起的報文字節(jié)，同時將慢啟動門限減半，擁塞窗口為慢啟動門限加3倍的報文大小；快速恢復(fù)階段：啟動快速恢復(fù)后，每收到一個重復(fù)的ACK，擁塞窗口設(shè)為ssthresh，并開始擁塞避免過程。

RTTcwnd5101520102030數(shù)據(jù)包擁塞窗口的動態(tài)特性：一個TCP報文的字節(jié)數(shù)主要集中在1500，576，66幾個值上TCP單位時間內(nèi)發(fā)送的報文數(shù)呈突發(fā)性。仿真兩條TCP流競爭瓶頸鏈路時，各自窗口的變化規(guī)律：12Buffer=20C=0.2Mbit/s鏈路時延D=10ms從混沌映射的角度分析TCP擁塞窗口：SendRecvH(w)ACK反饋控制系統(tǒng)輸入輸出包括分組的丟失、誤碼、失序，重復(fù)。cwndn=