Subject: RE: [Forces-protocol] topic 4c: Common Header: batching

From: "Khosravi, Hormuzd M" <[email-masked]>
Date: Wed, 12 May 2004 14:19:47 -0700

All,
-----Original Message-----
From: [email-masked]
[mailto:[email-masked]] On Behalf Of [email-masked]

> Jamal, I suppose you tend to use parallel atomicity because you first 
> raise
> this, but not very sure. How about other guys thoughts?
>

I would worry about introducing great amounts of complexity to the 
protocol.

While i see value in atomic operations, i think they should be kept to 
a minimum as opposed to non-atomic batching - which is just for 
transport convenience and can be used freely as long as there is a 
sperate status per operation.  I thus think that the mechanism should 
be kept simple.

[HK] I agree with Avri's view on this. From our implementation
experience and customer requirements, non-atomic transactions has been
the most common case (infact we rarely use atomic transactions). I don't
think we should be introducing too much complexity (sub-SeqN) into the
protocol, unless we think its absolutely necessary to support that
functionality.

I also think multiple atomic ops could be dealt 
with in parallel without special mechanisms - the CE should not send a 
dependent op until the preceding atomic op has completed successfully.

[HK] Sounds reasonable to me.

Thanks for commenting,
Hormuzd

_______________________________________________
Forces-protocol mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/forces-protocol

---

From: "Weiming Wang" <[email-masked]>
Date: Thu, 13 May 2004 22:02:02 +0800

Hi Avri, Hormuzd,

Thank you very much for both your comments.  Although I think it is not  so
difficult in the protocol PDU to support multiple atomic ops (I think just
defining a 4 bit sth like AtomicCouter is enough to solve it), I also a litltle
doubt the wide use of it.  Jamal, Robert, and Ligang, could you give your ideas
at your convenience ?
Sorry to push it,  just hope to move forward more quickly.

Thank you.
Weiming

----- Original Message -----
From: "Khosravi, Hormuzd M" <[email-masked]>
To: <[email-masked]>; <[email-masked]>
Sent: Thursday, May 13, 2004 5:19 AM
Subject: RE: [Forces-protocol] topic 4c: Common Header: batching

All,
-----Original Message-----

Thanks for commenting,
Hormuzd

---

From: Jamal Hadi Salim <[email-masked]>
Date: 13 May 2004 10:35:47 -0400

This is the last email on this thread - so let me jump to it;
Earlier i proposed for a definition of transaction - i should have
posted one. 
I may go a little academic, so i apologize in advance (with a warning
that i am no expert). I think we may need an expert on this subject if
we are to get it right (not sure if Weiming or Ligang are)

Transaction Definition:
A transaction is a sequence of operations that is guaranteed to be
_atomic_ in the presence of any failures by the CEs or FEs.

Note: Atomic is part of the definition - i just added the CE/FE portion
to be specific to ForCES.
So having atomicity is not just for fun, it is what defines a
transaction. 
What the definition implies is clear on recovery from error: Atomicity
implies an all-or-none operation. So _absolutely_ no question whatsoever
on what a failure reaction is in atomic operations. All operations which
are atomic (whether carried by one or multiple PL messages) are executed
serially to ensure consistency across multiple FEs[1]. 

What is the scope of a transaction?
In other words how small is a unit transaction?
We have introduced a flag to turn off atomicity. In such a case i
believe that each operation (part of msg body) in the PL message becomes a
standalone _transaction_. So to take it one more step: Each of those
transactions(in the message body) can be atomic. Lets pick an example to
clarify:

A config PL msg with "route-add A B,C:route-del X" operations

CASE I: decide that they both need to go together in which case an
atomic flag in the main header with the sequence number should suffice
to provide the semantics. 

CASE II: decide are independent atomic config operations in which case i
can put the atomic flag for route-add of A,B,C and another one for X in
their respective operation headers.  

What you should note from the above is that in both case the
transactions are still _atomic_, only thing is granularity is different.
Clearly what we need to achieve case II is:
a) to allow for the atomic flag to also be within the operation headers
and b)to have a subsequence number to separate the success or failure of
"route-add of A,B,C" vs "route-del of X".

