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

 


Help: OASIS Mailing Lists Help | MarkMail Help

wsrm message

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


Subject: Re: [wsrm] R: [wsrm] Rel YY


Sunil,

The case I mentioned was un-ordered case.
When GoupId is different one by one,
the case I described would not be used, as you mentioned.

However if we allow to use sequence number for
un-ordered messages, sender can send un-ordered
messages in one GroupId with unique SequenceNumber.
In detail, there are two ways to send un-ordered messages:

1. Different GroupId + SequenceNumber "0"
    1st message:
        GroupId = aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group1
        SequenceNmbr = 0
    2nd message:
        GroupId = aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group2
        SequenceNmbr = 0
    3rd message:
        GroupId = aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group3
        SequenceNmbr = 0

2.One GroupId + unique SequeceNumber
    1st message:
        GroupId = aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group1
        SequenceNmbr = 1
    2nd message:
        GroupId = aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group1
        SequenceNmbr = 2
    3rd message:
        GroupId = aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group1
        SequenceNmbr = 3

For the case#1 above, we can't use efficient multiple Acking,
but for case#2, we can. I believe we should allow both cases
above, since grouping is up to sender and receiver's policy.

And we can omit SequenceNumber for the case#1, and
spec can mention that it must be considered SequceNumber is 0,
if it is omitted. I think it helps those who don't want
to use SequceNumber.

In this case, since the messages are un-ordered, the
SequenceNumber doesn't have to indicate the order of the message,
but it helps to identify the message within the GroupId.
And it is much simpler than identifying message with
long GroupId, especially for multiple Acking.

Thanks,

Iwasa



