基于HiNOC網絡動態帶寬分配新算法的實現

樊 榮，萬 立，陳思思

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

基于HiNOC網絡動態帶寬分配新算法的實現

樊 榮，萬 立，陳思思

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

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

HiNOC；動態帶寬分配；令牌桶；截斷均衡。

高性能同軸網絡(High performance Network Over Coax，HiNOC)，又稱同軸電纜寬帶接入技術，是專門針對同軸電纜開發的擁有我國自主知識產權的通信體制，是一種利用同軸電纜，實現高性能雙向信息傳輸的寬帶接入解決方案[1]。HiNOC網絡由HiNOC網橋(HiNOC Bridge，HB)和HiNOC調制解調器(HiNOC Modem，HM)構成，是一種星型的拓撲網絡結構。國家新聞出版廣電總局于2012年8月正式發布了HiNOC1.0標準，該標準規定，HiNOC網絡單信道帶寬為16 MHz，在整個HiNOC網絡滿負荷運作的時候，單信道內支持32臺HM同時進行工作[2]。單信道內支持的最大用戶數為32個，可選64個。由于可支持的HM數量較多，因此，如何合理有效地進行帶寬分配，成為提高網絡性能的重要內容[3]。

1 現階段動態帶寬分配算法介紹

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

1)由于系統性能的限制，只有在數據幀組幀達到4 600 byte或者時間達到預先設定的超時閾值時，才會將數據發送出來。此時閾值則不太好界定，太短的話會肯定發不到4 600 byte；太長又會導致延時過長。

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

3)無法實現數據的均勻分布，以達到時延較低的目的。

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

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

2.1 算法的介紹

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

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

2.2 算法的實現

為了完整地實現本設計的算法，需要引入網管配置和HiNOC網絡節點接納維護期間得到參數。

網管配置參數：

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

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

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

根據節點接納維護時得到參數：

4)當前在線HM為Li(根據節點接納維護時得到數據)，Li=0代表離線，Li=1代表在線；

5)HMi傳輸速率(發送一幀所需要的時間)=Vi(根據節點接納維護時得到該數據)；

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

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

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

(1)

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

Si=Ai×Tpd

(2)

而每一個使用時間包括發送時間和接收時間之和，通過配置參數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作為分子，依次進行整除并歸一化，得到一組值小于閾值THRE的整數NR序列

NTi=Ri÷Rmin

(8)

NRi=min(「NT?i,THRE)

(9)

此時將得出的整數NR記錄進一個二維數組N_TRUE[MAX_HM_NUM][NR]。

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

圖1 令牌桶使用流程

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

3 仿真結果及分析

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

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

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

圖3 總體的HM令牌桶數

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

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

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

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

4 結束語

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

[1]GY/T 265—2012，NGB寬帶接入系統 HiNOC傳輸和接入控制技術規范[S].2012.

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

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

[4]王煒濤，汪亮，張奭，等.基于嵌入式平臺的HiNOC MAC協議設計與實現[J].網絡新媒體技術，2013(3)：27-32.

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

[6]彭武熹，施韻，萬立.HiNOC網絡中的動態帶寬調度算法[J].電腦知識與技術，2013(3)：1008-1009.

責任編輯：許 盈

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

【本文獻信息】樊榮，萬立，陳思思.基于HiNOC網絡動態帶寬分配新算法的實現[J].電視技術,2015，39(1).