Rate Based Message Scheduling Paradigm
We have proposed a generic rate-based scheduling paradigm that can be used as a vehicle for designing/implementing message scheduling algorithms to provide message streams (or connections) with various levels of quality-of-service (QoS), such as best-effort services, statistically-guaranteed services, and/or deterministically-guaranteed services.
Many rate based message scheduling schemes used at runtime packet transmission have been proposed/investigated, among which (1) VirtualClock and its variations Self-Clocked Fair Queuing (SCFQ) and Leap Forward Virtual Clock (LFVC), and (2) Generalized Processor Sharing (GPS (or termed elsewhere Weighted Fair Queuing and its realistic implementations Packet-by-Packet Generalized Processor Sharing (PGPS) and Worst-case Fair Weighted Fair Queuing (WF^2Q) have received the most attention. Although realized with different approaches, all the above schemes aim to develop service disciplines that can provide worst-case performance guarantees (e.g., bounded delay and minimum effective service rate) and fairness (in some sense) to connections, and/or prevent interference among connections. Moreover, all the above schemes are centered upon the notion of service share or requested service rate: each connection at a node is assigned a service share or can request a service rate. The message scheduler then serves connections in proportion to the service share (or rate), independent of the queuing load presented by the connections.
Extracting the common features of all the above schemes, we propose a generic rate-based scheduling paradigm. The paradigm captures the three states which a connection may experience in its lifetime in terms of whether or not the connection is eligible to transmit its packet(s) under the scheduling algorithm. Transitions between states are triggered either by packet arrival or by the outcome of whether or not the service rate received by a connection is greater than its effective service rate under the scheduling algorithm. When a message scheduler is ready to transmit a new packet, it picks up, subject to certain priority assignment, the first packet in the packet queue of an eligible connection. By specifying how the effective service rates are calculated (and hence the criteria for a connection to become eligible), how priorities are assigned to eligible connections, and how eligible connections are selected for transmitting their packets by the message scheduler in the proposed scheduling paradigm, the paradigm can be used as a vehicle to implement existing rate-based message schedulers. (We have demonstrated how to implement GPS, PGPS, WF^2Q, VirtualClock, SCFQ and LFVC using the proposed scheduling paradigm.)
To facilitate description of the proposed paradigm, we first define the following terms: if the service rate received by a connection is lower (higher) than its effective rate (calculated based on the requested rates), the connection is said to be under served (over served). A connection is said to be idle if it has no packets queued for transmission and is under served. A connection is said to be busy either if it has packets queued for transmission or if it is over served. A connection is said to be eligible to transmit its packet if it is busy and under served.
As shown in the above figure, a connection may experience three different states in its lifetime (and hence there are three states in the proposed paradigm): idle, eligible, and ineligible. Upon establishment of a connection, the connection is in the idle state. When the first packet arrives when a connection is idle, the connection enters the eligible state, i.e., it is eligible to transmit its packet(s). Whenever the scheduler is ready to transmit a new packet, it chooses a connection from those eligible ones. The decision on which connection to select is not defined in the paradigm, but is left to the specific message scheduling algorithm. After transmitting a packet, the connection that is selected for transmission may
The other eligible connections remain unchanged. A connection that is in the ineligible state may go toIn order to more precisely define the notion of idle, eligible, and ineligible, we define r_q, r_e, r_m and tol for each connection. Upon establishment, each connection specifies its requested rate, r_q. Since the sum of the requested rates over all the established connections may be greater than the link capacity in the case of overbooking, a message scheduler may not serve each connection exactly at the requested rate. Instead, the scheduler allocates the link bandwidth to connections based on the requested rates. The effective rate, r_e, of a connection is defined as the maximum link bandwidth (dynamically) allocated to the connection. Usually r_e is updated (recalculated) whenever the set of busy connections changes, but otherwise remains unchanged. The misbehaving tolerance, tol, of a connection is defined as the maximum deviation (from the effective rate) that is permitted for a connection. The rules in which r_e is calculated (based on the requested rates, r_q's, of all connections) and in which tol is calculated (based on the online behavior of the connection) are left to the message scheduling algorithm being implemented to specify.
In order to identify the state a connection is currently in, we also calculate the service rate (called measured rate, r_m) that the connection receives from the scheduler. If r_m > r_e + tol (r_m <= r_e + tol), then the connection is over served (under served). r_m is calculated as the average service rate over the time period from the most recent reference time point (t_s) until the current time (t). Specifically, we keep track of the service amount the connection has received since t_s (in terms of number of bits, n_b, transmitted since t_s), and r_m = n_b / (t - t_s). Every time r_e is to be updated, we set n_b to be the service left over, i.e., n_b - (t - t_s) r_e and reset t_s to be the current time.
The pseudo code for the modules that implement the proposed scheduling paradigm is listed here.
Features of the Implementation
The scheduling paradigm possesses several desirable features:
Rate enforcement The paradigm realizes rate enforcement on each connection in the sense that in the time period during which the effective rate of a connection is fixed, the departure times of any two consecutive packets are at least T time units apart if the connection is over served, where T is equal to the size of the first packet in a busy period/(r_e+tol). Rate enforcement provides good traffic regulation for connections and good isolation among connections. The major drawback of rate enforcement is, however, that it usually leads to inefficient link utilization since the scheme that realizes rate enforcement is in nature not work-conserving. The proposed scheduling paradigm compensates this inefficiency by allowing overbooking and certain degree of misbehavior. |
Capability of handling overbooking The paradigm handles overbooking by defining r_q, r_e, and r_m. r_q is the requested rate suggested by a connection upon its connection, and to allow overbooking, sum r_q may be greater than the link capacity. r_e is then calculated, based on r_q's, for all busy connections, and is used as the parameter for rate enforcement. |
Traffic monitoringTraffic monitoring based on rates can provide better flow control because (1) a connection can be prevented from using more bandwidth than its fair share by, for example, rate enforcement; and (2) the upstream nodes of a connection can be notified by a node of the node's (in)capability of handling more traffic. Since the effective rate r_e is explicitly calculated (via procedure effective_rates_update()) as the maximum service rate at which a connection can receive in a measurement period, r_e can be readily used for the purpose of traffic monitoring. Moreover, the effective rate at which an intermediate node can provide service to a connection can be passed back to the source node of the connection which can then adjust its requested rate to better utilize the link capacity. |
FlexibilityAs discussed above, if the effective rates of all busy connections can be explicitly calculated for a message scheduling algorithm, this algorithm can be implemented by specifying the abstract modules in the paradigm accordingly. The scheduling paradigm thus provides us with a vehicle to implement many existing well-known rate-based message scheduling algorithms. On the other hand, one can also design, with the use of the scheduling paradigm, new scheduling algorithms by properly devising those abstract modules. To demonstrate both functions, we have implemented several scheduling algorithms, i.e., PGPS, WF^2Q, VirtualClock, SCFQ, and LFVC, using the proposed paradigm, and proposed a simple and effective scheduling algorithm, called FIFO-r, and analyzed its end-to-end delay. |
ModularityThe fact that implementation of the proposed scheduling paradigm is structured with modules that have well-defined interfaces significantly eases the jobs of a designer of rate-based message schedulers. In particular, since rate enforcement is a built-in function in the modularized paradigm, the designer needs only to focus on the rules for calculating effective rates and for selecting connections for transmission. Modularity also facilitates implementation of multiple scheduling algorithms in an uniform framework on a node. Different levels of QoS can be provided to applications by invoking appropriate message schedulers implemented in the same framework. |
|
Return
to Project Home Page