Re: [RPRWG] A topology discovery algorithm for RPR
Brian, thank you for bringing up details that we will need to address within
the standard. I am not sure what the right solution is yet. However, we
would be remiss if we did not fully understand the way this problem has been
addressed in the past. I refer all that want to understand the background
to begin by studying the Token Ring Standard, 4.1.6.2 Neighbor Notification
process (on page 52 of ISO/IEC8802-5, ANSI/IEEE Std 802.5). I am not
suggesting that we copy that process, but just understand its operation,
what it accomplishes, and how it accomplishes it. For those that are a bit
more ambitious, I strongly recommend reading all of the 802.5 Clause 4,
Token Ring Protocols, more to understand the functionality it provides, than
to copy what it does.
Best regards,
Robert D. Love
Chair, Resilient Packet Ring Alliance
President, LAN Connect Consultants
7105 Leveret Circle Raleigh, NC 27615
Phone: 919 848-6773 Mobile: 919 810-7816
email: rdlove@xxxxxxxx Fax: 208 978-1187
----- Original Message -----
From: "Brian Holden" <Brian_Holden@xxxxxxxxxxxxxx>
To: <stds-802-17@xxxxxxxx>
Cc: "Heng Liao" <Heng_Liao@xxxxxxxxxxxxxx>; "Tom Alexander"
<Tom_Alexander@xxxxxxxxxxxxxx>; "Stuart Robinson"
<Stuart_Robinson@xxxxxxxxxxxxxx>
Sent: Wednesday, May 30, 2001 11:26 PM
Subject: [RPRWG] A topology discovery algorithm for RPR
>
>
> All,
>
> I was kicking around some ideas of how to get a distributed
> topology discovery algorithm for RPR that would be:
>
> 1) robust
> 2) not require a separate station numbering scheme
> 3) simple
>
>
> Here is one possiblity. There are likely many other ways to
> solve this problem - so feel free to shoot holes in this one!
>
> This algorithm requires:
> 1) That each station on the ring must have a separate 48-bit MAC address
just for control traffic
> 2) That we have a ring topology (although it may be extensible to a mesh)
> 3) That we have a means of sending traffic one and only one hop to each
> of a station's neighbors. This can be accomplished by:
> a) providing a well-known MAC address for one-hop traffic (my
preference)
> b) having a bit in the RPR shim which says it is one hop traffic
> c) some other mechanism
>
> The algorithm is:
> 1) Every T1*ms (forever) each station sends a one-hop MAC-Query message
on its East and West
> links which requests the MAC address of his immediate neighbors
> (along with an authentication field)
> 2) Upon receipt of a MAC-Query message, a station responds with its MAC
address
> (along with an authentication field)
> 3) If a MAC-Query is not received in T2*ms, a station records the fact
that it has no neighbor
> 4) If a MAC-Query response is not received in N attempts, the station
records the fact that it
> has no neighbor
> 5) Every T3*ms (forever) each station sends a broadcast message
containing
> a) its MAC address
> b) its East neighbor's MAC address (or absence)
> c) its West neighbor's MAC address (or absence)
> d) its capabilities
> e) the capabilities of its East Link
> f) the capabilities of its West Link
> g) (an authentication field)
> 6) Upon receipt of one of the broadcast messages, each node updates its
topology database.
> The MAC addresses in the message payload can be matched up with the
current database
> entries to find the complete set of neighbors in the ring.
>
>
>
> There are several good properties to this algorithm.
> 1) The actions of each station are largely stateless
> 2) There is no master node
> 3) There is no separate numbering system beyond the MAC addresses of the
station
> (numbering systems bring their own set of problems like when partitions
occur in
> a running system, then nodes are added separately to the partitions, then
the
> partition is healed)
> 4) The end result is that each node has a dynamically updated full
topology database of
> connectivity, control MAC addresses, and capabilities for the stations
around the ring
>
>
> Looking for some good feedback.
>
> Thanks,
> Brian Holden
>
>
> _______________________________________________
> Brian Holden PMC-Sierra, Inc.
> 3975 Freedom Circle, Santa Clara CA USA
> +1.408.239.8123 Fax +1.408.492.9862
> brian_holden@xxxxxxxxxxxxxx http://www.pmc-sierra.com
>
>
>