CN103929374A - Multilevel queue scheduling method based on service type - Google Patents

Abstract

The invention discloses a multilevel queue scheduling method based on a service type. The multilevel queue scheduling method includes the steps that a service flow is divided into an A type service and a B type service according to the type of the service flow; classified service flow data packets are stored in service flow queues corresponding to the service flow data packets, and second-level scheduling is performed; first-level scheduling is performed on the service flow data packets to be scheduled in the two queues after the second-level scheduling is completed, and the service flow data packets are output to a link according to a scheduling result. According to the multilevel queue scheduling method based on the service type, classification is performed firstly according to the service type, and multilevel scheduling is performed secondly. The basic service quality of services which have the strict requirements for the service quality can be effectively ensured, and meanwhile the fairness of overall scheduling can be ensured. The multilevel queue scheduling method can be widely applied to the technical field of communication.

Description

A kind of multilevel queue scheduling method based on type of service

Technical field

The present invention relates to communication technical field, relate in particular to a kind of multilevel queue scheduling method based on type of service.

Background technology

At present, along with the develop rapidly of the network communications technology, people have higher requirement to service quality, the performance etc. of network, and network is also gradually towards synthesization future development, and therefore, the business that network need to be supported is also diversified.Array dispatching method, as the important technology that ensures network efficiency and practicality, plays very important effect to network service quality.And dissimilar Business Stream needs different system supports more at present, although proposed at present a lot of dispatching methods, seldom can address the above problem.

Existing array dispatching method mainly contains SP, FIFO, RR etc., and fifo queue dispatching algorithm is mainly to dispatch the priority time arriving according to traffic data bag, i.e. First Come First Served, but this method is not considered actual service application needs.SP queue scheduling algorithm is dispatched according to queue priority, and schedules low priority queue again after queue scheduling that priority is high is complete may cause Low Priority Queuing to can not get for a long time service.RR queue scheduling algorithm is proportionally dispatched multiple queues, and the method has good fairness, but the application demand of the business of not considering.

Summary of the invention

In order to solve the problems of the technologies described above, to the object of this invention is to provide one and can improve QoS, and there is a kind of multilevel queue scheduling method based on type of service of better fairness.

The technical solution adopted in the present invention is:

A multilevel queue scheduling method based on type of service, comprises the following steps:

A, according to the type of Business Stream, Business Stream is divided into A service and b service;

B, sorted traffic data bag is deposited in to its corresponding traffic stream queues, and carry out second-level dispatching;

C, in two queues after second-level dispatching, treat that to completing dispatching services stream packets carries out schedule level one together, and export traffic data bag to link according to scheduling result.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, described step B comprises A service second-level dispatching step and b service second-level dispatching step:

Described A service second-level dispatching step comprises:

B11, A service stream packets is deposited in to the first traffic stream queues according to the sequencing arriving, and distribute corresponding weighted value according to the required bandwidth value of each A service stream packets;

B12, the A service stream packets of each the first traffic stream queues is carried out to the calculating of timestamp, and wait for the scheduling of the first dispatch server;

B13, when the first dispatch server is when idle, the A service stream packets of timestamp minimum in the first traffic stream queues is transmitted;

Described b service second-level dispatching step comprises:

B21, b service stream packets is deposited in to the second traffic stream queues according to the sequencing arriving, and the weighted value of each b service stream packets is made as to 1;

B22, the b service stream packets of each the second traffic stream queues is carried out to the calculating of timestamp, and wait for the scheduling of the second dispatch server;

B23, when the second dispatch server is when idle, the b service stream packets of timestamp minimum in the second traffic stream queues is transmitted.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the timestamp computing formula of described A service stream packets is:

$t_{\mathrm{qos}}^i\left(f\right)=\max \{V_{\mathrm{qos}},t_{\mathrm{qos}}^{i-1}\left(f\right)\}+\frac{p_i\left(f\right)}{B_{\min }\left(f\right)};$

