基于多星ＬＡＮ的競爭沖突淘汰存取方式仿真建模的探討

(1.青島科技大學 信息科學與技術學院， 山東 青島 266061；2.煙臺大學 計算機學院， 山東 煙臺 264005)

摘 要：競爭—沖突淘汰（CCC）存取方式是多星局域網（LAN）的存取控制方式，根據多星LAN的設計原理，CCC存取方式分為六類系統模型。利用OPNET仿真平臺，構建多星LAN并實現CCC存取方式Ⅰ類系統模型的仿真。通過仿真建模，將仿真結果與已有理論結果進行了比較；分別得到了M=2和M=4條件下多星LAN的三個性能參數，即數據包延遲、中心節點的隊列長度和吞吐量，并進行了性能比較與評價。

關鍵詞：仿真建模；多星局域網；競爭—沖突淘汰存取方式；OPNET

中圖分類號：TP393 文獻標志碼：A

文章編號：10013695(2009)01028003

Probing of simulation modeling for contention collision cancellation access mode based on multistar LAN

SUN Lijun1， WANG Lihong2

(1.School of Information Science Technology， Qingdao University of Science Technology， Qingdao Shandong 266061， China；2.School of Computer Science， Yantai University， Yantai Shandong 264005， China)

Abstract:Contentioncollision cancellation（CCC） access mode is an important access control mode in multistar local area network (LAN).According to the multistar LAN’s working mechanism and design principle， CCC access mode was classified six types of system model.This paper discussed the process of constructing the multistar LAN and implementing type Ⅰ system model using by OPNET modeler.Through simulation modeling，compared the simulation result with the theoretical result in previous reference，got 3 performance parameters for multistar LAN:packet delay， the queue size and throughput of central node.

Key words:simulation modeling; multistar LAN; contentioncollision cancellation access mode; OPNET

競爭—沖突淘汰（contentioncollision cancellation，CCC）訪問控制方式是多星LAN的介質訪問方式。多星LAN的運行機理文獻［1］已有詳盡闡述，因本文仿真需要，略作描述。如圖1所示多星LAN，中心節點有M條交換通道，M≥1；用戶終端數為N，N>>M。每個終端的緩沖區只能容納一個數據單元。數據單元有固定的長度，一旦產生就被復制一份寄存于緩沖區中，被正確發送之前就在緩沖區等待。數據單元通過中心節點時，如果同時要求通過的數據單元數>空閑通道數，就會因競爭通道發生沖突。此時中心節點從發生沖突的多路數據中隨機選擇與空閑通道數相等的數據單元讓其通過，其余的被淘汰。被選中的數據單元如果正確通過（以下稱服務成功），則源終端會收到響應單元ACK；如果服務不成功，則源終端收到NAK，且重新請求發送原數據單元。在沖突時被淘汰的數據經過“超時”時間后，由源終端重新發送。總之，CCC方式可歸結為：終端發送數據后，在某一確定時間內，要么收到ACK，要么收到NAK，要么因淘汰而“超時”。收到ACK后，終端有可能發送下一個信息單元；收到NAK或發生“超時”時，終端的原數據重新發送。

人們根據多星LAN的運行機理將CCC方式分為Ⅰ～Ⅵ類［2］系統模型。在單星LAN的條件下（即M=1），關于這六類系統模型的數學建模和性能評價的研究均取得了重要突破［3~8］。但是存在兩個問題：a）當中心節點通道M>1時，數學解析方面存在很大困難；b)數學模型是一個理論模型，網絡性能參數的理論值通常與實際值存在一定誤差。究竟網絡在實際運行中會出現什么問題、吞吐量如何還有待于進一步研究。在這種情況下，考慮到另一種研究網絡的方法——仿真建模。

OPNET是一個優秀的網絡協議建模和仿真工具［9］，面向對象的建模方法和圖形化的編輯器反映了真實的網絡和網絡組件的結構，因此用OPNET可以直觀地將實際的系統映射到模型中，并預測網絡系統的性能。

1 OPNET仿真建模

11 CCC存取方式Ⅰ類系統模型

在CCC存取方式的系統模型中，將中心節點的交換通道當做服務員，將用戶終端產生的數據單元當做顧客，Ⅰ類系統模型如圖2所示。顧客第一次請求服務、再次請求服務均只有在服務員空閑時發生，獲得服務權的顧客如果服務失敗，則保留服務權，再次接受服務，直到服務成功；或者可設定服務員一次服務成功。

本文采用OPNET平臺，對Ⅰ類系統模型在服務一次成功的條件下進行仿真建模。服務流程如圖3所示。

12 網絡域和節點域建模

