基于網絡演算的衛星網絡端到端時延上界

魏德賓，王 旭，楊 力

(1. 大連大學通信與網絡重點實驗室，遼寧 大連 116622；2. 大連大學信息工程學院，遼寧 大連 116622；3. 南京理工大學自動化學院，江蘇 南京 210094)

1 引言

近年來，衛星網絡以其傳輸容量大、通信距離遠、不受地形及自然災害影響等特點得到廣泛應用，成為地面通信的有益補充，也是實現全球無縫覆蓋的重要手段。但是，衛星網絡與地面網絡相比帶來了更大的時延，而網絡的端到端時延作為網絡服務質量(Quality of Service，QoS)最重要的參數之一，其邊界分析的準確性直接影響到網絡QoS的保障水平。

目前，網絡的延時性能分析主要包括排隊論和網絡演算等方法。利用排隊論方法對網絡性能分析需要較精確的流量和服務模型，而對于當前日益復雜的網絡形態和業務流特征，上述模型很難獲得。網絡演算[1]采用上界描述業務流的到達過程，采用下界描述服務過程，從而獲得業務流的QoS性能界，使其分析方法更加靈活。文獻[2]利用網絡演算理論分析了無線多跳網絡數據流端到端的服務曲線且利用服務曲線求解該網絡的最大時延。周德新等人[3]利用網絡演算求出了航空電子全雙工交換以太網的時延上界。王子君等人[4]利用確定網絡演算理論推導出了控制網絡中的時延確定上界。文獻[5]利用網絡演算理論提出了基于分形漏桶的端到端時延上界模型。文獻[6]利用確定性網絡演算理論計算列車實時數據的端到端時延的上界。文獻[7]利用網絡演算對車聯網中端到端的數據傳輸進行建模，計算其QoS參數，并基于建立的性能模型和遺傳算法設計了車聯網的QoS路由算法。HUANG J等人[8]針對SDN網絡的QoS性能問題，提出一種混合調度模型，通過優先級隊列和包通用處理器共享結合，利用網絡演算進行建模來評估網絡QoS性能。文獻[9]利用網絡演算對內容中心網絡進行建模并分析其模型下LRU算法對數據流的影響。秦亮等人[10]針對遠程測試通信網絡實時性問題，建立了遠程測試系統的網絡演算模型，并利用網絡演算理論推導了遠程測試業務數據端到端延遲上界的數學計算方法。

上述文獻，針對不同的地面網絡環境通過傳統網絡演算推導時延上界，具有較好的表現。但是，在衛星網絡中，由于其鏈路傳播時延成周期性變化，且變化不能被忽略，傳統網絡分析方法[11-12]若是直接應用于衛星網絡，將會導致對傳播時延進行統一取值，不可避免的面臨計算準確性的挑戰。此外，為了得到端到端時延上界，傳統時延邊界計算過于放大排隊時延，導致計算時延邊界與實際時延相差較大，影響基于網絡演算的QoS控制算法性能。因此，如何利用網絡演算理論分析和精確求解衛星網絡的端到端時延上界成了本文所關注的問題。

針對上述問題，本文基于網絡演算提出了一種面向衛星網絡的端到端網絡模型與時延上界分析方法。首先根據衛星網絡節點軌道參數、星下點位置等推導星間鏈路長度計算公式，通過星間鏈路長度推算鏈路的傳播時延。其次，將鏈路處于峰值速率時的時延作為鏈路排隊時延的上界，并結合鏈路傳播時延與節點服務時延改進到達曲線。進一步，利用網絡演算推導出衛星網絡的端到端的時延上界。最后，分別研究網絡端到端路徑包含節點數目、節點服務速率、業務流權重值以及突發量等對衛星網絡端到端時延上界的影響。

本文余下部分組織如下：第2節給出了本文用到的網絡演算基本定義、推論；第3節給出衛星網絡節點間傳播時延計算公式；第4節給出了衛星網絡端到端時延上界；第5節對第4節的結論進行數值計算與比較分析；第6節是結束語。

2 相關概念

2.1 網絡演算理論

定義1(廣義遞增函數)：對于?s≤t，若f(s)≤f(t)成立，則稱f為廣義遞增函數。

定義2(廣義遞增函數集合)：若F={f(t)|f(t)=0，?t<0，f(s)≤f(t)，t∈[0，+∞]}則稱F為廣義遞增函數集合。

定義3(最小加卷積)：對于?f，g∈F，函數f和g的最小加卷積運算為

定義4(到達曲線)：給定一個函數α(t)，且α∈F，t≥0，若輸入流函數A滿足A≤A?α，則稱α是A的到達曲線。

定義5(服務曲線)：對于β∈F，β(0)=0，若滿足輸出流A*≥A?β，則稱系統為數據流提供服務曲線β(t)。

