韓盼盼 張巍

摘要：帶寬是網(wǎng)絡(luò)路徑的重要參數(shù)之一，帶寬測(cè)量的發(fā)展有助于改善網(wǎng)絡(luò)應(yīng)用程序和提高服務(wù)的質(zhì)量，其在容量分配、服務(wù)質(zhì)量管理、服務(wù)器路由選擇等領(lǐng)域均有廣泛應(yīng)用。文章提出一種基于二分法的多跳無線網(wǎng)絡(luò)可用帶寬自適應(yīng)檢測(cè)方法，該方法利用二分法思想，不僅可以測(cè)量提高無線網(wǎng)絡(luò)可用帶寬測(cè)量值的精度，還能提高多跳無線網(wǎng)絡(luò)的可靠性，減少網(wǎng)絡(luò)的負(fù)載，改善網(wǎng)絡(luò)的性能。

關(guān)鍵詞：帶寬；二分法；自適應(yīng)檢測(cè)

隨著Internet的快速發(fā)展，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)應(yīng)用在為人們的生活帶來便利的同時(shí)，也對(duì)網(wǎng)絡(luò)的服務(wù)質(zhì)量提出了更高要求。由于網(wǎng)絡(luò)規(guī)模巨大，拓?fù)浣Y(jié)構(gòu)復(fù)雜，使得研究者難以對(duì)網(wǎng)絡(luò)分析建立起精確的數(shù)學(xué)模型，因此網(wǎng)絡(luò)測(cè)量成為網(wǎng)絡(luò)行為學(xué)研究的主要途徑。多跳無線網(wǎng)絡(luò)中節(jié)點(diǎn)通過無線鏈路以多跳的方式進(jìn)行通信，隨著人們對(duì)信息服務(wù)需求的快速增長(zhǎng)，近年來多跳無線網(wǎng)絡(luò)的研究和應(yīng)用得到不斷的擴(kuò)展，以往人們對(duì)多跳無線網(wǎng)絡(luò)的研究主要集中在如何高效地為網(wǎng)絡(luò)中的節(jié)點(diǎn)提供充分連接上，而隨著網(wǎng)絡(luò)中有服務(wù)質(zhì)量（QoS，Quality of Service）要求的多媒體業(yè)務(wù)逐漸增多，如何支持和保證業(yè)務(wù)的QoS要求成為多跳無線網(wǎng)絡(luò)研究中亟待解決的問題，在多跳無線網(wǎng)絡(luò)中，獲取傳輸路徑上的可用帶寬信息是支持和保證業(yè)務(wù)QoS的重要前提。通過可用帶寬信息才有可能實(shí)行對(duì)帶寬敏感業(yè)務(wù)的帶寬預(yù)留和QoS路由接納控制等操作，才有可能最大化地利用網(wǎng)絡(luò)資源，同時(shí)由于可用帶寬與傳輸延時(shí)等其他QoS參數(shù)有著緊密的聯(lián)系，獲取可用帶寬的信息還有助于優(yōu)化其他QoS參數(shù)的設(shè)計(jì)。

目前，可用帶寬測(cè)量技術(shù)主要分為兩大類：基于探測(cè)分組間隔模型的方法（Probe Gap Model，PGM）和基于探測(cè)分組速率模型的方法（Probe Rate Model，PRM），但這兩者之間各有優(yōu)缺點(diǎn)。本文針對(duì)現(xiàn)有技術(shù)的不足，提出一種可以減少對(duì)網(wǎng)絡(luò)負(fù)載壓力，同時(shí)也縮短了測(cè)量時(shí)間的基于二分法的多跳無線網(wǎng)絡(luò)可用帶寬自適應(yīng)檢測(cè)方法。

1 多跳無線網(wǎng)絡(luò)傳統(tǒng)下載方法與分析

