Subject: Re: [issue54] correlator in the PL message header

From: "Khosravi, Hormuzd M" <[email-masked]>
Date: Sat, 11 Jun 2005 20:19:14 -0700

Ok, so you're saying we should use the Sequence number as a Correlator.
If that is the case then we are in agreement, I think. We should update
the text.

Let me know if I misunderstood you,
Hormuzd

-----Original Message-----
From: Forwarding and Control Element Separation
[mailto:[email-masked]] On Behalf Of Wang,Weiming
Sent: Saturday, June 11, 2005 8:14 PM
To: [email-masked]
Subject: Re: [FORCES] [issue54] correlator in the PL message header

----- Original Message -----
From: "Khosravi, Hormuzd M" <[email-masked]>

Yes, a Correlator is useful and currently we have been using the
Sequence number as correlator. I don't see any other use of the Sequence
number since reliability is provided by the TML. I think we should
change Sequence number to correlator in the draft and update the
description accordingly unless there is some use for a sequence number.

[Weiming] I think it's too early to say the SN is only for correlation.
currently I don't think we should a hundred percent to rely on TML for
thinks
like sequential ordering.   As a safer mode, I still prefer to have it
as its
original  name of Sequence Number. Correlating request/reply messages
should
only be one of its functions.

thanks,
Weiming

BTW, issue 47 looks like the same one...we should close one of these
issues.

regards
Hormuzd

-----Original Message-----
From: Forwarding and Control Element Separation
[mailto:[email-masked]] On Behalf Of Wang,Weiming
Sent: Friday, June 10, 2005 9:12 AM
To: [email-masked]
Subject: Re: [FORCES] [issue54] correlator in the PL message header

Robert,

----- Original Message -----
From: "Robert Haas" <[email-masked]>

New submission from Robert Haas <[email-masked]>:

Adding a correlator seems useful: response messages can be matched to
the
request messages even if pipelining and reordering occurs.
It seems that some are currently using the sequence number as a
correlator:
this can be dangerous, and not suitable for event notifications messages
(nothing to correlate with).
[Weiming] I'm not sure if you mean to use the SN as a correlator is to
let the
response have the same SN as the sender.  If so, I cannot follow well
why it is
dangerous and not suit for event notifications.  Could you clarify this
more?

Thanks.
Weiming

But this introduces the risk of flooding an FE with too many commands as
there
is no windowing mechanism in place (yet).

----------
category: Technical
draft: draft-ietf-forces-protocol
messages: 129
nosy: rha
priority: Should fix
status: No discussion
title: correlator in the PL message header

___________________________________________________
Forces issue tracker <[email-masked]>
<http://www.mip4.org/issues/tracker/forces/issue54>
___________________________________________________

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 12 Jun 2005 11:00:25 -0400

Actually, I would prefer to change the name.

A Sequence number should have a different sequential value has I hand 
messages from the PL to the TML.
A correlator should have distinct values for distinct requests, and replies 
should have the value from the request.
These are not the same property.  They may even be in conflict.

Note that a request originator is capable of remembering the sequence in 
which it sends requests.
Thus, for most purposes a correlator will do more than a sequence number.
What a correlator does not provide is the ability to compare the order of a 
received even and a received response.  If some TML may disorder things, 
that would be lost information.
If that is a big deal, we need two fields.

But we can not simply treat the sequence number as the correlator.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 12 Jun 2005 11:36:47 -0400

> But we can not simply treat the sequence number as the correlator.

Agreed.
In the some cases we could - but i think allowing for such polymorphic
behavior is something we may live to regret (it has been trickery-hell
in netlink to ensure backward compatibility because the seq # is used as
a correlator as well) so lets just add a second 32 bit number in the
main header. 

cheers,
jamal

---

From: Weiming Wang <[email-masked]>
Date: Tue, 14 Jun 2005 23:13:52 +0800

My opinion is:

1.  Function to correlate a request to a response is necessary.
    Seems no one objecting to this.

2. PL message sequential numbering is also necessary
    One of  the reason now I can think of is for packet redirect messages. Note that we haven't make a reliability reqirement for packet redirection, while the sequence of redirected packets are useful for these packets applications.

3. It can fulfill the function 1) well by defining that a response message should always have the same SN with the request to reply, hence we only need one field that is called sequence number. 

