一種基于價格機制的網(wǎng)絡準入控制ＱｏＳ算法

（1. 北京交通大學 機械與電子控制工程學院，北京100044； 2. 中國科學院 沈陽自動化研究所，沈陽 110016）



摘 要：

除了技術(shù)因素以外，價格因素也會對網(wǎng)絡的服務質(zhì)量(QoS)產(chǎn)生較大的影響，根據(jù)排隊論方法和經(jīng)濟學理論，假設(shè)價格的變化量與網(wǎng)絡用戶請求接入的變化量是確定關(guān)系，結(jié)合多優(yōu)先級GPS調(diào)度模型，綜合分析網(wǎng)絡價格對網(wǎng)絡性能以及對網(wǎng)絡服務質(zhì)量產(chǎn)生的影響，提出一種接近實際的網(wǎng)絡QoS 準入控制算法。仿真實驗證明了算法的可行性。算法中價格的確定以適應各類流的丟包率指標和接入阻塞率指標為基礎(chǔ)，得到了可以保證系統(tǒng)QoS性能并且可以提高系統(tǒng)的利用率的價格機制。

關(guān)鍵詞：服務質(zhì)量； 價格機制； 準入控制； 阻塞率

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

文章編號：10013695(2008)12378203



Call admission control QoS algorithm based on price mechanism



YAO Zhenglin1， SUN Shouguang1， GUO Haifeng2

(1．School of Mechanical， Electronic Control Engineering，Beijing Jiaotong University，Beijing 100044，China; 2. Shenyang Institute of Automation， Chinese Academy of Sciences， Shenyang 110016， China)



Abstract:Besides technical factors， price also could make important effect of network quality of service (QoS). According to queue methods and economics theory， considering the certain relation between the price variables and the variables of the network users’ requests in call admission， for a multipriority GPS scheduler model， this paper analysed the impact of the network price on the network performances and the network QoS comprehensively and presented the network QoS call admission control algorithm closed to the real world. To prove it， gave a number example. Confirming of price in the algorithm considers the packet loss rate and the block rate in call admission of variety flow. It can ensure the system QoS performances and improve the utility of the system.

Key words：QoS; price mechanism; call admission control; block rate



0 引言

服務質(zhì)量（QoS）是網(wǎng)絡研究中重要的課題之一。在影響網(wǎng)絡QoS的諸多因素中，從經(jīng)濟學角度考慮實際的數(shù)據(jù)流價格機制對網(wǎng)絡QoS管理影響的文獻并不多。文獻[1~9]提出的定價策略均假設(shè)網(wǎng)絡用戶接入量與網(wǎng)絡使用價格的關(guān)系是確定的。

本文考慮網(wǎng)絡用戶接入的隨機性的前提下，假設(shè)網(wǎng)絡價格的變化量與網(wǎng)絡用戶請求接入的隨機量參數(shù)變化量是確定關(guān)系，結(jié)合多優(yōu)先級GPS調(diào)度模型，綜合分析網(wǎng)絡價格對網(wǎng)絡性能以及對網(wǎng)絡服務質(zhì)量產(chǎn)生的影響，提出一種接近實際的網(wǎng)絡QoS管理定價策略。

1 價格變化對用戶接入量的影響

考慮有n類接入數(shù)據(jù)流的系統(tǒng)，其中第i（i=1，2，…，n）類數(shù)據(jù)流的接入服從參數(shù)為λci的Poisson分布；每個流的系統(tǒng)服務時間服從均值為1/μci的負指數(shù)分布；各類數(shù)據(jù)流的價格分別為Pi，隨著價格的調(diào)節(jié)，會影響到各類數(shù)據(jù)流的輸入?yún)?shù)。實際系統(tǒng)中，價格變化與用戶接入數(shù)量的變化是一個隨機變量，其關(guān)系如下：

其中：Δλci表示第i類流的輸入?yún)?shù)的變化量;ΔPi為相應的第i類流的價格變化量。ki≥0，為第i類流自相關(guān)系數(shù)，rij≥0(i≠j)為第i類流與第j類流的相關(guān)系數(shù)。也就是說，如果一類數(shù)據(jù)流的價格升高，會使自身的接入?yún)?shù)減少，而使其他流的接入?yún)?shù)有一定程度的增加；反之亦然，一類數(shù)據(jù)流的價格降低，會使自身的接入?yún)?shù)增加，而使其他流的接入?yún)?shù)有一定程度的減少，變化程度與流之間的相關(guān)系數(shù)有關(guān)。

2 用戶接入量參數(shù)變化對數(shù)據(jù)流輸入的影響