OPNET提供了一個支持通信網絡和分布式系統建模的綜合開發平臺，OPNET采用離散事件驅動的模擬機理，動態地模擬實際系統的行為。所謂事件是指網絡狀態的變化，只有網絡狀態發生變化時，模擬機才工作。

OPNET中的建模工作在三種不同的環境中完成。這三個環境也稱為建模域，分別是網絡域、節點域和進程域。網絡域的作用是定義通信網絡的拓撲結構；在節點域可以為網絡中配置和互連好的通信設備建立模型；進程域中用有限狀態機來描述協議。

多星LAN由一個中心節點和N個用戶終端節點組成。對應于三個建模域的各部分如表1所列。圖4以N=60為例，直觀地表示了網絡域與節點域所包含的模塊。

表1 多星LAN到OPNET模型的映射

網絡域星型拓撲

節點域中心節點（一個）用戶終端（N個）

進程域收發器（N對）、switch進程收發器（一對）、data_gen進程、handle進程

13 進程域建模

用戶終端節點的data_gen進程負責產生數據單元。為了與已有的CCC數學模型結果相比較，數據到達還是采用獨立二項式分布。時間軸離散化，被劃分為以時隙為單位的小間隔。在一個時隙內，用戶終端最多可以產生一個數據單元。設定緩沖區空閑的用戶終端在一個時隙內產生一個數據單元的概率為Pc。

用戶終端節點的handle進程負責數據單元的發送、接收和處理，既將data_gen產生的數據處理后發送，又處理從中心節點接收來的數據，統計數據包延時。

中心節點的switch進程負責從所有請求的數據單元中隨機選擇與空閑通道數相等的數據單元進行處理、發送。每個顧客被服務完后的一個時隙內，中心節點會被置為空閑狀態；一個時隙過后再查看是否有請求的數據單元。這樣設置的目的是能夠讓用戶終端測到中心節點空閑，有機會產生數據單元或重新請求服務。

由于篇幅所限，僅對switch進程域進行圖表說明，狀態轉移圖和狀態轉移響應表如圖5和表2所示。



2 仿真結果與性能評價

本文的仿真設計分為兩部分：a）為了與文獻［3］的理論結果進行比較，令用戶終端數N=60、交換通道數M=1，構建了單星LAN運行仿真、采集統計量，最后得到了系統顧客數與等待時間的數值關系圖。b)令用戶終端數N=200、交換通道數M分別為2、4，構建了多星LAN，選取了三個統計量，即數據包平均延遲、中心節點的平均隊列長度和吞吐量。

如果設網絡的傳輸速率為100 Mbps，則位時寬為10 ns，也就是時隙寬度可取值到10 ns。其他設定如下：傳播時延為50個時隙；中心節點的處理時延為10個時隙；數據單元長度為256 bit；響應單元ACK長度為64 bit。每次運行時間為105個時隙。

21 單星LAN仿真結果與理論值的比較

文獻[3]為M=1條件下的Ⅰ類系統模型建立了數學模型，得到了等待時間τi的表達式

τ0=++N-1j=1[j/（j+1）]tjP0j(A=1)+N-2j=0τjP0j(A=0)

τi=+N-1j=1tjPij(A=1)+N-2j=0τjPij(A=0)

其中：τi表示在觀察時點系統顧客數為i，且觀察終端A無顧客的條件下，至終端A顧客第一次被服務結束的時間；為空閑期的平均長度；為服務期的平均長度；Pij(A=1)表示觀察時點系統顧客數為i，觀察終端A有顧客的條件下，至下一觀察時點系統顧客數變為j的概率；Pij(A=0)表示觀察時點系統顧客數為i，觀察終端A無顧客的條件下，至下一觀察時點系統顧客數變為j的概率。

令Pc分別取0.05、0.5、0.95，運行仿真得到了系統顧客數與等待時間的關系圖，并與文獻[3]的理論結果進行了比較，如圖6所示。仿真結果與理論值非常接近，從仿真的角度證明了文獻[3]數學模型的正確性。

22 多星LAN性能評價

由于計算機網絡的迅速發展，用戶終端數量高速增長，只具有一個交換通道的單星LAN已經不能滿足實際的需要。當局域網的用戶終端較多時，單星LAN就要擴展為多星LAN。令用戶終端數N=200、交換通道數M為2和4，分別進行了兩組實驗。為考察不同負載對性能參數的影響，實驗中Pc值分別取0.001、0.01、0.05、0.5、0.6、0.7、0.8、0.9、0.95，最后得到三個參數的曲線如圖7~9所示。

