樊 榮，萬 立，陳思思

(武漢船舶通信研究所，湖北 武漢 430070)

基于HiNOC網(wǎng)絡(luò)動態(tài)帶寬分配新算法的實現(xiàn)

樊 榮，萬 立，陳思思

(武漢船舶通信研究所，湖北 武漢 430070)

提出一種新型的HiNOC動態(tài)帶寬分配算法，利用令牌桶給各個HM分配令牌，在每個MAP周期都重新進(jìn)行一次計算，以分配在本MAP周期內(nèi)HM所需發(fā)送的令牌數(shù)，并按比例進(jìn)行截斷，依次對HM的數(shù)據(jù)進(jìn)行均衡。這樣將最大程度地合理分配每個HM的數(shù)據(jù)發(fā)送時間，既保證每個HM分配帶寬的公平性，又能有效的降低發(fā)送時延。

HiNOC；動態(tài)帶寬分配；令牌桶；截斷均衡。

高性能同軸網(wǎng)絡(luò)(High performance Network Over Coax，HiNOC)，又稱同軸電纜寬帶接入技術(shù)，是專門針對同軸電纜開發(fā)的擁有我國自主知識產(chǎn)權(quán)的通信體制，是一種利用同軸電纜，實現(xiàn)高性能雙向信息傳輸?shù)膶拵Ы尤虢鉀Q方案[1]。HiNOC網(wǎng)絡(luò)由HiNOC網(wǎng)橋(HiNOC Bridge，HB)和HiNOC調(diào)制解調(diào)器(HiNOC Modem，HM)構(gòu)成，是一種星型的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)。國家新聞出版廣電總局于2012年8月正式發(fā)布了HiNOC1.0標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)規(guī)定，HiNOC網(wǎng)絡(luò)單信道帶寬為16 MHz，在整個HiNOC網(wǎng)絡(luò)滿負(fù)荷運(yùn)作的時候，單信道內(nèi)支持32臺HM同時進(jìn)行工作[2]。單信道內(nèi)支持的最大用戶數(shù)為32個，可選64個。由于可支持的HM數(shù)量較多，因此，如何合理有效地進(jìn)行帶寬分配，成為提高網(wǎng)絡(luò)性能的重要內(nèi)容[3]。

1 現(xiàn)階段動態(tài)帶寬分配算法介紹

在現(xiàn)有技術(shù)中，HiNOC網(wǎng)絡(luò)采用基于令牌桶的方式進(jìn)行帶寬分配：某個HM“單位時間內(nèi)能夠發(fā)送/接收的數(shù)據(jù)量”。當(dāng)HB的驅(qū)動程序通過網(wǎng)管配置程序得到各個HM的DBA參數(shù)(CIR&PIR，每秒鐘保證發(fā)送的比特數(shù)和峰值比特數(shù))后，將其換算為“每PD周期各個HM能夠收發(fā)的比特數(shù)”[4]。算法的實現(xiàn)參考令牌桶算法，每個HM有2個令牌桶，分別對應(yīng)保證帶寬和峰值帶寬(即CIR和PIR數(shù)組)，當(dāng)為某個HM分配了上/下行帶寬后，從對應(yīng)的令牌桶中減少對應(yīng)令牌，當(dāng)某個HM的令牌數(shù)減少為0后，在本PD周期中停止為該HM分配帶寬，峰值帶寬令牌的剩余值不帶入下一個PD周期。而現(xiàn)行的DBA算法中，存在著如下不足：

1)由于系統(tǒng)性能的限制，只有在數(shù)據(jù)幀組幀達(dá)到4 600 byte或者時間達(dá)到預(yù)先設(shè)定的超時閾值時，才會將數(shù)據(jù)發(fā)送出來。此時閾值則不太好界定，太短的話會肯定發(fā)不到4 600 byte；太長又會導(dǎo)致延時過長。

2)在遇到PU幀或者PD幀的時候，現(xiàn)存算法會將這些靠近兩個物理層探測幀的時隙全都浪費(fèi)掉，導(dǎo)致帶寬浪費(fèi)較多。

3)無法實現(xiàn)數(shù)據(jù)的均勻分布，以達(dá)到時延較低的目的。

為了解決這些問題，本文提出了一種新的基于令牌桶的截斷均衡算法。

2 新的基于令牌桶的截斷均衡算法

2.1 算法的介紹

根據(jù)HiNOC1.0標(biāo)準(zhǔn)規(guī)定，將兩次下行探測幀(PD幀)之間的時間片稱為PD周期，每個PD周期的長度為64 ms。而在一個PD周期內(nèi)，則會包含多個MAP周期，其基本長度為4 ms，在MAP周期中，包含有下行時間片(用于發(fā)送各個HM的下行幀)，上行時間片(用于發(fā)送上行幀)，以及MAP幀(用于規(guī)劃下一個MAP周期內(nèi)的時隙分配)。

