Preemptive weighted round robin scheduler
First Claim
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 a 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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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 a 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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 a 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. - View Dependent Claims (8, 9, 10, 11)
-
-
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 a 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. - View Dependent Claims (13, 14, 15, 16)
-
Specification