US6011798A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive transmit rate control scheduler
Assignee: Intel Corp
•
Filing: 1997-08-15
•
Granted: 2000-01-04
•
Expires: 2017-08-15
Abstract
Abstract An adaptive rate control scheduler multiplexes virtual circuit data stream elements for transmission onto a network from a network node. The rate control scheduler is an adaptive circuit that utilizes a schedule table (having multiple time windows) and a set of virtual circuit (VC) specific rate control parameters to supply a transmit controller with a stream of tokens (each of which represents an active VC). The order in which tokens are supplied to the transmit controller is based upon their respective time slot locations in the schedule table. Each time a token is processed by the transmit scheduler, a target time for the next processing of the VC represented by the token is calculated, based upon the stored VC-specific parameters. The token is then inserted into the schedule table in the nearest available time slot to the calculated target time. Included in the calculation of the next target time for a particular token is a gain function based upon an accumulated error value for the associated VC. The accumulated error represents error introduced into the VC's data stream by the scheduling process.
Inventors
- 👤 Gary McAlpine
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 19:16
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
154 words
A rate controlled scheduling method in a network node having a transmit controller, a schedule table having a plurality of time windows, each time window including at least one token slot and a priority queue containing at least one token, where each token represents an active virtual circuit (VC), the method comprising the steps of: (A) selecting a first token from the priority queue; (B) sending a copy of the first token to the transmit controller for servicing of the VC represented by the first token; (C) calculating a next target time for servicing of the VC represented by the first token; (D) storing the first token in the schedule table in a time window near the calculated next target time, said time window representing a time period during which a token is expected to be processed; and (E) processing subsequent tokens from the schedule table by transferring said tokens to the priority queue.
Claim 2
Dependent Claim
154 words
A rate controlled scheduling method in a network node having a transmit controller, a schedule table having a plurality of time windows, each time window including at least one token slot and a priority queue containing at least one token, where each token represents an active virtual circuit (VC), the method comprising the steps of: (A) selecting a first token from the priority queue; (B) sending a copy of the first token to the transmit controller for servicing of the VC represented by the first token; (C) calculating a next target time for servicing of the VC represented by the first token; (D) storing the first token in the schedule table in a time window near the calculated next target time, said time window representing a time period during which a token is expected to be processed; and (E) processing subsequent tokens from the schedule table by transferring said tokens to the priority queue.
Claim 3
Dependent Claim
74 words
The method according to claim 1, wherein the node further includes a bitmap having a plurality of bits, each bit having one of a "set" state or a "cleared" state, and wherein a "set" state indicates one or more filled time windows and a "cleared" state indicates one or more unfilled time windows, and wherein the storing step includes traversing the bitmap to find the unfilled time window nearest the calculated next target time.
Claim 4
Dependent Claim
46 words
The method according to claim 1, wherein the virtual circuit represented by the first token has an associated previous target time value and a nominal stride value, and wherein the next target time is calculated using the previous target time value and the nominal stride value.
Claim 5
Dependent Claim
65 words
The method according to claim 3, wherein the schedule table has an associated current time value and the virtual circuit represented by the first token also has an associated gain value, and wherein an offset to the next target time window in the schedule table is calculated using the current time value, the previous target time value, the nominal stride value, and the gain value.
Claim 6
Dependent Claim
71 words
The method according to claim 3, wherein the schedule table has a selectable time window size and a current time value and the virtual circuit represented by the first token also has an associated gain value, and wherein an offset to the next target time window in the schedule table is calculated using the previous target time value, the nominal stride value, the gain value, and the time window size value.
Claim 7
Dependent Claim
55 words
The method of claim 4, wherein the schedule table also has a selectable time window size, and wherein an offset to the next target time window in the schedule table is calculated using the current time value, the previous target time value, the nominal stride value, the gain value, and the time window size value.
Claim 8
Independent Claim
147 words
An apparatus for scheduling tokens representing active virtual circuits and for supplying the tokens to a transmit controller, the apparatus comprising: (A) a schedule table having a plurality of time windows in which tokens can be stored; (B) a target time computation mechanism for generating an offset to a target time window in said schedule table, said target time window containing a token slot that is the target for storing a first token; (C) a coarse grain scheduling mechanism coupled between the target time computation mechanism and the schedule table for determining an available time window in the schedule table near the target time window, said time window representing a time period during which a token is expected to be processed; and (D) a priority queue coupled to the schedule table for buffering tokens from the schedule table and supplying the buffered tokens to the transmit controller.
Claim 9
Independent Claim
147 words
An apparatus for scheduling tokens representing active virtual circuits and for supplying the tokens to a transmit controller, the apparatus comprising: (A) a schedule table having a plurality of time windows in which tokens can be stored; (B) a target time computation mechanism for generating an offset to a target time window in said schedule table, said target time window containing a token slot that is the target for storing a first token; (C) a coarse grain scheduling mechanism coupled between the target time computation mechanism and the schedule table for determining an available time window in the schedule table near the target time window, said time window representing a time period during which a token is expected to be processed; and (D) a priority queue coupled to the schedule table for buffering tokens from the schedule table and supplying the buffered tokens to the transmit controller.
Claim 10
Dependent Claim
16 words
The apparatus of claim 7, wherein the coarse grain scheduling mechanism is comprised of a bitmap.
Claim 11
Dependent Claim
50 words
The apparatus of claim 8, wherein the bitmap is comprised of a plurality of bits, each bit having one of a "set" state or a "cleared" state, and wherein a "set" state indicates one or more filled time windows and a "cleared" state indicates one or more unfilled time windows.
Claim 12
Dependent Claim
18 words
The apparatus of claim 7, wherein the priority queue employs a prioritization scheme to arbitrate among the tokens.
Claim 13
Dependent Claim
54 words
The apparatus of claim 7, wherein the tokens include rate controlled tokens and non-rate controlled tokens and wherein the first token is a rate controlled token, further comprising a recirculating sequential queue having a plurality of non-rate controlled tokens, coupled to the transmit controller, for supplying the non-rate controlled tokens to the transmit controller.
Claim 14
Dependent Claim
38 words
The apparatus of claim 7, wherein the tokens include real-time tokens and non-real-time tokens, and wherein the schedule table is comprised of a real-time schedule table for storing real-time tokens and a non-real-time-schedule table for storing non-real-time tokens.
Claim 15
Dependent Claim
142 words
A scheduling method in a network node having a transmit controller, a schedule table having a plurality of time windows, each time window including at least one token slot and a priority queue containing at least one token, where each token represents an active virtual circuit (VC), the method comprising the steps of: (A) selecting a first token from the priority queue; (B) calculating a next target time for servicing of the VC represented by the first token in a transmit controller; (C) performing conflict resolution in a predetermined set of steps; (D) storing the first token in the schedule table in a time window near the calculated next target time, said time window representing a time period during which a token is expected to be processed; and (E) processing said first token by transferring said first token to said priority queue.
Claim 16
Dependent Claim
142 words
A scheduling method in a network node having a transmit controller, a schedule table having a plurality of time windows, each time window including at least one token slot and a priority queue containing at least one token, where each token represents an active virtual circuit (VC), the method comprising the steps of: (A) selecting a first token from the priority queue; (B) calculating a next target time for servicing of the VC represented by the first token in a transmit controller; (C) performing conflict resolution in a predetermined set of steps; (D) storing the first token in the schedule table in a time window near the calculated next target time, said time window representing a time period during which a token is expected to be processed; and (E) processing said first token by transferring said first token to said priority queue.
Claim 17
Dependent Claim
74 words
The method according to claim 13, wherein the node further includes a bitmap having a plurality of bits, each bit having one of a "set" state or a "cleared" state, and wherein a "set" state indicates one or more filled time windows and a "cleared" state indicates one or more unfilled time windows, and wherein the storing step includes traversing the bitmap to find the unfilled time window nearest the calculated next target time.
Claim 18
Dependent Claim
46 words
The method according to claim 13, wherein the virtual circuit represented by the first token has an associated previous target time value and a nominal stride value, and wherein the next target time is calculated using the previous target time value and the nominal stride value.
Claim 19
Dependent Claim
65 words
The method according to claim 15, wherein the schedule table has an associated current time value and the virtual circuit represented by the first token also has an associated gain value, and wherein an offset to the next target time window in the schedule table is calculated using the current time value, the previous target time value, the nominal stride value, and the gain value.
Claim 20
Dependent Claim
71 words
The method according to claim 15, wherein the schedule table has a selectable time window size and a current time value and the virtual circuit represented by the first token also has an associated gain value, and wherein an offset to the next target time window in the schedule table is calculated using the previous target time value, the nominal stride value, the gain value, and the time window size value.
Claim 21
Dependent Claim
55 words
The method of claim 16, wherein the schedule table also has a selectable time window size, and wherein an offset to the next target time window in the schedule table is calculated using the current time value, the previous target time value, the nominal stride value, the gain value, and the time window size value.
Claim 22
Independent Claim
108 words
An apparatus for scheduling tokens representing active virtual circuits and for supplying the tokens to a transmit controller, the apparatus comprising: (A) a schedule table having a plurality of time windows in which tokens can be stored, each token representing a data frame having a variable size; (B) a target time computation mechanism for generating an offset to a target time window in said schedule table, said time window representing a time period during which a token is expected to be processed; and (C) a priority queue coupled to the schedule table for buffering tokens from the schedule table and supplying the buffered tokens to the transmit controller.
Claim 23
Independent Claim
108 words
An apparatus for scheduling tokens representing active virtual circuits and for supplying the tokens to a transmit controller, the apparatus comprising: (A) a schedule table having a plurality of time windows in which tokens can be stored, each token representing a data frame having a variable size; (B) a target time computation mechanism for generating an offset to a target time window in said schedule table, said time window representing a time period during which a token is expected to be processed; and (C) a priority queue coupled to the schedule table for buffering tokens from the schedule table and supplying the buffered tokens to the transmit controller.
Claim 24
Dependent Claim
74 words
The apparatus of claim 19 wherein said target time computation mechanism is a rate control scheduler, said rate control scheduler maintaining a bin pointer and a service pointer where said bin pointer addresses a current time window of said schedule table for supplying buffered tokens in said current time window to the transmit controller and said service pointer addresses one of said tokens in said schedule table to be supplied to the transmit controller.
Claim 25
Dependent Claim
44 words
The apparatus of claim 20 wherein said service pointer is capable of lagging behind said bin pointer such that said service pointer addresses one of said tokens in one of said time windows other than the current time window addressed by said bin pointer.
Claim 26
Dependent Claim
58 words
The apparatus of claim 21 wherein said target time window contains a token that is the target for storing a first token, the apparatus further comprising: (D) a coarse grain scheduling mechanism coupled between the target time computation mechanism and the schedule table for determining an available time window in the schedule table near the target time window.
Claim 27
Dependent Claim
16 words
The apparatus of claim 22, wherein the coarse grain scheduling mechanism is comprised of a bitmap.
Claim 28
Dependent Claim
50 words
The apparatus of claim 23, wherein the bitmap is comprised of a plurality of bits, each bit having one of a "set" state or a "cleared" state, and wherein a "set" state indicates one or more filled time windows and a "cleared" state indicates one or more unfilled time windows.
Claim 29
Dependent Claim
18 words
The apparatus of claim 22, wherein the priority queue employs a prioritization scheme to arbitrate among the tokens.
Claim 30
Dependent Claim
54 words
The apparatus of claim 22, wherein the tokens include rate controlled tokens and non-rate controlled tokens and wherein the first token is a rate controlled token, further comprising a recirculating sequential queue having a plurality of non-rate controlled tokens, coupled to the transmit controller, for supplying the non-rate controlled tokens to the transmit controller.
Claim 31
Dependent Claim
38 words
The apparatus of claim 22, wherein the tokens include real-time tokens and non-real-time tokens, and wherein the schedule table is comprised of a real-time schedule table for storing real-time tokens and a non-real-time-schedule table for storing non-real-time tokens.
References Cited (Backward Citations)
US5050161A
Cited
US5268900A
Cited
US5422888A
Cited
US5515363A
Cited
US5533020A
Cited
US5649110A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-03 | 2003-07-05 | 2004-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-03 | 2007-07-05 | 2008-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-03 | 2011-07-05 | 2012-01-04 | $7700.00 | Window Closed / Lapsed |