一种天地一体化智能网络的混合队列调度方法

本发明涉及天地一体智能网络队列调度机制，特别是一种天地一体化智能网络的混合队列调度方法(MQSD，mixed queue scheduling based on demand service)。

天地一体智能网络中，节点的业务经过计算由粗粒度变成细粒度，导致流量具有变速、突发特性，排队时延及丢帧率增大；节点的存储能力使得用户可以直接从缓存节点获取请求信息，加快流量分发速度的同时，导致流量具有异质、混合特性，对排队时延、传输带宽等服务的需求也有所不同。因此，亟需在天地一体化智能网络中，结合流量突发及异质特性，构建合适的异构链路汇聚控制方法进行流量调度，以满足不同业务传输的服务质量(QoS，quality ofservices)要求，减小业务排队时延及丢帧率。

目前，有关队列调度算法设计时分别从突发性与服务质量业务分类两方面来考虑。在加权公平队列算法(WFQ，weighted fair queuing)的基础上，在每个队列中加入令牌桶控制，从而缓解突发业务流对时延和带宽的影响。将业务流分类安全关键性业务流与非安全关键性业务流，分别将先到先服务算法(FCFS，First Come First Service)、差额轮询算法(DRR，Deficit Round Robin)与静态优先级算法(SP，Strict Priority)并联，以保证其实时性与公平性。不同的业务流有不同的服务质量需求，业务流的突发性导致排队时延及丢帧率增大，现有的调度算法并不能解决上述问题。

为解决现有技术存在的上述问题，本发明要设计一种能满足服务质量需要和降低突发性造成的排队时延及丢帧率的天地一体化智能网络的混合队列调度方法。

为了实现上述目的，本发明的技术方案如下：一种天地一体化智能网络的混合队列调度方法，包括以下步骤：

A、定义智能网络中节点与业务流之间的基本模型

在天地一体化的智能网络中，卫星具有计算和存储能力，具有承载有效载荷和实现业务有效传输的能力。本发明设计智能网络队列调度算法时，既考虑来自其他节点的业务流，也考虑汇聚节点本身存储的业务流，并定义如下：

本发明定义1：用G(N,F)表示智能网络中节点与业务流之间的基本模型。其中，N＝{Si,Dj,I}代表智能网络中的卫星节点，Si为源节点，Dj为目的节点，I为汇聚节点。为t时刻智能网络各节点中的流量。其中i∈[0,m]，j∈[0,m]，m表示节点数量，表示t时刻智能网络源节点中的流量，表示t时刻智能网络目的节点中的流量，表示t时刻智能网络汇聚节点中的流量。

假设队列调度发生在t时刻，则t-1时刻各节点业务流未传输。因此，在t-1时刻，各节点中流量分别为t时刻，汇聚节点I中流量

在汇聚节点I中，分类器将所有流量按照服务质量要求分成4种：Fu为紧急类业务流，其数据帧短小，重要性与实时性极强，调度时优先级最高；Fd为时延敏感类业务流，数据帧较为短小，对时延要求次于紧急类业务流；Fb为带宽敏感类业务流；Fo为其他类业务流，对时延、带宽要求均不高。本发明中不同业务流的流量关系如公式(1)所示。业务流经分类器分类后，调度器对其进行调度。

B、设计一级调度算法及三级调度算法

本发明定义2：设b∈N+，如果业务流的帧在输入缓存区，为了避免队头阻塞现象，帧被虚拟成b个彼此无关联无影响的不同队列，则称这些队列为虚拟输出队列即VOQ(Virtual Output Queues)。

本发明定义3：假设c∈N+,i∈N+，队列i中数据帧经过不止一次调度，第c次调度的算法被称为c级调度算法。

一级调度算法中，在输入缓存区，时延敏感类业务流的帧被虚拟成一个VOQ，带宽敏感类业务流及其他类业务流的帧分别被虚拟成三个VOQ；然后，分别经由先到先服务调度算法、加权轮询调度算法、差额轮询调度算法调度；最后调度得到的帧分别进入队列1、2、3，准备二级调度。

二级调度算法即为动态调整队列调度算法，简称DASP(dynamic adjustmentbased on SP)。

三级调度算法中，紧急类业务流采用先到先服务调度算法后，与二级调度所得帧一起经由静态优先级调度器调度转发。由于紧急类业务流出现频率较低、执行时间较短，且该类业务流对时延要求极高，若未及时响应，会造成较为严重的后果。因此，在多业务混合队列调度算法中，紧急类业务流在所有业务流中具有最高优先级，即当前节点中若存在紧急类业务流，该类业务流将优先转发。

