Method and apparatus for implementing round robin scheduling

摘要

A method and an apparatus for implementing round robin scheduling are provided. The method includes: acquiring, from a queue, original location information of elements in the queue; performing location mapping processing on the original location information of the elements in the queue based on a set algorithm to obtain mapped location information of the elements in the queue, where the set algorithm or parameters used by the set algorithm change according to a set rule during each time of round robin scheduling; and starting from an element corresponding to a set initial location, performing round robin scheduling according to mapped queue sequences corresponding to the mapped location information of the elements. The method and the apparatus for implementing round robin scheduling can reduce the cost of storage devices and can ensure a balance in scheduling of elements in a service queue.

主权项

1. A method for implementing round robin scheduling performed by a network element, comprising:
acquiring, from a queue and by the network element, respective original location information of elements in the queue; performing location mapping processing by the network element on the respective original location information of the elements in the queue based on a set algorithm to obtain respective mapped location information of the elements in the queue, wherein the set algorithm or parameters used by the set algorithm change according to a set rule during each time of round robin scheduling; starting from an element corresponding to a set initial location, performing the round robin scheduling by the network element according to mapped queue sequences corresponding to the respective mapped location information of the elements; and routing data by the network element according to the round robin scheduling, wherein performing the location mapping processing on the respective original location information of the elements in the queue comprises: performing a calculation according to the respective original location information of the elements in the queue by using a random algorithm by the network element, to obtain respective mapped locations corresponding to respective original locations, wherein the respective mapped locations are used as the respective mapped location information of the elements in the queue, wherein performing the calculation according to the respective original location information of the elements in the queue comprises: selecting a random value of round robin scheduling according to the set rule by the network element, wherein the random value has a value range of 0 to (2n−1), and 2n is a quantity of the elements in the queue; calculating respective temporary locations of the elements in the queue according to the random value and the respective original locations of the elements in the queue, by the network element, wherein a calculation formula is:
a_tmp_loc=a_ori_loc +random wherein, random is the random value, a _ori_loc is an original location of a queue element, and a_tmp_loc is a temporary location of the queue element; removing the most significant bit in a binary number of the temporary location, with n bits left; and reversing the n-bit binary number of the temporary location of the queue element, to obtain a mapped location of the queue element.