Case II allows for higher concurency which is what i think Weiming is
refering to. I am torn apart because i see the value in it as a way to
further pipeline (fill that 100Gige pipe) but i dont see a clean way in
the responses which are not going to impose on the general message. I
believe we shouldnt give up on it yet. Weiming maybe you can think of
some clever way to do it? 

I think the confusion we are faced with has been a result of lumping
atomicity and concurency/parallelization in one. 
Concurency is to allow us to improve the Forces computational
capability. We want to fill the pipe with transactions so as to maximize
the throughput. In other words, if you are provided with a 100Gige pipe
to submit transactions through, Forces protocol MUST not be the
bottleneck. The 100Gige could, of course.
Unfortunately (or fortunately) pipelining mechanisms such as batching is
also helpful in achieving atomicity if your transaction spans multiple
PL messages. 

Ok, i probably spent over 30 minutes typing this - need to do real work.

cheers,
jamal

[1]A classical paper published on this subject (unfortunatley i am not
an ACM member so i cant retrieve it from their database) is 
" T. Haerder, A. Reuter, "Principles of Transaction-Oriented Database
Recovery", Computing Surveys, Vol. 15, No. 4 (December 1983)"
My dusty high school book refers to the ACID properties of a
transactions as defined in that paper (I am sure there are a lot of
better papers than that which came after). 
ACID is a mnemonic which translates to (some of the wording is mine):

-> A for Atomicity ("a transaction is all or nothing")
-> C for Consitency ("A transaction moves the NE/FE from one consistent
state to another"); Example if a packet treatment such as a route goes
across multiple FEs then you better make sure that the all those
multiple FEs are updated at the same time, otherwise things will go
wrong.
-> I for isolation; essentially seriliazation of operations
-> D for Durability; an FE or CE crashing or a transaction failure
should be survivable.

On Wed, 2004-05-12 at 17:19, Khosravi, Hormuzd M wrote: 
> --Original Message--

---

From: Robert Haas <[email-masked]>
Date: Fri, 14 May 2004 01:04:27 +0200

Weiming,

>doubt the wide use of it.  Jamal, Robert, and Ligang, could you give your ideas
I personally don't see a high need for interleaved independent atomic 
transactions. The pathological case that one could think of is an atomic 
batch of a very very large number of routes that postpones a 
high-priority message. The heartbeat is a bad example because the FE 
should not think that the CE disappeared if it is still receiving routes 
from it.

Can someone think of a case in which the pathological scenario could 
result in a real problem ?

-Robert

-- 
Robert Haas
IBM Zurich Research Laboratory
Säumerstrasse 4
CH-8803 Rüschlikon/Switzerland
phone +41-1-724-8698  fax +41-1-724-8578  http://www.zurich.ibm.com/~rha

---

From: Jamal Hadi Salim <[email-masked]>
Date: 13 May 2004 21:18:40 -0400

On Thu, 2004-05-13 at 19:04, Robert Haas wrote:

> transactions. The pathological case that one could think of is an
> atomic batch of a very very large number of routes that postpones a
> should not think that the CE disappeared if it is still receiving
> routes from it.
> 

As long as you have indepedent operations (eg add route and a get route)
i think interleaving should be fine. 

cheers,
jamal

---

From: "Weiming Wang" <[email-masked]>
Date: Mon, 17 May 2004 21:49:31 +0800

Hi Jamal,

I appreciate the (academic :-) )summary that you took so much time on.

----- Original Message -----
From: "Jamal Hadi Salim" <[email-masked]>
> serially to ensure consistency across multiple FEs[1].
[Weiming]No doubt on the above summary.

> transactions(in the message body) can be atomic.
[Weiming]I agree that we can take every op in one msg body (mostly with a TLV
format) as one transaction. Moreover, academically, we can take any contiguous
ops in the msg body (like TLV1:TLV2:...TLVn) as one transaction, but this has
made things much complex i practice. Therefore, I made a proposal in our last
meeting that we may better to limit the freedom more or less. I just proposed
that we may just define one msg as only one transaction/atomic. I think in most
cases to take all ops in one same msg as one atomic is reasonable and practical,
and with the help of multi-msgs of batching with free atomic/nonatomic
selection, protocol flexibility will not be limited.