>
>  Iwasa,
>
>  I'm bit confused. Could you clarify whether the options you have
>  mentioned are for ordered or un-ordered case?
>
>  If it is for un-ordered case, their GroupIds will be different,
>  so you can't club them as you have mentioned in Option 2.
>  If it is for ordered case, we do have SequenceNo and the current
>  proposal has 2 sub-elements (RefToGroupId and RefToSequenceNo)
>  under Response Header. For multiple acks., we will have multiple
>  Response Header elements.
>
>  Yes, it is in-efficient for multiple ack case, but we really haven't
solved
>  or visited the multiple-ack case so far.  We should definitely optimize
>  it for such cases.
>
>  Infact we still can use a modified option 2 for multiple acks efficiently
>  by saying that RefToSequenceNumberStart and RefToSequenceNumberEnd
>  as optional attributes?
>
>  Current Response Header:
>         <Response>
>              <RefToGroupId>
>              <RefToSequenceNumber>
>          </Response>
>
>  Modified version of your Option 2 would be:
>         <Response>
>             <RefToGroupId
>                         RefToSequenceNumberStart="1"
>                         RefToSequenceNumberEnd="100">
>                   aaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group
>              </RefToGroupId>
>           </Response>
>
>  RefToSequenceNumberStart and RefToSequenceNumberEnd will be
>  optional attributes.
>
>  For un-ordered msgs., they won't be needed.
>  For single ordered ack, they will be the same.
>  For multiple ordered acks, they will represent the range.
>
>  So I don't see a reason to have SequenceNumfer for un-ordered case.
>
>  -Sunil
>
> iwasa wrote:
>
> > I also agree with Jacques proposal,
> > since I was considering a resolution and struggling
> > to find out a way to send multiple acks in a single Ack message,
> > which is our requirement.
> >
> > See the following example of five Acks in a single
> > Ack message:
> > 1) Without SequeceNumber:
> >     <Response>
> >         <RefToGroupId>
> >               aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group1
> >         </RefToGroupId>
> >         <RefToGroupId>
> >               aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group2
> >         </RefToGroupId>
> >         <RefToGroupId>
> >               aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group3
> >         </RefToGroupId>
> >         <RefToGroupId>
> >               aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group4
> >         </RefToGroupId>
> >         <RefToGroupId>
> >               aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group5
> >         </RefToGroupId>
> >     </Response>
> >
> > 2) With SequceNumber
> >     <Response>
> >         <RefToGroupId SeqNmbrStart=1, SeqNumbrEnd=5>
> >               aaaaa.bbbbb.cccccc/xxxxxxx/yyyyyy/zzzzzz/group1
> >         </RefToGroupId>
> >     </Response>
> >
> > In conclusion, SequenceNumber is reasonably
> > desired to realize multiple Acks in a single Ack message.
> > Since we should not preclude a possibility of efficient and scalable
> > way of Duplicate Checking, and Multiple Acking.
> >
> > We may want to define default value of "0" as SequenceNumber for
> > non-ordered delivery, when it was ommitted.
> >
> > Thanks,
> >
> > Iwasa
> >
> > ----- Original Message -----
> > From: "Doug Bunting" <Doug.Bunting@Sun.COM>
> > To: "Paolo Romano" <paolo.romano@dis.uniroma1.it>
> > Cc: "'Jacques Durand'" <JDurand@fsw.fujitsu.com>;
> > <wsrm@lists.oasis-open.org>
> > Sent: Tuesday, September 23, 2003 9:28 AM
> > Subject: Re: [wsrm] R: [wsrm] Rel YY
> >
> > > Paulo and Jacques,
> > >
> > > This appears to be a standard performance / storage trade off.  The
> > > direction chosen at our last face to face meeting emphasizes
simplicity
> > > of the specification and implementations.  The suggestions below
> > > optimize on the other side, toward reduced storage requirements.  The
> > > included reasoning depends upon the number of messages received
overall
> > > (in some time period) and how many of those messages come from the
same
> > > origin.  Without clear numbers applicable to all WS-Reliability use
> > > cases (something we are not going to get), I find it hard to choose.
> > >
> > > Absent concrete numbers, I would probably lean toward the simpler
> > > solution already chosen by the group.
> > >
> > > thanx,
> > > doug
> > >
> > > On 22-Sep-03 16:49, Paolo Romano wrote:
> > >
> > > > I like Jacques proposal. We should address both the problems of (1)
> > > > minimizing the state information that needs to be persistently
stored
> > > > and of (2) how to efficiently acknowledge batches of messages. The
key
> > > > idea of Jacques suggestion is to have a sequential, strictly
> > > > increasing identifier. Such a property could then be exploited to
> > > > record/acknowledge continous sequences of messages (i.e. messages
with
> > > > sequential MessageIDs) by referincing only the lower and upper bound
of
> > > > the sequence.
> > > > With this approach, it is possible to reduce the amount of memory
> > > > required at the purpose of duplicates elimination even furtherly:in
fact
> > > > if, for a given GroupID, a set of messages with
> > > > MessageID={0,1,..i..,n-1,n} has been received, then it is only
necessary
> > > > to store the MessageID "n", to indicate that messages up to n have
> > > > already been received.
> > > > As an example, consider a receiver RMP which has caught the messages
> > > > carrying GroupID:X and MessageID={1,2,3,4,5,6,10,15,16}. It should
only
> > > > record that "messageIDs up to 6" and MessageID={10,15,16} have
> > > > been received. In general, if a sequence of
MessageIDs={j,j+1,..,k-1,k}
> > > > with k>j is received, it is sufficient to store just j and k. Note
that
> > > > this property is independent on having enabled the ordering
> > > > functionality at the RMP level.
> > > > On the other hand, GroupID is essential (and sufficient) to allow
> > > > univoque identification of the "conversation".
> > > >
> > > > Paolo
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >     Here is a more precise wording of the issue I see with limiting
> > > >     the use of sequence numbers to ordering only.
> > > >
> > > >     Jacques
> > > >
> > > >
> > > >     A new issue, (related to Rel-36, Rel-88)
> > > >     ------------
> > > >
> > > >     Precluding the use of sequence numbers, when message ordering is
NOT
> > > >     required,
> > > >     will pose serious scalability issues for duplicate elimination
> > > >     algorithms.
> > > >     Indeed, in doing so the GroupID would actually behave as a
Message
> > ID,
> > > >     and will require to be stored for each past message for the
> > > >     duplicate look up.
> > > >     Consider the two following deployment cases of WS-R:
> > > >
> > > >     Case 1: Assume a messaging Hub, that must guarantee exactly once
> > > >     delivery under
> > > >     the following conditions:
> > > >     Throughput: 1000 messages/sec
> > > >     Size of GroupID values (approximately): 30 bytes
> > > >     Scope of duplicate checks: messages over last 5 days
> > > >     Using a messageID-based duplicate check, this Hub must keep a
> > > >     database of GroupIDs able to store:
> > > >     1000 mesg * 432,000 (Number of seconds in 5 days) = 432,000,000
> > > >     GroupIDs to store.
> > > >     Database size: 12.9 GB.
> > > >     Besides the significant resource investment needed, (which may
> > > >     please database vendors!)
> > > >     this solution may simply not be feasible or at least cause quite
an
> > > >     additional headache and cost:
> > > >     the database may not keep up with the speed required for
duplicate
> > > >     checks:
> > > >     fast retrieval would require indexing. But the high rate of
updates
> > > >     of such an index
> > > >     (2000/sec counting additions and removals) offsets the
performance
> > > >     gain in indexed search,
> > > >     as we know indexes are costly to update, especially on a large
> > table.
> > > >     One way or the other, the overhead of duplicate checking may
simply
> > > >     be overwhelming.
> > > >
> > > >     Case 2: Assume a messaging end-point, receiving 10 messages/sec
> > > >     average.
> > > >     Duplicate search is required over the last 30 days. We would
still
> > need
> > > >     a full-fledged database (or B-tree) engine, with data size close
to
> > > >     1 GB.
> > > >
> > > >
> > > >     Proposal: (P1 + P2 + P3)
> > > >     ---------
> > > >
> > > >     P1: Make it possible for Senders to use GroupID + SequenceNo to
do
> > > >     any grouping they want,
> > > >     even when ordering is not required. The only requirement is,
these
> > > >     elements
> > > >     should be used as they are for ordering, i.e.:
> > > >     - (GroupID + SequenceNo) must be globally unique,
> > > >     - the sender must generate contiguous sequence numbers within a
> > group.
> > > >
> > > >     P2:SequenceNo element is mandatory in the header, even when NOT
> > > >     requiring ordering.
> > > >     In both cases, a Sender can at discretion:
> > > >     - (a) send messages with a different GroupID each time (1
message
> > > >     per group, with smallest
> > > >     SequenceNo)
> > > >     - (b) send longer sequences of messages within a group.
> > > >
> > > >     P3: To signal the Receiver to do ordered delivery on a sequence,
the
> > > >     Sender will add
> > > >     messageOrder element in the header (close to option (3) in Rel
88),
> > > >     and is required to
> > > >     do so at least in the first message(s) of a group.
> > > >
> > > >     NOTE1: On the receiver side, duplicate message elimination would
use
> > > >     SequenceNo
> > > >     for fast duplicate elimination within a group, and use an
indexed
> > > >     search over a store
> > > >     of GroupIDs for all groups currently active. Clearly, in the
extreme
> > > >     case (a) above,
> > > >     duplicate elimination would be as costly as over conventional
> > > >     message IDs.
> > > >     But if Case 1 above actually has only about 1000 "active groups"
at
> > > >     any time
> > > >     (e.g. 1000 concurrent senders generating each a single long
sequence
> > > >     at rate of 1 mesg/sec),
> > > >     then the GroupID store and seq number info associated with it,
can
> > > >     hold in the memory
> > > >     of a small device (estimate: 1 Mb) and does not need a DBMS.
> > > >
> > > >     NOTE2: The requirement (Rel 26) to allow for "multiple-Ack"
> > > >     messages, can be fulfilled
> > > >     in a simple way when using sequences of messages, by the use of
an
> > > >     interval notation to signal
> > > >     groups of messages that are acknowledged. Or, use an upper
bound:
> > > >     One Ack message could state
> > > >     that all messages below SequenceNo N are acknowledged.
> > >
> > >
> > >
> > > 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/wsrm/members/leave_workgroup.php.
> > >
> >
> > 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/wsrm/members/leave_workgroup.php.
>



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