對于擁有QoS控制機制系統(tǒng)，數(shù)據(jù)流的接入會由系統(tǒng)的準入控制機制進行調(diào)節(jié)。這樣系統(tǒng)會根據(jù)自身當前的狀態(tài)來判斷不同優(yōu)先級的數(shù)據(jù)流的接入數(shù)量。為了符合實際，假設(shè)每個數(shù)據(jù)流均是Poisson流，根據(jù)系統(tǒng)對各個流優(yōu)先權(quán)的分配，以及各個流QoS指標的不同，系統(tǒng)中最多可以接入ni條第i類流，系統(tǒng)的總帶寬為C，第i類流用戶的阻塞率為εi。

由上述分析可知，一種類型的網(wǎng)絡用戶的接入過程符合多通道損失制M/M/m/0模型，第i類流的接入強度為

ρci=λci/μci（2）



設(shè)系統(tǒng)允許的第i類流的最大接入數(shù)為mi。根據(jù)M/M/m/0模型在穩(wěn)態(tài)情況下的排隊分析可知，系統(tǒng)的穩(wěn)態(tài)狀態(tài)概率為

其中：s為損失率。

3 數(shù)據(jù)流輸入對系統(tǒng)性能的影響

為簡化分析，假設(shè)相同類型的流形成的數(shù)據(jù)包的輸入均是獨立同分布的。數(shù)據(jù)包的輸入服從參數(shù)為λfi的Poisson分布。系統(tǒng)中有n個隊列，每個類型的數(shù)據(jù)流輸入到相應的隊列中。在GPS系統(tǒng)中，系統(tǒng)根據(jù)優(yōu)先級的不同為不同隊列分配不同的帶寬，使對第i類流中數(shù)據(jù)包的服務時間長度分別服從均值為1/μfi的負指數(shù)分布。根據(jù)數(shù)據(jù)包的延遲指標，第i個隊列長度為Li，第i類流的丟包率，即第i個隊列的丟包率指標為ηi。

由上述分析可知，每個隊列中的數(shù)據(jù)包的輸入和服務過程均符合單通道混合制M/M/1/

定價策略直接影響運營商的收益、網(wǎng)絡的最優(yōu)利用率、網(wǎng)絡對用戶的最優(yōu)服務質(zhì)量、運營成本和用戶收益等，需要考慮多方面的因素。為了簡化分析，這里考慮的定價目標是在忽略運營商運營成本的情況下，滿足最優(yōu)用戶QoS，使網(wǎng)絡的利用率達到最優(yōu)。

考慮網(wǎng)絡QoS指標為隊列丟包率ηi。為了確定數(shù)據(jù)流價格與網(wǎng)絡性能之間的關(guān)系，先計算每個隊列適合的輸入強度，根據(jù)PiLi=ηi得

式（13）可以解得滿足約束條件的max(Ni)解ξi。這個解是在隊列數(shù)據(jù)流接入數(shù)量固定不變的情況下得到的，滿足系統(tǒng)QoS要求的最大接入數(shù)量。而由于接入流數(shù)量是隨機過程，則此時可以取系統(tǒng)第i類流的接入量均值Ei[X]為ξ，則根

又根據(jù)式（4）（5）可以解得第i類流的最大允許接入數(shù)量mi。

考慮價格因素，可以求解需要調(diào)整后的各類數(shù)據(jù)流價格Pi。設(shè)價格調(diào)整前各類流的輸入?yún)?shù)為λciq，價格為Piq，則

將式（18）代入（1），可以求出ΔPi，再根據(jù)式（19）可得調(diào)整后的價格Pi。

4. 2 價格變化對QoS指標的影響

如果在價格變化前滿足丟包率指標的第i類流的最大允許接入量為miq這里提出的這個定價策略以適應各類流的丟包率指標和接入阻塞率指標為基礎(chǔ)，得到了可以保證系統(tǒng)QoS性能并且可以提高系統(tǒng)的利用率的價格結(jié)構(gòu)。

5 仿真實驗

考慮有兩類數(shù)據(jù)流的系統(tǒng)，各類流的參數(shù)如表1所示。

表1 價格調(diào)整前各類流的參數(shù)

流參數(shù)Piλciμciλfiμfiεiηi自相關(guān)ki互相關(guān)kij隊列長

第一類流100.51/63500.020.00530.05100

第二類流150.61/55400.030.00150.05100

第一類數(shù)據(jù)流以參數(shù)為0.5的Poisson分布請求接入，接入時間服從均值為6的負指數(shù)分布；第二類流的接入速度為0.6，接入時間服從均值為5的負指數(shù)分布。第一類流的數(shù)據(jù)包輸入服從參數(shù)為3的Poisson分布；而第二類流的參數(shù)為5。接入阻塞率指標分別為0.02和0.03。丟包率指標分別為0.005和0.001。兩類流的互相關(guān)系數(shù)為0.05，自相關(guān)系數(shù)分別為3和5，調(diào)整前的價格是10和15。