由此規(guī)定，在本設(shè)計采用基于令牌桶的截斷均衡算法實現(xiàn)動態(tài)帶寬分配。采用基于令牌桶的算法統(tǒng)一分配發(fā)送接收時間片，是為了保證每個HM在一個PD周期內(nèi)能夠按照它們相應(yīng)的權(quán)值來進(jìn)行合理而公平的數(shù)據(jù)發(fā)送。截斷均衡則是讓各個HM的數(shù)據(jù)發(fā)送時間片能夠更加均勻地分布在PD周期的時間軸上，從而避免由于HM速度不一，導(dǎo)致HM某些時刻由于某個HM 達(dá)到降低延時的效果[5]。

2.2 算法的實現(xiàn)

為了完整地實現(xiàn)本設(shè)計的算法，需要引入網(wǎng)管配置和HiNOC網(wǎng)絡(luò)節(jié)點(diǎn)接納維護(hù)期間得到參數(shù)。

網(wǎng)管配置參數(shù)：

1)下行幀：上行幀=Di∶Ui，表示HMi上行幀和下行幀所占的時間比；

2)HMi帶寬比=Ci，表示每個HM發(fā)送和接收時間在整個PD周期中所占的權(quán)重；

3)最小收發(fā)顆粒=N，表示最小收發(fā)顆粒為發(fā)送N個最大HIPHY幀所需時間。

根據(jù)節(jié)點(diǎn)接納維護(hù)時得到參數(shù)：

4)當(dāng)前在線HM為Li(根據(jù)節(jié)點(diǎn)接納維護(hù)時得到數(shù)據(jù))，Li=0代表離線，Li=1代表在線；

5)HMi傳輸速率(發(fā)送一幀所需要的時間)=Vi(根據(jù)節(jié)點(diǎn)接納維護(hù)時得到該數(shù)據(jù))；

6)HMi下行隊列是否有數(shù)據(jù)=Qi(從MAC層動態(tài)讀取數(shù)據(jù))，Qi=0代表無，Qi=1代表有。

用某個HM“一個PD周期內(nèi)能夠發(fā)送/接收的時間”，即HM的發(fā)送接收時間為帶寬的衡量標(biāo)準(zhǔn)，單位為ms。每PD周期(64 ms)統(tǒng)計一次。當(dāng)HB的驅(qū)動程序通過遠(yuǎn)端配置程序得到各個HM的帶寬比Ci，和當(dāng)前在線HM(Li)，計算當(dāng)前實際HM帶寬比Ai，如果HMi處于離線狀態(tài)，則相應(yīng)的Ai=0。

Ai=Ci÷(∑(Ci×Li))

(1)

通過Ai與PD周期(64 ms，Tpd)相乘得到每個HM在一個PD周期中的使用時間

Si=Ai×Tpd

(2)

而每一個使用時間包括發(fā)送時間和接收時間之和，通過配置參數(shù)D∶U來約束

Di=Si×D÷(D+U)

(3)

Ui=Si×U÷(D+U)

(4)

D=∑(Di×Li),U=∑(Ui×Li)

(5)

在此處引入截斷均衡DBA算法，所謂截斷均衡，指的是在每次生成MAP幀的時候，會重新輪詢所有在線的HM，計算一次Di和Ui，計算出Ri值并遴選出擁有最小Ri值Rmin

Ri=Di÷(Vi×Ni)

(6)

Rmin=min(R1,R2,R3，…，RN)

(7)

完成遴選后，以此Rmin為分母，將其余HM的Ri作為分子，依次進(jìn)行整除并歸一化，得到一組值小于閾值THRE的整數(shù)NR序列

NTi=Ri÷Rmin

(8)

NRi=min(「NT?i,THRE)

(9)

此時將得出的整數(shù)NR記錄進(jìn)一個二維數(shù)組N_TRUE[MAX_HM_NUM][NR]。

在生成MAP幀的時候，首先隨機(jī)從MAX_HM_NUM中選取一個HMi，由其開始進(jìn)行規(guī)劃。若他的N_TRUE[i][NR]>0，則會規(guī)劃該HMi發(fā)送一個長度為VN[i]時間片，并從HMi的令牌桶中減少相應(yīng)的值，詳見圖1。

圖1 令牌桶使用流程

之后將NR-1，存入N_TRUE[i][NR]中。接著規(guī)劃HM(i+1)直到輪詢一次所有的HM。當(dāng)輪詢結(jié)束，再次回到HMi，若此時MAP周期的下行時隙沒有填滿，則繼續(xù)重復(fù)之前的操作，直至填滿MAP周期下行時隙。若某個HM的NR已為0，則無論它令牌桶是否還有余值，或MAP周期還沒填滿，其都不會在剩余的MAP周期內(nèi)有發(fā)送機(jī)會，直至下個MAP周期開始。到了再下個周期，又會重新計算一次Ri和NR的值，在新的MAP周期內(nèi)，再進(jìn)行新的時間分配，直至所有HM的令牌桶用完或者PD周期結(jié)束[6]。

3 仿真結(jié)果及分析

