基于M／M／1模型的網絡及時可靠性加速模型

李瑞瑩 康 銳 黃 寧

（北京航空航天大學 可靠性與系統工程學院，北京100191）

隨著網絡技術的不斷發展與應用，對網絡的定量與定性特征的科學理解，已成為一個極其重要的挑戰性課題，甚至被稱為“網絡的新科學”［1］.隨著網絡使用的普及，網絡負載增大，由擁塞造成的及時可靠性已經成為網絡定量特征理解的重要問題.

在一個新的網絡建成前，在一種新的服務投入使用前，試驗是考核網絡可靠性的重要途徑.然而，網絡任務周期普遍較長，為了有效暴露故障，網絡可靠性試驗時間往往是其任務周期的數倍［2］，這直接導致研制周期過長，對基于長時間效應的傳統可靠性試驗技術提出了挑戰.1967年，美國羅姆航空發展中心提出了加速壽命試驗（ALT，Accelerated Life Testing）方法［3］，使高可靠長壽命產品可靠性水平的快速評定成為可能，并廣泛應用于航空航天、武器裝備及機械電子等領域［4］.為了快速在可靠性試驗中暴露設計缺陷，確定網絡可靠性水平，也有必要采取加速試驗，增大單位時間內的循環次數，加速故障模式的出現.

文獻［5］提出故障過程的加速性是設計加速試驗的前提，即要求在保持產品故障機理不變的情況下，產品可靠性特征參數與應力之間存在一個確定的函數關系，稱為加速模型［6］.網絡服務層的應力主要體現為工作應力，即用戶對網絡服務的使用，也就是網絡的負載或數據包的到達.網絡及時可靠性的故障模式為時延過長，網絡的排隊機制［7］為探索延遲故障機理以及確定加速模型提供了支撐，典型的通信網絡排隊機制包括M／G／1，M／M／1，M／D／1，M／M／C，D－MAP／PH／1，DBMAP／PH／1［8－9］等.相似理論［10］是確定加速模型的理論依據，如文獻［11］在對混凝土結構的耐久性試驗中，分析了混凝土結構在室內加速試驗環境與現場自然環境條件下性能退化的時間相似關系，提出多重環境時間相似理論；文獻［12］對加速試驗中起關鍵作用的時間相似的各類情況進行了討論.流體力學是相似理論的重要應用領域［10］，對于通信網絡而言，網絡中數據也是一種流體，數據的流動也需要服從相應的規律，即排隊機制.文獻［13］結合運動相似和力相似的原理，采用拓撲結構簡化、網絡流合并等技術給出了一種網絡可靠性相似建模的初步方案，但其對網絡建模粒度較粗，沒有考慮網絡流量與服務機制的影響，同時對相似性實現原理研究不夠深入，缺乏相應的模型驗證.

本文以相似理論為理論基礎，研究通信網絡最簡單的排隊模型——M／M／1模型對應的網絡及時可靠性加速模型，并通過OPNET仿真平臺進行驗證.

1 基本概念

網絡可靠性是指網絡在規定條件下和規定時間內完成規定功能的能力.由于網絡使用量日益劇增，網絡可靠性研究焦點已集中到“及時可靠性”，即網絡能否及時地傳輸信息，其故障判據是網絡端到端傳輸時延超過用戶容許范圍，及時可靠度可以表達［14］為式中，D（t）表示t時刻的網絡端到端傳輸時延；Dmax表示用戶允許的最大時延，也就是故障判據.

網絡端到端時延包括4個部分，即：處理時延Tp、傳輸時延Tt、傳播時延Tg和排隊時延其中，前三者均取決于節點處理速度和信道傳播速度，且量值與排隊時延相比很小，因此對網絡端到端時延影響最大的是排隊時延，主要因素包括鏈路的負載情況、隊列管理機制、緩沖區管理機制、接口處理能力等.

試驗中，網絡及時可靠度的統計方法為

式中，Nt（Δt）表示t時刻以后的Δt時間段內網絡傳輸的數據包總個數；Nn（Δt）表示t時刻以后的Δt時間段內網絡傳輸時延不超過用戶允許的最大時延Dmax的數據包個數，也就是傳輸及時的數據包個數.

2 故障機理分析

常見的通信網排隊模型包括 M／M／m（n），M／D／m（n），M／Er／m（n）等［16］.M／M／1模型是以太網交換機的初級應用，其表達的含義為：網絡數據到達時間間隔服從參數為λ的負指數分布，服務時間服從參數為μ的負指數分布，服務臺數為1，無損失，服務機制為先到先服務，其排隊過程如圖1所示.

圖1 網絡通信M／M／1排隊過程