經(jīng)過計算，系統(tǒng)最大允許接入的兩類流平均數(shù)量分別為16和7，而目前這兩類流的平均接入數(shù)量均只是3，這就使系統(tǒng)資源沒有得到充分利用。根據(jù)上文提出的算法，對這兩類流的價格進行調(diào)整，調(diào)整后第一類流的價格為9.27，第二類流的價格為14.82。這個價格使系統(tǒng)平均收益由原來的10×3+15×3=75增加到9.27×16+14.82×7=252.06，得到了顯著提高。

系統(tǒng)隊列仿真如圖1所示。

根據(jù)計算得出在調(diào)整價格后，系統(tǒng)在隨機接入的情況下，第一類流的最大接入數(shù)量為23，第二類流為12，這樣才能保證平均接入數(shù)量分別為16和7。在價格調(diào)整前，由于系統(tǒng)處理能力遠大于接入數(shù)量，系統(tǒng)中兩類流的隊列均為0。圖1（a）表示了價格調(diào)整后的第一類流在系統(tǒng)中的隊列長度；（b）表示了價格調(diào)整后的第二類流在系統(tǒng)中的隊列長度?？梢钥吹?，在滿足丟包率指標的情況下，系統(tǒng)資源得到了更大的利用。

6 結(jié)束語 

本文研究了價格機制對網(wǎng)絡QoS準入控制的影響，根據(jù)排隊論的思想，以及經(jīng)濟學理論，提出了相應的基于價格機制的準入控制QoS算法。通過仿真證明了算法的可行性和有效性。這里只考慮了兩個QoS指標，其他指標如數(shù)據(jù)延遲、抖動等并沒有全部考慮，但這并不影響本文的結(jié)論。在實際應用中，需要確定價格變動與接入數(shù)量參數(shù)變動的關(guān)系。而價格的變動一般比較緩慢，而接入流數(shù)量參數(shù)卻變化較快，因此還需要建立一個良好的價格應變系統(tǒng)，對網(wǎng)絡性能和服務質(zhì)量方面進行全面的考慮。

參考文獻：

[1]FERGUSON D F， NIKOLAOU C， YEMINI Y. An economy for flow control in computer networks[C]//Proc of Conference on Computer Communications (IEEE Infocom). Ottawa:[s.n.]， 1989:100118.

[2]MACKIEMASON J K， VARIAN H R. Pricing congestible network resources[J]. IEEE Journal of Selected Areas in Communications， 1995，13(7) :1141149.

[3]SHENKER S， CLARK D， ESTRIN D， et al. Pricing in computer networks: reshaping the research agenda[J]. ACM Computer Communication Review， 1996，26 (2):1943.

[4]WANG X， SCHULZRINNE H. Performance study of congestion price based adaptive service[C]//Proc of International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV).[S.l.]: Chapel Hill， 2000:110.

[5]FALKNER M， DEVETSIKIOTIS M， LAMBADARIS I. An overview of pricing concepts for broadband IP networks[J]. IEEE Communications Surveys， 2000，3 (2):213.

[6]LEPLER J H， NEUHOFF K. Resource pricing under a marketbased reservation protocol[C]//Proc of QofIS/ICQT. 2002:303314.

[7]LI T， IRAQI Y， BOUTABA R. Pricing and admission control for QoSenabled Internet[J]. Computer Networks: Special Issue on Internet Economics，2004，6(1):87110.

[8]SHELFORD S， MANNING E G， SHOJA G C. A framework for quality of service control through pricing mechanisms[C]//Proc of IEEE/IFIP NOMS 2006. Vancouver:[s.n.]， 2006:37.

[9]SHELFORD S， SHOJA G S， MANNING E G. Optimal routing of dynamically priced network services[C]//Proc of IEEE Globecom. San Francisco:[s.n.]， 2006:15.

[10] YAO Zhenglin， ZHENG Xiangqi， LIU Jingang. Research on endtoend QoS management in UMTS network[C]//Proc of the 5th International Symposium on Test and Measuerment(ISTM). 2003: 17251728.

[11]YAO Zhenglin， ZHENG Xiangqi， LIU Jingang. Research on call admission control mechanism in UMTS core network[C]//Proc of the 5th International Symposium on Test and Measuerment(ISTM). 2003:33673371.

[12]盛友招. 排隊論及其在計算機通信中的應用[M]. 北京：北京郵電大學出版社， 1998.