Subject: Service disciplines for RSVP 7/08/95 7/11/95 22:33

From: "Roch Guerin ((914) 784-7038)" <[email-masked]>
Date: Wed, 12 Jul 95 07:22:48 EDT

Reference:  Your note of Tue, 11 Jul 95 22:33 EDT

>While I do not know what Roch means exactly by 'trigger greater load', sending

Did not mean greater load but greater load variations.  This happens as
sending things early at one point can create a bigger burst downstream.
Hence, a higher traffic (load) for some period of time.  Since the long
term intensity (load) does not change, this only means that the range
of load variations can get bigger.

>packets early will cause more jitter, whether or not the scheduling discipline
>is "rate controlled" (actually, when Hui Zhang and I came up with the term
>rate-controlled, we meant exactly that packets are NOT sent early,
>even if the line is idle). If packets can be sent early, it is easy
>to construct a pathological case where one packet experiences 0 queueing
>delay, and the next one experiences HD, where there are H hops, and D is the
>delay bound for each hop. In the case where packets are sent only
>at their appointed time (rate controlled), the best and worst case delay
>is HD, so that the delay jitter is 0.

Not sure I understand the above reasoning.  Rate controlled service
disciplines have two components, a rate controller and a scheduler.
Even if the rate controller releases a packet at its "appointed" time,
i.e., ensuring it is compliant with the specified traffic envelope, this
does not mean that the scheduler will send the packet out immediately.
The delay bound D (assuming it's the same at each node) applies only to
the scheduler, which only guarantees that the packet be released before
D time units after it's been received at the scheduler.  This still
leaves open the possibility of a scheduler delay varying between 0 and D,
i.e., a jitter of up to D at one node and HD for the path.

Actually, upon thinking some more about the issue of the impact of
releasing packets early in rate controlled service disciplines (to make
them work-conserving), I must actually disagree with my earlier
intuition.... Sic...  Allowing early release of packets when the link
is IDLE in rate-controlled service discipline will not worsen jitter,
at least not the maximum jitter.

The reasons are as follows: The best and worst delays which a packet
can experience are not changed by this modification of the discipline.
This is easy to see for the best delay, i.e., take a packet (for example
the first packet of a connection) which is compliant with its
rate-controller and is, therefore, immediately forwarded to the
scheduler at each node on its path.  If we further assume that this
packet sees no contention on its path (all the links are idle), then
the scheduler will always put it out immediately and the packet sees
an end-to-end delay which is simply the (constant) propagation delay.
For the worst case delay, we know (see section 6 of the report mentioned
in previous notes) that releasing packets early when the link is idle
does NOT impact the delay guarantees.  Hence, this modification of the
rate controlled service discipline provides the same delay bounds as the
non-work-conserving version.  Since the best and worst delays which a
packet can experience are the same, this then implies that the worst
jitter is also the same.  Hence, we have not made things worse from a
worst case jitter point of view by allowing early release of packets.

The next question is whether early packet release (in case of idle links)
may actually help improved overall jitter.  This is a little tricky as it
depends on the exact definition of jitter (a very elusive thing).  If we
are concerned about worst case jitter, then from the previous discussion
there is obviously no improvement.  On the other hand, if we focus on
more statistical quantities, e.g., average delay variations, then because
releasing packet earlier will lower average packet delays, we may
see better average jitter performance in some cases.  However, this is
not a general statement as one can again easily construct sample paths
where the average delay is lower but the delay variations are greater.

>The crux of the matter, it seems to me, is whether we want to have
>a zero jitter and have all packets arrive with HD delay, or whether
>we want to have a possibly much lower mean delay, but deal with
>a delay jitter of HD, and larger buffer sizes downstream. Not that we have
>to make a hard choice in the design - it is quite easy to construct hybrid
>disciplines that offer users a choice (variants of HRR or RCSP will do this).

Again, providing zero jitter is quite difficult as it requires that we
either impose both an upper and a lower bound on the operation of the
scheduler or that we have mechanisms to dynamically adjust delay bounds
at each node.  The first approach impacts/shrinks the schedulable region
since it imposes additional constraints on the scheduler.  The second
approach can certainly be achieved through variants of HRR or RCSP but
requires additional control information, so that local bounds can be
properly adjusted.  In any case, this more a design option than a hard
constraint.

Roch