[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: TPA and ebXML Header question
Regarding deadlocks, I have some questions and comments.
The example shows a fixed window size of 4. Who or what determines the
window size?
What is in a single window?
Only messages for one conversation?
Only messages for one pair of application instances?
All messages going on the same outbound link?
What happens if application-level responses are owed to all sent messages
but there aren't enough sent messages to fill the window?
I believe the answer is: deadlock, but I may not have understood something
in this proposal.
Example 1 shows that the sending message service waits until the window is
filled before attempting to retry message 3. If that is correct, then it
will deadlock if there aren't enough outgoing messages to fill the window.
Regards,
Marty
*************************************************************************************
Martin W. Sachs
IBM T. J. Watson Research Center
P. O. B. 704
Yorktown Hts, NY 10598
914-784-7287; IBM tie line 863-7287
Notes address: Martin W Sachs/Watson/IBM
Internet address: mwsachs @ us.ibm.com
*************************************************************************************
SHIMAMURA Masayoshi <shima@rp.open.cs.fujitsu.co.jp> on 10/26/2000 04:53:33
AM
To: ebxml-transport@lists.ebxml.org
cc: ebxml-tp@lists.ebxml.org
Subject: Re: TPA and ebXML Header question
TRP Team Members,
The latest RM specification, which is included in the MS specification
v0.21d, has not the blocking restriction. So the Sender can send some
messages without waiting for acknowledgement message. However the
removal of the blocking restriction caused two problems:
(1) Message order is not guaranteed
(2) The Receiver can't know required buffer size previously
Existing communication protocols resolve the problems by Sliding Window
technique. Mr. David Burdett's idea is near to the Sliding Window.
The Window begins from first unacknowledgment message in the Sender.
Only when the Sender does not receive Acknowledgement for the message in
the Window, the Sender stops sending new message. The Sender executes
retry sequence instead of sending new message, even if timeout is not
detected yet.
Here is an example of the Sliding Window protocol:
---------------------------------------
Ex. 1 [Window Size = 4]
---------------------------------------
[Sender] [Receiver]
Seq No.1 ----------> Passed to App
Ack for No.1 <----------
Seq No.2 ----------> Passed to App
Ack for No.2 <----------
Seq No.3 ---> LOST A
|
Seq No.4 ----------> Buffered |
Ack for No.4 <---------- |
|
Seq No.5 ----------> Buffered | Window (size = 4)
Ack for No.5 <---------- |
|
Seq No.6 ----------> Buffered |
Ack for No.6 <---------- V
[the Sender stop sending new message
and retry sending message No.3]
Seq No.3 (retry) -------> Passed to App
Ack for No.3 <----------
Pass Seq No.4 to APP
[the Sender initiates Pass Seq No.5 to APP
sending new message] Pass Seq No.6 to APP
Seq No.7 ----------> Passed to App
Ack for No.7 <----------
Seq No.8 ----------> Passed to App
Ack for No.8 <----------
In the Sender, the size of Window means number of messages which the
Sender can send without receiving Acknowledgement message. In the
Receiver, the size of Window means size of maximum buffer.
When the Sender receives delayed Acknowledgement message in the Window,
the Sender does not stop sending new message. Here is an example:
----------------------------------------
Ex. 2 [Window Size = 4]
----------------------------------------
[Sender] [Receiver]
Seq No.1 ----------> Passed to App
Ack for No.1 <----------
Seq No.2 ----------> Passed to App
Ack for No.2 <----------
Seq No.3 ----------> Passed to App A
|
Seq No.4 ----------> Passed to App |
Ack for No.4 <---------- |
|
Seq No.5 ----------> Passed to App | Window (size = 4)
Ack for No.5 <---------- |
|
Ack for No.3 <--- DELAYED | The unacknowledged message
| (Seq No.3) is acknowledged
[Since Mes No.3 is acknowledged | in the Window
in the Window, the Sender does |
not stop sending new message] |
|
Seq No.6 ----------> Passed to App |
Ack for No.6 <---------- V
Seq No.7 ----------> Passed to App
Ack for No.7 <----------
The Sliding Window above has not deadlock problem which Mr. Martin Sachs
pointed out in the RM-Group. I'd like to explain the detail of the
Sliding Window technique in the Tokyo Meeting.
On Wed, 18 Oct 2000 08:31:30 -0700
"Burdett, David" <david.burdett@commerceone.com> wrote:
> I think you can do sequencing without blocking on the RM ACK. In the
> following example a message is lost and resent ...
>
> Msg Seq No 1 ---> Passed to App
> <--- Msg Ack Seq no 1
> Msg Seq No 2 ---> Passed to App
> Msg Seq No 3 ---> GETS LOST ON THE NETWORK
> <--- Msg Ack Seq no 2
> Msg Seq No 4 ---> Buffered
> <--- Msg Ack Seq no 4
> Msg Seq No 5 ---> Buffered
> <--- Msg Ack Seq no 5
> Msg Seq No 3 ---> RESEND Passed to App
> Pass Msg Seq no 4 to APP
> Pass Msg Seq no 4 to APP
> <--- Msg Ack Seq no 3
>
> ... and if the transport sends messages out of sequence then you would
get
> the following variation ...
>
> Msg Seq No 1 ---> Passed to App
> <--- Msg Ack Seq no 1
> Msg Seq No 2 ---> Passed to App
> Msg Seq No 3 ---> IS DELAYED
> <--- Msg Ack Seq no 2
> Msg Seq No 4 ---> Buffered
> <--- Msg Ack Seq no 4
> Msg Seq No 5 ---> Buffered
> <--- Msg Ack Seq no 5
> Msg 3 arrives and is Passed to App
> Pass Msg Seq no 4 to APP
> Pass Msg Seq no 4 to APP
> <--- Msg Ack Seq no 3
>
> The key point is that if the sender does not get the ack for message 3
then
> he will eventually re-send the original message as in the earlier
example.
>
> Also if you know ...
> 1. The arrival rate of messages and
> 2. The timeout interval that triggers a resend if an ack is not received
> ... then you can calculate the likely maximum size of your buffer. So if
the
> time out interval is, say 1 minute and you are sending two messages a
second
> and you assume that you have to do two re-tries before the message gets
> through then a buffer size of 3 x 120 or around 360 messages would be
> required, so make it a 1000 and it should suffice.
>
> If eventually the recipient fills up their buffer for that conversation
then
> it can send an error message in response to the lost message and stop
> buffering further messages.
>
> Thoughts?
>
> David
Regards,
--
SHIMAMURA Masayoshi
E-mail: shima@rp.open.cs.fujitsu.co.jp
TEL:+81-45-476-4590(ext.7128-4241) FAX:+81-45-476-4726(ext.7128-6783)
Planning Dep., Strategic Planning Div., Software Group, FUJITSU LIMITED
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC