To understand how HFSC works, we must first introduce a service
curve. Overall, it's a nondecreasing function of some time unit,
returning the amount of service (an allowed or allocated amount
of bandwidth) at some specific point in time. The purpose of it
should be subconsciously obvious: if a class was allowed to
transfer not less than the amount specified by its service curve,
then the service curve is not violated.
Still, we need more elaborate criterion than just the above
(although in the most generic case it can be reduced to it). The
criterion has to take two things into account:
• idling periods
• the ability to "look back", so if during current active
period the service curve is violated, maybe it isn't if
we count excess bandwidth received during earlier active
period(s)
Let's define the criterion as follows:
(1) For each t1, there must exist t0 in set B, so S(t1-t0) <= w(t0,t1)
Here 'w' denotes the amount of service received during some time
period between t0 and t1. B is a set of all times, where a
session becomes active after idling period (further denoted as
'becoming backlogged'). For a clearer picture, imagine two
situations:
a) our session was active during two periods, with a small
time gap between them
b) as in (a), but with a larger gap
Consider (a): if the service received during both periods meets
(1), then all is well. But what if it doesn't do so during the
2nd period? If the amount of service received during the 1st
period is larger than the service curve, then it might compensate
for smaller service during the 2nd period and the gap - if the
gap is small enough.
If the gap is larger (b) - then it's less likely to happen
(unless the excess bandwidth allocated during the 1st part was
really large). Still, the larger the gap - the less interesting
is what happened in the past (e.g. 10 minutes ago) - what matters
is the current traffic that just started.
From HFSC's perspective, more interesting is answering the
following question: when should we start transferring packets, so
a service curve of a class is not violated. Or rephrasing it: How
much X() amount of service should a session receive by time t, so
the service curve is not violated. Function X() defined as below
is the basic building block of HFSC, used in: eligible, deadline,
virtual-time and fit-time curves. Of course, X() is based on
equation (1) and is defined recursively:
• At the 1st backlogged period beginning function X is
initialized to generic service curve assigned to a class
• At any subsequent backlogged period, X() is:
min(X() from previous period ; w(t0)+S(t-t0) for t>=t0),
... where t0 denotes the beginning of the current
backlogged period.
HFSC uses either linear, or two-piece linear service curves. In
case of linear or two-piece linear convex functions (first slope
< second slope), min() in X's definition reduces to the 2nd
argument. But in case of two-piece concave functions, the 1st
argument might quickly become lesser for some t>=t0. Note, that
for some backlogged period, X() is defined only from that
period's beginning. We also define X^(-1)(w) as smallest t>=t0,
for which X(t) = w. We have to define it this way, as X() is
usually not an injection.
The above generic X() can be one of the following:
E() In realtime criterion, selects packets eligible for
sending. If none are eligible, HFSC will use linkshare
criterion. Eligible time 'et' is calculated with
reference to packets' heads ( et = E^(-1)(w) ). It's
based on RT service curve, but in case of a convex curve,
uses its 2nd slope only.
D() In realtime criterion, selects the most suitable packet
from the ones chosen by E(). Deadline time 'dt'
corresponds to packets' tails (dt = D^(-1)(w+l), where
'l' is packet's length). Based on RT service curve.
V() In linkshare criterion, arbitrates which packet to send
next. Note that V() is function of a virtual time - see
LINKSHARE CRITERION section for details. Virtual time
'vt' corresponds to packets' heads (vt = V^(-1)(w)).
Based on LS service curve.
F() An extension to linkshare criterion, used to limit at
which speed linkshare criterion is allowed to dequeue.
Fit-time 'ft' corresponds to packets' heads as well
(ft = F^(-1)(w)). Based on UL service curve.
Be sure to make clean distinction between session's RT, LS and UL
service curves and the above "utility" functions.
