Subject: [rbridge] End station discovery/liveness detection

From: zinin at psg.com (Alex Zinin)
Date: Thu, 3 Mar 2005 11:04:08 -0800

Radia, et al-

 In reviewing the RBRIDGE proposal within the IESG, I've been evaluating its
 scaling properties. I'd like to clarify how exactly it is envisioned to
 discover new and detect unreachable end stations.

 In particular, I'm interested in what kind of time-outs we're looking at for
 traffic- and ARP/ND-based proposals. I also remember seeing a discussion about
 disadvantages of the ARP-based method in the meeting minutes. Was there a
 decision one way or the other?

-- 
Alex
http://www.psg.com/~zinin

---

From: Radia.Perlman at Sun.COM (Radia Perlman)
Date: Thu, 03 Mar 2005 11:43:44 -0800

Well, it's trivial to do no better or worse than bridges. Just learn 
from seeing data
packets and use the same timeouts as bridges do for station learning.

However, there is an opportunity to do better, and I think the WG should 
decide
what optimizations are worth doing.

Some of the possibilities:
a) have the DB on endnode E's LAN "keep tabs" on whether E is still there by
checking up on it (with periodic ARP/ND queries, for instance). The possible
downside of this is devices that want to go to sleep and save power. 
It's possible
this is only an issue on wireless links, but it should be discussed.
b) have the DB only check if E is there if E gets reported by some other 
DB as
existing in some other part of the campus. Then the DB can check to see if E
has indeed moved, or might perhaps be multiply connected (though multiple
connections with layer 2 is/should be illegal with bridges, so perhaps 
we shouldn't
say that it is not allowed because I'm sure mixing bridges and RBridges will
cause weird situations if we allow a layer 2 address to exist in 
multiple locations).

The other issue discussed was whether ARP/ND queries for E should be 
optimized.
The simplest thing would be doing exactly what bridges would 
do...forward all
queries through the spanning tree. But I think it would be nice to 
optimize so
that at least some of the time the DB proxies the answer, or routes the 
query to
where the DB thinks E is located (then there wouldn't be a false 
reply...only if
E is actually alive will it respond). Some combination can be done.

The cases people are worried about are:
a) E dies, but looks alive to S when S does an ARP/ND query because the S's
DB proxy ARPs. I don't think this is that bad a situation, though, 
because if E
died after responding to S's query, S still has to have some way of 
coping. The
RBridge timers won't keep E around forever. Without bridges or RBridges,
there are always issues with caches like ARP caches, or router-router links
that haven't yet missed n hellos, etc.
b) E moves, but the RBridges don't notice. Again, if E doesn't say 
something, bridges
won't forward traffic to E properly either.

But as I said, it is trivial to be at least as good as bridges at end 
station discovery/liveness
detection. The only question is should we take advantage of the fact 
that RBridges
can do better.

Radia

---

From: zinin at psg.com (Alex Zinin)
Date: Thu, 3 Mar 2005 15:36:48 -0800

Radia,

  That didn't answer my question about timing ;) Anyway, I'll explain what I
  have in mind.

  MAC address info would account for the largest portion of information
  distributed in the link-state routing protocol running in rbridges. Hence,
  it's important to understand the change dynamics for it, as this will affect
  how much information will be flooded around, and as a result affect
  scalability of the technology. Without trying to pin it down here and now, I'd
  like to understand what we can and can't get here.

  If rbridges use the method currently used in bridges, i.e. install a new MAC
  entry when a data frame is seen from the station, and remove it if the station
  hasn't been heard from for about 5-15 minutes, we will be seeing more dynamic
  state changes than if we used the control traffic-based approach. In other
  words, we'd be announcing end station activity information rather than end
  station reachability, and the former is likely to change faster, and thus
  cause the switch to reoriginate and reflood its link-state information more
  often. We would need something better than that for rbridges to scale.

  I need to think a little about control protocol probing...

---

From: Radia.Perlman at Sun.COM (Radia Perlman)
Date: Thu, 03 Mar 2005 16:04:45 -0800

