《帶寬測量綜述》PPT課件

1、Bandwidth Measuring and a tool : Nettimer,辜煒東 2004.11,提綱,帶寬測量綜述 測量技術(shù)和工具 帶寬測量模型 One packet Packet pair Packet tailgating,帶寬測量綜述 測量技術(shù)和工具 帶寬測量模型 One packet Packet pair Packet tailgating,帶寬測量概述,普通定義 指數(shù)據(jù)傳輸速率，即線路上每秒能傳輸多少字節(jié)(Byte/s)。 為何需要測量帶寬 雖然網(wǎng)絡(luò)帶寬不斷增加，但由于用戶數(shù)不斷增加，應(yīng)用程序需要的帶寬也越來越大，所以必須采用相應(yīng)的技術(shù)來讓網(wǎng)絡(luò)更加暢通帶寬測量是其基礎(chǔ)

2、難點(diǎn) 準(zhǔn)確性 對各種不同的網(wǎng)絡(luò)狀況的測量 布置測量軟件的靈活性 如何降低測量耗費(fèi),一些定義,帶寬容量(bandwidth capacity):網(wǎng)絡(luò)環(huán)境中或者端對端路徑上的鏈路層上理論上能達(dá)到的最大帶寬 當(dāng)前使用帶寬(bandwidth utilization)：當(dāng)前在某個hop或者某條路徑上已經(jīng)被占用的帶寬的總和 可用帶寬(available bandwidth)：帶寬容量-當(dāng)前使用帶寬 可達(dá)帶寬(achievable bandwidth):指兩個端之間的吞吐量，這兩個端處于特定的網(wǎng)絡(luò)條件下，例如傳輸協(xié)議，主機(jī)的硬件配置，操作系統(tǒng)，系統(tǒng)設(shè)置等。 延遲(delay)：單向延遲(OWD),往返延遲

3、(RTT)。 丟包(loss)：在兩個節(jié)點(diǎn)間丟失的包分片。同樣包括單向和往返。,測量帶寬的主要場景,主動測量、被動測量 單向、雙向 長路徑、短路徑,帶寬測量綜述 測量技術(shù)和工具 帶寬測量模型 One packet Packet pair Packet tailgating,當(dāng)前測量帶寬的主要技術(shù),Throughput TCP throughput測量法是不充分的，因為它不包括由鏈路層頭、IP頭、TCP頭和重傳所消耗的帶寬。 One packet Packet pair Packet tailgating,當(dāng)前比較流行的帶寬測量工具,測量一條路徑上所有鏈接的帶寬 pathchar、clink、p

4、char、tailgater 缺點(diǎn):耗時,對只需測量瓶頸帶寬的應(yīng)用來說是沒有必要的 還有，這些工具加上bprobe，都只能在單向上測量帶寬 主動發(fā)送探測包 tcpanaly、pathrate 比被動測量更加精確，但是負(fù)載重 nettimer 測量瓶頸帶寬 Libdpcap發(fā)包抓包庫:允許在遠(yuǎn)程機(jī)器上測量，以減少本地機(jī)器的計算量 采用被動方式實時測試長路經(jīng)上的平靜帶寬 能測量兩個方向上的帶寬,大部分技術(shù)/工具的缺點(diǎn),準(zhǔn)確度低 都是用樣本統(tǒng)計的方法，近似地測量 在網(wǎng)絡(luò)擁塞嚴(yán)重的情況下，測不準(zhǔn) 可測量性差 測量速度慢 有的網(wǎng)絡(luò)情況無法測量、或者只能測量單向 有些結(jié)果不支持統(tǒng)計學(xué)的規(guī)律 靈活性差 很難

