Adaptive transmit rate control scheduler
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
210 Citations
27 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. 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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. 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. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
19. 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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
Specification