推論1(水平偏差)：設一個流進入系統時被到達曲線α(t)約束，通過系統時系統提供服務曲線β(t)，則時延d(t)滿足

其中，h(α，β)也稱作曲線α和β之間的水平偏差。

推論2(串聯節點服務曲線)：系統1和系統2串聯后提供的總服務曲線β為系統1提供的服務曲線β1和系統2提供的服務曲線β2的最小加卷積，即

β=β1?β2

3 星間鏈路傳播時延分析

星間鏈路是衛星網絡的重要組成部分，它可以在不依賴地面設備的情況下實現所有網絡節點的連接，將衛星組合為一個整體。設Re為地球半徑，hA，hB分別為衛星A與衛星B所在的軌道高度，(λ1，φ1)，(λ2，φ2)分別為衛星A與衛星B的星下點經緯度，它可由星歷得到。則星間鏈路長度dBA可表示為

α=arccos[sin(φ1)sin(φ2)+cos(φ1)cos(φ2)cos(λ1-λ2)]

2顆衛星鏈路長度如圖1。

圖1 星間鏈路長度示意圖

在實際情況中，由于星間鏈路會受到地球的遮擋，因此任意2顆處于不同軌道的衛星，它們之間的星間鏈路長度應存在一個最大值，即為最大可見鏈路長度，如圖2。

圖2 最大可見鏈路長度示意圖

此時，衛星A與衛星B之間的鏈路長度dBA為其最大可見鏈路長度，可以表示為

由上述分析，可以得到兩顆衛星星間鏈路長度計算公式，然后通過星間鏈路長度以及光速，得到節點之間的傳播時延Dl為

其中，c為光速。

4 衛星網絡端到端時延上界

衛星網絡的端到端路徑模型，如圖3。

圖3 端到端網絡模型

衛星網絡中節點1與節點m之間存在m-2個中間節點，當業務流A(t)到達節點時，會受到該節點參數為(r，b)的令牌桶限制，也即受該節點的到達曲線α(t)=rt+b的約束，b為突發通信量，r為數據流長期平均速率。

對于業務流A(t)，通過的每一個節點都會為業務流提供一定的服務能力。所以對任一網絡節點，不管采用何種隊列調度算法，都可以假定節點對數據流提供速率—延時服務曲線作為對數據流的服務保證。由此可得，路徑中節點提供的服務曲線為：

(1)

其中，C表示節點所提供的服務速率，T表示數據分組在節點的服務延遲。在這里，延遲參數可以認為是包處理時延，因此網絡節點的延遲參數表示為

T=L/C

(2)

其中L表示最大包長。

又因為在衛星網絡中，會存在多條業務流Ai(t)同時到達一個節點。假設業務流之間互相獨立，且共享鏈路帶寬W，為了業務流都可以得到相應的服務，在這里根據各業務流所分配的權重來進行帶寬分配。若有n條業務流，假設業務流Ai(t)，i=1，2，…，n所分配的權重為ωi，則分配給業務流Ai(t)的服務速率Ci為

(3)

本文中使用上式中的Ci來代替式(1)中的C所得到的曲線為某個業務流Ai(t)的業務服務曲線。

在衛星網絡中，端到端時延由節點處系統緩存的排隊時延和鏈路傳播時延以及節點間的發送時延3部分組成。

定理1(單節點時延上界)：假設一個業務流Ai(t)通過節點p，該節點的到達曲線為α，服務曲線為β，則該業務流通過該節點的延時Dp為

(4)

其中，Wt為上一節點到目前節點的鏈路的峰值速率。Ti表示業務流Ai(t)在節點p處的服務延遲。

定理2(端到端時延上界)：假設一個業務流Ai(t)依次通過m個節點，節點中的到達曲線依次為αi，i=1，2，…，m，系統的服務曲線依次為βi，i=1，2，…，m，相鄰2個節點之間的傳播時延依次為Dl1，Dl2，…，Dlm-1，中間節點的發送時延依次為：Df1，Df2，…，Dfm-1，則端到端時延上界D1→m為

(5)

證明：用數學歸納法證明。

所以第1、2兩個節點之間的端到端時延為

D1→2=D1+Dl1+Df1+D2

由此可見，式(5)成立。

2)假設當m=k-1時，定理2成立，即

由定理1可以得出，第k個節點的時延為

顯然，節點1到節點k的端到端時延D1→k等于其前k-1個節點的時延D1→k-1和第k個節點的時延Dk之和，即

D1→k=D1→k-1+Dk

5 仿真驗證

5.1 仿真設置

本文仿真以銥星星座為網絡模型進行仿真和數值計算。具體星座參數見表1。

表1 銥星星座參數