Wherein, V_qosrepresent the reference time of the first dispatch server, p_i(f) length of i A service stream packets of expression,represent the timestamp of i-1 A service stream packets, B_min(f) represent weighted value.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the timestamp computing formula of described b service stream packets is:

$t_{\mathrm{best}}^i\left(f\right)=\max \{V_{\mathrm{best}},t_{\mathrm{best}}^{i-1}\left(f\right)\}+p_i\left(f\right);$

Wherein, V_bestrepresent the reference time of the second dispatch server, p_i(f) length of i b service stream packets of expression,represent the timestamp of i-1 b service stream packets.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, described step C comprises:

C1, according to the required bandwidth value of the first traffic stream queues each traffic data bag to be scheduled and network total resources value, calculate respectively the weighted value of the first traffic stream queues and the second traffic stream queues;

C2, according to the weighted value of two traffic stream queues calculating, calculate the schedule level one timestamp of each traffic data bag in its corresponding queue;

C3, the traffic data bag of schedule level one timestamp minimum in two traffic stream queues is dispatched and exported link to.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the weighted value computing formula of described the first traffic stream queues is:

$W_{\mathrm{qos}}=\underset{f\∈F_{\mathrm{qos}}\left(l\right)}{\mathrm{\Σ}}{B}_{\min }\left(f\right);$

Wherein, B_min(f) the required minimum amount of bandwidth of each traffic data bag of expression the first traffic stream queues.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the weighted value computing formula of described the second traffic stream queues is:

$W_{\mathrm{best}}=C\left(l\right)-\underset{f\∈F_{\mathrm{qos}}\left(l\right)}{\mathrm{\Σ}}{B}_{\min }\left(f\right);$

Wherein, B_min(f) the required minimum amount of bandwidth of each traffic data bag of expression the first traffic stream queues, C (l) represents network total resources value.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the computing formula of the schedule level one timestamp of described A service stream packets to be scheduled is:

$T_{\mathrm{qos}}^i=\max \{V_{\mathrm{link}},T_{\mathrm{qos}}^{i-1}\}+\frac{p_i}{W_{\mathrm{qos}}};$

Wherein, V_linkrepresent the reference time of schedule level one, p_irepresent the length of i A service stream packets,represent the timestamp that i-1 A service stream packets sends, W_qosrepresent the weighted value of the first traffic stream queues.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the computing formula of the schedule level one timestamp of described b service stream packets to be scheduled is:

$T_{\mathrm{best}}^i=\max \{V_{\mathrm{link}},T_{\mathrm{best}}^{i-1}\}+\frac{p_i}{W_{\mathrm{best}}};$

Wherein, V_linkrepresent the reference time of schedule level one, p_irepresent the length of i b service stream packets,represent the timestamp that i-1 b service stream packets sends, W_bestrepresent the weighted value of the second traffic stream queues.

The invention has the beneficial effects as follows:

A kind of multilevel queue scheduling method based on type of service of the present invention is by first classifying according to type of service, then carry out the method for multi-stage scheduling, can, effectively guarantee has the basic service quality of strict demand business to service quality in, also can ensure the fairness of overall scheduling.

Brief description of the drawings

Below in conjunction with accompanying drawing, the specific embodiment of the present invention is described further:

Fig. 1 is the flow chart of steps of a kind of multilevel queue scheduling method based on type of service of the present invention;

Fig. 2 is the schematic diagram of a kind of multilevel queue scheduling method specific embodiment based on type of service of the present invention.

Embodiment

With reference to figure 1, a kind of multilevel queue scheduling method based on type of service of the present invention, comprises the following steps:

A, according to the type of Business Stream, Business Stream is divided into A service and b service;

B, sorted traffic data bag is deposited in to its corresponding traffic stream queues, and carry out second-level dispatching;

C, in two queues after second-level dispatching, treat that to completing dispatching services stream packets carries out schedule level one together, and export traffic data bag to link according to scheduling result.