> Lets pick an example to
[Weiming]When using above proposal, we just put the ops of 'route-add A,B,C' and
'route-del X' in only one msg, while without any other flags to indicate the
transaction.

> their respective operation headers.
[Weiming]We may just use two msgs with two transactions, one for 'route-add
A,B,C' and one for 'route-del X', still without any flags to indicate the
transactions.

> some clever way to do it?
[Weiming]My thinking of the case above is to use two msgs for the ops, then we
can have separate responses for the msgs.
Actually I'm not very sure if I have cought what you mean or not? If you mean
the 'route-add A,B,C' are three ops that are put in three different msgs, then
my scheme is as follows:

First, pls let me explain the flags I used again:

Atomic flag: 1 - indicating the begin or middle of the atomicity(transaction)
             0 - indicating the end and the execution of the atomicity
Atomic counter: to inidicate which transactions the msg belongs in a concurrent
transaction case. (a 4 bit counter can support 16 concurrent transactions).

Then my scheme is as follows:

mark 4 msgs as:   msg(add A), msg(add B), msg(add C), msg(del X)
set atomic flag as:    1             1           0          0
set AtomCounter as:    1             1           1          2
(that means the msg(add A), msg(add B), msg(add C) belongs to the #1 concurrent
transaction, while msg (del X) belongs to #2 concurrent transaction)

After above setup, the 4 msgs can be sent to FE in any order, e.g., msg(add
A):msg(add B):msg(del X):msg(add C), or msg(add A):msg(del X):msg(add B):msg(add
C).

We can further use a Batch flag to let above msg chains batchingly transmitted
to FE. At the FE side, by using the atomic flag and the Atomic counter, we can
easily recover the transactions.

There may be only two responses for above 4 msgs (with 2 transactions), one for
msg(add C), one for msg(del X), but note that we should carefully define the
response msg format so that the response to a transaction end msg like the
msg(add C) should be able to include all information about the transaction. I
think something like a TLVforSummaryResponse in the end of the response msg can
do this well.
[/Weiming]

> also helpful in achieving atomicity if your transaction spans multiple
[Weiming]Agreed completely.

> -> D for Durability; an FE or CE crashing or a transaction failure

Cheers,
Weiming

---

From: Jamal Hadi Salim <[email-masked]>
Date: 17 May 2004 22:34:45 -0400

Weiming,

On Mon, 2004-05-17 at 09:49, Weiming Wang wrote:

[Deleted above because discussion below covers it]

> 'route-del X' in only one msg, while without any other flags to indicate the

That would work if you want to define everything in one message is
always atomic i.e from above example route-add and route-del have
all or none relationship.

> A,B,C' and one for 'route-del X', still without any flags to indicate the

This would also work with a caveat: your goodput may not be good.
Example in the case of route-del being a separate message the overhead
of the common header + TL and some of the common fileds in the V will be
much higher than the route-del itself.

> the 'route-add A,B,C' are three ops that are put in three different msgs, 

I meant they could be aggragated in one message.

> then

What i see is a need to a subseqeunce number (what you call atomic
counter) per TLV. In such a case if you can fit routes A, B, and C in
one message (example array of routes) then it becomes an all or nothing
operation. i.e. they either all get added or all fail.
You could then have a del-route as a separate TLV with its own counter.
You probably need startatomic and endatomic to make this work.
Also, as i mentioned earlier we should be able to use atomicstart/end on
either the whole message (which means all in the message is atomic) or
on a per TLV.

On failure or success each atomic message should probably get its own
ack/nack with proper sequence number. In other words, you may get
several messages with the same sequence number.
Not sure if i am clear.

> A):msg(add B):msg(del X):msg(add C), or msg(add A):msg(del X):msg(add B):msg(add

If you want to split them the counter should still apply - although i
think that each PDU should have its own unique seq number.

> easily recover the transactions.

Consider the atomic start/end flags.

> think something like a TLVforSummaryResponse in the end of the response msg can

Refer to what i said earlier above.

cheers,
jamal