next up previous
Next: Start Fair Queuing Up: Background on proportional share Previous: The ideal model

Weighted Fair Queuing

The first known Proportional Share scheduling algorithm is Weighted Fair Queuing (WFQ) [4], which emulates the behavior of a GPS system using the concept of virtual time. The virtual time v(t) is defined by increments as follows:

\begin{displaymath}\left \{ \begin{array}{l c l}
v(0) & = & 0 \\
dv(t) & = &
\...
...\sum_{\tau_i \in \Gamma_a(t)} w_i}dt \\
\end{array} \right. .
\end{displaymath}

Each request qik is assigned a virtual start time S(qik) and a virtual finish time F(qik) defined as follows:

\begin{eqnarray*}S(q_i^k) & = & \max\{v(r_{i,k}),F(q_i^{k-1})\} \\
F(q_i^k) & = & S(q_i^k) + \frac{Q_{i,k}}{w_i} \\
\end{eqnarray*}


where ri,k is the time at which request qik is generated and Qi,k is the request dimension (required execution time). Since Qi,k is not known a priori, it is assumed equal to the maximum value Qi. Tasks' requests are scheduled in order of increasing virtual finish time: in the virtual time domain, each request will finish before its virtual finish time.

In static systems, where all the tasks are always active, WFQ provides fairness by bounding the allocation error. However, it presents the following problems:


next up previous
Next: Start Fair Queuing Up: Background on proportional share Previous: The ideal model

1999-02-16