Wherein, A service is the higher business of requirement of real-time such as voice, video, and this class business has certain requirement for network quality conventionally, ensureing the service quality that need to reserve specific resource when business and determine such business.This just needs network at least can provide minimum bandwidth to ensure basic service quality, and does not limit for the maximum bandwidth that can offer such business.B service is for the business such as mail, file transfer services, and this class business is not strict with for service quality, thereby thinks that its required minimum bandwidth is 0.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, described step B comprises A service second-level dispatching step and b service second-level dispatching step:

Described A service second-level dispatching step comprises:

B11, A service stream packets is deposited in to the first traffic stream queues according to the sequencing arriving, and distribute corresponding weighted value according to the required bandwidth value of each A service stream packets;

B12, the A service stream packets of each the first traffic stream queues is carried out to the calculating of timestamp, and wait for the scheduling of the first dispatch server;

B13, when the first dispatch server is when idle, the A service stream packets of timestamp minimum in the first traffic stream queues is transmitted;

Described b service second-level dispatching step comprises:

B21, b service stream packets is deposited in to the second traffic stream queues according to the sequencing arriving, and the weighted value of each b service stream packets is made as to 1;

B22, the b service stream packets of each the second traffic stream queues is carried out to the calculating of timestamp, and wait for the scheduling of the second dispatch server;

B23, when the second dispatch server is when idle, the b service stream packets of timestamp minimum in the second traffic stream queues is transmitted.

In the second traffic stream queues, by the identical weighted value that is responsible for assigning for each traffic data, ensure the fairness in the second traffic stream queues scheduling.Also can, by being the dissimilar different weighted value of traffic flow assignment, also ensure the flexibility of scheduling in addition.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the timestamp computing formula of described A service stream packets is:

$t_{\mathrm{qos}}^i\left(f\right)=\max \{V_{\mathrm{qos}},t_{\mathrm{qos}}^{i-1}\left(f\right)\}+\frac{p_i\left(f\right)}{B_{\min }\left(f\right)};$

Wherein, V_qosrepresent the reference time of the first dispatch server, p_i(f) length of i A service stream packets of expression,represent the timestamp of i-1 A service stream packets, B_min(f) represent weighted value.

V_qosthe variable of safeguarding of the first dispatch server, for following the tracks of the timestamp of traffic data bag of first last transmission of traffic stream queues.It is for determining the timestamp of new data flow or the time started of new the first traffic stream queues.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the timestamp computing formula of described b service stream packets is:

$t_{\mathrm{best}}^i\left(f\right)=\max \{V_{\mathrm{best}},t_{\mathrm{best}}^{i-1}\left(f\right)\}+p_i\left(f\right);$

Wherein, V_bestrepresent the reference time of the second dispatch server, p_i(f) length of i b service stream packets of expression,represent the timestamp of i-1 b service stream packets.Wherein V_bestbe the variable of safeguarding of the second dispatch server, for following the tracks of the timestamp of traffic data bag of second last transmission of traffic stream queues.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, described step C comprises:

C1, according to the required bandwidth value of the first traffic stream queues each traffic data bag to be scheduled and network total resources value, calculate respectively the weighted value of the first traffic stream queues and the second traffic stream queues;

C2, according to the weighted value of two traffic stream queues calculating, calculate the schedule level one timestamp of each traffic data bag in its corresponding queue;

C3, the traffic data bag of schedule level one timestamp minimum in two traffic stream queues is dispatched and exported link to.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the weighted value computing formula of described the first traffic stream queues is:

$W_{\mathrm{qos}}=\underset{f\∈F_{\mathrm{qos}}\left(l\right)}{\mathrm{\Σ}}{B}_{\min }\left(f\right);$

Wherein, B_min(f) the required minimum amount of bandwidth of each traffic data bag of expression the first traffic stream queues.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the weighted value computing formula of described the second traffic stream queues is:

