基于带宽借用的动态队列调度装置及方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106533982A(43)申请公布日2017.03.22(21)申请号201611018477.8(22)申请日2016.11.14(71)申请人西安电子科技大学地址710071陕西省西安市雁塔区太白南路2号(72)发明人潘伟涛郑凌邱智亮梅益波高峥赵海峰刁卓王伟娜高丽丽张汶汶(74)专利代理机构陕西电子工业专利中心61205代理人王品华朱红星(51)Int.Cl.H04L12/873(2013.01)权利要求书2页说明书6页附图3页(54)发明名称基于带宽借用的动态队列调度装置及方法(57)摘要本发明公开一种基于带宽借用的动态队列调度装置及方法，主要解决现有技术中输出端口带宽利用率低的问题。其实现方案为：通过CPU接口模块(1)读取CPU可配置的寄存器，得出为每个队列所分配的带宽配额；通过带宽配额存储模块(2)存储为每个先入先出队列分配的带宽配额；通过先入先出缓存队列模块(3)缓存每条业务流到达的数据包；通过调度器模块(4)以加权轮询的方式根据每个队列分配的带宽配额对队列进行调度；通过带宽借用模块(5)将一个调度周期内未用完的空闲带宽配额分配给本次调度周期内仍有数据包未输出的非空队列。本发明降低了系统的丢包率，提高了带宽资源的利用率，可用于通信网络中的路由器和交换机中。CN106533982ACN106533982A权利要求书1/2页1.一种基于带宽借用的动态列调度的装置，包括：CPU接口模块(1)，用于在每一个调度周期开始时，通过读取CPU可配置的寄存器，得出为每个队列所分配的带宽配额；带宽配额存储模块(2)，用于存储为每个先入先出队列分配的带宽配额；先入先出缓存队列模块缓存每条业务流到达的数据包；调度器模块每个队列的带宽配额，以加权轮询的方式。带宽借用模块(5)，用于存储每个调度周期内未用完的带宽配额，并且根据每个队列以往向其他队列借出带宽的情况，将空闲带宽资源池子模块中存储的空闲带宽配额分配给本次调度周期内仍有数据包未输出的非空队列。2.根据权利要求1所述的装置，其中带宽借用模块(5)包括：空闲带宽资源池子模块(51)，用于存储在一个调度周期内没有用完的带宽配额，并在调度周期开始时清空；历史数据统计子模块(52)，用于统计一个历史时间段内，每个队列向其他队列借出的带宽配额量；空闲带宽分配子模块(53)，用于在一个调度周期中，将空闲带宽资源池子模块中存储的空闲带宽配额分配给本次调度周期内仍有数据包未输出的非空队列。3.一种基于带宽借用的动态列调度的方法，包括以下步骤：1)为每个队列分配带宽配额：1a)设系统提供的优先级有M种，每个优先级下有N个队列，共有M×N个队列；1b)将M种优先级按照从高到低的顺序进行编号，编号为1,2,…,i,…,M，将编号为i的队列分为一组，i＝1,2,…,M；令该队列组的编号为Qi，队列组Qi中第j个的队列的编号为Qi,j，j＝1,2,…,N；设队列Qi,j的权重为wi,j，设当前时刻队列Qi,j的长度为Li,j，调度周期的时长为T，调度器总带宽为B；1c)CPU根据队列的权重wi,j，为每个队列Qi,j分配带宽配额Bi,j，令将带宽配额Bi,j存储至CPU可配置的寄存器中；1d)从CPU可配置的寄存器中读取每个队列所分配的带宽配额Bi,j，并将每个队列的带宽配额存储到RAM中；为每个队列Qi,j维护一个计数器DCi,j，初始化为DCi,j＝Bi,jT；2)按照优先级从高到低对各个队列进行轮询，将队列中的数据包调度输出；2a)令i＝1，j＝1；2b)轮询队列Qi,j，根据队列头部数据包的长度以及该队列剩余的带宽配额，判断是否能够将队列头部的数据包输出：若队列Qi,j为空，则跳过该队列的轮询，并将该队列所剩余的带宽配额DCi,j累加到空闲带宽资源池中，令R表示空闲带宽资源池中的空闲带宽，得到更新后的空闲带宽为R+DCi,j，然后更新队列Qi,j的历史带宽借出数据，令Ci,j表示队列Qi,j在一个历史时间段内已借出的带宽，得到更新后的已借出带宽为Ci,j+DCi,j，执行步骤2c)；若队列Qi,j为非空，设队列Qi,j头部数据包的长度为Pi,j，如果DCi,j<Pi,j，则将该队列所剩余的带宽配额DCi,j累加到空闲带宽资源池中，并更新历史带宽借出数据，得到更新后的2CN106533982A权利要求书2/2页已借出带宽为Ci,j+DCi,j，执行步骤2c)；如果DCi,j≥Pi,j，则令DCi,j-Pi,j，将队列头部数据包调度输出；继续轮询队列Qi,j，直到队列Qi,j为空，或者将带宽配额DCi,j用完，执行步骤2c)；2c)令当前的队列编号j加1，得到下一个队列的编号，判断下一个队列编号是否大于N，若大于N，则表明当