Well, endnode reachability information in and of itself is not a 
problem, because
as those that remember DECnet (and CLNP)  that's what level 1 routers
passed around. The difference was that DECnet/CLNP had the advantage of 
having endnodes
proactively advertise. I think very large flag CLNP networks were 
deployed, and
worked better than bridged topologies of the same size.

But Ales, I think you are arguing that instead of reporting endnode 
up/down status
we are reporting endnode active/quiet status, which would be more volatile.

That argument I think argues for having the DB check up on the endnodes, 
so that
the DB is indeed arguing for aliveness rather than "recent activity". 
This can be
done for IP nodes, because we know how to make them talk (ARP, ND). Not
sure what other non-IP protocols are widely deployed, and how it would be
best to keep tabs on who is still there.

One optimization that come to mind is leaving E in your link state 
information unless
you see it pop up elsewhere. If E is dead, then it's not reachable 
anyway. It's no
different than assuming E is on link L based on its IP prefix. The 
obvious thing
to worry about is that E has moved, it has spoken, but nobody noticed it has
moved becausewhat it said when it came up in the new location
got lost.

To handle that case, we could have the DB, R, in the case where R
has reported E as being attached, but R hasn't verified that information
in "a long time", then R can continue assuming E is alive and well and still
connected, until someone attempts to talk to E.
If E is dead or not there and nobody wants to talk to E,
then who cares. But if E might have moved, then at the point of 
delivering data to it,
is a good time to check to make sure it's still there, so at that point 
R can do an ARP/ND
query to reassure itself that E is actually there.

Another optimization is pure data compression. Having link state 
information that reports
all the attached endnodes, with locally assigned dense nicknames (R 
reports 1=Alice,
2=George, 3=Debra, ...etc). Then R can report the up/down status of all 
its endnodes
as a bitmask.

Radia

---

From: zinin at psg.com (Alex Zinin)
Date: Thu, 3 Mar 2005 16:42:56 -0800

Radia,

Thursday, March 3, 2005, 4:04:45 PM, Radia Perlman wrote:
> Well, endnode reachability information in and of itself is not a problem,
> because as those that remember DECnet (and CLNP) that's what level 1 routers
> passed around. The difference was that DECnet/CLNP had the advantage of having
> endnodes proactively advertise. I think very large flag CLNP networks were
> deployed, and worked better than bridged topologies of the same size.

How large was "large", if you remember?

> But Ales, I think you are arguing that instead of reporting endnode up/down
> status we are reporting endnode active/quiet status, which would be more
> volatile.

Exactly.

> That argument I think argues for having the DB check up on the endnodes, so
> that the DB is indeed arguing for aliveness rather than "recent activity".
> This can be done for IP nodes, because we know how to make them talk (ARP,
> ND). Not sure what other non-IP protocols are widely deployed, and how it
> would be best to keep tabs on who is still there.

IPX and NetBEUI are probably the most widely spread in enterprise LANs.
See below.

> One optimization that come to mind is leaving E in your link state information
> unless you see it pop up elsewhere. If E is dead, then it's not reachable
> anyway. It's no different than assuming E is on link L based on its IP prefix.

Yes, I was thinking in the direction of "presumption of reachability". I.e.,
once you've seen it on the the port, assume it's still there unless you've got
an explicit evidence that it's not, at which time you start actively looking for
truth by probing or aging the entry out in the absence of traffic from it.

> The obvious thing to worry about is that E has moved, it has spoken, but
> nobody noticed it has moved becausewhat it said when it came up in the new
> location got lost.

If positive reachability can be identified based on both traffic and control
messages, that shouldn't happen.

> To handle that case, we could have the DB, R, in the case where R has reported
> E as being attached, but R hasn't verified that information in "a long time",
> then R can continue assuming E is alive and well and still connected, until
> someone attempts to talk to E. If E is dead or not there and nobody wants to
> talk to E, then who cares. But if E might have moved, then at the point of
> delivering data to it, is a good time to check to make sure it's still there,
> so at that point R can do an ARP/ND query to reassure itself that E is
> actually there.

One case that I worry about is when a station moves and its address is announced
by two rbridges for some time, because the old rbridge hasn't had enough time to
make sure the station is really down. Some of the traffic will be delivered to
the old location.