本文所述算法，已經(jīng)成功應(yīng)用于HiNOC芯片設(shè)計中，取得了理想的效果。本設(shè)計是在完成了算法的構(gòu)造后，編寫適用的代碼，并在Visual Studio 2008+TeeChart上進(jìn)行仿真分析。參考的預(yù)設(shè)數(shù)據(jù)如圖2所示。

圖2 輸入的參數(shù)一覽(截圖)

由圖3可見，只有兩個HM在線的時候，HM0和HM1的令牌數(shù)為各自一半，HM0為上部分?jǐn)?shù)據(jù)，HM1為下部分?jǐn)?shù)據(jù)。

圖3 總體的HM令牌桶數(shù)

而通過了DBA算法的分配之后，數(shù)據(jù)在MAP時間軸上的分布如圖4，在剛開始的時候，HM1為HM0的兩倍量發(fā)送數(shù)據(jù)；一段時間后，為同量發(fā)送；最后，則轉(zhuǎn)換成HM0為HM1兩倍來發(fā)送數(shù)據(jù)。以此可看到DBA在數(shù)據(jù)的分布上正在進(jìn)行適應(yīng)性調(diào)整。剛開始時，HM1由于速率比HM0快，因此HM1量為HM0的兩倍；而一段時間后，由于HM1令牌發(fā)送得過多，導(dǎo)致HM0需要跟HM1發(fā)送同樣數(shù)據(jù)量的令牌才能達(dá)到統(tǒng)一；而到了最后，則是HM0必須要比HM1發(fā)送更多，才能達(dá)到令牌的數(shù)量統(tǒng)一，以便達(dá)到每個MAP周期都能有數(shù)據(jù)發(fā)送。算法得以驗證，并行之有效。

圖4 在時間軸上的動態(tài)分布(截圖)

圖5則反映了未按照截斷均衡算法分配的時間片排列，明顯可以看到，到了整個時間片的末尾階段，早就沒有了HM1的數(shù)據(jù)，這樣就會導(dǎo)致HM1的延時加大，而HM0的時間片累計在一起進(jìn)行發(fā)送。導(dǎo)致時間片的分布不合理，系統(tǒng)延時變大。

圖5 未按照截斷均衡算法分配的時間片排列(截圖)

4 結(jié)束語

動態(tài)帶寬分配算法是HiNOC系統(tǒng)的關(guān)鍵技術(shù)之一，算法的好壞很大程度上決定了整個系統(tǒng)的性能。本算法在運(yùn)用到實際的HiNOC設(shè)備上后，在確實在保證公平性的前提下有效地降低時延的效果。但是該DBA算法依然還有可提升的空間，如何實現(xiàn)一種效率更高的動態(tài)帶寬分配算法，將依然成為一個熱門的研究話題。

[1]GY/T 265—2012，NGB寬帶接入系統(tǒng) HiNOC傳輸和接入控制技術(shù)規(guī)范[S].2012.

[2]崔競飛.自主創(chuàng)新的同軸電纜雙向接入技術(shù)HiNOC[J].世界寬帶網(wǎng)絡(luò)，2010(6)：60-64.

[3]歐陽鋒，崔競飛.HiNOC技術(shù)概述和進(jìn)展[J].電視技術(shù)，2011，35(12)：11-13.

[4]王煒濤，汪亮，張奭，等.基于嵌入式平臺的HiNOC MAC協(xié)議設(shè)計與實現(xiàn)[J].網(wǎng)絡(luò)新媒體技術(shù)，2013(3)：27-32.

[5]萬倩，歐陽鋒，李博，等.有線電視接入網(wǎng)EPON+HiNOC技術(shù)探析[J].電視技術(shù)，2012，36(18)：70-74.

[6]彭武熹，施韻，萬立.HiNOC網(wǎng)絡(luò)中的動態(tài)帶寬調(diào)度算法[J].電腦知識與技術(shù)，2013(3)：1008-1009.

責(zé)任編輯：許 盈

New Kind of Dynamic Bandwidth Allocation Algorithm Based on HiNOC Network

FAN Rong, WAN Li, CHEN Sisi

(WuhanMaritimeCommunicationsResearchInstitute,Wuhan430070,China)

In this paper, a new dynamic bandwidth allocation algorithm for HiNOC is proposesed. The token in each single MAP cycle for each HM is re-evaluated, pro rate in order to truncate the data in each HM. This will maximal the rational allocation of data transmission time of each HM, namely to ensure that each HM′s bandwidth fairness allocation and effectively reduce the transmission delay.

HiNOC; DBA; token bucket; truncate with pro rate

國家“863”計劃項目(2008BAH28B05)

TN919.3

B

10.16280/j.videoe.2015.01.024

2014-05-02

【本文獻(xiàn)信息】樊榮，萬立，陳思思.基于HiNOC網(wǎng)絡(luò)動態(tài)帶寬分配新算法的實現(xiàn)[J].電視技術(shù),2015，39(1).