CN101009655B - Traffic scheduling method and device - Google Patents
Traffic scheduling method and device Download PDFInfo
- Publication number
- CN101009655B CN101009655B CN200710003485XA CN200710003485A CN101009655B CN 101009655 B CN101009655 B CN 101009655B CN 200710003485X A CN200710003485X A CN 200710003485XA CN 200710003485 A CN200710003485 A CN 200710003485A CN 101009655 B CN101009655 B CN 101009655B
- Authority
- CN
- China
- Prior art keywords
- queue
- user
- bandwidth
- information
- scheduling
- 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.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 33
- 238000007493 shaping process Methods 0.000 claims description 7
- 238000012545 processing Methods 0.000 claims description 2
- 238000010586 diagram Methods 0.000 description 9
- 230000005540 biological transmission Effects 0.000 description 7
- 230000000694 effects Effects 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 2
- 241001522296 Erithacus rubecula Species 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000001914 filtration Methods 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 230000001737 promoting effect Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
- H04L47/62—Queue scheduling characterised by scheduling criteria
- H04L47/621—Individual queue per connection or flow, e.g. per VC
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/50—Queue scheduling
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The disclosed flow-schedule method in this case comprises: taking the user information of exact business in information flow as the sequence element to configure into queue of exact business, wherein, one queue matching one exact business; according to the exact business and user information in queue, allocating bandwidth for element in queue. It also discloses a flow-schedule device. This invention simplifies circuit and management work well, reduces data error, and improves schedule efficiency.
Description
Technical Field
The present invention relates to the field of traffic scheduling technologies for networks, and in particular, to a traffic scheduling method and apparatus.
Background
The rapidly growing Internet (Internet) is interacting with and promoting ever increasing consumer demand. Nowadays, the demand of users for communication has gradually extended from the low-speed services of traditional telephones, faxes, telegrams, etc. to the broadband services fields of high-speed Internet access, videophones, video on demand, etc. Therefore, the increasing network traffic and the user's requirements for quality of service are demanding the performance and quality of service (QoS) of the router as the core device of the Internet.
In the prior art, in order to ensure the QoS performance of the Internet, a traffic scheduling (TM) technology is currently used to schedule network traffic so as to reduce the message loss rate and reduce the message transmission delay and delay jitter. The scheduling refers to that the router allocates the sending rate of the information flow to be sent based on some reference factors, and guarantees the fairness of sending under the condition of network congestion. The information stream may be a video stream, an audio stream, or a data stream, etc.
Referring to fig. 1, fig. 1 is a schematic diagram of a conventional five-stage traffic scheduling scheme. The five-level scheduling scheme performs traffic scheduling based on five reference factors, namely, Flow (Flow), user (user), Virtual Local Area Network (VLAN), queue priority (class), and port (port). In order to implement scheduling, the existing traffic scheduling scheme needs to classify received information streams according to a certain rule before scheduling, so as to implement scheduling by using an applicable scheduling algorithm for different types of information streams. In the existing traffic scheduling scheme, message data having the same source Internet Protocol (IP) address, destination IP address, source port number, destination port number, protocol number, and service type in an information flow are generally classified into the same class, that is, the same flow, and a queue is divided based on one flow, where each queue is arranged with message data information belonging to the same flow.
The existing traffic scheduling scheme performs traffic scheduling based on a flow, which corresponds to the fifth level scheduling in fig. 1. In the fifth-level scheduling, the router searches for a scheduling parameter related to the message data information according to the message data information in the queue, calculates a scheduling result based on the scheduling parameter, i.e., calculates a bandwidth that can be allocated to the queue, configures different priorities for different queues, and allocates corresponding bandwidths, and the scheduling can be implemented by using scheduling algorithms such as absolute priority (SP) or Weight Round Robin (WRR). The reference factor for the fourth level scheduling is the user. One user may correspond to a plurality of streams, and therefore, if the total bandwidth allocated to the user exceeds the bandwidth purchased by the user as a result of the fifth-level scheduling, the total bandwidth allocated to the user does not exceed the bandwidth purchased by the user through the fourth-level scheduling; this stage of scheduling may be implemented using a virtual clock Shaping (SHVC) algorithm. The reference factor of the third-level scheduling is Virtual Local Area Network (VLAN), and the level scheduling adjusts the bandwidth distributed to each queue according to VLAN network planning; this level of scheduling may be implemented using a Weighted Fair Queuing (WFQ) algorithm. The reference factor of the second-level scheduling is queue priority (class), and the information flow with higher priority is guaranteed to be dequeued firstly through the second-level scheduling; this level of scheduling may be implemented using an absolute priority (SP) algorithm. The reference factor of the first-level scheduling is a port (port), and the role of the first-level scheduling is to shape the traffic of the output port so as to enable the information flow to be sent out more uniformly; the WFQ algorithm may be employed to achieve this level of scheduling.
The inventor finds in research that the prior art is a data-driven traffic scheduling technique. The data driving means that the network node responsible for traffic scheduling performs traffic scheduling only when receiving the packet data. The circuit for realizing scheduling firstly needs to perform the above-mentioned flow classification according to the received data, then needs to search the scheduling parameter corresponding to each item of data added into the queue from the corresponding scheduling parameter table in order to ensure the requirement of flow control, and then calculates the scheduling result based on the scheduling parameter. Because the length and content of actual data added into a queue change at any time, it is difficult to predict in advance, and if the existing traffic scheduling scheme needs to accurately control the traffic flow of each user, the number of queues to be set up may be large, for example, if there are 4k existing users and 8 flows for each user, then the existing traffic scheduling scheme needs to set up 32k queues to implement traffic scheduling, and to perform traffic scheduling on such numerous queues, the complexity of its implementation circuit is high, and it is difficult to implement high-speed scheduling. If the complexity of the circuit is reduced as much as possible by simplifying the measures of the second-level, third-level or fourth-level scheduling, the obtained scheduling effect will hardly meet the requirements of the network.
Therefore, the existing traffic scheduling scheme has a problem that the complexity of circuit implementation is high due to traffic scheduling based on received data.
Disclosure of Invention
The embodiment of the invention provides a flow scheduling method, which simplifies the complexity of realizing a flow scheduling circuit.
A traffic scheduling method comprises the following steps:
configuring user information corresponding to specific services in the service types to which the information flows belong as queue elements into queues corresponding to the specific services, wherein one queue corresponds to one specific service;
allocating bandwidth to the user corresponding to the element in the queue according to the specific service corresponding to the queue and the user information in the queue; the allocation of bandwidth to the users is embodied by the number of times of opportunities to send data provided to the users corresponding to the elements in the queue in a unit time.
The embodiment of the invention also provides a flow scheduling device, which simplifies the complexity of realizing the flow scheduling circuit.
A traffic scheduling apparatus, comprising: the device comprises a queue element configuration module and a bandwidth allocation module; wherein,
the queue element configuration module is used for configuring user information corresponding to specific services in the service types to which the information flow belongs as queue elements into queues corresponding to the specific services and outputting the queue information which is configured with the user information and corresponds to the specific services;
the bandwidth allocation module is used for receiving the queue information from the queue element configuration module and allocating bandwidth to the users corresponding to the elements in the queue according to the specific service corresponding to the queue and the user information in the queue; the allocation of bandwidth to the users is embodied by the number of times of opportunities to send data provided to the users corresponding to the elements in the queue in a unit time.
The traffic scheduling method and apparatus provided in the embodiments of the present invention divide a queue according to a specific service provided by an operator, use the user information of the specific service customized to correspond to the queue as an element constituting the queue, and perform traffic scheduling based on the user information in the queue and the corresponding specific service, because the type of the specific service provided by the operator is limited and the bandwidth of the specific service is usually fixed, the number of queues that can be divided is not too large, and because the number of users in one queue and the parameters such as the bandwidth of the specific service are predictable, when performing traffic scheduling, the bandwidth can be allocated to the user identified by the user information in the queue only according to the bandwidth of the specific service corresponding to the queue, compared with the existing traffic scheduling scheme that a flow classification needs to be performed according to actual data that is difficult to predict, and then the bandwidth is allocated by searching for the related traffic parameter, the flow scheduling scheme of the embodiment of the invention is easier to realize. Moreover, because the traffic scheduling is performed based on the specific service, and the operator performs configuration based on the specific service and the user who customizes the specific service during network planning, the traffic scheduling policy of the embodiment of the present invention can correspond to the relevant configuration of the operator during network planning, so that the scheduling result can better satisfy the network requirement. Therefore, by adopting the flow scheduling scheme of the embodiment of the invention, the circuit complexity of flow scheduling can be effectively simplified while the scheduling result can meet the network requirement.
Drawings
Fig. 1 is a schematic diagram of a prior art five-stage traffic scheduling scheme;
fig. 2 is a flowchart of an overall scheme of traffic scheduling provided by an embodiment of the present invention;
fig. 3 is a schematic structural diagram of a traffic scheduling apparatus according to an embodiment of the present invention;
fig. 4 is a schematic diagram of traffic scheduling based on a specific service in embodiment 1 of the present invention;
FIG. 5 is a diagram illustrating queue element placement in accordance with an embodiment of the present invention;
fig. 6 is a schematic diagram of traffic scheduling performed in embodiment 2 of the present invention.
Detailed Description
In order to make the technical solutions and advantages of the embodiments of the present invention clearer, the following detailed description is made with reference to the accompanying drawings.
Different from the existing traffic scheduling scheme mentioned in the background art, the traffic scheduling method provided in the embodiment of the present invention does not perform traffic scheduling based on received actual data, but performs traffic scheduling based on a user and a specific service customized by the user, so that the traffic scheduling process in the embodiment of the present invention is not related to whether actual service data exists in a queue, and a scheduling result is user information transmitted at a certain rate, that is, a chance of transmitting data for the user once is provided.
Referring to fig. 2, fig. 2 is a flowchart of an overall scheme of traffic scheduling according to an embodiment of the present invention. The process comprises the following steps:
step 201, according to the specific service of the service type to which the information flow belongs, dividing the queue corresponding to the specific service.
In existing network traffic, the traffic types to which information flows belong are generally not classified into three types: video traffic, audio traffic, and data traffic. The type of specific service of the service type to which the information flow provided by the operator belongs is also limited, for example, for audio service, the operator may provide specific services with basic rate of 64 kbytes/second (b/s), 128kb/s or 256 kb/s. The invention divides the queues based on the concrete service, if the operator only provides an audio service with a basic speed of 64kb/s, the number of the queues divided based on the audio service is also one, and the concrete service corresponding to the queues is the audio service with the basic speed of 64 kb/s.
Further, in practical applications, since the specific services available by the operator are usually multiple, there are multiple divided queues correspondingly. The process of dividing the queue may be: firstly, classifying the service types which can be provided by an operator, such as video service, audio service and data service, and determining the service type of the information flow through the classification; then, dividing the queues based on the specific services of each service type that the operator can provide, as mentioned above, there are three specific services of the audio stream, and accordingly, based on the three specific services, 3 queues respectively corresponding to the three specific services can be divided; in addition, if the specific services of the video stream available by the operator are 1Mb/s, 2Mb/s and 4Mb/s, then similarly, 3 queues can be further divided based on the three specific services; if the specific traffic of the provided data stream is 256kb/s, 1Mb/s and 10Mb/s, 3 queues may be similarly divided based on the three specific traffic.
The user information may be user Identification (ID) information, such as a mobile phone number of the user. In practical applications, if a user purchases a specific service, such as an audio service with a basic rate of 64kb/s, the user ID may be configured as an element in a queue corresponding to the specific service.
The situations that may occur in practical applications include: a plurality of users purchase the service of the same specific service, so that ID information of the plurality of users appears in a queue corresponding to the specific service, each user ID corresponds to one element forming the queue, numbers are distributed to the plurality of user IDs, and the user IDs are configured to the positions corresponding to the numbers in the queue according to the numbers; or, the operator provides a plurality of specific services, and one user purchases a service of the plurality of specific services, then the same element, that is, the user ID information of purchasing the plurality of specific services, may appear in each queue corresponding to the plurality of specific services, respectively.
Of course, the actual possible situations are not limited to the above, but the basic way of forming the queue in the present invention may be to divide the queue based on the specific service, and add the user ID corresponding to the specific service to the queue as the queue element corresponding to the group.
Step 203, allocating bandwidth to the user corresponding to the element in the queue according to the specific service corresponding to the queue and the user information in the queue.
The traffic scheduling policy of the embodiment of the invention is performed based on the user information and the corresponding specific service, rather than the actually received information flow. Because the required bandwidth of the specific service provided by the operator is relatively fixed, when performing traffic scheduling, compared with the method that the scheduling result is calculated by searching for the traffic parameter corresponding to the actual message data in the queue in the existing traffic scheduling scheme, the specific implementation of the scheduling policy of the embodiment of the present invention is relatively simple. This advantage of the present invention will be described in detail hereinafter.
In practical applications, if the queue is already divided based on specific services, the step 201 need not be executed, and only the queue element needs to be configured when the queue element changes.
The embodiment of the invention also provides a flow scheduling device based on the flow scheduling method. Referring to fig. 3, fig. 3 is a schematic structural diagram of an embodiment of the apparatus, including: a queue element configuration module 301 and a bandwidth allocation module 302; wherein,
a queue element configuration module 301, configured to configure, as a queue element, user information corresponding to a specific service in a service type to which an information flow belongs to a queue corresponding to the specific service, and output the queue information configured with the user information and corresponding to the specific service;
a bandwidth allocation module 302, configured to receive the queue information from the queue element configuration module 301, allocate bandwidth to a user corresponding to an element in the queue according to a specific service corresponding to the queue and user information in the queue, and output bandwidth allocation information.
The bandwidth allocation module 302 may further include: the system comprises a receiving module and a first distribution module; wherein,
the receiving module is used for receiving the queue information from the queue element configuration module and transmitting the queue information to the first distribution module;
and the first allocation module is used for receiving the queue information, allocating corresponding bandwidth to the user corresponding to each element in the queue according to the bandwidth parameter of the specific service corresponding to the queue, and outputting the user information as bandwidth allocation information according to the corresponding rate of the bandwidth.
The first distribution module may specifically include:
a queue bandwidth allocation module and a user bandwidth allocation module; wherein,
the queue bandwidth allocation module is used for allocating bandwidth to the queue according to the product of the bandwidth parameter of the specific service corresponding to the user in the queue and the number of elements in the queue, and transmitting the information of the user identifier to the user bandwidth allocation module according to the corresponding rate of the bandwidth;
and the user bandwidth allocation module is used for receiving the information from the queue bandwidth allocation module, scheduling the user information corresponding to the information out of the queue, allocating the bandwidth allocated to the queue to the users in the queue, and outputting the user information as bandwidth allocation information according to the corresponding rate of the bandwidth divided by the users.
The bandwidth allocation module 302 further comprises: a second allocation module and/or a third allocation module; wherein,
a second allocation module, configured to receive the user identifier of the first allocation module, determine whether the user in the queue has data to be sent, if so, reserve a bandwidth allocated to the user, and output user identifier information according to a rate corresponding to the bandwidth; otherwise, releasing the bandwidth allocated to the user; the judgment can be realized based on a preset valid data identifier;
and the third allocation module is used for receiving the user identification from the first allocation module or the second allocation module, adding the bandwidths allocated to the same user in each queue, limiting the sum of the obtained bandwidths within a preset threshold value, and then outputting the user identification according to the rate corresponding to the total bandwidth to be allocated to the user.
The traffic scheduling apparatus according to the embodiment of the present invention may further include, based on the structure shown in fig. 3, a data processing unit:
and the queue scheduling module is used for receiving the information from the bandwidth allocation module, allocating higher priority to the queue corresponding to the service type with higher real-time performance according to the service type to which the information flow belongs, and preferentially outputting the scheduling result of the queue with higher priority according to the priority.
The following describes the traffic scheduling scheme according to the embodiment of the present invention in detail with reference to two embodiments.
The scheduling object of the embodiment of the invention is not actual data, but individual user IDs forming a queue, so the obtained scheduling result is also the user ID, and after receiving the user ID, the subsequent data sending unit sends out a data unit with a certain length of the user, which is also the reason why the scheduling object of the embodiment of the invention is not actual data but provides the opportunity of sending data for the user once. Therefore, the number of times of sending the same user ID in unit time can be determined, and on the contrary, if the user knows the number of times of sending the data, the embodiment of the invention allocates the actual bandwidth to the user, and the actual bandwidth is reflected by providing the opportunity of sending the data for the user for many times.
Example 1:
referring to fig. 4, fig. 4 is a schematic diagram of performing traffic scheduling based on specific services in embodiment 1 of the present invention. The traffic scheduling of this embodiment is three-level scheduling, and reference factors of the scheduling are user and specific service, total queue bandwidth, and queue priority, respectively. Since the five-stage scheduling of the subsequent embodiment 2 is performed by adding two-stage scheduling to the three-stage scheduling of the embodiment 1, the numbers of the scheduling stages in the embodiment 1 having the same reference factors as those in the embodiment 2 are also the same in order to correspond to the embodiment 2. In this embodiment, setting the information flow provided by the operator includes: the system comprises a video stream, an audio stream and a data stream, wherein the specific services of the video stream comprise: 1Mb/s, 2Mb/s and 4 Mb/s; specific services of the audio stream include: 64 kbytes/sec (b/s), 128kb/s and 256 kb/s; specific services of the data stream include: 256kb/s, 1Mb/s and 10 Mb/s. Next, the scheduling of each stage of the present embodiment will be explained in order.
And fifth-stage scheduling:
in this stage of scheduling, to implement the traffic scheduling according to the embodiment of the present invention, queues need to be divided based on specific services. The process of dividing the queue may be: firstly, classifying information streams which are possibly received according to the service types of the information streams on the network provided by the current operator, wherein the information streams can be divided into video streams, audio streams and data streams; then, according to the specific services provided by the operator for each class of services, 9 queues shown in fig. 4 are divided; then, the user ID information for customizing each specific service is used as an element in the corresponding queue, and is configured in the queue according to the number, referring to fig. 5, the relevant user ID information is discharged in each queue, which is different from the message data information discharged in the queue of the existing traffic scheduling scheme.
The reference factors for the fifth level scheduling are the users and the specific services. In this level of scheduling, since the users in each queue purchase the same specific service, the user priorities corresponding to the elements constituting the queue in each queue may be the same, and the maximum bandwidths to be divided may also be the same, that is, the chances of sending data by the users corresponding to each element in one queue are equal. The maximum bandwidth is the rate of the specific service corresponding to the queue.
In addition, if the user is a guest-class user, a queue can be separately created for the user, and the queue can be configured according to the above-mentioned related description.
Fourth-level scheduling:
the reference factor for this level of scheduling is the total bandwidth of the queue. Specifically, in the level scheduling, a principle of configuring the scheduling parameter for each queue may be that the total bandwidth allocated to the queue is a product of the number of elements in the queue and a maximum bandwidth that can be allocated to a user corresponding to each element. Thus, in this level of scheduling, the total bandwidth allocated for each queue may be the maximum bandwidth that the queue can be allocated to. Considering that the sum of the total bandwidths allocated to all queues may exceed the bandwidth of the output port, when scheduling, a weight of the bandwidth may be allocated to each queue, that is, if the port bandwidth is 10M and the sum of the total bandwidths allocated to all queues is 20M, the total bandwidth of a certain queue calculated according to the principle of configuring the scheduling parameter is set to be 2M, and the corresponding weight when allocating the bandwidth to the queue is 0.5, so that the bandwidth actually obtained by the queue is 1M, thereby ensuring fairness of scheduling. When the scheduling is implemented, i.e. the scheduling result is calculated, different scheduling algorithms may be used for different service types. For example, for audio service, the existing SHVC algorithm may be used to calculate the scheduling result; for video service or data service, the existing WFQ algorithm or WRR algorithm can be selected to calculate the scheduling result according to the actual situation. The bandwidth allocated to a certain queue is represented by how many times of opportunities to send data are provided for users in the queue, or how many times of user IDs are sent in unit time, the user ID at the position is not limited to which one or more of the queues, and since the priorities of all users in the same queue are the same, the probability that the user corresponding to each element obtains the opportunities is equal, correspondingly, the fourth-stage scheduling result is the user identifier sent at the rate corresponding to the total bandwidth allocated to each queue, so that the corresponding rate refers to knowing the total bandwidth allocated to the queue, and based on the length of data sent by the user each time, how many user IDs are sent in unit time can be known.
Further, the fifth-level scheduling may be performed on the basis of the fourth-level scheduling, and after the fourth-level scheduling allocates the total bandwidth to each queue, the fifth-level scheduling uses a round-robin (RR) mechanism to averagely allocate the total bandwidth allocated to the queue to each user in the queue. This average allocation of bandwidth to each user is reflected in: determining the number of times of sending data in unit time by all users in the queue according to the total bandwidth of the queue; and proportionally distributing the times of sending the data to users corresponding to the elements in the queue. That is, the number of times that the queue sends the user ID in the unit time is equally distributed to the users corresponding to each element, for example, the number of the user IDs that can be sent in the unit time of the queue is 1 ten thousand, and there are 1 thousand users in the queue, so each user has 10 opportunities to send data in the unit time, accordingly, the fifth-level scheduling result is the user ID that is output at the rate corresponding to the bandwidth allocated to each user, and the explanation of the corresponding rate is similar to the related content above. The fourth level scheduling and the fifth level scheduling can be realized interactively.
It should be noted that, if the operator provides more specific services and the rate relationship between some specific services may be a multiple relationship, such as the above specific services corresponding to the video stream, the rate of 2Mb/s specific services is obviously 2 times the rate of 1Mb/s specific services, and the number of users actually purchasing specific services with higher rate is less, in this case, to avoid too many queues being divided and reduce resources for re-opening one queue, the method may be adopted: in a queue corresponding to 1Mb/s specific service, configuring the user ID for purchasing 2Mb/s specific service to two elements in the queue, that is, two identical elements may appear in one queue, specifically, allocating two numbers to the user, and configuring the user ID information to positions in the queue corresponding to the two allocated numbers respectively; then, when the fifth-level scheduling allocates bandwidth to each element round robin in each queue, the user purchasing the higher-rate service can be allocated to the bandwidth corresponding to the queue twice, so that the bandwidth allocated to the user is guaranteed to be the bandwidth purchased by the user, the number of queues is reduced, and further, the circuit resource for realizing scheduling is saved.
The description of the fifth and fourth level scheduling can be found so far.
First-stage scheduling:
the reference factor of the level scheduling is the service priority, and the purpose of the level scheduling is to assign a higher priority to a queue with higher real-time requirement according to the real-time requirements of different service types.
Based on the scheduling result of the fourth-level scheduling, the first-level scheduling further allocates a higher priority to the queue corresponding to the audio service with higher real-time requirement, so that the user in the queue with higher priority can obtain better service quality under the condition of ensuring the bandwidth of each queue, that is, the scheduling result of the queue with higher priority is output, and the scheduling result is also a certain user ID.
When the scheduling of the stage is specifically implemented, the existing SP scheduling algorithm can be adopted to calculate the scheduling result, namely, the priority is distributed to each queue based on the service characteristics.
The description of the first level scheduling can be found in the opening paragraph.
Example 2:
referring to fig. 6, fig. 6 is a schematic diagram of traffic scheduling performed in embodiment 2 of the present invention. In order to provide better scheduling performance and parameters, the embodiment is based on the embodiment shown in fig. 4, and based on the above three-level scheduling, a third-level scheduling and a second-level scheduling are added to form an optimization scheme of five-level scheduling. Since the fifth-level, fourth-level and first-level schedules shown in fig. 5 are the same as the schedules with the same number of levels shown in fig. 3, further description is omitted, and the third-level and second-level schedules shown in fig. 6 are mainly described in detail.
And (3) third-level scheduling:
the reference factor for this level of scheduling is the user's valid data. As can be seen from the above description about the fourth-level scheduling, the scheduling result of the fourth-level scheduling is the user identifier sent according to the rate corresponding to the total bandwidth allocated to each queue, so as to provide the opportunity for sending data to the user, without considering whether the user actually uses the allocated bandwidth, i.e., whether the user's valid data exists, for example, the user purchases a certain telephone service. The third level scheduling is used to release the unoccupied bandwidth resources of the allocated users, or to discard the opportunity of transmitting data provided to the users not using the service. In specific implementation, a valid data identifier may be preconfigured, that is, an information amount of one bit (bit) is used to indicate whether a user has valid data to be sent, if the valid data indicates that the user has valid data, bandwidth allocated to the user is reserved, that is, the user ID is output, and if the valid data does not indicate that the user does not have valid data, bandwidth resources allocated to the user are released, that is, the opportunity of the user to send data this time is discarded, so that a plurality of users can share bandwidth resources.
And (3) second-level scheduling:
reference factor users for this level of scheduling. A user may customize a plurality of specific services, and the scheduling of this stage is to limit the total bandwidth allocated to a user to a predetermined threshold, which may be the bandwidth actually customized by the user or the bandwidth configured by the operator for the user. Since the bandwidth allocated to each element in each queue by the fourth-level scheduling is the bandwidth of the corresponding specific service, that is, the maximum bandwidth that can be obtained by the user who customizes the specific service, if a user customizes a plurality of specific services, in the scheduling result of the fourth or fifth level, if the bandwidths allocated to the user in the queues are added together, it is likely that the sum of the obtained bandwidths exceeds the bandwidth actually customized by the user, and the sum of the bandwidths obtained by the user can be limited by the second-level scheduling, which may be specifically: pre-configuring total bandwidth parameter information purchased by a user; calculating the total bandwidth divided by the same user based on the user ID information in each queue; comparing the total bandwidth divided by the user with the pre-configured total bandwidth parameter information, if the former is greater than the latter, reducing the total bandwidth allocated to the user according to the queue bandwidth weight corresponding to each specific service customized by the user.
Another effect of the second-level scheduling is to perform traffic shaping on the basis of the fourth or third-level scheduling result, i.e. to make the rate at which the user sends the information flow conform to the traffic flow model. The scheduling of the stage can be realized by adopting the existing GCRA algorithm, and the specific method can be as follows: configuring a set of independent traffic parameters in advance based on specific services customized by each user so as to perform traffic shaping independently for each user, wherein the traffic parameters may include: average speed, maximum possible speed, etc. of the specific service; then, the maximum rate of the flow parameter is used as the bucket depth, and the available tokens for sending the data at this time are calculated by combining the time scale sent last time, if the number of the tokens is enough to send a unit data, the opportunity for sending the data by the user at this time can be output, and if the number of the tokens is not enough to send a unit data, the opportunity for sending the data by the user at this time is discarded; and then, taking the average rate of specific services as the bucket depth, calculating the available token number in combination with the time scale of the last data transmission, if the token number is enough to transmit one unit of data, outputting the opportunity of the user for transmitting the data, namely indicating a data transmission unit to transmit actual data, and if the token number is not enough to transmit one unit of data, discarding the opportunity of the user for transmitting the data. Through the GCRA algorithm operation, the data transmission rate of the user can be well adjusted, so that the data transmission rate is smooth as much as possible. Therefore, through the second-stage scheduling, the fairness of bandwidth allocation in the fourth-stage scheduling can be ensured, and the sharing of bandwidth resources among users is realized. In addition, since the operator generally performs bandwidth planning on the network according to the number of users, the basic performance of sending data of each port of the device can be ensured under the condition that each user is guaranteed to be allocated with an appropriate bandwidth.
The description of the second level scheduling is as far as this paragraph.
In addition, the third-level scheduling can be arranged after the fourth-level scheduling or the second-level scheduling, and the third-level scheduling is used for filtering out the opportunity of invalid users for sending data, so that the subsequent information transmission quantity can be reduced, the operation efficiency of the circuit is improved, and the performance requirement of the circuit corresponding to the second-level scheduling is effectively reduced after the fourth-level scheduling. It should be noted that if the user ID without valid data is removed from the queue during the fifth-level scheduling, the scheduling may still need to be performed according to the monitoring result of whether the user has valid data, which is not necessarily simple compared to the above-mentioned method of configuring the user ID for customizing a specific service into the queue. Therefore, in practical applications, it is recommended to perform the third-level scheduling after the fourth or second-level scheduling.
In order to make the rate of sending data more uniform, even though the traffic shaping effect is better, in practical application, a level of port-based traffic shaping may be added, and a mature prior art may be adopted for the port-based traffic shaping, which is not described herein again.
To sum up, the traffic scheduling method and apparatus provided in the embodiments of the present invention divide a queue according to a specific service provided by an operator, use user information for customizing the specific service corresponding to the queue as an element constituting the queue, and perform traffic scheduling based on the user information in the queue and the corresponding specific service, because the type of the specific service provided by the operator is limited and the bandwidth of the specific service is usually fixed, the number of queues that can be divided is not too large, and because the number of users in one queue and the parameters such as the bandwidth of the specific service are predictable, when performing traffic scheduling, the bandwidth can be allocated to the user identified by the user information in the queue only according to the bandwidth of the specific service corresponding to the queue, compared with the existing traffic scheduling scheme that flow classification needs to be performed according to actual data that is difficult to predict, and then, by searching for the bandwidth allocated by the relevant traffic parameter, the traffic scheduling scheme of the embodiment of the invention is easier to realize. Moreover, because the traffic scheduling is performed based on the specific service, and the operator performs configuration based on the specific service and the user who customizes the specific service during network planning, the traffic scheduling policy of the embodiment of the present invention can correspond to the relevant configuration of the operator during network planning, so that the scheduling result can better satisfy the network requirement. Therefore, by adopting the flow scheduling scheme of the embodiment of the invention, the scheduling result can meet the network requirement, the circuit complexity of flow scheduling can be effectively simplified, the software configuration management work can be scheduled, the error probability of scheduling data is reduced, and the scheduling efficiency is improved.
Furthermore, the traffic scheduling policy of the embodiment of the present invention can correspond to the relevant configuration of the operator during network planning, so that the configuration of the software parameters for traffic scheduling can be more convenient.
In addition, because the traffic scheduling policy of the embodiment of the present invention does not relate to actual data, and the scheduling is performed based on predictable user parameters and bandwidth parameters of specific services, the obtained scheduling result is actually to provide an opportunity for a user to send data, and the opportunity for sending data is transmitted to the data sending unit, and the data sending unit is instructed to send data according to the scheduling result, that is, according to information such as a certain rate and priority, in principle, the traffic scheduling policy of the embodiment of the present invention is adopted, so that the data loss or data sending error caused by a scheduling error is avoided, and therefore, the reliability and accuracy of data transmission can be effectively ensured, and the service quality is provided.
Claims (18)
1. A traffic scheduling method, comprising:
configuring user information corresponding to specific services in the service types to which the information flows belong as queue elements into queues corresponding to the specific services, wherein one queue corresponds to one specific service;
allocating bandwidth to the user corresponding to the element in the queue according to the specific service corresponding to the queue and the user information in the queue; the allocation of bandwidth to the users is embodied by the number of times of opportunities to send data provided to the users corresponding to the elements in the queue in a unit time.
2. The method of claim 1, wherein the user information is user Identification (ID) information.
3. The method according to claim 1 or 2, wherein the step of configuring the user information corresponding to the specific service in the service type to which the information flow belongs as a queue element into the queue corresponding to the specific service comprises:
and configuring one or more pieces of user information into the queue as each element of the queue.
4. The method of claim 3, wherein the step of configuring one or more of the user information into the queue as elements of the queue comprises:
and configuring the same user information to at least two elements in the queue.
5. The method according to claim 1 or 2, wherein the step of allocating bandwidth to the user corresponding to the element in the queue comprises:
and distributing corresponding bandwidth for the user corresponding to each element in the queue according to the bandwidth parameter of the specific service corresponding to the queue.
6. The method of claim 5, wherein the step of allocating the corresponding bandwidth to the user corresponding to each element in the queue comprises:
multiplying the bandwidth parameter of the specific service corresponding to the queue by the number of elements in the queue to obtain the total bandwidth allocated to the queue;
and proportionally distributing the total bandwidth to users corresponding to each element in the queue.
7. The method of claim 6, wherein the step of proportionally allocating the total bandwidth allocated to the queue to the users corresponding to the elements in the queue comprises:
averagely distributing the total bandwidth distributed to the queue to users corresponding to each element in the queue;
or, the total bandwidth is multiplied by the bandwidth obtained by the corresponding weight when the bandwidth is allocated to the queue, and the bandwidth is averagely allocated to the user corresponding to each element in the queue.
8. The method according to claim 6, wherein the step of proportionally allocating the total bandwidth to the users respectively corresponding to the elements in the queue specifically comprises:
determining the number of times of sending data in unit time by all users in the queue according to the total bandwidth; and proportionally distributing the times of sending the data to users corresponding to the elements in the queue.
9. The method of claim 5, wherein the step of allocating bandwidth to the user corresponding to the element in the queue further comprises:
judging whether the user has data to be sent, if so, reserving the bandwidth allocated to the user; otherwise, the bandwidth allocated to the user is released.
10. The method of claim 5, wherein the step of allocating bandwidth to the user corresponding to the element in the queue further comprises:
if the same user information exists in a plurality of queues, the bandwidths allocated to the user in each queue are added, and the sum of the obtained bandwidths is limited within a preset threshold value.
11. The method of claim 5, wherein after allocating the corresponding bandwidth to the user corresponding to each element in the queue, the method further comprises:
and carrying out flow shaping processing according to the specific service.
12. The method of claim 1, wherein after allocating bandwidth to the user corresponding to the element in the queue, the method further comprises:
and according to the service type of the information flow, distributing higher priority to the queue corresponding to the service type with higher real-time performance.
13. A traffic scheduling apparatus, comprising: the device comprises a queue element configuration module and a bandwidth allocation module; wherein,
the queue element configuration module is used for configuring user information corresponding to specific services in the service types to which the information flow belongs as queue elements into queues corresponding to the specific services and outputting the queue information which is configured with the user information and corresponds to the specific services;
the bandwidth allocation module is used for receiving the queue information from the queue element configuration module, allocating bandwidth to the user corresponding to the element in the queue according to the specific service corresponding to the queue and the user information in the queue, and outputting the bandwidth allocation information; the allocation of bandwidth to the users is embodied by the number of times of opportunities to send data provided to the users corresponding to the elements in the queue in a unit time.
14. The apparatus of claim 13, wherein the bandwidth allocation module comprises: the system comprises a receiving module and a first distribution module; wherein,
the receiving module is used for receiving the queue information from the queue element configuration module and transmitting the queue information to the first distribution module;
the first allocation module is used for receiving the queue information, allocating corresponding bandwidth to the user corresponding to each element in the queue according to the bandwidth parameter of the specific service corresponding to the queue, and outputting the user information as bandwidth allocation information according to the corresponding rate of the bandwidth;
the user information is a user identifier.
15. The apparatus of claim 14, wherein the first distribution module comprises:
a queue bandwidth allocation module and a user bandwidth allocation module; wherein,
the queue bandwidth allocation module is used for allocating bandwidth for the queue according to the product of the bandwidth parameter of the specific service corresponding to the user in the queue and the number of elements in the queue, and transmitting the information of the user identifier to the user bandwidth allocation module according to the corresponding rate of the bandwidth;
and the user bandwidth allocation module is used for receiving the information from the queue bandwidth allocation module, scheduling the user information corresponding to the information out of the queue, allocating the bandwidth allocated to the queue to the user corresponding to each element in the queue, and outputting the user information as bandwidth allocation information according to the corresponding rate of the bandwidth allocated by the user.
16. The apparatus of claim 14, wherein the bandwidth allocation module further comprises:
the second distribution module is used for receiving the user identification output by the first distribution module, judging whether the user in the queue has data to be sent or not, if so, reserving the bandwidth distributed to the user, and outputting user identification information according to the corresponding rate of the bandwidth; otherwise, the bandwidth allocated to the user is released.
17. The apparatus of claim 16, wherein the bandwidth allocation module further comprises:
and a third allocation module, configured to receive the user identifier from the first allocation module or the second allocation module, add bandwidths allocated to the same user in each queue, limit the sum of obtained bandwidths within a preset threshold, and output the user identifier at a rate corresponding to a total bandwidth allocated to the user.
18. The apparatus of claim 13, further comprising:
and the queue scheduling module is used for receiving the bandwidth allocation information from the bandwidth allocation module, allocating higher priority to the queue corresponding to the service type with higher real-time performance according to the service type of the information stream, and preferentially outputting the scheduling result of the queue with higher priority according to the priority.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN200710003485XA CN101009655B (en) | 2007-02-05 | 2007-02-05 | Traffic scheduling method and device |
| PCT/CN2007/071409 WO2008095397A1 (en) | 2007-02-05 | 2007-12-29 | Traffic scheduling method and apparatus thereof |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN200710003485XA CN101009655B (en) | 2007-02-05 | 2007-02-05 | Traffic scheduling method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101009655A CN101009655A (en) | 2007-08-01 |
| CN101009655B true CN101009655B (en) | 2011-04-20 |
Family
ID=38697796
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN200710003485XA Active CN101009655B (en) | 2007-02-05 | 2007-02-05 | Traffic scheduling method and device |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN101009655B (en) |
| WO (1) | WO2008095397A1 (en) |
Families Citing this family (23)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101009655B (en) * | 2007-02-05 | 2011-04-20 | 华为技术有限公司 | Traffic scheduling method and device |
| CN101772083A (en) * | 2008-12-30 | 2010-07-07 | 华为技术有限公司 | Method, device and system for allocating bandwidth |
| CN101499973B (en) * | 2009-03-11 | 2012-05-23 | 中兴通讯股份有限公司 | Method for realizing full-line speed dispatching service flow by switch |
| CN102137464B (en) * | 2010-01-25 | 2014-09-10 | 中兴通讯股份有限公司 | Base station system and transmitting method of Abis port data thereof |
| CN102300261B (en) * | 2010-06-25 | 2014-02-12 | 普天信息技术研究院有限公司 | Method for carrying out capacity assignment on HS-DSCH (high-speed downlink shared channel) |
| CN103024456B (en) | 2011-09-27 | 2016-02-24 | 腾讯科技（深圳）有限公司 | A kind of Online Video player method and video playback server |
| CN103379038B (en) | 2012-04-12 | 2018-08-03 | 南京中兴新软件有限责任公司 | A kind of device and method of flow scheduling |
| US8804523B2 (en) * | 2012-06-21 | 2014-08-12 | Microsoft Corporation | Ensuring predictable and quantifiable networking performance |
| CN102857440A (en) * | 2012-08-17 | 2013-01-02 | 杭州华三通信技术有限公司 | Data processing method and switchboard |
| CN103023812B (en) * | 2012-11-23 | 2018-07-31 | 上海寰创通信科技股份有限公司 | A kind of multi-user's balanced bandwidth configuration method |
| CN103037415B (en) * | 2012-12-12 | 2016-07-06 | 深信服网络科技（深圳）有限公司 | Network analysis method and system |
| US20140226571A1 (en) * | 2013-02-13 | 2014-08-14 | Qualcomm Incorporated | Apparatus and method for enhanced application coexistence on an access terminal in a wireless communication system |
| CN105159781B (en) * | 2015-08-25 | 2018-11-27 | 广东欧珀移动通信有限公司 | Adjust the method, apparatus and intelligent terminal of intelligent terminal application network speed |
| CN105591970A (en) * | 2015-08-31 | 2016-05-18 | 杭州华三通信技术有限公司 | Traffic control method and device |
| CN107404454B (en) * | 2016-05-18 | 2021-08-03 | 中国移动通信集团广东有限公司 | Call quality adjusting method and device |
| CN108243119B (en) * | 2016-12-26 | 2023-07-11 | 中兴通讯股份有限公司 | Scheduling method and device for improving RB resource utilization rate |
| CN110868357B (en) * | 2018-08-27 | 2024-09-13 | 南京中兴新软件有限责任公司 | Network flow control method, VTEP device and storage medium |
| CN109246023A (en) * | 2018-11-16 | 2019-01-18 | 锐捷网络股份有限公司 | Flow control methods, the network equipment and storage medium |
| WO2020248166A1 (en) * | 2019-06-12 | 2020-12-17 | 华为技术有限公司 | Traffic scheduling method, device, and storage medium |
| CN111565323B (en) * | 2020-03-23 | 2022-11-08 | 视联动力信息技术股份有限公司 | Flow control method and device, electronic equipment and storage medium |
| CN111491015B (en) * | 2020-03-31 | 2022-11-11 | 北京金山云网络技术有限公司 | Preheating task processing method and system, proxy server and service center |
| CN111970544B (en) * | 2020-08-31 | 2022-10-18 | 咪咕视讯科技有限公司 | Downlink flow scheduling policy adjusting method, server and readable storage medium |
| CN114268590B (en) * | 2021-11-24 | 2024-04-30 | 成都安恒信息技术有限公司 | System and method for guaranteeing bandwidth based on VPP |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1422475A (en) * | 2000-02-08 | 2003-06-04 | 天然网络技术有限公司 | Multi-level scheduling method for multiplexing packets in a communications network |
| CN1490993A (en) * | 2003-09-15 | 2004-04-21 | 北京港湾网络有限公司 | Multiservice system realizing method for broadband network cut-in apparatus user |
| CN1524395A (en) * | 2001-05-26 | 2004-08-25 | ���ſ������˾ | Method and apparatus for communications bandwidth allocation |
| US6917590B1 (en) * | 1998-11-13 | 2005-07-12 | Sprint Communications Company L.P. | Method and system for connection admission control |
| CN1842019A (en) * | 2005-03-28 | 2006-10-04 | 华为技术有限公司 | Dynamic control method for service bandwidth |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1501592A (en) * | 2002-11-19 | 2004-06-02 | 电子科技大学 | A novel multiple access method for communication technology |
| ES2229917B1 (en) * | 2003-07-15 | 2006-07-01 | Diseño De Sistemas En Silicio, S.A. | PROCEDURE OF DYNAMIC MANAGEMENT OF RESOURCES OF TELECOMMUNICATIONS SYSTEMS IN FUNCTION OF SERVICE QUALITY AND TYPE OF SERVICE. |
| US7733780B2 (en) * | 2005-12-07 | 2010-06-08 | Electronics And Telecommunications Research Institute | Method for managing service bandwidth by customer port and EPON system using the same |
| CN101009655B (en) * | 2007-02-05 | 2011-04-20 | 华为技术有限公司 | Traffic scheduling method and device |
-
2007
- 2007-02-05 CN CN200710003485XA patent/CN101009655B/en active Active
- 2007-12-29 WO PCT/CN2007/071409 patent/WO2008095397A1/en active Application Filing
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6917590B1 (en) * | 1998-11-13 | 2005-07-12 | Sprint Communications Company L.P. | Method and system for connection admission control |
| CN1422475A (en) * | 2000-02-08 | 2003-06-04 | 天然网络技术有限公司 | Multi-level scheduling method for multiplexing packets in a communications network |
| CN1524395A (en) * | 2001-05-26 | 2004-08-25 | ���ſ������˾ | Method and apparatus for communications bandwidth allocation |
| CN1490993A (en) * | 2003-09-15 | 2004-04-21 | 北京港湾网络有限公司 | Multiservice system realizing method for broadband network cut-in apparatus user |
| CN1842019A (en) * | 2005-03-28 | 2006-10-04 | 华为技术有限公司 | Dynamic control method for service bandwidth |
Non-Patent Citations (1)
| Title |
|---|
| 全文. |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2008095397A1 (en) | 2008-08-14 |
| CN101009655A (en) | 2007-08-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101009655B (en) | Traffic scheduling method and device | |
| EP3471341B1 (en) | Network slice method and system | |
| KR100608904B1 (en) | System and method for providing quality of service in ip network | |
| CN110912736B (en) | Resource allocation method and device | |
| WO2017157274A1 (en) | Network-traffic control method and network device thereof | |
| CN104378309B (en) | Method, system and the relevant device of QoS are realized in OpenFlow network | |
| CN101964758A (en) | Differentiated service-based queue scheduling method | |
| EP2302843A1 (en) | Method and device for packet scheduling | |
| CN104348751B (en) | Virtual output queue authorization management method and device | |
| JP4163044B2 (en) | BAND CONTROL METHOD AND BAND CONTROL DEVICE THEREOF | |
| Homg et al. | An adaptive approach to weighted fair queue with QoS enhanced on IP network | |
| US11929911B2 (en) | Shaping outgoing traffic of network packets in a network management system | |
| CN102845032A (en) | System and method for dynamically adjusting quality of service configuration based on real-time traffic | |
| JP6569374B2 (en) | Switch device and control method of switch device | |
| CN105700940B (en) | A kind of statistical multiplex method of scheduler and scheduler | |
| CN105915468B (en) | A kind of dispatching method and device of business | |
| Rukmani et al. | Scheduling algorithm for real time applications in mobile ad hoc network with opnet modeler | |
| CN107846341A (en) | Method, relevant apparatus and the system of schedules message | |
| CN103858474A (en) | Enhanced performance service-based profiling for transport networks | |
| CN102769566B (en) | A kind of Multi-stage scheduling system configuration, variation and device | |
| US8467401B1 (en) | Scheduling variable length packets | |
| KR20120055947A (en) | Method and apparatus for providing Susbscriber-aware per flow | |
| US20090073878A1 (en) | Usage based queuing with accounting for wireless access points | |
| CN113810305B (en) | Message forwarding method, device, forwarding node and computer readable storage medium | |
| KR101587379B1 (en) | Method of dynamic control for queue size and apparatus thereof |
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 |