Subject: [rbridge] FW: Pseudonode minimization thoughts...

From: "Thomas, Matthew R" <[email-masked]>
Date: Sat, 2 Feb 2008 01:01:51 -0000

Hi Radia,

Adding v quick tutorial as suggested... 

I have been involved in looking at this for a bit, but your original
solution is significantly more elegant, backwardly compatible, only 2
flags to add etc etc, than ospf-lite and more elegant.

Here is a summary as requested of the general discussion / explanation
from people so far. I hope I do them justice.. please forgive any errors

OSPF language (appologies if anyone not interested)
***************************************************************

Ospf works in a very similar way to ISIS. Two types of LSA are
generated. OSPF type 1 (router) you would refer to as a normal ISIS LSP.
Our type 2 (Network-LSA) is as your pseudonode LSP.

Our type 1 (router LSA) is very similar to your standard LSP. There are
a few oddities. Here is the main one I think: a point-to-point line has
two entries:

    Link connected to: another Router (point-to-point)
     (Link ID) Neighboring Router ID: 2.2.2.2
     (Link Data) Router Interface address: 172.16.1.1
      Number of TOS metrics: 0
       TOS 0 Metrics: 64

    Link connected to: a Stub Network
     (Link ID) Network/subnet number: 172.16.1.0
     (Link Data) Network Mask: 255.255.255.252
      Number of TOS metrics: 0
       TOS 0 Metrics: 64

This is a point-to-point line from this router (ID 1.1.1.1) to the
neighbour 2.2.2.2 The point-to-point line has local IP address
172.16.1.1. It is reported TWICE in the packet. Once as a point-to-point
line and then a second time to attach the IP network. This is all to
allow an IP unnumbered interface if required. If unnumbered then the
interface in the first block of text is represented by an MIB value.

Radia et al plan, configured for OSPF:
**************************************

1.) Use ospf LLS datablock Extended options to locate 2 flags.
2.) One flag (called NS-Bit) signifies to the other neighbors, the
compatability with the reduction draft.
3.) DR gets elected and Pseudonode LSP (Network-LSA) is not generated by
DR yet.
4.) DR signals to neighbors to move to pseudonode reduction using second
flag (SS-Bit).
5.) Neighbors set SS-Bit flag in accordance to signify acceptance.
6.) Router LSA (ISIS normal LSP) shows to the OUTSIDE world a network
type of "point-to-multipoint." Represented as lots of Point-to-point
lines (see below for example
7.) Routers actually operate on the LAN using DR as normal.

However! we already have a special network type called
point-to-multipoint that actually reduces the Network LSA anyway. So is
the problem solved already? Well partly...

Here are the problems not currently solved by P2MP (Point-to-multipoint)
alone (as I see it):
*****************************************************************

Problem 1: P2MP cant be configured as default, (to avoid configuration
issues). This is because a further router might be added to the network
that isn't configured to support point-to-multipoint. The hellos would
not match and the neighbour would not be established. This is the
current state.

Problem 2. We cant add flags to dynamically change the network to
point-to-multipoint, (on its own without your proposal) because if we
did then the  DR is removed (as P2MP doesn't use one), so cant change
BACK if another router is added that doesn't support
point-to-multipoint. (same problem as above).

Both of these problems are solved by continuing to use DR as normal, but
advertising in the router LSA's the "point-to-multipoint" option, which
looks like this below: This LSA is generated by router IS 1.1.1.1 and
the neighbors listed are 2.2.2.2, 3.3.3.3, and the network in question
is 192.168.1.0 255.255.255.0

  LS Type: Router Links
  Link State ID: 1.1.1.1
  Advertising Router: 1.1.1.1
  LS Seq Number: 80000002
  Checksum: 0xB5ED
  Length: 60
   Number of Links: 3

    Link connected to: another Router (point-to-point)
     (Link ID) Neighboring Router ID: 2.2.2.2
     (Link Data) Router Interface address: 192.168.1.1
      Number of TOS metrics: 0
       TOS 0 Metrics: 10

    Link connected to: another Router (point-to-point)
     (Link ID) Neighboring Router ID: 3.3.3.3
     (Link Data) Router Interface address: 192.168.1.1
      Number of TOS metrics: 0
       TOS 0 Metrics: 10

    Link connected to: a Stub Network
     (Link ID) Network/subnet number: 192.168.1.1
     (Link Data) Network Mask: 255.255.255.255 << note mask is 32
      Number of TOS metrics: 0
       TOS 0 Metrics: 0

Matthew Thomas

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Radia Perlman
Sent: 01 February 2008 18:48
To: Developing a hybrid router/bridge.
Subject: Re: [rbridge] Pseudonode minimization thoughts...

Here's a compromise proposal.

My goals:
a) no configuration required
b) no pseudonode if you have no router neighbors on the link (whether or

not there are endnodes).
c) avoid pseudonodes if easy to do so (explain in a minute) when there 
are just 2 routers (with perhaps endnodes)

Before Mike's arithmetic, I was thinking that pseudonodes weren't 
valuable until maybe 10 neighbors, and just was
embarrassed about the whole pseudonode thing in this brave new world 
where "Ethernets" are usually pt-to-pt links, but
now I think it's fine to simply *always* get rid of pseudonodes in the 
case of one router, and *almost always* in the case of
just two routers.

