網(wǎng)絡(luò)測(cè)量與分析技術(shù)課件

網(wǎng)絡(luò)測(cè)量與分析技術(shù)黃泳銘華北計(jì)算技術(shù)研究所2008年秋季Self-SimilarityinWorldWideWebTraffic:

EvidenceandPossibleCauses

I.INTRODUCTIONII.BACKGROUNDIII.RELATEDWORKIV.EXAMININGWEBTRAFFICSELF-SIMILARITYV.EXPLAININGWEBTRAFFICSELF-SIMILARITYSelf-SimilarityinWorldWideWebTraffic:

EvidenceandPossibleCauses（cont’d）VI.CONCLUSIONAbstract最近，自相似性這一概念已經(jīng)被證明適用于廣域網(wǎng)和局域網(wǎng)的網(wǎng)絡(luò)流量。本文，我們證明網(wǎng)絡(luò)流量表現(xiàn)出WorldWideWeb（萬(wàn)維網(wǎng)）傳輸?shù)淖韵嗨菩?，并且我們?duì)自相似做出了一種假設(shè)的解釋?？偟姆椒ǎ簩?duì)NCSAMosaic實(shí)際用戶做一套追蹤。我們檢查WWW流量的結(jié)構(gòu)。兩大步驟：首先我們證明WWW流量顯示它與自相似模型一致性。其次我們證明自相似性可以被解釋成是基于WWW文件大小的基本分配，傳輸中高速緩存和用戶偏好的影響，用戶的“思考時(shí)間”的影響和在一個(gè)局域網(wǎng)中許多傳輸?shù)寞B加。I.INTRODUCTION為了正確制定和執(zhí)行的計(jì)算機(jī)網(wǎng)絡(luò)和網(wǎng)絡(luò)服務(wù)，如萬(wàn)維網(wǎng)，了解網(wǎng)絡(luò)流量的性質(zhì)是關(guān)鍵。最近的局域網(wǎng)流量和廣域網(wǎng)流量調(diào)查共同挑戰(zhàn)已經(jīng)被承認(rèn)的網(wǎng)絡(luò)流量模型，例如泊松過(guò)程發(fā)生在許多或所有時(shí)間段的流量可以用自相似性概念描述。由于在一個(gè)長(zhǎng)的時(shí)間范圍內(nèi)已觀查到自相似性過(guò)程的發(fā)生，它應(yīng)該表現(xiàn)出長(zhǎng)相關(guān)性；在任意時(shí)刻的估計(jì)值應(yīng)該與將來(lái)時(shí)段的估計(jì)值相一致。然而，在網(wǎng)絡(luò)流量中自相似背后的原因還沒(méi)有被清楚地認(rèn)出。在本文中，我們列出一些情況，網(wǎng)絡(luò)流量的自相似可以從文件系統(tǒng)的特點(diǎn)和用戶行為方面解釋。兩個(gè)必要工具ON/OFFsources（在SectionII-C中會(huì)詳細(xì)描述）WorldWideWeb數(shù)據(jù)采集工作NCSAMosaic捕獲用戶訪問(wèn)網(wǎng)站的訪問(wèn)模式我們的數(shù)據(jù)包括50多萬(wàn)用戶文件傳輸要求而且包含了詳細(xì)的時(shí)間和傳輸長(zhǎng)度。另外，我們調(diào)查了一些Web服務(wù)器而得到文件大小的信息用來(lái)比較客戶的訪問(wèn)模式和出現(xiàn)在服務(wù)器上的訪問(wèn)模式。文章結(jié)構(gòu)第一部分：我們考慮我們衡量的Web流量最繁忙時(shí)間自相似的可能性。第二部分：利用網(wǎng)絡(luò)流量，用戶偏好，以及文件大小數(shù)據(jù)，我們解釋某一特定網(wǎng)絡(luò)的傳輸時(shí)間和空閑時(shí)間是重尾的原因。II.BACKGROUNDA.DefinitionofSelf-SimilarityB.StatisticalTestsforSelf-SimilarityC.Heavy-TailedDistributionsA.DefinitionofSelf-Similarity給一個(gè)零平均值固定時(shí)間序列X=(Xt；t=1,2,3,.....),定義m聚合度序列

X(m)=（X(m)k;k=1,2,3,...）我們稱序列X是H-self-similar,對(duì)于所有確定的m,X(m)有與被mk重新調(diào)節(jié)的序列X有相同的分布