5、有一種方法對所有的網(wǎng)絡(luò)情況(網(wǎng)絡(luò)類型、路徑長短、數(shù)據(jù)流向等)都適用 有的需要在測量的兩端都配置測量軟件 加大網(wǎng)絡(luò)擁塞 因為需要多次測量進(jìn)行統(tǒng)計，所以發(fā)數(shù)據(jù)包多,nettimer,用于測量瓶頸連接帶寬 在如下的環(huán)境下測試過 19.2Kb/s100Mb/s的帶寬 有線網(wǎng)絡(luò)、無線網(wǎng)絡(luò) 對稱帶寬、非對稱帶寬 局域網(wǎng)、廣域網(wǎng) 測試結(jié)果 誤差小于10% 最壞情況誤差為40%(超過17hop的長路經(jīng)) 測試時耗費(fèi)小于7%的網(wǎng)絡(luò)帶寬 nettimer采用packet pair模型,帶寬測量綜述 測量技術(shù)和工具 帶寬測量模型 One packet Packet pair Packet tailgating,on

6、e packet模型(1),one packet模型(2),關(guān)于傳輸延遲 和傳播延遲 傳輸延遲是由路由器復(fù)制一個包到其緩沖區(qū)里并且將它按順序地傳送到一個鏈路上的時間決定的。 傳播延遲是由信號的傳輸時間(光速)，路由器從路由表里查找路由的時間，以及路由器在轉(zhuǎn)發(fā)此包之前轉(zhuǎn)發(fā)其他包所帶來的延遲時間所決定的。 單包模型是建立在如下前提上的： 傳輸時間跟包的大小成線性比例(基本合理) 路由器都是存儲轉(zhuǎn)發(fā)的(基本合理) 鏈接是單通道的(single-channel)(有某些多通道的鏈路) 傳輸路徑上沒有其他網(wǎng)絡(luò)流量導(dǎo)致測量包的排隊阻塞(不大合理)通過取最小延遲的樣本作為正確的樣本，來解決這個問題,one

7、packet模型(3),one packet模型(4),單包技術(shù)的存在問題 每個鏈接上都必須用上圖的方法計算帶寬(斜率的倒數(shù))，因此可能發(fā)包數(shù)量多為了過濾去不正確的測量樣本 單包技術(shù)需要路由器及時的確認(rèn)包(ack) (ICMP或者UDP)有些路由器不支持 網(wǎng)橋，有些網(wǎng)橋(節(jié)點(diǎn))并不對TTL做減一的操作。application-kernel,kernel-NIC,NIC-kernel三種傳輸延遲沒有被扣除 依賴于ack，所以要計算往返延遲，加倍了被其他包影響而阻塞的誤差 后面說到的Packet tailgating技術(shù)正是能解決以上所有問題的技術(shù),帶寬測量綜述 測量技術(shù)和工具 帶寬測量模型 On

8、e packet Packet pair Packet tailgating,Packet Pair 模型(1),Packet Pair模型(2),Packet Pair特性: 假設(shè) 是0到l各個鏈接中帶寬最小的一 個，假如在很小的間隔時間內(nèi)( - ，n 是路徑上最小帶寬鏈路的下一hop)發(fā)出兩個大小 相同 ( = )的包，則這兩個包到達(dá)n的時間間 隔 將是 。,Packet Pair模型(3),使用此技術(shù)的前提 傳輸延遲與包的大小成正比 路由器都是存儲轉(zhuǎn)發(fā)的 Receive bandwidth Send bandwidth(注:認(rèn)為是連續(xù)發(fā)出的包),Packet Pair模型(4),過濾技術(shù)

9、過濾去不正常的測量樣本 A:正常;B:中間插入新包; C:第一個包被前面的包阻塞;D:初始間隔時間太長,Packet Pair模型(5),兩種過濾技術(shù)：密度估計技術(shù)、基于接收/發(fā)送帶寬比率的過濾技術(shù) 密度估計技術(shù),BrBs，不正常,Packet Pair模型(6),計算密度的方法kernel density estimation 核心函數(shù)K(t) 滿足 對于receive Bandwidth的一個樣本x,其密度函數(shù)為 c稱為核心帶寬比率，0 c 1，n為c*x中的點(diǎn)的個數(shù)。c取值越大，計算越準(zhǔn)確，但是計算耗費(fèi)越大。一般地，取c=0.1。,Packet Pair模型(7),基于接收/發(fā)送帶寬比率

