Subject: Re: Support for multicast in the ForCES protocol

From: "Putzolu, David" <[email-masked]>
Date: Fri, 21 Nov 2003 13:50:40 -0800

Jon Maloy wrote>
David Putzolu wrote> >
> > For #3, the same TCP connection can be used in unicast. In
> > multicast, either the same multicast connection is used
> > (this results in every FE seeing every other FE's ack - yuck!)
> > or a separate TCP connection must be maintained by the FE to
> > the CE.

> The multicast ack case does not sound that horrible to me, but there
> _will_ have to be (some kind of) connections FE-CE anyway, - most
> messages are still not multicast. The bottom line is, no base protocol
> in this world can fulfil this requirement, the acks have to be sent 
> user-to-user, and we are back to the "ack storm" scenario.

Hi Jon.

I agree that the CE will see a lot of acks (as many as there
are FEs) in this scenario whether unicast or multicast is used -
it is unavoidable (and is actually the desired behavior - the
CE wants to know that every FE received and successfully 
processed the FIB update).

I was more worried about what the FEs would see.  In particular,
I believe that if the same mcast grp is used for CE->FE *and* the 
response FE->CE ACK, the difference is that not only will the CE 
see N ACKs (desired behavior),  but each FE would also see the 
N-1 acks from all the other FEs as well (not desirable).  FEs 
are assumed to be fairly dumb boxes, and inundating them with 
ACKs from other FEs to process (at least far enough to know to 
discard them) precisely at the time of arrival of a route update 
would be a bad thing.

The only solution I saw to this is to use multicast in
CE->FE communication, and unicast in FE->CE communication - this
"shields" the other FEs from having to listen to (and at least
partially parse) each other ACKing.  One could use probabilistic
ACKing, but I don't think any operator would be comfortable
knowing that one or more of their line cards may have failed
to add a route until the next time they add a route.

> > For #5, in the unicast case, a single message could contain
> > transaction information and a set of sub-messages.  In the
> > multicast case I cannot off the top of my head come up with
> > a mechanism to even support transactioning.

> Why is this different ? Each FE receiving the multicast with bundled
> sub-messages performs defines a local transaction and reports the
> result back to the sender. It may be tricky, but not different from
the
> TCP based dito.

I was assuming a unicast approach something like the following
(using an XML-like notation for simplicity, the wire 
representation would likely be different):

<Transaction>
  <TransactionID>138</TransactionID> // A nonce indifying the xaction
  <LFBCommand>          // Start of a command to a LFB
    <LFBID>17</LFBID>   // Indicates what LFB this command targets
                        // in this case the IPv4 FIB LFB
    <PrefixAdd>         // This is a prefix add command, for FIB LFB
       <NetAddr>158.0.0.0</NetAddr>
       <PrefLen>8</PrefLen>
       ...
    </PrefixAdd>
  </LFBCommand>         // End of the first command in the transaction
  <LFBCommand>
    <LFBID>23</LFBID>   // Some other LFB that we want to be atomically
                        // updated with the FIB update above
    ...                 // Body of the second command.
  </LFBCommand>
  ...                   // More commands
</Transaction>          // End of the transaction

Upon receiving the above via unicast, a FE would manipulate 
LFB 17 with the prefix add,  LFB 32 with whatever command 
was applied to it, etc., using all-or-nothing semantics.  
Because the command is unicast to the FE, the LFB identifiers
used in the transaction indicate what particular 
LFBs to do the all-or-nothing semantics with.

In the multicast case, I assume each FE would have a different set
of IDs for the LFBs (perhaps the IPv4 FIB LFB would be #17 on
FE#1, but would be #12 on FE#2. So just multicasting the above 
message would not make any sense.

In the non-transactioned case, I assume the mcast group tells
the FE what LFB to deliver a message to.  One could try to reuse
that mechanism, but that requires either that one know a priori
all possible combinations of LFBs across FEs that might be
transactioned together (to allocate necessary groups in pre-
association time), or one could just brute force it, allocating
enough multicast groups to cover all cases (but that would cause
a factorial explosion so isn't feasible).

So the conclusion I came to was that for using multicast to
carry transactions one would have to either assume that every 
FE had the identical set of LFBs being addressed, in terms of
transaction ID, data being pushed down, and LFB instance IDs,
every time a transaction is used.  This is of course in addition
to requiring proper ordering & non-corruption of packets.  I
suspect that making the above assumption is not safe - different
LFBs are likely to be addressed in each FE (either different
instance IDs of the same type, or different types).  Different
data per FE (LFB instance IDs, transaction IDs) takes away the 
benefit of multicast, which primarily holds when data is the 
same for all receivers.

-David

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sat, 22 Nov 2003 11:29:59 -0500

Continuation of the last thread with a change in topic - i think these
are the real issues that need to be addressed instead of the distraction
to "multicast is evil".

Lets really list the requirements needed for a successful underlying
transport protocol that will serve ForCES well. i may be
missing some - but i hope to get challenged so i can add to them;
I am thinking of turning this into a draft so people read it first and
then post.
My previous email has some more claims which i will assume here.

I. ForCES  mechanisms requiring reliability:

a) time limit very sensitive (in other words obsolence period is
faster):
Example table updates;
I have argued TCP doesnt qualify in my previous email. SCTP-PR may
qualify.
Something like what netlink2 over UDP qualifies because it gives control
to netlink2 to make such decisions.

b) time limit best effort (obsolence takes longer)
Sample apps: File transfers,etc.
TCP qualifies but AFAIK, we dont have this need.

II.  mechanisms capable of tolerating unreliability: Example psamp.
TCP doesnt qualify.
something(like netlink2) over UDP or SCTP-PR.

III. mechanisms that prefer timeliness over reliability: Ex heartbeats
something (like netlink2) over UDP or SCTP-PR.

Clearly in the bigger picture TCP is not the best protocol.
UDP and SCTP-PR qualify partially merely because they dont hinder
progress not because they have some magic. Another non-IETF protocol
that would qualify is TIPC. I havent carefully studied DCCP but i
believe it also has a fit. I will exclude it because its not there yet.

So, to summarize: the transport protocol that meets all the requirements
For Forces has not been born.

Choosing TCP is choosing an answer and then trying to justify the
questions that it brings. It does sound like peer pressure instead of
looking at requirements and then deciding what you need to do.
I think we recognized this in netlink2 and made it clear that the choice
of underlying protocol chosen is up to the pre-association phase.
We compensate for "missing features" depending on the transport choice
(read the draft).
It's very few lines of code to provide that luxury. So the cost is low.

Now on the choice of netlink2 UDP vs SCTP-PR

1) UDP is here today. SCTP-PR is not. When SCTP-PR becomes available
Netlink2 can run over it. For now we choose to be standalone: We can run
over IP, over UDP or over ethernet, you take your pick.