如果X是H-self-similar，它有相同的自相關(guān)函數(shù)作為序列Xm中的所有m一個(gè)長(zhǎng)相關(guān)性進(jìn)程有一個(gè)自相關(guān)函數(shù)當(dāng)這個(gè)進(jìn)程的自相關(guān)函數(shù)遵循冪衰減，與傳統(tǒng)流量模式顯示的指數(shù)衰減相比較。冪衰減要慢于指數(shù)衰減。對(duì)時(shí)間序列采用自相似模型一個(gè)吸引人的特點(diǎn)（適當(dāng)?shù)臅r(shí)候）是一個(gè)序列的自相似程度可以只用一個(gè)單一的參數(shù)表示。這個(gè)參數(shù)表示序列的自相關(guān)函數(shù)的衰減速度。該參數(shù)用Hurst參數(shù)表示II.BACKGROUNDA.DefinitionofSelf-SimilarityB.StatisticalTestsforSelf-SimilarityC.Heavy-TailedDistributionsB.StatisticalTestsfor

Self-Similarity本文中用四種方法測(cè)試自相似：1.variance–timeplot2.R/S

plot3.periodogrammethod4.Whittleestimator由于我們只關(guān)心在我們的數(shù)據(jù)中的長(zhǎng)相性，所以我們用第四種方法Whittleestimator。其兩個(gè)基本結(jié)構(gòu)是這是分行高斯噪聲（FGN）和fractionalARIMA（p,d,p）。因?yàn)槊啃r(shí)收集的數(shù)據(jù)都使m增加，在使用FGN模型時(shí)Whittleestimator適用于每個(gè)m聚合度數(shù)據(jù)。隨著m的增加，短相關(guān)性達(dá)到數(shù)據(jù)的平均值，如果H的值始終不變，我們可以確信它估量出了自相似的基本水平。置信區(qū)間的增長(zhǎng)將趨于聚集程度增加;然而如果隨著聚集程度的增加H的估計(jì)出現(xiàn)穩(wěn)定，我們認(rèn)為置信區(qū)間具有代表性。II.BACKGROUNDA.DefinitionofSelf-SimilarityB.StatisticalTestsforSelf-SimilarityC.Heavy-TailedDistributionsC.Heavy-TailedDistributions如果一個(gè)分部是重尾分布那么應(yīng)該符合簡(jiǎn)單的重尾分布是Pareto分布，Pareto分布在其整個(gè)范圍是雙曲線Pareto分布的概率函數(shù)是其累積分布函數(shù)是參數(shù)k是隨機(jī)變量的最小可能值為了估計(jì)我們數(shù)據(jù)中重尾的出現(xiàn)我們使用log–logcomplementarydistribution(LLCD)plots有可能用LLCDplot產(chǎn)生參數(shù)的粗略估計(jì)III.RELATEDWORK先前的廣域網(wǎng)研究已經(jīng)研究了FTP,TELNET,NNTP,和SMTPtraffic我們的數(shù)據(jù)通過(guò)在一個(gè)“stub”network的WWW流量研究補(bǔ)充先前的研究。因?yàn)閃WW流量可以解釋互聯(lián)網(wǎng)流量的很大一部分。我們集中研究網(wǎng)絡(luò)流量的自相似性的原因。由于這個(gè)原因，我們并不分析流量資源的低，正常，繁忙的時(shí)段。相反，我們著重于在我們的記錄中四個(gè)繁忙的時(shí)間。我們的文件是根據(jù)在應(yīng)用層收集的數(shù)據(jù)而不是網(wǎng)絡(luò)層。因此，我們可以檢查傳輸時(shí)間和文件大小的關(guān)系，并能對(duì)這些分布的高速緩存和用戶偏好的影響進(jìn)行估計(jì)。IV.EXAMININGWEBTRAFFICSELF-SIMILARITYA.DataCollectionB.Self-SimilarityofWWWTrafficA.DataCollection我們收集數(shù)據(jù)從1994年十一月21日到1995年5月8日，但是本文里用的數(shù)據(jù)只是從1995年1月17日到1995年2月28日。選擇這段時(shí)間是因?yàn)楦鞑块T的WWW使用明顯降低而且因?yàn)?995年3月初Mosaic在我們的網(wǎng)站不再是占主導(dǎo)地位的瀏覽器。這個(gè)研究跟蹤數(shù)據(jù)的統(tǒng)計(jì)在表I。表1