PGM方法是通過計(jì)算探測(cè)分組的輸出間隔和輸入間隔的時(shí)間差，估計(jì)出背景業(yè)務(wù)流量的大小，再用己知路徑帶寬減去估計(jì)得到的背景業(yè)務(wù)流量的大小得到可用帶寬測(cè)量值，PGM方法前提是己知路徑的容量大小，其主要代表有IGI，Spruce等測(cè)量技術(shù)。

PRM方法是通過在網(wǎng)絡(luò)中引入擁塞通過分析探測(cè)分組的時(shí)延情況來估算可用帶寬，得到其測(cè)量值，PRM方法的優(yōu)點(diǎn)是概念簡(jiǎn)單，其關(guān)鍵點(diǎn)是如何準(zhǔn)確地捕捉到時(shí)延變化的轉(zhuǎn)折點(diǎn)，其主要代表有TOPP，Path Chirp等測(cè)量技術(shù)。

2 基于二分法的多跳無線網(wǎng)絡(luò)可用帶寬自適應(yīng)檢測(cè)方法

2.1 基于二分法的多跳無線網(wǎng)絡(luò)可用帶寬自適應(yīng)檢測(cè)方法

基于二分法的多跳無線網(wǎng)絡(luò)可用帶寬自適應(yīng)檢測(cè)方法包括如下步驟：

（SI）源主機(jī)利用二分法的思想將一串具有大范圍速率的包串（如典型網(wǎng)絡(luò)中為l-IOOMbps）發(fā)送到目的主機(jī)進(jìn)行無線網(wǎng)絡(luò)的可用帶寬測(cè)量，包串中各數(shù)據(jù)包對(duì)應(yīng)的速率呈線性形式遞增的，其遞增的斜率參數(shù)為h，參數(shù)h的大小由用戶的需求和網(wǎng)絡(luò)來決定，當(dāng)用戶對(duì)網(wǎng)絡(luò)需求量較大，適當(dāng)?shù)靥岣遠(yuǎn)的數(shù)值，當(dāng)用戶對(duì)網(wǎng)絡(luò)的需求量較小，適當(dāng)?shù)亟档蚳的數(shù)值，然后根據(jù)從目的主機(jī)返回的排隊(duì)時(shí)延的信息得到可用帶寬估測(cè)值。其中第i次測(cè)量所發(fā)包串的包速率范圍被劃分成2m+l個(gè)區(qū)域，即B1^（i），B2^（i），…，Bn^（i），…，BN^（i），N=2^m+l，m，i為正整數(shù)，其中B_n=[b_n，l，b_n，2]，當(dāng)i=l時(shí)，中間區(qū)域B_（n+1）/2^（i）典型取值的范圍為45-60源主機(jī)。首先發(fā)送中間區(qū)域B_（n+1）/2^（i）范圍的數(shù)據(jù)包串進(jìn)行第i次的測(cè)量，被測(cè)目的主機(jī)將包串的排隊(duì)時(shí)延信息反饋給源主機(jī)。

（l）當(dāng)返回的排隊(duì)時(shí)延含有轉(zhuǎn)折點(diǎn)，則可根據(jù)轉(zhuǎn)折點(diǎn)計(jì)算得到源主機(jī)到目的主機(jī)之間的可用帶寬的數(shù)值，而可用帶寬的數(shù)值的獲得是通過源主機(jī)發(fā)送包與包之間的間隔呈線性形式遞增的包串，然后根據(jù)目的主機(jī)反饋的包串的排隊(duì)時(shí)延的信息對(duì)每個(gè)包的可用帶寬做一個(gè)估測(cè)值Ek^（m），然后對(duì)多個(gè)Ek^（m）取加權(quán)平均值，作為這次測(cè)量得到的可用帶寬的估測(cè)值D^（m），即： 源主機(jī)需要將從目的主機(jī)反饋回來的排隊(duì)時(shí)延信息分割成屬于離群區(qū)間和不屬于離群區(qū)間，假設(shè)q^k是第k個(gè)包的排隊(duì)時(shí)延，每一個(gè)q^kk+1

