Subject: Re: Ambiguity in BLOCK semantics

From: "Putzolu, David" <[email-masked]>
Date: Fri, 11 Feb 2005 19:20:57 -0800

Comments inline...(hat off as usual) 

> -----Original Message-----
> From: Forwarding and Control Element Separation 
> [mailto:[email-masked]] On Behalf Of Jamal Hadi Salim
> Sent: Friday, February 11, 2005 1:09 PM
> To: [email-masked]
> Subject: Re: [FORCES] Ambiguity in BLOCK semantics
> 
> On Fri, 2005-02-11 at 12:38, Robert Haas wrote:
> > To summarize the ambiguity with the use of a BLOCK 
> construct, here is an 
> > illustration that should help:
> >
> > 
> > With only DATARAWs following the BLOCK construct, no ambiguity :
> > 
> >   For table entries 4 5 6, (BLOCK construct selection)
> >   (each table entry has fields name, surname, address)
> >     set entry with (a,b,c)
> >     set entry with (d,e,f)
> >     set entry with (g,h,i)
> > 
> > necessarily results in:
> > 
> > {...,(a,b,c),(d,e,f),(g,h,i),...}
> > 
> 
> The semantics are pretty simple.
> 
> 1) "Find the target first" - this is like a classifier filter "match"
> and is provided by the path + selector
> 2) Once you find the target, apply the SET data (this is like 
> the filter
> action)
> 
> In your case above zone on table:rows 4,5,6; apply the data in order.
> 
> 
> > As a potential optimization, if all table entries are set 
> with the same 
> > value (a,b,c), then instead of writing:
> >  
> >   For table entries 4 5 6,
> >   (each table entry has fields name, surname, address)
> >     set entry with (a,b,c)
> >     set entry with (a,b,c)
> >     set entry with (a,b,c)
> 
> This is also legit, but not efficient, given the commonality of the
> data set.
> 
> > one could also write:
> > 
> >   For table entries 4 5 6,
> >   (each table entry has fields name, surname, address)
> >     set entry with (a,b,c)
> > 
> 
> This fixes the efficiency issue above.

I can see that the second is more efficient.  I question whether
it really is necessary however.  In reading the above I tried to
come up with a compelling (real-world) example. The best one that
came to mind was a next-hop router going down.  I.e. imagine a
routing rable as follows:

Dest IP         Mask      -->       Next Hop IP
-----------------------------------------------
134.134.10.10  255.255.0.0       134.134.10.251
150.10.5.17    255.0.0.0         134.134.10.251
117.5.23.4     255.255.255.0     134.134.10.251
(default route)0.0.0.0           92.10.10.251

In the above example, the router in question has two next-hops it
might forward to - one at 134.134.10.251, one at 92.10.10.251.
If the first of the two next-hops above goes down, I could see
a case where one would want to identically replace multiple table
entries with the same data, i.e. replace the Next Hop IP on rows
1, 2, and 3 with the Next Hop IP on row 4.

However, upon a bit more reflection, I don't really think it
is necessary to provide protocol support for this operation.
Instead, it should be solved by correctly defining the LFB
used for (in this example) IP forwarding, i.e. by adding
indirection:

Dest IP         Mask      -->       Next Hop IP Identifier
----------------------------------------------------------
134.134.10.10  255.255.0.0                    1
150.10.5.17    255.0.0.0                      1
117.5.23.4     255.255.255.0                  1
(default route)0.0.0.0                        2

Next Hop IP Identifier --> Next Hop IP Addr
-------------------------------------------
     1                       134.134.10.251
     2                       92.10.10.251

In this case, if the next hop router at 134.134.10.251 goes down,
one simply updates the 1st row in the the identifier->addr table
above with the IP address of the default router (92.10.10.251).

My gut feeling is that any common example where one wants the 
ability to do "replace rows 1, 2, and 3 with identical value A" is 
probably solvable by better LFB definition (via indirection) 
instead of adding this operation to the protocol.  Furthermore, 
intelligently defining the LFBs to address such common examples 
should be expected - adding protocol operations to compensate 
for poor LFB definition would be a bad thing.

Regards,
David

---

From: Alia Atlas <[email-masked]>
Date: Sat, 12 Feb 2005 00:17:20 -0500

>Dest IP         Mask      -->       Next Hop IP

In the above example for the indirection, consider the case where there's a 
group of prefixes that pointed at a single Next Hop IP Identifier (1 as 
above).  Now, as the result of a change, subset A wants to change to use 
the Next-Hop IP Identifier 2  and subset B wants to change to use the 
Next-Hop IP identifier 3.   I don't believe this can be solved via better 
LFB definition.