2) UDP provides multicast (and broadcast). SCTP-PR does not.
Since SCTP has turned to be a swiss knife (or maybe a multi faceted
beast), i am sure it will soon as well support multicast;->

If multicast is there - we will use it. Sans that we will do something
multicast like (Jon calls it unireplicate i think).
All the three cauthors have had pleasant experiences using multicast for
ForCES like. We think it is a good thing to have. But we will not
torture you if you dont have multicast or broadcast ;->

Why Multicast is useful:
--
I must apologize since i have to repeat this.
In the simple case of a single multicast wire: each of the CEs or FEs
opens a single multicast socket/channel.

Why is this good:

1) Bandwidth is less used
a)because one or more CEs can send a single message to all FEs.
I really dont want to be teaching people the hows but i will provide one
example which David or maybe it was Joel didnt seem to make sense out of
(but one that i have successfuly used)[1]
b) you can reduce the number of packets further by limiting on
ACKs (partial acks)

2) RAM on the embedded CE or FE is used less. There are less sockets
open and less messages being built

3) CPU is preserved more.
Since there are fewer messages to process and fewer (socket states)
states to track.

4) The ability for all listeners on the wire to see message exchanges
even when not directed at them provides a cheap way to synchronize.

5) At a transport level, (not the forces transaction level), having
access to multicast provides location transparency.