$W_{\mathrm{best}}=C\left(l\right)-\underset{f\∈F_{\mathrm{qos}}\left(l\right)}{\mathrm{\Σ}}{B}_{\min }\left(f\right);$

Wherein, B_min(f) the required minimum amount of bandwidth of each traffic data bag of expression the first traffic stream queues, C (l) represents network total resources value.Can, in ensureing that the first dispatch server has minimum guarantee bandwidth, remaining bandwidth be distributed to the second dispatch server like this, be conducive to increase resource distributional equity.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the computing formula of the schedule level one timestamp of described A service stream packets to be scheduled is:

$T_{\mathrm{qos}}^i=\max \{V_{\mathrm{link}},T_{\mathrm{qos}}^{i-1}\}+\frac{p_i}{W_{\mathrm{qos}}};$

Wherein, V_linkrepresent the reference time of schedule level one, p_irepresent the length of i A service stream packets,represent the timestamp that i-1 A service stream packets sends, W_qosrepresent the weighted value of the first traffic stream queues.

As described a kind of multilevel queue scheduling further improvements in methods based on type of service, the computing formula of the schedule level one timestamp of described b service stream packets to be scheduled is:

$T_{\mathrm{best}}^i=\max \{V_{\mathrm{link}},T_{\mathrm{best}}^{i-1}\}+\frac{p_i}{W_{\mathrm{best}}};$

Wherein, V_linkrepresent the reference time of schedule level one, p_irepresent the length of i b service stream packets,represent the timestamp that i-1 b service stream packets sends, W_bestrepresent the weighted value of the second traffic stream queues.

With reference to figure 2, Fig. 2 is the schematic diagram of a kind of multilevel queue scheduling method specific embodiment based on type of service of the present invention, f1 in figure, f2, fm belongs to the first dispatch server Business Stream to be processed, and f3, fn belongs to the second dispatch server needs Business Stream to be processed.F1, f2, fm all needs to ensure minimum bandwidth, and the first dispatch server is distributed to f1, f2, the minimum of fm ensures that bandwidth is respectively B_min(f₁), B_min(f₂) and B_min(f_m), in ensureing the minimum guarantee of the first dispatch server bandwidth, remaining bandwidth is distributed to the second dispatch server like this, its residue broadband is C (l)-B_min(f₁)-B_min(f₂)-B_min(f_m), and the second dispatch server adopts Weighted Fair Queuing method to dispatch f3 and fn, and the weighted value of f3 and fn is all 1, therefore, the bandwidth that the second dispatch server is distributed to Business Stream f3 and fn is 0.5* (C (l)-B_min(f1)-B_min(f₂)-B_min(f_m))

Suppose f1, f2, fm arrives queue simultaneously, and in queue, each traffic data bag size is the same, is all 1.

The timestamp that can obtain first traffic data bag of Business Stream f1 is:

$t_{\mathrm{qos}}^1\left(f_1\right)=\max \{V_{\mathrm{qos}},t_{\mathrm{qos}}^{i-1}\left(f_1\right)\}+\frac{1}{B_{\min }\left(f_1\right)};$

The timestamp that can obtain first traffic data bag of Business Stream f2 is:

$t_{\mathrm{qos}}^1\left(f_2\right)=\max \{V_{\mathrm{qos}},t_{\mathrm{qos}}^{i-1}\left(f_2\right)\}+\frac{1}{B_{\min }\left(f_2\right)};$

The timestamp that can obtain first traffic data bag of Business Stream fm is:

$t_{\mathrm{qos}}^1\left(f_m\right)=\max \{V_{\mathrm{qos}},t_{\mathrm{qos}}^{i-1}\left(f_m\right)\}+\frac{1}{B_{\min }\left(f_m\right)};$

Can find by contrast, for the larger queue of weighted value, i.e. the minimum bandwidth B that ensures_min(f) larger queue, will preferentially obtain the dispatch service of the first dispatch server, and the first dispatch server is by the traffic data bag of preferentially exporting in the traffic stream queues that weight is larger.

