CN100463451C - A multi-dimensional queue scheduling and management method for network data flow - Google Patents
A multi-dimensional queue scheduling and management method for network data flow Download PDFInfo
- Publication number
- CN100463451C CN100463451C CNB200510121085XA CN200510121085A CN100463451C CN 100463451 C CN100463451 C CN 100463451C CN B200510121085X A CNB200510121085X A CN B200510121085XA CN 200510121085 A CN200510121085 A CN 200510121085A CN 100463451 C CN100463451 C CN 100463451C
- Authority
- CN
- China
- Prior art keywords
- queue
- scheduling
- management
- attribute
- group
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
Description
技术领域 technical field
本发明属于网络技术领域,特别是涉及一种对网络中的数据包进行多维的分类排队服务的技术。The invention belongs to the field of network technology, and in particular relates to a technology for multi-dimensional classification and queuing service for data packets in the network.
技术背景technical background
常用的队列调度策略,其核心问题是如何实现公平的带宽分配和动态的带宽共享,且避免不正常业务的影响。所谓公平地分配带宽,就是每个业务类型获得相同的带宽,或者一些业务类型按照管理者的意图获得比其他业务类型更多的带宽。所谓合理地共享带宽,就是将分配给一种业务类型的剩余带宽,给其它业务类型共享。所谓避免不正常业务类型的影响,就是在某些业务类型表现不正常的时候,保证其他业务类型得到正常的服务。Commonly used queue scheduling strategies, the core issue is how to achieve fair bandwidth allocation and dynamic bandwidth sharing, and avoid the impact of abnormal services. The so-called fair bandwidth allocation means that each service type obtains the same bandwidth, or some service types obtain more bandwidth than other service types according to the administrator's intention. The so-called reasonable sharing of bandwidth refers to sharing the remaining bandwidth allocated to one type of business with other types of business. The so-called avoiding the impact of abnormal business types is to ensure that other business types receive normal services when certain business types behave abnormally.
现有的常用队列调度策略有:FIFO(先进先出)、PQ(优先级队列)、FQ(公平队列)、WRR(加权循环)、WFQ(加权公平队列)、DRR(赤字循环)等。Existing commonly used queue scheduling strategies include: FIFO (first in first out), PQ (priority queue), FQ (fair queue), WRR (weighted round robin), WFQ (weighted fair queue), DRR (deficit round robin), etc.
FIFO是一种最基本也是目前使用最多的队列调度策略。FIFO按照数据包的到达顺序入队,又按照这个顺序对每个包进行无区别的服务。数据包的最大时延是由队列的长度决定的,因此可以通过调整队列缓冲区的大小使得时延被控制在允许的范围内。FIFO is the most basic and currently most used queue scheduling strategy. FIFO enters the queue according to the order of arrival of data packets, and performs indiscriminate service for each packet in this order. The maximum delay of data packets is determined by the length of the queue, so the delay can be controlled within the allowable range by adjusting the size of the queue buffer.
在PQ调度算法中,每个类型的数据包对应于一个优先级队列。同一优先级队列中的数据包按照FIFO服务。但在调度过程中,高优先级的队列总是在低优先级队列之前被服务。其特点是关键的业务可以得到保证。它包括绝对优先级队列(Strict priority queuing)和速率限制优先级队列(Rate-controlled priority queuing)两种应用。在前一应用中,某一队列只有在比其优先级高的队列为空的情况下才被调度。其缺点是在高优先级队列流量较大的情况下,较低优先级的队列会长时间的处于饥饿(starvation)状态。在后一应用中,高优先级队列被加上一个带宽限制,一旦高优先级队列消耗的带宽超过此限制,则转到下一个低优先级队列。In the PQ scheduling algorithm, each type of data packet corresponds to a priority queue. Packets in the same priority queue are served according to FIFO. But in the scheduling process, high priority queues are always served before low priority queues. Its characteristic is that key business can be guaranteed. It includes two applications: Strict priority queuing and Rate-controlled priority queuing. In the previous application, a queue is scheduled only if the queue with a higher priority than it is empty. The disadvantage is that when the high-priority queue has a large flow, the lower-priority queue will be in a starvation state for a long time. In the latter application, a bandwidth limit is added to the high-priority queue, and once the bandwidth consumed by the high-priority queue exceeds this limit, it goes to the next low-priority queue.
FQ对各个队列循环服务,每一队列在一次循环中只传送一个数据包。其特点是防止突发流对网络资源的强占,使各个队列享有完全相同的输出带宽。它缺点是当一个队列中的数据包明显大于其他队列中的数据包时,这个队列就会占有比其他队列更多的带宽,所以它并不能真正实现带宽的公平分配。FQ circulates services for each queue, and each queue only transmits one data packet in one cycle. Its feature is to prevent burst flow from occupying network resources, so that each queue can enjoy exactly the same output bandwidth. Its disadvantage is that when the data packets in a queue are significantly larger than those in other queues, this queue will occupy more bandwidth than other queues, so it cannot really achieve a fair allocation of bandwidth.
WFQ作为对FQ的一种改进,它通过给各个队列分配不同的权重来满足不同业务对于带宽的不同要求。As an improvement to FQ, WFQ satisfies different requirements of different services for bandwidth by assigning different weights to each queue.
在WRR队列调度算法中,每个业务类型对应一个队列,每个队列被分配一定的资源和优先级,采用轮询的方式服务这些队列。一次循环当中,每个队列至少可以发送一个数据包,根据权重的不同获得不同的带宽。In the WRR queue scheduling algorithm, each service type corresponds to a queue, each queue is allocated certain resources and priorities, and the polling method is used to serve these queues. In a cycle, each queue can send at least one data packet, and obtain different bandwidths according to different weights.
DRR(赤字循环)给各队列分配不同的定额(quantum)——它决定该队列所占的带宽。调度器轮询每个非空的队列,在将赤字计数器的值加上该队列的定额以后,若此队列队首数据包的大小不大于赤字计数器的值,则对其进行服务,同时相应减少赤字计数器的值;如此对该队列服务,直到队列为空或队首数据包的大小大于计数器的值。其特点是算法简单、各个队列可真正得到和权重相当的带宽、各队列间互不影响、可按需要给各个队列分配不同带宽等。其改进调度策略MDRR在Cisco 12000系列的路由器中被采用。DRR (deficit round robin) assigns different quotas (quantum) to each queue - it determines the bandwidth occupied by the queue. The scheduler polls each non-empty queue, and after adding the value of the deficit counter to the quota of the queue, if the size of the head data packet of this queue is not greater than the value of the deficit counter, it will be served and correspondingly reduced The value of the deficit counter; the queue is serviced in this way until the queue is empty or the size of the packet at the head of the queue is greater than the value of the counter. It is characterized by a simple algorithm, each queue can actually obtain a bandwidth equivalent to the weight, each queue does not affect each other, and different bandwidths can be allocated to each queue according to needs. Its improved scheduling policy MDRR is adopted in Cisco 12000 series routers.
目前常用的队列管理方法,其队列管理机制可以分为两大类:被动式队列管理(Passive Queue Management,PQM)和主动式队列管理(Active Queue Management,AQM)。Currently commonly used queue management methods, the queue management mechanism can be divided into two categories: passive queue management (Passive Queue Management, PQM) and active queue management (Active Queue Management, AQM).
传统的被动式队列管理一般采用“丢尾”(DropTail)策略,即当缓冲区满时,丢弃新到达的数据包。它的局限性是将拥塞控制的责任推给端用户,不能处罚恶意流;在某些情况下,会让某个流或者少数几个流独占队列空间,阻止其他流的包进入队列;会使得队列在相当长时间内处于充满(或几乎充满)的状态。Traditional passive queue management generally adopts the "DropTail" strategy, that is, when the buffer is full, the newly arrived data packets are discarded. Its limitation is that it pushes the responsibility of congestion control to end users, and cannot punish malicious flows; in some cases, it will allow a certain flow or a few flows to monopolize the queue space, preventing packets of other flows from entering the queue; it will make The queue is full (or nearly full) for a significant amount of time.
主动式队列管理机制就是要求网络本身参与资源的管理和控制。它的不同之处在于:通过采用特定的数据包丢弃技术,维护缓冲区的占用量(即队列的长度)在一定的范围内。即,在网络轻度拥塞的时候就按照预定的规则来丢弃少量的数据包,从而使得某些源端降低发送速率,减少了数据包因为在缓冲区中的时间过长而导致的超时重传,并且防止了拥塞的进一步恶化,降低了丢包率,同时还具有容纳突发流量的能力。典型的主动式队列管理机制包括RED、BLUE、ARED、PDPC等。The active queue management mechanism requires the network itself to participate in the management and control of resources. Its difference lies in that by adopting a specific data packet discarding technique, the occupancy of the buffer (that is, the length of the queue) is maintained within a certain range. That is, when the network is slightly congested, a small number of data packets are discarded according to predetermined rules, so that some sources reduce the sending rate and reduce the timeout retransmission of data packets caused by the long time in the buffer , and prevent the further deterioration of congestion, reduce the packet loss rate, and also have the ability to accommodate burst traffic. Typical active queue management mechanisms include RED, BLUE, ARED, PDPC, etc.
RED算法,即随机早期检测算法有两个和队列长度相关的阈值:minth和maxth。当有数据包到达路由器时,RED计算出平均队长avg,当平均队列长度avg小于预先设定的阈值minth时接收所有数据包;当avg大于minth并小于maxth时按照一定的概率P丢弃新到数据包;当avg大于maxth时到达的数据包全部被丢弃。RED在计算平均队长avg时,采用了滑动平均的方法。丢包概率P不仅和avg有关,还和从上一次丢包到现在连续进入队列的包的数量count有关。随着count的增加,下一个包被丢弃的可能性也在缓慢增加,以便均匀地、避免连续地丢包。The RED algorithm, that is, the random early detection algorithm has two thresholds related to the queue length: min th and max th . When a data packet arrives at the router, RED calculates the average queue length avg, and receives all data packets when the average queue length avg is less than the preset threshold min th ; when avg is greater than min th and less than max th , it is discarded according to a certain probability P Newly arrived data packets; when avg is greater than max th, all arriving data packets are discarded. RED uses a moving average method when calculating the average captain avg. The packet loss probability P is not only related to avg, but also related to the number count of packets that have entered the queue continuously since the last packet loss. As count increases, the probability that the next packet will be dropped is slowly increased in order to evenly and avoid consecutive packet drops.
BLUE算法与RED最大的区别在于,BLUE使用实际队列长度来反映拥塞状况,并且使用丢包事件和链路空闲事件来管理拥塞。BLUE动态地改变丢包概率P值:链路空闲和队列空时减小P值,队列溢出导致连续丢包则增加P值。在最小时间间隔freeze-time时间内,概率P只能改变一次。参数d1决定了当队列溢出时P增加的量,d2决定了当链路空闲时P减少的量。当d1比d2大很多时,丢包事件被赋予更大的比重,因而能够对流量的快速增加作出快速反应。The biggest difference between the BLUE algorithm and RED is that BLUE uses the actual queue length to reflect the congestion situation, and uses packet loss events and link idle events to manage congestion. BLUE dynamically changes the packet loss probability P value: when the link is idle and the queue is empty, the P value is reduced, and the queue overflow causes continuous packet loss, and the P value is increased. During the minimum time interval freeze-time, the probability P can only be changed once. The parameter d1 determines the amount by which P increases when the queue overflows, and d2 determines the amount by which P decreases when the link is idle. When d1 is much larger than d2, the packet loss event is given a greater proportion, thus enabling a quick response to a rapid increase in traffic.
ARED(Adaptive RED)算法的基本思想就是通过检查平均队长的变化来决定RED是应更激进还是更保守,从而尽量保持平均队长在minth和maxth之间。它根据流量的变化来自动配置参数maxp。如果avg是在minth附近振荡,说明拥塞控制太激进了,所以减小maxp;如果avg在maxth附近振荡,说明拥塞控制太保守了,那么就增大maxp。ARED是对RED改动很小的一种算法,它保留了RED的基本结构,但消除了RED的队列延时问题和参数敏感性问题。The basic idea of the ARED (Adaptive RED) algorithm is to determine whether RED should be more aggressive or conservative by checking the change of the average captain, so as to keep the average captain between min th and max th . It automatically configures the parameter maxp according to the change of traffic. If avg oscillates near min th , it means that congestion control is too aggressive, so reduce maxp; if avg oscillates near max th , it means that congestion control is too conservative, then increase maxp. ARED is an algorithm with little changes to RED. It retains the basic structure of RED, but eliminates the problem of queue delay and parameter sensitivity of RED.
PDPC(Packet Discard Prevention Counter)算法对队列的实际长度进行监测:当队列长度小于minth时接收新到达的数据包;当队长大于maxth时丢弃该数据包;当队长介于minth和maxth之间时,将该数据包丢弃,并将计算器counter置为n,然后在队长不超过maxth的情况下接收接下来的n个数据包。PDPC的特点是通过丢弃单个数据包来表明拥塞,接收接下来的n个数据包可以减小从TCP同一个发送窗口丢弃多个数据包的可能性。算法简单,易于实现,对无线网络的变化反应速度快,提供了不同流之间的公平性。其缺点是:当网络用户数大大增加的时候,它的性能会很快下降,各项参数缺乏足够的自适应性。The PDPC (Packet Discard Prevention Counter) algorithm monitors the actual length of the queue: when the queue length is less than min th , the newly arrived data packet is received; when the queue length is greater than max th , the data packet is discarded; when the queue length is between min th and max th When between, discard the data packet, set the counter to n, and then receive the next n data packets under the condition that the captain does not exceed max th . The characteristic of PDPC is to indicate congestion by dropping a single packet, and receiving the next n packets can reduce the possibility of dropping multiple packets from the same sending window of TCP. The algorithm is simple, easy to implement, fast in response to changes in the wireless network, and provides fairness among different flows. Its disadvantages are: when the number of network users increases greatly, its performance will decrease rapidly, and various parameters lack sufficient adaptability.
从前述队列调度策略可以看到,现有的技术都是按照数据包的某一种属性,例如流、业务类型等对它们进行区分,然后送入相应的队列排队等待服务。这种区分方法,不适用于多属性的情况。假如一个数据包最多有N个属性,每个属性最多有M个值,则用现有的分类排队方法,最大需要(M+1)N-1个队列,才能够实现分类排队控制!例如,如果我们将网络中的IP数据报按照它的protocol字段、port字段、长度等属性进行区分,则由下表表示的日本到美国的主干线上的实际统计数据可以看到:It can be seen from the aforementioned queue scheduling strategy that the existing technologies all distinguish data packets according to a certain attribute, such as flow and service type, and then send them into corresponding queues to wait for service. This method of distinction does not apply to the case of multiple attributes. If a data packet has at most N attributes, and each attribute has at most M values, then using the existing classification queuing method, a maximum of (M+1) N -1 queues are needed to realize classification queuing control! For example, if we distinguish the IP datagrams in the network according to its protocol field, port field, length and other attributes, the actual statistical data on the backbone line from Japan to the United States can be seen in the following table:
表1 MAWI2005年03月20日14:0-14:5分的统计结果Table 1 Statistical results of MAWI at 14:0-14:5 on March 20, 2005
按protocol进行分类,至少分为6种;Classified by protocol, at least 6 types;
按数据报长度进行区分,可以分成7个段;According to the length of the datagram, it can be divided into 7 segments;
按port进行分类,至少可以分成19个;Classified by port, it can be divided into at least 19 categories;
在一个属性内可以被区分开的二个包,在另一个属性内又可能被合在一起。例如,按protocol区分为tcp和upd的二个包,它们的port可能都是53(dns),包长度可能都在128-255之间。Two packages that can be distinguished in one attribute may be combined in another attribute. For example, two packets divided into tcp and upd according to the protocol may both have port 53 (dns), and the packet length may be between 128-255.
所以当我们通过全部这三个属性来对数据报进行分类时,将需要分成24(协议:端口)×7(长度段)=168个队列。So when we classify datagrams by all these three attributes, it will need to be divided into 24 (protocol: port) × 7 (length segment) = 168 queues.
在有些情况下,例如在对网络运行情况进行监控的时候,系统需要通过队列调度和管理,将网络中各分量所占的比例限制在正常范围内,如上表所示,以避免某些分量的异常增高对网络造成的危害。某些分量异常增高的典型例子是泛洪攻击,例如攻击者向被害服务器发送大量的TCP SYN分组、HTTP GET请求、DNS查询、超长包、或者端口扫描包等。如果采用现有的队列调度与管理技术,对于上述例子,系统将需要建立168个并列的队列,对到达的数据包进行分类排队控制。如果采用串行队列调度与管理的方式,则在各属性之间人为引入了先后顺序。某些具有较多属性的包,在串行队列中可能遇到瓶颈,有可能被丢弃;某些具有较少属性的包在串行队列中走的路径短,因而得以快速通过。由此可见,采用现有技术进行串行队列调度与管理,失去了并行队列的优先权和权重控制、同一队列内的先进先出排队服务等重要特征。因此,现有的队列调度与管理技术,不适用于多属性(或多维)排队控制的情况。In some cases, for example, when monitoring the network operation, the system needs to limit the proportion of each component in the network within the normal range through queue scheduling and management, as shown in the above table, to avoid certain components. Abnormally increased damage to the network. A typical example of an abnormally high component is a flood attack, for example, the attacker sends a large number of TCP SYN packets, HTTP GET requests, DNS queries, overlong packets, or port scanning packets to the victim server. If the existing queue scheduling and management technology is adopted, for the above example, the system will need to establish 168 parallel queues to perform classification and queuing control on the arriving data packets. If the method of serial queue scheduling and management is adopted, an artificial order is introduced between the attributes. Some packets with more attributes may encounter bottlenecks in the serial queue and may be discarded; some packets with fewer attributes take a short path in the serial queue, so they can pass through quickly. It can be seen that using the prior art for serial queue scheduling and management loses important features such as priority and weight control of parallel queues, first-in-first-out queuing service in the same queue, and the like. Therefore, the existing queue scheduling and management technology is not suitable for the situation of multi-attribute (or multi-dimensional) queuing control.
发明内容 Contents of the invention
本发明的目的在于克服现有技术的不足,提供一种网络数据流的多维队列调度与管理系统。利用该技术使得网络可以用比现有队列调度技术更有效的方式,对不同的数据包进行有区别的控制,例如业务质量控制、安全控制等。The purpose of the present invention is to overcome the deficiencies of the prior art and provide a multi-dimensional queue scheduling and management system for network data flow. Utilizing this technology enables the network to perform differentiated control on different data packets, such as service quality control, security control, etc., in a more effective manner than the existing queue scheduling technology.
为了实现发明目的,采用的技术方案如下:In order to realize the purpose of the invention, the technical scheme adopted is as follows:
一种网络数据流的多维队列调度与管理系统,用于对具有多属性且每个属性具有多个取值的网络数据流进行管理,它设置有与网络数据包的属性个数相等的N个队列组,且每个队列组i设置有与属性i取值个数相等的Mi个队列,然后将网络数据包按属性和属性值分类在具体的队列里排队进行调度和管理,以提供不同的服务。A multi-dimensional queue scheduling and management system for network data flow, used to manage network data flow with multiple attributes and each attribute has multiple values, it is set with N number of attributes equal to the number of network data packets Queue groups, and each queue group i is set with M i queues equal to the value of attribute i, and then classifies network data packets according to attributes and attribute values and queues them in specific queues for scheduling and management, so as to provide different services.
具体的多属性排队方式如下:The specific multi-attribute queuing method is as follows:
设数据包i有Ci个属性:
将数据包i的标识i分别送入与属性对应的队列组内,所述标识i可采用指针或数据包的存储地址;Send the identity i of the data packet i to the attribute corresponding queue group Inside, the identifier i can be a pointer or a storage address of a data packet;
在每个队列组内,将i送入与属性值对应的队列内。in each queue group Inside, send i into the attribute value corresponding queue Inside.
通过上述多维队列对数据包进行多属性分类排队后,具有相同属性值的数据包在队列中进行FIFO排队。After multi-attribute classification and queuing of data packets through the above multi-dimensional queue, they have the same attribute value packets in the queue FIFO queuing in.
本发明还包括队列组调度策略,所述队列组调度策略包括预调度操作、实际调度操作和队列组之间的轮询操作:The present invention also includes a queue group scheduling strategy, which includes pre-scheduling operations, actual scheduling operations and polling operations between queue groups:
所述预调度操作是对一个队列组内的队列的调度操作,可采用现有的适用于该队列组所对应的属性特点的队列调度策略,例如优先级队列PQ、或公平队列FQ、或加权循环WRR、或加权公平队列WFQ、或赤字循环DRR等。当一个队列组被轮询到且非空时,则运行该队列组的队列调度策略,直到一个正在排队的项(不妨设数据包标识i)能够离开其所在的队列将该标识i从队列中取出;记录下刚刚被轮询的队列号以备下次运行该队列组的队列调度策略时,从下一状态,即队列开始;然后结束这一次预调度操作。The pre-scheduling operation is a scheduling operation for queues in a queue group, and an existing queue scheduling strategy suitable for the attribute characteristics corresponding to the queue group can be used, such as a priority queue PQ, or a fair queue FQ, or a weighted queue Round-robin WRR, or weighted fair queue WFQ, or deficit round-robin DRR, etc. When a queue group is polled and is not empty, run the queue scheduling strategy of the queue group until a queued item (maybe set the packet identifier i) can leave its queue remove the identifier i from the queue Take it out; record the queue number that was just polled To prepare for the next time the queue scheduling policy of this queue group is run, from the next state, that is, the queue Start; then end this pre-scheduled operation.
所述实际调度操作是将得到一次预调度操作的数据包i的属性计数器Ci减1,并检查是否Ci=0;如果Ci≠0,则结束这一次实际调度操作;如果Ci=0,则完成对该数据包的最后调度操作,即将数据包i实际调离全部的队列组和队列,并提供预设的服务(例如发送出去、或处理其请求等);完成预设的服务将需要一段时间,完成后结束这一次实际调度操作。The actual scheduling operation is to subtract 1 from the attribute counter C i of the data packet i obtained by a pre-scheduling operation, and check whether C i =0; if C i ≠0, then end this actual scheduling operation; if C i = 0, the final scheduling operation of the data packet is completed, that is, the data packet i is actually transferred from all queue groups and queues, and the preset service is provided (such as sending out, or processing its request, etc.); the preset service is completed It will take a while, and the actual scheduling operation will end after completion.
所述的队列组之间的轮询操作,具体如下:The polling operation between the queue groups is as follows:
(a)按照公平轮询或加权轮询的方式轮询所有的队列组;(a) poll all queue groups according to fair round-robin or weighted round-robin;
(b)如果是空队列组,则转到下一个队列组;(b) if it is an empty queue group, then go to the next queue group;
(c)如果是非空队列组,则进行预调度操作,再进行实际的调度操作,然后转到下一个队列组。(c) If it is a non-empty queue group, perform a pre-scheduling operation, then perform an actual scheduling operation, and then go to the next queue group.
与上述的多属性排队方法和队列组调度策略相对应,本发明还提供多维队列管理算法,所述多维队列管理算法设置一个队列管理主模块,且为每个队列设置一个管理子模块。但队列管理子模块并不直接进行队列的操作,只是为队列管理主模块提供参数,即丢弃数据包的概率;由队列管理主模块真正执行对所有队列的管理和操作。Corresponding to the above-mentioned multi-attribute queuing method and queue group scheduling strategy, the present invention also provides a multi-dimensional queue management algorithm. The multi-dimensional queue management algorithm is provided with a main queue management module and a management sub-module for each queue. But the queue management sub-module does not directly operate the queue, but only provides parameters for the queue management main module, that is, the probability of discarding data packets; the queue management main module actually performs the management and operation of all queues.
所述多维队列管理算法具体如下:The multidimensional queue management algorithm is specifically as follows:
当数据包i到达时,所述多属性排队方式将对其进行属性匹配,并按照其属性和属性值选择队列组和每个组内的一个队列,设有Ci个属性,并设这些队列分别为
每个队列所对应的管理子模块按照设定的队列管理算法进行队列管理,从而得出每个队列丢弃一个新到达数据包的概率 The management sub-module corresponding to each queue performs queue management according to the set queue management algorithm, so as to obtain the Probability of dropping a newly arriving packet
以概率决定丢弃该数据包还是让它参加排队;如果允许它排队,则将它的标识i同时加入到队列内;否则丢弃该数据包。with probability Decide whether to discard the packet or let it queue; if it is allowed to queue, add its identifier i to queue; otherwise discard the packet.
所述管理子模块根据队列长分布、时延分布、到达过程、丢弃率、服务时间分布的一种或多种结合来决定丢弃数据包的概率。每个管理子模块都采用适合于自身特点的队列管理算法,它可以是现有的任何队列管理算法,包括RED算法、或BLUE算法、或ARED算法、或PDPC算法,且每个管理子模块采用的队列管理算法可以不同。The management sub-module determines the probability of discarding data packets according to one or more combinations of queue length distribution, delay distribution, arrival process, discard rate, and service time distribution. Each management sub-module adopts a queue management algorithm suitable for its own characteristics, which can be any existing queue management algorithm, including RED algorithm, or BLUE algorithm, or ARED algorithm, or PDPC algorithm, and each management sub-module adopts The queue management algorithm can be different.
本发明通过N个队列组对应数据包的N个属性,每个队列组设置最多M个队列,每个队列对应一个属性值。通过本发明提供的队列调度策略和队列管理算法,最大只需要NM个队列就可以实现分类排队控制。而且本发明可应用于对网络中的数据包进行细粒度的控制,可实现多种应用系统,例如QoS保证、有区分的服务、带宽共享、分类速率控制和过滤、网络入侵防御、异常流过滤等,适用面广。In the present invention, N queue groups correspond to N attributes of data packets, and each queue group sets up to M queues, and each queue corresponds to an attribute value. Through the queue scheduling strategy and queue management algorithm provided by the present invention, only NM queues are needed at most to realize classified queuing control. Moreover, the present invention can be applied to fine-grained control of data packets in the network, and can realize various application systems, such as QoS guarantee, differentiated service, bandwidth sharing, classification rate control and filtering, network intrusion prevention, abnormal flow filtering Etc., widely applicable.
附图说明 Description of drawings
图1为本发明的一个实施例的系统结构图;Fig. 1 is a system structure diagram of an embodiment of the present invention;
图2为本发明的队列调度原理示意图;Fig. 2 is a schematic diagram of the queue scheduling principle of the present invention;
图3为本发明的队列管理原理示意图。Fig. 3 is a schematic diagram of the queue management principle of the present invention.
具体实施方式 Detailed ways
下面结合附图对本发明做进一步的说明。The present invention will be further described below in conjunction with the accompanying drawings.
本发明的系统结构如附图1所示,首先将系统感兴趣的有关各协议层的各字段的特征值存入属性特征库,以备多属性匹配时使用。当一个数据包到达时,系统将它存入存储区内,并记下其所在地址或本地标识。然后开始对该数据包进行多属性匹配。将这些属性和所对应的属性值记录下来。按照这些属性找到多维队列管理模块中的多个对应的队列组,再按照属性值找到每个队列组中的一个队列,由此得到每个队列丢弃该数据包的概率。再由所有这些丢弃概率得到总的平均丢弃概率。总的平均丢弃概率就决定了是丢弃还是接纳该数据包。如果决定丢弃,则将该数据包从存储中清除,并清空其它有关该数据包的记录;如果决定接纳,则将该数据包的标识或者地址送入多维队列调度模块进行排队服务。所进的队列就是该数据包的各属性所对应的队列组中与属性值对应的队列。当该数据包在所进各队列组均获得服务权以后,该数据包就可以离开多维队列调度模块,也即,将该数据包的标识或存储地址送给分类服务模块,由它从存储中取出该数据包,并提供分类服务。分类服务策略可以依据应用系统的不同而不同。例如,最简单的服务方式就是将该数据包发送出去。这种方式借助于前述队列调度和队列管理策略,可以保证网络中的各分量所占比例在一定范围内,避免某些分量异常增高,因而可以应用于保证业务质量、保证各业务公平共享网络带宽、保证网络谐调运行、化解攻击流等各种应用系统。较为复杂的服务方式是对具有某些属性的数据包提供有区别的服务。这种方式除了具有前述的保证网络谐调运行的特点以外,还可以实现对数据包的细粒度的控制,发现可能存在的异常现象或者已知的或新型的攻击。例如从高溢出率的队列的组合模式可以发现被丢弃的数据包的共同特征,由此可以采取对应的策略防御,防止攻击并减少对正常数据包的丢弃。The system structure of the present invention is as shown in accompanying drawing 1, at first the eigenvalues of each field of relevant each protocol layer that the system is interested in are stored in the attribute characteristic library, in order to use when multi-attribute matching. When a data packet arrives, the system stores it in the storage area and records its address or local identification. Then start multi-attribute matching on the packet. Record these attributes and their corresponding attribute values. Find a plurality of corresponding queue groups in the multi-dimensional queue management module according to these attributes, and then find a queue in each queue group according to the attribute value, thereby obtaining the probability that each queue discards the data packet. The total average drop probability is then obtained from all these drop probabilities. The overall average drop probability determines whether to drop or accept the packet. If it is decided to discard, the data packet is cleared from the storage, and other records related to the data packet are emptied; if it is decided to be accepted, the identification or address of the data packet is sent to the multidimensional queue scheduling module for queuing service. The entered queue is the queue corresponding to the attribute value in the queue group corresponding to each attribute of the data packet. After the data packet has obtained the service right in each queue group entered, the data packet can leave the multi-dimensional queue scheduling module, that is, the identification or storage address of the data packet is given to the classification service module, and it can retrieve the information from the storage by it. The packet is fetched and a classification service is provided. Classification service strategy can vary according to different application systems. For example, the easiest way to serve is to send that packet out. With the help of the aforementioned queue scheduling and queue management strategies, this method can ensure that the proportion of each component in the network is within a certain range and avoid abnormal increase of some components. Therefore, it can be applied to ensure service quality and ensure that all services share network bandwidth fairly. , Guarantee the coordinated operation of the network, defuse attack flow and other application systems. A more complex service method is to provide differentiated services for data packets with certain attributes. In addition to the above-mentioned characteristics of ensuring the coordinated operation of the network, this method can also realize fine-grained control of data packets and discover possible abnormal phenomena or known or new attacks. For example, from the combination mode of queues with a high overflow rate, the common characteristics of discarded data packets can be found, so that corresponding defense strategies can be adopted to prevent attacks and reduce the discarding of normal data packets.
队列调度原理如附图2所示。首先要确定系统的队列组数目和每个队列组内的队列的个数。如果系统感兴趣的属性有N个,则需要N个队列组。如果各属性分别有M1,M2,...,MN个值,则各队列组分别需要M1,M2,...,MN个队列。在确定队列组数目和每个队列组内的队列的个数以后,需要根据各属性的特点,分别确定各队列组的队列调度策略。它们不必采用相同的队列调度策略,可以是现有队列调度策略中的任意一种,例如PQ、FQ、WRR、WFQ、DRR等,只要它适合于队列组所对应的属性的特点。各队列组调度策略之间也不必相互谐调,它们可以各自独立运行。The principle of queue scheduling is shown in Figure 2. First, determine the number of queue groups in the system and the number of queues in each queue group. If there are N attributes that the system is interested in, N queue groups are needed. If each attribute has M 1 , M 2 , . . . , M N values, then each queue group needs M 1 , M 2 , . . . , M N queues. After determining the number of queue groups and the number of queues in each queue group, it is necessary to determine the queue scheduling policy of each queue group according to the characteristics of each attribute. They do not have to adopt the same queue scheduling strategy, and can be any of the existing queue scheduling strategies, such as PQ, FQ, WRR, WFQ, DRR, etc., as long as it is suitable for the characteristics of the corresponding attributes of the queue group. The scheduling policies of each queue group do not need to be coordinated with each other, and they can run independently.
在确定各队列组的队列调度策略以后,需要确定各队列的最大长度,它应该保证排队项的平均等待时间和丢弃概率在一定范围内。这里需要注意的是,在计算平均等待时间和丢弃概率的时候,服务时间与被服务的数据包的长度没有直接关系,这是因为每个队列组只完成预调度,刚被预调度出该队列组的项,不一定立即得到服务,它可能还需要等待其它的队列组完成对该数据包的预调度,才可以获得后续的服务。所以从一个给定的队列组看来,在它预调度出队列的两个项之间,有可能有未参加该队列组排队的数据包得到服务并造成这两个项目之间的时延。After determining the queue scheduling strategy of each queue group, it is necessary to determine the maximum length of each queue, which should ensure that the average waiting time and discard probability of queued items are within a certain range. It should be noted here that when calculating the average waiting time and discard probability, the service time is not directly related to the length of the served data packet, because each queue group only completes pre-scheduling, and has just been pre-scheduled out of the queue The item in the group may not be served immediately, and it may need to wait for other queue groups to complete the pre-scheduling of the data packet before it can obtain subsequent services. So from the perspective of a given queue group, between two items that it pre-scheduled out of the queue, there may be data packets that are not queued in the queue group to be served and cause a delay between these two items.
当一个数据包到达并完成属性匹配以后,设有Ci个属性:
在每个队列组内,按值分类模块将数据包标识i送入与属性值对应的队列内。所以,具有相同属性值的数据包,会在相同的队列内进行FIFO排队。in each queue group Inside, the classification module by value sends the packet identifier i into the attribute value corresponding queue Inside. So, with the same attribute value packets, will be in the same queue FIFO queuing within.
对于一个给定的队列组预调度模块可以采用任何预定的队列调度策略,例如PQ、FQ、WRR、WFQ、DRR中的一种。如果该队列组非空,则运行给定的队列调度策略,直到一个正在排队的项,例如数据包标识i能够离开队列。将该标识i从队列中取出,并记录下当前的状态,以备下次运行该队列组的队列调度策略时,从下一状态开始。在完成这些操作以后,即完成了一次预调度以后,进行下一步的实际调度操作。For a given queue group The pre-scheduling module may adopt any predetermined queue scheduling strategy, such as one of PQ, FQ, WRR, WFQ, and DRR. If the queue group is non-empty, run the given queue scheduling policy until an enqueuing item, such as packet id i, is able to leave the queue. The identifier i is taken out of the queue, and the current state is recorded, so as to start from the next state when the queue scheduling policy of the queue group is run next time. After these operations are completed, that is, after a pre-scheduling is completed, the next actual scheduling operation is performed.
实际调度操作首先将刚刚得到一次预调度操作的数据包i的属性计数器Ci减1。然后检查Ci是否等于0,即该数据包是否得到了它所加入的所有队列组的预调度服务。如果Ci≠0,则说明该数据包仍然在某些队列组中排队等待服务;如果Ci=0,则说明可以完成对该数据包的最后调度操作,即将数据包i的有关记录从全部的队列组和队列中清除,然后从缓冲区中取出,送入后续的分类服务模块。完成后续的分类服务将需要一段时间。在此期间,所有队列组停止预调度操作,仅仅进行新到数据包的入队操作。在完成对数据包i的服务后,将控制权交回给轮询模块。The actual scheduling operation first decrements the attribute counter C i of the data packet i that has just received a pre-scheduling operation by 1. Then check whether C i is equal to 0, that is, whether the data packet has obtained the pre-scheduled service of all the queue groups it joins. If C i ≠ 0, it means that the data packet is still queued in some queue groups for service ; The queue group and the queue are cleared, then taken out from the buffer, and sent to the subsequent classification service module. It will take some time to complete the subsequent triage service. During this period, all queue groups stop pre-scheduling operations, and only enqueue new data packets. After completing the service of packet i, control is passed back to the polling module.
由轮询模块执行队列组之间的轮询操作。它负责轮询所有的队列组。如果是空队列组,则不做任何操作,转到下一个队列组;如果是非空队列组,则进行预调度操作,然后进行实调度操作。除了正在被轮询到的那个队列组执行所述的预调度操作以外,其它队列组不能进行预调度操作,但可以进行新到项目的入队操作以及队列管理操作。Polling between queue groups is performed by the polling module. It is responsible for polling all queue groups. If it is an empty queue group, do nothing and go to the next queue group; if it is a non-empty queue group, perform a pre-scheduling operation, and then perform a real scheduling operation. Except for the queue group that is being polled to perform the pre-scheduling operation, other queue groups cannot perform the pre-scheduling operation, but can perform the enqueue operation and queue management operation of newly arrived items.
队列管理原理如附图3所示。首先确定每个队列组每个队列的队列管理算法,例如:RED、BLUE、ARED、PDPC等,这里统称为AQMn,m,其中AQM代表主动队列管理算法,n代表第几个队列组,m代表该队列组中的第几个队列。每个队列的队列管理算法都由一个管理子模块来执行。每个管理子模块都独立运行,采用各自的队列管理算法进行队列管理。但这些队列管理子模块并不直接进行队列的操作,例如丢弃溢出的数据包等,它们只是根据队列长分布、时延分布、到达过程、丢弃率、服务时间分布等,采用它们中的部分或全部参数,这些决定于队列管理算法,来决定丢弃数据包的概率。以队列管理算法RED为例,当队列的平均队列长小于minth时,丢弃新到达数据包的概率为0;当平均队列长大于maxth时,丢弃新到达数据包的概率为1;当平均队列长处于minth和maxth之间时,丢弃新到达数据包的概率为动态决定的所以,各队列管理子模块仅仅为队列管理主模块的决策提供所需的参数。队列管理主模块真正执行对所有队列的管理和操作,包括丢弃溢出的数据包等。The principle of queue management is shown in Figure 3. First determine the queue management algorithm for each queue group, such as: RED, BLUE, ARED, PDPC, etc., here collectively referred to as AQM n, m , where AQM represents the active queue management algorithm, n represents the number of queue groups, m Represents the number of queues in the queue group. The queue management algorithm for each queue is executed by a management submodule. Each management sub-module runs independently and uses its own queue management algorithm for queue management. However, these queue management sub-modules do not directly perform queue operations, such as discarding overflowing data packets, etc., they only use part or All parameters, which depend on the queue management algorithm, determine the probability of dropping a packet. Taking the queue management algorithm RED as an example, when the queue When the average queue length is less than min th , the probability of discarding newly arrived data packets is 0; when the average queue length is greater than max th , the probability of discarding newly arrived data packets is 1; when the average queue length is between min th and max th When , the probability of discarding a newly arrived packet is determined dynamically Therefore, each queue management sub-module only provides the required parameters for the decision-making of the main queue management module. The main module of queue management actually executes the management and operation of all queues, including discarding overflow data packets and so on.
当数据包i到达并完成属性匹配之后,开始进行队列管理。按照该数据包的属性和属性值,设该数据包拟加入的队列分别为 每个队列都按照自己的队列管理算法由各自的队列管理子模块进行队列管理。设队列丢弃一个新到达数据包的概率为则数据包i被正要加入的所有队列都丢弃的平均概率p为在计算了平均丢弃概率p以后,按照(0,1)区间上的均匀分布产生一个随机数R。根据R大于p否,决定是丢弃该数据包还是让它参加排队。如果R大于p则允许它排队,即将它的标识i送给后续的队列调度模块,使得该数据包的标识i可以同时加入到队列 内;否则丢弃该数据包,即将它从缓冲区内清除,并清空与该数据包有关的全部记录。When the data packet i arrives and completes attribute matching, queue management starts. According to the attributes and attribute values of the data packet, the queues to be joined by the data packet are respectively Each queue is managed by its own queue management sub-module according to its own queue management algorithm. set queue The probability of dropping a newly arriving packet is Then the average probability p that the packet i is discarded by all the queues it is about to join is After calculating the average discarding probability p, a random number R is generated according to the uniform distribution on the (0, 1) interval. According to whether R is greater than p or not, it is decided whether to discard the data packet or let it participate in the queue. If R is greater than p, it is allowed to queue, that is, its identifier i is sent to the subsequent queue scheduling module, so that the identifier i of the data packet can be added to the queue at the same time Otherwise, the data packet is discarded, that is, it is cleared from the buffer, and all records related to the data packet are cleared.
Claims (3)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CNB200510121085XA CN100463451C (en) | 2005-12-29 | 2005-12-29 | A multi-dimensional queue scheduling and management method for network data flow |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CNB200510121085XA CN100463451C (en) | 2005-12-29 | 2005-12-29 | A multi-dimensional queue scheduling and management method for network data flow |
Publications (2)
Publication Number | Publication Date |
---|---|
CN1801778A CN1801778A (en) | 2006-07-12 |
CN100463451C true CN100463451C (en) | 2009-02-18 |
Family
ID=36811544
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CNB200510121085XA Expired - Fee Related CN100463451C (en) | 2005-12-29 | 2005-12-29 | A multi-dimensional queue scheduling and management method for network data flow |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN100463451C (en) |
Cited By (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US9141569B2 (en) | 2012-12-18 | 2015-09-22 | International Business Machines Corporation | Tracking a relative arrival order of events being stored in multiple queues using a counter |
US9575822B2 (en) | 2014-08-01 | 2017-02-21 | Globalfoundries Inc. | Tracking a relative arrival order of events being stored in multiple queues using a counter using most significant bit values |
CN107645455A (en) * | 2017-09-12 | 2018-01-30 | 天津津航计算技术研究所 | A kind of message transmission dispatching method of CAN |
Families Citing this family (16)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN101179486B (en) * | 2006-11-10 | 2010-07-14 | 中兴通讯股份有限公司 | Computer network data packet forwarded CAR queue management method |
CN101447943B (en) * | 2008-12-26 | 2011-05-11 | 杭州华三通信技术有限公司 | Queue scheduling system and method |
CN101557340B (en) * | 2009-05-07 | 2011-09-21 | 中兴通讯股份有限公司 | Method for realizing multilevel queue scheduling in data network and device |
ATE525835T1 (en) * | 2009-06-29 | 2011-10-15 | Alcatel Lucent | METHOD FOR MANAGING TRAFFIC LOAD |
CN102073539B (en) * | 2010-12-02 | 2013-10-09 | 华为技术有限公司 | Queue request processing method and device |
CN102594663A (en) * | 2012-02-01 | 2012-07-18 | 中兴通讯股份有限公司 | Queue scheduling method and device |
CN103281257B (en) * | 2013-06-05 | 2016-06-08 | 杭州华三通信技术有限公司 | A kind of protocol message processing method and equipment |
CN104348751B (en) | 2013-07-31 | 2019-03-12 | 中兴通讯股份有限公司 | Virtual output queue authorization management method and device |
CN103731238B (en) * | 2013-12-11 | 2017-04-05 | 福建星网锐捷网络有限公司 | Data transmission method for uplink and device |
CN106603433B (en) * | 2015-10-14 | 2019-10-25 | 瑞昱半导体股份有限公司 | Data output scheduling apparatus and method |
CN105471859B (en) * | 2015-11-20 | 2019-02-26 | 中铁工程装备集团有限公司 | A kind of access control method based on stream granularity |
CN105610733B (en) * | 2016-02-17 | 2019-03-05 | 京信通信系统(中国)有限公司 | Queue scheduling processing method and system |
CN108259382B (en) * | 2017-12-06 | 2021-10-15 | 中国航空工业集团公司西安航空计算技术研究所 | 3x256 priority scheduling circuit |
CN109408483A (en) * | 2018-09-14 | 2019-03-01 | 厦门天锐科技股份有限公司 | Date storage method based on squid proxy server |
CN109586947B (en) * | 2018-10-11 | 2020-12-22 | 上海交通大学 | Distributed equipment information collection system and method |
CN115834486A (en) * | 2022-11-23 | 2023-03-21 | 南京理工大学 | SDN-based traffic scheduling method facing distributed machine learning |
Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US20040120325A1 (en) * | 2002-12-13 | 2004-06-24 | Lawrence Ayres | System for content based message processing |
CN1631008A (en) * | 2001-07-13 | 2005-06-22 | 艾利森公司 | Method and apparatus for scheduling message processing |
CN1682502A (en) * | 2002-07-15 | 2005-10-12 | 索马网络公司 | Apparatus, system and method for transmitting data with different QoS attributes |
-
2005
- 2005-12-29 CN CNB200510121085XA patent/CN100463451C/en not_active Expired - Fee Related
Patent Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN1631008A (en) * | 2001-07-13 | 2005-06-22 | 艾利森公司 | Method and apparatus for scheduling message processing |
CN1682502A (en) * | 2002-07-15 | 2005-10-12 | 索马网络公司 | Apparatus, system and method for transmitting data with different QoS attributes |
US20040120325A1 (en) * | 2002-12-13 | 2004-06-24 | Lawrence Ayres | System for content based message processing |
Non-Patent Citations (2)
Title |
---|
一种分布式联合输入输出排队结构及其调度算法. 赵俊鹏,伊鹏,郭云飞.高技术通讯,第15卷第2期. 2005 |
一种分布式联合输入输出排队结构及其调度算法. 赵俊鹏,伊鹏,郭云飞.高技术通讯,第15卷第2期. 2005 * |
Cited By (5)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US9141569B2 (en) | 2012-12-18 | 2015-09-22 | International Business Machines Corporation | Tracking a relative arrival order of events being stored in multiple queues using a counter |
US9189433B2 (en) | 2012-12-18 | 2015-11-17 | International Business Machines Corporation | Tracking a relative arrival order of events being stored in multiple queues using a counter |
US9823952B2 (en) | 2012-12-18 | 2017-11-21 | International Business Machines Corporation | Tracking a relative arrival order of events being stored in multiple queues using a counter |
US9575822B2 (en) | 2014-08-01 | 2017-02-21 | Globalfoundries Inc. | Tracking a relative arrival order of events being stored in multiple queues using a counter using most significant bit values |
CN107645455A (en) * | 2017-09-12 | 2018-01-30 | 天津津航计算技术研究所 | A kind of message transmission dispatching method of CAN |
Also Published As
Publication number | Publication date |
---|---|
CN1801778A (en) | 2006-07-12 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN100463451C (en) | A multi-dimensional queue scheduling and management method for network data flow | |
EP3955550B1 (en) | Flow-based management of shared buffer resources | |
US8467295B2 (en) | System and methods for distributed quality of service enforcement | |
US8467342B2 (en) | Flow and congestion control in switch architectures for multi-hop, memory efficient fabrics | |
US8532130B2 (en) | Service interface for QoS-driven HPNA networks | |
US6678248B1 (en) | Policy based quality of service | |
US8274974B1 (en) | Method and apparatus for providing quality of service across a switched backplane for multicast packets | |
Parris et al. | Lightweight active router-queue management for multimedia networking | |
EP2174450B1 (en) | Application data flow management in an ip network | |
US9998400B2 (en) | Attribution of congestion contributions | |
US20040081093A1 (en) | Policy based quality of service | |
US8547846B1 (en) | Method and apparatus providing precedence drop quality of service (PDQoS) with class-based latency differentiation | |
US20080304503A1 (en) | Traffic manager and method for performing active queue management of discard-eligible traffic | |
EP2575303A1 (en) | Determining congestion measures | |
US8144588B1 (en) | Scalable resource management in distributed environment | |
US20120176903A1 (en) | Non-uniform per-packet priority marker for use with adaptive protocols | |
Ahammed et al. | Anakyzing the performance of active queue management algorithms | |
US6985442B1 (en) | Technique for bandwidth sharing in internet and other router networks without per flow state record keeping | |
US7408876B1 (en) | Method and apparatus for providing quality of service across a switched backplane between egress queue managers | |
US7599292B1 (en) | Method and apparatus for providing quality of service across a switched backplane between egress and ingress queue managers | |
Astuti | Packet handling | |
Ceco et al. | Performance comparison of active queue management algorithms | |
WO2025055717A1 (en) | Network congestion processing method and apparatus, and readable medium | |
CN116781642A (en) | QoS cloud host communication queue guaranteeing system for quantum computing equipment | |
Yamagaki et al. | RED method with dual-fairness metrics cooperating with TCP congestion control |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
C06 | Publication | ||
PB01 | Publication | ||
C10 | Entry into substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
C14 | Grant of patent or utility model | ||
GR01 | Patent grant | ||
CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20090218 Termination date: 20141229 |
|
EXPY | Termination of patent right or utility model |