在M／M／1的排隊系統中，網絡數據包到達后，如交換機空閑，則開始提供數據交換服務，否則排隊等待，直到前面所有的數據包完成數據交換.如果等待時間過長，達到故障判據，則發生延遲故障.

對于M／M／1排隊系統，有兩類情況，當系統服務強度ρ＝λ／μ＜1時，系統能達到統計平衡，網絡排隊時延隨時間變化如圖2a所示；否則，數據到達累積會越來越多，系統無法達到穩態，網絡排隊時延越來越長，其隨時間變化如圖2b所示.

因此，這里只分析服務強度ρ＝λ／μ＜1的情況.ρ＝λ／μ＜1時，數據包在服務系統中的逗留時間分布函數為［7］

圖2 不同服務強度下M／M／1系統的排隊時延

式中，W（t）是數據包的逗留時間，為等待時間與服務時間之和.實際上，這就是通信網絡及時可靠度的表達式.式（3）中，t就是給定的時延閾值Dmax.結合式（2）和式（3），網絡及時可靠度可以表達為

式中，μ（t）表示t時刻的網絡平均服務時間；λ（t）表示t時刻的平均數據到達時間間隔；Dmax表示用戶允許的最大時延.

3 基于相似理論的加速模型

下面針對式（4），采用相似理論的方程分析法推導加速模型.令原始現象為

相似現象為

式（5）中有5個物理量（R，λ，μ，D，t），令相似常數分別為cR，cμ，cλ，ct和cD，即

將式（7）代入式（6），有

考慮到式（5）中只有2個物理量綱（s和bit，即時間量綱和信息量綱［17］），則根據相似第二定理，可知其相似準則數應為：物理量個數－基本量綱個數＝3個.簡單起見，要求相似現象中的可靠度R′（t′）與原始現象中的可靠度R（t）保持不變，即cR＝1；且取平均數據到達間隔時間和平均服務時間的相似常數相等，即cμ＝cλ；根據相似第一定理，聯立式（5）和式（8），則可得cμ·cD＝1.

由此，整理出 M／M／1排隊網絡的3個相似準則為

同時，要使兩個現象相同，還需要滿足相似第三定理，即要求單值量相似，也就是要求幾何條件、介質條件、邊界條件和起始條件.在本問題中，僅涉及起始條件，即要求兩個現象t0時刻狀態相同，而通常情況下，只要t0時刻起開始施加流量，即可保證t0時刻狀態相同.

總結起來，根據相似理論三大定理可知，在如下情況下，基于M／M／1模型的網絡排隊及時可靠度等價：

1）網絡平均服務時間和網絡平均數據到達時間間隔同比例變化，即cμ＝cλ；

2）網絡平均服務時間、平均數據到達時間間隔的變化與用戶允許的最大時延的變化成反比，即cμ·cD＝1；

3）t0時刻起開始施加流量，即t0時刻狀態相同.

隨著網絡數據到達強度的增加，相同時間內到達的數據包個數增多，可靠性信息量增大.為了達到可靠性試驗截尾所需的數據量要求［18］，當網絡數據到達強度增大ε倍以后，試驗時長可減小ε倍，兩次試驗的數據量不變.即試驗時長和網絡數據到達強度的關系為

4 仿真驗證

為了驗證第3節提出的加速模型，根據網絡數據到達強度是否變化設計了兩類實驗.

4.1 數據到達強度不變的情況

在該案例中，網絡服務率為9 600bit／s，數據到達強度服從均值為1.0包／s的負指數分布，數據包大小服從均值為9 000bit的負指數分布，服務機制采用M／M／1的排隊模型.

假定網絡延遲故障服從二項分布［19］，取檢驗上限R＝0.999，鑒別比D＝1.50，生產方風險α和使用方風險β為10%，那么，可靠性鑒定試驗中要求至少需要收集32 922個數據包的時延信息，因此至少需要仿真9.145h，才可到達此數量的數據包.應用OPNET仿真10h，總共收集到36 209個數據包，每個數據包的排隊時延如圖3所示.

取用戶允許的最大時延要求Dmax＝60s，發現有969個數據包不符合要求，則可知網絡不能滿足R＝0.999的要求.

圖3 原始網絡每個數據包的排隊時延

下面建立相似網絡，根據第3節確定的加速模型，取cμ＝cλ＝4，cD＝ct＝0.25，t0時刻狀態相同.如此，網絡服務率為38 400bit／s，平均數據到達時間間隔服從均值為4.0包／s的負指數分布，數據包大小服從均值為9 000bit的負指數分布，服務機制仍采用M／M／1的排隊模型.根據加速模型，仿真2.5h，共收集到36 180個數據包，每個數據包的排隊時延如圖4所示.由圖可知，相似網絡的排隊時延與原始網絡基本一致.

