Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

RE: [RPRWG] Questions about alladin draft.


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
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

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.


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
    active when the leaky bucket is non-empty. The activity of the flow
    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
    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
    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
    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
    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
    worst case bound.

        loop delay = fiber delay + transit buffer depth (time unit) + flow
                      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
    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

       Oscillation, on-off behavior which will result in poor network
utilization and/or
       excessive delay and jitter.




----- 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
> 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
> time monitor
>      rate conformance (police transit traffic) of transit traffic from
> 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
> 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