[RPRWG] A topology discovery algorithm for RPR

[Brian Holden <Brian_Holden@xxxxxxxxxxxxxx>]

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