IV.EXAMININGWEBTRAFFICSELF-SIMILARITYA.DataCollectionB.Self-SimilarityofWWWTraffic

B.Self-SimilarityofWWWTraffic

我們集中研究流量序列中的個(gè)別時(shí)間，以便能夠提供一個(gè)盡可能接近于靜止的數(shù)據(jù)。提供這四種方法的一個(gè)例子，我們?cè)趫D1中分析1995年2月5日星期四4-5點(diǎn)這一小時(shí)的數(shù)據(jù)。圖1（a）variance–time分析

圖1（b）R/S

plot分析

圖1（c）periodogrammethod

以上的三個(gè)圖各表示用variance–timeplot、R/S

plot和periodogrammethod方法分析一個(gè)小時(shí)的數(shù)據(jù)證明了網(wǎng)絡(luò)流量具有自相似性。我們使用的Whittleestimator方法要求提供基本時(shí)間序列的構(gòu)成。因此我們使用分型高斯噪聲模型，用這種方法分析四個(gè)最忙時(shí)間的結(jié)果見(jiàn)圖2圖2（a）最繁忙時(shí)間

圖2（b）次繁忙時(shí)間

圖2（c）次空閑時(shí)間

圖2（d）最空閑時(shí)間

以上四圖表明我們使用的Whittleestimator方法分析網(wǎng)絡(luò)上的數(shù)據(jù)得到的判斷依然是在“stub”network網(wǎng)絡(luò)傳輸具有自相似性。V.EXPLAININGWEBTRAFFICSELF-SIMILARITYA.SuperimposingHeavy-TailedRenewalProcessesB.ExaminingTransmissionTimesC.ExaminingQuietTimesA.SuperimposingHeavy-TailedRenewalProcesses考慮大量同時(shí)存在的進(jìn)程，每個(gè)不是ON就是OFF。每個(gè)進(jìn)程的ON和OFF周期交替，并且其中ON的時(shí)間分配是參數(shù)為的重尾，或者OFF的時(shí)間分配是參數(shù)為的重尾。這樣的模型相當(dāng)于一個(gè)工作站的網(wǎng)絡(luò)，每個(gè)不是保持沉默，就是以恒定速率傳輸數(shù)據(jù)。對(duì)于這種模式，它顯示出許多資源的收集結(jié)果是一個(gè)自相似fractionalGaussiannoise過(guò)程，其中通過(guò)這個(gè)模型來(lái)解釋W(xué)eb流量的自相似性需要解釋ON或OFF時(shí)間的重尾分布。在我們的研究中ON時(shí)間相當(dāng)于獨(dú)個(gè)網(wǎng)站文件的傳輸持續(xù)時(shí)間，OFF時(shí)間相當(dāng)于傳輸間隔時(shí)間。如果ON和OFF時(shí)間的重尾分布這是為什么？為了回答這些問(wèn)題，我們可以分析我們的客戶記錄的特點(diǎn)。V.EXPLAININGWEBTRAFFICSELF-SIMILARITYA.SuperimposingHeavy-TailedRenewalProcessesB.ExaminingTransmissionTimesC.ExaminingQuietTimesB.ExaminingTransmissionTimes1)TheDistributionofWebTransmissionTimes:我們首先觀察的網(wǎng)絡(luò)文件傳輸時(shí)間分布顯示文件傳輸時(shí)間有明顯的分布規(guī)律。圖3（a）顯示發(fā)生在測(cè)量期間所有的130140文件的持續(xù)時(shí)間的LLCDplot。圖3（b）顯示對(duì)變量k的Hillestimator的估計(jì)值圖3（a）LLCDplot

圖3（b）Hillestimator

從圖3可以看出ON時(shí)間的基本分布在一個(gè)非常高或者無(wú)窮的差異狀態(tài)。值得注意的是在ON時(shí)間分布的大量的ON/OFF進(jìn)程的收集結(jié)果是一個(gè)自相似進(jìn)程。2)WhyAreWebTransmissionTimesHighlyVariable?：為了理解為什么傳輸時(shí)間存在較大差異，我們檢查網(wǎng)絡(luò)文件本身的大小分布。首先，我們展示在我們?nèi)罩局形募鬏數(shù)拇笮》植?。所有?30140個(gè)文件傳輸?shù)慕Y(jié)果在圖4中顯示。圖4（a）LLCDplot

