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

[Sunil Kunisetty <Sunil.Kunisetty@oracle.com>]

Tom Rutt wrote:

> Sunil Kunisetty wrote:
>
> > 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.
> >
> Jacques proposal allows the use of sequence numbers other than zero
> value for the un ordered case.  His proposal goes back to the input
> document, which has sequence number and
> the messageOrder elements as separate things.  Jacques wants to allow
> groups with more
> than one member even when ordered delivery is not requested.

 That's fine. The point I was making in that email is simple - we
 don't need Seq No. just for multiple ack case. If there is another
 justified or needed requirement, we could have it, but not boz
 we have to support multiple acks.

 -Sunil

>
>
> Tom Rutt
>
> > 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.
> >>
> >>
> >
> >
> >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.
> >
> >
> >
>
> --
> ----------------------------------------------------
> Tom Rutt                email: tom@coastin.com; trutt@fsw.fujitsu.com
> Tel: +1 732 801 5744          Fax: +1 732 774 5133