---

   tc-hfsc    ( 7 )

---

BASICS OF HFSC

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.