圖4 相似網絡每個數據包的排隊時延

根據加速模型，取用戶允許的最大時延要求Dmax＝15s，發現有969個數據包不符合要求，可知網絡不能滿足R＝0.999的要求，這一結論與原始網絡相同.

隨后，在原始網絡和相似網絡中分別以10min和2.5min為間隔，根據式（2）計算網絡端到端及時可靠度的點估計值，兩者的對比如圖5所示，經計算其均方誤差為0.012 06.

圖5 原始網絡和相似網絡的及時可靠度對比

表1討論了在不同的延遲故障判據下，原始網絡和相似網絡及時可靠度的均方誤差.在本案例中，當原始網絡時延閾值在30～60s變化時，兩個網絡及時可靠度的均方誤差變化不大.由此可知，延遲故障判據的取值大小并不影響原始網絡和相似網絡在及時可靠度上的相似性.

表1 故障判據對加速模型的影響

表2進一步討論了網絡在不同的應力增加倍數下，原始網絡和相似網絡可靠度的均方誤差.這里，當應力增加倍數在2～12倍變化時，兩個網絡及時可靠度的均方誤差變化也不大.這說明，網絡應力增加的倍數也不影響原始網絡和相似網絡在可靠度上的相似性.

在上述分析中，由于每個Δt時間段（原始網絡中Δt＝10min，相似網絡中Δt＝2.5min）只有約600個數據，故而兩個網絡的及時可靠性尚存在一定的誤差.如果增加單位時間的數據量，則誤差將大幅減小，如表3、表4所示，其絕對誤差基本都在10－5附近.這也就是說，應用第3節提出的加速模型構建的相似網絡，其及時可靠性與原始網絡非常接近，且與延遲故障閾值、應力增大倍數的選取無關.

表4 應力增加倍數對加速模型的影響

4.2 數據到達強度變化的情況

網絡運行過程中，數據到達強度隨時間往往是變化的，這里再構造一個數據到達強度變化的案例.在該案例中，網絡服務率為9 600bit／s，數據包大小服從均值為9 000bit的負指數分布，數據到達強度也服從負指數分布，其均值與時間的對應關系如圖6所示（始終滿足ρ＝λ／μ＜1）.服務機制采用M／M／1的排隊模型.

圖6 數據到達強度隨時間變化關系

根據第3節確定的加速模型，取cμ＝cλ＝4，cD＝ct＝0.25，t0時刻狀態相同，建立相似網絡.如此，網絡服務率為38 400bit／s，數據到達強度均值與時間的對應關系變化如圖6所示，排隊模型中的其他信息不變.

應用OPNET在原始網絡中仿真24h，得到50 612個數據包，在相似網絡中仿真6h，得到50 611個數據包，兩個網絡中，每個數據包的排隊時延分別如圖7、圖8所示，基本一致.

圖7 原始網絡每個數據包的排隊時延

在原始網絡和相似網絡中分別以10min和2.5min為間隔，取用戶允許的最大時延要求Dmax＝30s（相似網絡中Dmax＝7.5s），根據式（2）計算網絡端到端及時可靠度R（t）的點估計值，兩者的對比如圖9所示，經計算其均方誤差為0.001 155.這說明，第3節的加速模型對數據到達強度變化的M／M／1排隊網絡仍然適用.

圖8 相似網絡每個數據包的排隊時延

圖9 原始網絡和相似網絡的可靠度對比

由此可知，對于服務機制采用M／M／1的排隊模型的網絡，在排隊時延能達到穩定的情況下（即ρ＝λ／μ＜1），可以運用第3節的加速模型，設計加速試驗方案，通過短時高應力條件下的網絡及時可靠性反映正常應力下的及時可靠性.

5 結 論

本文分析了M／M／1排隊網絡的延遲故障機理，并根據相似三大定理，推導了端到端及時可靠性相似準則，得到了加速模型，并應用OPNET平臺對該加速模型進行了驗證.該加速模型適用于服務強度ρ＝λ／μ＜1的 M／M／1排隊網絡，通過增大數據到達強度，可有效縮短試驗時間，解決網絡可靠性試驗時間長、成本高的問題.仿真結果表明相似誤差小，且該加速模型的效用不隨故障閾值、應力增加倍數變化，該加速模型為規劃網絡可靠性加速試驗奠定了重要基礎.接下來，需要進一步討論其他排隊模型下的網絡可靠性加速模型，并進行試驗驗證.

（

）

［1］Duncan J Watts.The“new”science of networks［J］.Annual Review of Sociology，2004，30：243－270