（3）如果返回的排隊(duì)時(shí)延不屬于步驟（l）和（2）的情況，則源主機(jī)重新選取包速率范圍被劃分的區(qū)域，即B₁^（i+1），B₂^（i+1），…，B_n^（i+1），…，B_N^（i+1），其中B₁^（i+1）=B_N+1/2ⁱ，B_N^（i+1）=B_N^（i），重新步驟（S1）進(jìn)行第（i+1）次測(cè)量。

（4）重復(fù)上述步驟，當(dāng)N值為1或者返回排隊(duì)時(shí)延含有轉(zhuǎn)折點(diǎn)時(shí)，停止上述步驟。當(dāng)返還的排隊(duì)時(shí)延含有轉(zhuǎn)折點(diǎn)時(shí)可以分析計(jì)算得到源主機(jī)到目的主機(jī)之間的可用帶寬的估計(jì)值；當(dāng)返回的排隊(duì)時(shí)延沒有轉(zhuǎn)折點(diǎn)并且變化幅度很大，則源主機(jī)重新選取包速率范圍被劃分的區(qū)域，即B₁^（i+1），B₂^（i+1），…，B_n^（i+1），…，B_N^（i+1），其中B₁^（i+1）=B₁^（i），B_N^（i+1）=B_n+1/2^（i）?；氐讲襟E（SI）進(jìn)行第（i+1）次測(cè)量；當(dāng)返回的排隊(duì)時(shí)延不屬于所述上述2種情況，則源主機(jī)重新選取包速率范圍被劃分的區(qū)域，即B₁^（i+1），B₂^（i+1），…，B_n^（i+1），…，B_N^（i+1），其中B₁^（i+1）=B_（N+1）/2^（i），B_N^（i+1）=B_N^（i），回到步驟（SI）進(jìn)行第（i+1）次測(cè)量，當(dāng)N值為l或返回排隊(duì)時(shí)延含有轉(zhuǎn)折點(diǎn)，計(jì)算得到源主機(jī)到目的主機(jī)之間可用帶寬的估計(jì)值。

（S2）源主機(jī)每隔t時(shí)間向目的主機(jī)發(fā)送數(shù)據(jù)包串進(jìn)行另外一次測(cè)量，該次測(cè)量的數(shù)據(jù)包串速率的范圍是上次測(cè)得可用帶寬數(shù)值的±M范圍，M取用帶寬數(shù)值的7%。t取決于網(wǎng)絡(luò)的實(shí)際情況，數(shù)據(jù)包串之間的包與包的之間的時(shí)間間隔t₁等于無線網(wǎng)絡(luò)中瓶頸鏈路的帶寬容量C除以前一個(gè)包發(fā)送的速率v，即t₁=C/v，該次測(cè)量的數(shù)據(jù)包串速率范圍是上次測(cè)得可用帶寬數(shù)值的±n的范圍，n可取可用帶寬數(shù)值的7%。