In the time of the second dispatch server dispatch deal, can obtain about Business Stream f3 equally, the timestamp of first bag of fn,

The timestamp of first traffic data bag of Business Stream f3 is:

$t_{\mathrm{best}}^1\left(f_3\right)=\max \{V_{\mathrm{best}},t_{\mathrm{best}}^{i-1}\left(f_3\right)\}+p_i\left(f_3\right);$

The timestamp of first traffic data bag of Business Stream fn is:

$t_{\mathrm{best}}^1\left(f_n\right)=\max \{V_{\mathrm{best}},t_{\mathrm{best}}^{i-1}\left(f_n\right)\}+p_i\left(f_n\right);$

As can be seen here, for the traffic stream queues that needs scheduling in the second dispatch server, these queue schedulings do not have obvious dominance relation, and only relevant with the traffic data bag time of advent itself and traffic data bag size, thereby can be good at ensureing the fairness service between these traffic stream queues.

Suppose that the first dispatch server and the second dispatch server all have traffic data bag to need transmission, at this moment just need to, by schedule level one server, carry out dispatch deal to the two queue.And the traffic data bag that the first dispatch server need to be dispatched is the traffic data bag queue calculating according to timestamp size in second-level dispatching, and the traffic data bag that the second dispatch server need to be dispatched is also the traffic data bag queue of calculating according to timestamp size.

Can obtain according to the method proposing, the timestamp of first traffic data bag of the first dispatch server queue is:

$T_{\mathrm{qos}}^1=\max \{V_{\mathrm{link}},T_{\mathrm{qos}}^{i-1}\}+\frac{p_i}{W_{\mathrm{qos}}};$

The timestamp of first traffic data bag of the second dispatch server is:

$T_{\mathrm{best}}^1=\max \{V_{\mathrm{link}},T_{\mathrm{best}}^{i-1}\}+\frac{p_i}{W_{\mathrm{best}}};$

Therefore, one-level queue dispatcher will select the traffic data bag for the treatment of timestamp minimum in dispatching services stream packets to dispatch output, suppose that traffic data bag size is the same, server weighted value is larger, and its corresponding queue traffic data bag will preferentially obtain dispatch service.

More than that better enforcement of the present invention is illustrated, but the invention is not limited to described embodiment, those of ordinary skill in the art also can make all equivalent variations or replacement under the prerequisite without prejudice to spirit of the present invention, and the distortion that these are equal to or replacement are all included in the application's claim limited range.

Claims (9)

1. the multilevel queue scheduling method based on type of service, is characterized in that, comprises the following steps:

A, according to the type of Business Stream, Business Stream is divided into A service and b service;

B, sorted traffic data bag is deposited in to its corresponding traffic stream queues, and carry out second-level dispatching;

C, in two queues after second-level dispatching, treat that to completing dispatching services stream packets carries out schedule level one together, and export traffic data bag to link according to scheduling result.

2. a kind of multilevel queue scheduling method based on type of service according to claim 1, is characterized in that: described step B comprises A service second-level dispatching step and b service second-level dispatching step:

Described A service second-level dispatching step comprises:

B11, A service stream packets is deposited in to the first traffic stream queues according to the sequencing arriving, and distribute corresponding weighted value according to the required bandwidth value of each A service stream packets;

B12, the A service stream packets of each the first traffic stream queues is carried out to the calculating of timestamp, and wait for the scheduling of the first dispatch server;

B13, when the first dispatch server is when idle, the A service stream packets of timestamp minimum in the first traffic stream queues is transmitted;

Described b service second-level dispatching step comprises:

B21, b service stream packets is deposited in to the second traffic stream queues according to the sequencing arriving, and the weighted value of each b service stream packets is made as to 1;

B22, the b service stream packets of each the second traffic stream queues is carried out to the calculating of timestamp, and wait for the scheduling of the second dispatch server;