圖7是M=2和M=4兩組實驗的中心節點平均隊列長度曲線圖。從圖7中可以看出，無論M取2或4，平均隊列長度曲線均在一開始短時間內急速上升，到達頂峰后很快回落，最后趨于穩定。這是由于在仿真一開始，中心節點的初始狀態處于空閑，所有的用戶終端均測到該空閑狀態并以一定概率產生數據，這些數據在中心節點排隊，造成了隊列長度在仿真最初階段的突發性增長。系統穩定后，Pc越大隊列越長。在第一組M=2的曲線中，只有Pc值取0.001和0.01時，平均隊長在10以內；當Pc取值大于0.05時，六條曲線基本重合，均穩定在110左右，產生擁塞。在第二組M=4的曲線中，無論Pc取值如何，平均隊長均在5以內。

圖8描述了M=2和M=4兩組實驗的中心節點吞吐量變化情況。在第一組M=2的曲線中，Pc取值大于等于0.05的七組曲線基本重合，說明Pc=0.05時中心節點的交換能力就已經達到飽和，飽和值為18 125 000。在第二組M=4的曲線中，Pc取值為0.05時，還沒有達到飽和吞吐量；當Pc取值大于等于0.5時才逐漸達到飽和吞吐量，飽和值為31 335 880。當兩組的Pc取值相同時，第二組的吞吐量遠遠大于第一組，Pc取值越大兩組吞吐量的差值越大。

運行M=2和M=4的兩組仿真，選定一個用戶終端，收集它的統計量——數據包延遲，即從源終端產生數據包至收到確認包ACK的時間，按時間求平均后得到圖9。在第一組M=2的曲線中，延遲區間在10~37 μs。Pc取值為0.001、0.01、005的三條曲線相對平滑、趨于平穩，且Pc取值越大平均延遲越大；其他曲線波動較大，且沒有變化規律。在第二組M=4的曲線中，延遲區間在10~22 μs，整體上小于第一組的曲線值。所有曲線均趨于平穩，且Pc取值越大平均延遲越大。從延遲區間來看，基本可以實現實時通信。

從圖7~9可以看出，M的取值由2變為4對Pc為0.001、0.01的曲線影響不大。說明如果是輕負載（Pc<0.01）下的星型LAN，中心節點中有兩條通道就足夠了。

3 結束語

隨著計算機網絡的發展，大型網絡中交換節點的結構和功能越來越復雜，數學模型的建立也會越來越困難。當多星LAN中心節點的交換通道M＞1時，其CCC存取方式的數學建模存在較大困難。在這種情況下，本文采用OPNET仿真工具構建了多星LAN，對CCC存取方式Ⅰ類系統模型進行了仿真建模。通過仿真，與已有的M=1的單星LAN數學模型的結果進行了對比，并得到了多星LAN中三個重要的網絡性能參數，即數據包平均延遲、中心節點平均隊長和吞吐量；推斷出網絡負載與交換通道數之間的聯系。仿真建模研究無須在實際中建立網絡就可以預測和較真實地模擬網絡運行的情況，降低了成本。與數學建模相比，更具有實際意義。

參考文獻：

［1］

LU Zhaoyi，SAITO T.Star type local area network access control[J].Science in China，1990，33(9)：11231131.

[2]逯昭義.競爭—沖突淘汰存取方式Ι類系統模型性能評價[J].電子學報， 1995，23（9）：115117.

[3]LU Zhaoyi，SUN Lijun.Mathematical model for access mode of contentioncollision cancellation in a star LAN[J].Journal of Electronics，2004，21(1): 3747.

[4]LU Zhaoyi，LU Mai，ZHAO Dongfeng，et al.On the Ⅱnd model of contentioncollision elimination access mode in star LAN[J].Applied Mathematical Modelling，2003，27(11):899911.

[5]LU Zhaoyi，LU Mai，CHEN Yongyi，et al.A special random selective services queueing model for access to a star LAN[J].Applied Mathematical Modelling，1997，21(1):1520.

[6]LU Zhaoyi，SUN Lijun，LU Mai，et al.The mathematical modelling for the access mode of the Ⅳth system model to a multiple star LAN[J].Applied Mathematical Modelling，2006，30(4):367385.

[7]LU Zhaoyi，ZHANG Jianshu，LU Mai.The mathematical modelling for the access mode of the Ⅴth system model to a multiple star LAN[J].Applied Mathematical Modelling，1999，23(3):231239.

[8]逯昭義，楊興梅.競爭－沖突淘汰存取方式Ⅵ類系統模型建模研究［J］.電子學報，2007，35（10）：18171822.

[9]孫屹.OPNET通信仿真開發手冊［M］.北京：國防工業出版社，2005.