Preemptive weighted round robin scheduler

• US 7,430,207 B2
• Filed: 04/19/2005
• Issued: 09/30/2008
• Est. Priority Date: 02/07/2005
• Status: Expired due to Fees

• Current Assignee: Reti Corp.
• Original Assignee: Reti Corp.
• Inventors: Wang, Lan-Feng, Wu, Chiutien
• Primary Examiner(s): Vu; Huy D.
• Assistant Examiner(s): KHAN, SHAFIQUL H
• Application Number:
  US11/108,777
• Publication Number:
  US 20060176807A1
• Time in Patent Office: 1,260 Days
• Field of Search: 370/395, 370/229, 370/351, 370/235.1, 370/395.41, 370/395.42
• US Class Current: 370/395.41
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin

Abstract

The present invention is to disclose a scheduler which comprising a priority tagging module for receiving a plurality of information chucks, a plurality of output lines, and a WRR (weighted round robin) module. In this regards, each information chucks are tagged with a priority tag by said priority tagging module according to a priority classification scheme. In addition, the WRR module further comprises a bucket list, which has a plurality of buckets, and a control module. Each bucket stores a ticket, which comprises an identification representing one of the plurality of output lines and an associated weight value of the represented output line. Besides, the control module receives the tagged information chucks from the priority tagging module and schedules the tagged information chucks into the plurality of output lines according to a scheduling scheme based on said bucket list.

Claims

1. A scheduler, comprising:

a priority tagging module for receiving a plurality of information chucks, wherein each information chucks are tagged with a priority tag by said priority tagging module according to a priority classification scheme;

a plurality of output lines; and

a WRR (weighted round robin) module, further comprising;

a bucket list, wherein said bucket list comprises a plurality of buckets, each bucket stores a ticket, said ticket comprises an identification, represented one of said plurality of output lines, and an associated weight value of said represented output line; and

a control module, wherein said control module receives said tagged information chucks from said priority tagging module and schedules said tagged information chucks into said plurality of output lines according to a scheduling scheme based on said bucket list.

2. A scheduler of claim 1, wherein said priority classification scheme is a combination of a pre-determination scheme and a random determination scheme.

3. A scheduler of claim 2, wherein said information chuck is classified into a plurality of priority classes by a property of said information chuck in said pre-determination scheme.

4. A scheduler of claim 2, wherein said information chuck is classified into a plurality of priority classes by a random in a given probability in said random determination scheme.

5. A scheduler of claim 1, wherein said plurality of output lines comprise first-in first-out queue structures.

6. A scheduler of claim 1, wherein said scheduling scheme based on said bucket list further comprising:

a) choosing a chuck with a high priority tag;

b) masking out other low priority tagged chucks;

c) performing at least one procedure on a target bucket of said bucket list, wherein said procedure comprising;

c1) determining that whether any chucks waited in an associated output line, represented by the identification of said ticket stored in said target bucket;

c2) sending said waited chuck to said associated output line and determining that whether said weight value of said ticket stored in said target bucket is greater than zero when said c1 step is determined true;

c3) decreasing said weight value of said ticket stored in said target bucket when said weight value is determined greater than zero in said c2 step; and

c4) reloading said weight value of said ticket with an initial weight value associated with said output line and shift said ticket stored in said target bucket to the bottom bucket of said bucket list; and

d) repeating said c step by assigning a next bucket of said target bucket as new said target bucket when said c1 step is not determined true.

7. A scheduler, comprising:

a priority tagging module for receiving a plurality of information chucks, wherein each information chucks are tagged with a priority tag by said priority tagging module according to a priority classification scheme;

a plurality of output lines; and

a WRR (weighted round robin) module, further comprising;

a bucket list, wherein said bucket list comprises a plurality of buckets, each bucket stores a ticket, said ticket comprises an identification, represented one of said plurality of output lines, and an associated weight value of said represented output line; and

a control module, wherein said control module receives said tagged information chucks from said priority tagging module and schedules said tagged information chucks into said plurality of output lines according to a scheduling scheme based on said bucket list, wherein said scheduling scheme based on said bucket list further comprising;

a) choosing a chuck with a high priority tag;

b) masking out other low priority tagged chucks;

c) performing at least one procedure on a target bucket of said bucket list, wherein said procedure comprising;

c1) determining that whether any chucks waited in an associated output line, represented by the identification of said ticket stored in said target bucket;

c2) sending said waited chuck to said associated output line and determining that whether said weight value of said ticket stored in said target bucket is greater than zero when said c1 step is determined true;

c3) decreasing said weight value of said ticket stored in said target bucket when said weight value is determined greater than zero in said c2 step; and

c4) reloading said weight value of said ticket with an initial weight value associated with said output line and shift said ticket stored in said target bucket to the bottom bucket of said bucket list; and

d) repeating said c step by assigning a next bucket of said target bucket as new said target bucket when said c1 step is not determined true.

8. A scheduler of claim 7, wherein said priority classification scheme is a combination of a pre-determination scheme and a random determination scheme.

9. A scheduler of claim 8, wherein said information chuck is classified into a plurality of priority classes by a property of said information chuck in said pre-determination scheme.

10. A scheduler of claim 8, wherein said information chuck is classified into a plurality of priority classes by a random in a given probability in said random determination scheme.

11. A scheduler of claim 7, wherein said plurality of output lines comprise first-in first-out queue structures.

12. A scheduling method, comprising:

providing a scheduler, wherein said scheduler further comprising;

a priority tagging module for receiving a plurality of information chucks, wherein each information chucks are tagged with a priority tag by said priority tagging module according to a priority classification scheme;

a plurality of output lines; and

a WRR (weighted round robin) module, further comprising;

a bucket list, wherein said bucket list comprises a plurality of buckets, each bucket stores a ticket, said ticket comprises an identification, represented one of said plurality of output lines, and an associated weight value of said represented output line; and

a control module, wherein said control module receives said tagged information chucks from said priority tagging module; and

scheduling said tagged information chucks into said plurality of output lines according to a scheduling scheme based on said bucket list, wherein said scheduling scheme based on said bucket list further comprising;

a) choosing a chuck with a high priority tag;

b) masking out other low priority tagged chucks;

c) performing at least one procedure on a target bucket of said bucket list, wherein said procedure comprising;

c1) determining that whether any chucks waited in an associated output line, represented by the identification of said ticket stored in said target bucket;

c2) sending said waited chuck to said associated output line and determining that whether said weight value of said ticket stored in said target bucket is greater than zero when said c1 step is determined true;

c3) decreasing said weight value of said ticket stored in said target bucket when said weight value is determined greater than zero in said c2 step; and

c4) reloading said weight value of said ticket with an initial weight value associated with said output line and shift said ticket stored in said target bucket to the bottom bucket of said bucket list; and

d) repeating said c step by assigning a next bucket of said target bucket as new said target bucket when said c1 step is not determined true.

13. A scheduling method of claim 12, wherein said priority classification scheme is a combination of a pre-determination scheme and a random determination scheme.

14. A scheduling method of claim 13, wherein said information chuck is classified into a plurality of priority classes by a property of said information chuck in said pre-determination scheme.

15. A scheduling method of claim 13, wherein said information chuck is classified into a plurality of priority classes by a random in a given probability in said random determination scheme.

16. A scheduling method of claim 12, wherein said plurality of output lines comprise first-in first-out queue structures.