summaryrefslogtreecommitdiffstats
path: root/net/sched/sch_csz.c
diff options
context:
space:
mode:
authorRalf Baechle <ralf@linux-mips.org>1998-08-25 09:12:35 +0000
committerRalf Baechle <ralf@linux-mips.org>1998-08-25 09:12:35 +0000
commitc7fc24dc4420057f103afe8fc64524ebc25c5d37 (patch)
tree3682407a599b8f9f03fc096298134cafba1c9b2f /net/sched/sch_csz.c
parent1d793fade8b063fde3cf275bf1a5c2d381292cd9 (diff)
o Merge with Linux 2.1.116.
o New Newport console code. o New G364 console code.
Diffstat (limited to 'net/sched/sch_csz.c')
-rw-r--r--net/sched/sch_csz.c78
1 files changed, 39 insertions, 39 deletions
diff --git a/net/sched/sch_csz.c b/net/sched/sch_csz.c
index c21d8ac43..207a1dd51 100644
--- a/net/sched/sch_csz.c
+++ b/net/sched/sch_csz.c
@@ -49,12 +49,12 @@
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 to minimization of network delay and jitter.
+ apparently contradict minimization of network delay and jitter.
Moreover, correct handling of predictive flows seems to be
impossible in CBQ.
- CSZ presents more precise but less flexible and less efficient
- approach. As I understand, the main idea is to create
+ 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;
@@ -62,22 +62,23 @@
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 flow passed admission control at the edge
- of QoS network and it more need no 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.
+ 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 exists the statement (Sally Floyd), that delay
- can be estimated by a IntServ compliant formulae.
+ 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 true algorithm must take it
+ Note that temporary overlimits are inevitable because
+ real links are not ideal, and the real algorithm must take this
into account.
ALGORITHM.
@@ -92,14 +93,14 @@
--- Flow model.
- Let $m_a$ is number of backlogged bits in flow $a$.
- The flow is {\em active }, if $m_a > 0$.
- This number is discontinuous function of time;
+ 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 arrived packet.
+ 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}.
@@ -112,23 +113,23 @@
{d m_a \over dt} = - B r_a .
\]
More complicated hierarchical bandwidth allocation
- policies are possible, but, unfortunately, basic
- flows equation have simple solution only for proportional
+ policies are possible, but unfortunately, the basic
+ flow equations have a simple solution only for proportional
scaling.
--- Departure times.
- We calculate time until the last bit of packet will be sent:
+ 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 packet with minimal $E_a^i$ and send it.
+ then find the packet with minimal $E_a^i$ and send it.
- It sounds good, but direct implementation of the algorithm
+ This sounds good, but direct implementation of the algorithm
is absolutely infeasible. Luckily, if flow rates
- are scaled proportionally, the equations have simple solution.
+ are scaled proportionally, the equations have a simple solution.
The differential equation for $E_a^i$ is
\[
@@ -149,7 +150,7 @@
$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 monotonically increasing
+ 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 }
@@ -160,17 +161,17 @@
$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
- recalculation of $E$ numbers and resorting queues.
- Number $F_a^i$ is called finish number of the packet.
- It is just value of $R(t)$, when the last bit of packet
- will be sent out.
+ 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 packet of length $L_i$ bit arrives to flow $a$ at time $t_i$,
- we calculate number $F_a^i$ as:
+ 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}$
@@ -179,31 +180,30 @@
These equations complete the algorithm specification.
- It looks pretty hairy, but there exists a simple
+ It looks pretty hairy, but there is a simple
procedure for solving these equations.
See procedure csz_update(), that is a generalization of
- algorithm from S. Keshav's thesis Chapter 3
+ 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 explicit 4band priority fifo.
- It is bad, but we need "peek" operation in addition
+ 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 make it, until it is not absolutely
+ I do not want to do that, unless it is absolutely
necessary.
* A primitive support for token bucket filtering
- presents too. It directly contradicts to CSZ, but
- though the Internet is on the globe ... :-)
- yet "the edges of the network" really exist.
+ 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.
-*/
+ wrong. Check it later. */
/* This number is arbitrary */