一种网络数据流的多维队列调度与管理方法

摘要

本发明提供一种网络数据流的多维队列调度与管理系统，用于对具有多属性且每个属性具有多个取值的网络数据流进行调度和管理。该系统设置有与网络数据包的属性个数相等的N个队列组，且每个队列组i设置有与属性i取值个数相等的M_i个队列，到达该系统的网络数据包按属性和属性值分类在具体的队列里排队进行调度和管理，以提供不同的服务。本发明最大只需要NM个队列就可以实现细粒度的分类排队控制，与现有的队列调度技术(最大需要(M+1)^N-1个队列)相比，简化了系统实现的复杂性。可实现多种应用系统，例如QoS保证、有区分的服务、带宽共享、分类速率控制和过滤、网络入侵防御、异常流过滤等，适用面广。

主权项

1、一种网络数据流的多维队列调度与管理方法，用于对具有多属性且每个属性具有多个取值的网络数据流进行调度和管理，其特征在于设置与网络数据包的属性个数相等的N个队列组，且每个队列组i设置与属性i取值个数相等的M_i个队列，然后将到达的网络数据包按属性和属性值进行如下操作：包括多维队列管理算法，所述多维队列管理算法设置一个队列管理主模块，且为每个队列设置一个管理子模块；所述多维队列管理算法具体如下：设数据包i有C_i个属性，且按照其属性和属性值选择的队列分别为$q_{i_1},q_{i_2},···,q_{i_{C_i}};$每个队列所对应的管理子模块都按照设定的队列管理算法进行队列管理，从而得出每个队列丢弃一个新到达数据包的概率数据包i被正要加入的所有队列都丢弃的平均概率p为在计算了平均丢弃概率p以后，按照(0，1)区间上的均匀分布产生一个随机数R，根据R大于p否，决定是丢弃该数据包还是让它参加排队，如果R大于p则允许它排队，如果允许它排队，则将它的标识i同时加入到队列内；否则丢弃该数据包；所述的排队方式如下：当数据包i到达时，进行属性匹配，设数据包i有C_i个属性：$A_{i_1}=a_{i_1},A_{i_2}=a_{i_2},...,A_{i_{C_i}}=a_{i_{C_i}},$其中为属性的取值；将数据包i的标识i分别送入与属性对应的队列组内，所述标识i可采用指针或数据包的存储地址；在每个队列组内，将i送入与属性值对应的队列内；具有相同属性值的数据包在队列中进行FIFO排队；还包括队列组调度策略，所述队列组调度策略包括预调度操作、实际调度操作和队列组之间的轮询操作；所述预调度操作是当一个队列组被轮询到并且非空时，运行该队列组的队列调度策略，直到任一个正在排队的数据包标识能够离开其所在队列；将该标识从所在队列中取出；记录下刚刚被轮询的队列号，使得下次运行该队列组的队列调度策略时，知道从下一个队列开始；结束这一次预调度操作；所述实际调度操作是将得到一次预调度操作的数据包i的属性计数器C_i减1；检查是否C_i＝0，如果C_i≠0，则结束这一次实际调度操作；如果C_i＝0，则将数据包i实际调离全部的队列组和队列，并提供预设的服务，包括发送出去或处理其请求；在完成对数据包i的服务以后，结束这一次实际调度操作；所述队列组之间的轮询操作采用如下方式：(a)采用公平轮询或加权轮询的方式轮询所有的队列组；(b)如果是空队列组，则转到下一个队列组；(c)如果是非空队列组，则进行预调度操作，再进行实际的调度操作；然后转到下一个队列组。