[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: Re: [ebxml-msg] CSMA Back-Off Algorithm
Patrick, 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. http://www.adobe.com/products/server/ mattm@adobe.com +1 (506) 871.5409
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]