From help-file :
CSZ packet scheduler CONFIG_NET_SCH_CSZ Say Y here if you want to use the Clark-Shenker-Zhang (CSZ) packet scheduling algorithm for some of your network devices. At the moment, this is the only algorithm that can guarantee service for real-time applications (see the top of net/sched/sch_csz.c for details and references about the algorithm). Note: this scheduler is currently broken. This code is also available as a module called sch_csz.o ( = code which can be inserted in and removed from the running kernel whenever you want). If you want to compile it as a module, say M here and read Documentation/modules.txt.
From source-files :
Clark-Shenker-Zhang algorithm.
=======================================
SOURCE.
David D. Clark, Scott Shenker and Lixia Zhang
"Supporting Real-Time Applications in an Integrated Services Packet
Network: Architecture and Mechanism".
CBQ presents a flexible universal algorithm for packet scheduling,
but it has pretty poor delay characteristics.
Round-robin scheduling and link-sharing goals
apparently contradict minimization of network delay and jitter.
Moreover, correct handling of predictive flows seems to be
impossible in CBQ.
CSZ presents a more precise but less flexible and less efficient
approach. As I understand it, the main idea is to create
WFQ flows for each guaranteed service and to allocate
the rest of bandwith to dummy flow-0. Flow-0 comprises
the predictive services and the best effort traffic;
it is handled by a priority scheduler with the highest
priority band allocated for predictive services, and the rest ---
to the best effort packets.
Note that in CSZ flows are NOT limited to their bandwidth. It
is supposed that the flow passed admission control at the edge
of the QoS network and it doesn't need further shaping. Any
attempt to improve the flow or to shape it to a token bucket
at intermediate hops will introduce undesired delays and raise
jitter.
At the moment CSZ is the only scheduler that provides
true guaranteed service. Another schemes (including CBQ)
do not provide guaranteed delay and randomize jitter.
There is a proof (Sally Floyd), that delay
can be estimated by a IntServ compliant formula.
This result is true formally, but it is wrong in principle.
It takes into account only round-robin delays,
ignoring delays introduced by link sharing i.e. overlimiting.
Note that temporary overlimits are inevitable because
real links are not ideal, and the real algorithm must take this
into account.
ALGORITHM.
--- Notations.
$B$ is link bandwidth (bits/sec).
$I$ is set of all flows, including flow $0$.
Every flow $a \in I$ has associated bandwidth slice $r_a < 1$ and
$\sum_{a \in I} r_a = 1$.
--- Flow model.
Let $m_a$ is the number of backlogged bits in flow $a$.
The flow is {\em active}, if $m_a > 0$.
This number is a discontinuous function of time;
when a packet $i$ arrives:
\[
m_a(t_i+0) - m_a(t_i-0) = L^i,
\]
where $L^i$ is the length of the arrived packet.
The flow queue is drained continuously until $m_a == 0$:
\[
{d m_a \over dt} = - { B r_a \over \sum_{b \in A} r_b}.
\]
I.e. flow rates are their allocated rates proportionally
scaled to take all available link bandwidth. Apparently,
it is not the only possible policy. F.e. CBQ classes
without borrowing would be modelled by:
\[
{d m_a \over dt} = - B r_a .
\]
More complicated hierarchical bandwidth allocation
policies are possible, but unfortunately, the basic
flow equations have a simple solution only for proportional
scaling.
--- Departure times.
We calculate the time until the last bit of packet is sent:
\[
E_a^i(t) = { m_a(t_i) - \delta_a(t) \over r_a },
\]
where $\delta_a(t)$ is number of bits drained since $t_i$.
We have to evaluate $E_a^i$ for all queued packets,
then find the packet with minimal $E_a^i$ and send it.
This sounds good, but direct implementation of the algorithm
is absolutely infeasible. Luckily, if flow rates
are scaled proportionally, the equations have a simple solution.
The differential equation for $E_a^i$ is
\[
{d E_a^i (t) \over dt } = - { d \delta_a(t) \over dt} { 1 \over r_a} =
{ B \over \sum_{b \in A} r_b}
\]
with initial condition
\[
E_a^i (t_i) = { m_a(t_i) \over r_a } .
\]
Let's introduce an auxiliary function $R(t)$:
--- Round number.
Consider the following model: we rotate over active flows,
sending $r_a B$ bits from every flow, so that we send
$B \sum_{a \in A} r_a$ bits per round, that takes
$\sum_{a \in A} r_a$ seconds.
Hence, $R(t)$ (round number) is a monotonically increasing
linear function of time when $A$ is not changed
\[
{ d R(t) \over dt } = { 1 \over \sum_{a \in A} r_a }
\]
and it is continuous when $A$ changes.
The central observation is that the quantity
$F_a^i = R(t) + E_a^i(t)/B$ does not depend on time at all!
$R(t)$ does not depend on flow, so that $F_a^i$ can be
calculated only once on packet arrival, and we need not
recalculate $E$ numbers and resorting queues.
The number $F_a^i$ is called finish number of the packet.
It is just the value of $R(t)$ when the last bit of packet
is sent out.
Maximal finish number on flow is called finish number of flow
and minimal one is "start number of flow".
Apparently, flow is active if and only if $F_a \leq R$.
When a packet of length $L_i$ bit arrives to flow $a$ at time $t_i$,
we calculate $F_a^i$ as:
If flow was inactive ($F_a < R$):
$F_a^i = R(t) + {L_i \over B r_a}$
otherwise
$F_a^i = F_a + {L_i \over B r_a}$
These equations complete the algorithm specification.
It looks pretty hairy, but there is a simple
procedure for solving these equations.
See procedure csz_update(), that is a generalization of
the algorithm from S. Keshav's thesis Chapter 3
"Efficient Implementation of Fair Queeing".
NOTES.
* We implement only the simplest variant of CSZ,
when flow-0 is a explicit 4band priority fifo.
This is bad, but we need a "peek" operation in addition
to "dequeue" to implement complete CSZ.
I do not want to do that, unless it is absolutely
necessary.
* A primitive support for token bucket filtering
presents itself too. It directly contradicts CSZ, but
even though the Internet is on the globe ... :-)
"the edges of the network" really exist.
BUGS.
* Fixed point arithmetic is overcomplicated, suboptimal and even
wrong. Check it later.