［2］張建濤，張劍.軍用通信網綜合可靠性試驗與檢驗［J］.電子產品可靠性與環境試驗，2007，25（2）：19－22 Zhang Jiantao，Zhang Jian.Integrated reliability test and inspection for military communication network［J］.Electronic Product Reliability and Environmental Testing，2007，25（2）：19－22（in Chinese）

［3］Yurkowsky W，Schafer R E，Finkelstein J M.Accelerated testing technology［R］.RADC－TR－67－420，1967

［4］張春華，溫熙森，陳循.加速壽命試驗技術綜述［J］.兵工學報，2004，25（4）：485－490 Zhang Chunhua，Wen Xisen，Chen Xun.A comprehensive review of accelerated life testing［J］.ACTA Armament Arii，2004，25（4）：485－490（in Chinese）

［5］Nelson W.Accelerated life testing－step stress models and data analysis［J］.IEEE Transactions on Reliability，1980，29（2）：103－108

［6］張志華.加速壽命試驗及其統計分析［M］.北京：北京工業大學出版社，2002 Zhang Zhihua.Accelerated life testing and its statistics analysis［M］.Beijing：Press of Beijing University of Technology，2002（in Chinese）

［7］唐應輝，唐小我.排隊論－基礎與分析技術［M］.北京：科學出版社，2006：33 Tang Yinghui，Tang Xiaowo.Queuing theory－basics and analysis technology［M］.Beijing：Science Press，2006：33（in Chinese）

［8］朱信忠.網絡分組交換中的排隊論模型分析［J］.微機發展，2003，13：29－30 Zhu Xinzhong.Queuing theory model analysis of network packet switching［J］.Microcomputer Development，2003，13：29－30（in Chinese）

［9］何志鵬.基于排隊論的Ad Hoc網絡性能分析［D］.蘭州：蘭州理工大學電氣工程與信息工程學院，2008 He Zhipeng.Network performance analysis for Ad Hoc based on queuing theory ［D］.Lanzhou：School of Electrical and Information Engineering，Lanzhou University of Technology，2008（in Chinese）

［10］徐挺.相似理論與模型試驗［M］.北京：中國農業機械出版社，1982 Xu Ting.Similarity theory and model testing［M］.Beijing：Chinese Agriculture Machine Press，1982（in Chinese）

［11］金立兵，金偉良，王海龍，等.多重環境時間相似理論及其應用［J］.浙江大學學報：工學版，2010，44（4）：789－797 Jin Libing，Jin Weiliang，Wang Hailong，et al.Multi－environmental time similarity theory and its application ［J］.Journal of Zhejiang University：Engineering Science，2010，44（4）：789－797（in Chinese）

［12］張馳 李新東.相似理論中時間相似的達成與意義 ［J］.鄭州鐵路職業技術學院學報，2011，23（2）：15－17 Zhang Chi，Li Xindong.Time similarity and its significance in similarity theory［J］.Journal of Zhengzhou Railway Vocational ＆ Technical College，2011，23（2）：15－17（in Chinese）

［13］Li Ruiying，Kang Rui，Huang Ning，et al.A practical approach for network application reliability assessment［J］.Eesploatacja I Niezawodnosc－Maintenance and Reliability，2009，43（4）：17－27

［14］李碩，黃寧，李瑞瑩，等.通信網絡服務可靠性參數分析［J］.系統工程與電子技術，2012，34（9）：1946－1950 Li Shuo，Huang Ning，Li Ruiying，et al.Analysis for service reliability parameters of communication networks［J］.Systems Engineering and Electronics，2012，34（9）：1946－1950（in Chinese）

［15］裴昌幸.現代通信系統與網絡測量［M］.北京：人民郵電出版社，2008：108－109 Pei Changxing.Modern communication system and network mesurement［M］.Beijing：Posts ＆ Telecom Press，2008：108－109（in Chinese）

［16］紀陽.通信網理論概要［M］.北京：北京郵電大學出版社，2008：109 Ji Yang.Communication network theory summary［M］.Beijing：Beijing University of Posts and Telecommunications Press，2008：109（in Chinese）

［17］鄧宇，鄧非，戴瀕君，等.信息運動學與動力學－信息運動三定律［J］.職業與健康.2007，23（19）：1750－1752 Deng Yu，Deng Fei，Dai Pingjun，et al.Information kinematics and dynamics：three laws of information kinematic［J］.Occup Health，2007，23（19）：1750－1752（in Chinese）

［18］GJB 899A－2009可靠性鑒定和驗收試驗［S］GJB 899A－2009Reliability testing for qualification and production acceptance［S］（in Chinese）

［19］Li Meinan，Li Ruiying.The failure distribution for service layer of communication networks［C］／／The 2nd International Conference on Consumer Electronics，Communications and Networks.Three Gorges，China：IEEE，2012