P.S. 
1. Sequence number should be maintained per CE and FE separately, and the message type uniquely recognize a message as a response message, therefore there will be no opaque in the Sequence number maintaince. 
2. Sequence number of an event from FE is generated by the FE, while response of the event (if any) should have the same sequence number as the event to response. 
3. A response to batching messages to meet two-phase-commits will have the same SN as that of the first message or the last message in the batch, just as what we'd like to define.

Thanks,
Weiming

---

From: Robert Haas <[email-masked]>
Date: Tue, 14 Jun 2005 17:36:23 +0200

Weiming,
I agree with 1 and 2, but I would not merge the two into the same 
sequence number concept. As an example, according to your suggestion, 
event notifications and packet redirections should be numbered according 
to a different sequence than response messages for which the numbering 
is imposed by the CE. So the CE would have to maintain two independent 
parallel sequences. This is unnecessary complexity to me.

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: Weiming Wang <[email-masked]>
Date: Wed, 15 Jun 2005 08:55:15 +0800

Robort,

----- Original Message ----- 
From: "Robert Haas" <[email-masked]>

Weiming,
is imposed by the CE. 
[Weiming] I didn't   think like this. Why the response message should be numbered by an CE here?  

So the CE would have to maintain two independent 
parallel sequences. This is unnecessary complexity to me.
[Weiming] I may miss something, but what I think of for this case is we never have two sequences to maintain in one same  CE or FE.  We only have one SN for one CE and one SN for one FE. Note that we don't need to maintain a SN for any response messages then. 

Thanks,
Weiming

Regards,
-Robert

---

From: Robert Haas <[email-masked]>
Date: Wed, 15 Jun 2005 10:44:22 +0200

Weiming,

>[Weiming] I didn't   think like this. Why the response message should be numbered by an CE here?  
Maybe I did not understand your point, so let's take a concrete example:

-> request from CE to FE, SN 5
<- response from FE to CE, SN 5 (5 is imposed by the CE, necessary for 
correlation and/or sequencing reasons)
-> request from CE to FE, SN 6 (ACK flag off)
no response from FE to CE
-> request from CE to FE, SN 7
<- response from FE to CE, SN 7
... so you see above that the CE would have to expect holes in the 
sequence numbers coming back from the FE.
... but in addition, there is another parallel sequence that the CE has 
to distinguish:
-> packet redirect messages and/or event notifications are sent from FE 
to CE, SN 11, 12, 13, 14 ... (decided by the FE)
... this means that, in addition to the added complexity of maintaining 
two parallel sequences, you cannot enforce any ordering between the 
command responses and the packet redirection/event notifications (=both 
sequences are independent).

Moreover, consider the case for which the CE is pipelining commands 
(=sending more than one command at a time, i.e., not waiting for each 
response before sending the next command), then things become really 
hairy ...

Please send a concrete example to describe how you propose to operate.

Regards,
-Robert

---

From: Jamal Hadi Salim <[email-masked]>
Date: Wed, 15 Jun 2005 12:51:59 -0400

> Maybe I did not understand your point, so let's take a concrete example:

[..]
So heres an example where the second 16/32-bit number will be useful.
This was actually well summarized by Joel's one paragraph[1], I am
hoping this may actually help rather than cause confusion ;->. This is
the closest i can get to the problem netlink is facing today.

Take an implementation which does the following:

On the CE, it has two connections between the PL and the TML
(lets make no assumptions of whether there are is one or more
processes/tasks).
On the FE (assuming different vendor from the CE), the implementation
has only one PL-TML connection.

On the CE, something at PL sends a message via one of the two PL level
connections to the CE - call it connection Y (and the other is
connection Z).
So TML grabs this message, sends it to the correct FE based on FEID.
FE responds back. TML grabs response and now has to mux it to the
correct PL connection. How does it do this?

One answer is the TML maintains a lot of PL level knowledge. But this is
clearly bad abstraction. Another answer is to tell the implementor
"no you cant do that - thou shalt implement a single process". Thats a
bad thing to say because it may limit the implementation only to some
specific OSes or it may make for an inefficient implementation on some
OSes. I could give a few more ways to implement this - none which are
"clean". 

Our implementation at the moment works fine because we have a single
process/task where all PL messages get muxed to and a single PL-TML
connection. We can therefore live with the command corelator being the
sequence number. Perhaps what we need to call the other number is
process correlator or context? Maybe its all in the naming? 

cheers,
jamal

