Subject: Re: [issue55] Execution text replacement

From: Robert Haas <[email-masked]>
Date: Thu, 14 Jul 2005 13:36:11 +0200

Here is some text to resolve the issue wrt "fast recovery" of pending 
transactions across association tear-down and reestablishment. Please 
comment.

Associations may be taken down either due to heartbeat timeout, or an 
explicit teardown message.

The first question is: what do we do with all the state in the FE after 
the association is down ?
1) if it is due to a heartbeat timeout, then the "CE failover and 
restart policy" attribute in the FE Protocol LFB indicates if the FE 
should continue operation even though the CE is gone.
2) if the association was taken down explicitely with a teardown 
message, then we can assume that operation of the FE must be stopped. OK ?

The next question is: what do we do with all the "old" FE state when the 
association is reestablished ?
1) if the association was taken down explicitely, then all the "old" 
state in the FE is gone. The CE must restore all necessary state. OK ?
2) if the association timed out, then unless the FE Protocol LFB keeps a 
state that indicates how the last association went down, the FE cannot 
remember if association was lost due to timeout or explicit message, 
hence the same treatment as 1) above is expected.

If we agree on the above, then a new association means starting from 
scratch (all state in the FE must first be restored by the CE) so that 
no "fast" recovery of a transaction in intermediate state can occur.

OK ?

So we would have to change the text in section 3.3.1.1.1.3 "Recovery":
"When the associations are re-established, the CE will discover a
transaction in an intermediate state." and instead say: "Whenever an 
association is established (whether the association is new or it is 
recovered from a previous association), the CE MUST NOT expect that any 
state from the previous association has been kept in the FE."

OK ?

Regards,
-Robert

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 14 Jul 2005 07:52:10 -0400

I disagree with the last part.
The FE clearly can remember if it has been reset or not.

Let me separate the question into two parts.
The first part, which we discussed on the call, is what happens to pending 
transactions that have not been fully committed when the FE loses 
association with the CE.  In my opinion, no matter what the reason for the 
lose of association, such transactions MUST be unwound.

The second part is what state / operation the FE is permitted to retain 
when it does not have an association.  Robert distinguishes three cases:
1) When the FE is switching to the backup CE,
2) When the FE  has lost heartbeat with the CE, but does not have a backup, and
3) When the association was explicitly terminated by the CE.
Clearly, when switching from primary to secondary CE, the FE should keep 
its state, and keep forwarding packets
according to that state, until the new CE tells it otherwise.  The new CE 
may or may not already have knowledge of that state.  Even if it does not 
have such knowledge, it can read the state from the FE.

So, the question is what the FE "should" do when it loses association and 
does not have a backup CE or can not associate with it.  My answer is 
roughly "what ever it wants".  There is no reason for the FE to delete its 
state.  After all, we permit FEs with fixed state (or fixed portions of 
state), so whenever it does associate the CE will need to fetch that state 
anyway.
In terms of practical effect, once the CE is no longer advertising for the 
FE, after a time the other folks will stop sending it packets.  Until 
routing has expired the information about the FE, it is better for it to 
keep forwarding packets according to the old table, rather than 
black-holing them.  So for at least 90 seconds, it should keep operating.
However, if a particular FE implementation has a reason to clear state and 
bring down interfaces, that should not be prohibited.

Yours,
Joel

At 07:36 AM 7/14/2005, Robert Haas wrote:
>transactions across association tear-down and reestablishment. Please comment.
>
>1) if it is due to a heartbeat timeout, then the "CE failover and restart 
>policy" attribute in the FE Protocol LFB indicates if the FE should 
>continue operation even though the CE is gone.
>2) if the association was taken down explicitely with a teardown message, 
>then we can assume that operation of the FE must be stopped. OK ?
>
>1) if the association was taken down explicitely, then all the "old" state 
>in the FE is gone. The CE must restore all necessary state. OK ?
>remember if association was lost due to timeout or explicit message, hence 
>the same treatment as 1) above is expected.
>
>scratch (all state in the FE must first be restored by the CE) so that no 
>"fast" recovery of a transaction in intermediate state can occur.
>
>OK ?
>

---

From: Alistair Munro <[email-masked]>
Date: Thu, 14 Jul 2005 13:31:34 +0100

Hi All,

Now that we are back on transactionality again...

> The FE clearly can remember if it has been reset or not.

Yes, and if not reset then it can remember what its configuration is.

> The first part, which we discussed on the call, is what happens to
> pending transactions that have not been fully committed when the FE loses
> association with the CE.  In my opinion, no matter what the reason for
> the lose of association, such transactions MUST be unwound.

We could go for finer granularity but that just makes recovery a real pain. 
Let's go for this simple level of rollback. Do we also say that it is the 
CE that is the recovery master? Can the FE initiate the rollback/recovery?

>> explicit teardown message.

This suggests an ordered world out there. Maybe the heartbeat takes care of 
most disasters, but it could fail too. The recovery model should provide 
for a failure where the loss of association is not guaranteed to be 
reported.

Regards,

Alistair

--
Alistair Munro,
Principal Engineer, U4EA Technologies Ltd.
City Point, Temple Gate, Bristol, BS1 6PL, U.K.
E-mail: [email-masked]
Tel: (work) +44-117-373-6765, (home) +44-1275-462707, (mobile)
+44-7974-922-442;
Fax: +44-117-373-6751
Web: http://www.u4eatech.com

---

From: Robert Haas <[email-masked]>
Date: Thu, 14 Jul 2005 15:51:50 +0200

> Yes, and if not reset then it can remember what its configuration is.

Although the FE can remember what its configuration is between two 
associations, the CE cannot make any assumption about this. So the CE 
must check the configuration state of any newly associated FE.

