韓盼盼 張巍

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

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

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

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

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

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

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

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

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

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

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

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

（3）如果返回的排隊時延不屬于步驟（l）和（2）的情況，則源主機重新選取包速率范圍被劃分的區(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）進行第（i+1）次測量。

（4）重復上述步驟，當N值為1或者返回排隊時延含有轉(zhuǎn)折點時，停止上述步驟。當返還的排隊時延含有轉(zhuǎn)折點時可以分析計算得到源主機到目的主機之間的可用帶寬的估計值；當返回的排隊時延沒有轉(zhuǎn)折點并且變化幅度很大，則源主機重新選取包速率范圍被劃分的區(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）進行第（i+1）次測量；當返回的排隊時延不屬于所述上述2種情況，則源主機重新選取包速率范圍被劃分的區(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）進行第（i+1）次測量，當N值為l或返回排隊時延含有轉(zhuǎn)折點，計算得到源主機到目的主機之間可用帶寬的估計值。

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

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

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

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

3 結(jié)語

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