[1] 
"A Sequence number should have a different sequential value has I hand 
messages from the PL to the TML.
A correlator should have distinct values for distinct requests, and
replies should have the value from the request.
These are not the same property.  They may even be in conflict."

---

From: Weiming Wang <[email-masked]>
Date: Thu, 16 Jun 2005 01:19:20 +0800

Robert,

Thanks for a more detailed explaination.

----- Original Message ----- 

Weiming,

[Weiming]I agree there is a different understanding to such a case. I don't think the response message will  result in a sequence number hole for the CE, because I only expect to define a sequence number that is used to mark the order of messages the CE originally generates , which should exclude response messages.  In another word, we will define that response messages only take a field that is only for correlating. Yes, such a definition of a SN will be problematic if the SN have to be used by TML for TML level flow control, but such SN usage has already been excluded.  We only leave SN for PL level use. My thought is such SN is useful and is also enough. 

[Weiming] Note that we also have to maintain two correlators, one is for CE and another is for FE, therefore, to have two SN parallelly maintained seems unavoidable.  Moreover, if we separate correlator from SN, we then need to maintain four parameters for them.  To  merge correlator and SN together is actually a very simple treatment, that is, to let a correlator be generated sequentially rather than randomly, without adding any other complexity, whereas benifits from  it is great: to ease the generation of a correlator in some way as well as providing a sequential information for sorts of messages, which are useful in some cases.

Moreover, consider the case for which the CE is pipelining commands 
(=sending more than one command at a time, i.e., not waiting for each 
response before sending the next command), then things become really 
hairy ...
[Weiming] As I mentioned, in this case, we should define to let the response SN (as the correlator) either with the pipelined commands' first message or last message. For instance, 
1. CE sends a pipeline message with SN of 21, 22, 23, 24, 25, then wait for the commitment response for the excution.
2. FE then may either response a message with SN=21, or SN=25, just as we'd like to define. Personally I think to define the last SN as the batch response may be better.

Thanks,
Weiming

---

From: Weiming Wang <[email-masked]>
Date: Thu, 16 Jun 2005 01:50:07 +0800

Jamal,

----- Original Message ----- 
From: "Jamal Hadi Salim" <[email-masked]>

> correct PL connection. How does it do this?

Firstly, I'm not sure if the two PL-TML connections actually imply, do you imply they'l have different and independant SN or correlator generator? I suppose either SN or correlator should all be consistently maintained by one PL core.

Secondly, I don't see any difficulty to demux responses in such case. It's just by the SN field which acts as a correlator, considering correlators generated by the PL core are always in this case. Maybe I still miss something?

> One answer is the TML maintains a lot of PL level knowledge. But this is
I actually think such demux should be done by a unique PL core rather than by TML(s). 

> connection. 
There might be multiple PL-TML threads created, but these threads should be all under control of only one process, that is, the core PL process. To try to parallelize the core process may be very difficut and may also be problematic. Of course, there may be multiple PL application processes though. 

Thanks,
Weiming

>We can therefore live with the command corelator being the

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 15 Jun 2005 14:41:44 -0400

Weiming, will it suffice for your purposes if there are two fields:

1) A sequence number.  Filled in sequentially by the sender of the 
message.  May be used by the receiver to detect gaps, misordering, etc.
2) A request-ID field.  On request messages, filled in by the request 
originator with any value suited to the requestors implementation and usage 
(may be a pointer, a counter, etc.)  On response messages, this will be 
filled in with the value from the request that is being responded to?

I understand that you argue that a (1) may be used to fill the purpose of 
(2).  Can you live with two fields?

Yours,
Joel

PS: My personal opinion is that (1) could be covered by (2), but not the 
reverse.  However, I can easily live with two fields.

---

From: Jamal Hadi Salim <[email-masked]>
Date: Wed, 15 Jun 2005 14:56:11 -0400

On Thu, 2005-16-06 at 01:50 +0800, Weiming Wang wrote:

> Firstly, I'm not sure if the two PL-TML connections actually 
> imply, do you imply they'l have different and independant SN or 
> correlator generator? I suppose either SN or correlator should 
> all be consistently maintained by one PL core.
>
> Secondly, I don't see any difficulty to demux responses in such 
> case. It's just by the SN field which acts as a correlator, considering 
> correlators generated by the PL core are always in this case. Maybe I 
> still miss something?