The use of better LFB definition with indirection only solves the set of 
cases where the set  doesn't need to be broken up or new sets created.

Alia

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 12 Feb 2005 00:41:54 -0500

While thinking about this case (which is the one almost everyone seems to 
come up with independently) I was struck by the fact that the actual LFB 
structure will likely be more complex.
I would expect that the table with the IP address and prefix length will 
have a subtable of next-hop information to support ECMP.
Given that the entries which will need to be update will have different 
subscripts in different base entries, it seems that the use of this "apply 
all path-data to all selected entitites" gets harder and less applicable.

It is true that one can construct cases where it applies.
And they might turn out to be common.

It is also true that we can add selectors to the protocol later.  With very 
little complication.

Yours,
Joel

At 12:17 AM 2/12/2005, Alia Atlas wrote:

>In the above example for the indirection, consider the case where there's 
>a group of prefixes that pointed at a single Next Hop IP Identifier (1 as

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sat, 12 Feb 2005 11:24:45 -0500

> structure will likely be more complex.

I think the main challenge is that the LFB may need to be more
accomodating. We cant assume a certain "design". The indirection example
will make it really easy to parse for some FEs but not others; i know of
ASICs where that would be a real nice straight mapping (since they do
have such indirections) and of others where this would a complete pain
and would require the intervention of the CE to chew things  into
something along the first example from David. Whats more interesting is
i have seen desire to have NH as a LFB on its own right where the NHID
would infact be an alias; 

> have a subtable of next-hop information to support ECMP.

And indeed this will make the case even more applicable.

> all path-data to all selected entitites" gets harder and less applicable.

There are a lot of use cases other than the one above (refer to the
different ASIC models talk above); one thats applicable to me (dont know
how common this is) is to change the MAC addresses of the NH in one shot
in many many entries in an L2 table - the faster i can do this the
better; it is very common for my case in rerouting/failover scenarios.
Not sure about the rest of the world.

Another place where this is applicable:
a) There are tables where you could instantiate rows but not activate
many rows; and then later issue "activate all in rows 1000-2000"
or something along those lines. Essentialy some boolean set or reset.

b) Scenario where i want to instantiate and initialize either a whole
table or range of row entries with the same values.

etc

> It is also true that we can add selectors to the protocol later.  With very 

Again like i mentioned earlier if we want to start simple, we might as
well kill keys - because even that is an efficiency vehicle; the CE
could do the chweing and have the FEs do a little more work.

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 12 Feb 2005 11:36:31 -0500

I would like to ask the question differently.

I will grant that there will be some cases where the block construct, with 
outer product semantics (apply all following path-datas to all selected 
block entries) will be useful.
We know that the same operations can be performed without the block selectors.
We do not know how often the block will be useful.  Or how large the blocks 
will be (which ought to dominate the efficiency calculation.)

We do know that the 1-1 semantics also applies to many cases.
We don't know how often the 1-1 semantics would be useful, or how much it 
would help.

We do know that we can add block TLVs later if we need to.

Given the relationship between what we do know and what we don't know, 
wouldn't it make more sense to defer he block?
Note that we will still have the ability to handle the most important 
block:  setting or getting an entire table.  That is clearly needed, and is 
covered by the structure without block selectors.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sat, 12 Feb 2005 13:07:07 -0500

Joel,

I dont see any complexity adding BLKs. I think now that weve discovered
we have different semantical connotations on what we mean by what
follows a selector, we may never reach a compromise (I contend its
complex just because of how you intepret what follows the selctor). I
could susbtitute everything you said about the BLK and show you that you
will have the same issue with KEYs in a cross product given the selector
interpretation. The issue is the selector IMO - the only reason we have
it is to improve efficiency of on the wire bits and parsing/compute
reduction.

How about this as a middle ground (because i cant think of a good way we
can close this): 
Lets Keep those flags on the path; lets just have the draft talk that
BLK is defered for now[1] and will be revisited later. Keeping the flags
will guarantee that we can add them back if we ned to.

cheers,
jamal

[1] I Know i will implement BLK even if it is to prove i am foolish - at
this point i feel i will have better perfomance numbers (throughput and
latency) than someone who doesnt in both real world(small CPUs, lots of
IO, shared bandwidth etc) as well as benchmark scenarios for the same
work set and same hardware.

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 12 Feb 2005 13:12:37 -0500

I can live with that.
Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 13 Feb 2005 23:01:01 -0500

It would be nice to hear from Weiming on this topic.

cheers,
jamal