So, here's the proposal:
a) do not report a pseudonode unless there is at least one *IS* 
adjacency. This eliminates my nightmare of an unconfigured
RBridge with 1000 ports, each with one endnode on it, reporting 1000 
pseudonodes. (Les confirmed my nightmare, that
all it takes is a single ES adjacency on a port and IS-IS today would 
create a pseudonode for that port. We *really* have to
fix that case, and without requiring configuration)
b) if there is just one IS adjacency, and you are the DR, and your other

IS is cool with this feature (as signalled in its Hello), don't use a 
pseudonode.
Just have each of the two IS's report a link to the other.
If your neighbor IS isn't cool with it, go ahead and make an adjacency. 
(Note: for TRILL, I'd hope we'd put this feature in from the
start, so that all RBridges would be cool with this, so that is simple)
c) if there are ever 2 IS adjacencies on the port, create a pseudonode 
*and remember, as long as you are up,
that this link should have a pseudonode as long as there is at least one

IS adjacency*. In other words,
this is not really a pt-to-pt link, and it won't be wasteful to keep the

link with a pseudonode because there might be other
IS's that will come up in the future. I would drop the pseudonode (in 
the case of TRILL especially, maybe not for CLNP),
if there is ever no other IS adjacencies.

This is kind of like the original proposal but with the threshold of "1"

and "3" rather than "2" and "5", except once you hit 3, the
threshold becomes "1" and "2". So in this case R1 would do the following
a) no IS neighbors: no pseudonode. R1 reports nothing about that port in

its LSP, and does not report a pseudonode.
b) neighbor R2 comes up: no pseudonode: R1 just reports a link to R2 in 
its LSP. R2 reports a link to R1 in its LSP.
c) R3 comes up (two IS nbrs): R1 says "use pseudonode". R1, R2, and R3 
claim neighbor R1.25. R1.25 (the pseudonode name)
reports an LSP with neighbors R1, R2, R3.
d) R3 dies, leaving just R1 and R2: still pseudonode. R1.25 reissued, 
with just R1 and R2 reported. R3's LSP dies of old age.
e) R2 dies (so there is just R1): no pseudonode. R1 does not report any 
adjacencies for that port. R1 reissues its LSP
without R1.25 in it. R1.25's LSP dies of old age (or is given a 
premature death by R1)
f) R2 comes up: R1 says "use pseudonode". R2 issues its first LSP saying

it is connected to R1.25. R1 adds R1.25 to its LSP,
and issues R1.25's LSP with neighbors R1 and R2.

Note I think pseudonode minimization might not work for OSPF, since if I

remember correctly, OSPF reports some things in
the pseudonode LSA (type 2?) like the IP prefix for that link, that I 
think cannot go in
a non-pseudonode LSA (type 1?). So I think OSPF needs a pseudonode for
every link. (is this true?). But TRILL IS-IS has *no* information in the

pseudonode LSP other than reporting router neighbors.

Radia

mike shand wrote:
> On 31/01/2008 mike shand wrote:
>   
>> I'm not even convinced it simplifies the SPF, but since an SPF for a 
>> several hundred node network takes < 1mS, I don't see this as a big 
>> issue either way. However for a 15 node LAN, WITH pseudonode you
explore 
>> 1 hop to the PN then 14 hops to the other nodes, then check on back
link 
>> from each of the 14 to the PN (i.e 29 links). In the non PN case you 
>> explore 14 hops, then another 14 hops back from each of those 14
(i.e. 
>> 210 links). It would need a better analysis to determine exactly what

>> the relative merits are, but at best I would say it is a wash, and it

>>
>> might even be a pessimisation not to have a PN.
>>   
>>     
> I couldn't resist conducting the experiment:-) For what its worth, my 
> simulation seems to indicate that the SPF is faster WITH the
pseudonodes 
> than without, at least for 4 node LANs and above.
>
> I constructed a network consisting of 4 LANs each containing 4
routers. 
> The groups of routers were randomly interconnected with point to point

> links.
>
> The average time to run an SPF WITH pseudonodes was 52 uS, and without

> pseudonodes (i.e. each "LAN" of 4 routers was replaced by a fully
meshed 
> set of pt-pt links... each router connected to the 3 other routers on 
> the "LAN", was 64uS.
>
> The absolute values are irrelevant, but it does seem to indicate that,

> for 4 node LANs, the SPF is faster with pseudonodes.
>
>
> As I said, I don't think this matters at all; it is lost in the noise,

> but it certainly can't be said that it is BETTER not to have the 
> pseudonodes from the SPF point of view.
>
>     Mike
>
> _______________________________________________
> rbridge mailing list
> [email-masked]
> http://mailman.postel.org/mailman/listinfo/rbridge
>   

_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: "Thomas, Matthew R" <[email-masked]>
Date: Sat, 2 Feb 2008 01:39:14 -0000

In terms of threshold,

For OSPF a variable would be most useful. The ability to set it to say 5
as standard and then reduce to 3 as described from time to time would be
most useful. One of the advantages of this proposal is that the values
can be set differently from LAN to LAN without a problem, and there is
no requirement to upgrade all of your routers /Rbridges at the same
time.

MT

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On
Behalf Of Thomas, Matthew R
Sent: 02 February 2008 01:02
To: [email-masked]
Cc: [email-masked]
Subject: [rbridge] FW: Pseudonode minimization thoughts...

Hi Radia,

  LS Type: Router Links
  Link State ID: 1.1.1.1

Matthew Thomas

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

My goals:

not there are endnodes).

So, here's the proposal:

Radia

explore 
link 
(i.e. 

pseudonodes 
routers. 

meshed