[..]
> There might be multiple PL-TML threads created, but these threads 
> should be all under control of only one process, that is, the core 
> PL process. 

Yes, thats how we do it in our implementation today (i.e with one
process)- what worries me is the enforcement of such implementation.
Robert and I have come up with two different approaches on how to
implement: i would say it is therefore insufficient to say there would
be one "core PL" mux point since his approach is to implement one
process per LFB. Unless, that is,  we are willing to sign on it and say
"you will only implement this way". If we are going to say that we
should say it in the draft. Then i will be sure my FE will interop with
Roberts CE.

The reason is:
We actually may have more than one app on the CE which _in my view_ may
have totaly independent things they configure at the FE. And in my view,
each such app should be able to use Forces as a transport and not need
to coordinate any sequence numbers. If you call each app a context, then
the correlator maps to the context. And in each context the whole range
of sequence numbers (I am begining to think this is a bad name) is
available. 
For our implementation, the only value such a context correlator would
add is reduced state at the CE. For Roberts, it would i suppose complete
his.

cheers,
jamal

---

From: "Wang,Weiming" <[email-masked]>
Date: Thu, 16 Jun 2005 17:26:10 +0800

Joel,

----- Original Message ----- 
From: "Joel M. Halpern" <[email-masked]>
Subject: Re: [issue54] correlator in the PL message header

> (may be a pointer, a counter, etc.)  
[Weiming] Even eventually we decide to use such reqeust-ID field, I suggest the value just be value of the sequence number in the message, which is the simplest way to generate the value.

>On response messages, this will be 
Compared with only one correlator field, this more fits my thought, though as I alreayd argued, it seems a little to waste something.

Yes, if you all think this is  a better solution, I can live with it.

> reverse.  However, I can easily live with two fields.

[Weiming] My thought is 2 can be covered by 1, but 1 can only partially cover 2. But I'm afraid this may only be a description difference. We may mean the same thing. : )

Thanks,
Weiming

---

From: Robert Haas <[email-masked]>
Date: Thu, 16 Jun 2005 18:33:16 +0200

The current practice seem to be for the Sequence Number (SN) in the 
Messager Header of all Responses to be set to the same value as the SN 
in the Message Header of the original message. Note that it is spelled 
as a SHOULD in the draft for the Query Response and Event Notifs, and 
not even mentioned at all for the Config Response, we need to correct 
this !
Note that this behavior is expected at the FE AND at the CE (the CE may 
generate Event Notification Responses).

Hence what we called SN in the draft is actually used as a transaction 
ID: it allows a response to be matched with the corresponding request, 
and it is therefore impossible to ensure that all messages generated by 
a sender to a receiver are numbered sequentially with this field unless 
you exclude from the sequencing, for instance :
- on the CE-to-FE direction: exclude Event Notif Responses
- on the FE-to-CE direction: exclude Config and Query Responses (one 
could choose to exclude instead the Packet Redir and Event Notification, 
but then the Config and Query messages with ACK flag off on the CE-to-FE 
direction must be excluded too otherwise they will create gaps on the 
FE-to-CE direction)

So, if the sequencing and transaction semantics are handled by the same 
field (SN), then it can only apply to a subset of the messages. 
Otherwise we have to introduce another field to handle proper sequencing 
independently from the transaction ID, or we drop sequencing completely 
and only keep the transaction semantics. What do you think ?

> message.  May be used by the receiver to detect gaps, misordering, etc.

As mentioned above, this deviates from the current use of the sequence 
number (=transaction ID). If the sequence number is now used for proper 
sequencing as you also seem to propose, then we have to introduce a 
separate transaction ID.

> originator with any value suited to the requestors implementation and 
> usage (may be a pointer, a counter, etc.)  On response messages, this 
> will be filled in with the value from the request that is being 
> responded to?

Agreed, this field remains opaque to the protocol; it is used like a 
cookie. The only requirement is that the receiver (CE or FE) copies it 
from requests into responses. I propose that this field is also 32 bits. 
Note I dislike the term request-ID because it implies that each request 
has a different ID.

>
> I understand that you argue that a (1) may be used to fill the purpose 
> of (2).  Can you live with two fields?
>
> Yours,
> Joel
>
> PS: My personal opinion is that (1) could be covered by (2), but not 
> the reverse.  However, I can easily live with two fields.

Note that I've shown above that you cannot cover (1) with (2), or only 
for a chosen subset of the messages.

Regards,
-Robert