> We could go for finer granularity but that just makes recovery a real 
> pain. Let's go for this simple level of rollback. Do we also say that 
> it is the CE that is the recovery master? Can the FE initiate the 
> rollback/recovery?

I agree that the FE MUST rollback by itself any unfinished transactions 
whenever the association is lost.
But what about this case: if the DONE-ACK (message from FE to CE to 
signal that the FE has completed the transaction) is lost due to 
association breakdown, the FE won't rollback anything (it just can't 
know that the DONE-ACK message did not make it to the CE). But from the 
CE viewpoint, it is unclear whether the transaction was completed.

As the association is reestablished, the CE will have to figure out what 
happened to that last transaction. Two ways of doing this:
- fetch all necessary FE state and double-check, or
- introduce an attribute in the FE Protocol LFB that indicates the ID of 
the last completed transaction (from the FE viewpoint). The CE will read 
this attribute as the association is reestablished.

What do you think ?

> This suggests an ordered world out there. Maybe the heartbeat takes 
> care of most disasters, but it could fail too. The recovery model 
> should provide for a failure where the loss of association is not 
> guaranteed to be reported.
>
Then I don't follow you: by definition, as association goes down either 
because heartbeats are not received for a period of time, or the 
teardown procedure was followed. The FSM does not consider any other 
event as a cause to bring the association down.

Regards,
-Robert

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

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 14 Jul 2005 16:54:47 -0400

Given that the CE has no way to know what may have happened to the FE since 
they were last talking, the CE
should always reload the FE state when an association is established by 
talking to the FE.

Yours,
Joel

At 09:51 AM 7/14/2005, you wrote:
>But what about this case: if the DONE-ACK (message from FE to CE to signal 
>that the FE has completed the transaction) is lost due to association 
>breakdown, the FE won't rollback anything (it just can't know that the 
>DONE-ACK message did not make it to the CE). But from the CE viewpoint, it 
>is unclear whether the transaction was completed.
>

---

From: Alistair Munro <[email-masked]>
Date: Thu, 14 Jul 2005 23:25:29 +0100

Hi Robert,

Thank you for your response. Apologies for a long reply, which may not make 
much sense...

> must check the configuration state of any newly associated FE.

I would like some time to think about this, but I am sure we have gone 
through the thought processes before and please remind me of the outcome if 
I'm repeating the obvious.

The FE may have valid next-hop and prefix tables for 10000's of routes and 
hundred of interfaces. Given an arbitrary disconnect between the CE and FE, 
what should we do to reconcile any differences? Probably transactional 
recovery is not enough but it might be the best case for brief 
interruptions. A newly associated FE (a blade I just plugged in for 
example) might have no state. But it has no transactions to recover.

> association breakdown, the FE won't rollback anything (it just can't know
> that the DONE-ACK message did not make it to the CE). But from the CE
> viewpoint, it is unclear whether the transaction was completed.

I didn't mean that the FE could autonomously roll transactions back. 
Recovery processes have a master and the assumption of shared state is the 
worst-case knowledge of the master - I'm assuming this is the CE but am I 
wrong?

If the CE is the master then all the FE can do is tell it that it has 
uncommitted transaction IDs (no commit request received), or committed 
transaction IDs (either acknowledged - it did them, or unacknowledged - it 
doesn't know). If the FE sent DONE-ACKs then it knows what it did - but if 
the CE has no recollection of receiving the DONE-ACK then, in principle, it 
doesn't know what happened. In that case we should go for presumed-abort, 
rolling back to the last confirmed transaction. But this will sometimes be 
inconsistent with recently received routing table/adjacency updates.

To avoid doubt, I'm confident that the protocol is good. It is the actions 
that may need to be examined. We should possibly aim to give estimates of 
uncertainty?

Apart from this, I agree with what you say, but this is the usual situation 
with transactional protocols - the certainty is only the last confirmed 
action that was executed.

By way of an opinion on how I think it works, I believe the protocol gives 
rollback responsibility to the CE. The FE can go for presumed abort, i.e. 
it notifies the CE of incomplete transactions and undoes them if the CE 
knows it received confirmation of them having been done (even if the FE did 
them). Recoveries are usually acknowledged so this should be safe even if 
the association fails during the recovery - as it tends to do.

As noted above, I thought the handshaking was OK so far, but I'll check 
again.

> this attribute as the association is reestablished.

You are starting to define a more complex recovery protocol. I think we 
must minimise the complexity but I have to admit I don't know how right now.

> because heartbeats are not received for a period of time, or the teardown
> procedure was followed. The FSM does not consider any other event as a
> cause to bring the association down.

Yes, this is what has been defined but the definition is possibly too 
optimistic. Busy CEs may not deliver heartbeats. My position is that there 
is *no* certainty in this kind of system, only minimising the extent and 
duration of inconsistency.

It's not a flaw in the concept but maybe it is a guideline for users about 
how much they can load their CEs?

If you got this far, thanks for reading this long and probably confusing 
message!

Alistair

---

From: Robert Haas <[email-masked]>
Date: Fri, 15 Jul 2005 16:29:10 +0200

Hi Alistair,

> The FE may have valid next-hop and prefix tables for 10000's of routes 
> and hundred of interfaces. Given an arbitrary disconnect between the 
> CE and FE, what should we do to reconcile any differences?

So let's see first what we should do in a simple case: the association 
breaks while there is NO transaction underway. The FE had 250k routes 
stored. When the association is reestablished, the CE MUST either:
- delete all the routes in the FE, and set the new routes.
- get all routes in the FE and modify/delete/add routes as necessary

Or do you propose something else ? Joel says that the CE should reload 
the entire FE state (by doing either of the two above).

Regards,
-Robert