B23, when the second dispatch server is when idle, the b service stream packets of timestamp minimum in the second traffic stream queues is transmitted.

3. a kind of multilevel queue scheduling method based on type of service according to claim 2, is characterized in that: the timestamp computing formula of described A service stream packets is:

$t_{\mathrm{qos}}^i\left(f\right)=\max \{V_{\mathrm{qos}},t_{\mathrm{qos}}^{i-1}\left(f\right)\}+\frac{p_i\left(f\right)}{B_{\min }\left(f\right)};$

Wherein, V_qosrepresent the reference time of the first dispatch server, p_i(f) length of i A service stream packets of expression,represent the timestamp of i-1 A service stream packets, B_min(f) represent weighted value.

4. a kind of multilevel queue scheduling method based on type of service according to claim 2, is characterized in that: the timestamp computing formula of described b service stream packets is:

$t_{\mathrm{best}}^i\left(f\right)=\max \{V_{\mathrm{best}},t_{\mathrm{best}}^{i-1}\left(f\right)\}+p_i\left(f\right);$

Wherein, V_bestrepresent the reference time of the second dispatch server, p_i(f) length of i b service stream packets of expression,represent the timestamp of i-1 b service stream packets.

5. a kind of multilevel queue scheduling method based on type of service according to claim 1, is characterized in that: described step C comprises:

C1, according to the required bandwidth value of the first traffic stream queues each traffic data bag to be scheduled and network total resources value, calculate respectively the weighted value of the first traffic stream queues and the second traffic stream queues;

C2, according to the weighted value of two traffic stream queues calculating, calculate the schedule level one timestamp of each traffic data bag in its corresponding queue;

C3, the traffic data bag of schedule level one timestamp minimum in two traffic stream queues is dispatched and exported link to.

6. a kind of multilevel queue scheduling method based on type of service according to claim 5, is characterized in that: the weighted value computing formula of described the first traffic stream queues is:

$W_{\mathrm{qos}}=\underset{f\∈F_{\mathrm{qos}}\left(l\right)}{\mathrm{\Σ}}{B}_{\min }\left(f\right);$

Wherein, B_min(f) the required minimum amount of bandwidth of each traffic data bag of expression the first traffic stream queues.

7. a kind of multilevel queue scheduling method based on type of service according to claim 5, is characterized in that: the weighted value computing formula of described the second traffic stream queues is:

$W_{\mathrm{best}}=C\left(l\right)-\underset{f\∈F_{\mathrm{qos}}\left(l\right)}{\mathrm{\Σ}}{B}_{\min }\left(f\right);$

Wherein, B_min(f) the required minimum amount of bandwidth of each traffic data bag of expression the first traffic stream queues, C (l) represents network total resources value.

8. a kind of multilevel queue scheduling method based on type of service according to claim 5, is characterized in that: the computing formula of the schedule level one timestamp of described A service stream packets to be scheduled is:

$T_{\mathrm{qos}}^i=\max \{V_{\mathrm{link}},T_{\mathrm{qos}}^{i-1}\}+\frac{p_i}{W_{\mathrm{qos}}};$

Wherein, V_linkrepresent the reference time of schedule level one, p_irepresent the length of i A service stream packets,represent the timestamp that i-1 A service stream packets sends, W_qosrepresent the weighted value of the first traffic stream queues.

9. a kind of multilevel queue scheduling method based on type of service according to claim 5, is characterized in that: the computing formula of the schedule level one timestamp of described b service stream packets to be scheduled is:

$T_{\mathrm{best}}^i=\max \{V_{\mathrm{link}},T_{\mathrm{best}}^{i-1}\}+\frac{p_i}{W_{\mathrm{best}}};$

Wherein, V_linkrepresent the reference time of schedule level one, p_irepresent the length of i b service stream packets,represent the timestamp that i-1 b service stream packets sends, W_bestrepresent the weighted value of the second traffic stream queues.