（S3）每次測(cè)量后，被測(cè)量的目的主機(jī)將把本次測(cè)量是否成功以及數(shù)據(jù)包串的排隊(duì)時(shí)延信息反饋回源主機(jī)，然后源主機(jī)根據(jù)反饋回的排隊(duì)時(shí)延信息計(jì)算得到這次測(cè)量可用帶寬的數(shù)值或者調(diào)整探測(cè)包串速率范圍的大??；當(dāng)源主機(jī)接收到的是數(shù)據(jù)包串的測(cè)量成功的信息，即反饋回來的排隊(duì)時(shí)延信息經(jīng)分析處理存在轉(zhuǎn)折點(diǎn)時(shí)，則重復(fù)步驟（S2）（S3），進(jìn)行下一次的測(cè)量，經(jīng)過多次測(cè)量以后，根據(jù)從目的主機(jī)返回的排隊(duì)時(shí)延信息對(duì)網(wǎng)絡(luò)的可用帶寬計(jì)算估測(cè)值E_m，將這些數(shù)據(jù)取平均值得出可用帶寬的估測(cè)值E_m⁰，然后選取處于估測(cè)值（1±b%） XE_m⁰的范圍的數(shù)據(jù)，其中b的典型取值為30，計(jì)算這些數(shù)據(jù)的平均值，得出新的可用帶寬的估計(jì)值E_m¹，并且求出這些數(shù)據(jù)的方差D₁。如果Dl>c，其中c的大小由系統(tǒng)對(duì)測(cè)量數(shù)據(jù)的精度來決定，c可取0.3～0.5，則選取出處于估測(cè)值（1±（b%～ 5%））E_m¹的范圍的數(shù)據(jù)，計(jì)算其平均值，并得到新的帶寬估計(jì)值E_m²以及對(duì)應(yīng)的方差D2，按調(diào)整范圍依次縮小5%的規(guī)律重復(fù)上述步驟，直到第n次選取的數(shù)據(jù)方差D_n^c。當(dāng)源主機(jī)接收到的是數(shù)據(jù)包串的測(cè)量不成功的信息，則將上一次的探測(cè)包串速率范圍變化±A，然后發(fā)送調(diào)整后的數(shù)據(jù)包，進(jìn)行另外一次的測(cè)量，同時(shí)計(jì)數(shù)器將測(cè)量不成功的次數(shù)加1，當(dāng)測(cè)量連續(xù)k次不成功，取4-6倍K，則源主機(jī)由步驟（SI）開始進(jìn)行重新測(cè)量。步驟（S3）中的當(dāng)源主機(jī)接收到的是數(shù)據(jù)包串的測(cè)量不成功的信息，探測(cè)包串速率變化范圍變化±A采用的變化原則是：當(dāng)沒有變化或者變化幅度很小，則源主機(jī)調(diào)整包串速率范圍使得數(shù)據(jù)包串的范圍上下限分別增大A，A取5%，并且重新發(fā)送數(shù)據(jù)包串進(jìn)行測(cè)量；當(dāng)沒有轉(zhuǎn)折點(diǎn)并且變化幅度很大，則源主機(jī)調(diào)整包串速率范圍使得數(shù)據(jù)包串的范圍上下限分別減小A，A取5%，并且重新發(fā)送數(shù)據(jù)包串進(jìn)行測(cè)量。

2.2 基于二分法的多跳無線網(wǎng)絡(luò)可用帶寬自適應(yīng)檢測(cè)方法的優(yōu)點(diǎn)

（1）每次的測(cè)量都是發(fā)送以上次的測(cè)量分析得到的可用帶寬數(shù)值為中心的一定速率范圍的包串，這樣可以減少對(duì)網(wǎng)絡(luò)的負(fù)載壓力，同時(shí)也縮短了測(cè)量的時(shí)間。（2）根據(jù)反饋回來的當(dāng)前網(wǎng)絡(luò)信息，自適應(yīng)的調(diào)整包串中包與包之間的間隔發(fā)送時(shí)間，不僅可以實(shí)現(xiàn)對(duì)無線網(wǎng)絡(luò)可用帶寬的實(shí)時(shí)監(jiān)測(cè)，還能減少數(shù)據(jù)包丟失和差錯(cuò)率，改善了網(wǎng)絡(luò)的性能。

3 結(jié)語

帶寬是衡量IP網(wǎng)絡(luò)性能重要的度量參數(shù)之一，對(duì)其準(zhǔn)確測(cè)量與估計(jì)是流量工程中網(wǎng)絡(luò)資源控制與QoS中接入控制必須解決的問題。本文基于二分法的多跳無線網(wǎng)絡(luò)可用帶寬自適應(yīng)檢測(cè)方法，不僅可以實(shí)現(xiàn)對(duì)無線網(wǎng)絡(luò)可用帶寬實(shí)時(shí)監(jiān)測(cè)，還能減少差錯(cuò)率和數(shù)據(jù)包的丟失，改善了網(wǎng)絡(luò)的性能。