C、设计二级队列调度算法

C1、定义智能网络中等待调度业务流基本模型

针对天地一体化智能网络流量的突发特性，考虑SP算法即静态优先级算法的优势，采用构造判断矩阵法选取业务流的优先级、突发度及允许发送最大帧长度的权值，并进行一致性检验以确定权值被接受；同时，建立调度量模型，动态调整服务量，对业务流获得服务量进行确定。

本发明定义4：用M＝M(O(F),A(F))表示智能网络中等待调度业务流基本模型。其中，O(F)为业务流的调度顺序模型，由各业务流的权值所决定；A(F)为业务流的调度量模型，由提供服务量所决定。

C2、动态调整服务量

队列i中的帧在调度时，除了考虑调度顺序，还考虑调度量，即每次调度多少。

本发明定义5：设0

下面通过比较提供服务量QT与需求服务量的大小，决定当前业务流获得服务量Qi。当QT消耗完后，当前业务流剩余部分将进行降级处理，即进入优先级最低的队列等待下一轮调度。QT将进行动态调整，其量化指标为时间片T，量化指标为执行时间ti，即QT:QT～aT，

设有数集X＝{Xa:a＝1,2,3…,x}，对数集X中所有数据按照从小到大的顺序排序后为：

X′＝{X′(a):a＝1,2,3…,x} (2)

中位数是按顺序排列的数集中位于中间位置的数，它不受最大、最小两个极端数值的影响，部分数据的变动对中位数没有影响。

对于数集X，其中位数XM求解公式如下：

对于时间片的选取，采取动态调整的策略。鉴于中位数对数集的描述更具代表性，时间片T的计算方法决定采用计算所有队列执行时间中位数的方法。其计算公式如下：

式中：M为参与调度业务流执行时间中位数；tk为所有业务流执行时间按照升序排列后第k个执行时间，k＝1、2、…、n；

队列在解析执行时间ti的同时，分配默认时间片T0。因此，对于时间片T的计算公式将更新如下：

提供服务量如公式(6)所示：

此时，队列获得服务量如公式(7)所示。

一个数集中最多有一半的数值小于中位数，也最多有一半的数值大于中位数。因此，若时间片T为执行时间中位数M，则至少有一半的业务流执行时间大于时间片；若时间片T为默认时间片T0，也存在业务流执行时间大于时间片的情况，即大于QT。对于大于QT的部分，将采取降级处理，以获取最大服务量。时，降级服务量

C3、动态调整权值

本发明定义6：设pi∈N+，i∈N+，记队列i中业务流的优先级为pi。pi值越大，业务流优先级越高。

本发明定义7：设为当前时刻队列i的长度，为队列i的最大长度，为队列i的平均长度，则业务流突发度：

队列平均长度由指数加权移动平均的低通滤波器计算得出，反映网络拥塞情况，如式(8)所示：

式中：fi为低通滤波系数，取值为0.01。

本发明定义8：设0

调度顺序模型Oi中，由于优先级、突发度及允许发送最大帧长度为业务流的不同属性，对其简单进行加和处理不能综合反映各参数影响效果，故先对其对应参数进行归一化处理，将所有的原始数据映射到[0,1]区间上，使得各指标处于同一数量级。归一化函数为：

其中xi可取值为业务流优先级pi、突发度或允许发送最大帧长度归一化后得到的且无量级。

归一化处理后，计算所有参数的加权值ci：

式中为第i个队列中业务流归一化处理的优先级参数，为第i个队列中业务流归一化处理的突发度参数，为第i个队列中业务流归一化处理的允许发送最大帧长度；ω1为业务流优先级所占权重，ω2为业务流突发度所占权重，ω3为业务流允许发送最大帧长度所占权重。通过对所得加权值ci排序，按照从大到小的顺序依次调度对应业务流。

业务流权重选取策略采用构造判断矩阵法。首先对不同指标进行两两对比，比较时采用重要尺度标准度量，得到相对重要尺度参数组成一个n×n阶方阵，然后通过特征根法计算各指标权重，最后通过检验系数CR对矩阵一致性进行检验。不同元素间的重要尺度定义如下：

重要尺度为1表示前一指标与后一指标重要性相同；

重要尺度为3表示前一指标比后一指标稍微重要；

重要尺度为5表示前一指标比后一指标明显重要；

重要尺度为7表示前一指标比后一指标非常重要；

重要尺度为9表示前一指标比后一指标十分重要。

依据各指标相对重要尺度参数构造矩阵A如公式(11)所示。

其中，aij为第i个指标对第j个指标的相对重要度，且：

aij＞0,aijaji＝1。

