基于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).