6) A lot of switch fabrics (shared memory designs or otherwise)
interconnecting FEs and CES have multicast capabilities; so it is good
if we can take advantage of it where possible.

The above is the simple case, by induction you could extend the
reasoning to the case where you have X sockets.

I dont want to preach multicast as panacea; we address some of the
limitations in the draft; however, i want it to be available when i need
it and not shoved down the toilet.

So far apart from Joel (who implemented on ATM) on real boxes and Ram
(who did something very specific that needs unicast) the rest of the
arguements i have seen are from people who see the need for this
feature. You can choose to ignore it - and you may be influenced by some
implementation you are familiar with - thats your loss. I do think TCP
is valid for some cases (low latency and congestion), but i wouldnt
claim it to be the answer weve all been waiting for.
Again let me reiterate that Netlink2 does not need to have multicast (it
is a MAY) but would love to have it when it is available. We can run on
your favorite protocol TCP ;->

cheers,
jamal

[1] I will give the example in another email - this one is already
getting too long.

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 22 Nov 2003 17:02:22 -0500

For the control protocol (not for the encapsulation of data between the CE
and the FE, I have to disagree.
I think that every transaction must be transferred successfully, and in order.
Otherwise, ensuring the CE properly understands the state of the FE is
extremely difficult.

Note that your argument about extreme delay is probably a red herring.  If
transactions are being delayed that long, the communication needs to be
declared down, and you start over with a clean slate.  This has very little
relationship to actual protocol behavior.

Yours,
Joel M. Halpern

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sat, 22 Nov 2003 21:28:14 -0500

> representation would likely be different):

Ok, thanks for providing this because it cleared some confusion as to
what angle you are looking at things.
We are being bitten by lack of some NPF document again (i saw your
description before in my brief glance of an NPF doc at MPLS). As i
mentioned the need for NPF documents is to at least understand what one
is arguing against. We would have saved a lot of bandwith on this
thread.
I am glad i took a break and came back and read all these messages. I
dont need to give an example anymore, this is a good one;->
Again, thanks for providing this.

> message would not make any sense.

Why would the LFBID change depending on whether it was unicast or
multicast? The LFBID would stay pretty static across FEs,
and is probably issued by IANA.
Lets take the case of netlink2 running on top of multicast.
[Refer to netlink2 current draft section 5.1 for the header.]
-cmd/type = RTM_NEWROUTE which is essentially saying "this is directed
to the IPV4 Forwarding LFB to add the entry(ies) associated with this
message"
-Destination PID = either a specific FEs proxy for IPV4 LFB,
or the "all IPV4 LFBs",  or directly targeting a specific LFB.
Refer to section 8.4.2.1 "IPv4 and IPv6 Forwarding LFB Template".
The template is infact an encapsulator of a IPV4 LFB _transaction_
i.e not only does it include the prefix entry needed for the transaction
but also the nexthop gateway. I suspect the nexthop gw is what you were
trying to do with your LFBID = 23.
A transaction like the above could be encapsulated in a message in the
simple case within a single UDP PDU. To illustrate, it will be sent on a
UDP socket on port 5000 to a multicast IP address.
Does that clarify things? If it gets sent on that multicast address,
and three FEs are joined to it, all three will see it. All three may ACK
it. Or two may ACK and one will send a NACK. Or partial ACKS may be
used. Or one of the FEs may be passive synchronizing state as a backup.
etc.
Does this clarify how multicast is being used by netlink2? Its merely a
transport which when available is used.

> the FE what LFB to deliver a message to.