则：

(nE-A)ω＝0 (12)

其中E为单位矩阵。依据特征根法知：

λmaxω＝Aω (13)

其中，λmax为矩阵A的最大特征值。其对应特征向量ω＝[ω1,ω2,…,ωn]T即为权向量。

为确保不同指标相对重要尺度的逻辑性，将引入检验系数CR对矩阵A进行一致性检验，即矩阵A确定不一致的允许范围。检验系数CR为一致性指标CI与随机一致性指标RI的比值，即：

式中：

当CI＝0时，有完全的一致性；CI越大，不一致性越严重，判断误差越大。RI值受判断矩阵阶数影响，矩阵阶数越大，则出现一致性随机偏离的可能性越大。矩阵阶数对应RI值如下：

矩阵阶数为1时，对应RI值为0；

矩阵阶数为2时，对应RI值为0；

矩阵阶数为3时，对应RI值为0.58；

矩阵阶数为4时，对应RI值为0.90；

矩阵阶数为5时，对应RI值为1.12；

矩阵阶数为6时，对应RI值为1.24；

矩阵阶数为7时，对应RI值为1.32；

矩阵阶数为8时，对应RI值为1.41；

矩阵阶数为9时，对应RI值为1.45；

矩阵阶数为10时，对应RI值为1.49。

对于检验系数CR，若CR＜0.1，则认为矩阵A通过一致性检验；否则不通过，重新确认相对重要尺度。

与现有技术相比，本发明具有以下有益效果：

1、本发明基于现有不同调度算法的优点，提出了一种混合队列调度机制，区分了业务的不同需求，满足了不同业务的服务质量需求。

2、本发明设计了一种动态调整队列调度算法，在SP算法的基础上，采用构造判断矩阵法计算了业务流权值，建立调度量模型动态调整了服务量，降低了突发性造成的排队时延及丢帧率。综上，本发明的天地一体化智能网络的混合队列调度方法具有良好的应用前景。

图1是本发明的流程图。

图2是智能网络中节点与业务流之间的基本模型示意图。

图3是混合队列调度机制逻辑图。

图4是仿真拓扑结构图。

图5是时延敏感类业务流平均时延曲线。

图6是紧急类业务流平均时延曲线。

图7是带宽敏感类业务流带宽占用曲线。

图8是其他类业务流丢帧率曲线。

下面结合附图对本发明进行进一步地说明。如图1-3所示，一种天地一体化智能网络的混合队列调度方法(MQSD，mixed queue scheduling based on demand service)的具体步骤如下：

Step1：帧到达汇聚节点时，分类器判断当前帧的类型，若为紧急类，转至Step2，若为时延敏感类，转至Step3，若为带宽敏感类，转至Step4，否则，转至Step5；

Step2：帧经由先到先服务调度器调度后缓存在队列5中，优先级为2，转至Step12；

Step3：所有帧虚拟成一个虚拟输出队列VOQ3i，i＝1。先到先服务调度器从VOC31中取帧并进行转发，帧缓存在队列3中，优先级为3，转至Step6；

Step4：所有帧虚拟成三个虚拟输出队列VOQ2i，i＝1,2,3。加权轮询调度器从VOC2i中取帧并进行转发，帧缓存在队列2中，优先级为2，转至Step6；

Step5：所有帧虚拟成三个虚拟输出队列VOQ1i，i＝1,2,3。差额轮询调度器从VOC1i中取帧并进行转发，帧缓存在队列1中，优先级为1，转至Step6；

Step6：准备经动态调整队列调度器调度，建立智能网络中等待调度业务流基本模型，解析各队列中帧的参数：优先级pi、突发度允许发送最大帧长度执行时间ti、默认时间片T0。依据业务流调度时的执行时间计算其中位数M，建立调度量模型；

Step7：比较T0与M大小。若T0小于M，则时间片T等于M，否则，时间片T等于T0。

Step8：比较ti与T的大小。若ti大于T，则转至Step9，否则转至Step10；

Step9：当前队列给当前业务流分配服务量QT，转至Step5。剩余服务量QL分配给降级队列并转至Step6；

Step10：对参数：pi、及分别进行归一化，通过构造判断矩阵，得到权值ci；

Step11：对ci按照从大到小的顺序排序并依次输出帧，缓存在队列4中，优先级为1；

Step12：静态优先级调度器对队列4、5中的帧调度并转发；

Step13：判断各队列中是否有等待调度转发的帧存在，若是则转至Step1，否则调度结束。