10、的過濾技術(shù) 定義關(guān)于接收帶寬樣本x的接收/發(fā)送帶寬比率為 p(x) = 1 - 其中s(x)是x的發(fā)送帶寬 但是，如果給定具有相同發(fā)送帶寬的兩個不同的樣本，上面的公式更偏向于接收帶寬小者(x越小,ln(x)越小,p(x)越大)。因此定義接收帶寬比率如下：,Packet Pair模型(8),綜合的過濾算法 取f(x)的最大值為瓶頸帶寬的值。 f(x)中各項取何種比例最好，還尚在研究中。 另外一點(diǎn)，一般地，都使用最后w個樣本，這樣可以更敏捷地測量瓶頸帶寬(不過w越小，測得越不準(zhǔn)確)。,測量機(jī)器數(shù)的問題,雙主機(jī) Receiver Based Packet Pair(RBPP) 單主機(jī) Sender

11、Based Packet Pair(SBPP) 使用應(yīng)用層的ACK信息取代RBPP需要的包 Only Packet Pair(ROPP) 只使用包的到達(dá)時間,分包和抓包技術(shù)(1),server抓包，計算 好處：無法分發(fā)，節(jié)省帶寬 server抓包，分發(fā)，client計算 好處：server計算負(fù)少 client可以靈活編寫性能測量的代碼 減少必須在root權(quán)限下執(zhí)行的代碼數(shù)量,分包和抓包技術(shù)(2),Libdpcap庫 基于libpcap庫 啟動libdpcap server時，需指定如下4個參數(shù) send_thresh 包頭部的字節(jié)數(shù) send_interval 包頭部發(fā)送間隔 filter_

12、cmd 指定這個server必須抓取哪些包 cap_len 指定抓取的包的長度 啟動libdpcap client時， filter_cmd 指定要連接的服務(wù)器的集合,分包和抓包技術(shù)(3),當(dāng)client連接上一個server時，server返回cap_len和clock resolution。不同機(jī)器有不同的clock resolution，如linux=2.2.0的resolution是20microseconds。,Nettimer的實驗結(jié)果(1),Nettimer的實驗結(jié)果(2),提綱,帶寬測量綜述 測量技術(shù)和工具 帶寬測量模型 One packet Packet pair Packe

13、t tailgating,帶寬測量：包延遲的確定性模型(1),先前模型 用數(shù)據(jù)庫來存放帶寬，無法跟上路由情況的變化速率。路由器不報告鏈接帶寬(link bandwidths)，因為要求路由器回應(yīng)帶寬詢問請求，會大大加重其負(fù)擔(dān)。最好的方法是終端主機(jī)自己測量，并且可以跟其他主機(jī)分享測量信息。 單測量包模型 需要路由器始終如一地處理ICMP包，以及及時傳輸?shù)腁CK信息 并且占用可觀的帶寬，可能測量速度較慢,包延遲的確定性模型(2),包延遲的決定性模型 使用packet tailgating技術(shù)測量internet上一條路徑上各個鏈接的帶寬 packet tailgating技術(shù) 通過在特定鏈接間引起

14、包的排隊，來獲取該鏈接的特性 對于每個鏈接，發(fā)送一個大的包，同時把它的TTL設(shè)為在該鏈接處中止的值，隨后接著發(fā)送一個很小的包，該包會在前面的大包后面排隊，直到大包被丟棄。 理論上，packet tailgating可以偵察到多通道的鏈接，能夠在多播樹上運(yùn)行。,包延遲的確定性模型(3),此模型融合了兩種技術(shù)的優(yōu)點(diǎn)： FIFO排隊網(wǎng)絡(luò)的packet pair特性 主動測量鏈路層帶寬的packet tailgating技術(shù) Packet tailgating技術(shù)相比于之前的其他技術(shù)： 消耗更少的網(wǎng)絡(luò)帶寬。發(fā)送更少數(shù)量的包，而保持同樣精確的測量效果 不依賴路由器(不需要路由器持續(xù)地處理ICMP包) 不