> Another optimization is pure data compression. Having link state information
> that reports all the attached endnodes, with locally assigned dense nicknames
> (R reports 1=Alice, 2=George, 3=Debra, ...etc). Then R can report the up/down
> status of all its endnodes as a bitmask.

That would have a visible advantage only in cases where multiple end stations
changed their state simultaneously. If only one station does (the common case),
it is not a big difference whether one flushes/floods its MAC address or the
updated bitmask--the size of the message is approx the same, and the frequency
is still the same.

--
Alex

---

From: ruwhite at cisco.com (Russ White)
Date: Fri, 4 Mar 2005 09:51:58 -0500 (Eastern Standard Time)

>  often. We would need something better than that for rbridges to scale.

Hmmm... A simple thought is if there are no "traditional" bridges between 
you and the attached host, you could rely on simple link state, right? In 
other words, assuming the host is directly attached to an rbridge, there's 
really no reason the link would be up with the host down.

(There are exceptions for ethernet and other oddities, and we're not going 
to solve those very easily for all cases, so let's consider them an 
exception, for now, and work with the majority of cases).

So, what we could do is:

-- Use some "magic" to determine if we're directly connected to the 
attached host.

-- If we are, then just consider the link state the actual state, just like 
in a real link state protocol. :-)

-- If we aren't, either use probing, or just use normal bridge techniques 
(learn etc).

Thoughts? It would, at least, reduce the number of cases where we would 
need some technique other than simple link state to a minimal, and possible 
none in many networks.

:-)

Russ

__________________________________
riw at cisco.com CCIE <>< Grace Alone

---

From: Radia.Perlman at Sun.COM (Radia Perlman)
Date: Fri, 04 Mar 2005 10:32:39 -0800

I agree with Russ. Simplifications/optimizations are possible, depending 
on the
type of link. If the DB knows a port is not shared media...that it's 
only a pt-to-pt link
with no intervening bridges, then certainly it seems like a good
idea to do what Russ says below. Also, when we
know a link isn't shared media, we can do another optimization Alex 
suggested earlier (routing towards the exit RBridge rather than the
next hop RBridge). The hop-by-hop specifics of exactly what the
encapsulation header looks like, and various other strategies like how
to learn who is attached, are really link type
specific.

Radia

Russ White wrote:

>_______________________________________________
>rbridge mailing list
>rbridge at postel.org
>http://www.postel.org/mailman/listinfo/rbridge
>  
>

---

From: Cheng-Yin.Lee at alcatel.com (Cheng-Yin Lee)
Date: Fri, 04 Mar 2005 14:49:42 -0500

Alex, Radia,

> updated bitmask--the size of the message is approx the same, and the frequency

One thought (to overcome Alex's concerns with link state dissemination of MAC
addresses) is to have the remote RBridge acts as a  "Proxy MAC" (analogous to Proxy
ARP) for its attached hosts.

E.g : X ARP for Y,  Y responds but DstR intercepts the ARP Reply and replies with
its own MAC address, MAC R.
DstR have to cache the attached IP Y address to MAC Y address

X sends pkt to Y with DstR's MAC addresss MAC R.. DstR replaces the dest MAC address
with Y's real MAC address, MAC Y.
=> RBridges flood MAC addresses link states of RBridges,  but not MAC addresses of
hosts.
There would be n MAC addresses link states  if there are n RBridges in the network.

Regards
Cheng-Yin

---

From: sommerfeld at sun.com (Bill Sommerfeld)
Date: Fri, 04 Mar 2005 14:57:18 -0500

On Fri, 2005-03-04 at 13:32, Radia Perlman wrote:
> If the DB knows a port is not shared media...that it's 
> only a pt-to-pt link with no intervening bridges, 

I think you mean "the DB's admin knows".

I suspect there are few situations where a bridge could know *for sure* 
that that there can be only one mac address on the other end of the link.  
There could be a hub.. there could be a bridge told not to talk STP..
could be a host which uses multiple source mac addresses.

on the other hand, "I've only seen one source mac address so far and I 
haven't heard any STP" might be a good enough heuristic in practice.

						- Bill

---

From: zinin at psg.com (Alex Zinin)
Date: Fri, 4 Mar 2005 12:31:57 -0800