实施例：仿真所使用网络拓扑结构如图4所示。A1、A2、A3、A4分别为四个卫星源节点，其传输至B节点业务流分别为紧急类业务流、时延敏感类业务流、带宽敏感类业务流及其他类业务流，发送时间间隔与发送速率见表1。B为汇聚节点，服务速率为60Mbps，具有分类的作用，同时，汇聚节点B也将产生业务流，该业务流不做类型限制，经分类后与源节点产生业务流一起参与调度。C为目的节点。

表1源节点参数设置

A2、A3、A4源节点发送业务流到达汇聚节点B时，各自形成VOQ，分别采用先到先服务调度、加权轮询调度和差额轮询调度后，缓存在队列3、2、1中。队列3、2、1的优先级分别为4、3、2，降级队列优先级为1。对不同类型业务流中的各项参数重要性进行两两比较，依据所得重要尺度及判断矩阵得到各项指标权值。各业务流优先级、突发度以及允许发送最大帧长度的权值设置如表2所示。

表2仿真属性权值设置

根据属性权值设置，并结合公式(8)计算可得：CRd＝0.05，CRb＝0.07，CRo＝0.08。由于三类业务流检验系数均小于0.1，故其权向量估计均在误差范围内。

为体现本发明队列调度机制的优势，将本发明与基于预测的动态包调度机制PSS(Packet Scheduling Scheme，PSS)及混合队列调度机制P-VDWRR进行仿真对比，对比结果将从排队时延、带宽占用、丢帧率三个性能方面来体现。

本发明将以时延敏感类业务流及紧急类业务流为分析样本，分析本发明机制、PSS机制和P-VDWRR机制的排队时延性能。三种调度机制对两种不同业务流的平均时延仿真结果分别如图5-6所示。

对于时延敏感类业务流，本发明调度机制比PSS机制平均降低了5.84％，比P-VDWRR机制平均降低了2.9％。这主要是因为PSS机制通过实时统计每个类中的活动流的数量动态调整队列调度权重，P-VDWRR机制中，令牌桶机制对业务流进行了限制，二者均未考虑业务流的突发性。然而业务流突发时，队列中缓存的帧将会急剧增加，导致队列中帧的时延增大。本发明机制中，动态设置权值及服务量时，综合考虑了其突发性，在其突发前调度该业务流，从而减小了时延；同时，对于时延敏感类业务流，一级调度采用的是先到先服务调度算法，该算法时延性能好。

对于紧急类业务流，本发明调度机制比PSS机制降低了16.73％，比P-VDWRR机制降低了14.59％。这是因为按照PSS机制与P-VDWRR机制对业务流的分类标准，紧急类业务流与时延敏感类业务流属于同一优先级业务，而本发明调度机制中，相较于时延敏感类业务流，紧急类业务流具有更高的优先级，故其时延性能远比PSS机制与P-VDWRR机制好。

带宽是指单位时间内能传输的数据量。本发明将带宽敏感类业务流的发送速率逐步从20MB/s增加到70MB/s，对于不同调度机制，其带宽占用曲线仿真结果如图7所示。由图7可以看出，相较于PSS调度机制及P-VDWRR调度机制，随着业务流发送速率的增加，帧的数量在不断改变，本发明调度机制能更好的利用带宽，其带宽利用比PSS调度机制平均提高了6.99％，比P-VDWRR调度机制平均提高了10.58％。这主要是因为P-VDWRR仅保留了加权轮询调度机制的优势，其带宽性能与加权轮询调度机制类似，PSS机制仅能动态调整队列缓冲区大小。本发明调度机制中，带宽敏感类业务流在经由加权轮询调度后，引入了降级策略，使得需求服务量超过可提供服务量部分帧能够得到再次调度的机会，也就是说增加了其权值，分配到了更多的带宽，得到了更多的服务。本发明调度机制在带宽性能方面优势明显。

丢帧率是指数据传输时，丢失的帧占发送总数的比值。在网络拥塞时，丢帧是必然现象。因此，在缓冲区长度固定时，应尽可能的降低其丢帧率。对于不同调度机制，其丢帧率仿真曲线如图8所示。可以看出，本发明机制丢帧率比PSS机制降低了7.9％，比P-VDWRR机制降低了14.2％。这主要是因为业务流突发会造成队列中缓存的帧变多，当帧的数量大于缓冲区长度时，部分帧会溢出，即丢帧。本发明机制在动态设置调度权值时引入业务流突发度参数，在其突发之前进行调度，因此将会减少数据突发造成丢帧的概率；而PSS机制及P-VDWRR机制并未考虑流量突发度。

本发明不局限于本实施例，任何在本发明披露的技术范围内的等同构思或者改变，均列为本发明的保护范围。