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

[Patrick Yee <kcyee@cecid.hku.hk>]

Matt,

Thanks for your prompt explanation. While the backoff algorithm helps in 
reducing the system loading, does it fail to address the service 
contract? If we view the statement "try to retransmit every 30 seconds" 
as a partner agreement from higher level (e.g. CPA in ebXML suite), it 
seems to me that the ebMS layer should implement that. What I try to 
point out is that, implementation of a more advanced algorithm needs 
more configuration to the ebMS handler, and sometimes this will impact 
the coupling of higher level specificatons.

Just my $0.02.

Regards, -Patrick


Matthew MacKenzie wrote:

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