15、需要及時的確認(rèn)信息(ACK) 缺點(diǎn) 在長路經(jīng)上的帶寬的測量上仍然不夠準(zhǔn)確,包延遲的確定性模型(4),用多包延遲模型來滿足FIFO排隊網(wǎng)絡(luò)的packet pair特性。Packet pair本是用于公平排隊(fair-queueing)網(wǎng)絡(luò)的，而非FIFO排隊網(wǎng)絡(luò)。,multi-packet模型,統(tǒng)一了one packet和packet pair模型的優(yōu)點(diǎn)，能很好地測量一條路經(jīng)上所有鏈接的帶寬,multi-packet延遲公式(1),假定第一個包從不排隊，即 與one packet模型的公式： 的不同是，對于第k個包，它考慮了前面k-1個包所帶來的排隊延遲,如果沒有pcaket k-1的阻塞而導(dǎo)

16、致排隊，packet k應(yīng)該從此刻開始傳送,multi-packet延遲公式(2),綜合這兩個式子: 得到,鏈接帶寬測量使用multi-packet技術(shù)(1),鏈接帶寬測量使用multi-packet技術(shù)(2),定義: 則上頁式子 解出,Packet tailgating技術(shù)(1),這個技術(shù)分為兩種情況： sigma情況：測量整條路徑的特性 tailgating狀況：獨(dú)立測量每一個鏈接的特性 sigma狀況： 發(fā)送不同大小的包，選擇每個包延遲最小的樣本作為正確樣本，不斷發(fā)送包，直到線性回歸超過99% tailgating狀況： 假定我們可以發(fā)送不被排隊的第一個包，然后發(fā)送在鏈接 排隊、而此后的

17、鏈接中再也不排隊的第二個包。 為了做到這一點(diǎn)，我們先發(fā)送盡量大的(不被分片)的包，這個包帶有一個TTL值，設(shè)定到 時TTL變?yōu)?。然后這個包后面緊跟著一個小的包。小包的傳輸延遲遠(yuǎn)遠(yuǎn)小于第一個的大包。 這就導(dǎo)致了小包(稱為tailgater)在大包(tailgated)后面阻塞排隊。而由于大包在 處被丟棄，因此小包在此后的鏈接中再也不會因阻塞而排隊。 同樣地取小包的多個延遲樣本中的最小值作為正確值，從TTL=1開始，啟動這個過程，就可以測量到各個鏈接的帶寬。,Packet tailgating技術(shù)(2),必須解決的負(fù)責(zé)問題 1. 如何確保大包小包的發(fā)送間隔足夠短，已使得小包會在某個鏈接因大包而阻

18、塞排隊。如果我們要包k在鏈接 排隊，即 ，也即 使用前面的公式，可以得到： 化簡得：,Packet tailgating技術(shù)(3),2. 如果只能在一段安置測量程序，則必須依靠另一端的ACK包，如何讓對方發(fā)ACK包？ 3. 測量包丟失該怎么辦？ 加序列號？ 4. 不可見節(jié)點(diǎn)有時包經(jīng)過的節(jié)點(diǎn)有延遲，但是卻不把TTL減一,Packet tailgating技術(shù)優(yōu)缺點(diǎn)分析(1),優(yōu)點(diǎn) 快速 因為整條路徑，只執(zhí)行一次線性回歸過程，而不是每個鏈接上都執(zhí)行一次。Tailgating過程則必須在每個鏈接上都做一次，但是這只要求找到每一對packet的最小的延遲，而不是找1664對不同size的包的最小的延遲?？梢允褂胣ettimer 可以偵察到多通道的鏈接 通過發(fā)送packet串填滿所有channel，發(fā)送一個大包，后面跟著若干小包，如果通道數(shù)為c，發(fā)送的小包數(shù)為c，則最后一個小包就會在大包后面排隊。如果發(fā)送了第c個小包后，延遲明顯增大，則說明該鏈接上的通道數(shù)為c。所以可以測量多通道的鏈接的帶寬。,Packet tailgating技術(shù)優(yōu)缺點(diǎn)分析(2),缺點(diǎn) 源端必須能在極短的間隔內(nèi)發(fā)出測量包 對于在帶寬極小