OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

ebxml-msg message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]

Subject: Re: [ebxml-msg] CSMA Back-Off Algorithm


At the ebMS face to face meeting last week in Ottawa, improving the retry
mechanism popped up as an issue we would like to address.

The Back-Off algorithm in CSMA seems like suitable prior art to consider in
this issue.  Consider the following:

"A reliable message exchange that must complete within 2 days.  If the
remote party is unavailable, try to retransmit every 30 seconds."

Expiration (e) = P2D
Retry Interval (ri) = P30S

If the remote host experiences an extended period unavailability, valuable
CPU and network resources are wasted on the sending side for 2 days just to
figure this out.  If we apply a back-off algorithm, we can at least reduce
the time allotted to transmitting or attempting to transmit a message to a
host that is not available.

So, with a modified back-off algorthim, we would have:

Expiration (e) = P2D
Retry Interval (ri) = P30S
Back-Off Multiplier (bom) = 1.5
Multiplications before reset (mbr) = 10

Given the above, transmission attempts would look like:

ri+0s: transmit
ri+30s since last transmit
ri+45s since last transmit
ri+67.5s since last transmit
ri+101.25s since last transmit
ri+151.88s since last transmit
ri+227.81s since last transmit
ri+341.7s since last transmit
ri+512.6s since last transmit
ri+768.9s since last  transmit
(reset occurs, ri=0)

This cycle would continue until the point of expiration.  I've added the
"reset" so that messages with shorter expiration periods have a reasonable
chance of being transmitted.  If we ran without the reset in a situation
where the expiration period ended in 2 days, it really wouldn't take long
before ri reached a point beyond 2 days (172800s).

Regards, Matt

On 6/19/04 10:11 AM, "Patrick Yee" <kcyee@cecid.hku.hk> wrote:

> Hi,
> This is a very interesting proposal. May we know how the CSMA algorithm
> helps to improve the retry mechaism?
> Regards, -Patrick
> Matthew MacKenzie wrote:
>> On the topic of improving our retry algorithm, I think a variant of the
>> Back-Off algorithm used in Carrier Sense Multiple Access may be suitable.
>> Me may want to specify a "reset interval", so that the delay does not built
>> up to such a high number that the message is never transmitted after an
>> extended loss of connectivity.
>> http://www2.rad.com/networks/2001/ethernet/backof.htm
>> "Each sender will delay after a collision before attempting to retransmit.
>> If they will delay for the same time, another collision will occur. That¹s
>> why each sender chooses a random delay between 0 and d (d is some standard
>> delay value). If, nevertheless, another collision occurs, each computer
>> doubles the range from which the delay is chosen,  that means, the random
>> delay will now be between 0 and 2d. If another collision occurs the range
>> will be between 0 and 4d and so onŠ After each collision the range of the
>> random delay increases exponentially, therefore the probability of collision
>> rapidly decreases and after few iterations becomes negligible."
>> ___________________________
>> Matthew MacKenzie
>> Senior Architect
>> IDBU Server Solutions
>> Adobe Systems Canada Inc.
>> http://www.adobe.com/products/server/
>> mattm@adobe.com
>> +1 (506) 871.5409
>> To unsubscribe from this mailing list (and be removed from the roster of the
>> OASIS TC), go to
>> http://www.oasis-open.org/apps/org/workgroup/ebxml-msg/members/leave_workgrou
>> p.php.

Matthew MacKenzie
Senior Architect
IDBU Server Solutions
Adobe Systems Canada Inc.
+1 (506) 871.5409

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]