RE: [RPRWG] Questions about alladin draft.
Ping,
Actually, the questions of starvation, committed rate services, efficient BW
reclamation you brought are very fundamental to RPR. Not just you, I'm, too,
get confused on these issues from time-to-time. I hope that my response
below
can clear things up for your somewhat. If not, I'm sure other people on the
reflector who are an expert in these subject areas can jump in and help you
out.
Please see my comment in-line below.
-----Original Message-----
From: Ping Yuan [mailto:pyuan@xxxxxxxx]
Sent: Friday, January 11, 2002 12:03 PM
To: Adisak Mekkittikul
Cc: stds-802-17@xxxxxxxx
Subject: Re: [RPRWG] Questions about alladin draft.
Adisak,
Thanks a lot for your feedback. I still got confused...
1. What's the definition of an active flow? A flow that has packets to send
during the previous interval T? Or a flow that uses more than it's committed
bandwidth in the previous interval T? From the pseudo code, it looks like
the second one. But, if it's the second one, how to allocate the available
bandwidth among flows? For example, if a flow uses less than its committed
bandwidth, but does have some packets to send, what's its allocated
bandwidth? It's committed bandwidth or 0?
>>> For a leaky bucket implementation, a flow from each source node is
considered
active when the leaky bucket is non-empty. The activity of the flow
depends
on the relativity of the service rate (allocated BW) and arrival rate
(the actual
traffic on the ring) of the bucket (of a given sending node). These are
possible
cases
1. a source is sending more than allowed rate --> a bucket is active
100% of the time
and overflow eventually (a transit node can use this overflow
condition to police
transit rate)
2. a source node is sending exactly at the allowed rate-> bucket 100%
active, no
overflow
3. a source node is sending x% of the allowed rate, the bucket is active
x% of the
time (time avg)
4. a source node send no traffic (sub-case of 3), the bucket remain
inactive all
the time.
Note that the allowed rate (the drain rate of the bucket) is committed
rate plus
available rate. Each bucket will be drained at least by its committed
rate.
All the leaky bucket tries to do is to guarantee committed rate and at
the same time
"reclaim" the unused BW that the node previously allocated to each
upstream node.
As you can see, how efficient an RPR network can achieve depends largely
on how well
the MAC can reclaim the BW.
2. Since the transit path will always has the highest priority, how to
prevent starvation?
>>> Oh, this is a very good question.
Without a flow control mechanism, an RPR MAC will starves downstream
nodes because it gives priority to transit traffic as you pointed out.
I'm not sure if most people will agree with me or not. A flow control
brings the well-known issue of a classical closed-loop control system:
"A convergence time of the flow control."
When congestion occurs and a downstream node cannot get on the ring
(i.e. being
starved), it can correct the situation by asking upstream nodes to
reduce their
traffic. The sooner the upstream traffic is let up, the less starvation
downstream
node experiences.
But with the ring being geographically separate, the fastest a upstream
can receive
a downstream slow-down request is fiber delay, by this time it has
already put many
packets in-flight on the fiber and in transit buffer.
In general the starvation time is equal to the loop-delay, which has the
following
worst case bound.
loop delay = fiber delay + transit buffer depth (time unit) + flow
control
convergence time + source response time.
Proposed RPR flow control algorithms differ greatly in each of the above
loop-delay components. Going forward, I expect to see more studies in
terms
of simulation and analytical analysis in this area when we have to
choose on
proposal vs. another.
Is this the area you might be interested in?
As in any closed-loop system, in trying to get out of starvation, a
system can get
into a over-correcting situation and causes many other undesirable
effects:
Oscillation, on-off behavior which will result in poor network
utilization and/or
excessive delay and jitter.
Thanks,
-Ping
----- Original Message -----
From: "Adisak Mekkittikul" <adisak@xxxxxxxxxxxxxx>
To: "'Ping Yuan'" <pyuan@xxxxxxxx>; <stds-802-17@xxxxxxxx>
Sent: Wednesday, January 09, 2002 4:11 PM
Subject: RE: [RPRWG] Questions about alladin draft.
> Ping,
>
> Please find the answers to your questions below. Please let us know if
> you need more detail to any question.
>
> Regards,
> Adisak
>
>
>
> -----Original Message-----
> From: Ping Yuan [mailto:pyuan@xxxxxxxx]
> Sent: Tuesday, January 08, 2002 3:48 PM
> To: stds-802-17@xxxxxxxx
> Subject: [RPRWG] Questions about alladin draft.
>
>
>
> Hi,
>
> I have some questions about the "Media Access Control (Bandwidth
Management
> and Transit-Path)" in alladin draft.
>
> 1. What does the "link bandwidth monitor entry" measures exactly? Does it
> measure per-ingress based sending rate?
>
> Ans: The link bandwidth monitor entity measures traffic from each source
> node
> by using per-source leaky buckets to track the traffic and at the
same
> time monitor
> rate conformance (police transit traffic) of transit traffic from
each
> source.
> Conceptwise, this is simple a generic credit based rate pacer.
> The bandwidth allocation is done based on the state of the buckets at
> line xx
> yy in the following pseudo-code.
>
> @calcInterval
> /* initialization */
> sum_R = 0;
> sum_W = 0;
>
> /* do for each source node */
> for (i = 0; i < 256; i++) {
> /* drain the bucket for node i */
> bucket[i] -= calcInterval * (Ri + Wi * RCF_new);
> if (bucket[i] <= 0) { /* flow is inactive */
> bucket[i] = 0;
> } else { /* do only for active flows */
> sum_R += R[i];
> sum_W += W[i];
> }
> }
> line xx AvailableRingBW = link_capacity - sum_R;
> line yy RCF_sampled = min((AvailableRingBW / sum_W), link_capacity);
>
>
>
> 2. Is it true that every ring node will send a RCM message periodically?
>
> ans: Yes, each node send RCM periodically every 10ms interval, but if the
> congestion
> is imminent a node can send out RCM immediately too.
>
>
> 3. Is it true that ever node will keeps the RCM information from all the
> down stream nodes so as to police the transmitting rate to different
> destination?
>
> Ans: Yes,
>
> 4. How to calculate the policing rate for traffic to different destination
> based on the RCM information? Is it true that a node will pick the minimum
> RCM along the path to destination as the transmitting rate? I didn't find
> pseudo code about that. It would be helpful if you can let me know where
to
> find more pseudo code about the bandwidth management algorithm in Alladin
> draft.
>
> Ans: The Pseudo code on page 15 and 16 of C8_MAC_V0_6.doc are for two
> type of policers. The one on page 15 is all destinations (per
> destination)
> The one on page 16 is a single rate policer (one choke point).
>
> Both are credit based policers that translate rates (RCMs) into
> credits. In doing so the policer, in effect, meets minimum RCM,
> i.e. logically performs min (RCM) function (at line zz)
>
>
> @Tupdate
> for each (link segment j on the ring) {
> /* calculate the allowable bandwidth for this node */
> F[j] = R[j] + W[local_node] * RCF[j];
> /* accumulate credits for each segment */
> segment_credit[j] += F[j] * Tupdate;
> segment_credit[j] = MIN(segment_credit[j], MAX_CREDIT);
> line zz if (segment_credit[j] < 0) { /* client has exceeded credit for
> segment */
> segment_paused[j] = TRUE;
> assert PAUSE.indicate for segment j;
> } else {
> segment_paused[j] = FALSE;
> clear PAUSE.indicate for segment j;
> }
> }
>
> @DATA.request from client
> for each (link segment j between source and destination) {
> if (segment_paused[j] == TRUE) {
> reject DATA.request;
> return;
> }
> }
> accept DATA.request;
> for each (link segment j between source and destination) {
> /* deduct segment credit */
> segment_credit[j] -= packet_length;
> }
>
>
> I will highly appreciate any response from you.
>
> -Ping
>
>