Yes, this would work, and would most probably represent the largest part of
station attachments in today deployments. There are corner cases, like a
mini-hub in a cubicle with a single station attached to it, but we don't
optimize for those and a probing-based safe-fail should take care of them.

---

From: zinin at psg.com (Alex Zinin)
Date: Fri, 4 Mar 2005 15:09:50 -0800

Bill,

  Unfortunately, node-local knowledge is insufficient. The edge rbridges
  need to know what dst mac to put in the frame, and the internal nodes
  need to know whether to install mac entries for all end stations or
  only other rbridges. So the knowledge and behavior must be consistent
  throughout the network.

---

From: ruwhite at cisco.com (Russ White)
Date: Fri, 4 Mar 2005 21:01:47 -0500 (Eastern Standard Time)

> Yes, this would work, and would most probably represent the largest part 
> of station attachments in today deployments. There are corner cases, like 
> a mini-hub in a cubicle with a single station attached to it, but we 
> don't optimize for those and a probing-based safe-fail should take care 
> of them.

I assume all bridges use BPDU's? If so, could we listen for those, and if 
we don't hear them, simply assume the link is point-to-point? Another thing 
we could look for would be multiple source mac addresses (?).

I think those are the two pieces of "magic" that come to mind without 
spending a lot of time thinking about it.....

:-)

Russ

---

From: zinin at psg.com (Alex Zinin)
Date: Fri, 4 Mar 2005 21:03:11 -0800

> I assume all bridges use BPDU's?

They start sending/processing BPDUs when STP is enabled, otherwise they're
silently flooding/learning/forwarding.

> If so, could we listen for those, and if
> we don't hear them, simply assume the link is point-to-point?

Presence of BPDUs unambiguously identifies a bridge on the port. However,
absence of them does not.

> Another thing 

This will work most of the time, except for the hub case I mentioned:

  +---+
  | Sw|-----[Hub]---[E]
  +---+

The switch sees one link, one MAC. If the Sw-Hub link is down, it does mean that
E is unavailable. However, if that link is up, it is still possible for E to be
unavailable because link Hub-E is down.

I think the above should be good enough, as long as we assume that we're
announcing _reachability of a specific MAC address, rather than momentary
connectivity to the station that uses it. This should go well with the
"presumption of reachability" I mentioned in a previous message to Radia.

Alex

---

From: Radia.Perlman at Sun.COM (Radia Perlman)
Date: Wed, 09 Mar 2005 07:59:43 -0800

There are various ways that we can optimize for VLANs, and as usual, the 
choices are
a continuum of tradeoffs between optimality of memory, bandwidth, 
complexity, etc.

One thing we should do is have RBridges announce which VLANs they are 
supporting
for endnodes. This would have to be configured, which I believe it is 
done for bridges.

So each RBridge knows, for each of its links, which VLANs are allowed on 
that link.
It announces this information in its link state information.

Now all RBridges know which RBridges are attached to which VLANs.

This now allows confining the broadcast domains. Unknown destinations or 
ARP/ND
queries only need to be sent to Designated RBridges attached to the VLAN 
in which
the packet originated. Depending on the amount of traffic which is 
unicast vs
needing to be flooded (within the VLAN), there is a range of choices of 
how to get
a packet to all the nodes within the VLAN. These are the same choices as 
for multicast,
which I summarized in an earlier message, but basically it's
a) send through a spanning tree to all RBridges, and DRs only flood onto 
their LAN
to endnodes if the packet is for the right VLAN (if we did this we 
wouldn't even
need to announce in link state packets which VLANs RBridge supported)
b) send through the same single spanning tree to all RBridges, but an 
RBridge looks
downstream, and stops forwarding if there are no RBridges supporting 
that VLAN further down
c) compute per-source-RBridge trees, and when RBridge R floods a packet 
for VLAN A,
the flooding will be done based on the tree rooted at R, and pruning 
will also be done,
as per point b.

Now for known endnodes:
Especially since someone told me that people want the capability to have 
overlapping
MAC address spaces among VLANs (the node with MAC address "m" in VLAN A
might be totally different from the node "m" in VLAN B), RBridges, in 
their link
state information, should tag what VLAN "m" belongs to.