其中，衛星間的ISL(Inter Satellite Link)鏈路帶寬是500Mb/s，數據流長期平均速率為80Mb/s，數據流的突發量為200kbits，系統的服務速率為100Mb/s，兩相鄰節點的發送時延設定為0.2ms，包的平均大小為1000bits。根據所設定的參數以及銥星星座拓撲如(圖4所示)，分別研究端到端路徑所含節點數目、節點服務速率、業務流權重值以及突發量等對衛星網絡端到端時延上界的影響。

圖4 銥星星座拓撲圖

5.2 實驗結果分析

將本文提出的衛星網絡的端到端時延上界與基于令牌桶的端到端理論時延上界以及MATLAB仿真得到的銥星星座端到端時延上界進行比較，結果如圖5所示。

圖5 端到端時延與路徑節點數

從圖5可以看出，當衛星網絡端到端節點數目增加時，理論時延與仿真時延都增大，且基于令牌桶的端到端時延要較本文所提方法的理論值偏高。這是因為：第一，本文基于衛星網絡的端到端時延上界分析方法，考慮了衛星網絡節點隨時間變化，其傳播時延也隨之變化的特點。第二，將鏈路處于峰值速率時的時延作為鏈路排隊時延的上界，計算得到衛星網絡端到端時延上界更加準確。此外，隨著路徑中節點數目的增加，仿真得到的時延與本文所提方法的理論時延上界越來越接近，此結果反映了當鏈路上的節點數多時，網絡演算能反映真實的網絡時延性能。

在圖6中，設定端到端路徑中的節點數為7。從圖中可以看出，當服務速率值較小時，仿真值與理論的時延差距較大，這是因為鏈路負載過重，造成網絡擁塞，從而導致仿真值與理論計算的時延差距較大，隨著服務速率的增大，網絡狀況轉好，仿真值與理論時延差距逐漸減小，尤其是在服務速率達到400Mb/s之后，仿真值與理論時延差距較小，更加接近本文所提方法求得的理論值。

圖6 端到端時延與服務速率

當端到端路徑中的節點數為7時，從圖7可以看出，理論時延與仿真時延都隨著業務權重值的增大而減小，且這種減小的趨勢變得越來越平坦。這是因為隨著業務權重值的增大，節點的服務速率也隨之增大，導致時延隨業務權重值的增大而減小。但是在權重值小于0.5時，時延下降較快，而權重值大于0.5之后，趨于平坦。這是因為隨著節點的服務，網絡趨于穩定，使得相應的數據流都得到了相應服務，從而導致時延趨于平緩。網絡端到端時延仿真值與本文所提出方法求得的時延理論值上界越來越接近，從而驗證了基于網絡演算推導得出的衛星網絡時延上界能更好的反映地衛星網絡性能。

圖7 端到端時延與權重

當端到端路徑中的節點數為7時，從圖8中可以看出，隨著突發量的增加，端到端仿真時延值也隨之增大。而在仿真初期，端到端仿真時延值增長速度過快，而在達到一定突發量值時，端到端時延趨于平緩并接近理論值。這是因為在仿真初期，網絡并不穩定，而此時突發量在增加，導致時延增長速度較快，而在網絡處于相對穩定之后，隨著突發量的增加，且節點間具有負載均衡能力，使得時延增長緩慢。

圖8 端到端時延與突發量

當端到端路徑中的節點數為7時，從圖9中可以看出，隨著鏈路帶寬的增加，端到端仿真時延值也隨之增大。而在仿真初期，端到端仿真時延值增長速度過快，而在達到一定鏈路帶寬值時，端到端時延趨于平緩并接近理論值。這是因為在仿真初期，網絡并不穩定，節點服務速率小于鏈路帶寬，導致時延增長速度較快，而在網絡處于相對穩定之后，隨著鏈路帶寬的增加，且節點間具有負載均衡能力，使得時延增長緩慢。

圖9 端到端時延與鏈路帶寬

當端到端路徑中的節點數為7時，從圖10中可以看出，隨著兩節點間的發送時延的增加，端到端仿真時延值也隨之增大，且越來越接近于本文所提方法求得的理論值。這是因為，兩節點間的發送時延的增加，導致節點轉發效率降低，使得時延增長較快，但是在網絡處于相對穩定之后，隨著發送時延的增加，且節點間具有負載均衡能力，使得時延增長緩慢，更加接近本文所提方法求得的理論值。

圖10 端到端時延與發送時延

6 結論

本文提出的衛星網絡的端到端時延分析方法，通過計算星間距離得到傳播時延，以及設置節點的到達曲線與服務曲線并結合衛星網絡模型，推導出了衛星網絡的端到端的時延上界。仿真結果表明，本文方法得到的衛星網絡端到端時延上界比傳統方法更接近于仿真值，能夠為網絡QoS控制提供支持。