圖4（b）Hillestimator

由圖4可以觀察出文件大小大于10000字節(jié)時(shí)，流量分布似乎可以相當(dāng)好的被重尾分布建模。一個(gè)重要問(wèn)題是：為什么文件傳輸表現(xiàn)出重尾分布？filerequest不是其主要原因，其真正原因是文件傳輸似乎更跟據(jù)在Web中的Availablefile而定。就這兩個(gè)原因的具體分析見(jiàn)圖5圖5（a）filerequest

圖5(b)uniquefile

UniqueFiles，F(xiàn)ileTransfers和FileRequests的關(guān)系在圖6中可以觀察的更詳細(xì)。是什么決定了uniquefiles的分布呢?為了幫助回答這個(gè)問(wèn)題，我們調(diào)查了遍布北美的32個(gè)網(wǎng)站服務(wù)器。事實(shí)上，所有可見(jiàn)文件的分布出現(xiàn)在32個(gè)網(wǎng)絡(luò)服務(wù)器很接近我們的客戶蹤跡的uniquefiles分布。Uniquefiles和AvailableFiles的文件分布見(jiàn)圖7圖7圖7表明Uniquefiles可以被考慮成是AvailableFiles的版本。這種說(shuō)法依據(jù)的假設(shè)是，緩存管理不根據(jù)引用文件的大小排除或引用;并且Uniquefiles是在一套AvailableFiles中不注重大小的抽樣。因此，我們斷定只要緩存是有效的，在Web中AvailableFiles可能是文件傳輸重尾的首要限定，用戶的要求不再重要。3)WhyAreAvailableFilesHeavy-Tailed?:如果AvailableFiles在Web上是重尾，一個(gè)可能的解釋可能是明確支持多種格式可能促進(jìn)文件大小變大，因此增加分布大小的尾重。然而我們發(fā)現(xiàn)多種方式在一定層度上增加尾重，事實(shí)上，它不是重尾的根本原因?？梢?jiàn)圖8。圖8

圖8的中把所有服務(wù)器文件根據(jù)文件擴(kuò)展名規(guī)成7個(gè)類別。我們使用的類別有：圖片，文字，音頻，視頻。結(jié)果表明文本文件分布也許是重尾。事實(shí)上，文件大小分布有很長(zhǎng)的tails之前已注意到，但他們沒(méi)有明確檢查尾的power-law行為，值的測(cè)量被忽視了。我們把我們的記錄中Web文件的分布和Unix文件系統(tǒng)在一次觀測(cè)中發(fā)現(xiàn)的文件分布作比較。收集的數(shù)據(jù)見(jiàn)圖9圖9

令人驚訝的是，圖9顯示了我們的Web比Unix文件系統(tǒng)對(duì)小文件有偏好。更重要的是，Web文件的tail分布與Unix文件tail分布不一樣。V.EXPLAININGWEBTRAFFICSELF-SIMILARITYA.SuperimposingHeavy-TailedRenewalProcessesB.ExaminingTransmissionTimesC.ExaminingQuietTimesC.ExaminingQuietTimes在第5章A部分，我們認(rèn)為網(wǎng)絡(luò)流量的自相似性是重尾ON/OFF進(jìn)程的疊加。ON時(shí)間相當(dāng)于個(gè)人網(wǎng)絡(luò)文件的傳輸持續(xù)時(shí)間，OFF時(shí)間相當(dāng)于工作站沒(méi)有接收到Web數(shù)據(jù)的周期。規(guī)定OFF時(shí)間分兩種情況是“積極OFF”時(shí)間和“消極OFF“的時(shí)間。積極OFF時(shí)間和消極OFF時(shí)間的差異在本節(jié)考慮的OFF時(shí)間分布中很重要。從我們的追蹤中抽出OFF時(shí)間，我們進(jìn)行如下解釋。在每個(gè)Mosaic通信中，ai是URL的i請(qǐng)求的絕對(duì)達(dá)到時(shí)間，ci是URL的i請(qǐng)求的絕對(duì)傳輸時(shí)間，遵循（ci-ai）是ON時(shí)間的隨機(jī)變量（如圖3中的描述），而（ai+1-ci