I am begining to understand where all the confusion was coming from.
I have to say i found it strange when i saw mentions of multicast groups
per LFB that were posted earlier. Please make those NPF documents
available.
The LFB message for a single transaction must be sent on the same
multicast group or you dont save much. The RTM_* netlink2 template puts
them together, so it is a non-issue. The NPF document i believe
separates the nh gw from the IPV4 Prefix to be two separate LFBs - too
fine grained and very very implementation specific IMO. If they are part
of the same transaction, it may not make sense to separate them - when
will a next hop be configured without a route to associate with? I would
encourage that we demarcate the concept of LFBs at the transaction
level, not every little table that exists on a device. It will help
making it a lot non-hardware specific.
That is why you need to have it in one message like you attempted to
(but left out i.e LFBID 23). You can go fine grained and separate them,
but you better make sure you have atomicity to make their updates a
single transaction.
BTW, all these details have been explained in a few presentations at the
WG on netlink2 and rather painfully laboriously in the draft.
You could jump to:
page 30 "section 7.5.5 Atomicity and Ordering of Transactions".

> One could try to reuse

Think transaction level (the way netlink2 does) and you will feel much
better.
A transaction configuration always goes onto the same wire.
I think the problem with the NPF model is it is too fine grained.
It follows what MIT Click and infact abuses it by implying each table to
be an LFB. This may make sense for something like a meter. It doesnt for
IPV4/6 Forwarding.
You need to group a number of tables together to form a meaningful
service. You can then refer to that as an LFB.
You may think you are being clever, but some devices may infact _not_
separate the GW and L3 tables i.e they are closely intertwined.

> benefit of multicast, which primarily holds when data is the

That may be true for the other proposed protocols, it is not for
netlink2.
I strongly recommend reading the netlink2 draft then lets discuss
further. And you really oughta make those docs available if you want to
save bandwidth (in the same manner that multicast does;->).

cheers,
jamal

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sat, 22 Nov 2003 21:38:53 -0500

> Otherwise, ensuring the CE properly understands the state of the FE is

Thats the transaction level not the transport protocol level. And we
dont disagree there.

> relationship to actual protocol behavior.

I take it you had no issue with the other points mentioned otherwise
you would have said something about them?
I am afraid, the extreme delay is as much a red herring (it is there to
illustrate a point) as multicast "would complicate things" or "multicast
is only useful if you have a lot of updates per unit of time" .

Maybe ive said enough for today.

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 22 Nov 2003 23:34:58 -0500

My both our own agreement and the direction we have been given, we have to
deal with flow control, retransmission, and congestion control in the
transfer of ForCES control messages.  (And security.)  With TCP / SCTP for
Unicast we get those things.  With UDP, we will have to redefine all those
behaviors for ourselves.  With Multicast, all those things are
significantly more complex.  (The correct semantics for multicast flow
control even in a limited environment are tricky, for example.)

Now, if there is a substantial benefit to the use of multicast, then it may
be worth our while to support it.
If there are protocols hooks that can easily be put in now that would allow
addition of full support for multicast later, those are worth considering
if there is a reasonable value to multicast.
But otherwise it seems sensible to just stick to unicast.

Remember that as a general rule optional mechanisms (even simple optional
mechanisms) are a source of interoperability failures.

Yours,
Joel M. Halpern

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 23 Nov 2003 11:00:52 -0500

Sigh. We are back to square one. We have two religious views based on
our implementation experiences. Ive just spent 10 emails explaining why
i dont think TCP is sufficient by itself and why multicast transport is
useful;-> Ive been on enough threads on usenet and email to wisen up
and know when to stop.[1]
This is the point where reasonable people agree to disagree and end the
discussion. If this was an implementation this is where we fork ;->

cheers,
jamal

PS: Selection of what gets used for transport is a pre-association
config issue not sure what you see as being interoperable with that.

[1]Otherwise you will make me repeat everything i said in the last 10
emails and you will then repeat exactly what you say below. Its a
vicious cycle - you have not changed my views on multicast and neither
have i changed yours.