Given that R knows what VLANs MAC addresses belong to, if R does not support
VLAN B, then there is no reason for R to put MAC addresses for B in its
forwarding table. But if the endnode information is in the regular link 
state information
(assume that for now), then R will need to store it so R can participate 
in link state
flooding.

Now another optimization: Suppose you want to avoid making R know about any
endnodes except in VLANs that R supports.

Then we could do the distribution of endnode information separately from the
rest of the link state information (the "regular stuff" is the connectivity
of the network consisting of RBridges, and tagging which RBridges are in 
which
VLANs).

If R is in VLAN A, then R must inform all the other RBridges attached to 
VLAN A
of all of R's VLAN A attached endnodes. If there were enough VLAN A peers in
the campus, it would probably be simplest to just use the regular link state
flooding to distribute the information. However, if that isn't the case, 
then
the VLAN A RBridge peers could talk to each other across the cloud to 
separately
distribute their endnode information. For instance, it could be sent as
a VLAN A flood, which the core would know how to do (as per the beginning of
this note).

Now, if non-VLAN-A RBridges do not know about the MAC addresses in A,
that can't be what they base their forwarding decision on.

If RBridge is working over MPLS, this isn't a problem, since the MPLS
path leads to the egress RBridge.

If there were only pt-to-pt links (no shared media) we could have the
encapsulation header point to the egress RBridge.

But on shared media, what we can do, at a cost of only 6 additional
bytes, is to also put "egress RBridge ID" into the encapsulation header.

So before on Ethernets a packet being forwarded by RBridges looked like:

outer header: source=transmitting RBridge, dest=nexthop RBridge, protocol
type=to be defined
encapsulation header: TTL
original frame

But by making the encapsulation header include "destination RBridge",
and having the RBridges along the path forward based on that, then
they wouldn't need to be forwarding based on endnode MACs, only
RBridge MACs.

Radia

---

From: touch at ISI.EDU (Joe Touch)
Date: Thu, 10 Mar 2005 10:32:52 -0800

IMO, VLAN support requires a few things:

	a) a way to assign an rbridge port to a VLAN

	b) separate forwarding tables and routing protocol instances
	   for each VLAN, inside the rbridge campus

		which thus contains the MAC addresses on each VLAN
		sufficiently

Other than that, what is hard? and wouldn't these take care of the stuff 
below?

Joe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : http://www.postel.org/pipermail/rbridge/attachments/20050310/2bfca609/signature.bin

---

From: zinin at psg.com (Alex Zinin)
Date: Thu, 10 Mar 2005 12:52:39 -0600

Joe,

 I explained issues with multi-instance routing in one of the previous
 threads.

---

From: dino at cisco.com (Dino Farinacci)
Date: Thu, 10 Mar 2005 11:48:21 -0800

>> the flooding will be done based on the tree rooted at R, and pruning 

    d) Use IGMP-snooping to further constrain the forwarding to only where
       there are group members. Can be added to schemes a) through c) above.

    e) Put group membership in LSPs ala MOSPF and use per-source-Rbridge trees.
 
    I think in this environment (where there are less protocols than in IP), 
    that e) might be the best way to go. Typically in layer-2 networks, there 
    is less diameter but more fanout, so you can get the benefits of source
    aggregation per attached switch.

    Flooding of LSPs are pretty fast, incremental Dijkstra's have been
    optimized so good join and prune latency can be acheived.

    In the case of e), IGMP-snooping is not used as the traditional way but 
    the IGMP protocol is used as a link-local protocol as in layer-3.
    That is, received IGMP reports would dictate what groups are put in an
    LSP by an attached DR.

Dino

---

From: touch at ISI.EDU (Joe Touch)
Date: Thu, 10 Mar 2005 19:32:58 -0800

> optimize for those and a probing-based safe-fail should take care of them.

That sort of probing can cause large amounts of broadcasts outside the 
rbridge campus, notably which may cascade into a subsequent rbridge 
(imagine two campuses that get connected by a hub).

What about this case (the direct attached one) is so significantly worth 
optimizing?

Joe
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : http://www.postel.org/pipermail/rbridge/attachments/20050310/5cfc3662/signature.bin